avltree.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2004-2005 by Reality Rift Studios                       *
 *   http://www.realityrift.com  -  mattias@realityrift.com                *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#ifndef neo_core_avltree_h
#define neo_core_avltree_h

#include "platform.h"
#include "exception.h"
#include "queue.h"
#include "util.h"

namespace neo {
namespace core {

template < typename T, typename Cmp > class AVLTree;
    
template < typename T > class AVLTreeNode
{
    public:

    enum Balance
    {
        LEFTHEAVY,
    
        BALANCED,
    
        RIGHTHEAVY
    };


    inline                                              AVLTreeNode( AVLTreeNode* p_parent, const T& obj );
    
    Balance                                             _balance;
    
    AVLTreeNode*                                        _p_left;
    
    AVLTreeNode*                                        _p_right;
    
    AVLTreeNode*                                        _p_parent;
    
    T                                                   _obj;
};

template < class T > class AVLTreeIterator
{
    public:
    
    typedef std::forward_iterator_tag                       iterator_category;
    typedef T                                               value_type;
    typedef std::ptrdiff_t                                  difference_type;
    typedef T*                                              pointer;
    typedef T&                                              reference;
    
    typedef AVLTreeNode< T >                                Node;


    inline                                                  AVLTreeIterator( Node* p_node = 0 );


    inline                                                  AVLTreeIterator( const AVLTreeIterator& iter );


    inline T&                                               operator *();


    inline T*                                               operator ->();
    

    inline const T&                                         operator *() const;


    inline const T*                                         operator ->() const;


    inline AVLTreeIterator&                                 operator ++() const;


    inline AVLTreeIterator                                  operator ++(int) const;


    inline bool                                             operator ==( const AVLTreeIterator< T >& rhs ) const;


    inline bool                                             operator !=( const AVLTreeIterator< T >& rhs ) const;


    inline AVLTreeIterator&                                 operator = ( const AVLTreeIterator< T >& rhs ) const;


    inline                                                  operator bool () const;


    inline AVLTreeIterator                                  left() const;


    inline AVLTreeIterator                                  right() const;


    inline AVLTreeIterator                                  parent() const;


    inline bool                                             isLeaf() const;

    mutable Node*                                           _p_node;

    private:
    
    mutable Queue< Node* >                                  _nodes;
};

template < class T, class Cmp = Comparator< T, T > > class AVLTree : public Noncopyable
{
    public:
    
    typedef AVLTreeIterator< T >                            iterator;
    
    typedef const iterator                                  const_iterator;
    
    
    typedef AVLTreeNode< T >                                Node;
    
    
                                                            AVLTree();

    virtual                                                ~AVLTree();


    inline void                                             insert( const T& obj );


    inline void                                             erase( const T& obj );


    inline void                                             erase( const_iterator& pos );
    

    void                                                    clear();
    

    inline unsigned int                                     size() const;
    

    inline bool                                             empty() const;
    

    inline iterator                                         begin();
    

    inline const_iterator                                   begin() const;
    

    inline iterator                                         end();
    

    inline const_iterator                                   end() const;
    

    inline void                                             swap( AVLTree< T, Cmp >& tree );
    
#if !NEO_COMPILER_MSVC7
    //MSVC 7 cannot handle the templated friend declaration, cheers MS
    private:
#endif

    enum Result
    {
        OK,

        BALANCE,

        INVALID
    };


    Node*                                                   _p_root;

    unsigned int                                            _size;



    inline void                                             rotateLeft( Node** pp_node );


    inline void                                             rotateRight( Node** pp_node );


    inline Result                                           balanceLeftGrown( Node** pp_node );


    inline Result                                           balanceRightGrown( Node** pp_node );


    inline Result                                           balanceLeftShrunk( Node** pp_node );


    inline Result                                           balanceRightShrunk( Node** pp_node );


    inline bool                                             replaceWithHighest( Node* p_target, Node** pp_subtree, Result* p_result );
    

    inline bool                                             replaceWithLowest( Node* p_target, Node** pp_subtree, Result* p_result );
    

    Result                                                  insert( Node** pp_parent, Node** pp_node, const T& data );
    

    Result                                                  erase( Node** pp_node, const T& data );
    

    void                                                    deleteSubtree( Node* p_node );


    Node**                                                  getParent( Node* p_node );
    
#if !NEO_COMPILER_MSVC7
    //MSVC 7 cannot handle the templated friend declaration, cheers MS
    template < typename TT, typename TKey, typename TCmp > friend typename AVLTree< TT, TCmp >::iterator searchBestFit( AVLTree< TT, TCmp >& tree, const TKey& key );
#endif
};


template < typename T, typename Key, typename Cmp > typename AVLTree< T, Cmp >::iterator searchBestFit( AVLTree< T, Cmp >& tree, const Key& key );

//template < typename T > bool validateTree( AVLTree< T >& tree );

#include "avltree.inl"


template < typename T, typename Cmp > inline void swap( AVLTree< T, Cmp >& lval, AVLTree< T, Cmp >& rval ) { lval.swap( rval ); }

}
}

#endif

---