• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • Directories
  • File List
  • File Members

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-2008 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 
00035 #include <claw/binary_node.hpp>
00036 
00037 namespace claw
00038 {
00039   //---------------------------------------------------------------------------
00055   template < class K, class Comp = std::less<K> >
00056   class avl_base
00057   {
00058   private:
00059 
00060     //**************************** avl_node ***********************************
00061 
00065     class avl_node:
00066       public binary_node< typename claw::avl_base<K,Comp>::avl_node >
00067     {
00068     private:
00070       typedef binary_node< typename claw::avl_base<K,Comp>::avl_node > super;
00071 
00072     public:
00073       explicit avl_node( const K& k );
00074       ~avl_node();
00075 
00076       avl_node* duplicate( unsigned int& count ) const;
00077 
00078       void del_tree();
00079       unsigned int depth() const;
00080 
00081       avl_node* find( const K& k );
00082       const avl_node* find( const K& k ) const;
00083 
00084       avl_node* find_nearest_greater( const K& key );
00085       const avl_node* find_nearest_greater( const K& key ) const;
00086 
00087       avl_node* find_nearest_lower( const K& key );
00088       const avl_node* find_nearest_lower( const K& key ) const;
00089 
00090       avl_node* lower_bound();
00091       const avl_node* lower_bound() const;
00092 
00093       avl_node* upper_bound();
00094       const avl_node* upper_bound() const;
00095 
00096       avl_node* prev();
00097       const avl_node* prev() const;
00098 
00099       avl_node* next();
00100       const avl_node* next() const;
00101 
00102     private:
00103       explicit avl_node( const avl_node& that );
00104 
00105     public:
00107       K key;
00108 
00114       char balance;
00115 
00117       avl_node *father;
00118 
00119     }; // class avl_node
00120 
00121   private:
00122     typedef avl_node* avl_node_ptr;
00123     typedef avl_node const* const_avl_node_ptr;
00124 
00125   public:
00126     //*************************** avl::avl_iterator ***************************
00127 
00131     class avl_iterator
00132     {
00133     public:
00134       typedef K  value_type;
00135       typedef K& reference;
00136       typedef K* const pointer;
00137       typedef ptrdiff_t difference_type;
00138           
00139       typedef std::bidirectional_iterator_tag iterator_category;
00140 
00141     public:
00142       avl_iterator();
00143       avl_iterator( avl_node_ptr node, bool final );
00144 
00145       avl_iterator& operator++();
00146       avl_iterator operator++(int);
00147       avl_iterator& operator--();
00148       avl_iterator operator--(int);
00149       reference operator*() const;
00150       pointer   operator->() const;
00151       bool operator==(const avl_iterator& it) const;
00152       bool operator!=(const avl_iterator& it) const;
00153 
00154     private:
00156       avl_node_ptr m_current;
00157 
00159       bool m_is_final;
00160 
00161     }; // class avl_iterator
00162 
00166     class avl_const_iterator
00167     {
00168     public:
00169       typedef K  value_type;
00170       typedef const K& reference;
00171       typedef const K* const pointer;
00172       typedef ptrdiff_t difference_type;
00173           
00174       typedef std::bidirectional_iterator_tag iterator_category;
00175 
00176     public:
00177       avl_const_iterator();
00178       avl_const_iterator( const_avl_node_ptr node, bool final );
00179 
00180       avl_const_iterator& operator++();
00181       avl_const_iterator operator++(int);
00182       avl_const_iterator& operator--();
00183       avl_const_iterator operator--(int);
00184       reference operator*() const;
00185       pointer   operator->() const;
00186       bool operator==(const avl_const_iterator& it) const;
00187       bool operator!=(const avl_const_iterator& it) const;
00188 
00189     private:
00191       const_avl_node_ptr m_current;
00192 
00194       bool m_is_final;
00195 
00196     }; // class avl_const_iterator
00197 
00198   public:
00199     typedef K value_type;
00200     typedef K key_type;
00201     typedef K referent_type;
00202     typedef Comp key_less;
00203     typedef const K& const_reference;
00204     typedef avl_iterator iterator;
00205     typedef avl_const_iterator const_iterator;
00206 
00207   public:
00208     //**************************** avl_base (main) *****************************
00209 
00210     avl_base();
00211     explicit avl_base( const avl_base<K, Comp>& that );
00212     ~avl_base();
00213 
00214     void insert( const K& key );
00215     template<typename Iterator>
00216     void insert( Iterator first, Iterator last );
00217 
00218     void erase( const K& key );
00219     void clear();
00220 
00221     inline unsigned int size() const;
00222     inline bool empty() const;
00223 
00224     iterator begin();
00225     const_iterator begin() const;
00226 
00227     iterator end();
00228     const_iterator end() const;
00229 
00230     iterator find( const K& key );
00231     const_iterator find( const K& key ) const;
00232 
00233     iterator find_nearest_greater( const K& key );
00234     const_iterator find_nearest_greater( const K& key ) const;
00235 
00236     iterator find_nearest_lower( const K& key );
00237     const_iterator find_nearest_lower( const K& key ) const;
00238 
00239     iterator lower_bound();
00240     const_iterator lower_bound() const;
00241 
00242     iterator upper_bound();
00243     const_iterator upper_bound() const;
00244 
00245     avl_base<K, Comp>& operator=( const avl_base<K, Comp>& that );
00246     bool operator==( const avl_base<K, Comp>& that ) const;
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 
00253     void swap( avl_base<K, Comp>& that );
00254 
00255   private:
00256     //-------------------------------------------------------------------------
00257     // We need some methods to check the validity of our trees
00258 
00259     bool check_in_bounds( const avl_node_ptr node, const K& min, 
00260                           const K& max ) const;
00261     bool check_balance( const avl_node_ptr node ) const;
00262     bool correct_descendant( const avl_node_ptr node ) const;
00263     bool validity_check() const;
00264 
00265   private:
00266     iterator make_iterator( avl_node_ptr node ) const;
00267     const_iterator make_const_iterator( const_avl_node_ptr node ) const;
00268 
00269     //-------------------------------------------------------------------------
00270     // Tree management methods
00271 
00272     void rotate_right( avl_node_ptr& node );
00273     void rotate_left( avl_node_ptr& node );
00274     void rotate_left_right( avl_node_ptr& node );
00275     void rotate_right_left( avl_node_ptr& node );
00276 
00277     void update_balance( avl_node_ptr node, const K& key );
00278     void adjust_balance( avl_node_ptr& node );
00279     void adjust_balance_left( avl_node_ptr& node );
00280     void adjust_balance_right( avl_node_ptr& node );
00281 
00282 
00283     //-------------------------------------------------------------------------
00284     //    Methods for insertion
00285     //-------------------------------------------------------------------------
00286 
00287 
00288     void insert_node( const K& key );
00289     avl_node_ptr* find_node_reference( const K& key, 
00290                                        avl_node_ptr& last_imbalanced, 
00291                                        avl_node_ptr& node_father);
00292 
00293 
00294     //-------------------------------------------------------------------------
00295     //    Methods for deletion
00296     //-------------------------------------------------------------------------
00297 
00298 
00299     bool recursive_delete( avl_node_ptr& node, const K& key );
00300     bool new_balance( avl_node_ptr& node, int imbalance );
00301     bool recursive_delete_node( avl_node_ptr& node );
00302     int recursive_delete_max( avl_node_ptr& root, avl_node_ptr node );
00303 
00304   public:
00306     static key_less s_key_less;
00307 
00308   private:
00310     unsigned int m_size;
00311 
00313     avl_node_ptr m_tree;
00314 
00315   }; // class avl_base
00316 } // namespace claw
00317 
00318 #include <claw/impl/avl_base.tpp>
00319 
00320 #endif // __CLAW_AVL_HPP__

Generated on Sat Sep 18 2010 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.7.1