table of contents
MultiNode(3pm) | User Contributed Perl Documentation | MultiNode(3pm) |
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.my $tree = new Tree::MultiNode; my $handle = new Tree::MultiNode::Handle($tree);
$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.
API REFERENCE¶
Tree::MultiNode The tree object.@param package name or tree object [scalar] @returns new tree objectCreates 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;
new($) @param package name or node object to clone [scalar] @returns new node object new($$) @param key [scalar] @param value [scalar] @returns new node objectCreates 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");
@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'
@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'
@returns the deleted keyClears the key member bu deleting it.
$node3->clear_key();
@returns the deleted valueClears the value member bu deleting it.
$node3->clear_value();
@returns reference to children [array reference]Returns a refrence to the array that contains the children of the node object.
$array_ref = $node3->children();
my @keys = $handle->child_keys(); my @vals = $handle->child_values(); my %kv_pairs = $handle->child_kv_pairs();
my %h = $node->child_key_positions();
$node_parent = $node3->parent();
$node3->dump();
1. the top of the tree 2. the current node 3. the current child node 4. the depth of the current 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. 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.
my $tree = new Tree::MultiNode; my $handle = new Tree::MultiNode::Handle($tree);
my $handle2 = new Tree::MultiNode::Handle($handle->tree());
my ($key,$val) = $handle->get_data();
$key = $handle->get_key();
$handle->set_key("lname");
$val = $handle->get_value();
$handle->set_value("Wall");
my $child_node = $handle->get_child();
- 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 front
my $depth = $handle->depth();
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; } );
print "curr child pos is: ", $handle->position(), "\n"; $handle->position(5); # sets the 6th child as the current child
$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.
$handle->down();
$handle->up();
$handle->top();
print "There are: ", scalar($handle->children()), " children\n"; foreach $child ($handle->children()) { print $child->key(), " : ", $child->value(), "\n"; }
my %h = $handle->child_key_positions();
my $key = $handle->get_child_key();
my $value = $handle->get_child_value();
my %pairs = $handle->kv_pairs();
$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.
$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.2003-05-27 | perl v5.10.0 |