NAME

Tree::Nary - Perl implementation of N-ary search trees.

SYNOPSIS

use Tree::Nary;

$node = new Tree::Nary;
$another_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->tsort($node);

$normalized_node = $node->normalize($node);

$bool = $node->is_identical($node, $another_node);
$bool = $node->has_same_struct($node, $another_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.

tsort( NODE )

Sorts all the children references of NODE according to the data field.

normalize( NODE )

Returns the normalized shape of NODE.

is_identical( NODE, ANOTHER_NODE )

Returns TRUE if NODE and ANOTHER_NODE have same structures and contents.

has_same_struct( NODE, ANOTHER_NODE )

Returns TRUE if the structure of NODE and ANOTHER_NODE are identical.

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 suite bundled with Tree::Nary.

AUTHOR

Frederic Soriano, <fsoriano@cpan.org>

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.

cpanm Tree::Nary

perl -MCPAN -e shell
install Tree::Nary