/ 
Sort-Tree-1.09
River stage zero No dependents
/ Sort::Tree

NAME

Sort::Tree - Organize list of objects into parent/child order.

SYNOPSIS

use Sort::Tree;

my @tree = list_to_tree(\@my_list, 
                        $id_field, 
                        $parent_field);

my @sorted_list = tree_to_list(\@tree,
                               [$id_field],
                               [\&Sort::Tree::numerically],
                               $parent_field));

DESCRIPTION

Sort::Tree includes three routines, list_to_tree, tree_to_list and traverse. These are used to organize an unordered list of objects into a tree form. For example, you'd perform a database query to gain a list of folders in a document system, and then order them by parentage for display in a webpage.

EXAMPLE

use Sort::Tree;

my @creatures = (
             { id => 1, class => -1, name => 'animal' },
             { id => 2, class => 1,  name => 'mammal' },
             { id => 3, class => 1,  name => 'bird' },
             { id => 4, class => 1,  name => 'reptile' },
             { id => 5, class => 2,  name => 'primate' },
             { id => 6, class => 2,  name => 'feline' },
             { id => 7, class => 5,  name => 'human' },
             { id => 8, class => 6,  name => 'housecat' },
             { id => 9, class => 3,  name => 'penguin' },
             { id => 10,class => 4,  name => 'gecko' }
             );

my @tree = Sort::Tree::list_to_tree(\@creatures, 'id', 'class');

foreach my $row (Sort::Tree::tree_to_list(\@tree,
                                      ['id'],
                                      [\&Sort::Tree::numerically],
                                      'class')) {
    print ' ' x $row->{class}, $row->{name}, "\n";
}

The following is displayed:

animal mammal primate human feline housecat bird penguin reptile gecko

METHODS

list_to_tree($list, $idField, $parentField)

Takes a list of queried objects and builds a tree, resorting it into tree order and including the nesting level. Inspired by DBIx::Tree.

tree_to_list(tree, cmpFields, cmpFuncs, idField, depth, max_depth)

Takes a tree and serializes it into a sorted list. Recursive. Inspired by DBIx::Tree (but not derived from it)

Parameters:
  $tree - the tree data structure
  $cmpFields - Field to do comparison on (default idField)
  $cmpFuncs - Ordering function (default &numerically)
  $idField - 
  $depth - Depth to display (default 0)
  $max_depth - Maximum depth to display; -1 for all (default -1)

traverse(tree, %traverseArgs)

Performs a depth-first traversal of the tree, calling a specified callback method for each element.

Parameters:
  $tree - the tree data structure
  %traverseArgs - two or more key/value paired arguments ('method' and 'idField' required)

%traverseArgs is expected to contain valid 'method' (code ref) and 'idField' (string) keys. The 'method' should expect to be called with a list of arguments and have a signature like

sub mymethod {
	my %arguments = @_;
	# ...
}

$traverseArgs{'method'} will be called for each tree element encountered with the following key/value arguments:

'id'		string, id of current element
'item'		actual tree element currently being processed
'level'		integer, depth within tree
'parent_id'	string, id of parent element if available
'parent'	parent element of 'item'
%traverseArgs	args passed to traverse()

The values passed to $traverseArgs{'method'} will also contain the arguments passed in the %traverseArgs used in the call to traverse(), which is a handy way to pass information along to the processing method.

The method specified with the $traverseArgs{'method'} parameter should return a FALSE value to continue processing of the tree. Should the $traverseArgs{'method'} return something which evaluates to Perl 'true', traverse() will abort and immediately return THAT value to the caller.

EXAMPLES of traverse():

 {
  	# Modifying all elements in a tree, by traversing it
  	# ... 
 	my $tree = Sort::Tree::list_to_tree(...);
	
	Sort::Tree::traverse($tree, 
				   'method'	=> \&uppercaseTitles,
				   'idField'	=> 'myid'
				);
	
	# $tree now contains uppercase titles in each element.
	# ...
 }
 
 # uppercaseTitles assumes tree items contain a 'title' key.
 sub uppercaseTitles {
 	my %details = @_;
	
	print "Uppercasing title from item " . $details{'id'} . "\n";
	
	$details{'item'}->{'title'} = uc($details{'item'}->{'title'});
	
	return false; # continue processing tree
 }

The above example demonstrated a traversal which needed to interact with each element in the tree. In some instances, such as during as search, it is desirable to abort the operation at some point. This is accomplished by having the traverse method return a true value. Since this true value is returned to the original caller, it can be used to return a tree element or a portion thereof.

 {
  	# Search elements in tree, return first match
  	# ... 
 	my $tree = Sort::Tree::list_to_tree(...);
	
	my %traverseArgs = (
				'method'	=> \&findByOwner,
				'idField'	=> 'myid',
				'owner'		=> 'bob', # traversArgs are passed to callback method
		);
	
	my $bobsElement = Sort::Tree::traverse($tree, %traverseArgs) || die "can't find bob's stuff";
	
	# use the element
	
 }
 
 # findByOwner assumes tree elements have an 'owner' attribute
 sub findByOwner {
 	my %details = @_;
 
	if ($details{'item'}->{'owner'} eq $details{'owner'})
	{
		return $details{'item'};
	}
	
	return false; # continue processing tree
 }

PREREQUISITES

Nothing outside of the normal Perl core modules (Exporter & Carp).

BUGS

None reported.

VERSION

1.09 - Released on 2004/05/06.

SEE ALSO

perl(1)

AUTHOR

Bryce Harrington <brycehar@bryceharrington.com>

http://www.osdl.org/

CONTRIBUTIONS

Pat Deegan, http://www.psychogenic.com. 2004-05-06 Sort bugfix, traverse() method.

COPYRIGHT

Copyright (C) 2003 Bryce Harrington. All Rights Reserved.

This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

REVISION

Revision: $Revision: 1.3 $