PHP: Sort data from nested sets

Question

We're currently building a website with a categorized MySQL table containing various competences, and we noticed that the nested set model would be optimized for this. Although, we've got a pretty serious problem - the nested set model doesn't allow any sorting, and we really need that possibility. I'd like the output data to be array(id, name, depth), as this function supports (though without any kind of sorting):

function tree()
{
    $query = 'SELECT node.id, node.name, (COUNT(parent.name) - 1) AS depth FROM test_competence AS node, test_competence AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY node.lft';
    $result = mysql_query($query) or die(mysql_error());

    while($data = mysql_fetch_assoc($result))
    {
     $returnarray[] = $data;
    }

    return $returnarray;
}

I've started with a function but have no idea how to continue:

function tree_sorted()
{
    //Get data
    $query = 'SELECT node.id, node.name, node.parent, (COUNT(parent.name) - 1) AS depth FROM test_competence AS node, test_competence AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY node.lft';
    $result = mysql_query($query) or die(mysql_error());

    //Fetch gotten data
    while($data = mysql_fetch_assoc($result))
    {
     $fetched[$data['depth']][$data['id']] = array($data['name'], $data['parent']);
    }

    //Sort fetched data
    foreach($fetched as $i => $row)
    {
     asort($row);
     $sorted[$i] = $row;
    }

    //Merge sorted data (???)
    foreach($sorted as $i => $arr)
    {
     foreach($arr as $x => $row)
     {
      $returnarray[] = array('id' => key($row), 'name' => $row[0], 'depth' => $x);
     }
    }

Any help would be greatly appreciated. I've googled for different ways to sort data from nested sets, but without any good result.

Thank you in advance.

EDIT: Now I've tried some with the uasort() function which feels to be the right way, but the problem still remain.

Answer 1

In my experience using the nested set model is not really necessary unless you expect some really heavy traffic. I'm not sure what exactly you need the hierarchy for, but I would recommend checking whether a simple parent-son-table with a cache in front of it wouldn't suffice, it's much easier to maintain and work with

Again, this of course depends on your application and how worried you are about performance issues.

Answer 2

Taking a stab in the dark, since nested set-tree data is, by definition, already sorted, it sounds like you need to convert the data into another format (usually a flat one) in order to sort it. The easiest way to achieve this is to simply work through the data, creating a flat dataset as you go.

You do already have a few options in the SQL. Ordering by the Left ID gets you in-order traversal, if I have the terminology correct. This is usually what people want when they list a set-tree as it makes sense when flattened into a list. I'd be experimenting with the ORDER BY clause in the SQL; for example, ordering by the depth parameter would give you a level-order traversal. Try combining that with node.name.

Answer 3

If you need sort a set of nodes in a tree, and maintain unlimited numbers of levels in the tree, might I recommend using pre-ordered tree traversal?

See http://dev.mysql.com/tech-resources/articles/hierarchical-data.html for an example implementation.

The point is that you maintain a left and right value for each node. You could also maintain a depth column for each node, which tells which level of the tree it is in. You can use these left and right values to sort nodes by their order in the tree, and use the depth value to only select a given number of levels of the tree.

The only notable downside of this approach is that you have to actively maintain those left and right values when altering the structure of the nodes.

Answer 4

here is my solution for sorting a nested set of values strictly in PHP.

     include('functions.php');
 $dbc = mysqli_connect('localhost','root','infra1800','****') or die('error connecting to database to deleate things');
 $query ="SELECT * FROM category";

 $result = mysqli_query($dbc, $query) or die('Error Removing products from database');

 //while ($row = mysqli_fetch_array($result)){
 //echo $row['Category_ID'] . "," . $row['Name'] . "," . $row['Parent_ID'] . "<br>";

    // }
 //mysqli_close($dbc);
       echo '_______________________________________________________________________________________________<br>';
 $array = array();
 $organized_array = array();
 $tracker_array = array();
 $holder_temp_array = array();
 $temp_tracker_array = array();
 $organized_array_tracker = "";
 $i = 0;
 while ($row = mysqli_fetch_array($result)){

         $array[$i] = array($row['Category_ID'], $row['Name'], $row['Parent_ID'], $row['Category_Level']);
         $i+=1;
         }


     print_r($array);

  $array_size = sizeof($array);
  echo $array_size . 'yes';


       for ($i = 0; $i < $array_size; $i++){



            if ($array[$i][2]== NULL){
            echo '<br>working<br>';
            echo $array[$i][0] . "turkey<br><br><br><br>";

            array_push($tracker_array,$array[$i][0] );
            array_push($organized_array, $array[$i]);
            unset($array[$i]);

            }}
               $organized_array_size = sizeof($organized_array);

                    echo '<br>this is once?';


              WHILE (count($array)>0){
               if(count($tracker_array)==0){
                       $tracker_array=$temp_tracker_array;
                       $temp_tracker_array = array();}
              foreach ($array as $key=>$value){

                       echo '<br>' . $key . 'this is the value lolkj';
                       if ($array[$key][2]== $tracker_array[0]){



                               for ($i = 0; $i < $organized_array_size; $i++){

                                   if($organized_array[$i][0]==$array[$key][2]){
                                   $organized_array_tracker = $i;

                                   echo'DINOSOURASREX!';
                                   $src = $organized_array;
                                   //$src = array($array[$key][0],$array[$key][1],$array[$key][2]);
                                   //print_r($array[$key]) . ' <br><br>this is the array key<br><br>';
           $in = array($array[$key]);
           $pos = $organized_array_tracker;

           $organized_array = array_push_after($src,$in,$pos);

                    echo $organized_array_tracker . 'organized array tracker';
                                   array_push($temp_tracker_array,$array[$key][0] );

                                   }

                                   }
                                unset($array[$key]);
                                // array_shift($tracker_array);
                                //    print_r($tracker_array);
                                 //   echo'THIS IS THE TRACKER ARRAY';

                        //$src = $array[$key];
       //$in = $organized_array;
       //$pos = $organized_array_tracker;
         //array_push_after($src,$in,$pos);
         //echo $oranized_array_tracker . 'organized array tracker';
                 //array_shift($tracker_array);
        //unset($array[$key]);
                     }


                                      //array_shift($tracker_array);


                       }

unset($value); print_r($tracker_array); array_shift($tracker_array); print_r($tracker_array); $organized_array_size = sizeof($organized_array);

}

              $array_size = sizeof($array);
           //echo $array_size . 'yes again';
              echo '<br><br><br>this is the organized array';
              print_r($organized_array);


              //print_r($tracker_array);
              echo '<br><br><br> this is the array after loosing some guts<br>';
              print_r($array);
              //echo $tracker_array[0][1] . 'this is the value of 1 i hope<br><br>';
              print_r($holder_temp_array);

IF ANYONE HAS A DETAILED DESCRIPTION OF HOW TO EASILY SORT THE RESULT I HAVE CREATED BY ALPHABETIZING EACH NESTED SET PLEASE LET ME KNOW. I have included a field for levels (i.e. 1 at the top, 2 following, etc) so it is easy for me to yank out each level and crap it out into a temporary array for sorting (and then re-insert it). All i need to do is sort that temporary array based on the name field. isn't there a way to do this easily with array_multisort? Any ideas?