.\" -*- mode: troff; coding: utf-8 -*-
.\" Automatically generated by Pod::Man 5.01 (Pod::Simple 3.43)
.\"
.\" 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
..
.\" \*(C` and \*(C' are quotes in nroff, nothing in troff, for use with C<>.
.ie n \{\
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    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 >0, 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
.\" ========================================================================
.\"
.IX Title "Paranoid::Data::AVLTree 3pm"
.TH Paranoid::Data::AVLTree 3pm 2024-03-07 "perl v5.38.2" "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
Paranoid::Data::AVLTree \- AVL\-Balanced Tree Class
.SH VERSION
.IX Header "VERSION"
\&\f(CW$Id:\fR lib/Paranoid/Data/AVLTree.pm, 2.10 2022/03/08 00:01:04 acorliss Exp $
.SH SYNOPSIS
.IX Header "SYNOPSIS"
.Vb 2
\&    # Preferred use
\&    tie %tree, \*(AqParanoid::Data::AVLTree\*(Aq;
\&
\&    # Or, purely as an object
\&    $tree   = new Paranoid::Data::AVLTree;
\&    $count  = $tree\->count;
\&    $height = $tree\->height;
\&    @keys   = $tree\->nodeKeys;
\&    $rv     = $tree\->nodeExists($key):
\&    $val    = $tree\->fetchVal($key);
\&    $rv     = $tree\->addPair($key, $value);
\&    $rv     = $tree\->delNode($key);
\&    $rv     = $tree\->purgeNodes;
\&
\&    $tree\->dumpKeys;
\&    $tree\->profile(1);
\&    %stats = $tree\->stats;
\&
\&    $rv = $tree\->save2File($filename);
\&    $rv = $tree\->loadFromFile($filename);
.Ve
.SH DESCRIPTION
.IX Header "DESCRIPTION"
This class provides an AVL-balance tree implementation, that can work both as
an independent object or as a tied hash.  Future versions will include methods
to allow for simple spooling to and from disk.
.PP
\&\fBNOTE:\fR while these objects do support assignment of any arbitrary value to
each node, spooling to and from files only supports the use of scalar values.
Any object/code references, globs, or nested data structures will not survive
save/load functionality.
.SH SUBROUTINES/METHODS
.IX Header "SUBROUTINES/METHODS"
.SS new
.IX Subsection "new"
.Vb 1
\&    $tree   = new Paranoid::Data::AVLTree;
.Ve
.PP
This creates a new tree object.
.SS profile
.IX Subsection "profile"
.Vb 2
\&    $rv     = $obj\->profile(1);
\&    $rv     = $obj\->profile(0);
.Ve
.PP
This method enables or disables performance profiling, which can provide some
basic statistics on internal operations.  Whenever profiling is enabled the
counters are reset.
.SS stats
.IX Subsection "stats"
.Vb 1
\&    %stats = $obj\->stats;
.Ve
.PP
This method returns a hash of various performance counters.  The contents of
the hash at this time consists of the following:
.PP
.Vb 6
\&    key         purpose
\&    \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-
\&    insertions  number of node insertions
\&    deletions   number of node deletions
\&    rebalances  number of rebalances triggered
\&    rotations   number of branch rotations triggered
.Ve
.SS count
.IX Subsection "count"
.Vb 1
\&    $count  = $tree\->count;
.Ve
.PP
This method returns a count of all the nodes in the tree.
.SS height
.IX Subsection "height"
.Vb 1
\&    $height = $tree\->height;
.Ve
.PP
This method returns the height of the tree.
.SS nodeKeys
.IX Subsection "nodeKeys"
.Vb 1
\&    @keys   = $tree\->nodeKeys;
.Ve
.PP
This method returns a list of all keys for all nodes in the tree.
.SS nodeExists
.IX Subsection "nodeExists"
.Vb 1
\&    $rv     = $tree\->nodeExists($key):
.Ve
.PP
This method returns a boolean value indicating whether a node exists wtih a
matching key.
.SS fetchVal
.IX Subsection "fetchVal"
.Vb 1
\&    $val    = $tree\->fetchVal($key);
.Ve
.PP
This method returns the associated value for the passed key.  Like hashes, it
will return undef for nonexistant keys.
.SS addPair
.IX Subsection "addPair"
.Vb 1
\&    $rv     = $tree\->addPair($key, $value);
.Ve
.PP
This method adds the requested key/value pair, or updates an existing node
with the same key.  It will return a boolean false if the key is an invalid
value.
.SS delNode
.IX Subsection "delNode"
.Vb 1
\&    $rv     = $tree\->delNode($key);
.Ve
.PP
This method deletes the specified node if it exists.  It will return boolean
false should no matching node exist.
.SS purgeNodes
.IX Subsection "purgeNodes"
.Vb 1
\&    $rv     = $tree\->purgeNodes;
.Ve
.PP
This purges all nodes from the tree.
.SS dumpKeys
.IX Subsection "dumpKeys"
.Vb 1
\&    $tree\->dumpKeys;
.Ve
.PP
This method exists purely for diagnostic purposes.  It dumps a formatted tree
structure to \fBSTDERR\fR showing all keys in the tree, along with the relative
branch height and balance of every node, along with what side of the tree each
node is attached.
.SS save2File
.IX Subsection "save2File"
.Vb 1
\&    $rv = $tree\->save2File($filename);
.Ve
.PP
This method saves the current contents of the AVL Tree to the specified file.
It attempts to save the nodes in an order which minimizes the number of
rotations when read to maximize loading performance.
.SS loadFromFile
.IX Subsection "loadFromFile"
.Vb 1
\&    $rv = $tree\->loadFromFile($filename);
.Ve
.PP
This method loads the contents of the named file into memory.  It does only the
most rudimentary validation of records upon loading.  Note that the current
contents of the AVL Tree is purged prior to loading to ensure the contents
after loading reflect precisely what is in the file.  That said, if there is
any kind of file corruption in the middle of the file, it can mean the AVL
Tree is only partially loaded after a failed attempt.
.SS "TIE METHODS"
.IX Subsection "TIE METHODS"
These methods aren't intended for direct use, but to support tied hashes.
.PP
\fICLEAR\fR
.IX Subsection "CLEAR"
.PP
\fIDELETE\fR
.IX Subsection "DELETE"
.PP
\fIEXISTS\fR
.IX Subsection "EXISTS"
.PP
\fIFETCH\fR
.IX Subsection "FETCH"
.PP
\fIFIRSTKEY\fR
.IX Subsection "FIRSTKEY"
.PP
\fINEXTKEY\fR
.IX Subsection "NEXTKEY"
.PP
\fISCALAR\fR
.IX Subsection "SCALAR"
.PP
\fISTORE\fR
.IX Subsection "STORE"
.PP
\fITIEHASH\fR
.IX Subsection "TIEHASH"
.PP
\fIUNTIE\fR
.IX Subsection "UNTIE"
.SH DEPENDENCIES
.IX Header "DEPENDENCIES"
.IP o 4
.IX Item "o"
Carp
.IP o 4
.IX Item "o"
Paranoid
.IP o 4
.IX Item "o"
Paranoid::Debug
.IP o 4
.IX Item "o"
Paranoid::Data::AVLTree::AVLNode
.SH "BUGS AND LIMITATIONS"
.IX Header "BUGS AND LIMITATIONS"
.SH AUTHOR
.IX Header "AUTHOR"
Arthur Corliss (corliss@digitalmages.com)
.SH "LICENSE AND COPYRIGHT"
.IX Header "LICENSE AND COPYRIGHT"
This software is free software.  Similar to Perl, you can redistribute it
and/or modify it under the terms of either:
.PP
.Vb 7
\&  a)     the GNU General Public License
\&         <https://www.gnu.org/licenses/gpl\-1.0.html> as published by the 
\&         Free Software Foundation <http://www.fsf.org/>; either version 1
\&         <https://www.gnu.org/licenses/gpl\-1.0.html>, or any later version
\&         <https://www.gnu.org/licenses/license\-list.html#GNUGPL>, or
\&  b)     the Artistic License 2.0
\&         <https://opensource.org/licenses/Artistic\-2.0>,
.Ve
.PP
subject to the following additional term:  No trademark rights to
"Paranoid" have been or are conveyed under any of the above licenses.
However, "Paranoid" may be used fairly to describe this unmodified
software, in good faith, but not as a trademark.
.PP
(c) 2005 \- 2020, Arthur Corliss (corliss@digitalmages.com)
(tm) 2008 \- 2020, Paranoid Inc. (www.paranoid.com)