Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Algorithm For Forum Style Trees/Threads

by Revelation (Deacon)
on Mar 18, 2005 at 22:53 UTC ( [id://440821]=perlquestion: print w/replies, xml ) Need Help??

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

Let me preface this by saying I haven't slept in more than 24 hours. I'm also going to give some background; you can skip to the last (so considering...) paragraph if you'd like to just answer my questions :)

I'm currently trying to implement a threaded forum, akin to the Mr. Fong Device located at: http://hammer.prohosting.com/~fongdev/wwwboard9/. I plan for my implementation to be mod_perl combatable (I guess mod_perl driven) and use MySQL and Cache::FastMmap in order to store data and cache it, respectively. Now, I've hit a bit of a snag with regards to parsing of the threads and the generation of html (brainfart...?) Right now I have a table of posts that as a CSV file would look like (in point of fact this is the data from DBIx::Tree):
"id","pid","subject" 1,0,"Food" 2,1,"Beans and Nuts" 3,2,"Beans" 4,2,"Nuts" 5,3,"Black Beans" 6,4,"Pecans" 7,3,"Kidney Beans" 8,7,"Red Kidney Beans" 9,7,"Black Kidney Beans" 10,1,"Dairy" 11,10,"Beverages" 12,11,"Whole Milk" 13,11,"Skim Milk" 14,10,"Cheeses" 15,14,"Cheddar" 16,14,"Stilton" 17,14,"Swiss" 18,14,"Gouda" 19,14,"Muenster" 20,11,"Coffee Milk" 21,0,"Not Food!"
I would like to generate an html page similar to the Fong example (with Food and Not Food as starter threads.) ( Things get a bit more interesting here :) ) DBIx::Tree and Sort::Tree both have algorithms for generating this type of tree; for DBIx::Tree, I would simply have to create a display_tree subroutine that incremented and decremented levels and printed  <ul> </ul>, based on that. However, I need to modify the modules to fit my needs. What are my needs you ask? In order to appropriately generate HTML (and personal preference), instead of hashrefs, I use objects with get methods of 'id','pid', and 'subject' as data. In order to not have to retrieve a table of posts every request, I have decided to store either a hash or an array, or array of hashes (etc.) in memory (using Cache::FastMmap) from which I can generate HTML directly. Moreover, for performance reasons (this is the kicker), I would like to be able to insert data into this array/hash (probably hash) and still appropriately generate HTML. My first question is: does this caching mechanism make _any_ sense? Considering these needs, I currently generate an array of hashes, like so:
$sth->execute; my @cols = ( ); @cols[0..2] = ( ); $sth->bind_columns( undef, \(@cols) ); while ( $sth->fetch ) { my $o = Forum::Post->new([ @cols[0..2] ]); push( @{ $children{ $o->pid } }, $o->id ) and $obj{ $o->id } = +$o; }
So considering the data structure I have (two hashes)- one which is keyed with object ids and whose values are the objects themselves, and the other which stores the children for each object, what would be a good way to generate a tree? I assume I would want to create an ordered list, with an arrayref  [objlevel,obj], and call a display_item() subroutine on each element? What would be the ideal algorithm for generating such a list from these hashes (DBIx::Tree has a linear model, which I can't, for the life of me understand, a recursive model, but comments that the next step is to optimize the algorithm for both of them, and Sort::Tree has a recursive model as well)? The zero node simply exists to index root nodes. I guess that's my real questions.

I've included some example input hashes (I use hashes, because in reality, the indexes may not be contiguous numbers) and the desired output array (I've removed the OO elements of the hash).
my %children = ( 0 => [1,21], 1 => [2,10], 2 => [3,4], 3 => [5,7], 7 => [8,9], 4 => [6], 10 => [11,14], 11 => [12,13,20], 14 => [15,16,17,18,19] ); my %obj = ( 1 => "Food", 2 => "Beans and Nuts", 3 => "Beans", 4 => "Nuts", 5 => "Black Beans", 6 => "Pecans", 7 => "Kidney Beans", 8 => "Red Kidney Beans", 9 => "Black Kidney Beans", 10 => "Dairy", 11 => "Beverages", 12 => "Whole Milk", 13 => "Skim Milk", 14 => "Cheeses", 15 => "Cheddar", 16 => "Stilton", 17 => "Swiss", 18 => "Gouda", 19 => "Muenster", 20 => "Coffee Milk", 21 => "Not Food!", ); my @out = ( [1,'Food'],[2,'Beans and Nuts'],[3,'Beans'],[4,'Black Bean +s'],[4,'Kidney Beans'],[5,'Red Kiney Beans'],[5,'Black Kidney Beans'] +,[3,'Nuts'],[4,'Pecans'],[2,'Dairy'],[3,'Beverages'],[4,'Whole Milk'] +,[4,'Skim Milk'], [4,'Coffee Milk'], [3,'Cheeses'], [4,'Cheddar'],[4, +'Stilton'],[4,'Swiss'],[4,'Gouda'],[4,'Muenster'],[1,'Not Food!']);
On second thought, it probably makes more sense to cache @out, but I still need to know the best way to get from %children and %obj (on the initial SQL query) to @out.

The most efficient algorithm I can think of (more efficient than Sort::Tree's, at least) would be:
my @mystack; my $i = 1; tree_children('0'); sub tree_children { my $r = shift; # push(@mystack,$obj{$r}) unless $r eq '0'; if ($children{$r}) { for (@{ $children{$r} }) { push(@mystack,[$_,$obj{$_}]); $i++; tree_children($_); $i--; } } }
But I would like to know if somebody could explain the DBIx::Tree linear method to me, or explain a better method if one exists.

Update : In considering, I think the recursive algorithm is probably the fastest for this problem. The question, then, is, is there a faster algorithm to generate code directly from a database request? Rather than storing a hash, is there a way to create orphaned trees of children and then link them up? That seems like it would get rid of the intermediary step of the two hashes...

Gyan Kapur

Replies are listed 'Best First'.
A reply falls below the community's threshold of quality. You may see it by logging in.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2024-03-28 19:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found