Tree::Nary extension module for Perl
------------------------------------

Author:		Frederic Soriano [FSORIANO]
		best reached at : fsoriano@cpan.org

Version:	1.3

Date:		January 2004

DSLI:		RdpO
		- stable release
		- support by developer
		- plain functions, no references used

Copyright:	Public domain

Documentation is in pod format at the end of Tree::Nary.pm.
Installation hints are in a file named INSTALL inside this package.
See also CHANGES for a history of updates to this module.

-----------------------------------------------------------------------------
  THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR
  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
-----------------------------------------------------------------------------

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->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.