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

I've been trying to find a decent, generic way of creating a variable level category structure. Also, a way of using that structure to display a table of contents, which are really a subset of a category structure.

Someone pointed out that I'm probably looking for a concept called 'tree structure' or something to that effect, and gave me a link or two but I'm having a hard time making the transition from white paper to real code.

Does anyone know of a decent tutorial that will help me bridge that gap?

Harley J Pig

Replies are listed 'Best First'.
Re: Categories. Table of Contents. Trees?
by monarch (Priest) on Nov 04, 2005 at 01:26 UTC
    It sounds like you may be looking for a basic tutorial on the definition of a tree structure. If that is so, I recommend having a look at Wikipedia (tree structures) which I'm finding has good introductions to basic computer science concepts such as this these days..

    As an aside, I think Perl lends itself quite naturally to tree structures. Having references makes building trees very simple. For example, consider a table of contents:

    my %contents = ( 1 => [ 'Introduction', undef ], 2 => [ 'Design', { 1 => [ 'Wheels', undef ], 2 => [ 'Frame', undef ], 3 => [ 'Electronics', { 1 => [ 'Dashboard', undef ], 2 => [ 'Fuel Injection', undef ], }, 4 => [ 'Petrol Tank', undef ], }, 3 => [ 'Summary', undef ], );

    Merely defining things these ways is, by definition, a tree. If references are tripping you up, then read about pointers.. and re-read until you become more comfortable with this concept.

Re: Categories. Table of Contents. Trees?
by ickyb0d (Monk) on Nov 03, 2005 at 23:27 UTC

    Tree.pm looks like a pretty decent start for you. If not, you might consider making your own module. If you make your own module there are a few things to take into consideration.

    • Each node should have a unique id
    • Each node should have a parent id that it refers to (0 if it has no parents)
    • Each node may have children nodes

    Is this a tree that you will be creating from scratch? or reading in from a file or system (i.e. directory tree). After quickly looking at CPAN it seems theres a few modules. For my needs, i've always made my own since my nodes require more complex objects than just parent/child relationships. The main idea behind a tree layout is the parent/child relationship; so if you can get that down the rest should eventually fall into place. Hope this helps.

      For my immediate purposes I need to take a mysql structure set up like so:

      Book Name <-> Chapter Name <-> Sentence text

      where the <-> is a lookup table and Chapter name exists only once in the database, but has a 1:N relationship with books (i.e., Chapter 1 exists in many books). This is where I'm having a problem converting from. I'm not sure how I handle the unique id per node, or how to recalculate or anything else along those lines. This is new territory for me. I think I'm going to have to get the book suggested below.

      I ran across Tree.pm awhile ago, thanks for refreshing my memory on it.

      Harley J Pig
        I smell over-abstraction.

        Unless space is truly at a premium, I would strongly suggest a design where you have a book table (with id, name, publisher, etc) and a chapter table (with a book_id, position_id, name, etc). And then not worry about the fact that some chapter names are replaced. Then just use the database in the obvious way for the specific query.

        As an example of why, consider how much work it takes with your schema to change the name of a chapter in a book if it was misentered. Think of how little work it takes with my schema. Another example of why, think of how much work you're putting out now to try to figure out how to make hierarchies completely generic. I guarantee that when you're done, your code will be a lot harder to understand and be a lot slower than the obvious, straightforward approach.

        My general rule of thumb says, Do not try to come up with an abstraction until I am solving a problem for the third time. Why? Well the first time I have no idea what is important or what kinds of changes I'll have. So I'll over-design for things that I won't need. (Plus I may never face this problem again.) The second time I'll design a great solution for my second problem, and will be shocked at things that are different. (This time I'm more likely to face it again.) But the third time I have enough of a sense of the problem that I have a chance of coming up with something useful. (And if I've faced it three times, I'll almost definitely see it again.)

        This is where I'm having a problem converting from. I'm not sure how I handle the unique id per node, or how to recalculate or anything else along those lines

        The way you might want to handle it in the DB is to have each table have a parent_id column. This parent_id would refer to the unique id of a row entry. So a 'Chapter 1' row entry in the chapter table might have a parent id of '32'. Where '32' is the book_id of the book 'Moby Dick'. Or something along those lines. I assume you would want this for your chapter and sentance tables. As previously stated, to do this you would have to have multiple entries of 'Chapter X' dependant on each book.

Re: Categories. Table of Contents. Trees?
by samtregar (Abbot) on Nov 03, 2005 at 23:51 UTC
    I recommend you pick up a copy of Mastering Algorithms in Perl. It will teach you all about trees and many other useful data-structures. There are lots of other good algorithm books around, of course, but if you're going to be coding in Perl this one will be the most immediately useful.


Re: Categories. Table of Contents. Trees?
by NetWallah (Canon) on Nov 04, 2005 at 01:27 UTC
    Tree.pm is pretty old. Try Tree::Simple instead, with Tree::Visualize

    (I have not tried this combo,but is seems to match your needs).

    Update: Oops - I looked at the wrong module - Tree.pm is fine - in fact it is based on Tree::Simple, and simplifies it further.

         "Man cannot live by bread alone...
             He'd better have some goat cheese and wine to go with it!"