PHP SPL to manipulate recursive menu

Question

I have a table in a database which has category data:

id   title       parent 
1    category 1  0
2    category 2  2
3    category 3  3
4    category 4  0

Eeach parent may have the parent row id.

For example, category 3 is a child of category 2, which is child of category 1.

category 1
   category 2
      category 3

category 4

1 - Is there a better way to manipulate this technique? 2 - My implementation is to fetch all the rows in one SQL query, then use a recursive function to build a multi-dimensional array, then I loop through it using multi level foreach to build a menu or whatever. I need a better way using PHP SPL.

I want to create either a full menu or an item path like:

category1 -> catgory 2 -> etc.

and create a grid which holds the category level in each row.

Answer 1

I've recently dome something similar using a single query and a single while loop. It uses references to build a tree data structures (array) by means of a flat one (array). There's no SPL involved because I don't felt there was a need for it. There's a gist on GitHub with a better color scheme :)

/**
* Each element in the return array has a 'data' key, holding category data,
* like name, and a 'children' key holding its subcategories.
*
* @param resource $resource MySQL resource resulted from mysql_query
* @param string $id_key Name of the 'id' field
* @param string $parent_id_key Name of the 'parent_id' field
* @param boolean $use_cache Use cached result from previous calls. Defaults to TRUE
* @return array
*/
function categories($resource, $id_key, $parent_id_key, $use_cache = true) {
    // Cache the categories in a static local variable. This way, the query
    // will be executed just for the first function call. Subsequent calls
    // will return imediatelly, unless you tell it not to.
    static $tree = array();

    if ($tree && $use_cache) {
        return $tree;
    }

    // Flat representation of the categories for fast retrieval using array
    // keys. Each element will be referenced in the $tree array. This
    // allows to build a tree data structure using a flat one.
    $flat = array();

    // Reset the $tree, in case $use_cache=false in a subsequent call
    $tree = array();

    while ($row = mysql_fetch_object($resource)) {
        $flat[$row->$id_key] = array(
            'data' => $row,
            'children' => array(),
        );

        if (array_key_exists($row->$parent_id_key, $flat)) {
            // Assign children by reference so that possible subcategories of
            // this one will appear in the tree structure ($tree)
            $flat[$row->$parent_id_key]['children'][] =& $flat[$row->$id_key];
        }

        if ($row->$parent_id_key == 0) {
            // Assign by reference for synchronizing $flat with $tree;
            $tree[] =& $flat[$row->$id_key];
        }
    }

    return $tree;
}

Also, the function is totally decoupled from the database. You need to pass it a mysql_query resource, a string representing the id field and a string representing the parent_id field. The bad part is that it is coupled to the PHP mysql extension because it uses a call to mysql_fetch_object. It could probably be improved.

Some other advantage is that it caches the result for consequent calls, unless you tell it to invalidate the cache, which is the fourth (boolean) parameter.

Take a look and see if it helps you.

Answer 2

If your data is strictly hierarchical, and it looks like it is, I would recommend the Modified Preorder Tree Traversal method for storing your data.

There is a superb article at Sitepoint that discusses this exact problem. You appear to be using the Adjacency List model, which is discussed on page one, but the MPTT is much more efficient for a read-heavy storage of this type of data.

Check out page 2 to see the examples. It's really quite an excellent piece of architecture.