.\" Automatically generated by Pod::Man 2.27 (Pod::Simple 3.28)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Tree::RB 3pm"
.TH Tree::RB 3pm "2013-09-15" "perl v5.18.1" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Tree::RB \- Perl implementation of the Red/Black tree, a type of balanced binary search tree.
.SH "VERSION"
.IX Header "VERSION"
This document describes Tree::RB version 0.500004
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 1
\&    use Tree::RB;
\&
\&    my $tree = Tree::RB\->new;
\&    $tree\->put(\*(AqFrance\*(Aq  => \*(AqParis\*(Aq);
\&    $tree\->put(\*(AqEngland\*(Aq => \*(AqLondon\*(Aq);
\&    $tree\->put(\*(AqHungary\*(Aq => \*(AqBudapest\*(Aq);
\&    $tree\->put(\*(AqIreland\*(Aq => \*(AqDublin\*(Aq);
\&    $tree\->put(\*(AqEgypt\*(Aq   => \*(AqCairo\*(Aq);
\&    $tree\->put(\*(AqGermany\*(Aq => \*(AqBerlin\*(Aq);
\&
\&    $tree\->put(\*(AqAlaska\*(Aq => \*(AqAnchorage\*(Aq); # D\*(Aqoh! Alaska isn\*(Aqt a Country
\&    $tree\->delete(\*(AqAlaska\*(Aq);
\&
\&    print scalar $tree\->get(\*(AqIreland\*(Aq); # \*(AqDublin\*(Aq
\&
\&    print $tree\->min\->key; # \*(AqEgypt\*(Aq 
\&    print $tree\->max\->key; # \*(AqIreland\*(Aq 
\&    print $tree\->size; # 6
\&
\&    # print items, ordered by key
\&    my $it = $tree\->iter;
\&
\&    while(my $node = $it\->next) {
\&        printf "key = %s, value = %s\en", $node\->key, $node\->val;
\&    }
\&
\&    # print items in reverse order
\&    $it = $tree\->rev_iter;
\&
\&    while(my $node = $it\->next) {
\&        printf "key = %s, value = %s\en", $node\->key, $node\->val;
\&    }
\&
\&    # Hash interface
\&    tie my %capital, \*(AqTree::RB\*(Aq;
\&
\&    # or do this to store items in descending order 
\&    tie my %capital, \*(AqTree::RB\*(Aq, sub { $_[1] cmp $_[0] };
\&
\&    $capital{\*(AqFrance\*(Aq}  = \*(AqParis\*(Aq;
\&    $capital{\*(AqEngland\*(Aq} = \*(AqLondon\*(Aq;
\&    $capital{\*(AqHungary\*(Aq} = \*(AqBudapest\*(Aq;
\&    $capital{\*(AqIreland\*(Aq} = \*(AqDublin\*(Aq;
\&    $capital{\*(AqEgypt\*(Aq}   = \*(AqCairo\*(Aq;
\&    $capital{\*(AqGermany\*(Aq} = \*(AqBerlin\*(Aq;
\&
\&    # print items in order
\&    while(my ($key, $val) = each %capital) {
\&        printf "key = $key, value = $val\en";
\&    }
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This is a Perl implementation of the Red/Black tree, a type of balanced binary search tree.
.PP
A tied hash interface is also provided to allow ordered hashes to be used.
.PP
See the Wikipedia article at <http://en.wikipedia.org/wiki/Red\-black_tree> for more on Red/Black trees.
.SH "INTERFACE"
.IX Header "INTERFACE"
.SS "new([\s-1CODEREF\s0])"
.IX Subsection "new([CODEREF])"
Creates and returns a new tree. If a reference to a subroutine is passed to
\&\fInew()\fR, the subroutine will be used to override the tree's default lexical
ordering and provide a user a defined ordering.
.PP
This subroutine should be just like a comparator subroutine used with sort, 
except that it doesn't do the \f(CW$a\fR, \f(CW$b\fR trick.
.PP
For example, to get a case insensitive ordering
.PP
.Vb 5
\&    my $tree = Tree::RB\->new(sub { lc $_[0] cmp lc $_[1]});
\&    $tree\->put(\*(AqWall\*(Aq  => \*(AqLarry\*(Aq);
\&    $tree\->put(\*(AqSmith\*(Aq => \*(AqAgent\*(Aq);
\&    $tree\->put(\*(Aqmouse\*(Aq => \*(Aqmicky\*(Aq);
\&    $tree\->put(\*(Aqduck\*(Aq  => \*(Aqdonald\*(Aq);
\&
\&    my $it = $tree\->iter;
\&
\&    while(my $node = $it\->next) {
\&        printf "key = %s, value = %s\en", $node\->key, $node\->val;
\&    }
.Ve
.SS "resort(\s-1CODEREF\s0)"
.IX Subsection "resort(CODEREF)"
Changes the ordering of nodes within the tree. The new ordering is
specified by a comparator subroutine which must be passed to \fIresort()\fR.
.PP
See \*(L"new\*(R" for further information about the comparator.
.SS "\fIsize()\fP"
.IX Subsection "size()"
Returns the number of nodes in the tree.
.SS "\fIroot()\fP"
.IX Subsection "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.
.SS "\fImin()\fP"
.IX Subsection "min()"
Returns the node with the minimal key.
.SS "\fImax()\fP"
.IX Subsection "max()"
Returns the node with the maximal key.
.SS "lookup(\s-1KEY,\s0 [\s-1MODE\s0])"
.IX Subsection "lookup(KEY, [MODE])"
When called in scalar context, lookup(\s-1KEY\s0) returns the value
associated with \s-1KEY.\s0
.PP
When called in list context, lookup(\s-1KEY\s0) returns a list whose first
element is the value associated with \s-1KEY,\s0 and whose second element
is the node containing the key/value.
.PP
An optional \s-1MODE\s0 parameter can be passed to \fIlookup()\fR to influence
which key is returned.
.PP
The values of \s-1MODE\s0 are constants that are exported on demand by
Tree::RB
.PP
.Vb 1
\&    use Tree::RB qw[LUEQUAL LUGTEQ LULTEQ LUGREAT LULESS LUNEXT LUPREV];
.Ve
.IP "\s-1LUEQUAL\s0" 4
.IX Item "LUEQUAL"
Returns node exactly matching the key.
.IP "\s-1LUGTEQ\s0" 4
.IX Item "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.
.IP "\s-1LULTEQ\s0" 4
.IX Item "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.
.IP "\s-1LUGREAT\s0" 4
.IX Item "LUGREAT"
Returns the node that is just greater than the specified key \- not equal to. 
This mode is similar to \s-1LUNEXT\s0 except that the specified key need not exist in the tree.
.IP "\s-1LULESS\s0" 4
.IX Item "LULESS"
Returns the node that is just less than the specified key \- not equal to. 
This mode is similar to \s-1LUPREV\s0 except that the specified key need not exist in the tree.
.IP "\s-1LUNEXT\s0" 4
.IX Item "LUNEXT"
Looks for the key specified, if not found returns \f(CW\*(C`undef\*(C'\fR. 
If the node is found returns the next node that is greater than 
the one found (or \f(CW\*(C`undef\*(C'\fR if there is no next node).
.Sp
This can be used to step through the tree in order.
.IP "\s-1LUPREV\s0" 4
.IX Item "LUPREV"
Looks for the key specified, if not found returns \f(CW\*(C`undef\*(C'\fR. 
If the node is found returns the previous node that is less than 
the one found (or \f(CW\*(C`undef\*(C'\fR if there is no previous node).
.Sp
This can be used to step through the tree in reverse order.
.SS "get(\s-1KEY\s0)"
.IX Subsection "get(KEY)"
\&\fIget()\fR is an alias for \fIlookup()\fR.
.SS "iter([\s-1KEY\s0])"
.IX Subsection "iter([KEY])"
Returns an iterator object that can be used to traverse the tree in order.
.PP
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.
.PP
See the synopsis for an example.
.PP
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.
.PP
.Vb 3
\&    $it = $tree\->iter(\*(AqFrance\*(Aq);
\&    my $node = $it\->next;
\&    print $node\->key; # \-> \*(AqFrance\*(Aq
.Ve
.SS "rev_iter([\s-1KEY\s0])"
.IX Subsection "rev_iter([KEY])"
Returns an iterator object that can be used to traverse the tree in reverse order.
.PP
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.
.PP
.Vb 3
\&    $it = $tree\->rev_iter(\*(AqFrance\*(Aq);
\&    my $node = $it\->next;
\&    print $node\->key; # \-> \*(AqFrance\*(Aq
\&
\&    $it = $tree\->rev_iter(\*(AqFinland\*(Aq);
\&    my $node = $it\->next;
\&    print $node\->key; # \-> \*(AqEngland\*(Aq
.Ve
.SS "hseek(\s-1KEY,\s0 [{\-reverse => 1|0}])"
.IX Subsection "hseek(KEY, [{-reverse => 1|0}])"
For tied hashes, determines the next entry to be returned by each.
.PP
.Vb 1
\&    tie my %capital, \*(AqTree::RB\*(Aq;
\&
\&    $capital{\*(AqFrance\*(Aq}  = \*(AqParis\*(Aq;
\&    $capital{\*(AqEngland\*(Aq} = \*(AqLondon\*(Aq;
\&    $capital{\*(AqHungary\*(Aq} = \*(AqBudapest\*(Aq;
\&    $capital{\*(AqIreland\*(Aq} = \*(AqDublin\*(Aq;
\&    $capital{\*(AqEgypt\*(Aq}   = \*(AqCairo\*(Aq;
\&    $capital{\*(AqGermany\*(Aq} = \*(AqBerlin\*(Aq;
\&    tied(%capital)\->hseek(\*(AqGermany\*(Aq);
\&
\&    ($key, $val) = each %capital;
\&    print "$key, $val"; # \-> Germany, Berlin
.Ve
.PP
The direction of iteration can be reversed by passing a hashref with key '\-reverse' and value 1
to hseek after or instead of \s-1KEY,\s0 e.g. to iterate over the hash in reverse order:
.PP
.Vb 3
\&    tied(%capital)\->hseek({\-reverse => 1});
\&    $key = each %capital;
\&    print $key; # \-> Ireland
.Ve
.PP
The following calls are equivalent
.PP
.Vb 2
\&    tied(%capital)\->hseek(\*(AqGermany\*(Aq, {\-reverse => 1});
\&    tied(%capital)\->hseek({\-key => \*(AqGermany\*(Aq, \-reverse => 1});
.Ve
.SS "put(\s-1KEY, VALUE\s0)"
.IX Subsection "put(KEY, VALUE)"
Adds a new node to the tree.
.PP
The first argument is the key of the node, the second is its value.
.PP
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.
.SS "delete(\s-1KEY\s0)"
.IX Subsection "delete(KEY)"
If the tree has a node with the specified key, that node is
deleted from the tree and returned, otherwise \f(CW\*(C`undef\*(C'\fR is returned.
.SH "DEPENDENCIES"
.IX Header "DEPENDENCIES"
enum
.SH "INCOMPATIBILITIES"
.IX Header "INCOMPATIBILITIES"
None reported.
.SH "BUGS AND LIMITATIONS"
.IX Header "BUGS AND LIMITATIONS"
Please report any bugs or feature requests via the GitHub web interface at 
<https://github.com/arunbear/perl5\-scalar\-constant/issues>.
.SH "AUTHOR"
.IX Header "AUTHOR"
Arun Prasad  \f(CW\*(C`<arunbear@cpan.org>\*(C'\fR
.PP
Some documentation has been borrowed from Benjamin Holzman's Tree::RedBlack
and Damian Ivereigh's libredblack (<http://libredblack.sourceforge.net/>).
.SH "ACKNOWLEDGEMENTS"
.IX Header "ACKNOWLEDGEMENTS"
Thanks for bug reports go to Anton Petrusevich, Wes Thompson, Petre Mierlutiu, Tomer Vromen and Christopher Gurnee.
.SH "LICENCE AND COPYRIGHT"
.IX Header "LICENCE AND COPYRIGHT"
Copyright (c) 2007, Arun Prasad \f(CW\*(C`<arunbear@cpan.org>\*(C'\fR. All rights reserved.
.PP
This module is free software; you can redistribute it and/or
modify it under the same terms as Perl itself. See perlartistic.
.SH "DISCLAIMER OF WARRANTY"
.IX Header "DISCLAIMER OF WARRANTY"
\&\s-1BECAUSE 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 \*(L"AS IS\*(R" 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.\s0
.PP
\&\s-1IN 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 \s0(\s-1INCLUDING 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\s0), \s-1EVEN IF
SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF
SUCH DAMAGES.\s0