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!"
[download]

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; 
     }
[download]

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!']);
[download]

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--;
    }
  }
}
[download]

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...

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.