include/sieve/class_tree.inc

   1 <?php
   2
   3 class Tree
   4 {
   5         var $childs_;
   6         var $parents_;
   7         var $nodes_;
   8         var $maxId_;
   9         var $dumpFn_;
  10         var $dump_;
  11
  12         function Tree(&$root)
  13         {
  14                 $this->_construct($root);
  15         }
  16
  17         function _construct(&$root)
  18         {
  19                 $this->childs_ = array();
  20                 $this->parents_ = array();
  21                 $this->nodes_ = array();
  22                 $this->maxId_ = 0;
  23
  24                 $this->parents_[0] = null;
  25                 $this->nodes_[0] = $root;
  26         }
  27
  28         function addChild(&$child)
  29         {
  30                 return $this->addChildTo($this->maxId_, $child);
  31         }
  32
  33         function addChildTo($parent_id, &$child)
  34         {
  35                 if (!is_int($parent_id) ||
  36                     !isset($this->nodes_[$parent_id]))
  37                 {
  38                         return null;
  39                 }
  40
  41                 if (!isset($this->childs_[$parent_id]))
  42                 {
  43                         $this->childs_[$parent_id] = array();
  44                 }
  45
  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);
  50
  51                 return $child_id;
  52         }
  53
  54         function getRoot()
  55         {
  56                 if (!isset($this->nodes_[0]))
  57                 {
  58                         return null;
  59                 }
  60
  61                 return 0;
  62         }
  63
  64         function getParent($node_id)
  65         {
  66                 if (!is_int($node_id) ||
  67                     !isset($this->nodes_[$node_id]))
  68                 {
  69                         return null;
  70                 }
  71
  72                 return $this->parents_[$node_id];
  73         }
  74
  75         function getChilds($node_id)
  76         {
  77                 if (!is_int($node_id) ||
  78                     !isset($this->nodes_[$node_id]))
  79                 {
  80                         return null;
  81                 }
  82
  83                 if (!isset($this->childs_[$node_id]))
  84                 {
  85                         return array();
  86                 }
  87
  88                 return $this->childs_[$node_id];
  89         }
  90
  91         function getNode($node_id)
  92         {
  93                 if (!is_int($node_id) ||
  94                     !isset($this->nodes_[$node_id]))
  95                 {
  96                         return null;
  97                 }
  98
  99                 return $this->nodes_[$node_id];
 100         }
 101
 102         function setDumpFunc($callback)
 103         {
 104                 if ($callback == NULL || is_callable($callback))
 105                 {
 106                         $this->dumpFn_ = $callback;
 107                 }
 108         }
 109
 110         function dump()
 111         {
 112                 $this->dump_ = "tree\n";
 113                 $this->doDump_(0, '', true);
 114                 return $this->dump_;
 115         }
 116
 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                 }
 129
 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                 }
 139
 140                 if (isset($this->childs_[$node_id]))
 141                 {
 142                         $childs = $this->childs_[$node_id];
 143                         $last_child = count($childs);
 144
 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 }
 152
 153 ?>