NYCPHP Meetup

[(kris)janis p gale]

the trees thread made me realize it was a topic near and dear to my heart,
since way-back-when i had devoted pretty much an entire day's
research-and-development effort towards devising a method of not only
creating an arbitrarily-deep tree structure using a single self-referencing
table, but also be able to traverse such a structure with relative ease...

my development environment at the time was a windows nt box running
coldfusion and access as a db -- so recursion was NOT an option, not only
because coldfusion doesn't even support recursion, but also due to the total
lack of resources on that puny development box...

call me crazy, but i actually Enjoy developing iterative algorithms for
problems that usually lend themselves to recursion, especially when even
brainstorming such an iterative solution would send most developers
screaming out the door in search of fresh air and daylight.

anyways, porting my coldfusion script to php proved extremely rudimentary.

i created a basic table for this exercise, called "test"
it has three fields -- id [int], parent_id [int], and name [varchar(64)]
there's an index on id (primary) and parent_id

contents of "test":

id, parent_id, name

3, 0, primary1
2, 0, primary2
1, 0, primary3
5, 3, secondary1
6, 3, secondary2
4, 1, secondary3
7, 5, tertiary1
8, 4, tertiary2
9, 4, tertiary3


my assumption here is that
a top-level item's parent_id is to be zero.
(i could have just as easily used NULL.)


the code to display this tree:
----


<?php

$mc = mysql_connect("localhost") or die("!mysql_connect");
$md = mysql_select_db("mysql",$mc) or die("!mysql_select_db");

$mq = mysql_query("SELECT id, parent_id, name FROM test ORDER BY name") or
die("!mysql_query");
$nrows = mysql_num_rows($mq);

$data = array_fill(0,$nrows,NULL);
$n = 0;
while($mfa = mysql_fetch_array($mq,MYSQL_ASSOC))
 $data[$n++] = $mfa;

mysql_free_result($mq);
mysql_close($mc);

$id_list = array();
$row_list = array();
$depth_list = array();

for($n = 0 ; $n < $nrows ; $n++)
 if($data[$n]["parent_id"] == 0)
 { array_push($id_list,$data[$n]["id"]);
  array_push($row_list,$n);
  array_push($depth_list,0);
 }

while(count($id_list) < $nrows)
{ $id_temp = array();
 $row_temp = array();
 $depth_temp = array();
 for($i = 0 ; $i < count($id_list) ; $i++)
 { $id = $id_list[$i];
  $row = $row_list[$i];
  $depth = $depth_list[$i];
  array_push($id_temp,$id);
  array_push($row_temp,$row);
  array_push($depth_temp,$depth);
  for($j = 0 ; $j < $nrows ; $j++)
   if(($data[$j]["parent_id"] == $id)
   && (array_search($data[$j]["id"],$id_list) == NULL))
   { array_push($id_temp,$data[$j]["id"]);
    array_push($row_temp,$j);
    array_push($depth_temp,$depth + 1);
   }
 }
 $id_list = $id_temp;
 $row_list = $row_temp;
 $depth_list = $depth_temp;
}

print('<pre>');
for($n = 0 ; $n < $nrows ; $n++)
 print(str_repeat("----",$depth_list[$n]) . $data[$row_list[$n]]["name"] .
'<br>');
print('</pre>');

?>


----
the useful variables created by the end result of this code
is as such...

$nrows
number of rows in your dataset

$data[][]
contains the entirety of your data, in a two-dimensional array

$row_list[]
a single dimentional array that you'll use to index rows
of $data in tree-order, not in alphabetical or row-order
(see the very end of the above code to see what i mean)

$depth_list[]
the depth of each item in the tree, in tree-order
(see above how i used this variable to indent
the displayed item to show its depth in the tree)

----

see the code in action:
http://krisgale.com/code/tree.php

----

incidentally, anyone have a job for me?
i truly miss solid development work like this...
(database-driven web applications is my forté)

my resumé:
http://krisgale.com/work/kpg_resume.gif


regards,
- kris gale