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.

LICENCE AND COPYRIGHT

       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.