AVLTree.h

Go to the documentation of this file.

/** @file AVLTree.h
* @author Gabor Madl
* @date Created 10/2006
* @brief AVL-tree template class.
*
*
* =================================================================
* DREAM License v2.0
* 
* DREAM - Distributed Real-time Embedded Analysis Method
* http://dre.sourceforge.net.
* Copyright (c) 2005-2007 Gabor Madl, All Rights Reserved.
* 
* This file is part of DREAM.
* 
* DREAM is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation. No future versions of
* the GPL license may be automatically applied to DREAM. It is in
* the sole discretion of the copyright holder to determine whether
* DREAM may be released under a different license or terms. There
* are no restrictions on the use of DREAM for any purpose.
* 
* DREAM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* 
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
* 
* By submitting comments, suggestions, code, code snippets,
* techniques (including that of usage), and algorithms, submitters
* acknowledge that they have the right to do so, that any such
* submissions are given freely and unreservedly, and that they
* waive any claims to copyright or ownership. In addition,
* submitters acknowledge that any such submission might become
* part of the copyright maintained on the overall body of code,
* which comprises DREAM. By making a submission, submitter agrees
* to these terms. Furthermore, submitters acknowledge that the
* incorporation or modification of such submissions is entirely
* at the discretion of the moderators of the DREAM project.
* 
* DREAM links to the Libxml2 third party library. Please see 
* COPYING-libxml for the copyright information of Libxml2.
* =================================================================
*/

#if (_MSC_VER >= 1400)                          // VC8+
#pragma warning (disable:4996)          // Disable all deprecation warnings
#endif 

#ifndef DREAM_AVLTREE
#define DREAM_AVLTREE

/** Unsigned int type definition.
* Redefining the basic type allows easy portability to 8 or 16 bit machines. 
*/
typedef unsigned int uint;
#define maxuint 4294967295

#include "Iterator.h"
#include "Iterator.cpp"

namespace DREAM
{

template <class key_type, class item_type> class AVLTree;

/** Class for one element in the AVLTree. */
template <class key_type, class item_type>
class AVLTreeNode
{
// friend class declarations and typedefs confuse Doxygen... Starting with protected members first.
protected:
        /** ++ operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        AVLTreeNode <key_type, item_type>* iter_next ();

        /** -- operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        AVLTreeNode <key_type, item_type>* iter_previous ();

        /** ++ operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        const AVLTreeNode <key_type, item_type>* iter_next () const;

        /** -- operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        const AVLTreeNode <key_type, item_type>* iter_previous () const;

        /** The left child of the node. */
        AVLTreeNode <key_type, item_type>* left_;
        
        /** The right child of the node. */
        AVLTreeNode <key_type, item_type>* right_;

        /** The parent of the node. */
        AVLTreeNode <key_type, item_type>* parent_;

        /** Stores the depth of the node's subtree. */
        uint depth_;

        /** Stores the number of nodes with the given depth.
        * The use of this variable allows us to decrease the depth of trees when no more nodes are available with the give depth.
        */
        uint depth_count_;

public:
        /** Constructor. */
        AVLTreeNode (key_type key, item_type item, AVLTreeNode <key_type, item_type>* parent = NULL);

        /** Destructor. */
        ~AVLTreeNode ();

        /** Called when the node is on the path to a newly inserted or removed node. 
        * It manages the depth_ and depth_count_ variables...
        */
        void calculate_depth ();

        /** Returns the depth of the subtree from the given point */
        uint depth ();

        /** Return the left child of the node. */
        AVLTreeNode <key_type, item_type>* left ();

        /** Return the left child of the node. */
        const AVLTreeNode <key_type, item_type>* left () const ;

        /** Sets the left child of the node. */
        void left (AVLTreeNode <key_type, item_type>* node_ptr);

        /** Return the right child of the node. */
        AVLTreeNode <key_type, item_type>* right ();

        /** Return the right child of the node. */
        const AVLTreeNode <key_type, item_type>* right () const;

        /** Sets the right child of the node. */
        void right (AVLTreeNode <key_type, item_type>* node_ptr);

        /** Returns the parent of the node. */
        AVLTreeNode <key_type, item_type>* parent ();

        /** Returns the parent of the node. */
        const AVLTreeNode <key_type, item_type>* parent () const;

        /** Sets the parent of the node. */
        void parent (AVLTreeNode <key_type, item_type>* node_ptr);

        /** Assignment operator */
        AVLTreeNode <key_type, item_type>& operator= (AVLTreeNode <key_type, item_type>& node);

        /** The key of the node. */
        key_type first;

        /** The item of the node. */
        item_type second;

        /** Allow iterators to manipulate protected members. */
        friend class Iterator <AVLTreeNode <key_type, item_type> >;

        /** Allow iterators to manipulate protected members. */
        friend class Const_Iterator <AVLTreeNode <key_type, item_type> >;

        /** Allow AVLTree to manipulate protected members. */
        friend class AVLTree <key_type, item_type>;
};



/** This class combines STL vectors and maps providing a fast implementation for find (), operator++ (), operator-- (), 
* and operator[] () in a common class. This is necessary since we want random access to elements in the tree, which
* requires a mix of STL maps and vectors. We prefer faster find and insert  operations, therefore the underlying data
* structure is an AVL tree as it allows for the easy and efficient implementation of all these operators.
*/
template <class key_type, class item_type>
class AVLTree
{
// friend class declarations and typedefs confuse Doxygen... Starting with protected members first.
protected:
        /** Balances the AVLTree from the given node if necessary. */
        void balance (AVLTreeNode <key_type, item_type>* node_ptr);

        /** Balances the AVLTree to the right from the given node. */
        void balance_left (AVLTreeNode <key_type, item_type>* node_ptr);

        /** Balances the AVLTree to the right from the given node. */
        void balance_right (AVLTreeNode <key_type, item_type>* node_ptr);

        /** Finds the next smaller node in the subtree of node_ptr, removes it, and reconstructs the tree. */
        AVLTreeNode <key_type, item_type>* get_smaller_node (AVLTreeNode <key_type, item_type>* node_ptr,
                AVLTreeNode <key_type, item_type>* left_ptr, AVLTreeNode <key_type, item_type>* right_ptr);

        /** Finds the next larger node in the subtree of node_ptr, removes it, and reconstructs the tree. */
        AVLTreeNode <key_type, item_type>* get_larger_node (AVLTreeNode <key_type, item_type>* node_ptr,
                AVLTreeNode <key_type, item_type>* left_ptr, AVLTreeNode <key_type, item_type>* right_ptr);

        /** Erase a leaf from the AVLTree. */
        void erase_leaf (AVLTreeNode <key_type, item_type>* node_ptr, AVLTreeNode <key_type, item_type>* parent_ptr);

        /** Erase a node with only a left child from the AVLTree. */
        void erase_left_child (AVLTreeNode <key_type, item_type>* node_ptr, 
                AVLTreeNode <key_type, item_type>* parent_ptr, AVLTreeNode <key_type, item_type>* left_ptr);

        /** Erase a node with only a right child from the AVLTree. */
        void erase_right_child (AVLTreeNode <key_type, item_type>* node_ptr, 
                AVLTreeNode <key_type, item_type>* parent_ptr, AVLTreeNode <key_type, item_type>* right_ptr);

        /** Erase a node with both children present from the AVLTree. */
        void erase (AVLTreeNode <key_type, item_type>* node_ptr, AVLTreeNode <key_type, item_type>* parent_ptr, 
                AVLTreeNode <key_type, item_type>* left_ptr, AVLTreeNode <key_type, item_type>* right_ptr);

        /** Pointer to the root of the tree. */
        AVLTreeNode <key_type, item_type>* root_ptr_;

        /** Pointer to the last element of the tree. */
        AVLTreeNode <key_type, item_type>* last_ptr_;

        /** Stores the number of items in the AVLTree. */
        uint size_;

public:
        /** Constructor. */
        AVLTree ();

        /** Destructor. */
        ~AVLTree ();

        /** Assign operator. */
        void assign (const AVLTreeNode <key_type, item_type>* begin_node, const AVLTreeNode <key_type, item_type>* end_node);

        /** Assign operator. */
        void assign (Iterator <AVLTreeNode <key_type, item_type> >& begin_iter, Iterator <AVLTreeNode <key_type, item_type> >& end_iter);

        /** Assign operator. */
        void assign (Const_Iterator <AVLTreeNode <key_type, item_type> >& begin_iter, Const_Iterator <AVLTreeNode <key_type, item_type> >& end_iter);

        /** Returns a pointer to the smallest element in the AVLTree. */
        AVLTreeNode <key_type, item_type>* begin ();

        /** Returns a pointer to the smallest element in the AVLTree. */
        const AVLTreeNode <key_type, item_type>* begin () const;

        /** Erases elements in the AVLTree. */
        void clear ();

        /** Erases elements in the AVLTree, and calls delete on the item_type.
        * Use this function whenever you would like to iterate through the AVLTree, and erase dynamically allocated data.
        */
        void destroy ();

        /** Returns true if the AVLTree is empty. */
        bool empty ();

        /** Returns true if the AVLTree is empty. */
        bool empty () const;

        /** Returns NULL. */
        AVLTreeNode <key_type, item_type>* end ();

        /** Returns NULL. */
        const AVLTreeNode <key_type, item_type>* end () const;

        /** Erase a node from the AVLTree. */
        void erase (Iterator <AVLTreeNode <key_type, item_type> >& iter);

        /** Erase a node from the AVLTree. */
        void erase (key_type key);

        /** Finds an AVLTree node in the AVLTree. */
        AVLTreeNode <key_type, item_type>* find (const key_type& key);

        /** Finds an AVLTree node in the AVLTree. */
        const AVLTreeNode <key_type, item_type>* find (const key_type& key) const;

        /** Inserts an AVLTree node in the AVLTree. */
        void insert (key_type key, item_type item);

        /** Returns an iterator to the last element of the AVLTree. */
        AVLTreeNode <key_type, item_type>* last ();

        /** Returns an iterator to the last element of the AVLTree. */
        const AVLTreeNode <key_type, item_type>* last () const;

        /** operator [].*/
        item_type& operator [] (uint i);

        /** operator [].*/
        const item_type& operator [] (uint i) const;

        /** Return the number of items in the AVLTree. */
        uint size () const;

        /** iterator class for convenience. */
        typedef Iterator <AVLTreeNode <key_type, item_type> > iterator;

        /** const_iterator class for convenience. */
        typedef Const_Iterator <AVLTreeNode <key_type, item_type> > const_iterator;

        /** Allow iterators to manipulate protected members. */
        friend class Iterator <AVLTreeNode <key_type, item_type> >;

        /** Allow iterators to manipulate protected members. */
        friend class Const_Iterator <AVLTreeNode <key_type, item_type> >;
};

};

#endif

---