One Pass Parent-Child Array Structure

This is an old archived post from my former blog The Idea Shower. It's where I cataloged my product explorations and releases, one of which ultimately became Pocket.

This post was published back in 2007. It may not function as originally intended or may be missing images.

One Pass Parent-Child Array Structure

September 29, 2007

During the time that I've been programming I've continually run into times when I needed to be able to store a multi-level list into a database and retrieve it. I've used this in a CMS system to allow uses to create and nest their own menu options or to allow users to create and nest categories of items. Saving it was never a problem, but retrieving it and building a PHP array with nested structure was a messy task.

We want to turn this:

Database Table: Items
Id	Parent Id	Name
1	0	North America
2	1	Canada
3	7	California
4	0	Europe
5	0	Antartica
6	3	Los Angeles
7	1	United States
8	7	Florida
9	3	Hollywood
10	2	Quebec

Into this:

Antartica
North America
- Canada
  - Quebec
- United States
  - California
    - Hollywood
    - Los Angeles
- Florida
South America

The problem was that you couldn't easily enter a variable four levels deep into an array without knowing all of the parents of that item. This was okay if you retrieved the data in order of parents, but that meant if you wanted to sort the data by another column (such as name), you would have to do multiple passes through your data to continully reshuffle it. And this is a huge drain of cpu cycles on even medium sized data-sets.

The Solution

Let me show you what it looks like:

$refs = array();
$list = array();
$sql = "SELECT item_id, parent_id, name FROM items ORDER BY name";
$result = mysql_query($sql);
while($data = @mysql_fetch_assoc($result)) {
$thisref = &$refs[ $data['item_id'] ];
$thisref['parent_id'] = $data['parent_id'];
$thisref['name'] = $data['name'];

if ($data['parent_id'] == 0) {
    $list[ $data['item_id'] ] = &amp;$thisref;
} else {
    $refs[ $data['parent_id'] ]['children'][ $data['item_id'] ] = &amp;$thisref;
}

}

How it Works

PHP References

This solution's core is based on using PHP References. A reference allows you to access the same variable but with different names. In other words, it allows you to assign aliases to a variable. This way, any changes made to the reference will also affect the original variable.

Here's an example:

$var = 'Hello World'; $ref = &$var; //you define a reference by using '&' $ref = 'Goodbye World'; print "var = " . $var; print "ref = " . $ref;Outputs: var = Goodbye World ref = Goodbye World

Two Lists

To solve this, we are going to use not one, but two arrays. We will have our main array which is the one we are building with multilple levels, and secondly, we will have a single-level array that is all references to parts of our main list. This will allow us to target deep inside of the array without knowing the depth, or all of the parents above the level.

Let me explain how this will look in a more visual way.

On the left, we have our references array and on the right we have the list we are building with multiple levels. Now you have two ways to make an adjustment to a variable deep inside the main array, such as adding 'Miami' to Floria.

$main_list['North America']['children']['United States']['children']['Florida]['children'][] = 'Miami'; or $references['Florida']['children'][] = 'Miami';

You can see how it is much easier to target deep inside of the array using the reference, rather having to know the entire structure above where Florida is.

All Together Now

So when you extract the data from the database you will do the following process, repeating until all the data has been processed.

Add item to reference list
If item has no parent (meaning it's a top level item), add item reference to top level of build list.
If item has a parent, add the item reference to it's parents list of children.

Watch It Step by Step

If I've completely lost you, I suggest that you take a look how this works step by step. I've provided an example of building the location list above, where it prints out what the reference and main list look like after each item as been added. You can view that here.