Create Multi-Dimensional Array With Algorithm Using Data in Single-Dimensional Array

Question

I have an single-dimensional array of PHP objects. Each object has two attributes, one attribute is the object's unique ID and the other is the unique ID of another object in the array that is its parent. For example:

array(3) {
  [0]=>
  object(stdClass)#1 (2) {
    ["ID"]=>
    int(1)
    ["parentID"]=>
    int(0)
  }
  [1]=>
  object(stdClass)#2 (2) {
    ["ID"]=>
    int(3)
    ["parentID"]=>
    int(2)
  }
  [2]=>
  object(stdClass)#3 (2) {
    ["ID"]=>
    int(2)
    ["parentID"]=>
    int(1)
  }
}

I need to convert this single-dimensional array into a multi-dimensional array. I have taken a few stabs at this but I can't find a way to get it done without having a loop for each level of nesting. The algorithm needs to be able to adapt to hypothetically infinite levels of nesting. I've tried using some recursion techniques but I've never gotten it quite right.

To add a bit of complexity, the objects in the array that I am getting are not always in a sensical order. I tried to replicate this in my example above; you'll notice that the object with the ID of 3 comes in the array before the object with the ID of 2. So their will probably be a sorting algorithm involved as well.

Ideally the example above would turn out something like this:

Array
(
    [0] => Array
        (
            [ID] => 1
            [parentID] => 0
            [0] => Array
                (
                    [ID] => 2
                    [parentID] => 1
                    [0] => Array
                        (
                            [ID] => 3
                            [parentID] => 2
                        )

                )

        )

)

Answer 1

Try this algorithm:

// sort objects by parentID
function cmpNodes($a, $b) {
    return $a->parentID - $b->parentID;
}
usort($objects, 'cmpNodes');

// define first node as root of tree
$tree = (array) array_shift($objects);
// lookup table for direct jumps
$idTable = array($tree['ID'] => &$tree);
foreach ($objects as $object) {
    $node = (array) $object;
    // test if parent node exists
    if (!isset($idTable[$node['parentID']])) {
        // Error: parent node does not exist
        break;
    }
    // append new node to the parent node
    $idTable[$node['parentID']][] = $node;
    // set a reference in the lookup table to the new node
    $idTable[$node['ID']] = &$idTable[$node['parentID']][count($idTable[$node['parentID']])-3];
}
// unset($idTable);
var_dump($tree);

I used a lookup table ($idtable) for the IDs to jump directly to the nodes.

Answer 2

So, just as a precursor - I do not know php, really at all. I am primarily a c-style language developer (aka c, Objective c and Java). So some of this may be harder to do in php, but here is the attempt I would make:

//the original input array
oldArray;
//the output array
array[] newArray = new array[];

foreach (element : oldArray) {
    //if the element is at the top, put it at the top of the array
    if (element.parentId == 0) {
        newArray.add(element);
    } else {
        //otherwise, find it's parent and put it in the child array of the parent
        for (potentialParent : oldArray) {
            if (potentialParent.id = element.parentId) {
                potentialParent.array.add(element);
                break;
            }
        }
    }
}

A couple of notes: I am assuming you are passing everything around with pointers. If you are making copies of the objects, it is harder, but not impossible. I am also assuming you can change the size of the array dynamically. Again, I am not too aware of php - if you cannot do that, then you would need a procedural way to do this behavior. In Java I would use a list type, or just copy the array and reset it again.

The key to this algorithm working is that the children are placed under their parent - wherever they are - in one pass. This means that, no matter the order, the hierarchy will be created in that single pass. If you need the wrapper array around the parent that you show in your example, you can simply add something like this to the end of the code:

finalArray = new array[];
finalArray[0] = newArray;

Hope this helps.