avl_base.hpp

Go to the documentation of this file.

/*
  CLAW - a C++ Library Absolutely Wonderful

  CLAW is a free library without any particular aim but being useful to 
  anyone.

  Copyright (C) 2005-2011 Julien Jorge

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library 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
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

  contact: julien.jorge@gamned.org
*/
#ifndef __CLAW_AVL_BASE_HPP__
#define __CLAW_AVL_BASE_HPP__

#include <iterator>
#include <cstddef>

#include <claw/binary_node.hpp>

namespace claw
{
  //---------------------------------------------------------------------------
  template < class K, class Comp = std::less<K> >
  class avl_base
  {
  private:

    //**************************** avl_node ***********************************

    class avl_node:
      public binary_node< typename claw::avl_base<K,Comp>::avl_node >
    {
    private:
      typedef binary_node< typename claw::avl_base<K,Comp>::avl_node > super;

    public:
      explicit avl_node( const K& k );
      ~avl_node();

      avl_node* duplicate( unsigned int& count ) const;

      void del_tree();
      unsigned int depth() const;

      avl_node* find( const K& k );
      const avl_node* find( const K& k ) const;

      avl_node* find_nearest_greater( const K& key );
      const avl_node* find_nearest_greater( const K& key ) const;

      avl_node* find_nearest_lower( const K& key );
      const avl_node* find_nearest_lower( const K& key ) const;

      avl_node* lower_bound();
      const avl_node* lower_bound() const;

      avl_node* upper_bound();
      const avl_node* upper_bound() const;

      avl_node* prev();
      const avl_node* prev() const;

      avl_node* next();
      const avl_node* next() const;

    private:
      explicit avl_node( const avl_node& that );

    public:
      K key;

      char balance;

      avl_node *father;

    }; // class avl_node

  private:
    typedef avl_node* avl_node_ptr;
    typedef avl_node const* const_avl_node_ptr;

  public:
    //*************************** avl::avl_iterator ***************************

    class avl_iterator
    {
    public:
      typedef K  value_type;
      typedef K& reference;
      typedef K* const pointer;
      typedef ptrdiff_t difference_type;
          
      typedef std::bidirectional_iterator_tag iterator_category;

    public:
      avl_iterator();
      avl_iterator( avl_node_ptr node, bool final );

      avl_iterator& operator++();
      avl_iterator operator++(int);
      avl_iterator& operator--();
      avl_iterator operator--(int);
      reference operator*() const;
      pointer   operator->() const;
      bool operator==(const avl_iterator& it) const;
      bool operator!=(const avl_iterator& it) const;

    private:
      avl_node_ptr m_current;

      bool m_is_final;

    }; // class avl_iterator

    class avl_const_iterator
    {
    public:
      typedef K  value_type;
      typedef const K& reference;
      typedef const K* const pointer;
      typedef ptrdiff_t difference_type;
          
      typedef std::bidirectional_iterator_tag iterator_category;

    public:
      avl_const_iterator();
      avl_const_iterator( const_avl_node_ptr node, bool final );

      avl_const_iterator& operator++();
      avl_const_iterator operator++(int);
      avl_const_iterator& operator--();
      avl_const_iterator operator--(int);
      reference operator*() const;
      pointer   operator->() const;
      bool operator==(const avl_const_iterator& it) const;
      bool operator!=(const avl_const_iterator& it) const;

    private:
      const_avl_node_ptr m_current;

      bool m_is_final;

    }; // class avl_const_iterator

  public:
    typedef K value_type;
    typedef K key_type;
    typedef K referent_type;
    typedef Comp key_less;
    typedef const K& const_reference;
    typedef avl_iterator iterator;
    typedef avl_const_iterator const_iterator;

  public:
    //**************************** avl_base (main) *****************************

    avl_base();
    explicit avl_base( const avl_base<K, Comp>& that );
    ~avl_base();

    void insert( const K& key );
    template<typename Iterator>
    void insert( Iterator first, Iterator last );

    void erase( const K& key );
    void clear();

    inline unsigned int size() const;
    inline bool empty() const;

    iterator begin();
    const_iterator begin() const;

    iterator end();
    const_iterator end() const;

    iterator find( const K& key );
    const_iterator find( const K& key ) const;

    iterator find_nearest_greater( const K& key );
    const_iterator find_nearest_greater( const K& key ) const;

    iterator find_nearest_lower( const K& key );
    const_iterator find_nearest_lower( const K& key ) const;

    iterator lower_bound();
    const_iterator lower_bound() const;

    iterator upper_bound();
    const_iterator upper_bound() const;

    avl_base<K, Comp>& operator=( const avl_base<K, Comp>& that );
    bool operator==( const avl_base<K, Comp>& that ) const;
    bool operator!=( const avl_base<K, Comp>& that ) const;
    bool operator<( const avl_base<K, Comp>& that ) const;
    bool operator>( const avl_base<K, Comp>& that ) const;
    bool operator<=( const avl_base<K, Comp>& that ) const;
    bool operator>=( const avl_base<K, Comp>& that ) const;

    void swap( avl_base<K, Comp>& that );

  private:
    //-------------------------------------------------------------------------
    // We need some methods to check the validity of our trees

    bool check_in_bounds( const avl_node_ptr node, const K& min, 
                          const K& max ) const;
    bool check_balance( const avl_node_ptr node ) const;
    bool correct_descendant( const avl_node_ptr node ) const;
    bool validity_check() const;

  private:
    iterator make_iterator( avl_node_ptr node ) const;
    const_iterator make_const_iterator( const_avl_node_ptr node ) const;

    //-------------------------------------------------------------------------
    // Tree management methods

    void rotate_right( avl_node_ptr& node );
    void rotate_left( avl_node_ptr& node );
    void rotate_left_right( avl_node_ptr& node );
    void rotate_right_left( avl_node_ptr& node );

    void update_balance( avl_node_ptr node, const K& key );
    void adjust_balance( avl_node_ptr& node );
    void adjust_balance_left( avl_node_ptr& node );
    void adjust_balance_right( avl_node_ptr& node );


    //-------------------------------------------------------------------------
    //    Methods for insertion
    //-------------------------------------------------------------------------


    void insert_node( const K& key );
    avl_node_ptr* find_node_reference( const K& key, 
                                       avl_node_ptr& last_imbalanced, 
                                       avl_node_ptr& node_father);


    //-------------------------------------------------------------------------
    //    Methods for deletion
    //-------------------------------------------------------------------------


    bool recursive_delete( avl_node_ptr& node, const K& key );
    bool new_balance( avl_node_ptr& node, int imbalance );
    bool recursive_delete_node( avl_node_ptr& node );
    int recursive_delete_max( avl_node_ptr& root, avl_node_ptr node );

  public:
    static key_less s_key_less;

  private:
    unsigned int m_size;

    avl_node_ptr m_tree;

  }; // class avl_base
} // namespace claw

#include <claw/impl/avl_base.tpp>

#endif // __CLAW_AVL_HPP__