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_HPP__
00031 #define __CLAW_AVL_HPP__
00032
00033 #include <functional>
00034 #include <stack>
00035 #include <iostream>
00036 #include <iterator>
00037
00038 #include <claw/binary_node.hpp>
00039
00040 namespace claw
00041 {
00042
00043
00059 template <class K, class Comp = std::less<K> > class avl
00060 {
00061 private:
00062
00063
00064
00068 class avl_node : public binary_node< typename claw::avl<K,Comp>::avl_node >
00069 {
00070 private:
00071 typedef binary_node< typename claw::avl<K,Comp>::avl_node > super;
00072
00073 public:
00075 K key;
00081 char balance;
00083 avl_node *father;
00084
00085 explicit avl_node( const K& k );
00086 ~avl_node();
00087
00088 avl_node* duplicate( unsigned int& count ) const;
00089
00090 void del_tree();
00091 unsigned int depth() const;
00092
00093 private:
00094 explicit avl_node( const avl_node& that );
00095
00096 };
00097
00098 private:
00099 typedef avl_node* avl_node_ptr;
00100 typedef avl_node const* const_avl_node_ptr;
00101
00102
00103
00107 class avl_iterator
00108 {
00109 public:
00110 typedef const K value_type;
00111 typedef const K& reference;
00112 typedef const K* const pointer;
00113 typedef ptrdiff_t difference_type;
00114
00115 typedef std::bidirectional_iterator_tag iterator_category;
00116
00117 public:
00118
00119 avl_iterator();
00120 avl_iterator( const_avl_node_ptr node, bool final );
00121
00122 avl_iterator& operator++();
00123 avl_iterator operator++(int);
00124 avl_iterator& operator--();
00125 avl_iterator operator--(int);
00126 reference operator*() const;
00127 pointer operator->() const;
00128 bool operator==(const avl_iterator& it) const;
00129 bool operator!=(const avl_iterator& it) const;
00130
00131 private:
00133 const_avl_node_ptr m_current;
00135 bool m_is_final;
00136 };
00137
00138 public:
00139 typedef const K value_type;
00140 typedef K key_type;
00141 typedef K referent_type;
00142 typedef Comp key_less;
00143 typedef const K& const_reference;
00144 typedef avl_iterator const_iterator;
00145
00146 public:
00147
00148
00149 avl();
00150 explicit avl( const avl<K, Comp>& that );
00151 ~avl();
00152
00153 void insert( const K& key );
00154 template<typename Iterator>
00155 void insert( Iterator first, Iterator last );
00156
00157 void erase( const K& key );
00158 void clear();
00159
00160 inline unsigned int size() const;
00161 inline bool empty() const;
00162
00163 const_iterator begin() const;
00164 const_iterator end() const;
00165 const_iterator find( const K& key ) const;
00166 const_iterator find_nearest_greater( const K& key ) const;
00167 const_iterator find_nearest_lower( const K& key ) const;
00168 const_iterator lower_bound() const;
00169 const_iterator upper_bound() const;
00170
00171 avl<K, Comp>& operator=( const avl<K, Comp>& that );
00172
00173 private:
00174
00175
00176
00177 bool check_in_bounds( const avl_node_ptr node, const K& min,
00178 const K& max ) const;
00179 bool check_balance( const avl_node_ptr node ) const;
00180 bool correct_descendant( const avl_node_ptr node ) const;
00181 bool validity_check() const;
00182
00183 private:
00184
00185
00186
00187 void rotate_right( avl_node_ptr& node );
00188 void rotate_left( avl_node_ptr& node );
00189 void rotate_left_right( avl_node_ptr& node );
00190 void rotate_right_left( avl_node_ptr& node );
00191
00192 void update_balance( avl_node_ptr node, const K& key );
00193 void adjust_balance( avl_node_ptr& node );
00194 void adjust_balance_left( avl_node_ptr& node );
00195 void adjust_balance_right( avl_node_ptr& node );
00196
00197
00198
00199
00200
00201
00202
00203 void insert_node( const K& key );
00204 avl_node_ptr* find_node_reference( const K& key,
00205 avl_node_ptr& last_imbalanced,
00206 avl_node_ptr& node_father);
00207
00208
00209
00210
00211
00212
00213
00214 bool recursive_delete( avl_node_ptr& node, const K& key );
00215 bool new_balance( avl_node_ptr& node, int imbalance );
00216 bool recursive_delete_node( avl_node_ptr& node );
00217 int recursive_delete_max( avl_node_ptr& root, avl_node_ptr node );
00218
00219 protected:
00221 static key_less s_key_less;
00222
00223 private:
00225 unsigned int m_size;
00226
00228 avl_node_ptr m_tree;
00229
00230 };
00231
00232 }
00233
00234 #include <claw/impl/avl.tpp>
00235
00236 #endif // __CLAW_AVL_HPP__