Take me over?
NAME
MultiNode.pm -- a multi node tree object. Most useful for modeling heirarchial data structures.
SYNOPSIS
use Tree::MultiNode;
my $tree = new Tree::MultiNode;
my $handle = new Tree::MultiNode::Handle($tree);
$handle->set_key("top");
$handle->set_key("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);
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 childTo move back up, you can call the method up:
$handle->up(); # moves to this node's parentup() 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
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 MultiTree 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
Creates a new Node. There are two optional arguments. If passed, the first is stored as the key, and the second is stored as the value.
my $node1 = new Tree::MultiNode::Node;
my $node2 = new Tree::MultiNode::Node("fname");
my $node3 = new Tree::MultiNode::Node("fname","Larry");Tree::MultiNode::Node::key
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
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
Clears the key member bu deleting it.
$node3->clear_key();Tree::MultiNode::Node::clear_value
Clears the value member bu deleting it.
$node3->clear_value();Tree::MultiNode::Node::children
Returns a refrence to the array that contains the children of the node object.
$array_ref = $node3->children();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 nodeThe 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.
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::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 positionIf 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 frontTree::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 childTree::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";
}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
BUGS
- There is currently no way to remove a child node.
- Not all the methods are tested, this is one of the first releases and only very minimal testing has been done.