Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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
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 };
00121
00122 private:
00123 typedef avl_node* avl_node_ptr;
00124 typedef avl_node const* const_avl_node_ptr;
00125
00126 public:
00127
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 };
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 };
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
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
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
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
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
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 };
00317 }
00318
00319 #include <claw/impl/avl_base.tpp>
00320
00321 #endif // __CLAW_AVL_HPP__