1 <?php
3 class Tree
4 {
5 var $childs_;
6 var $parents_;
7 var $nodes_;
8 var $maxId_;
9 var $dumpFn_;
10 var $dump_;
12 function Tree(&$root)
13 {
14 $this->_construct($root);
15 }
17 function _construct(&$root)
18 {
19 $this->childs_ = array();
20 $this->parents_ = array();
21 $this->nodes_ = array();
22 $this->maxId_ = 0;
24 $this->parents_[0] = null;
25 $this->nodes_[0] = $root;
26 }
28 function addChild(&$child)
29 {
30 return $this->addChildTo($this->maxId_, $child);
31 }
33 function addChildTo($parent_id, &$child)
34 {
35 if (!is_int($parent_id) ||
36 !isset($this->nodes_[$parent_id]))
37 {
38 return null;
39 }
41 if (!isset($this->childs_[$parent_id]))
42 {
43 $this->childs_[$parent_id] = array();
44 }
46 $child_id = ++$this->maxId_;
47 $this->nodes_[$child_id] = $child;
48 $this->parents_[$child_id] = $parent_id;
49 array_push($this->childs_[$parent_id], $child_id);
51 return $child_id;
52 }
54 function getRoot()
55 {
56 if (!isset($this->nodes_[0]))
57 {
58 return null;
59 }
61 return 0;
62 }
64 function getParent($node_id)
65 {
66 if (!is_int($node_id) ||
67 !isset($this->nodes_[$node_id]))
68 {
69 return null;
70 }
72 return $this->parents_[$node_id];
73 }
75 function getChilds($node_id)
76 {
77 if (!is_int($node_id) ||
78 !isset($this->nodes_[$node_id]))
79 {
80 return null;
81 }
83 if (!isset($this->childs_[$node_id]))
84 {
85 return array();
86 }
88 return $this->childs_[$node_id];
89 }
91 function getNode($node_id)
92 {
93 if (!is_int($node_id) ||
94 !isset($this->nodes_[$node_id]))
95 {
96 return null;
97 }
99 return $this->nodes_[$node_id];
100 }
102 function setDumpFunc($callback)
103 {
104 if ($callback === NULL || is_callable($callback))
105 {
106 $this->dumpFn_ = $callback;
107 }
108 }
110 function dump()
111 {
112 $this->dump_ = "tree\n";
113 $this->doDump_(0, '', true);
114 return $this->dump_;
115 }
117 function doDump_($node_id, $prefix, $last)
118 {
119 if ($last)
120 {
121 $infix = '`--- ';
122 $child_prefix = $prefix . ' ';
123 }
124 else
125 {
126 $infix = '|--- ';
127 $child_prefix = $prefix . '| ';
128 }
130 $node = $this->nodes_[$node_id];
131 if ($this->dumpFn_ !== NULL)
132 {
133 $this->dump_ .= $prefix . $infix . call_user_func($this->dumpFn_, $node) . "\n";
134 }
135 else
136 {
137 $this->dump_ .= "$prefix$infix$node\n";
138 }
140 if (isset($this->childs_[$node_id]))
141 {
142 $childs = $this->childs_[$node_id];
143 $last_child = count($childs);
145 for ($i=1; $i <= $last_child; ++$i)
146 {
147 $this->doDump_($childs[$i-1], $child_prefix, ($i == $last_child ? true : false));
148 }
149 }
150 }
151 }
153 ?>