Provided by: libtree-multinode-perl_1.0.10-2_all bug

NAME

       MultiNode.pm  -- a multi node tree object.  Most useful for modeling heirarchial data
       structures.

SYNOPSIS

         use Tree::MultiNode;
         use strict;
         use warnings;
         my $tree   = new Tree::MultiNode;
         my $handle = new Tree::MultiNode::Handle($tree);

         $handle->set_key("top");
         $handle->set_value("level");

         $handle->add_child("child","1");
         $handle->add_child("child","2");

         $handle->first();
         $handle->down();

         $handle->add_child("grandchild","1-1");
         $handle->up();

         $handle->last();
         $handle->down();

         $handle->add_child("grandchild","2-1");
         $handle->up();

         $handle->top();
         &dump_tree($handle);

         my $depth = 0;
         sub dump_tree
         {
           ++$depth;
           my $handle = shift;
           my $lead = ' ' x ($depth*2);
           my($key,$val);

           ($key,$val) = $handle->get_data();

           print $lead, "key:   $key\n";
           print $lead, "val:   $val\n";
           print $lead, "depth: $depth\n";

           my $i;
           for( $i = 0; $i < scalar($handle->children); ++$i ) {
             $handle->down($i);
               &dump_tree($handle);
             $handle->up();
           }
           --$depth;
         }

DESCRIPTION

       Tree::MultiNode, Tree::MultiNode::Node, and MultiNode::Handle are objects modeled after
       C++ classes that I had written to help me model heirarchical information as datastructures
       (such as the relationships between records in an RDBMS).  The tree is basicly a list of
       lists type data structure, where each node has a key, a value, and a list of children.
       The tree has no internal sorting, though all operations perserve the order of the child
       nodes.

       Creating a Tree

       The concept of creating a handle based on a tree lets you have multiple handles into a
       single tree without having to copy the tree.  You have to use a handle for all operations
       on the tree (other than construction).

       When you first construct a tree, it will have a single empty node.  When you construct a
       handle into that tree, it will set the top node in the tree as it's current node.

         my $tree   = new Tree::MultiNode;
         my $handle = new Tree::MultiNode::Handle($tree);

       Using a Handle to Manipulate the Tree

       At this point, you can set the key/value in the top node, or start adding child nodes.

         $handle->set_key("blah");
         $handle->set_value("foo");

         $handle->add_child("quz","baz");
         # or
         $handle->add_child();

       add_child can take 3 paramters -- a key, a value, and a position.  The key and value will
       set the key/value of the child on construction.  If pos is passed, the new child will be
       inserted into the list of children.

       To move the handle so it points at a child (so you can start manipulating that child),
       there are a series of methods to call:

         $handle->first();   # sets the current child to the first in the list
         $handle->next();    # sets the next, or first if there was no next
         $handle->prev();    # sets the previous, or last if there was no next
         $handle->last();    # sets to the last child
         $handle->down();    # positions the handle's current node to the
                             # current child

       To move back up, you can call the method up:

         $handle->up();      # moves to this node's parent

       up() will fail if the current node has no parent node.  Most of the member functions
       return either undef to indicate failure, or some other value to indicate success.

       $Tree::MultiNode::debug

       If set to a true value, it enables debugging output in the code.  This will likely be
       removed in future versions as the code becomes more stable.

API REFERENCE

       Tree::MultiNode

       The tree object.

       Tree::MultiNode::new

         @param    package name or tree object [scalar]
         @returns  new tree object

       Creates a new Tree.  The tree will have a single top level node when created.  The first
       node will have no value (undef) in either it's key or it's value.

         my $tree = new Tree::MultiNode;

       Tree::MultiNode::Node

       Please note that the Node object is used internaly by the MultiNode object.  Though you
       have the ability to interact with the nodes, it is unlikely that you should need to.  That
       being said, the interface is documented here anyway.

       Tree::MultiNode::Node::new

         new($)
           @param    package name or node object to clone [scalar]
           @returns  new node object

         new($$)
           @param    key   [scalar]
           @param    value [scalar]
           @returns  new node object

       Creates a new Node.  There are three behaviors for new.  A constructor with no arguments
       creates a new, empty node.  A single argument of another node object will create a clone
       of the node object.  If two arguments are passed, the first is stored as the key, and the
       second is stored as the value.

         # clone an existing node
         my $node = new Tree::MultiNode::Node($oldNode);
         # or
         my $node = $oldNode->new();

         # create a new node
         my $node = new Tree::MultiNode::Node;
         my $node = new Tree::MultiNode::Node("fname");
         my $node = new Tree::MultiNode::Node("fname","Larry");

       Tree::MultiNode::Node::key

         @param     key [scalar]
         @returns   the key [scalar]

       Used to set, or retreive the key for a node.  If a parameter is passed, it sets the key
       for the node.  The value of the key member is alwyays returned.

         print $node3->key(), "\n";    # 'fname'

       Tree::MultiNode::Node::value

         @param    the value to set [scalar]
         @returns  the value [scalar]

       Used to set, or retreive the value for a node.  If a parameter is passed, it sets the
       value for the node.  The value of the value member is alwyays returned.

         print $node3->value(), "\n";   # 'Larry'

       Tree::MultiNode::Node::clear_key

         @returns  the deleted key

       Clears the key member bu deleting it.

         $node3->clear_key();

       Tree::MultiNode::Node::clear_value

         @returns  the deleted value

       Clears the value member bu deleting it.

         $node3->clear_value();

       Tree::MultiNode::Node::children

         @returns  reference to children [array reference]

       Returns a refrence to the array that contains the children of the node object.

         $array_ref = $node3->children();

       Tree::MultiNode::Node::child_keys Tree::MultiNode::Node::child_values
       Tree::MultiNode::Node::child_kv_pairs

       These functions return arrays consisting of the appropriate data from the child nodes.

         my @keys     = $handle->child_keys();
         my @vals     = $handle->child_values();
         my %kv_pairs = $handle->child_kv_pairs();

       Tree::MultiNode::Node::child_key_positions

       This function returns a hashtable that consists of the child keys as the hash keys, and
       the position in the child array as the value.  This allows for a quick and dirty way of
       looking up the position of a given key in the child list.

         my %h = $node->child_key_positions();

       Tree::MultiNode::Node::parent

       Returns a refrence to the parent node of the current node.

         $node_parent = $node3->parent();

       Tree::MultiNode::Node::dump

       Used for diagnostics, it prints out the members of the node.

         $node3->dump();

       Tree::MultiNode::Handle

       Handle is used as a 'pointer' into the tree.  It has a few attributes that it keeps track
       of.  These are:

         1. the top of the tree
         2. the current node
         3. the current child node
         4. the depth of the current node

       The top of the tree never changes, and you can reset the handle to point back at the top
       of the tree by calling the top() method.

       The current node is where the handle is 'pointing' in the tree.  The current node is
       changed with functions like top(), down(), and up().

       The current child node is used for traversing downward into the tree.  The members
       first(), next(), prev(), last(), and position() can be used to set the current child, and
       then traverse down into it.

       The depth of the current node is a measure of the length of the path from the top of the
       tree to the current node, i.e. the top of the node has a depth of 0, each of its children
       has a depth of 1, etc.

       Tree::MultiNode::Handle::New

       Constructs a new handle.  You must pass a tree object to Handle::New.

         my $tree   = new Tree::MultiNode;
         my $handle = new Tree::MultiNode::Handle($tree);

       Tree::MultiNode::Handle::tree

       Returns the tree that was used to construct the node.  Useful if you're trying to create
       another node into the tree.

         my $handle2 = new Tree::MultiNode::Handle($handle->tree());

       Tree::MultiNode::Handle::get_data

       Retrieves both the key, and value (as an array) for the current node.

         my ($key,$val) = $handle->get_data();

       Tree::MultiNode::Handle::get_key

       Retrieves the key for the current node.

         $key = $handle->get_key();

       Tree::MultiNode::Handle::set_key

       Sets the key for the current node.

         $handle->set_key("lname");

       Tree::MultiNode::Handle::get_value

       Retreives the value for the current node.

         $val = $handle->get_value();

       Tree::MultiNode::Handle::set_value

       Sets the value for the current node.

         $handle->set_value("Wall");

       Tree::MultiNode::Handle::get_child

       get_child takes an optional paramater which is the position of the child that is to be
       retreived.  If this position is not specified, get_child attempts to return the current
       child.  get_child returns a Node object.

         my $child_node = $handle->get_child();

       Tree::MultiNode::Handle::add_child

       This member adds a new child node to the end of the array of children for the current
       node.  There are three optional parameters:

         - a key
         - a vlaue
         - a position

       If passed, the key and value will be set in the new child.  If a position is passed, the
       new child will be inserted into the current array of children at the position specified.

         $handle->add_child();                    # adds a blank child
         $handle->add_child("language","perl");   # adds a child to the end
         $handle->add_child("language","C++",0);  # adds a child to the front

       Tree::MultiNode::Handle::depth

       Gets the depth for the current node.

         my $depth = $handle->depth();

       Tree::MultiNode::Handle::select

       Sets the current child via a specified value -- basicly it iterates through the array of
       children, looking for a match.  You have to supply the key to look for, and optionaly a
       sub ref to find it.  The default for this sub is

         sub { return shift eq shift; }

       Which is sufficient for testing the equality of strings (the most common thing that I
       think will get stored in the tree).  If you're storing multiple datatypes as keys, you'll
       have to write a sub that figures out how to perform the comparisions in a sane manner.

       The sub ref should take 2 args, and compare them -- return false if they don't match, and
       true if they do.

         $handle->select('lname', sub { return shift eq shift; } );

       Tree::MultiNode::Handle::position

       Sets, or retreives the current child position.

         print "curr child pos is: ", $handle->position(), "\n";
         $handle->position(5);    # sets the 6th child as the current child

       Tree::MultiNode::Handle::first Tree::MultiNode::Handle::next Tree::MultiNode::Handle::prev
       Tree::MultiNode::Handle::last

       These functions manipulate the current child member.  first() sets the first child as the
       current child, while last() sets the last.  next(), and prev() will move to the next/prev
       child respectivly.  If there is no current child node, next() will have the same effect as
       first(), and prev() will operate as last().  prev() fails if the current child is the
       first child, and next() fails if the current child is the last child -- i.e. they do not
       wrap around.

       These functions will fail if there are no children for the current node.

         $handle->first();  # sets to the 0th child
         $handle->next();   # to the 1st child
         $handle->prev();   # back to the 0th child
         $handle->last();   # go straight to the last child.

       Tree::MultiNode::Handle::down

       down() moves the handle to point at the current child node.  It fails if there is no
       current child node.  When down() is called, the current child becomes invalid (undef).

         $handle->down();

       Tree::MultiNode::Handle::up

       down() moves the handle to point at the parent of the current node.  It fails if there is
       no parent node.  When up() is called, the current child becomes invalid (undef).

         $handle->up();

       Tree::MultiNode::Handle::top

       Resets the handle to point back at the top of the tree.  When top() is called, the current
       child becomes invalid (undef).

         $handle->top();

       Tree::MultiNode::Handle::children

       This returns an array of Node objects that represents the children of the current Node.
       Unlike Node::children(), the array Handle::children() is not a refrnece to an array, but
       an array.  Useful if you need to iterate through the children of the current node.

         print "There are: ", scalar($handle->children()), " children\n";
         foreach $child ($handle->children()) {
           print $child->key(), " : ", $child->value(), "\n";
         }

       Tree::MultiNode::Handle::child_key_positions

       This function returns a hashtable that consists of the child keys as the hash keys, and
       the position in the child array as the value.  This allows for a quick and dirty way of
       looking up the position of a given key in the child list.

         my %h = $handle->child_key_positions();

       Tree::MultiNode::Handle::get_child_key

       Returns the key at the specified position, or from the corresponding child node.

         my $key = $handle->get_child_key();

       Tree::MultiNode::Handle::get_child_value

       Returns the value at the specified position, or from the corresponding child node.

         my $value = $handle->get_child_value();

       Tree::MultiNode::Handle::remove_child

       Returns Tree::MultiNode::Node::child_kv_paris() for the current node for this handle.

         my %pairs = $handle->kv_pairs();

       Tree::MultiNode::Handle::remove_child

       Tree::MultiNode::Handle::child_keys

       Returns the keys from the current node's children.  Returns undef if there is no currnet
       node.

       Tree::MultiNode::Handle::traverse

         $handle->traverse(sub {
           my $h = shift;
           printf "%sk: %s v: %s\n",('  ' x $handle->depth()),$h->get_data();
         });

       Traverse takes a subroutine reference, and will visit each node of the tree, starting with
       the node the handle currently points to, recrusivly down from the current position of the
       handle.  Each time the subroutine is called, it will be passed a handle which points to
       the node to be visited.  Any additional arguments after the sub ref will be passed to the
       traverse function _before_ the handle is passed.  This should allow you to pass constant
       arguments to the sub ref.

       Modifying the node that the handle points to will cause traverse to work from the new node
       forward.

       Tree::MultiNode::Handle::traverse or to have the subref to be a method on an object (and
       still pass the object's 'self' to the method).

         $handle->traverse( \&Some::Object::method, $obj, $const1, \%const2 );

         ...
         sub method
         {
           my $handle = pop;
           my $self   = shift;
           my $const1 = shift;
           my $const2 = shift;
           # do something
         }

SEE ALSO

       Algorithms in C++
          Robert Sedgwick
          Addison Wesley 1992
          ISBN 0201510596

       The Art of Computer Programming  Volume 1 Fundamental Algorithms
         third edition, Donald E. Knuth

AUTHORS

       Kyle R. Burton mortis@voicenet.com (initial version, and maintenence) Daniel X. Pape
       dpape@canis.uiuc.edu (see Changes file from the source archive), Eric Joanis
       <joanis@cs.toronto.edu>

BUGS

       - There is currently no way to remove a child node.