API tools faq
paste
lignite0

node.php -- Klasa do przechodzenia po drzewach

lignite0
Apr 21st, 2016
253
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 12.78 KB | None | 0 0
raw download clone embed print report
  1. <?php
  2.  
  3. class Node implements \IteratorAggregate
  4. {
  5.     public $id = 0;
  6.     public $pid = 0;    
  7.     public $pos = 0;    
  8.     //public $data = null;    
  9.    
  10.     protected $parent = null;    
  11.     protected $children = [];
  12.  
  13.     public function __construct($id, $pid, $pos, $data)
  14.     {
  15.         $this->id = $id;
  16.         $this->pid = $pid;
  17.         $this->pos = $pos;
  18.         //$this->data = $data;
  19.     }
  20.    
  21.     public static function createBranch(&$parents, $children)
  22.     {
  23.         $tree = array();
  24.         foreach ($children as $child) {
  25.             if (isset($parents[$child->id])) {                
  26.                 $child->setChildren(self::createBranch($parents, $parents[$child->id]));
  27.             }
  28.             $tree[$child->id] = $child;
  29.         }
  30.         return $tree;
  31.     }
  32.    
  33.     public static function createTreeObject(array $array, $rootID = 0, $fieldID = 'id', $fieldPID = 'pid', $fieldPos = 'pos')
  34.     {
  35.         $parents = array();
  36.         foreach ($array as $element) {
  37.             $node = new static($element->$fieldID, $element->$fieldPID, $element->$fieldPos, $element);
  38.             $nodes[$node->id] = $node;
  39.             $parents[$node->pid][$node->id] = $node;
  40.         }
  41.        
  42.         if ($rootID > 0) {
  43.             $root = $nodes[$rootID];
  44.         } else {
  45.             $root = new static(0, 0, 1, 0);
  46.         }
  47.        
  48.         $root->setChildren(self::createBranch($parents, $parents[$rootID]));
  49.         return $root;
  50.     }
  51.        
  52.     public function debug()
  53.     {
  54.         $count = 1;
  55.         $this->printDebugTree($count, 0);
  56.     }
  57.    
  58.     public function debugSelf()
  59.     {
  60.         echo 'nod - id:'.intval($this->id);
  61.         echo ' - pid:'.intval($this->pid);
  62.         echo ' - pos:'.intval($this->pos);
  63.         echo ' ---- p:'.($this->getParent()?'t':'f');
  64.         echo ' c:'.count($this->getChildren());
  65.         echo ' o:'.count($this->getDescendants());
  66.         echo ' a:'.count($this->getAncestors());
  67.         echo PHP_EOL;
  68.     }
  69.    
  70.     public function getAncestor($id)
  71.     {      
  72.         $node = $this;
  73.         do {
  74.             $parent = $node->getParent();
  75.             if ($parent and $parent->id == $id) {
  76.                 return $parent;
  77.             }
  78.             $node = $parent;
  79.         } while ($parent);        
  80.         return null;
  81.     }
  82.    
  83.     public function getAncestorRecursive($id)
  84.     {
  85.         $parent = $this->getParent();
  86.     }
  87.    
  88.     public function getAncestors()
  89.     {
  90.         $ancestors = [];
  91.         $this->getAncestorsRecursive($ancestors);
  92.         return $ancestors;
  93.     }
  94.    
  95.     protected function getAncestorsRecursive(&$ancestors)
  96.     {
  97.         $parent = $this->getParent();
  98.         if ($parent) {
  99.             $ancestors[$parent->pos] = $parent;
  100.             $parent->getAncestorsRecursive($ancestors);
  101.         }
  102.     }
  103.    
  104.     public function getBrother($id)
  105.     {
  106.         $parent = $this->getParent();
  107.         return $parent?$parent->getChild($id):null;
  108.     }
  109.    
  110.     public function getChild($id)
  111.     {
  112.         if (isset($this->children[$id])) {
  113.             return $this->children[$id];
  114.         }
  115.         return null;
  116.     }
  117.    
  118.     public function getChildren()
  119.     {
  120.         return $this->children;
  121.     }
  122.    
  123.     public function getDescendant($id)
  124.     {
  125.         if (isset($this->children[$id])) {
  126.             return $this->children[$id];
  127.         }
  128.         foreach($this->children as $child) {
  129.             $result = $child->getDescendant($id);
  130.             if ($result) {
  131.                 return $result;
  132.             }
  133.         }
  134.         return null;
  135.     }
  136.    
  137.     public function getDepth()
  138.     {
  139.         $depth = 0;
  140.         $node = $this;
  141.         while ($node = $node->getParent()) {
  142.             $depth++;
  143.         }
  144.         return $depth;
  145.     }
  146.    
  147.     public function getDepthMax()
  148.     {
  149.         $max = 0;
  150.         return $this->getDepthMaxRecursive(0, $max);
  151.     }
  152.    
  153.     protected function getDepthMaxRecursive($depth, &$max)
  154.     {        
  155.         if ($depth > $max) {
  156.             $max = $depth;
  157.         }
  158.         foreach ($this->children as $child) {
  159.             $child->getDepthMaxRecursive($depth+1, $max);
  160.         }
  161.         return $max;
  162.     }
  163.    
  164.     public function getDepthRelative($id)
  165.     {
  166.         $depth = 0;
  167.         $node = $this;
  168.         while ($node = $node->getParent()) {
  169.             $depth++;
  170.             if ($node->id == $id) {
  171.                 return $depth;
  172.             }
  173.         }
  174.        
  175.         $depth = 0;
  176.         $node = $this->getDescendant($id);
  177.         while ($node and $node = $node->getParent()) {
  178.             $depth--;
  179.             if ($node->id == $this->id) {
  180.                 return $depth;
  181.             }
  182.         }
  183.        
  184.         return $this->getBrother($id) ? 0 : null;
  185.     }
  186.    
  187.     public function getIterator()
  188.     {
  189.         return new \ArrayIterator($this->children);
  190.     }
  191.    
  192.     public function getDescendants()
  193.     {
  194.         $descendants = [];
  195.         $this->getDescendantsRecursive($descendants);
  196.         return $descendants;
  197.     }
  198.    
  199.     protected function getDescendantsRecursive(&$descendants)
  200.     {
  201.         foreach ($this->children as $child) {
  202.             $descendants[$child->pos] = $child;
  203.             $child->getDescendantsRecursive($descendants);
  204.         }
  205.     }
  206.    
  207.     public function getParent()
  208.     {
  209.         return $this->parent;
  210.     }
  211.    
  212.     public function getRoot()
  213.     {
  214.         $node = $this;
  215.         do {
  216.             if ($node and $node->isRoot()) {
  217.                 return $node;
  218.             }
  219.             $node = $node->getParent();
  220.         } while ($node);    
  221.        
  222.         return null;
  223.     }
  224.    
  225.     public function getSiblings()
  226.     {
  227.         $parent = $this->getParent();
  228.         return $parent?$parent->getChilden():null;
  229.     }
  230.            
  231.     public function isChildren($id)
  232.     {
  233.         $root = $this->getRoot();
  234.         $node = $root->getDescendant($id);
  235.         if ($node) {            
  236.             return array_key_exists($this->id, $node->getChildren());
  237.         }
  238.         return null;
  239.     }
  240.    
  241.     public function isDescendant($id)
  242.     {
  243.         return array_key_exists($id, $this->getAncestors());
  244.     }
  245.    
  246.     public function isRoot()
  247.     {
  248.         return $this->getParent()?false:true;
  249.     }
  250.    
  251.     protected function printDebugTree(&$count, $level)
  252.     {
  253.         echo sprintf('%03d', $count).' ';
  254.         if ($level > 0 ) {
  255.             echo implode(' ', array_fill(0, $level, '---')).' ';
  256.         }
  257.         $this->debugSelf();
  258.         foreach ($this->getChildren() as $child) {            
  259.             $count += 1;
  260.             $child->printDebugTree($count, $level + 1);
  261.         }
  262.     }
  263.    
  264.     protected function setChildren($tree)
  265.     {
  266.         $this->children = $tree;
  267.         foreach ($this->children as $child) {
  268.             $child->setParent($this);
  269.         }
  270.         return true;
  271.     }
  272.    
  273.     protected function setParent(self $parent)
  274.     {
  275.         $this->parent = $parent;
  276.         return true;
  277.     }
  278. }
  279.  
  280. class Record
  281. {
  282.     public $id = 0;
  283.     public $pid = 0;
  284.     public $name = 0;
  285. }
  286.  
  287. class PageNode extends Node
  288. {
  289.     public $name = '';
  290. }
  291.  
  292. /* Recursive branch extrusion */
  293. function createBranch(&$parents, $children) {
  294.    
  295.     $tree = array();
  296.     foreach ($children as $child) {
  297.         if (isset($parents[$child['id']])) {
  298.             $child['children'] = createBranch($parents, $parents[$child['id']]);
  299.         }
  300.         $tree[] = $child;
  301.     }
  302.     return $tree;
  303. }
  304.  
  305. /* Initialization */
  306. function createTree($flat, $root = 0) {
  307.     $parents = array();
  308.     foreach ($flat as $a) {
  309.         $parents[$a['parent']][] = $a;
  310.     }
  311.     return createBranch($parents, $parents[$root]);
  312. }
  313.  
  314. function r($id, $p, $n)
  315. {
  316.     return array('id' => $id, 'parent'=>$p, 'name'=>$n);
  317. }
  318. function r2($id, $p, $pos, $n)
  319. {
  320.     $r = new Record();
  321.     $r->id = $id;
  322.     $r->pid = $p;
  323.     $r->pos = $pos;
  324.     $r->name = $n;
  325.     return $r;
  326. }
  327.  
  328. $p = array(
  329.     r( 1,  0, 'strona_1'),
  330.     r( 2,  0, 'strona_2'),
  331.     r( 3,  0, 'strona_3'),
  332.     r( 4,  2, 'strona_4'),
  333.     r( 5,  2, 'strona_5'),
  334.     r( 6,  2, 'strona_6'),
  335.     r( 7,  4, 'strona_7'),
  336.     r( 8,  4, 'strona_8'),
  337.     r( 9,  8, 'strona_9'),
  338.     r(10,  8, 'strona_10'),
  339.     r(11,  1, 'strona_11'),
  340.     r(12,  3, 'strona_12'),
  341.     r(13,  3, 'strona_13'),
  342.     r(14,  3, 'strona_14'),
  343.     r(15,  12, 'strona_15'),
  344.     r(16,  12, 'strona_16'),
  345.     r(17,  16, 'strona_17'),
  346.     r(18,  10, 'strona_18'),
  347.     r(19,  10, 'strona_19'),
  348.     r(20,  19, 'strona_20'),
  349.     r(21,  8, 'strona_21'),
  350. );
  351.  
  352. $p2 = array(
  353.     r2( 1,  0,  1, 'strona_1'),
  354.     r2( 2,  0,  2, 'strona_2'),
  355.     r2( 3,  0,  3, 'strona_3'),
  356.     r2( 4,  2,  1, 'strona_4'),
  357.     r2( 5,  2,  2, 'strona_5'),
  358.     r2( 6,  2,  3, 'strona_6'),
  359.     r2( 7,  4,  1, 'strona_7'),
  360.     r2( 8,  4,  2, 'strona_8'),
  361.     r2( 9,  8,  1, 'strona_9'),
  362.     r2(10,  8,  2, 'strona_10'),
  363.     r2(11,  1,  1, 'strona_11'),
  364.     r2(12,  3,  3, 'strona_12'),
  365.     r2(13,  3,  2, 'strona_13'),
  366.     r2(14,  3,  1, 'strona_14'),
  367.     r2(15,  12, 1, 'strona_15'),
  368.     r2(16,  12, 1, 'strona_16'),
  369.     r2(17,  16, 1, 'strona_17'),
  370.     r2(18,  10, 1, 'strona_18'),
  371.     r2(19,  10, 2, 'strona_19'),
  372.     r2(20,  19, 1, 'strona_20'),
  373.     r2(21,  8,  3, 'strona_21'),
  374.     r2(28,  19, 2, 'strona_22'),
  375.     r2(23,  19, 3, 'strona_22'),
  376. );
  377.  
  378.  
  379. echo '$g = Node::createTreeObject($p, 0):'.PHP_EOL;
  380. $g = Node::createTreeObject($p2, 0);
  381. $g->debug();
  382.  
  383. echo PHP_EOL.'$f = Node::createTreeObject($p, 4):'.PHP_EOL;
  384. $f = Node::createTreeObject($p2, 4);
  385. $f->debug();
  386.  
  387. echo PHP_EOL.'foreach($f as $c) { $c->debug(); }:'.PHP_EOL;
  388. foreach($f as $c) { $c->debug(); }
  389.  
  390. echo PHP_EOL.'$f->getChild(8):'.PHP_EOL;
  391. $f->getChild(8)->debug();
  392.  
  393. echo PHP_EOL.'$g->getDescendant(10):'.PHP_EOL;
  394. $g->getDescendant(10)->debug();
  395.  
  396. echo PHP_EOL.'$g->getDescendant(10)->getDepth():'.PHP_EOL;
  397. var_dump($g->getDescendant(10)->getDepth());
  398.  
  399. echo PHP_EOL.'$g->getDescendant(2)->getDepthMax():'.PHP_EOL;
  400. var_dump($g->getDescendant(4)->getDepthMax());
  401.  
  402. echo PHP_EOL.'$g->getDescendant(20)->getDepthRelative(8):'.PHP_EOL;
  403. var_dump($g->getDescendant(20)->getDepthRelative(8));
  404.  
  405. echo PHP_EOL.'$g->getDescendant(8)->getDepthRelative(20):'.PHP_EOL;
  406. var_dump($g->getDescendant(8)->getDepthRelative(20));
  407.  
  408. echo PHP_EOL.'$g->getDescendant(7)->getDepthRelative(8):'.PHP_EOL;
  409. var_dump($g->getDescendant(7)->getDepthRelative(8));
  410.  
  411. echo PHP_EOL.'$g->getDescendant(10)->getAncestor(2)->debugSelf():'.PHP_EOL;
  412. $g->getDescendant(10)->getAncestor(2)->debugSelf();
  413.  
  414. echo PHP_EOL.'$g->getDescendant(10)->getParent()->getParent()->debugSelf():'.PHP_EOL;
  415. $g->getDescendant(10)->getParent()->getParent()->debugSelf();
  416.  
  417. echo PHP_EOL.'$g->isRoot():'.PHP_EOL;
  418. var_dump($g->isRoot());
  419.  
  420. echo PHP_EOL.'$g->getDescendant(10)->isDescendant(4):'.PHP_EOL;
  421. var_dump($g->getDescendant(10)->isDescendant(4));
  422.  
  423. echo PHP_EOL.'$g->getDescendant(8)->isChildren(4):'.PHP_EOL;
  424. var_dump($g->getDescendant(8)->isChildren(4));
  425.  
  426. echo PHP_EOL.'foreach($g->getDescendant(3)>getDescendants() as $c) { $c->debugSelf(); }:'.PHP_EOL;
  427. foreach($g->getDescendant(3)->getDescendants() as $c) { $c->debugSelf(); }
  428.  
  429. echo PHP_EOL.'foreach($g->getDescendant(20)->getAncestors() as $c) { $c->debugSelf(); }:'.PHP_EOL;
  430. foreach($g->getDescendant(20)->getAncestors() as $c) { $c->debugSelf(); }
  431.  
  432.  
  433. echo PHP_EOL.'----------------------------------------------------------------------------'.PHP_EOL;
  434.  
  435. /*
  436.  
  437. Node or null    $n->getChild($id);                  # zwróć dziecko o id
  438. array           $n->getChildren();                  # zwróć wszystkie dzieci
  439. Node or null    $n->getDescendant($id);             # zwróć potomka o id
  440. array           $n->getDescendants();               # zwróć wszyskich potomków
  441. Node or null    $n->getParent();                    # zwróć rodzica
  442. Node or null    $n->getAncestor($id);               # zwróć przodka o id
  443. array           $n->getAncestors();                 # zwróć wszystkich przodków
  444. Node            $n->getRoot();                      # zwróć korzeń drzewa
  445. Node or null    $n->getBrother($id);                # zwróć brata o id
  446. array           $n->getSiblings();                  # zwróć wszelkie rodzeństwo
  447.                        
  448. unsigned int    $n->getDepth();                     # zwróć zagłębienie względem korzenia
  449. unsigned int    $n->getDepthMax();                  # zwróć maksymalne zagłębienie względem węzła
  450. signed int      $n->getDepthRelative($id);          # zwróć zagłębienie względem węzła o id
  451.  
  452. bool            $n->isRoot($id);                    # Czy węzeł $n jest korzeniem?
  453. bool            $n->isDescendant($id);              # Czy węzeł $n jest potomkiem węzła o id?
  454. bool            $n->isChildren($id);                # Czy węzeł $n jest dzieckiem węzła o id?
  455.  
  456. */
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!