interface visitor {
public function visitRootNode($node);
public function visitLeafNode($node);
}
interface node {
public function accept(visitor $v);
public function getName();
}
class rootNode implements node {
public function accept(visitor $v) {
$v->visitRootNode($this);
}
public function getName() {
return 'Root';
}
}
class leafNode implements node {
private $name;
private $parent;
public function __construct($name, $parent) {
$this->name = $name;
$this->parent = $parent;
}
public function accept(visitor $v) {
if ($v->visitLeafNode($this)) {
$this->getParent()->accept($v);
}
}
public function getName() {
return $this->name;
}
public function getParent() {
return $this->parent;
}
public function setParent($parent) {
$this->parent = $parent;
}
}
class treeChecker implements visitor {
private $path = array();
public function reset() {
$this->path = array();
}
public function visitRootNode($node) {
$this->echoPath('Tree is ok', $node->getName());
return true;
}
public function visitLeafNode($node) {
if ($this->inPath($node)) {
$this->echoPath('Loop detected', $node->getName());
return false;
}
$this->path[] = $node;
if (!$node->getParent()) {
$this->echoPath('Dangling leaf reference', '?');
return false;
}
return true;
}
private function echoPath($message, $start) {
echo $message . ': <b>' . $start . '</b>';
for ($i = count($this->path) - 1; $i >= 0; --$i) {
echo ' -> ' . $this->path[$i]->getName();
}
echo '<br/>';
}
private function inPath($node) {
for ($i = count($this->path) - 1; $i >= 0; --$i) {
if ($this->path[$i] === $node) {
return true;
}
}
return false;
}
}
$trch = new treeChecker();
$tree = new leafNode('zzz', new leafNode('yyy', new leafNode('xxx', new rootNode())));
$tree->accept($trch);
$trch->reset();
$tree1 = new leafNode('aaa', new leafNode('bbb', new leafNode('ccc', null)));
$tree1->accept($trch);
$trch->reset();
$loop = new leafNode('loop', null);
$loop->setParent(new leafNode('mmm', new leafNode('lll', new leafNode('kkk', $loop))));
$loop->accept($trch);
