GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  SORT::TREE (3)

.ds Aq ’

NAME

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

CONTENTS

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

<B>Sort::TreeB> 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 "cant find bobs 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 $
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 SORT::TREE (3) 2004-05-06

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.