TUTORIAL: Menu Hierarchies and Breadcrumbs

  • joebert
  • Fart Bubbles
  • Genius
  • User avatar
  • Posts: 13502
  • Loc: Florida

Post 3+ Months Ago

Introduction



I wrote this tutorial because of this thread and subsequently this thread. I was beginning to get frustrated with trying to explain myself without going off in a bunch of directions so I figured it would be easier to just start from the beginning and walk through the code I use when doing this sort of thing.

This is not a novice tutorial, it assumes you've got a handle on PHP and MySQL for the most part and are perhaps exploring new ways to do things.


Categories Database Table



First I need a database table to store my categories. For the purpose of example, I only need three columns to maintain a hierarchy.

SQL Code: [ Select ]
CREATE TABLE `categories` (
  `category_id` smallint(5) UNSIGNED NOT NULL AUTO_INCREMENT,
  `parent_id` smallint(6) UNSIGNED DEFAULT NULL,
  `label` varchar(64) NOT NULL,
  PRIMARY KEY  (`category_id`),
)
  1. CREATE TABLE `categories` (
  2.   `category_id` smallint(5) UNSIGNED NOT NULL AUTO_INCREMENT,
  3.   `parent_id` smallint(6) UNSIGNED DEFAULT NULL,
  4.   `label` varchar(64) NOT NULL,
  5.   PRIMARY KEY  (`category_id`),
  6. )


category_id as you can see is an auto_increment and my primary key. I'll use this column to keep track of each category individually and this column with be referenced by parent_id to create a hierarchy. label is exactly what it sounds like, the human readable name of the category.

If a categories parent_id is ever NULL, I know it's a root category and not a sub-category.


Querying The Database



My first instinct would be to ask the database for all of the root categories, or categories with a NULL parent_id. This is a bad idea though, it means I need to make another query to retrieve the sub-categories, and then I need to make more queries to retrieve the sub-categories of the sub-categories, and so on. If I have 4 root categories with 4 sub-categories which each have 2 sub-categories, I need a bunch of queries. That's like following a recipe in a cook book and going to the store and buying each individual ingredient as I get to it in the recipes ingredient list.

Instead, I'm going to use 1 query. A simple query that just pulls every row in the table at once without sorting or anything.

SQL Code: [ Select ]
SELECT category_id, parent_id, label
FROM categories;
  1. SELECT category_id, parent_id, label
  2. FROM categories;


Now for a threaded discussion or something likely to return hundreds of thousands of rows, this would probably be a horrible idea because of how much memory would be wasted holding the entire table in most requests. (a much more likely scenario would be running out of memory) But for the purpose of categories where it's likely the majority of rows can be utilized in each request and where, assuming I have the 65535 categories my SMALLINT accounts for, will only use 16M.

Why on earth would I ever have 65535 categories? The only reason I used a SMALLINT in the first place is to provide room for deleted categories.
I can't recall seeing a website, which is actually usable, using even 1000 categories. Heck, I think the highest category id for any of Ozzus forums is only in the low 100s at most.

Using that most basic of database table I have up there basically gives me 4 categories for every 1 KB.


Hierarchy



First I want a variable to build my hierarchy in. I want to setup this hierarchy in a way that can be utilized by numerous routines for building navigation elements. The idea here is build it once and reuse it multiple times.

PHP Code: [ Select ]
$category_lineage = new array();


I'm going to use the MySQLi PHP extension and assume you're familiar with it, meaning I'm going to skip all of the connection parts and tell you that from here on $db is the database object returned from "$db = new mysqli(...);"

Using the MySQLi objects query method, I pull all of the rows using the query before. I want to reiterate this query so I can point out that I'm using the MYSQLI_USE_RESULT flag when actually executing the query. I use this flag so the step of retrieving the rows before I use them is skipped. Without using this flag I would basically be retrieving the rows twice since I don't want to execute any other queries before I've iterated through the return rows and therefore have no worries about out of sync query errors.

PHP Code: [ Select ]
$result = $db->query('SELECT category_id, parent_id, label FROM categories', MYSQLI_USE_RESULT);


With $result holding a reference to my category rows, I can begin iterating through the rows and filling my $category_lineage using the category_id as the array index instead of just letting PHP assign indexes.

PHP Code: [ Select ]
while($row = $result->fetch_object())
{
   $row->sub_categories = array();
   $category_lineage[$row->category_id] = $row;
}
$result->close();
  1. while($row = $result->fetch_object())
  2. {
  3.    $row->sub_categories = array();
  4.    $category_lineage[$row->category_id] = $row;
  5. }
  6. $result->close();


The reason I use $category_lineage[$row->category_id] = $row; instead of using for instance $category_lineage[] = $row; is that I want a quick answer to whether a category_id exists when I need to answer that question, whether I'm asking it for a security check, or when I'm looking for the parent of a sub-category.

For instance, if a user wants to view the category with category_id "12" I can quickly go to $category_lineage and see if that index exists.

PHP Code: [ Select ]
if( empty($category_lineage[(int)$_GET['category_id']]))
{
    // bail on account of non-existant category
}
  1. if( empty($category_lineage[(int)$_GET['category_id']]))
  2. {
  3.     // bail on account of non-existant category
  4. }


Without the $category_lineage I probably would have queried the database to see if the category exists. Since I'm more than likely going to need the $category_lineage for menu items and other things anyways, I might as well check against it instead of asking the database if a category exists.

Another thing you'll notice is that I'm adding an array for sub-categories to the object row returned. I could pass the classname argument to fetch_object to have this array added automatically via a class, but for the sake of this example I'm just going to do it like I have below.

PHP Code: [ Select ]
$row->sub_categories = array();


At first glance it might seem like I'm going to fill that array with other arrays to create a multi-dimensional array for the hierarchy, but I'm not. That sub-category array will actually only contain references to other items in the $category_lineage.

Here's the array I'll have after I've retrieved all of the rows from the database and setup an array to hold the sub-category references.
Note how the category_id property of each corresponds to the items array key/index.
Code: [ Select ]
Array
(
    [1] => stdClass Object
        (
            [category_id] => 1
            [parent_id] =>
            [label] => Sports
            [sub_categories] => Array()
        )
    [2] => stdClass Object
        (
            [category_id] => 2
            [parent_id] => 1
            [label] => Baseball
            [sub_categories] => Array()
        )
    [5] => stdClass Object
        (
            [category_id] => 5
            [parent_id] => 1
            [label] => Basketball
            [sub_categories] => Array()
        )
    [8] => stdClass Object
        (
            [category_id] => 8
            [parent_id] => 1
            [label] => Hockey
            [sub_categories] => Array()
        )
    [11] => stdClass Object
        (
            [category_id] => 11
            [parent_id] => 1
            [label] => Football
            [sub_categories] => Array()
        )
    [14] => stdClass Object
        (
            [category_id] => 14
            [parent_id] =>
            [label] => Babes
            [sub_categories] => Array()
        )
    [15] => stdClass Object
        (
            [category_id] => 15
            [parent_id] => 14
            [label] => Eva Mendes
            [sub_categories] => Array()
        )
    [16] => stdClass Object
        (
            [category_id] => 16
            [parent_id] => 14
            [label] => Elisha Cuthbert
            [sub_categories] => Array()
        )
    [21] => stdClass Object
        (
            [category_id] => 21
            [parent_id] =>
            [label] => test
            [sub_categories] => Array()
        )
)
  1. Array
  2. (
  3.     [1] => stdClass Object
  4.         (
  5.             [category_id] => 1
  6.             [parent_id] =>
  7.             [label] => Sports
  8.             [sub_categories] => Array()
  9.         )
  10.     [2] => stdClass Object
  11.         (
  12.             [category_id] => 2
  13.             [parent_id] => 1
  14.             [label] => Baseball
  15.             [sub_categories] => Array()
  16.         )
  17.     [5] => stdClass Object
  18.         (
  19.             [category_id] => 5
  20.             [parent_id] => 1
  21.             [label] => Basketball
  22.             [sub_categories] => Array()
  23.         )
  24.     [8] => stdClass Object
  25.         (
  26.             [category_id] => 8
  27.             [parent_id] => 1
  28.             [label] => Hockey
  29.             [sub_categories] => Array()
  30.         )
  31.     [11] => stdClass Object
  32.         (
  33.             [category_id] => 11
  34.             [parent_id] => 1
  35.             [label] => Football
  36.             [sub_categories] => Array()
  37.         )
  38.     [14] => stdClass Object
  39.         (
  40.             [category_id] => 14
  41.             [parent_id] =>
  42.             [label] => Babes
  43.             [sub_categories] => Array()
  44.         )
  45.     [15] => stdClass Object
  46.         (
  47.             [category_id] => 15
  48.             [parent_id] => 14
  49.             [label] => Eva Mendes
  50.             [sub_categories] => Array()
  51.         )
  52.     [16] => stdClass Object
  53.         (
  54.             [category_id] => 16
  55.             [parent_id] => 14
  56.             [label] => Elisha Cuthbert
  57.             [sub_categories] => Array()
  58.         )
  59.     [21] => stdClass Object
  60.         (
  61.             [category_id] => 21
  62.             [parent_id] =>
  63.             [label] => test
  64.             [sub_categories] => Array()
  65.         )
  66. )


Here's where using those references combined with those meaningful item keys really comes in handy. Instead of iterating through the array and for each item iterating through the array again looking for items with the current item as the parent id, I only iterate through the $category_lineage array one time to build the entire hierarchy.

Code: [ Select ]
foreach($category_lineage as $key => $val)
{
    if($val->parent_id)
    {
        $category_lineage[$val->parent_id]->sub_categories[$key] =& $category_lineage[$key];
    }
}
  1. foreach($category_lineage as $key => $val)
  2. {
  3.     if($val->parent_id)
  4.     {
  5.         $category_lineage[$val->parent_id]->sub_categories[$key] =& $category_lineage[$key];
  6.     }
  7. }


Keep in mind that $category_lineage is still a two dimensional array, but when I use print_r on it this time I get the following result.

Code: [ Select ]
Array
(
  [1] => stdClass Object
    (
      [category_id] => 1
      [parent_id] =>
      [label] => Sports
      [sub_categories] => Array
        (
          [2] => stdClass Object
            (
              [category_id] => 2
              [parent_id] => 1
              [label] => Baseball
              [sub_categories] => Array()
            )
          [5] => stdClass Object
            (
              [category_id] => 5
              [parent_id] => 1
              [label] => Basketball
              [sub_categories] => Array()
            )
          [8] => stdClass Object
            (
              [category_id] => 8
              [parent_id] => 1
              [label] => Hockey
              [sub_categories] => Array()
            )
          [11] => stdClass Object
            (
              [category_id] => 11
              [parent_id] => 1
              [label] => Football
              [sub_categories] => Array()
            )
        )
    )
  [2] => stdClass Object
    (
      [category_id] => 2
      [parent_id] => 1
      [label] => Baseball
      [sub_categories] => Array()
    )
  [5] => stdClass Object
    (
      [category_id] => 5
      [parent_id] => 1
      [label] => Basketball
      [sub_categories] => Array()
    )
  [8] => stdClass Object
    (
      [category_id] => 8
      [parent_id] => 1
      [label] => Hockey
      [sub_categories] => Array()
    )
  [11] => stdClass Object
    (
      [category_id] => 11
      [parent_id] => 1
      [label] => Football
      [sub_categories] => Array()
    )
  [14] => stdClass Object
    (
      [category_id] => 14
      [parent_id] =>
      [label] => Babes
      [sub_categories] => Array
        (
          [15] => stdClass Object
            (
              [category_id] => 15
              [parent_id] => 14
              [label] => Eva Mendes
              [sub_categories] => Array()
            )
          [16] => stdClass Object
            (
              [category_id] => 16
              [parent_id] => 14
              [label] => Elisha Cuthbert
              [sub_categories] => Array()
            )
        )
    )
  [15] => stdClass Object
    (
      [category_id] => 15
      [parent_id] => 14
      [label] => Eva Mendes
      [sub_categories] => Array()
    )
  [16] => stdClass Object
    (
      [category_id] => 16
      [parent_id] => 14
      [label] => Elisha Cuthbert
      [sub_categories] => Array()
    )
  [21] => stdClass Object
    (
      [category_id] => 21
      [parent_id] =>
      [label] => test
      [sub_categories] => Array()
    )
)
  1. Array
  2. (
  3.   [1] => stdClass Object
  4.     (
  5.       [category_id] => 1
  6.       [parent_id] =>
  7.       [label] => Sports
  8.       [sub_categories] => Array
  9.         (
  10.           [2] => stdClass Object
  11.             (
  12.               [category_id] => 2
  13.               [parent_id] => 1
  14.               [label] => Baseball
  15.               [sub_categories] => Array()
  16.             )
  17.           [5] => stdClass Object
  18.             (
  19.               [category_id] => 5
  20.               [parent_id] => 1
  21.               [label] => Basketball
  22.               [sub_categories] => Array()
  23.             )
  24.           [8] => stdClass Object
  25.             (
  26.               [category_id] => 8
  27.               [parent_id] => 1
  28.               [label] => Hockey
  29.               [sub_categories] => Array()
  30.             )
  31.           [11] => stdClass Object
  32.             (
  33.               [category_id] => 11
  34.               [parent_id] => 1
  35.               [label] => Football
  36.               [sub_categories] => Array()
  37.             )
  38.         )
  39.     )
  40.   [2] => stdClass Object
  41.     (
  42.       [category_id] => 2
  43.       [parent_id] => 1
  44.       [label] => Baseball
  45.       [sub_categories] => Array()
  46.     )
  47.   [5] => stdClass Object
  48.     (
  49.       [category_id] => 5
  50.       [parent_id] => 1
  51.       [label] => Basketball
  52.       [sub_categories] => Array()
  53.     )
  54.   [8] => stdClass Object
  55.     (
  56.       [category_id] => 8
  57.       [parent_id] => 1
  58.       [label] => Hockey
  59.       [sub_categories] => Array()
  60.     )
  61.   [11] => stdClass Object
  62.     (
  63.       [category_id] => 11
  64.       [parent_id] => 1
  65.       [label] => Football
  66.       [sub_categories] => Array()
  67.     )
  68.   [14] => stdClass Object
  69.     (
  70.       [category_id] => 14
  71.       [parent_id] =>
  72.       [label] => Babes
  73.       [sub_categories] => Array
  74.         (
  75.           [15] => stdClass Object
  76.             (
  77.               [category_id] => 15
  78.               [parent_id] => 14
  79.               [label] => Eva Mendes
  80.               [sub_categories] => Array()
  81.             )
  82.           [16] => stdClass Object
  83.             (
  84.               [category_id] => 16
  85.               [parent_id] => 14
  86.               [label] => Elisha Cuthbert
  87.               [sub_categories] => Array()
  88.             )
  89.         )
  90.     )
  91.   [15] => stdClass Object
  92.     (
  93.       [category_id] => 15
  94.       [parent_id] => 14
  95.       [label] => Eva Mendes
  96.       [sub_categories] => Array()
  97.     )
  98.   [16] => stdClass Object
  99.     (
  100.       [category_id] => 16
  101.       [parent_id] => 14
  102.       [label] => Elisha Cuthbert
  103.       [sub_categories] => Array()
  104.     )
  105.   [21] => stdClass Object
  106.     (
  107.       [category_id] => 21
  108.       [parent_id] =>
  109.       [label] => test
  110.       [sub_categories] => Array()
  111.     )
  112. )


Remember, $category_lineage is still a two dimensional array. It can be iterated like an unlimited depth hierarchy because of references instead of copied values though.

Display



Looking back to the example from before, where empty() is used to see if the category requested by the user even exists, we're going to assume that the category does exist for the purpose of this tutorial and I'm going to refer to the screened $_GET['category_id'] as $current_category from here on.

PHP Code: [ Select ]
$current_category = (int)$_GET['category_id'];


How could I generate a list of links for breadcrumbs to the current category ?

PHP Code: [ Select ]
   $t->breadcrumbs            = new stdClass;
   $t->breadcrumbs->current   =& $category_lineage[$current_category];
   $t->breadcrumbs->url_mask  = 'index.php?category_id=%1$s&category_label=%2$s&page=%3$s';
 
   $t->breadcrumbs->links = array(
      sprintf('<a href="%1$s">%2$s</a>',
         sprintf($t->breadcrumbs->url_mask, $t->breadcrumbs->current->category_id, $t->breadcrumbs->current->label, 1),
         $t->breadcrumbs->current->label
      )
   );
 
   while($t->breadcrumbs->current->parent_id)
   {
      $t->breadcrumbs->current =& $category_lineage[$t->breadcrumbs->current->parent_id];
      array_unshift(
         $t->breadcrumbs->links,
         sprintf('<a href="%1$s">%2$s</a>',
            sprintf($t->breadcrumbs->url_mask, $t->breadcrumbs->current->category_id, $t->breadcrumbs->current->label, 1),
            $t->breadcrumbs->current->label
         )
      );
   }
 
   $t->breadcrumbs = implode(' &bull; ', $t->breadcrumbs->links);
  1.    $t->breadcrumbs            = new stdClass;
  2.    $t->breadcrumbs->current   =& $category_lineage[$current_category];
  3.    $t->breadcrumbs->url_mask  = 'index.php?category_id=%1$s&amp;category_label=%2$s&amp;page=%3$s';
  4.  
  5.    $t->breadcrumbs->links = array(
  6.       sprintf('<a href="%1$s">%2$s</a>',
  7.          sprintf($t->breadcrumbs->url_mask, $t->breadcrumbs->current->category_id, $t->breadcrumbs->current->label, 1),
  8.          $t->breadcrumbs->current->label
  9.       )
  10.    );
  11.  
  12.    while($t->breadcrumbs->current->parent_id)
  13.    {
  14.       $t->breadcrumbs->current =& $category_lineage[$t->breadcrumbs->current->parent_id];
  15.       array_unshift(
  16.          $t->breadcrumbs->links,
  17.          sprintf('<a href="%1$s">%2$s</a>',
  18.             sprintf($t->breadcrumbs->url_mask, $t->breadcrumbs->current->category_id, $t->breadcrumbs->current->label, 1),
  19.             $t->breadcrumbs->current->label
  20.          )
  21.       );
  22.    }
  23.  
  24.    $t->breadcrumbs = implode(' &bull; ', $t->breadcrumbs->links);


How about a category hierarchy using nested <ul> elements, something you'd see a lot in menus and sitemaps ?

PHP Code: [ Select ]
$c = new stdClass;
$c->listing = '';
 
function recursive_ul(&$cat)
{
   $str = sprintf('<div><a href="%1$s">%2$s</a></div><ul>', $cat->list_link, $cat->label);
   foreach($cat->sub_categories as &$sub_cat)
   {
      $str .= '<li>' . recursive_ul($sub_cat) . '</li>';
   }
   return "$str</ul>";
}
 
foreach($category_lineage as &$c->category)
{
   $c->url = '?category_id=%1$s&amp;title=%2$s&amp;page=%3$s';
   $c->category->list_link = sprintf($c->url, $c->category->category_id, $c->category->label, 1);
}
 
foreach($category_lineage as &$c->category)
{
   if(empty($c->category->parent_id))
   {
      $c->listing .= '<li>' . recursive_ul($c->category) . '</li>';
   }
}
  1. $c = new stdClass;
  2. $c->listing = '';
  3.  
  4. function recursive_ul(&$cat)
  5. {
  6.    $str = sprintf('<div><a href="%1$s">%2$s</a></div><ul>', $cat->list_link, $cat->label);
  7.    foreach($cat->sub_categories as &$sub_cat)
  8.    {
  9.       $str .= '<li>' . recursive_ul($sub_cat) . '</li>';
  10.    }
  11.    return "$str</ul>";
  12. }
  13.  
  14. foreach($category_lineage as &$c->category)
  15. {
  16.    $c->url = '?category_id=%1$s&amp;title=%2$s&amp;page=%3$s';
  17.    $c->category->list_link = sprintf($c->url, $c->category->category_id, $c->category->label, 1);
  18. }
  19.  
  20. foreach($category_lineage as &$c->category)
  21. {
  22.    if(empty($c->category->parent_id))
  23.    {
  24.       $c->listing .= '<li>' . recursive_ul($c->category) . '</li>';
  25.    }
  26. }


Additions



What if I wanted to retrieve a list of items from a category, and every level of sub-category under that category ?
I could hit the database a few times looking for sub-categories, or I could reuse my $category_lineage somehow.

I can add a descendants array along side the sub_categories array. I could use references for the items in the descendants array like I do with the sub_categories array, but I think more times than not I'm just going to want a list of category ids rather than all of the information about each category when it comes to this.

PHP Code: [ Select ]
function category_lineage($branch)
{
   $descendants = array();
   foreach($branch->sub_categories as $key => $val)
   {
      $descendants[] = $key;
      $descendants   = array_merge($descendants, category_lineage($val));
   }
   return $descendants;
}
 
foreach($category_lineage as $key => $val)
{
   $category_lineage[$key]->descendants = category_lineage($val);
}
  1. function category_lineage($branch)
  2. {
  3.    $descendants = array();
  4.    foreach($branch->sub_categories as $key => $val)
  5.    {
  6.       $descendants[] = $key;
  7.       $descendants   = array_merge($descendants, category_lineage($val));
  8.    }
  9.    return $descendants;
  10. }
  11.  
  12. foreach($category_lineage as $key => $val)
  13. {
  14.    $category_lineage[$key]->descendants = category_lineage($val);
  15. }


Now let's say my $current_category is 14, and when I view category 14 I want to include the items from categories 15 and 16 since they're sub-categories of category 14. I can do something like this.

PHP Code: [ Select ]
   if(isset($category_lineage[$current_category]->descendants[0]))
   {
      $t->category_sql = "SELECT item_id FROM category_relations WHERE category_id IN($current_category," . implode(',', $category_lineage[$current_category]->descendants) . ')';
   }
   else
   {
      $t->category_sql = "SELECT item_id FROM category_relations WHERE category_id = $current_category";
   }
  1.    if(isset($category_lineage[$current_category]->descendants[0]))
  2.    {
  3.       $t->category_sql = "SELECT item_id FROM category_relations WHERE category_id IN($current_category," . implode(',', $category_lineage[$current_category]->descendants) . ')';
  4.    }
  5.    else
  6.    {
  7.       $t->category_sql = "SELECT item_id FROM category_relations WHERE category_id = $current_category";
  8.    }


Conclusion



Remember, you're not a computer, meaning you should ask as many questions as you need to without worrying about efficiency when asking questions. I could sit here for days and anticipate questions everyone could ask, but then I'd never get to go fishing. ;)
  • Anonymous
  • Bot
  • No Avatar
  • Posts: ?
  • Loc: Ozzuland
  • Status: Online

Post 3+ Months Ago

Post Information

  • Total Posts in this topic: 1 post
  • Moderator: Tutorial Writers
  • Users browsing this forum: No registered users and 1 guest
  • You cannot post new topics in this forum
  • You cannot reply to topics in this forum
  • You cannot edit your posts in this forum
  • You cannot delete your posts in this forum
  • You cannot post attachments in this forum
 
 

© 1998-2014. Ozzu® is a registered trademark of Unmelted, LLC.