oracular (3) Tree::RB.3pm.gz

Provided by: libtree-rb-perl_0.500006-3_all bug

NAME

       Tree::RB - Perl implementation of the Red/Black tree, a type of balanced binary search tree.

SYNOPSIS

           use Tree::RB;

           my $tree = Tree::RB->new;
           $tree->put('France'  => 'Paris');
           $tree->put('England' => 'London');
           $tree->put('Hungary' => 'Budapest');
           $tree->put('Ireland' => 'Dublin');
           $tree->put('Egypt'   => 'Cairo');
           $tree->put('Germany' => 'Berlin');

           $tree->put('Alaska' => 'Anchorage'); # D'oh! Alaska isn't a Country
           $tree->delete('Alaska');

           print scalar $tree->get('Ireland'); # 'Dublin'

           print $tree->size; # 6
           print $tree->min->key; # 'Egypt'
           print $tree->max->key; # 'Ireland'

           print $tree->nth(0)->key;  # 'Egypt'
           print $tree->nth(-1)->key; # 'Ireland'

           # print items, ordered by key
           my $it = $tree->iter;

           while(my $node = $it->next) {
               printf "key = %s, value = %s\n", $node->key, $node->val;
           }

           # print items in reverse order
           $it = $tree->rev_iter;

           while(my $node = $it->next) {
               printf "key = %s, value = %s\n", $node->key, $node->val;
           }

           # Hash interface
           tie my %capital, 'Tree::RB';

           # or do this to store items in descending order
           tie my %capital, 'Tree::RB', sub { $_[1] cmp $_[0] };

           $capital{'France'}  = 'Paris';
           $capital{'England'} = 'London';
           $capital{'Hungary'} = 'Budapest';
           $capital{'Ireland'} = 'Dublin';
           $capital{'Egypt'}   = 'Cairo';
           $capital{'Germany'} = 'Berlin';

           # print items in order
           while(my ($key, $val) = each %capital) {
               printf "key = $key, value = $val\n";
           }

DESCRIPTION

       This is a Perl implementation of the Red/Black tree, a type of balanced binary search tree.

       A tied hash interface is also provided to allow ordered hashes to be used.

       See the Wikipedia article at <http://en.wikipedia.org/wiki/Red-black_tree> for further information about
       Red/Black trees.

INTERFACE

   new([CODEREF])
       Creates and returns a new tree. If a reference to a subroutine is passed to new(), the subroutine will be
       used to override the tree's default lexical ordering and provide a user a defined ordering.

       This subroutine should be just like a comparator subroutine used with sort, except that it doesn't do the
       $a, $b trick.

       For example, to get a case insensitive ordering

           my $tree = Tree::RB->new(sub { lc $_[0] cmp lc $_[1]});
           $tree->put('Wall'  => 'Larry');
           $tree->put('Smith' => 'Agent');
           $tree->put('mouse' => 'micky');
           $tree->put('duck'  => 'donald');

           my $it = $tree->iter;

           while(my $node = $it->next) {
               printf "key = %s, value = %s\n", $node->key, $node->val;
           }

   resort(CODEREF)
       Changes the ordering of nodes within the tree. The new ordering is specified by a comparator subroutine
       which must be passed to resort().

       See "new" for further information about the comparator.

   size()
       Returns the number of nodes in the tree.

   root()
       Returns the root node of the tree. This will either be undef if no nodes have been added to the tree, or
       a Tree::RB::Node object.  See the Tree::RB::Node manual page for details on the Node object.

   min()
       Returns the node with the minimal key.

   max()
       Returns the node with the maximal key.

   nth(INDEX)
       Returns the node at the given (zero based) index, or undef if there is no node at that index. Negative
       indexes can be used, with -1 indicating the last node, -2 the penultimate node and so on.

   lookup(KEY, [MODE])
       When called in scalar context, lookup(KEY) returns the value associated with KEY.

       When called in list context, lookup(KEY) returns a list whose first element is the value associated with
       KEY, and whose second element is the node containing the key/value.

       An optional MODE parameter can be passed to lookup() to influence which key is returned.

       The values of MODE are constants that are exported on demand by Tree::RB

           use Tree::RB qw[LUEQUAL LUGTEQ LULTEQ LUGREAT LULESS LUNEXT LUPREV];

       LUEQUAL
           This is the default mode. Returns the node exactly matching the key, or "undef" if not found.

       LUGTEQ
           Returns the node exactly matching the specified key, if this is not found then the next node that is
           greater than the specified key is returned.

       LULTEQ
           Returns the node exactly matching the specified key, if this is not found then the next node that is
           less than the specified key is returned.

       LUGREAT
           Returns the node that is just greater than the specified key - not equal to.  This mode is similar to
           LUNEXT except that the specified key need not exist in the tree.

       LULESS
           Returns the node that is just less than the specified key - not equal to.  This mode is similar to
           LUPREV except that the specified key need not exist in the tree.

       LUNEXT
           Looks for the key specified, if not found returns "undef".  If the node is found returns the next
           node that is greater than the one found (or "undef" if there is no next node).

           This can be used to step through the tree in order.

       LUPREV
           Looks for the key specified, if not found returns "undef".  If the node is found returns the previous
           node that is less than the one found (or "undef" if there is no previous node).

           This can be used to step through the tree in reverse order.

   get(KEY)
       get() is an alias for lookup().

   iter([KEY])
       Returns an iterator object that can be used to traverse the tree in order.

       The iterator object supports a 'next' method that returns the next node in the tree or undef if all of
       the nodes have been visited.

       See the synopsis for an example.

       If a key is supplied, the iterator returned will traverse the tree in order starting from the node with
       key greater than or equal to the specified key.

           $it = $tree->iter('France');
           my $node = $it->next;
           print $node->key; # -> 'France'

   rev_iter([KEY])
       Returns an iterator object that can be used to traverse the tree in reverse order.

       If a key is supplied, the iterator returned will traverse the tree in order starting from the node with
       key less than or equal to the specified key.

           $it = $tree->rev_iter('France');
           my $node = $it->next;
           print $node->key; # -> 'France'

           $it = $tree->rev_iter('Finland');
           my $node = $it->next;
           print $node->key; # -> 'England'

   hseek(KEY, [{-reverse => 1|0}])
       For tied hashes, determines the next entry to be returned by each.

           tie my %capital, 'Tree::RB';

           $capital{'France'}  = 'Paris';
           $capital{'England'} = 'London';
           $capital{'Hungary'} = 'Budapest';
           $capital{'Ireland'} = 'Dublin';
           $capital{'Egypt'}   = 'Cairo';
           $capital{'Germany'} = 'Berlin';
           tied(%capital)->hseek('Germany');

           ($key, $val) = each %capital;
           print "$key, $val"; # -> Germany, Berlin

       The direction of iteration can be reversed by passing a hashref with key '-reverse' and value 1 to hseek
       after or instead of KEY, e.g. to iterate over the hash in reverse order:

           tied(%capital)->hseek({-reverse => 1});
           $key = each %capital;
           print $key; # -> Ireland

       The following calls are equivalent

           tied(%capital)->hseek('Germany', {-reverse => 1});
           tied(%capital)->hseek({-key => 'Germany', -reverse => 1});

   put(KEY, VALUE)
       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(KEY)
       If the tree has a node with the specified key, that node is deleted from the tree and returned, otherwise
       "undef" is returned.

DEPENDENCIES

       enum

INCOMPATIBILITIES

       None reported.

BUGS AND LIMITATIONS

       Please report any bugs or feature requests via the GitHub web interface at
       <https://github.com/arunbear/perl5-red-black-tree/issues>.

AUTHOR

       Arun Prasad  "<arunbear@cpan.org>"

       Some documentation has been borrowed from Benjamin Holzman's Tree::RedBlack and Damian Ivereigh's
       libredblack (<http://libredblack.sourceforge.net/>).

ACKNOWLEDGEMENTS

       Thanks for bug reports go to Anton Petrusevich, Wes Thompson, Petre Mierlutiu, Tomer Vromen, Christopher
       Gurnee and Ole Bjorn Hessen.

       Copyright (c) 2007, Arun Prasad "<arunbear@cpan.org>". All rights reserved.

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

DISCLAIMER OF WARRANTY

       BECAUSE THIS SOFTWARE IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE SOFTWARE, TO THE EXTENT
       PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER
       PARTIES PROVIDE THE SOFTWARE "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED,
       INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
       PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE SOFTWARE IS WITH YOU. SHOULD THE
       SOFTWARE PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR CORRECTION.

       IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY
       OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE SOFTWARE AS PERMITTED BY THE ABOVE LICENCE, BE LIABLE
       TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
       THE USE OR INABILITY TO USE THE SOFTWARE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING
       RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE SOFTWARE TO OPERATE
       WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
       DAMAGES.