|
Tree::Binary - A Object Oriented Binary Tree for Perl |
Tree::Binary - A Object Oriented Binary Tree for Perl
use Tree::Binary;
# a tree representaion of the expression:
# ((2 + 2) * (4 + 5))
my $btree = Tree::Binary->new("*")
->setLeft(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("2"))
->setRight(Tree::Binary->new("2"))
)
->setRight(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("4"))
->setRight(Tree::Binary->new("5"))
);
# Or shown visually:
# +---(*)---+
# | |
# +-(+)-+ +-(+)-+
# | | | |
# (2) (2) (4) (5)
# get a InOrder visitor my $visitor = Tree::Binary::Visitor::InOrderTraversal->new(); $btree->accept($visitor);
# print the expression in infix order print $visitor->getAccumulation(); # prints "2 + 2 * 4 + 5"
# get a PreOrder visitor my $visitor = Tree::Binary::Visitor::PreOrderTraversal->new(); $btree->accept($visitor);
# print the expression in prefix order print $visitor->getAccumulation(); # prints "* + 2 2 + 4 5"
# get a PostOrder visitor my $visitor = Tree::Binary::Visitor::PostOrderTraversal->new(); $btree->accept($visitor);
# print the expression in postfix order print $visitor->getAccumulation(); # prints "2 2 + 4 5 + *"
# get a Breadth First visitor my $visitor = Tree::Binary::Visitor::BreadthFirstTraversal->new(); $btree->accept($visitor);
# print the expression in breadth first order print $visitor->getAccumulation(); # prints "* + + 2 2 4 5"
# be sure to clean up all circular references $btree->DESTROY();
This module is a fully object oriented implementation of a binary tree. Binary trees are a specialized type of tree which has only two possible branches, a left branch and a right branch. While it is possible to use an n-ary tree, like the Tree::Simple manpage, to fill most of your binary tree needs, a true binary tree object is just easier to mantain and use.
Binary Tree objects are especially useful (to me anyway) when building parse trees of things like mathematical or boolean expressions. They can also be used in games for such things as descisions trees. Binary trees are a well studied data structure and there is a wealth of information on the web about them.
This module uses exceptions and a minimal Design By Contract style. All method arguments are required unless specified in the documentation, if a required argument is not defined an exception will usually be thrown. Many arguments are also required to be of a specific type, for instance the $tree argument to both the setLeft and setRight methods, must be a Tree::Binary object or an object derived from Tree::Binary, otherwise an exception is thrown. This may seems harsh to some, but this allows me to have the confidence that my code works as I intend, and for you to enjoy the same level of confidence when using this module. Note however that this module does not use any Exception or Error module, the exceptions are just strings thrown with die.
This object uses a number of methods copied from another module of mine, Tree::Simple. Users of that module will find many similar methods and behaviors. However, it did not make sense for Tree::Binary to be derived from Tree::Simple, as there are a number of methods in Tree::Simple that just wouldn't make sense in Tree::Binary. So, while I normally do not approve of cut-and-paste code reuse, it was what made the most sense in this case.
$node value argument. The $node value can be any scalar value (which includes references and objects).
$node_value
$uid is a true value (evaluates to true in a boolean context). For even more information about the Tree::Binary UID see the getUID method.
$tree to be the left subtree of the current Tree::Binary object.
DESTROY method. See the CIRCULAR REFERENCES section for more information.
$tree to be the right subtree of the current Tree::Binary object.
DESTROY method. See the CIRCULAR REFERENCES section for more information.
setUID method, or you can just use the default. The default is the hex-address extracted from the stringified Tree::Binary object. This may not be a universally unique identifier, but it should be adequate for at least the current instance of your perl interpreter. If you need a UUID, one can be generated with an outside module (there are many to choose from on CPAN) and the setUID method (see above).
1), otherwise it will return false (0).
1) if the current Tree::Binary object has a left subtree, otherwise it will return false (0).
1) if the current Tree::Binary object has a right subtree, otherwise it will return false (0).
1) if the current Tree::Binary object is the root (it does not have a parent), otherwise it will return false (0).
$func. If the argument is not defined and is not in fact a CODE reference then an exception is thrown. The function is then applied recursively to both subtrees of the invocant. Here is an example of a traversal function that will print out the hierarchy as a tabbed in list.
$tree->traverse(sub {
my ($_tree) = @_;
print (("\t" x $_tree->getDepth()), $_tree->getNodeValue(), "\n");
});
=item B<mirror>
This method will swap the left node for the right node and then do this recursively on down the tree. The result is the tree is a mirror image of what it was. So that given this tree:
+---(-)---+
| |
+-(*)-+ +-(+)-+
| | | |
(1) (2) (4) (5)
Calling mirror will result in your tree now looking like this:
+---(-)---+
| |
+-(+)-+ +-(*)-+
| | | |
(5) (4) (2) (1)
It should be noted that this is a destructive action, it will alter your current tree. Although it is easily reversable by simply calling mirror again. However, if you are looking for a mirror copy of the tree, I advise calling clone first.
my $mirror_copy = $tree->clone()->mirror();
Of course, the cloning operation is a full deep copy, so keep in mind the expense of this operation. Depending upon your needs it may make more sense to call mirror a few times and gather your results with a Visitor object, rather than to clone.
visit method available (tested with $visitor->can('visit')). If these qualifications are not met, and exception will be thrown. We then run the Visitor's visit method giving the current tree as its argument.
clone recursively on all its children. This does not call clone on the parent tree however. Doing this would result in a slowly degenerating spiral of recursive death, so it is not recommended and therefore not implemented. What it does do is to copy the parent reference, which is a much more sensible act, and tends to be closer to what we are looking for. This can be a very expensive operation, and should only be undertaken with great care. More often than not, this method will not be appropriate. I recommend using the cloneShallow method instead.
clone method. This method allows the cloning of single Tree::Binary object while retaining connections to the rest of the tree/hierarchy. This will attempt to call clone on the invocant's node if the node is an object (and responds to $obj->can('clone')) otherwise it will just copy it.
DESTROY method. This method will attempt to call DESTROY on each of its children (if it as any). This will result in a cascade of calls to DESTROY on down the tree. It also cleans up it's parental relations as well.
Because of perl's reference counting scheme and how that interacts with circular references, if you want an object to be properly reaped you should manually call DESTROY. This is especially nessecary if your object has any children. See the section on CIRCULAR REFERENCES for more information.
Perl uses reference counting to manage the destruction of objects, and this can cause problems with circularly referencing object like Tree::Binary. In order to properly manage your circular references, it is nessecary to manually call the DESTROY method on a Tree::Binary instance. Here is some example code:
# create a root my $root = Tree::Binary->new()
{ # create a lexical scope
# create a subtree (with a child)
my $subtree = Tree::Binary->new("1")
->setRight(
Tree::Binary->new("1.1")
);
# add the subtree to the root
$root->setLeft($subtree);
# ... do something with your trees
# remove the first child
$root->removeLeft();
}
At this point you might expect perl to reap $subtree since it has been removed from the $root and is no longer available outside the lexical scope of the block. However, since $subtree itself has a subtree, its reference count is still (at least) one and perl will not reap it. The solution to this is to call the DESTROY method manually at the end of the lexical block, this will result in the breaking of all relations with the DESTROY-ed object and allow that object to be reaped by perl. Here is a corrected version of the above code.
# create a root my $root = Tree::Binary->new()
{ # create a lexical scope
# create a subtree (with a child)
my $subtree = Tree::Binary->new("1")
->setRight(
Tree::Binary->new("1.1")
);
# add the subtree to the root
$root->setLeft($subtree);
# ... do something with your trees
# remove the first child and capture it
my $removed = $root->removeLeft();
# now force destruction of the removed child
$removed->DESTROY();
}
As you can see if the corrected version we used a new variable to capture the removed tree, and then explicitly called DESTROY upon it. Only when a removed subtree has no children (it is a leaf node) can you safely ignore the call to DESTROY. It is even nessecary to call DESTROY on the root node if you want it to be reaped before perl exits, this is especially important in long running environments like mod_perl.
As crazy as it might seem, there are no pure (non-search) binary tree implementations on CPAN (at least not that I could find). I found several balanaced trees of one kind or another (see the OTHER TREE MODULES section of the Tree::Binary::Search documentation for that list). The closet thing I could find was the Tree module described below.
This module is part of a larger group, which are listed below.
None that I am aware of. Of course, if you find a bug, let me know, and I will be sure to fix it.
I use Devel::Cover to test the code coverage of my tests, below is the Devel::Cover report on this module test suite.
-------------------------------------------- ------ ------ ------ ------ ------ ------ ------ File stmt branch cond sub pod time total -------------------------------------------- ------ ------ ------ ------ ------ ------ ------ Tree/Binary.pm 100.0 97.3 93.9 100.0 100.0 71.7 98.7 Tree/Binary/Search.pm 99.0 90.5 81.2 100.0 100.0 13.9 95.1 Tree/Binary/Search/Node.pm 100.0 100.0 66.7 100.0 100.0 11.7 98.2 Tree/Binary/VisitorFactory.pm 100.0 100.0 n/a 100.0 100.0 0.5 100.0 Tree/Binary/Visitor/Base.pm 100.0 100.0 66.7 100.0 100.0 0.5 96.4 Tree/Binary/Visitor/BreadthFirstTraversal.pm 100.0 100.0 100.0 100.0 100.0 0.0 100.0 Tree/Binary/Visitor/InOrderTraversal.pm 100.0 100.0 100.0 100.0 100.0 1.1 100.0 Tree/Binary/Visitor/PostOrderTraversal.pm 100.0 100.0 100.0 100.0 100.0 0.3 100.0 Tree/Binary/Visitor/PreOrderTraversal.pm 100.0 100.0 100.0 100.0 100.0 0.3 100.0 -------------------------------------------- ------ ------ ------ ------ ------ ------ ------ Total 99.6 94.4 88.8 100.0 100.0 100.0 97.4 -------------------------------------------- ------ ------ ------ ------ ------ ------ ------
stevan little, <stevan@iinteractive.com>
Copyright 2004, 2005 by Infinity Interactive, Inc.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
|
Tree::Binary - A Object Oriented Binary Tree for Perl |