NAME

Tree::Simple - A simple tree object

SYNOPSIS

  use Tree::Simple;
  
  # make a tree root
  my $tree = Tree::Simple->new("0", Tree::Simple->ROOT);
  
  # explicity add a child to it
  $tree->addChild(Tree::Simple->new("1"));
  
  # specify the parent when creating
  # an instance and it adds the child implicity
  my $sub_tree = Tree::Simple->new("2", $tree);
  
  # chain method calls
  $tree->getChild(0)->addChild(Tree::Simple->new("1.1"));
  
  # add more than one child at a time
  $sub_tree->addChildren(
            Tree::Simple->new("2.1"),
            Tree::Simple->new("2.2")
            );

  # add siblings
  $sub_tree->addSibling(Tree::Simple->new("3"));
  
  # insert children a specified index
  $sub_tree->insertChild(1, Tree::Simple->new("2.1a"));
  
  # clean up circular references
  $tree->DESTROY();

DESCRIPTION

This module in an fully object-oriented implementation of a simple n-ary tree. It is built upon the concept of parent-child relationships, so therefore every Tree::Simple object has both a parent and a set of children (who themselves may have children, and so on). Every Tree::Simple object also has siblings, as they are just the children of their immediate parent.

It is can be used to model hierarchal information such as a file-system, the organizational structure of a company, an object inheritance hierarchy, versioned files from a version control system or even an abstract syntax tree for use in a parser. It makes no assumptions as to your intended usage, but instead simply provides the structure and means of accessing and traversing said structure.

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 $parent argument to the constructor must be a Tree::Simple object or an object derived from Tree::Simple, 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.

I consider this module to be production stable, it is based on a module which has been in use on a few production systems for approx. 2 years now with no issue. The only difference is that the code has been cleaned up a bit, comments added and the thorough tests written for its public release. I am confident it behaves as I would expect it to, and is (as far as I know) bug-free. I have not stress-tested it under extreme duress, but I don't so much intend for it to be used in that type of situation. If this module cannot keep up with your Tree needs, i suggest switching to one of the modules listed in the "OTHER TREE MODULES" section below.

CONSTANTS

ROOT: This class constant serves as a placeholder for the root of our tree. If a tree does not have a parent, then it is considered a root.

METHODS

Constructor

new ($node, $parent): The constructor accepts two arguments a $node value and an optional $parent. The $node value can be any scalar value (which includes references and objects). The optional $parent value must be a Tree::Simple object, or an object derived from Tree::Simple. Setting this value implies that your new tree is a child of the parent tree, and therefore adds it to the parent's children. If the $parent is not specified then its value defaults to ROOT.

Mutators

setNodeValue ($node_value)

This sets the node value to the scalar $node_value, an exception is thrown if $node_value is not defined.

setUID ($uid)

This allows you to set your own unique ID for this specific Tree::Simple object. A default value derived from the object's hex address is provided for you, so use of this method is entirely optional. It is the responsibility of the user to ensure the value's uniqueness, all that is tested by this method is that $uid is a true value (evaluates to true in a boolean context). For even more information about the Tree::Simple UID see the getUID method.

addChild ($tree)

This method accepts only Tree::Simple objects or objects derived from Tree::Simple, an exception is thrown otherwise. This method will append the given $tree to the end of it's children list, and set up the correct parent-child relationships. This method is set up to return its invocant so that method call chaining can be possible. Such as:

  my $tree = Tree::Simple->new("root")->addChild(Tree::Simple->new("child one"));

Or the more complex:

  my $tree = Tree::Simple->new("root")->addChild(
                         Tree::Simple->new("1.0")->addChild(
                                     Tree::Simple->new("1.0.1")     
                                     )
                         );

addChildren (@trees)

This method accepts an array of Tree::Simple objects, and adds them to it's children list. Like addChild this method will return its invocant to allow for method call chaining.

insertChild ($index, $tree)

This method accepts a numeric $index and a Tree::Simple object ($tree), and inserts the $tree into the children list at the specified $index. This results in the shifting down of all children after the $index. The $index is checked to be sure it is the bounds of the child list, if it out of bounds an exception is thrown. The $tree argument's type is verified to be a Tree::Simple or Tree::Simple derived object, if this condition fails, an exception is thrown.

insertChildren ($index, @trees)

This method functions much as insertChild does, but instead of inserting a single Tree::Simple, it inserts an array of Tree::Simple objects. It too bounds checks the value of $index and type checks the objects in @trees just as insertChild does.

removeChild ($child | $index)>

Accepts two different arguemnts. If given a Tree::Simple object ($child), this method finds that specific $child by comparing it with all the other children until it finds a match. At which point the $child is removed. If no match is found, and exception is thrown. If a non-Tree::Simple object is given as the $child argument, an exception is thrown.

This method also accepts a numeric $index and removes the child found at that index from it's list of children. The $index is bounds checked, if this condition fail, an exception is thrown.

When a child is removed, it results in the shifting up of all children after it, and the removed child is returned. The removed child is properly disconnected from the tree and all its references to its old parent are removed. However, in order to properly clean up and circular references the removed child might have, it is advised to call it's DESTROY method. See the "CIRCULAR REFERENCES" section for more information.

addSibling ($tree)

addSiblings (@trees)

insertSibling ($index, $tree)

insertSiblings ($index, @trees)

The addSibling, addSiblings, insertSibling and insertSiblings methods pass along their arguments to the addChild, addChildren, insertChild and insertChildren methods of their parent object respectively. This eliminates the need to overload these methods in subclasses which may have specialized versions of the *Child(ren) methods. The one exceptions is that if an attempt it made to add or insert siblings to the ROOT of the tree then an exception is thrown.

NOTE: There is no removeSibling method as I felt it was probably a bad idea. The same effect can be achieved by manual upwards traversal.

Accessors

getNodeValue: This returns the value stored in the object's node field.
getUID: This returns the unique ID associated with this particular tree. This can be custom set using the setUID method, or you can just use the default. The default is the hex-address extracted from the stringified Tree::Simple 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).
getChild ($index): This returns the child (a Tree::Simple object) found at the specified $index. Note that we do use standard zero-based array indexing.
getAllChildren: This returns an array of all the children (all Tree::Simple objects). It will return an array reference in scalar context.
getSibling ($index)
getAllSiblings: Much like addSibling and addSiblings, these two methods simply call getChild and getAllChildren on the invocant's parent.
getDepth: Returns a number representing the invocant's depth within the hierarchy of Tree::Simple objects.
getParent: Returns the invocant's parent, which could be either ROOT or a Tree::Simple object.
getChildCount: Returns the number of children the invocant contains.
getIndex: Returns the index of this tree within its parent's child list. Returns -1 if the tree is the root.

Predicates

isLeaf: Returns true (1) if the invocant does not have any children, false (0) otherwise.
isRoot: Returns true (1) if the invocant's "parent" field is ROOT, returns false (0) otherwise.

Recursive Functions

traverse ($func)

This method takes a single argument of a subroutine reference $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 all the children 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");
        });

size

Returns the total number of nodes in the current tree and all its sub-trees.

height

Returns the length of the longest path from the current tree to the furthest leaf node.

Misc. Functions

accept ($visitor)

It accepts either a Tree::Simple::Visitor object (which includes classes derived from Tree::Simple::Visitor), or an object who has the 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.

I have also created a number of Visitor objects and packaged them into the Tree::Simple::VisitorFactory.

clone

The clone method does a full deep-copy clone of the object, calling 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.

cloneShallow

This method is an alternate option to the plain clone method. This method allows the cloning of single Tree::Simple 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

To avoid memory leaks through uncleaned-up circular references, we implement the DESTROY method. This method will attempt to call DESTROY on each of its children (if it has 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.

fixDepth

For the most part, Tree::Simple will manage your tree's depth fields for you. But occasionally your tree's depth may get out of place. If you run this method, it will traverse your tree correcting the depth as it goes.

Private Methods

_init ($node, $parent, $children): This method is here largely to facilitate subclassing. This method is called by new to initialize the object, where new's primary responsibility is creating the instance.
_setParent ($parent): This method sets up the parental relationship. It is for internal use only.

CIRCULAR REFERENCES

Perl uses reference counting to manage the destruction of objects, and this can cause problems with circularly referencing object like Tree::Simple. In order to properly manage your circular references, it is nessecary to manually call the DESTROY method on a Tree::Simple instance. Here is some example code:

  # create a root
  my $root = Tree::Simple->new()
  
  { # create a lexical scope
  
      # create a subtree (with a child)
      my $subtree = Tree::Simple->new("1")
                          ->addChild(
                              Tree::Simple->new("1.1")
                          );
                          
      # add the subtree to the root                    
      $root->addChild($subtree);                    
      
      # ... do something with your trees 
      
      # remove the first child
      $root->removeChild(0);
  }

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 child, 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::Simple->new()
  
  { # create a lexical scope
  
      # create a subtree (with a child)
      my $subtree = Tree::Simple->new("1")
                          ->addChild(
                              Tree::Simple->new("1.1")
                          );
                          
      # add the subtree to the root                    
      $root->addChild($subtree);                    
      
      # ... do something with your trees 
      
      # remove the first child and capture it
      my $removed = $root->removeChild(0);
      
      # 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.

BUGS

None that I am aware of. The code is pretty thoroughly tested (see "CODE COVERAGE" below) and is based on an (non-publicly released) module which I had used in production systems for about 2 years without incident. Of course, if you find a bug, let me know, and I will be sure to fix it.

CODE COVERAGE

I use Devel::Cover to test the code coverage of my tests, below is the Devel::Cover report on this module's test suite.

 ------------------------ ------ ------ ------ ------ ------ ------ ------
 File                       stmt branch   cond    sub    pod   time  total
 ------------------------ ------ ------ ------ ------ ------ ------ ------
 Tree/Simple.pm            100.0   97.9   86.7  100.0   96.7   94.7   97.4
 Tree/Simple/Visitor.pm    100.0   96.2   90.0  100.0  100.0    5.3   97.7
 ------------------------ ------ ------ ------ ------ ------ ------ ------
 Total                     100.0   97.5   87.5  100.0   97.4  100.0   97.5
 ------------------------ ------ ------ ------ ------ ------ ------ ------

OTHER TREE MODULES

There are a few other Tree modules out there, here is a quick comparison between Tree::Simple and them. Obviously I am biased, so take what I say with a grain of salt, and keep in mind, I wrote Tree::Simple because I could not find a Tree module that suited my needs. If Tree::Simple does not fit your needs, I recommend looking at these modules. Please note that I only list registered Tree::* modules here, I have only seen a few other modules outside of that namespace that seem to fit, although most of them are part of another distribution (HTML::Tree, Pod::Tree, etc).

Tree::DAG_Node

This module seems pretty stable and very robust, but it is also very large module. It is approx. 3000 lines with POD, and 1,500 without the POD. The shear depth and detail of the documentation and the ratio of code to documentation is impressive, and not to be taken lightly. Tree::Simple, by comparison, is around 500 lines of code and another 330 lines of documentation. Tree::DAG_Node is part of the reason why I wrote Tree::Simple, the author contends that you can use Tree::DAG_Node for simpler purposes if you so desire, for me it is too beefy.

My other issue with Tree::DAG_Node is its test-suite. There is one test, and that is that the module loads. This is not acceptable to me, no matter how good a module is.

Tree::Nary

It is a (somewhat) direct translation of the N-ary tree from the GLIB library, and the API is based on that. GLIB is a C library, which means this is a very C-ish API. That doesn't appeal to me, it might to you, to each their own.

This module is similar in intent to Tree::Simple. It implements a tree with n branches and has polymorphic node containers. It implements much of the same methods as Tree::Simple and a few others on top of that, but being based on a C library, is not very OO. In most of the method calls the $self argument is not used and the second argument $node is. Tree::Simple is a much more OO module than Tree::Nary, so while they are similar in functionality they greatly differ in implementation style.

Tree

This module is pretty old, it has not been updated since Oct. 31, 1999 and is still on version 0.01. It also seems to be (from the limited documentation) a balanced tree, Tree::Simple makes no attempt to balance anything.

Tree::Ternary

This module is older than Tree, last update was Sept. 24th, 1999. It seems to be a special purpose tree, for storing and accessing strings, not general purpose like Tree::Simple.

Tree::Ternary_XS

This module is an XS implementation of the above tree type.

Tree::Trie

This too is a specialized tree type, it sounds similar to the Tree::Ternary, but it much newer (latest release in 2003). It seems specialized for the lookup and retrieval of information like a hash.

Tree::M

Is a wrapper for a C++ library, whereas Tree::Simple is pure-perl. It also seems to be a more specialized implementation of a tree, therefore not really the same as Tree::Simple.

Tree::Fat

Is a wrapper around a C library, again Tree::Simple is pure-perl. The author describes FAT-trees as a combination of a Tree and an array. It looks like a pretty mean and lean module, and good if you need speed and are implementing a custom data-store of some kind. The author points out too that the module is designed for embedding and there is not default embedding, so you can't really use it "out of the box".

ACKNOWLEDGEMENTS

Thanks to Nadim Ibn Hamouda El Khemir for making Data::TreeDumper work with Tree::Simple.
Thanks to Brett Nuske for his idea for the getUID and setUID methods.
Thanks to whoever submitted the memory leak bug to RT (#7512).

AUTHOR

stevan little, <stevan@iinteractive.com>

COPYRIGHT AND LICENSE

http://www.iinteractive.com

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

To install Tree::Simple, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Tree::Simple

CPAN shell

perl -MCPAN -e shell
install Tree::Simple

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)