A Tree From a Database

[smeshy123]

I'm developing a website for a newspaper, what I would like to be able to do is for the Archives set up the system so that it takes all the information in the database and makes it look like this:

+ Year
+ Year
- Year
+ Month
+ Month
- Month
Page 1 Link
- Description of Page
Page 2 Link
- Description of Page

That kind of thing. How would that be done? I have no clue where to start. Can anyone point me in the right direction? If you need more details please ask.

Thanks!

Smesh

[AaronW]

Um, was there supposed to be some kind of hierarchy in your example? Try using the CODE tags to preserve the whitespace.

I'd imagine you meant:

+ Year
  + Year
    - Year
+ Month
  + Month
    - Month
Page 1 Link
  - Description of Page
Page 2 Link
  - Description of Page

Am I right? For that, you'd probably be best using an algorithm known as the "Adjacency List Model".

Basically you have one MySQL table called "categories". It looks like:

id | parent | name

Then you'd stuff it with categories and fill in the IDs like so:

1 | 0 | Farm Animals
2 | 1 | Sheep
3 | 1 | Cows
4 | 1 | Birds
5 | 4 | Chickens
6 | 4 | Ducks

So "Farm Animals" has no parent. Sheep, Cows, and Birds use "Farm Animals" as their parent. Chickens and Ducks use "Farm Animals > Birds" as their parent, because Chickens uses 4 as its parent and 4 (Birds) uses 1 (Farm Animals) as its parent. Then you'd simply query the table and loop through the results using PHP to build your tree.

Was that helpful at all? Heh.

[smeshy123]

I'm sort of getting it. Could you elaborate a little further? Or send me to a good resource on how to do it?

Thanks!

Smesh

[AaronW]

Here's a class I wrote (see the comments for instructions) to handle such tables: (Copy the code into an editor of some kind so you can read it more clearly... It's sort of butchered here while presented in HTML)

PHP Code:

<?php
    /*------------------------------------------------------------------------*\
      This class is for handling tables that are designed for the adjacency list
      model:

      id | parent | name
      ---+--------+--------------
         1 |      0 | Farm Animals
         2 |      1 | Sheep
         3 |      1 | Cows
         4 |      1 | Birds
         5 |      4 | Chickens
         6 |      4 | Ducks

        The id, parent, and name field names in this example table are 'id',
        'parent', and 'name'.
    \*------------------------------------------------------------------------*/
  class AdjacencyList
  {
    var $raw_nodes  = array ();
    var $nodes      = array ();
    var $separator  = ' > ';

        /*----------------------------------------------------------------------*\
            Function:       object AdjacencyList ( resource result, string id_field, string parent_field, string name_field )
            Description: Given a MySQL result, this will build an array of $nodes
                         and $raw_nodes which are keyed and sorted by their paths.
                         The three $*_field arguments are to be filled out with the
                         names of the fields in the result.

                         Example:
                         // Select as many fields as you want, but you need the id, parent, and name fields
                         $result = mysql_query ('SELECT id, parent_id, name, date, creator FROM categories');

                         // Build the tree, and give it our 'categories' table's id, parent, and name field names
                         $tree = new AdjacencyList ($result, 'id', 'parent_id', 'name');

                         // Output HTML List of the tree
                         echo $tree->to_html ();
        \*----------------------------------------------------------------------*/
    function AdjacencyList ($result, $id_field, $parent_field, $name_field)
    {
      while ($category = mysql_fetch_object ($result))
        $this->raw_nodes[$category->{$id_field}] = $category;

      // Traverse the raw nodes and build the associative array
            foreach ($this->raw_nodes as $key => $node)
            {
                $path = $node->{$name_field};
                $child_id = $node->{$id_field};

                // Build verbose path to the category
                while ($node->{$parent_field})
                {
                    $parent = $this->raw_nodes[$node->{$parent_field}];
                    $path = $parent->{$name_field}.$this->separator.$path;
                    $node = $parent;
                }

                // Add node as a child of its direct parent
                $bricks = explode ($this->separator, $path);
                array_pop ($bricks);
                if (count ($bricks))
                {
                    $parent_obj =& $this->nodes[implode ($this->separator, $bricks)];
                    $parent_obj->children[$this->raw_nodes[$child_id]->{$name_field}] =& $this->raw_nodes[$child_id];
                }

                // Cross-reference the two node arrays. I think using references saves memory...
                $this->nodes[$path] =& $this->raw_nodes[$key];
                $this->nodes[$path]->path = $path;
            }

            // Sort the tree and its branches alphabetically
            ksort ($this->nodes);
    }

    /*----------------------------------------------------------------------*\
            Function:       string to_html ( [string current [, string css_class [, string css_id ]]] )
            Description: Traverse the nodes and build the HTML for a <ul>, with a
                         nested <ul> for each branch. CSS #id and the ID/Path of
                         the currently-selected category can be customized.
                         $current is the $path of the currently-selected node. That
                         is, for example: 'Animals > Cow'. The <li> containing this
                         branch will be giving a CSS class of 'current' for unique
                         styling.
        \*----------------------------------------------------------------------*/
        function to_html ($current = '', $css_id = '', $css_class = '')
        {
            // Monitor depth, and open/close a new list when it changes between nodes
            $last_depth = 0;

            if ($css_id != '')
            {
                $css_id = ' id="'.$css_id.'"';
            }
            if ($css_class != '')
            {
                $css_class = ' class="'.$css_class.'"';
            }

            $html = '<ul'.$css_id.$css_class.'>';
            foreach ($this->nodes as $node)
            {
                // Current category?
                $class = '';
                if ($node->path == $current)
                    $class = 'current';

                $depth = substr_count ($node->path, $this->separator);

                if (!empty ($node->children))
                    $html .= '<li class="parent'.$class.'">'.$node->name.'<ul'.$css_class.'>';
                else
                {
                    if ($depth < $last_depth) $html .= '</ul></li>';
                    $html .= '<li'. (!empty ($class) ? ' class="'.trim ($class).'"' : '').'>'.$node->name.'</li>';
                }

                $last_depth = $depth;
            }
            if ($last_depth != 0) $html .= '</ul></li>';
            $html .= "</ul>";

            return $html;
        }
  }
?>

[smeshy123]

Thanks! That was a great help!

Smesh