NAME

       Paranoid::Data::AVLTree - AVL-Balanced Tree Class

VERSION

       $Id: lib/Paranoid/Data/AVLTree.pm, 2.10 2022/03/08 00:01:04 acorliss Exp $

SYNOPSIS

           # Preferred use
           tie %tree, 'Paranoid::Data::AVLTree';

           # 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);

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.

       NOTE: 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.

SUBROUTINES/METHODS

   new
           $tree   = new Paranoid::Data::AVLTree;

       This creates a new tree object.

   profile
           $rv     = $obj->profile(1);
           $rv     = $obj->profile(0);

       This method enables or disables performance profiling, which can provide some basic
       statistics on internal operations.  Whenever profiling is enabled the counters are reset.

   stats
           %stats = $obj->stats;

       This method returns a hash of various performance counters.  The contents of the hash at
       this time consists of the following:

           key         purpose
           ------------------------------------------------
           insertions  number of node insertions
           deletions   number of node deletions
           rebalances  number of rebalances triggered
           rotations   number of branch rotations triggered

   count
           $count  = $tree->count;

       This method returns a count of all the nodes in the tree.

   height
           $height = $tree->height;

       This method returns the height of the tree.

   nodeKeys
           @keys   = $tree->nodeKeys;

       This method returns a list of all keys for all nodes in the tree.

   nodeExists
           $rv     = $tree->nodeExists($key):

       This method returns a boolean value indicating whether a node exists wtih a matching key.

   fetchVal
           $val    = $tree->fetchVal($key);

       This method returns the associated value for the passed key.  Like hashes, it will return
       undef for nonexistant keys.

   addPair
           $rv     = $tree->addPair($key, $value);

       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.

   delNode
           $rv     = $tree->delNode($key);

       This method deletes the specified node if it exists.  It will return boolean false should
       no matching node exist.

   purgeNodes
           $rv     = $tree->purgeNodes;

       This purges all nodes from the tree.

   dumpKeys
           $tree->dumpKeys;

       This method exists purely for diagnostic purposes.  It dumps a formatted tree structure to
       STDERR 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.

   save2File
           $rv = $tree->save2File($filename);

       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.

   loadFromFile
           $rv = $tree->loadFromFile($filename);

       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.

   TIE METHODS
       These methods aren't intended for direct use, but to support tied hashes.

       CLEAR

       DELETE

       EXISTS

       FETCH

       FIRSTKEY

       NEXTKEY

       SCALAR

       STORE

       TIEHASH

       UNTIE

DEPENDENCIES

       o   Carp

       o   Paranoid

       o   Paranoid::Debug

       o   Paranoid::Data::AVLTree::AVLNode

BUGS AND LIMITATIONS

AUTHOR

       Arthur Corliss (corliss@digitalmages.com)

LICENSE AND COPYRIGHT

       This software is free software.  Similar to Perl, you can redistribute it and/or modify it
       under the terms of either:

         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>,

       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.

       (c) 2005 - 2020, Arthur Corliss (corliss@digitalmages.com) (tm) 2008 - 2020, Paranoid Inc.
       (www.paranoid.com)