Tree::MultiNode
MultiNode(3) User Contributed Perl Documentation MultiNode(3)
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 multi-
ple 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 con-
struction).
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 chil-
dren.
To move the handle so it points at a child (so you can start manipu-
lating 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 posi-
tion 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 sup-
ply 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 com-
mon thing that I think will get stored in the tree). If you’re stor-
ing multiple datatypes as keys, you’ll have to write a sub that fig-
ures 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::chil-
dren() 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, recru-
sivly 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
}
=cut
sub otraverse {
my($self,$subref,@args) = @_;
confess "Error, invalid sub ref: $subref\n" unless ’CODE’ eq
ref($subref);
# operate on a cloned handle
return Tree::MultiNode::Handle->new($self)->_otraverseImpl($sub-
ref,@args); }
sub _otraverseImpl {
my($self,$obj,$method,@args) = @_;
$obj->$method( @args, $self );
for(my $i = 0; $i < scalar($self->children); ++$i ) {
$self->down($i);
$self->_otraverseImpl($obj,$method,@args);
$self->up();
}
return; }
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.
perl v5.8.8 2003-05-27 MultiNode(3)
