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
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
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 };
00120
00121 private:
00122 typedef avl_node* avl_node_ptr;
00123 typedef avl_node const* const_avl_node_ptr;
00124
00125 public:
00126
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 };
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 };
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
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
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
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
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
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 };
00316 }
00317
00318 #include <claw/impl/avl_base.tpp>
00319
00320 #endif // __CLAW_AVL_HPP__