NAME

Forest - the distribution for Tree and friends

DESCRIPTION

Forest is the name for a group of related modules that all deal with trees.

NOTE: This is currently a developer release. The API is nearly-completely frozen, but we reserve the right to make incompatible changes. When 1.0 is released, its API will be backwards-compatible.

CIRCULAR REFERENCES

All the modules in this distribution use Scalar::Util's weaken() to avoid circular references. This avoids the problem of circular references in all cases.

BUGS

None that we are aware of.

The test suite for Forest is based very heavily on the test suite for Test::Simple, which has been tested extensively and is used in a number of major applications/distributions, such as Catalyst and rt.cpan.org.

TODO

• Traversals and memory

  Need tests for what happens with a traversal list and deleted nodes, particularly w.r.t. how memory is handled - should traversals weaken?

• Added NestedSets has a way of storing trees in a DB

• Provide a way of loading the payload from a secondary datastore

• Lazyload the children of the loaded tree

• Provide a way of defaulting the class if it's not a column in the DB

• Allow has_child() and get_index_for() to work with a supplied callback

NOTES

These are items to consider adding in general.

• Partial balancing

  Creating an AVL search tree

• BTree

  A special m-ary balanced tree.

  1 The root either is a leaf or has 2+ children

  2 Every node (except root/leaf) has between ceil(m/2) and m children

  3 Every path from root to leaf is the same size

• 2-3 Tree

  A BTree of order 3.

  1 All nodes have 2 or 3 children

  2 The leaves, traversed from left to right, are ordered.

  3 Insertion

  Locate where it should be and add it. If the parent's children > 3, split it into two nodes with 2 children and add the 2nd to the parent. Continue up to the root, adding a new root, if needed.

  4 Deletion

  Locate the leaf and remove it. If the parent's children < 2, merge it with an adjacent sibling, removing it from its parent. Continue up to the root, removing the root, if needed.

• Red-Black

  1 Every node has 2 children colored either red or black

  2 Every leaf is black

  3 Every red node has 2 black children

  4 Every path from the root to a leaf contains the same number of black children (called the black-height)

  Special case is an AA tree. This requires that right children must always be red. q.v. http://en.wikipedia.org/wiki/AA_tree for more info.

• Andersson

  q.v. http://www.eternallyconfuzzled.com/tuts/andersson.html

• Splay

  q.v. http://en.wikipedia.org/wiki/Splay_tree

• Scapegoat

  q.v. http://en.wikipedia.org/wiki/Scapegoat_tree

CODE COVERAGE

We use Devel::Cover to test the code coverage of our tests. Below is the Devel::Cover report on this module's test suite. We use TDD, which is why our coverage is so high.

---------------------------- ------ ------ ------ ------ ------ ------ ------
File                           stmt branch   cond    sub    pod   time  total
---------------------------- ------ ------ ------ ------ ------ ------ ------
blib/lib/Tree.pm              100.0  100.0  100.0  100.0  100.0   58.9  100.0
blib/lib/Tree/Binary.pm        96.1   95.0  100.0  100.0  100.0    7.1   96.5
blib/lib/Tree/Fast.pm          99.4   95.5   91.7  100.0  100.0   27.7   98.5
blib/lib/Tree/Persist.pm      100.0   83.3    n/a  100.0  100.0    1.5   97.6
.../lib/Tree/Persist/Base.pm  100.0   87.5  100.0  100.0  100.0    1.0   98.1
blib/lib/Tree/Persist/DB.pm   100.0    n/a    n/a  100.0    n/a    0.1  100.0
...ist/DB/SelfReferential.pm  100.0   90.0    n/a  100.0    n/a    2.6   99.1
.../lib/Tree/Persist/File.pm  100.0   50.0    n/a  100.0    n/a    0.4   96.7
.../Tree/Persist/File/XML.pm  100.0  100.0  100.0  100.0    n/a    0.8  100.0
Total                          99.3   94.4   97.7  100.0  100.0  100.0   98.6
---------------------------- ------ ------ ------ ------ ------ ------ ------

AUTHORS

Rob Kinyon <rob.kinyon@iinteractive.com>

Stevan Little <stevan.little@iinteractive.com>

Thanks to Infinity Interactive for generously donating our time.

COPYRIGHT AND LICENSE

Copyright 2004, 2005 by Infinity Interactive, Inc.

http://www.iinteractive.com

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.