PHP Sorting array by id and parent id

Question

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.

Answer 1

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

Answer 2

Your problem here is that you've got a one-dimensional array trying to do something which is actually meant to be displayed in a tree. What this means is that as your children link to a parent, that parent should know who its children are, but in this case they do not. So either you could put it into a new data structure, or build a recursive function to calculate the parents for each.

This is done by first sorting by the ID globally. This will ensure that we don't need to do any other sorting, as the array is already in the order you want it (at each level). Then we simply get each level in turn, recursively to find the items at that level and append them to the list:

<?php

$dudzio = 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')
);

function sortDudzio($a, $b)
{
    // If you need to switch which way the values are sorted
    // switch the 1 and -1 around
    if($a['id'] > $b['id']) {
        return 1;
    } elseif($a['id'] < $b['id']) {
        return -1;
    } else {
        return 0;
    }
}

function getByParent($array, $id, $level)
{

    $orderedArray = array();

    foreach($array as $k=>$arr) {
        if($arr['parent'] == $id) {
            $arr['title'] = str_repeat('-', $level) . $arr['title'];
            $orderedArray[] = $arr;
            $children = getByParent($array, $arr['id'], $level + 1);
            foreach($children as $child) {
                $orderedArray[] = $child;
            }
        }
    }

    return $orderedArray;

}

usort($dudzio, 'sortDudzio');

print_r(getByParent($dudzio, 0, 0));