.\" Automatically generated by Pod::Man v1.37, Pod::Parser v1.32
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sh \" Subsection heading
.br
.if t .Sp
.ne 5
.PP
\fB\\$1\fR
.PP
..
.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.  | will give a
.\" real vertical bar.  \*(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-|\(bv\*(Tr
.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" ''
'br\}
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.if \nF \{\
.    de IX
.    tm Index:\\$1\t\\n%\t"\\$2"
..
.    nr % 0
.    rr F
.\}
.\"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.hy 0
.if n .na
.\"
.\" 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::Node 3"
.TH Tree::Node 3 "2008-01-07" "perl v5.8.8" "User Contributed Perl Documentation"
.SH "NAME"
Tree::Node \- Memory\-efficient tree nodes in Perl
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 1
\&  use Tree::Node;
.Ve
.PP
.Vb 1
\&  $node = Tree::Node->new(2);
.Ve
.PP
.Vb 2
\&  $node->set_child(0, $left);
\&  $node->set_child(1, $right);
.Ve
.PP
.Vb 3
\&  while ($node->key_cmp($key) < 0) {
\&    $node = $node->get_child(0);
\&  }
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This module implements a memory-efficient node type (for trees,
skip lists and similar data structures) for Perl.
.PP
You may ask \*(L"Why bother implementing an ordered structure such
as a tree when Perl has hashes built\-in?\*(R"  Since Perl is optimized
for speed over memory usage, hashes (and lists) use a lot of memory.
.PP
Using Devel::Size for a reference, a list with four elements
(corresponding to a key, value, and two child node pointers) will
use at least 120 bytes.  A hash with four key/value pairs will
use at least 228 bytes.  But an equivalent Tree::Node object
will use at least 68 bytes.  (However, see the \*(L"\s-1KNOWN\s0 \s-1ISSUES\s0\*(R"
section below for caveats regarding memory usage.)
.PP
So the purpose of this package is to provide a simple low-level Node
class which can be used as a base class to implement various kinds
of tree structures.  Each node has a key/value pair and a variable
number of \*(L"children\*(R" pointers.
.PP
How nodes are organized or the algorithm used to organize them is
for you to implement.
.Sh "Object Oritented Interface"
.IX Subsection "Object Oritented Interface"
.IP "new" 4
.IX Item "new"
.Vb 1
\&  $node = Tree::Node->new( $child_count );
.Ve
.Sp
Creates a new node with \f(CW$child_count\fR children.  Only as much space as is
needed is allocated, and the number of children cannot be expanded later
on.
.Sp
\&\f(CW$child_count\fR cannot exceed \*(L"\s-1MAX_LEVEL\s0\*(R".
.IP "child_count" 4
.IX Item "child_count"
.Vb 1
\&  $child_count = $node->child_count;
.Ve
.Sp
Returns the number of childen allocated.
.IP "set_key" 4
.IX Item "set_key"
.Vb 1
\&  $node->set_key($key);
.Ve
.Sp
Sets the key. Once it is set, it cannot be changed.
.IP "key" 4
.IX Item "key"
.Vb 1
\&  $key = $node->key;
.Ve
.Sp
Returns the node key.
.IP "key_cmp" 4
.IX Item "key_cmp"
.Vb 1
\&  if ($node->key_cmp($key) < 0) { ... }
.Ve
.Sp
Compares the node key with a key using the Perl string comparison
function \f(CW\*(C`cmp\*(C'\fR.  Returns \-1 if the node key is less than the
argument, 0 if it is equal, and 1 if it is greater.
.Sp
This method can be overriden if you need a different comparison
routine.  To use numeric keys, for example:
.Sp
.Vb 1
\&  package Tree::Node::Numeric;
.Ve
.Sp
.Vb 1
\&  use base 'Tree::Node';
.Ve
.Sp
.Vb 5
\&  sub key_cmp {
\&    my $self = shift;
\&    my $key  = shift;
\&    return ($self->key <=> $key);
\&  }
.Ve
.Sp
\&\fBWarning\fR: if you are also using the \*(L"Procedural Interface\*(R", then you
should be aware that \*(L"p_key_cmp\*(R" will not be inherited.  Instead, you
should use something like the following:
.Sp
.Vb 2
\&  {
\&    no warnings 'redefine';
.Ve
.Sp
.Vb 5
\&    sub p_key_cmp {
\&      my $ptr  = shift;
\&      my $key  = shift;
\&      return (p_key_key($ptr) <=> $key);
\&    }
.Ve
.Sp
.Vb 6
\&    sub key_cmp {
\&      my $self = shift;
\&      my $key  = shift;
\&      return (p_key_cmp($self->to_p_node), $key);
\&    }
\&  }
.Ve
.IP "set_value" 4
.IX Item "set_value"
.Vb 1
\&  $node->set_value($value);
.Ve
.Sp
Sets the value of the node.  The value can be changed.
.IP "value" 4
.IX Item "value"
.Vb 1
\&  $value = $node->value;
.Ve
.Sp
Returns the value of the node.
.IP "set_child" 4
.IX Item "set_child"
.Vb 1
\&  $node->set_child($index, $child);
.Ve
.Sp
Sets the child node.  \f(CW$index\fR must be between 0 and \*(L"child_count\*(R"\-1.
Dues when the \f(CW$index\fR is out of bounds.
.IP "get_child" 4
.IX Item "get_child"
.Vb 1
\&  $child = $node->get_child($index);
.Ve
.Sp
Returns the child node.  Dies when the \f(CW$index\fR is out of bounds.
.IP "get_child_or_undef" 4
.IX Item "get_child_or_undef"
.Vb 1
\&  $child = $node->get_child_or_undef($index);
.Ve
.Sp
Like \*(L"get_child\*(R", but returns \f(CW\*(C`undef\*(C'\fR rather than dying when the
\&\f(CW$index\fR is out of bounds.
.IP "get_children" 4
.IX Item "get_children"
.Vb 1
\&  @children = $node->get_children;
.Ve
.IP "add_children" 4
.IX Item "add_children"
.Vb 1
\&  $node->add_children(@children)
.Ve
.Sp
Increases the \*(L"child_count\*(R" and allocates space for the child nodes
specified.  (The child nodes can be \f(CW\*(C`undef\*(C'\fR.)
.IP "add_children_left" 4
.IX Item "add_children_left"
Same as \*(L"add_children\*(R", except that the new nodes are added to
the beginning rather than end of the node list.
.IP "\s-1MAX_LEVEL\s0" 4
.IX Item "MAX_LEVEL"
.Vb 1
\&  use Tree::Node ':utility';
.Ve
.Sp
.Vb 1
\&  ...
.Ve
.Sp
.Vb 1
\&  $max = MAX_LEVEL;
.Ve
.Sp
Returns the maximum number of children. Defaults to the C constant
\&\f(CW\*(C`UCHAR_MAX\*(C'\fR, which is usually 255.
.IP "_allocated" 4
.IX Item "_allocated"
.Vb 1
\&  $size = $node->_allocated;
.Ve
.Sp
This is a utility routine which says how much space is allocated for a
node.  It does not include the Perl overhead (see \*(L"\s-1KNOWN\s0 \s-1ISSUES\s0\*(R" below).
.IP "_allocated_by_child_count" 4
.IX Item "_allocated_by_child_count"
.Vb 1
\&  use Tree::Node ':utility';
.Ve
.Sp
.Vb 1
\&  ...
.Ve
.Sp
.Vb 1
\&  $size = _allocated_by_child_count( $child_count );
.Ve
.Sp
This is a utility routine which returns the amount of space that would be
allocated for a node with \f(CW$child_count\fR children.
.IP "to_p_node" 4
.IX Item "to_p_node"
.Vb 1
\&  $ptr = $node->to_p_node;
.Ve
.Sp
This returns the pointer to the raw node data, which can be used in
the \*(L"Procedural Interface\*(R".
.Sp
\&\fBWarning\fR: do not mix and match object-oriented and procedural interface
calls when reading child nodes!  Child node pointers are stored in an
incompatible format.
.Sh "Procedural Inferface"
.IX Subsection "Procedural Inferface"
The experimental procedural interface was added in version 0.06.  The
advantage of this interface is that there is much less overhead than the
object-oriented interface (16 bytes instead of 45 bytes).  A disadvantage
is that the node cannot be simply subclassed to change the \*(L"p_key_cmp\*(R"
function.
.PP
To use the procedural interface, you must import the procedure names:
.PP
.Vb 1
\&  use Tree::Node ':p_node';
.Ve
.PP
Aside from working with pointers rather than blessed objects, the 
procedures listed below are analagous to their object-oriented
counterparts.
.PP
However, you must manually call \*(L"p_destroy\*(R" when you are done with
the node, since Perl will not automatically destroy it when done.
.IP "p_new" 4
.IX Item "p_new"
.Vb 1
\&  $ptr = p_new( $child_count );
.Ve
.IP "p_child_count" 4
.IX Item "p_child_count"
.Vb 1
\&  $child_count = p_child_count( $ptr );
.Ve
.IP "p_set_child" 4
.IX Item "p_set_child"
.Vb 1
\&  p_set_child( $mother_ptr, $index, $daughter_ptr );
.Ve
.IP "p_get_child" 4
.IX Item "p_get_child"
.Vb 1
\&  $daughter_ptr = p_get_child( $mother_ptr, $index );
.Ve
.IP "p_get_child_or_null" 4
.IX Item "p_get_child_or_null"
.Vb 1
\&  $daughter_ptr = p_get_child_or_null( $mother_ptr, $index );
.Ve
.IP "p_set_key" 4
.IX Item "p_set_key"
.Vb 1
\&  p_set_key( $ptr, $key );
.Ve
.Sp
See \*(L"to_p_node\*(R" for caveats about mixing interfaces.
.IP "p_get_key" 4
.IX Item "p_get_key"
.Vb 1
\&  $key = p_get_key( $ptr );
.Ve
.Sp
See \*(L"to_p_node\*(R" for caveats about mixing interfaces.
.IP "p_key_cmp" 4
.IX Item "p_key_cmp"
.Vb 1
\&  if (p_key_cmp( $ptr, $key ) < 0) { ... }
.Ve
.Sp
See \*(L"key_cmp\*(R" for caveats about mixing interfaces.
.IP "p_set_value" 4
.IX Item "p_set_value"
.Vb 1
\&  p_set_value( $ptr, $value );
.Ve
.IP "p_get_value" 4
.IX Item "p_get_value"
.Vb 1
\&  $value = p_get_value( $ptr );
.Ve
.IP "p_allocated" 4
.IX Item "p_allocated"
.Vb 1
\&  $size = p_allocated($ptr);
.Ve
.IP "p_destroy" 4
.IX Item "p_destroy"
.Vb 1
\&  p_destroy($ptr);
.Ve
.Sp
This unallocates the memory.  Perl will not call this automatically, so
you must remember to manually destroy each pointer!
.SH "KNOWN ISSUES"
.IX Header "KNOWN ISSUES"
This module implements a Perl wrapper around a C struct, which for the
object-oriented inferface involves a blessed reference to a pointer to
the struct.  This overhead of about 45 bytes may make up for any memory
savings that the C\-based struct provided!
.PP
So if you what you are doing is implementing a simple key/value lookup,
then you may be better off sticking with hashes.  If what you are doing
requires a special structure that cannot be satisfied with hashes (even
sorted hashes), then this module may be useful to you.
.PP
Another alternative is to use the \*(L"Procedural Interface\*(R".
.PP
Packages such as Clone and Storable cannot properly handle Tree::Node
objects.
.PP
Devel::Size may not properly determine the size of a node. Use the
\&\*(L"_allocated\*(R" method to determine how much space is allocated for the
node in C.  This does not include the overhead for Perl to maintain a
reference to the C struct.
.SH "SEE ALSO"
.IX Header "SEE ALSO"
Tree::DAG_Node is written in pure Perl, but it offers a more
flexible interface.
.SH "AUTHOR"
.IX Header "AUTHOR"
Robert Rothenberg <rrwo at cpan.org>
.Sh "Suggestions and Bug Reporting"
.IX Subsection "Suggestions and Bug Reporting"
Feedback is always welcome.  Please use the \s-1CPAN\s0 Request Tracker at
<http://rt.cpan.org> to submit bug reports.
.SH "LICENSE"
.IX Header "LICENSE"
Copyright (c) 2005 Robert Rothenberg. All rights reserved.
This program is free software; you can redistribute it and/or
modify it under the same terms as Perl itself.