Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

Nested Categories

by spaceout (Initiate)
on Jan 03, 2005 at 17:23 UTC ( #418991=perlquestion: print w/replies, xml ) Need Help??

spaceout has asked for the wisdom of the Perl Monks concerning the following question:

Hello all...I'm looking for some suggestions on a good method for creating nested categories. What I would like to do is store the category info in a database with 3 columns:

| category_id | parent_id | category_name |

That's easy enough...where I'm having trouble is retrieving this data in a way that makes it easy to place into a drop down list on a web page like this:

Category 1
 - Subcategory 1
   - Subsubcategory1
     - Subsubsubcategory1
     - Subsubsubcategory2
 - Subcategory 2
   - Subsubcategory1
   - Subsubcategory2
   - Subsubcategory3

This is what I have so far (not the entire script...just the relevant parts):

my ($category_list) = getCategories(); ### Trying to figure out how to loop through $category_list for (my $search_total=0; $search_total<=$#$category_list; $search_tota +l++) { # Do something with these: # $category_list->[$search_total]->{category_id} # $category_list->[$search_total]->{parent_id} # $category_list->[$search_total]->{category_name} } ### Used to do a single select to grab all categories sub getCategories { my ($results_data) = []; my $row = 0; my $sql = qq~SELECT category_id, parent_id, category_name FROM +ss_catalog_categories~; my $sth = $dbh->prepare($sql); $sth->execute; while (my @results = $sth->fetchrow_array()) { $results_data->[$row]->{category_id} = $results[0]; $results_data->[$row]->{parent_id} = $results[1]; $results_data->[$row++]->{category_name} = $results[2]; } $sth->finish; return ($results_data); }

Any suggestions on doing this correctly would be wonderful. Thanks.

Replies are listed 'Best First'.
Re: Nested Categories (Aka: How to build a child pointer tree from a parent pointer representation)
by demerphq (Chancellor) on Jan 03, 2005 at 19:36 UTC

    This is a common pattern. The basic problem is "how to I generate a child pointer tree from a parent pointer representation (as would normally be stored in a DB)". The following is a (proven but not debugged) solution that doesnt require multiple queries, can handle the data in any order, and only requires a single forward pass over the data.

    sub getCategories { my ($dbh)=@_; my $sql = qq~SELECT category_id, parent_id, category_name FROM ss_ +catalog_categories~; my $sth = $dbh->prepare($sql); $sth->execute; my %nodes; my @roots; my ($cid,$pid,$name); while ( ($cid,$pid,$name) = $sth->fetchrow_array()) { my $node=($nodes{$cid}||={}); $node->{name}=$name; $node->{pid}=$pid; $node->{cid}=$cid; if ($pid) { $nodes{$pid}{_kids}{$cid}=$node; } else { push @roots,$node; } } $sth->finish; return (\@roots,\%nodes); }

    Roots contains the root nodes of your forest, and %nodes contains a hash keyed by the category id of the nodes. You can traverse each tree in the forest like this:

    sub traverse { my ($node,$depth)=@_; $depth||=0; print " " x $depth,$node->{cid}," ",$node->{name},"\n"; foreach my $id ( sort {$a <=> $b} keys %{$node->{_kids}||{}} ) { traverse($node->{_kids}{$id},$depth+1); } } my ($r,$n)=getCategories($dbh); traverse($_) for sort { $a->{cid} <=> $b->{cid} } @$r;

    For those that care the above code is a highly simplified form of what is used here for the Recently Active Threads.


      Thanks, demerphq. That looks like exactly what I was looking for. I'll give it a try!
Re: Nested Categories
by mpeters (Chaplain) on Jan 03, 2005 at 18:17 UTC
    Although it might not be the most efficient solution, this sounds like a job for recursion. First get all the top_level categories. Then loop through each one getting the children of that category.
    # this assumes that you have the top level categories with a # parent_id that is NULL my $sql = qq~SELECT category_id, parent_id, category_name FROM ss_catalog_categories~ WHERE parent_id IS NULL; my $sth = $dbh->prepare($sql); $sth->execute; my $results = $sth->fetchall_arrayref({}); my $categories = format_results( $results ); sub format_results { my $results = shift; foreach my $result (@$results) { my $children = get_childrent($result->{category_id}); my %category = ( name => $result->{category_name}, children => $children, ); push(@$categories, \%category); } } sub get_children { my $parent = shift; my $sql = qq~SELECT category_id, parent_id, category_name FROM ss_catalog_categories~ WHERE parent_id IS ?; my $sth = $dbh->prepare($sql); $sth->execute($parent); return format_results($sth->fetchall_arrayref({})); }
    This should at least give you an idea to go on - remember, this code is untested, but I've used the same idea before lots of times.
Re: Nested Categories
by punkish (Priest) on Jan 03, 2005 at 17:56 UTC
Re: Nested Categories
by jZed (Prior) on Jan 03, 2005 at 19:13 UTC
    Google for "CELKO nested sets" to find Joe Celko's excellent nested set method for dealing with tree structures in databases. Also check out DBIx::Tree and DBIx::Tree::NestedSets.
Re: Nested Categories
by osunderdog (Deacon) on Jan 03, 2005 at 18:01 UTC

    In your getCategories function, you can do some optimizations. fetchrow_hashref rather than fetchfow_array this will give you a hash by column so you don't have to. Use push which will get rid of the $row variable completely.

    while (my $rh = $sth->fetchrow_hashref()) { push(@{$results_data}, $rh); }

    Unless there is a good reason to loop, you could replace loop in getCategories and just call selectall_hashref

    "Look, Shiny Things!" is not a better business strategy than compatibility and reuse.

Re: Nested Categories
by holli (Abbot) on Jan 03, 2005 at 18:49 UTC
    is ist ensured, that categories are always listed before the corresponding sub-categories?
      Thanks for the suggestions.

      Yes, holli, the parent category should always be listed before the corresponding sub-categories.

      I know this may not be possible, but my goal is to do only one query on the database to grab all of the categories and then be able to sort them properly from there. Otherwise, if I had 100 or so categories I would need to do a ton of database queries and I would love to avoid that if possible.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://418991]
Approved by jfroebe
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2022-12-04 18:50 GMT
Find Nodes?
    Voting Booth?

    No recent polls found