Algorithm: Category Tree Sorting

Question

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

Category ID
Parent Category ID
NodePath

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?

Expedito · Accepted Answer · 2013-08-14 20:57:37Z

1

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 } }

edited Aug 14, 2013 at 20:57

answered Aug 14, 2013 at 20:33

Expedito

7,8095 gold badges32 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jeremy Harris Over a year ago

I've tried that. Setting NodePath to NULL means the explode will return nothing and hence the loop will never run. So it's essentially like that added null node never existed.

Expedito Over a year ago

@cillosis - I updated my code to show the exact code that I'm running with the result.

Expedito Over a year ago

@cillosis - You're also mistaken. Try running the following var_dump(explode(":", NULL)); You get an array with an empty string, so the loop is actually being entered, and it does show up in the array $tree if the array_filter line is omitted.

Saic Siquot · Accepted Answer · 2013-08-14 22:08:06Z

0

<?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));

answered Aug 14, 2013 at 22:08

Saic Siquot

6,5135 gold badges37 silver badges56 bronze badges

1 Comment

Saic Siquot Over a year ago

@cillosis, did you try this? did I miss something?

Collectives™ on Stack Overflow

Algorithm: Category Tree Sorting

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related