Claw
1.7.3
|
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-2011 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@gamned.org 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__