CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
avl_base.hpp
Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2010 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #ifndef __CLAW_AVL_BASE_HPP__
00031 #define __CLAW_AVL_BASE_HPP__
00032 
00033 #include <iterator>
00034 #include <cstddef>
00035 
00036 #include <claw/binary_node.hpp>
00037 
00038 namespace claw
00039 {
00040   //---------------------------------------------------------------------------
00056   template < class K, class Comp = std::less<K> >
00057   class avl_base
00058   {
00059   private:
00060 
00061     //**************************** avl_node ***********************************
00062 
00066     class avl_node:
00067       public binary_node< typename claw::avl_base<K,Comp>::avl_node >
00068     {
00069     private:
00071       typedef binary_node< typename claw::avl_base<K,Comp>::avl_node > super;
00072 
00073     public:
00074       explicit avl_node( const K& k );
00075       ~avl_node();
00076 
00077       avl_node* duplicate( unsigned int& count ) const;
00078 
00079       void del_tree();
00080       unsigned int depth() const;
00081 
00082       avl_node* find( const K& k );
00083       const avl_node* find( const K& k ) const;
00084 
00085       avl_node* find_nearest_greater( const K& key );
00086       const avl_node* find_nearest_greater( const K& key ) const;
00087 
00088       avl_node* find_nearest_lower( const K& key );
00089       const avl_node* find_nearest_lower( const K& key ) const;
00090 
00091       avl_node* lower_bound();
00092       const avl_node* lower_bound() const;
00093 
00094       avl_node* upper_bound();
00095       const avl_node* upper_bound() const;
00096 
00097       avl_node* prev();
00098       const avl_node* prev() const;
00099 
00100       avl_node* next();
00101       const avl_node* next() const;
00102 
00103     private:
00104       explicit avl_node( const avl_node& that );
00105 
00106     public:
00108       K key;
00109 
00115       char balance;
00116 
00118       avl_node *father;
00119 
00120     }; // class avl_node
00121 
00122   private:
00123     typedef avl_node* avl_node_ptr;
00124     typedef avl_node const* const_avl_node_ptr;
00125 
00126   public:
00127     //*************************** avl::avl_iterator ***************************
00128 
00132     class avl_iterator
00133     {
00134     public:
00135       typedef K  value_type;
00136       typedef K& reference;
00137       typedef K* const pointer;
00138       typedef ptrdiff_t difference_type;
00139           
00140       typedef std::bidirectional_iterator_tag iterator_category;
00141 
00142     public:
00143       avl_iterator();
00144       avl_iterator( avl_node_ptr node, bool final );
00145 
00146       avl_iterator& operator++();
00147       avl_iterator operator++(int);
00148       avl_iterator& operator--();
00149       avl_iterator operator--(int);
00150       reference operator*() const;
00151       pointer   operator->() const;
00152       bool operator==(const avl_iterator& it) const;
00153       bool operator!=(const avl_iterator& it) const;
00154 
00155     private:
00157       avl_node_ptr m_current;
00158 
00160       bool m_is_final;
00161 
00162     }; // class avl_iterator
00163 
00167     class avl_const_iterator
00168     {
00169     public:
00170       typedef K  value_type;
00171       typedef const K& reference;
00172       typedef const K* const pointer;
00173       typedef ptrdiff_t difference_type;
00174           
00175       typedef std::bidirectional_iterator_tag iterator_category;
00176 
00177     public:
00178       avl_const_iterator();
00179       avl_const_iterator( const_avl_node_ptr node, bool final );
00180 
00181       avl_const_iterator& operator++();
00182       avl_const_iterator operator++(int);
00183       avl_const_iterator& operator--();
00184       avl_const_iterator operator--(int);
00185       reference operator*() const;
00186       pointer   operator->() const;
00187       bool operator==(const avl_const_iterator& it) const;
00188       bool operator!=(const avl_const_iterator& it) const;
00189 
00190     private:
00192       const_avl_node_ptr m_current;
00193 
00195       bool m_is_final;
00196 
00197     }; // class avl_const_iterator
00198 
00199   public:
00200     typedef K value_type;
00201     typedef K key_type;
00202     typedef K referent_type;
00203     typedef Comp key_less;
00204     typedef const K& const_reference;
00205     typedef avl_iterator iterator;
00206     typedef avl_const_iterator const_iterator;
00207 
00208   public:
00209     //**************************** avl_base (main) *****************************
00210 
00211     avl_base();
00212     explicit avl_base( const avl_base<K, Comp>& that );
00213     ~avl_base();
00214 
00215     void insert( const K& key );
00216     template<typename Iterator>
00217     void insert( Iterator first, Iterator last );
00218 
00219     void erase( const K& key );
00220     void clear();
00221 
00222     inline unsigned int size() const;
00223     inline bool empty() const;
00224 
00225     iterator begin();
00226     const_iterator begin() const;
00227 
00228     iterator end();
00229     const_iterator end() const;
00230 
00231     iterator find( const K& key );
00232     const_iterator find( const K& key ) const;
00233 
00234     iterator find_nearest_greater( const K& key );
00235     const_iterator find_nearest_greater( const K& key ) const;
00236 
00237     iterator find_nearest_lower( const K& key );
00238     const_iterator find_nearest_lower( const K& key ) const;
00239 
00240     iterator lower_bound();
00241     const_iterator lower_bound() const;
00242 
00243     iterator upper_bound();
00244     const_iterator upper_bound() const;
00245 
00246     avl_base<K, Comp>& operator=( const avl_base<K, Comp>& that );
00247     bool operator==( const avl_base<K, Comp>& that ) const;
00248     bool operator!=( const avl_base<K, Comp>& that ) const;
00249     bool operator<( const avl_base<K, Comp>& that ) const;
00250     bool operator>( const avl_base<K, Comp>& that ) const;
00251     bool operator<=( const avl_base<K, Comp>& that ) const;
00252     bool operator>=( const avl_base<K, Comp>& that ) const;
00253 
00254     void swap( avl_base<K, Comp>& that );
00255 
00256   private:
00257     //-------------------------------------------------------------------------
00258     // We need some methods to check the validity of our trees
00259 
00260     bool check_in_bounds( const avl_node_ptr node, const K& min, 
00261                           const K& max ) const;
00262     bool check_balance( const avl_node_ptr node ) const;
00263     bool correct_descendant( const avl_node_ptr node ) const;
00264     bool validity_check() const;
00265 
00266   private:
00267     iterator make_iterator( avl_node_ptr node ) const;
00268     const_iterator make_const_iterator( const_avl_node_ptr node ) const;
00269 
00270     //-------------------------------------------------------------------------
00271     // Tree management methods
00272 
00273     void rotate_right( avl_node_ptr& node );
00274     void rotate_left( avl_node_ptr& node );
00275     void rotate_left_right( avl_node_ptr& node );
00276     void rotate_right_left( avl_node_ptr& node );
00277 
00278     void update_balance( avl_node_ptr node, const K& key );
00279     void adjust_balance( avl_node_ptr& node );
00280     void adjust_balance_left( avl_node_ptr& node );
00281     void adjust_balance_right( avl_node_ptr& node );
00282 
00283 
00284     //-------------------------------------------------------------------------
00285     //    Methods for insertion
00286     //-------------------------------------------------------------------------
00287 
00288 
00289     void insert_node( const K& key );
00290     avl_node_ptr* find_node_reference( const K& key, 
00291                                        avl_node_ptr& last_imbalanced, 
00292                                        avl_node_ptr& node_father);
00293 
00294 
00295     //-------------------------------------------------------------------------
00296     //    Methods for deletion
00297     //-------------------------------------------------------------------------
00298 
00299 
00300     bool recursive_delete( avl_node_ptr& node, const K& key );
00301     bool new_balance( avl_node_ptr& node, int imbalance );
00302     bool recursive_delete_node( avl_node_ptr& node );
00303     int recursive_delete_max( avl_node_ptr& root, avl_node_ptr node );
00304 
00305   public:
00307     static key_less s_key_less;
00308 
00309   private:
00311     unsigned int m_size;
00312 
00314     avl_node_ptr m_tree;
00315 
00316   }; // class avl_base
00317 } // namespace claw
00318 
00319 #include <claw/impl/avl_base.tpp>
00320 
00321 #endif // __CLAW_AVL_HPP__