-----------------------------------
tree.lib.php -- readme
-----------------------------------

A Tree library for PHP 4 / PHP 5
 
This package arose from the need for a simple, memory 
efficient and upwards compatible tree module.
It provides
- n-ary trees
- efficient traversal, using pseudo-pointers "up", 
  "down" and "right"
- storage facility for arbitrary data within the nodes

Two shortcomings of PHP are addressed by this package:
- memory hogging: both arrays and objects reserve huge 
  chunks of memory for each element or instance. For 
  example, a simple array holding 64K characters takes 
  4 MB of RAM.  Nested arrays reserve multiples of this
- The OOP model and implementation of references changed 
  significantly between PHP4 and PHP5, making it 
  difficult or impossible to write portable code using 
  object references

The present package uses fixed-length tables implemented 
with the string datatype. Instead of references, it 
implements pseudo-pointers, using integer indexes into 
these tables. Think C.

The storage capacity is limited by the constant 
TREE_POINTLEN (default: 2 bytes). The highest number
that can be stored in the pointer (actually, -1) is the 
maximum total number of nodes the tree can hold,
including deleted nodes. The depth of the tree and the 
number of branches is not limited, although depth values 
will not be reported correctly for values taking more than 
8*TREE_POINTLEN-4 bits (the missing four bits are used for 
a checksum). Thus, with the default pointer size, the tree 
depth is effectively limited to 2^12 == 4096.
The upper limit to TREE_POINTLEN is constituted by PHP's 
maxint (4 bytes).

A disadvantage: No garbage collection implemented; our 
pseudo-memory (stored in the strings) grows with each "add" 
operation, but does not free unused space after "delete" 
operations. (Can be retrofitted by changing the "newnode" 
logic to use previously freed space instead of claiming new) 
Ignore this problem if you use the tree mainly to store and 
retrieve data, and if you don't reorganize the tree 
extensively (many prune and graft operations)

A comparison with Richard Heyes' object-oriented Tree-Class 
1.0.3. shows, how and where this approach is more 
efficient, while not sacrificing speed:

                     tree.lib.php        Tree-1.0.3.php
                     ------------        --------------
insert 4096          CPU: 0.577s         CPU: 0.186s
nodes in bintree     MEM: 0.3M           MEM: 3.5M

get flat list        CPU: 0.099s         CPU: 0.064s
from this tree       MEM: 243K           MEM: 206K

remove this tree's   CPU: 0.125s         CPU: 0.001s
root node            MEM: 3456B          MEM: 16B


-----------------------------------
Page: PHP/tree.lib.readme.htm
mtime: Sat Nov 11 18:17:51 CET 2006