The Code Dojo

I have a flat MPTT (also called a nested set) array (really any tree ordered array will work, not necessarily an MPTT array) which has it’s elements output in order as follows:

• Top Parent 1
• Child 1-1
• Child 1-2
• Sub-Child 1-2-1
• Sub-Child 1-2-2
• Child 1-3
• Top Parent 2
• Child 2-1
• …

Each element is it’s own entry in the one dimensional array. This makes outputting that data in any kind of readable form very difficult, where keeping track of parents and branches are required in order to make sense of it. This gets pretty messy, pretty quickly. And the deeper the tree, the more complicated the process.

To make this easier to deal with, the array should be built in a tree format as follows:

• Top Parent 1
  • Child 1-1
  • Child 1-2
    • Sub-Child 1-2-1
    • Sub-Child 1-2-2
  • Child 1-3
• Top Parent 2
  • Child 2-1
  • …

Where the children of the elements in the tree are actually children of the elements in the array.

In order to do this quickly and painlessly, we are going to parse through this array twice… no iterations, just a couple of foreach loops and we’ll get our tree exactly how we want it.

In order to do this, we must first make sure our array indexes are the same as the IDs of the items we are sorting (because we are pulling this from a database, right?).

To do this in CakePHP we run it through the Set::combine function like so:
Set::combine($tree_data, '/Model/id', '/.');

If you are not using CakePHP, you can create a new array, and as you foreach through your original array, set elements in the new array accordingly:

$old_tree_data = $tree_data;
$tree_data = array( );
foreach ($old_tree_data as $node) {
	$tree_data[$node['Model']['id']] = $node;
}

Now that we have our array indexes set to our model ID, we can proceed.

The trick to this method is not to move the nodes around, because if we did that, we’d still have to keep track of what went where, and that’s exactly what we’re trying to avoid. Instead, we’re going to use references to keep track of our data as it gets moved around. That way we still have our original base array element that we can play with without having to know where it actually is in the tree.

Here is the code, and then we’ll go through it and explain.

foreach ($tree_data as $key => $node) {
	if ( ! $node['Model']['parent_id']) {
		continue;
	}

	if ( ! isset($tree_data[$node['Model']['parent_id']]['Child']) {
		$tree_data[$node['Model']['parent_id']]['Child'] = array( );
	}

	$tree_data[$node['Model']['parent_id']]['Child'] =& $tree_data[$key];
}

Now to explain… We parse through the array and for each element, we first test the element to see if it has a parent, if it does not, we just skip it, there’s no need to go further.

We then check and see if the parent element has an index called ‘Child’ and if it does not, we create one and set it as an array.

Then we do the magic. We set the next item in the parent node’s Child element to the reference of the current node. We don’t actually move the node. So now if you look at the array, you’ll see two entries for the current node, one inside the parent element, and one that was the original in the flat array.

WARNING: One thing to note here, is that we are not setting it to the reference of $node, but to the reference of $tree_data[$key]. The reason for this is because if the element is referenced to $node, the next time through the loop, the value of $node will change and all of the referenced elements will be set to the new value of $node, and we certainly don’t want that.

The magical part of this, is that no matter where the references end up, the original is still there to be modified. So for instance if I have a branch path with IDs as follows: 12, 5, 13, 14… it doesn’t matter what that path is, I can still access the element with ID 14 by modifying $tree_data[14]. So if element 14 has child nodes, I can place them in the tree by modifying $tree_data[14]['Child'], and wherever that node is actually supposed to be, it will get modified there as well. That’s the beauty of references.

Now to clean up the array, we just parse through it once more, and clear out the original reference nodes (the ones that have parents):

foreach ($tree_data as $key => $node) {
	if ( ! empty($node['Model']['parent_id']) {
		unset($tree_data[$key]);
	}
}

And that’s it! No messing around with paths… no iterative functions… just twice through an array (maybe three times), and it’s all sorted, compartmentalized, and pretty.

If you have other methods of getting your trees into a usable form, please let us know in the comments. We love seeing how other people do things.