CODEWITHSUNDEEP
phparrayssorting
Jeremy Harris
Jeremy Harris

Reputation: 24549

Algorithm: Category Tree Sorting

I've setup an "infinite depth" category system which is stored in the database with three important pieces of information:

The first two are self explanatory, but the last one needs some clarification. If the category is #20, it's parent is #10, and the parent's parent is #5, then the NodePath would look like 5:10:20. In this way I can recursively find a categories parent branch.

I'm looking for a way to get every category from the database, and then sort them in some way where the result is an array like this:

array(
   0 => array(
      3 => array(
         7,
         13,
      ),
      5,
   ),
   1 => array(
      6,
      9
   ),
);

Essentially, this is a map of the tree hierarchy created from the NodePath structure described before.

I've come up with something like this:

 $tree = array();

 foreach( $categories as $category )
 {
    // A NodePath Example is "1:7:13:24" where 1 is the root category,
    // 24 is the "leaf" or end node, and the other numbers are sub categories
    // in order.
    $nodes = explode( ":", $category->NodePath );

    $lastNode = &$tree;
    foreach( $nodes as $node )
    {
        // Add New Branch if not Termination
        if( !isset( $lastNode[ $node ] ) && $node != end($nodes) )
            $lastNode[ $node ] = array();

        // Recursive Addressing
        $lastNode = &$lastNode[ $node ];
    }        
 }

Which produces this var_dump() of the tree (which matches the data in my database):

array (size=3)
  1 => 
    array (size=1)
      4 => null
  2 => 
    array (size=2)
      5 => 
        array (size=1)
          7 => &null
      6 => null
  3 => null

The third depth down sets terminal nodes as "&null" instead of just "null". How can I fix this?

Upvotes: 2

Views: 1289

Answers (2)

Saic Siquot
Saic Siquot

Reputation: 6513

<?php


function builTree($categories){
    $tree = array();
    foreach($categories as $category){
        $path = explode( ":", $category->NodePath );
        $lastNode = &$tree;
        for($deep=0;$deep<count($path);$deep++){
             if(!is_array($lastNode[$path[$deep]])) {
                 if($deep==count($path)-1) { $lastNode[$path[$deep]] = null;}
                 else {$lastNode[$path[$deep]] = array(); $lastNode = &$lastNode[$path[$deep]];}
             } else {$lastNode = &$lastNode[$path[$deep]];}
        }
    }
    return $tree;
}


echo "<pre>";
// works with full tree given
$categories = [
    (object)['NodePath' => '1'],
    (object)['NodePath' => '1:4'],
    (object)['NodePath' => '2'],
    (object)['NodePath' => '2:5:7:90:23'],
    (object)['NodePath' => '2:6'],
    (object)['NodePath' => '3'],
    (object)['NodePath' => '2:5'],
    (object)['NodePath' => '3:1']     // even works with loop paths
];
print_r(builTree($categories));


// works even if just leafs are given
$categories = [
(object)['NodePath' => '2:5:7:90:23'],
(object)['NodePath' => '2:5:7:66:21']
];
print_r(builTree($categories));

Upvotes: 0

Expedito
Expedito

Reputation: 7795

It only happens with the very last item in your array, so one way to fix it is to add a NULL value to the end of $categories and then remove it afterwards with array_filter:

$categories = [
    (object)['NodePath' => '1'],
    (object)['NodePath' => '1:4'],
    (object)['NodePath' => '2'],
    (object)['NodePath' => '2:5:7'],
    (object)['NodePath' => '2:6'],
    (object)['NodePath' => '3'],
    (object)['NodePath' => '2:5'],
    (object)['NodePath' => '3:1']
];

$tree = array();
$categories[] = (object)array('NodePath' => NULL);
foreach( $categories as $category ){
   $nodes = explode( ":", $category->NodePath );
   $lastNode = &$tree;
   foreach( $nodes as $node ){
       // Add New Branch if not Termination
       if( !isset( $lastNode[ $node ] ) && $node != end($nodes) ){
           $lastNode[ $node ] = array();
       }
       // Recursive Addressing
       $lastNode = &$lastNode[ $node ];
   }        
}
$tree = array_filter($tree);
var_dump($tree);

Here's the dump which without doing what I said had & before the last value. I also tried rearranging elements in the categories array, and it worked the same.

array(3) { [1]=> array(1) { [4]=> NULL } [2]=> array(2) { [5]=> array(1) { [7]=> NULL } [6]=> NULL } [3]=> array(1) { [1]=> NULL } }

Upvotes: 1

Related Questions