This is Info file pm.info, produced by Makeinfo version 1.68 from the input file bigpm.texi.  File: pm.info, Node: Tree/Fat, Next: Tree/MultiNode, Prev: Tree/DAG_Node, Up: Module List Perl Extension to Implement Fat-Node Trees ****************************************** NAME ==== Tree::Fat - Perl Extension to Implement Fat-Node Trees SYNOPSIS ======== This is not a plug-and-play perl extension. This module is designed for embedding (and there is no default embedding). 1. tvgen.pl -p PREFIX 2. Edit PREFIXtv.tmpl 3. Compile and link into your own application! DESCRIPTION =========== Implements object-oriented trees using algorithms adapted from b-trees and AVL trees (without resorting to yucky C++). Fat-node trees are not the best for many niche applications but they do have excellent all-terrain performance. TYPE Speed Flexibility Scales Memory Keeps-Order ---------- ----------- ------------ ---------- -------- ------------ Arrays fastest so-so not good MIN yes Hashes fast good so-so so-so no Fat-Trees medium silly big good yes WHAT IS A FAT-TREE? =================== It's a cross between a tree and an array. Each tree node contains a fixed length array of slots. Tree performance is enhanced by balancing array operations with tree operations. Moreover, tree operations are better optimized by taking the arrays into account. HOW ABOUT PERSISTANCE? ====================== F-Trees are designed for embedding. (If you want *persistent* F-Trees without the work, then check out the `ObjStore' extension by the same author. F-Trees are already integrated into the ObjectStore database, right now!) CURSOR BEHAVIOR =============== The only way to access a tree is via a cursor. Cursors behavior is derived from the principle of least-surprise (rather than greatest efficiency). More documentation there isn't. Please read the source code for more information. * Both cursors and trees store a version number. If you modify the same tree with more than one cursor, you can get mismatched versions. If there is a mismatch, an exception is thrown. * If you allow duplicate keys, seek always returns the first key that matches. For example, the cursor will always match at the first instance of 'c': (a,b,*c,c,c,d,e). EMBEDDING API ============= Flexibility is paramount. The embedding API is much more flexible than would be possible with C++ templates. See `tvcommon.*' & `tv.*'. PERFORMANCE =========== * Average Fill The number elements in the collection divided by the number of available slots. Higher is better. (Perl built-in hashes max out around 50-60%. Hash tables generally max out at around 70%.) * Average Depth The average number of nodes to be inspected during a search. Lower is better. * Average Centering Each fat-node is essentially an array of elements. This array is allocated contiguously from the available slots. The best arrangement (for insertions & deletions) is if the block of filled slots is centered. REFERENCES ========== * http://paris.lcs.mit.edu/~bvelez/std-colls/cacm/cacm-2455.html Author: Foster, C. C. A generalization of AVL trees is proposed in which imbalances up to (triangle shape) is a small integer. An experiment is performed to compare these trees with standard AVL trees and with balanced trees on the basis of mean retrieval time, of amount of restructuring expected, and on the worst case of retrieval time. It is shown that, by permitting imbalances of up to five units, the retrieval time is increased a small amount while the amount of restructuring required is decreased by a factor of ten. A few theoretical results are derived, including the correction of an earlier paper, and are duly compared with the experimental data. Reasonably good correspondence is found. CACM August, 1973 * http://www.imada.ou.dk/~kslarsen/Papers/AVL.html AVL Trees with Relaxed Balance Kim S. Larsen Proceedings of the 8th International Parallel Processing Symposium, pp. 888-893, IEEE Computer Society Press, 1994. AVL trees with relaxed balance were introduced with the aim of improving runtime performance by allowing a greater degree of concurrency. This is obtained by uncoupling updating from rebalancing. An additional benefit is that rebalancing can be controlled separately. In particular, it can be postponed completely or partially until after peak working hours. We define a new collection of rebalancing operations which allows for a significantly greater degree of concurrency than the original proposal. Additionally, in contrast to the original proposal, we prove the complexity of our algorithm. If N is the maximum size the tree could ever have, we prove that each insertion gives rise to at most floor(log_phi(N + 3/2) + log_phi(sqrt(5)) - 3) rebalancing operations and that each deletion gives rise to at most floor(log_phi(N + 3/2) + log_phi(sqrt(5)) - 4) rebalancing operations, where phi is the golden ratio. PUBLIC SOURCE CODE ================== The source code is being released in a malleable form to encourage as much testing as possible. Bugs in fundemental collections are simply UNACCEPTABLE and it is hard to trust a single vendor to debug their code properly. Get it via http://www.perl.com/CPAN/authors/id/JPRIT/ ! TODO ==== Optimize more! Clean up refcnts in test scripts. More documentation. AUTHOR ====== Copyright © 1997-1999 Joshua Nathaniel Pritikin. All rights reserved. This package is free software and is provided "as is" without express or implied warranty. It may be used, redistributed and/or modified under the terms of the Perl Artistic License (see http://www.perl.com/perl/misc/Artistic.html)  File: pm.info, Node: Tree/MultiNode, Next: Tree/Nary, Prev: Tree/Fat, Up: Module List a multi node tree object. Most useful for modeling heirarchial data structures. ********************************************************************************* 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 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 -------------------- 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 -------------------------- 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::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. The handle passed to the subroutine is a copy of the handle that is used to traverse the tree, so it's ok to change which node it points to. 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, 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 BUGS ==== - There is currently no way to remove a child node.  File: pm.info, Node: Tree/Nary, Next: Tree/RedBlack, Prev: Tree/MultiNode, Up: Module List Perl implementation of N-ary search trees. ****************************************** NAME ==== Tree::Nary - Perl implementation of N-ary search trees. SYNOPSIS ======== use Tree::Nary; $node = new Tree::Nary; $inserted_node = $node->insert($parent, $position, $node); $inserted_node = $node->insert_before($parent, $sibling, $node); $inserted_node = $node->append($parent, $node); $inserted_node = $node->prepend($parent, $node); $inserted_node = $node->insert_data($parent, $position, $data); $inserted_node = $node->insert_data_before($parent, $sibling, $data); $inserted_node = $node->append_data($parent, $data); $inserted_node = $node->prepend_data($parent, $data); $node->reverse_children($node); $node->traverse($node, $order, $flags, $maxdepth, $funcref, $argref); $node->children_foreach($node, $flags, $funcref, $argref); $root_node = $obj->get_root($node); $found_node = $node->find($node, $order, $flags, $data); $found_child_node = $node->find_child($node, $flags, $data); $index = $node->child_index($node, $data); $position = $node->child_position($node, $child); $first_child_node = $node->first_child($node); $last_child_node = $node->last_child($node); $nth_child_node = $node->nth_child($node, $index); $first_sibling = $node->first_sibling($node); $next_sibling = $node->next_sibling($node); $prev_sibling = $node->prev_sibling($node); $last_sibling = $node->last_sibling($node); $bool = $node->is_leaf($node); $bool = $node->is_root($node); $cnt = $node->depth($node); $cnt = $node->n_nodes($node); $cnt = $node->n_children($node); $bool = $node->is_ancestor($node); $cnt = $obj->max_height($node); $node->unlink($node); DESCRIPTION =========== The *Tree::Nary* class implements N-ary trees (trees of data with any number of branches), providing the organizational structure for a tree (collection) of any number of nodes, but knowing nothing about the specific type of node used. It can be used to display hierarchical database entries in an internal application (the NIS netgroup file is an example of such a database). It offers the capability to select nodes on the tree, and attachment points for nodes on the tree. Each attachment point can support multiple child nodes. The data field contains the actual data of the node. The next and previous fields point to the node's siblings (a sibling is another node with the same parent). The parent field points to the parent of the node, or is undef if the node is the root of the tree. The children field points to the first child of the node. The other children are accessed by using the next pointer of each child. This module is a translation (albeit not a direct one) from the C implementation of N-ary trees, available in the *GLIB distribution* (see SEE ALSO). GLOBAL VARIABLES ================ BOOLEANS -------- TRUE FALSE TRAVERSE FLAGS -------------- Specifies which nodes are visited during several of the tree functions, including traverse() and find(). TRAVERSE_LEAFS Specifies that only leaf nodes should be visited. TRAVERSE_NON_LEAFS Specifies that only non-leaf nodes should be visited. TRAVERSE_ALL Specifies that all nodes should be visited. TRAVERSE_MASK Combination of multiple traverse flags. ORDER FLAGS ----------- Specifies the type of traversal performed by traverse() and find(). PRE_ORDER Visits a node, then its children. IN_ORDER Visits a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function. POST_ORDER Visits the node's children, then the node itself. LEVEL_ORDER Calls the function for each child of the node, then recursively visits each child. METHODS ======= new( [DATA] ) ------------- Creates a new Tree::Nary object. Used to create the first node in a tree. Insert optional DATA into new created node. insert( PARENT, POSITION, NODE ) -------------------------------- Inserts a NODE beneath the PARENT at the given POSITION, returning inserted NODE. If POSITION is -1, NODE is inserted as the last child of PARENT. insert_before( PARENT, SIBLING, NODE ) -------------------------------------- Inserts a NODE beneath the PARENT before the given SIBLING, returning inserted NODE. If SIBLING is undef, the NODE is inserted as the last child of PARENT. append( PARENT, NODE ) ---------------------- Inserts a NODE as the last child of the given PARENT, returning inserted NODE. prepend( PARENT, NODE ) ----------------------- Inserts a NODE as the first child of the given PARENT, returning inserted NODE. insert_data( PARENT, POSITION, DATA ) ------------------------------------- Inserts a new node containing DATA, beneath the PARENT at the given POSITION. Returns the new inserted node. insert_data_before( PARENT, SIBLING, DATA ) ------------------------------------------- Inserts a new node containing DATA, beneath the PARENT, before the given SIBLING. Returns the new inserted node. append_data( PARENT, DATA ) --------------------------- Inserts a new node containing DATA as the last child of the given PARENT. Returns the new inserted node. prepend_data( PARENT, DATA ) ---------------------------- Inserts a new node containing DATA as the first child of the given PARENT. Returns the new inserted node. reverse_children( NODE ) ------------------------ Reverses the order of the children of NODE. It doesn't change the order of the grandchildren. traverse( NODE, ORDER, FLAGS, MAXDEPTH, FUNCTION, DATA ) -------------------------------------------------------- Traverses a tree starting at the given root NODE. It calls the given FUNCTION (with optional user DATA to pass to the FUNCTION) for each node visited. The traversal can be halted at any point by returning TRUE from FUNCTION. The ORDER in which nodes are visited is one of IN_ORDER, PRE_ORDER, POST_ORDER and LEVEL_ORDER. FLAGS specifies which types of children are to be visited, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS. MAXDEPTH is the maximum depth of the traversal. Nodes below this depth will not be visited. If MAXDEPTH is -1, all nodes in the tree are visited. If MAXDEPTH is 1, only the root is visited. If MAXDEPTH is 2, the root and its children are visited. And so on. children_foreach( NODE, FLAGS, FUNCTION, DATA ) ----------------------------------------------- Calls a FUNCTION (with optional user DATA to pass to the FUNCTION) for each of the children of a NODE. Note that it doesn't descend beneath the child nodes. FLAGS specifies which types of children are to be visited, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS. get_root( NODE ) ---------------- Gets the root node of a tree, starting from NODE. find( NODE, ORDER, FLAGS, DATA ) -------------------------------- Finds a NODE in a tree with the given DATA. The ORDER in which nodes are visited is one of IN_ORDER, PRE_ORDER, POST_ORDER and LEVEL_ORDER. FLAGS specifies which types of children are to be searched, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS. Returns the found node, or undef if the DATA is not found. find_child( NODE, FLAGS, DATA ) ------------------------------- Finds the first child of a NODE with the given DATA. FLAGS specifies which types of children are to be searched, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS. Returns the found child node, or undef if the DATA is not found. child_index( NODE, DATA ) ------------------------- Gets the position of the first child of a NODE which contains the given DATA. Returns the index of the child of node which contains data, or -1 if DATA is not found. child_position( NODE, CHILD ) ----------------------------- Gets the position of a NODE with respect to its siblings. CHILD must be a child of NODE. The first child is numbered 0, the second 1, and so on. Returns the position of CHILD with respect to its siblings. first_child( NODE ) ------------------- Returns the first child of a NODE. Returns undef if NODE is undef or has no children. last_child( NODE ) ------------------ Returns the last child of a NODE. Returns undef if NODE is undef or has no children. nth_child( NODE, INDEX ) ------------------------ Gets a child of a NODE, using the given INDEX. The first child is at INDEX 0. If the INDEX is too big, undef is returned. Returns the child of NODE at INDEX. first_sibling( NODE ) --------------------- Returns the first sibling of a NODE. This could possibly be the NODE itself. prev_sibling( NODE ) -------------------- Returns the previous sibling of a NODE. next_sibling( NODE ) -------------------- Returns the next sibling of a NODE. last_sibling( NODE ) -------------------- Returns the last sibling of a NODE. This could possibly be the NODE itself. is_leaf( NODE ) --------------- Returns TRUE if NODE is a leaf node (no children). is_root( NODE ) --------------- Returns TRUE if NODE is a root node (no parent nor siblings). depth( NODE ) ------------- Returns the depth of NODE. If NODE is undef, the depth is 0. The root node has a depth of 1. For the children of the root node, the depth is 2. And so on. n_nodes( NODE, FLAGS ) ---------------------- Returns the number of nodes in a tree. FLAGS specifies which types of children are to be counted, one of TRAVERSE_ALL, TRAVERSE_LEAFS and TRAVERSE_NON_LEAFS. n_children( NODE ) ------------------ Returns the number of children of NODE. is_ancestor( NODE, DESCENDANT ) ------------------------------- Returns TRUE if NODE is an ancestor of DESCENDANT. This is true if NODE is the parent of DESCENDANT, or if NODE is the grandparent of DESCENDANT, etc. max_height( NODE ) ------------------ Returns the maximum height of all branches beneath NODE. This is the maximum distance from NODE to all leaf nodes. If NODE is undef, 0 is returned. If NODE has no children, 1 is returned. If NODE has children, 2 is returned. And so on. unlink( NODE ) -------------- Unlinks NODE from a tree, resulting in two separate trees. The NODE to unlink becomes the root of a new tree. EXAMPLES ======== An example for each function can be found in the test script test.pl. AUTHOR ====== Frederic Soriano, COPYRIGHT ========= This package is free software and is provided "as is" without express or implied warranty. It may be used, redistributed and/or modified under the same terms as Perl itself. SEE ALSO ======== API from the GLIB project, http://developer.gnome.org/doc/API/glib/glib-n-ary-trees.html.  File: pm.info, Node: Tree/RedBlack, Next: Tree/RedBlack/Node, Prev: Tree/Nary, Up: Module List Perl implementation of Red/Black tree, a type of balanced tree. *************************************************************** NAME ==== Tree::RedBlack - Perl implementation of Red/Black tree, a type of balanced tree. SYNOPSIS ======== use Tree::RedBlack; my $t = new Tree::RedBlack; $t->insert(3, 'cat'); $t->insert(4, 'dog'); my $v = $t->find(4); my $min = $t->min; my $max = $t->max; $t->delete(3); $t->print; DESCRIPTION =========== This is a perl implementation of the Red/Black tree algorithm found in the book "Algorithms", by Cormen, Leiserson & Rivest (more commonly known as "CLR" or "The White Book"). A Red/Black tree is a binary tree which remains "balanced"- that is, the longest length from root to a node is at most one more than the shortest such length. It is fairly efficient; no operation takes more than O(lg(n)) time. A Tree::RedBlack object supports the following methods: new () Creates a new RedBlack tree object. root () Returns the root node of the tree. Note that this will either be undef if no nodes have been added to the tree, or a Tree::RedBlack::Node object. See the *Note Tree/RedBlack/Node: Tree/RedBlack/Node, manual page for details on the Node object. cmp (&) Use this method to set a comparator subroutine. The tree defaults to lexical comparisons. This subroutine should be just like a comparator subroutine to sort, except that it doesn't do the $a, $b trick; the two elements to compare will just be the first two items on the stack. insert ($;$) Adds a new node to the tree. The first argument is the key of the node, the second is its value. If a node with that key already exists, its value is replaced with the given value and the old value is returned. Otherwise, undef is returned. delete ($) The argument should be either a node object to delete or the key of a node object to delete. WARNING!!! THIS STILL HAS BUGS!!! find ($) Searches the tree to find the node with the given key. Returns the value of that node, or undef if a node with that key isn't found. Note, in particular, that you can't tell the difference between finding a node with value undef and not finding a node at all. If you want to determine if a node with a given key exists, use the node method, below. node ($) Searches the tree to find the node with the given key. Returns that node object if it is found, undef otherwise. The node object is a Tree::RedBlack::Node object. min () Returns the node with the minimal key. max () Returns the node with the maximal key. AUTHOR ====== Benjamin Holzman SEE ALSO ======== Tree::RedBlack::Node  File: pm.info, Node: Tree/RedBlack/Node, Next: Tree/Ternary, Prev: Tree/RedBlack, Up: Module List Node class for Perl implementation of Red/Black tree **************************************************** NAME ==== Tree::RedBlack::Node - Node class for Perl implementation of Red/Black tree SYNOPSIS ======== use Tree::RedBlack; my $t = new Tree::RedBlack; $t->insert(3, 'dog'); my $node = $t->node(3); $animal = $node->val; DESCRIPTION =========== A Tree::RedBlack::Node object supports the following methods: key () Key of the node. This is what the nodes are sorted by in the tree. val ($) Value of the node. Can be any perl scalar, so it could be a hash-ref, f'rinstance. This can be set directly. color () Color of the node. 1 for "red", 0 or undef for "black". parent () Parent node of this one. Returns undef for root node. left () Left child node of this one. Returns undef for leaf nodes. right () Right child node of this one. Returns undef for leaf nodes. min () Returns the node with the minimal key starting from this node. max () Returns the node with the maximal key starting from this node. successor () Returns the node with the smallest key larger than this node's key, or this node if it is the node with the maximal key. predecessor () Similar to successor. WARNING: NOT YET IMPLEMENTED!! You can use these methods to write utility routines for actions on red/black trees. For instance, here's a routine which writes a tree out to disk, putting the byte offsets of the left and right child records in the record for each node. sub dump { my($node, $fh) = @_; my($left, $right); my $pos = tell $fh; print $fh $node->color ? 'R' : 'B'; seek($fh, 8, 1); print $fh $node->val; if ($node->left) { $left = dump($node->left,$fh); } if ($node->right) { $right = dump($node->right,$fh); } my $end = tell $fh; seek($fh, $pos+1, 0); print $fh pack('NN', $left, $right); seek($fh, $end, 0); $pos; } You would call it like this: my $t = new Tree::RedBlack; ... open(FILE, ">tree.dump"); dump($t->root,\*FILE); close FILE; As another example, here's a simple routine to print a human-readable dump of the tree: sub pretty_print { my($node, $fh, $lvl) = @_; if ($node->right) { pretty_print($node->right, $fh, $lvl+1); } print $fh ' 'x($lvl*3),'[', $node->color ? 'R' : 'B', ']', $node->key, "\n"; if ($node->left) { pretty_print($this->left, $fh, $lvl+1); } } A cleaner way of doing this kind of thing is probably to allow sub-classing of Tree::RedBlack::Node, and then allow the Tree::RedBlack constructor to take an argument saying what class of node it should be made up out of. Hmmm... AUTHOR ====== Benjamin Holzman SEE ALSO ======== Tree::RedBlack  File: pm.info, Node: Tree/Ternary, Next: Tree/Ternary_XS, Prev: Tree/RedBlack/Node, Up: Module List Perl implementation of ternary search trees. ******************************************** NAME ==== Tree::Ternary - Perl implementation of ternary search trees. SYNOPSIS ======== use Tree::Ternary; $obj = new Tree::Ternary; $ref = $obj->insert($str); $ref = $obj->rinsert($str); $ref = $obj->search($str); $ref = $obj->rsearch($str); $cnt = $obj->nodes(); $cnt = $obj->terminals(); $cnt = $obj->pmsearch($char, $str); @list = $obj->pmsearch($char, $str); $cnt = $obj->nearsearch($dist, $str); @list = $obj->nearsearch($dist, $str); @list = $obj->traverse(); DESCRIPTION =========== Tree::Ternary is a Perl implementation of ternary search trees as described by Jon Bentley and Robert Sedgewick. Ternary search trees are interesting data structures that provide a means of storing and accessing strings. They combine the time efficiency of digital tries with the space efficiency of binary search trees. Unlike a hash, they also maintain information about relative order. This module is a translation (albeit not a direct one) from the C implementation published in Bentley and Sedgewick's article in the April 1998 issue of Dr. Dobb's Journal (see SEE ALSO). METHODS ======= new() ----- Creates a new Tree::Ternary object. insert( STRING ) ---------------- Inserts STRING into the tree. When a string is inserted, a scalar variable is created to hold whatever data you may wish to associate with the string. A reference to this scalar is returned on a successful insert. If the string is already in the tree, undef is returned. rinsert( STRING ) ----------------- This is a recursive implementation of the insert function. It behaves the same as insert(), except it is slower and will carp about deep recursion for strings near 100 characters in length. This is included for reference purposes only and may eventually deprecated as an alias for insert(). search( STRING ) ---------------- Searches for the presence of STRING in the tree. If the string is found, a reference to the associated scalar is returned, otherwise undef is returned. rsearch( STRING ) ----------------- A recursive implementation of search(), suffers the same drawbacks as rinsert(). This is included for reference purposes only and may eventually deprecated as an alias for search(). nodes() ------- Returns the total number of nodes in the tree. This count does not include terminal nodes. terminals() ----------- Returns the total number of terminal nodes in the tree. pmsearch( CHAR, STRING ) ------------------------ Performs a pattern match for STRING against the tree, using CHAR as a wildcard character. The wildcard will match any characters. For example, if '.' was specified as the wildcard, and STRING was the pattern ".a.a.a." would match "bananas" and "pajamas" (if they were both stored in the tree). In a scalar context, returns the count of matches found. In an array context, returns a list of the matched strings. nearsearch( DISTANCE, STRING ) ------------------------------ Searches for all strings in a tree that differ from STRING by DISTANCE or fewer characters. In a scalar context, returns the count of matches found. In an array context, returns a list of the matched strings. traverse() ---------- Simply returns a sorted list of the strings stored in the tree. This method will do more tricks in the future. NOTES ===== Character Set ------------- Tree::Ternary currently only has support for strings of 8-bit characters. Since it uses a 2 character string to represent termination of the input strings, it will handle any 8-bit character properly. In the future, I plan to expand the scope of its character handling, and even include Unicode support. Attributes ---------- Specifying the :attrib tag as an argument to the use statement will export the following internal constants for debugging purposes. Tree::Ternary was built using Greg Bacon's array-based object design, and these constants are used as attribute indices. SPLIT_CHAR LO_KID EQ_KID HI_KID PAYLOAD NODE_COUNT TERMINAL_COUNT AUTHOR ====== Mark Rogaski, wendigo@pobox.com CREDITS ======= Many thanks to Tom Phoenix for his invaluable advice and critique. COPYRIGHT ========= Copyright 1999, Mark Rogaski, wendigo@pobox.com, all rights reserved. This package is free software and is provided "as is" without express or implied warranty. It may be used, redistributed and/or modified under the same terms as Perl itself. SEE ALSO ======== Bentley, Jon and Sedgewick, Robert. "Ternary Search Trees". Dr. Dobbs Journal, April 1998. http://www.ddj.com/articles/1998/9804/9804a/9804a.htm Bentley, Jon and Sedgewick, Robert. "Fast Algorithms for Sorting and Searching Strings". Eighth Annual ACM-SIAM Symposium on Discrete Algorithms New Orleans, January, 1997. http://www.cs.princeton.edu/~rs/strings/  File: pm.info, Node: Tree/Ternary_XS, Next: Tree/Trie, Prev: Tree/Ternary, Up: Module List Perl extension implementing ternary search trees. ************************************************* NAME ==== Ternary_XS - Perl extension implementing ternary search trees. SYNOPSIS ======== use Tree::Ternary_XS; $obj = new Tree::Ternary_XS; $obj->insert($str); $obj->search($str); $obj->nodes(); $obj->terminals(); $cnt = $obj->pmsearch($char, $str); @list = $obj->pmsearch($char, $str); $cnt = $obj->nearsearch($dist, $str); @list = $obj->nearsearch($dist, $str); @list = $obj->traverse(); DESCRIPTION =========== Tree::Ternary_XS is a Perl interface to a C implementation of ternary search trees as described by Jon Bentley and Robert Sedgewick. Ternary search trees are interesting data structures that provide a means of storing and accessing strings. They combine the time efficiency of digital tries with the space efficiency of binary search trees. Unlike a hash, they also maintain information about relative order. This module is an adaptation from the C implementation published in Bentley and Sedgewick's article in the April 1998 issue of Dr. Dobb's Journal (see SEE ALSO). This module attempts to recreate the interface as much as possible of Mark Rogaski's Tree::Ternary, a pure Perl implementation. As Tree::Ternary_XS uses C code, it has important space and speed advantages over Tree::Ternary. METHODS ======= new() ----- Creates a new Tree::Ternary object. insert( STRING ) ---------------- Inserts STRING into the tree. When a string is inserted, a scalar variable is created to hold whatever data you may wish to associate with the string. A reference to this scalar is returned on a successful insert. If the string is already in the tree, undef is returned. search( STRING ) ---------------- Searches for the presence of STRING in the tree. If the string is found, a reference to the associated scalar is returned, otherwise undef is returned. nodes() ------- Returns the total number of nodes in the tree. This count does not include terminal nodes. terminals() ----------- Returns the total number of terminal nodes in the tree. pmsearch( CHAR, STRING ) ------------------------ Performs a pattern match for STRING against the tree, using CHAR as a wildcard character. The wildcard will match any characters. For example, if '.' was specified as the wildcard, and STRING was the pattern ".a.a.a." would match "bananas" and "pajamas" (if they were both stored in the tree). In a scalar context, returns the count of matches found. In an array context, returns a list of the matched strings. nearsearch( DISTANCE, STRING ) ------------------------------ Searches for all strings in a tree that differ from STRING by DISTANCE or fewer characters. In a scalar context, returns the count of matches found. In an array context, returns a list of the matched strings. traverse() ---------- Simply returns a sorted list of the strings stored in the tree. This method will do more tricks in the future. NOTES ===== Character Set ------------- Tree::Ternary_XS currently only has support for strings not containing the null character. Incompatibilities ----------------- There are a number of differences between Tree::Ternary and Tree::Ternary_XS: The rinsert() and rsearch() methods are not supported. Use insert() and search() instead. The insert and search methods do not return a reference to a scalar. This limits the possibilities of the module somewhat, but is expected to be rectified (with a different interface) in a later version. Performance ----------- Tree::Ternary_XS has been benchmarked at about 50 times faster than Tree::Ternary, with a great reduction in memory usage. AUTHOR ====== Leon Brocard, leon@astray.com CREDITS ======= Thanks to Mark Rogaski for the pure Perl interface. Most of the documentation and test scripts are simply copies from Tree::Ternary. COPYRIGHT ========= Copyright (c) 2000 Leon Brocard. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself. SEE ALSO ======== Bentley, Jon and Sedgewick, Robert. "Ternary Search Trees". Dr. Dobbs Journal, April 1998. http://www.ddj.com/articles/1998/9804/9804a/9804a.htm Bentley, Jon and Sedgewick, Robert. "Fast Algorithms for Sorting and Searching Strings". Eighth Annual ACM-SIAM Symposium on Discrete Algorithms New Orleans, January, 1997. http://www.cs.princeton.edu/~rs/strings/  File: pm.info, Node: Tree/Trie, Next: UDDI, Prev: Tree/Ternary_XS, Up: Module List An implementation of the Trie data structure in Perl **************************************************** NAME ==== Tree::Trie - An implementation of the Trie data structure in Perl SYNOPSIS ======== use Tree::Trie; use strict; my($trie) = new Tree::Trie; $trie->add(qw[aeode calliope clio erato euterpe melete melpomene mneme polymnia terpsichore thalia urania]); my(@all) = $trie->lookup(""); my(@ms) = $trie->lookup("m"); $" = "--"; print "All muses: @all\nMuses beginning with 'm': @ms\n"; my(@deleted) = $trie->remove(qw[calliope thalia doc]); print "Deleted muses: @deleted\n"; DESCRIPTION =========== This module implements a trie data structure. The term "trie" comes from the word re*trie*val, but is generally pronounced like "try". A trie is a tree structure (or directed acyclic graph), the nodes of which represent letters in a word. For example, the final lookup for the word 'bob' would look something like `$ref->{'b'}{'o'}{'b'}{HASH(0x80c6bbc)}' (the HASH being an end marker). Only nodes which would represent words in the trie exist, making the structure slightly smaller than a hash of the same data set. The advantages of the trie over other data storage methods is that lookup times are O(1) WRT the size of the index. For sparse data sets, it is probably not as efficient as performing a binary search on a sorted list, and for small files, it has a lot of overhead. The main advantage (at least from my perspective) is that it provides a relatively cheap method for finding a list of words in a large, dense data set which begin with a certain string. METHODS ======= new([\%options]) This is the constructor method for the class. You may optionally pass it a hash reference with a set of option => value pairs. Currently, the only option available is 'deepsearch' and its valid values are 'boolean', 'choose' or 'count'. The documentation on the 'lookup' method describes the effects of these different values. add(word0 [, word1...wordN]) This method attempts to add words 0 through N to the trie. Returns, in list context, the words successfully added to the trie. In scalar context, returns the number of words successfully added. As of this release, the only reason a word would fail to be added is if it is already in the trie. remove(word0 [, word1...wordN]) This method attempts to remove words 0 through N from the trie. Returns, in list context, the words successfully removed from the trie. In scalar context, returns the number of words successfully removed. As of this release, the only reason a word would fail to be removed is if it is not already in the trie. lookup(word0) This method performs lookups on the trie. In list context, it returns a complete list of words in the trie which begin with word0. In scalar context, the value returned depends on the setting of the 'deepsearch' option. You can set this option while creating your Trie object, or by using the deepsearch method. If deepsearch is set to 'boolean', it will return a true value if any word in the trie begins with word0. This setting is the fastest. If deepsearch is 'choose', it will return one word in the trie that begins with word0, or undef if nothing is found. If word0 exists in the trie exactly, it will be returned. Finally, if deepsearch is set to 'count', it will return a count of the words in the trie that begin with word0. This operation requires walking the entire tree, so can possibly be significantly slower than the other two options. For reasons of backwards compatibilty, 'choose' is the default value of this option. To get a list of all words in the trie, use `lookup("")' in list context. deepsearch([option]) If option os specified, sets the deepsearch parameter. Option may be one of: 'boolean', 'choose', 'count'. Please see the documentation for the lookup method for the details of what these options mean. Returns the current value of the deepsearch parameter. Future Work =========== * The ability to associate data with each word in a trie will be added, eventually. * There are a few methods of compression that allow you same some amount of space in the trie. I have to figure out which ones are worth implemeting. I may end up making the different compression methods configurable. I have now made one of them the default. * The ability to have Tree::Trie store its internal hash as a TIEd object of some sort. AUTHOR ====== Copyright 2000 Avi Finkel <`avi@finkel.org'> This package is free software and is provided "as is" without express or implied warranty. It may be used, redistributed and/or modified under the terms of the Perl Artistic License (see http://www.perl.com/perl/misc/Artistic.html)