PHP Sorting array by id and parent id

I searched a lot for this problem:

I've got an array:

array(
  array('id' = '1'; 'parent' = '0'; 'title' = 'XXX1');
  array('id' = '85'; 'parent' = '0'; 'title' = 'XXX2');
  array('id' = '41'; 'parent' = '0'; 'title' = 'XXX2');
  array('id' = '17'; 'parent' = '0'; 'title' = 'XXX3');
  array('id' = '66'; 'parent' = '1'; 'title' = 'XXX4');
  array('id' = '92'; 'parent' = '1'; 'title' = 'XXX5');
  array('id' = '65'; 'parent' = '1'; 'title' = 'XXX6');
  array('id' = '45'; 'parent' = '41'; 'title' = 'XXX7');
  array('id' = '19'; 'parent' = '92'; 'title' = 'XXX8');
  array('id' = '101'; 'parent' = '45'; 'title' = 'XXX9');
  array('id' = '102'; 'parent' = '45'; 'title' = 'XXX10');
  array('id' = '103'; 'parent' = '19'; 'title' = 'XXX11');
  array('id' = '104'; 'parent' = '19'; 'title' = 'XXX12');
  array('id' = '105'; 'parent' = '19'; 'title' = 'XXX13');
);

How can I sort it that:

it sorts by ID if parent == 0, but if it has child, they should go right after their parent. And if that child has child they should also be right after its parent.
Consider that items where parent = 0 are level 0 and every child of this id has level 1 etc.
Now: If level = 0 It should add "-TITLE" before title. If level is 2 - "--TITLE", and if level is 5 - "-----TITLE"

I have about 300 records with max level about 4. I don't need sorting script for levels < 5, but for level 100 too.

Solution

When you are working with hira ...heira... tree-like data it is always a good idea to represent the data as a tree.

The following snipped can be used to translate your flat-array into a tree, which you now could process easily by recursively processing all the children arrays of a given element.

The method does the following:

iterate over all elements until the flat array is empty (it assumes that EVERY element is either a root element or has a matching parent inside the array)
if its a root element, add it to the result root
If the matching parent has been transferred to the result array already, add the element as a child.

I used a second array $refs that just contains references to each element based on their id, cause that allows to insert elements at any level of the $result array without having to search the right level.

ps.: there might be recursive approaches out there that are easier to understand.

pps.: I added an empty child-array to any element so I don't have to deal with non-existing arrays, when inserting children.

<?php
$arr = array(
  array('id' => 1, 'parent' => 0, 'title' => 'XXX1', 'children'=>array()),
  array('id' => 85, 'parent' => 0, 'title' => 'XXX2', 'children'=>array()),
  array('id' => 41, 'parent' => 0, 'title' => 'XXX2', 'children'=>array()),
  array('id' => 17, 'parent' => 0, 'title' => 'XXX3', 'children'=>array()),
  array('id' => 66, 'parent' => 1, 'title' => 'XXX4', 'children'=>array()),
  array('id' => 92, 'parent' => 1, 'title' => 'XXX5', 'children'=>array()),
  array('id' => 65, 'parent' => 1, 'title' => 'XXX6', 'children'=>array()),
  array('id' => 45, 'parent' => 41, 'title' => 'XXX7', 'children'=>array()),
  array('id' => 19, 'parent' => 92, 'title' => 'XXX8', 'children'=>array()),
  array('id' => 101, 'parent' => 45, 'title' => 'XXX9', 'children'=>array()),
  array('id' => 102, 'parent' => 45, 'title' => 'XXX10', 'children'=>array()),
  array('id' => 103, 'parent' => 19, 'title' => 'XXX11', 'children'=>array()),
  array('id' => 104, 'parent' => 19, 'title' => 'XXX12', 'children'=>array()),
  array('id' => 105, 'parent' => 19, 'title' => 'XXX13', 'children'=>array())
);

$newArr = unflattenArray($arr);

echo "<pre>";
print_r($newArr);
echo "</pre>";


function unflattenArray($flatArray){
  $refs = array(); //for setting children without having to search the parents in the result tree.
    $result = array();

    //process all elements until nohting could be resolved.
    //then add remaining elements to the root one by one. 
    while(count($flatArray) > 0){
        for ($i=count($flatArray)-1; $i>=0; $i--){
            if ($flatArray[$i]["parent"]==0){
                //root element: set in result and ref!
                $result[$flatArray[$i]["id"]] = $flatArray[$i]; 
                $refs[$flatArray[$i]["id"]] = &$result[$flatArray[$i]["id"]];
                unset($flatArray[$i]);
        $flatArray = array_values($flatArray);
            }

            else if ($flatArray[$i]["parent"] != 0){
                //no root element. Push to the referenced parent, and add to references as well. 
                if (array_key_exists($flatArray[$i]["parent"], $refs)){
                    //parent found
                    $o = $flatArray[$i];
                    $refs[$flatArray[$i]["id"]] = $o;
          $refs[$flatArray[$i]["parent"]]["children"][] = &$refs[$flatArray[$i]["id"]];
                    unset($flatArray[$i]);
          $flatArray = array_values($flatArray);
                }
            }
        }
  }
  return $result;
}

This method will return you a result like (outtake):

[1] => Array
        (
            [id] => 1
            [parent] => 0
            [title] => XXX1
            [children] => Array
                (
                    [0] => Array
                        (
                            [id] => 65
                            [parent] => 1
                            [title] => XXX6
                            [children] => Array
                                (
                                )

                        )

                    [1] => Array
                        (
                            [id] => 92
                            [parent] => 1
                            [title] => XXX5
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 19
                                            [parent] => 92

it is still unsorted but now in a format that could be easily processed.

for instance to sort everything, you could now simple use a recursive sort method like

sortMyArrays($newArr);
echo "<pre>";
print_r($newArr);
echo "</pre>";

function sortMyArrays(&$arr){
   uasort($arr, "srt");
   foreach ($arr as $a) {
     sortMyArrays($a["children"]);
   }
}

function srt($a, $b){
  return $a["id"] - $b["id"];
}

of course the same logic can be used to manipulate the title, display the data etc...