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 #include <cassert>
00031
00032
00033
00034
00039 template<class K, class Comp>
00040 claw::avl_base<K, Comp>::avl_node::avl_node( const K& k )
00041 : super(), key(k), balance(0), father(NULL)
00042 {
00043 assert(!super::left);
00044 assert(!super::right);
00045 }
00046
00047
00051 template<class K, class Comp>
00052 claw::avl_base<K, Comp>::avl_node::~avl_node()
00053 {
00054
00055 }
00056
00057
00063 template<class K, class Comp>
00064 typename claw::avl_base<K, Comp>::avl_node*
00065 claw::avl_base<K, Comp>::avl_node::duplicate( unsigned int& count ) const
00066 {
00067 avl_node* node_copy = new avl_node(key);
00068 ++count;
00069 node_copy->balance = balance;
00070 node_copy->father = NULL;
00071
00072 if (super::left)
00073 {
00074 node_copy->left = super::left->duplicate(count);
00075 node_copy->left->father = node_copy;
00076 }
00077 else
00078 node_copy->left = NULL;
00079
00080 if (super::right)
00081 {
00082 node_copy->right = super::right->duplicate(count);
00083 node_copy->right->father = node_copy;
00084 }
00085 else
00086 node_copy->right = NULL;
00087
00088 return node_copy;
00089 }
00090
00091
00096 template<class K, class Comp>
00097 void claw::avl_base<K, Comp>::avl_node::del_tree()
00098 {
00099 if (super::left)
00100 {
00101 delete super::left;
00102 super::left = NULL;
00103 }
00104 if (super::right)
00105 {
00106 delete super::right;
00107 super::right = NULL;
00108 }
00109 assert( !super::left );
00110 assert( !super::right );
00111 }
00112
00113
00119 template<class K, class Comp>
00120 unsigned int claw::avl_base<K, Comp>::avl_node::depth() const
00121 {
00122 unsigned int pl=0, pr=0;
00123
00124 if (super::left) pl = super::left->depth();
00125 if (super::right) pr = super::right->depth();
00126
00127 if (pl > pr)
00128 return 1 + pl;
00129 else
00130 return 1 + pr;
00131 }
00132
00133
00138 template<class K, class Comp>
00139 typename claw::avl_base<K,Comp>::avl_node*
00140 claw::avl_base<K,Comp>::avl_node::find( const K& key )
00141 {
00142 bool ok = false;
00143 avl_node* node = this;
00144
00145 while (node && !ok)
00146 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00147 node = node->left;
00148 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00149 node = node->right;
00150 else
00151 ok = true;
00152
00153 return node;
00154 }
00155
00156
00161 template<class K, class Comp>
00162 const typename claw::avl_base<K,Comp>::avl_node*
00163 claw::avl_base<K,Comp>::avl_node::find( const K& key ) const
00164 {
00165 bool ok = false;
00166 const avl_node* node = this;
00167
00168 while (node && !ok)
00169 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00170 node = node->left;
00171 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00172 node = node->right;
00173 else
00174 ok = true;
00175
00176 return node;
00177 }
00178
00179
00185 template<class K, class Comp>
00186 typename claw::avl_base<K,Comp>::avl_node*
00187 claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key )
00188 {
00189 bool ok = false;
00190 avl_node* node = this;
00191 avl_node* prev_node = NULL;
00192
00193 while (node && !ok)
00194 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00195 {
00196 prev_node = node;
00197 node = node->left;
00198 }
00199 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00200 {
00201 prev_node = node;
00202 node = node->right;
00203 }
00204 else
00205 ok = true;
00206
00207 if (ok)
00208 return node->next();
00209 else if (prev_node)
00210 {
00211 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
00212 return prev_node->next();
00213 else
00214 return prev_node;
00215 }
00216 else
00217 return node;
00218 }
00219
00220
00226 template<class K, class Comp>
00227 const typename claw::avl_base<K,Comp>::avl_node*
00228 claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key ) const
00229 {
00230 bool ok = false;
00231 const avl_node* node = this;
00232 const avl_node* prev_node = NULL;
00233
00234 while (node && !ok)
00235 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00236 {
00237 prev_node = node;
00238 node = node->left;
00239 }
00240 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00241 {
00242 prev_node = node;
00243 node = node->right;
00244 }
00245 else
00246 ok = true;
00247
00248 if (ok)
00249 return node->next();
00250 else if (prev_node)
00251 {
00252 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
00253 return prev_node->next();
00254 else
00255 return prev_node;
00256 }
00257 else
00258 return node;
00259 }
00260
00261
00267 template<class K, class Comp>
00268 typename claw::avl_base<K,Comp>::avl_node*
00269 claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key )
00270 {
00271 bool ok = false;
00272 avl_node* node = this;
00273 avl_node* prev_node = NULL;
00274
00275 while (node && !ok)
00276 if ( s_key_less(key, node->key) )
00277 {
00278 prev_node = node;
00279 node = node->left;
00280 }
00281 else if ( s_key_less(node->key, key) )
00282 {
00283 prev_node = node;
00284 node = node->right;
00285 }
00286 else
00287 ok = true;
00288
00289 if (ok)
00290 return node->prev();
00291 else if (prev_node)
00292 {
00293 if ( s_key_less(key, prev_node->key) )
00294 return prev_node;
00295 else
00296 return prev_node->prev();
00297 }
00298 else
00299 return node;
00300 }
00301
00302
00308 template<class K, class Comp>
00309 const typename claw::avl_base<K,Comp>::avl_node*
00310 claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key ) const
00311 {
00312 bool ok = false;
00313 const avl_node* node = this;
00314 const avl_node* prev_node = NULL;
00315
00316 while (node && !ok)
00317 if ( s_key_less(key, node->key) )
00318 {
00319 prev_node = node;
00320 node = node->left;
00321 }
00322 else if ( s_key_less(node->key, key) )
00323 {
00324 prev_node = node;
00325 node = node->right;
00326 }
00327 else
00328 ok = true;
00329
00330 if (ok)
00331 return node->prev();
00332 else if (prev_node)
00333 {
00334 if ( s_key_less(key, prev_node->key) )
00335 return prev_node;
00336 else
00337 return prev_node->prev();
00338 }
00339 else
00340 return node;
00341 }
00342
00343
00347 template<class K, class Comp>
00348 typename claw::avl_base<K,Comp>::avl_node*
00349 claw::avl_base<K,Comp>::avl_node::lower_bound()
00350 {
00351 avl_node* node = this;
00352
00353 if (node)
00354 while (node->left)
00355 node = node->left;
00356
00357 return node;
00358 }
00359
00360
00364 template<class K, class Comp>
00365 const typename claw::avl_base<K,Comp>::avl_node*
00366 claw::avl_base<K,Comp>::avl_node::lower_bound() const
00367 {
00368 const avl_node* node = this;
00369
00370 if (node)
00371 while (node->left)
00372 node = node->left;
00373
00374 return node;
00375 }
00376
00377
00381 template<class K, class Comp>
00382 typename claw::avl_base<K,Comp>::avl_node*
00383 claw::avl_base<K,Comp>::avl_node::upper_bound()
00384 {
00385 avl_node* node = this;
00386
00387 if (node)
00388 while (node->right)
00389 node = node->right;
00390
00391 return node;
00392 }
00393
00394
00398 template<class K, class Comp>
00399 const typename claw::avl_base<K,Comp>::avl_node*
00400 claw::avl_base<K,Comp>::avl_node::upper_bound() const
00401 {
00402 const avl_node* node = this;
00403
00404 if (node)
00405 while (node->right)
00406 node = node->right;
00407
00408 return node;
00409 }
00410
00411
00415 template<class K, class Comp>
00416 typename claw::avl_base<K,Comp>::avl_node*
00417 claw::avl_base<K,Comp>::avl_node::next()
00418 {
00419 avl_node* result = this;
00420
00421
00422 if (result->right != NULL)
00423 {
00424 result = result->right;
00425
00426 while (result->left != NULL)
00427 result = result->left;
00428 }
00429 else
00430 {
00431 bool done = false;
00432 avl_node* previous_node = this;
00433
00434
00435 while (result->father && !done)
00436 {
00437 if (result->father->left == result)
00438 done = true;
00439
00440 result = result->father;
00441 }
00442
00443
00444 if (!done)
00445 result = previous_node;
00446 }
00447
00448 return result;
00449 }
00450
00451
00455 template<class K, class Comp>
00456 const typename claw::avl_base<K,Comp>::avl_node*
00457 claw::avl_base<K,Comp>::avl_node::next() const
00458 {
00459 const avl_node* result = this;
00460
00461
00462 if (result->right != NULL)
00463 {
00464 result = result->right;
00465
00466 while (result->left != NULL)
00467 result = result->left;
00468 }
00469 else
00470 {
00471 bool done = false;
00472 const avl_node* previous_node = this;
00473
00474
00475 while (result->father && !done)
00476 {
00477 if (result->father->left == result)
00478 done = true;
00479
00480 result = result->father;
00481 }
00482
00483
00484 if (!done)
00485 result = previous_node;
00486 }
00487
00488 return result;
00489 }
00490
00491
00495 template<class K, class Comp>
00496 typename claw::avl_base<K,Comp>::avl_node*
00497 claw::avl_base<K,Comp>::avl_node::prev()
00498 {
00499 avl_node* result = this;
00500
00501
00502 if (result->left != NULL)
00503 {
00504 result = result->left;
00505
00506 while (result->right != NULL)
00507 result = result->right;
00508 }
00509 else
00510 {
00511 bool done = false;
00512
00513
00514 while (result->father && !done)
00515 {
00516 if (result->father->right == result)
00517 done = true;
00518
00519 result = result->father;
00520 }
00521 }
00522
00523 return result;
00524 }
00525
00526
00530 template<class K, class Comp>
00531 const typename claw::avl_base<K,Comp>::avl_node*
00532 claw::avl_base<K,Comp>::avl_node::prev() const
00533 {
00534 const avl_node* result = this;
00535
00536
00537 if (result->left != NULL)
00538 {
00539 result = result->left;
00540
00541 while (result->right != NULL)
00542 result = result->right;
00543 }
00544 else
00545 {
00546 bool done = false;
00547
00548
00549 while (result->father && !done)
00550 {
00551 if (result->father->right == result)
00552 done = true;
00553
00554 result = result->father;
00555 }
00556 }
00557
00558 return result;
00559 }
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00575 template<class K, class Comp>
00576 claw::avl_base<K, Comp>::avl_node::avl_node( const avl_node& that )
00577 : super(that), key(that.key), balance(that.balance), father(NULL)
00578 {
00579 assert(0);
00580 }
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00594 template<class K, class Comp>
00595 claw::avl_base<K,Comp>::avl_iterator::avl_iterator()
00596 : m_current(NULL), m_is_final(true)
00597 {
00598
00599 }
00600
00601
00605 template<class K, class Comp>
00606 claw::avl_base<K,Comp>::avl_iterator::avl_iterator
00607 ( avl_node_ptr node, bool final )
00608 : m_current(node), m_is_final(final)
00609 {
00610
00611 }
00612
00613
00618 template<class K, class Comp>
00619 typename claw::avl_base<K,Comp>::avl_iterator&
00620 claw::avl_base<K,Comp>::avl_iterator::operator++()
00621 {
00622 assert(!m_is_final);
00623 assert(m_current);
00624
00625 avl_node* p = m_current->next();
00626
00627 if ( m_current == p )
00628 m_is_final = true;
00629 else
00630 m_current = p;
00631
00632 return *this;
00633 }
00634
00635
00639 template<class K, class Comp>
00640 typename claw::avl_base<K,Comp>::avl_iterator
00641 claw::avl_base<K,Comp>::avl_iterator::operator++(int)
00642 {
00643 avl_iterator it = *this;
00644 ++(*this);
00645 return it;
00646 }
00647
00648
00653 template<class K, class Comp>
00654 typename claw::avl_base<K,Comp>::avl_iterator&
00655 claw::avl_base<K,Comp>::avl_iterator::operator--()
00656 {
00657 assert(m_current);
00658
00659 if (m_is_final)
00660 m_is_final = !m_is_final;
00661 else
00662 m_current = m_current->prev();
00663
00664 assert(m_current != NULL);
00665
00666 return *this;
00667 }
00668
00669
00673 template<class K, class Comp>
00674 typename claw::avl_base<K,Comp>::avl_iterator
00675 claw::avl_base<K,Comp>::avl_iterator::operator--(int)
00676 {
00677 avl_iterator it = *this;
00678 --(*this);
00679 return it;
00680 }
00681
00682
00686 template<class K, class Comp>
00687 typename claw::avl_base<K,Comp>::avl_iterator::reference
00688 claw::avl_base<K,Comp>::avl_iterator::operator*() const
00689 {
00690 return m_current->key;
00691 }
00692
00693
00697 template<class K, class Comp>
00698 typename claw::avl_base<K,Comp>::avl_iterator::pointer
00699 claw::avl_base<K,Comp>::avl_iterator::operator->() const
00700 {
00701 return &m_current->key;
00702 }
00703
00704
00709 template<class K, class Comp>
00710 bool
00711 claw::avl_base<K,Comp>::avl_iterator::operator==(const avl_iterator& it) const
00712 {
00713 return (m_current == it.m_current) && (m_is_final == it.m_is_final);
00714 }
00715
00716
00721 template<class K, class Comp>
00722 bool
00723 claw::avl_base<K,Comp>::avl_iterator::operator!=(const avl_iterator& it) const
00724 {
00725 return !( *this == it );
00726 }
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00740 template<class K, class Comp>
00741 claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator()
00742 : m_current(NULL), m_is_final(true)
00743 {
00744
00745 }
00746
00747
00751 template<class K, class Comp>
00752 claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator
00753 ( const_avl_node_ptr node, bool final )
00754 : m_current(node), m_is_final(final)
00755 {
00756
00757 }
00758
00759
00764 template<class K, class Comp>
00765 typename claw::avl_base<K,Comp>::avl_const_iterator&
00766 claw::avl_base<K,Comp>::avl_const_iterator::operator++()
00767 {
00768 assert(!m_is_final);
00769 assert(m_current);
00770
00771 const_avl_node_ptr p = m_current->next();
00772
00773 if ( m_current == p )
00774 m_is_final = true;
00775 else
00776 m_current = p;
00777
00778 return *this;
00779 }
00780
00781
00785 template<class K, class Comp>
00786 typename claw::avl_base<K,Comp>::avl_const_iterator
00787 claw::avl_base<K,Comp>::avl_const_iterator::operator++(int)
00788 {
00789 avl_const_iterator it = *this;
00790 ++(*this);
00791 return it;
00792 }
00793
00794
00799 template<class K, class Comp>
00800 typename claw::avl_base<K,Comp>::avl_const_iterator&
00801 claw::avl_base<K,Comp>::avl_const_iterator::operator--()
00802 {
00803 assert(m_current);
00804
00805 if (m_is_final)
00806 m_is_final = !m_is_final;
00807 else
00808 m_current = m_current->prev();
00809
00810 assert(m_current != NULL);
00811
00812 return *this;
00813 }
00814
00815
00819 template<class K, class Comp>
00820 typename claw::avl_base<K,Comp>::avl_const_iterator
00821 claw::avl_base<K,Comp>::avl_const_iterator::operator--(int)
00822 {
00823 avl_const_iterator it = *this;
00824 --(*this);
00825 return it;
00826 }
00827
00828
00832 template<class K, class Comp>
00833 typename claw::avl_base<K,Comp>::avl_const_iterator::reference
00834 claw::avl_base<K,Comp>::avl_const_iterator::operator*() const
00835 {
00836 return m_current->key;
00837 }
00838
00839
00843 template<class K, class Comp>
00844 typename claw::avl_base<K,Comp>::avl_const_iterator::pointer
00845 claw::avl_base<K,Comp>::avl_const_iterator::operator->() const
00846 {
00847 return &m_current->key;
00848 }
00849
00850
00855 template<class K, class Comp>
00856 bool claw::avl_base<K,Comp>::avl_const_iterator::operator==
00857 (const avl_const_iterator& it) const
00858 {
00859 return (m_current == it.m_current) && (m_is_final == it.m_is_final);
00860 }
00861
00862
00867 template<class K, class Comp>
00868 bool claw::avl_base<K,Comp>::avl_const_iterator::operator!=
00869 (const avl_const_iterator& it) const
00870 {
00871 return !( *this == it );
00872 }
00873
00874
00875
00876
00877
00878
00879
00880
00881
00882 template<class K, class Comp>
00883 typename claw::avl_base<K,Comp>::key_less claw::avl_base<K,Comp>::s_key_less;
00884
00885
00890 template<class K, class Comp>
00891 claw::avl_base<K,Comp>::avl_base()
00892 : m_size(0), m_tree(NULL)
00893 {
00894
00895 }
00896
00897
00902 template<class K, class Comp>
00903 claw::avl_base<K,Comp>::avl_base( const avl_base<K, Comp>& that )
00904 {
00905 m_size = 0;
00906
00907 if (that.m_tree)
00908 m_tree = that.m_tree->duplicate( m_size );
00909 else
00910 m_tree = NULL;
00911 }
00912
00913
00917 template<class K, class Comp>
00918 claw::avl_base<K,Comp>::~avl_base()
00919 {
00920 if (m_tree)
00921 {
00922 m_tree->del_tree();
00923 delete m_tree;
00924 }
00925 }
00926
00927
00933 template<class K, class Comp>
00934 void claw::avl_base<K,Comp>::insert( const K& key )
00935 {
00936 assert( validity_check() );
00937
00938 if ( m_tree == NULL )
00939 {
00940 m_tree = new avl_node(key);
00941 m_size = 1;
00942 }
00943 else
00944 insert_node(key);
00945
00946 assert( validity_check() );
00947 }
00948
00949
00957 template<class K, class Comp>
00958 template<typename Iterator>
00959 void claw::avl_base<K,Comp>::insert( Iterator first, Iterator last )
00960 {
00961 for ( ; first!=last; ++first )
00962 insert( *first );
00963 }
00964
00965
00971 template<class K, class Comp>
00972 void claw::avl_base<K,Comp>::erase( const K& key )
00973 {
00974 assert( validity_check() );
00975
00976 if (m_tree != NULL)
00977 recursive_delete( m_tree, key );
00978
00979 assert( validity_check() );
00980 }
00981
00982
00987 template<class K, class Comp>
00988 void claw::avl_base<K,Comp>::clear()
00989 {
00990 if (m_tree != NULL)
00991 {
00992 m_tree->del_tree();
00993 delete m_tree;
00994
00995 m_tree = NULL;
00996 m_size = 0;
00997 }
00998 }
00999
01000
01005 template<class K, class Comp>
01006 inline unsigned int claw::avl_base<K,Comp>::size() const
01007 {
01008 return m_size;
01009 }
01010
01011
01016 template<class K, class Comp>
01017 inline bool claw::avl_base<K,Comp>::empty() const
01018 {
01019 return m_size == 0;
01020 }
01021
01022
01026 template<class K, class Comp>
01027 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::begin()
01028 {
01029 if (m_tree == NULL)
01030 return iterator(NULL, true);
01031 else
01032 return lower_bound();
01033 }
01034
01035
01039 template<class K, class Comp>
01040 typename claw::avl_base<K,Comp>::const_iterator
01041 claw::avl_base<K,Comp>::begin() const
01042 {
01043 if (m_tree == NULL)
01044 return const_iterator(NULL, true);
01045 else
01046 return lower_bound();
01047 }
01048
01049
01053 template<class K, class Comp>
01054 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::end()
01055 {
01056 if (m_tree == NULL)
01057 return iterator(NULL, true);
01058 else
01059 return iterator(m_tree->upper_bound(), true);
01060 }
01061
01062
01066 template<class K, class Comp>
01067 typename claw::avl_base<K,Comp>::const_iterator
01068 claw::avl_base<K,Comp>::end() const
01069 {
01070 if (m_tree == NULL)
01071 return const_iterator(NULL, true);
01072 else
01073 return const_iterator(m_tree->upper_bound(), true);
01074 }
01075
01076
01081 template<class K, class Comp>
01082 typename claw::avl_base<K,Comp>::iterator
01083 claw::avl_base<K,Comp>::find( const K& key )
01084 {
01085 return make_iterator( m_tree->find(key) );
01086 }
01087
01088
01093 template<class K, class Comp>
01094 typename claw::avl_base<K,Comp>::const_iterator
01095 claw::avl_base<K,Comp>::find( const K& key ) const
01096 {
01097 return make_const_iterator( m_tree->find(key) );
01098 }
01099
01100
01106 template<class K, class Comp>
01107 typename claw::avl_base<K,Comp>::iterator
01108 claw::avl_base<K,Comp>::find_nearest_greater( const K& key )
01109 {
01110 return make_iterator( m_tree->find_nearest_greater(key) );
01111 }
01112
01113
01119 template<class K, class Comp>
01120 typename claw::avl_base<K,Comp>::const_iterator
01121 claw::avl_base<K,Comp>::find_nearest_greater( const K& key ) const
01122 {
01123 return make_const_iterator( m_tree->find_nearest_greater(key) );
01124 }
01125
01126
01132 template<class K, class Comp>
01133 typename claw::avl_base<K,Comp>::iterator
01134 claw::avl_base<K,Comp>::find_nearest_lower( const K& key )
01135 {
01136 return make_iterator( m_tree->find_nearest_lower(key) );
01137 }
01138
01139
01145 template<class K, class Comp>
01146 typename claw::avl_base<K,Comp>::const_iterator
01147 claw::avl_base<K,Comp>::find_nearest_lower( const K& key ) const
01148 {
01149 return make_const_iterator( m_tree->find_nearest_lower(key) );
01150 }
01151
01152
01156 template<class K, class Comp>
01157 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::lower_bound()
01158 {
01159 return make_iterator( m_tree->lower_bound() );
01160 }
01161
01162
01166 template<class K, class Comp>
01167 typename claw::avl_base<K,Comp>::const_iterator
01168 claw::avl_base<K,Comp>::lower_bound() const
01169 {
01170 return make_const_iterator( m_tree->lower_bound() );
01171 }
01172
01173
01177 template<class K, class Comp>
01178 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::upper_bound()
01179 {
01180 return make_iterator( m_tree->upper_bound() );
01181 }
01182
01183
01187 template<class K, class Comp>
01188 typename claw::avl_base<K,Comp>::const_iterator
01189 claw::avl_base<K,Comp>::upper_bound() const
01190 {
01191 return make_const_iterator( m_tree->upper_bound() );
01192 }
01193
01194
01199 template<class K, class Comp>
01200 claw::avl_base<K, Comp>&
01201 claw::avl_base<K, Comp>::operator=( const avl_base<K, Comp>& that )
01202 {
01203 if (this != &that)
01204 {
01205 if (m_tree)
01206 {
01207 m_tree->del_tree();
01208 delete m_tree;
01209 }
01210
01211 m_size = 0;
01212
01213 if (that.m_tree)
01214 m_tree = that.m_tree->duplicate( m_size );
01215 else
01216 m_tree = NULL;
01217 }
01218
01219 return *this;
01220 }
01221
01222
01227 template<class K, class Comp>
01228 bool claw::avl_base<K, Comp>::operator==( const avl_base<K, Comp>& that ) const
01229 {
01230 if (m_size != that.m_size)
01231 return false;
01232 else
01233 return std::equal( begin(), end(), that.begin(), s_key_less );
01234 }
01235
01236
01241 template<class K, class Comp>
01242 bool claw::avl_base<K, Comp>::operator!=( const avl_base<K, Comp>& that ) const
01243 {
01244 return !( *this == that );
01245 }
01246
01247
01252 template<class K, class Comp>
01253 bool claw::avl_base<K, Comp>::operator<( const avl_base<K, Comp>& that ) const
01254 {
01255 return std::lexicographical_compare
01256 ( begin(), end(), that.begin(), that.end(), s_key_less );
01257 }
01258
01259
01264 template<class K, class Comp>
01265 bool claw::avl_base<K, Comp>::operator>( const avl_base<K, Comp>& that ) const
01266 {
01267 return that < *this;
01268 }
01269
01270
01275 template<class K, class Comp>
01276 bool claw::avl_base<K, Comp>::operator<=( const avl_base<K, Comp>& that ) const
01277 {
01278 return !( that < *this );
01279 }
01280
01281
01286 template<class K, class Comp>
01287 bool claw::avl_base<K, Comp>::operator>=( const avl_base<K, Comp>& that ) const
01288 {
01289 return !( *this < that );
01290 }
01291
01292
01297 template<class K, class Comp>
01298 void claw::avl_base<K, Comp>::swap( avl_base<K, Comp>& that )
01299 {
01300 std::swap(m_size, that.m_size);
01301 std::swap(m_tree, that.m_tree);
01302 }
01303
01304
01305
01306
01307
01308
01309
01318 template<class K, class Comp>
01319 bool claw::avl_base<K,Comp>::check_in_bounds
01320 ( const avl_node_ptr node, const K& min, const K& max ) const
01321 {
01322 if (node == NULL)
01323 return true;
01324 else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) )
01325 return (node->left == NULL)
01326 && check_in_bounds( node->right, node->key, max );
01327 else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) )
01328 return (node->right == NULL)
01329 && check_in_bounds( node->left, min, node->key );
01330 else
01331 return s_key_less(node->key, max) && s_key_less(min, node->key)
01332 && check_in_bounds( node->left, min, node->key )
01333 && check_in_bounds( node->right, node->key, max );
01334 }
01335
01336
01345 template<class K, class Comp>
01346 bool claw::avl_base<K,Comp>::check_balance( const avl_node_ptr node ) const
01347 {
01348 int pl=0, pr=0;
01349
01350 if (node == NULL)
01351 return true;
01352 else
01353 {
01354 if (node->left) pl = node->left->depth();
01355 if (node->right) pr = node->right->depth();
01356
01357 return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
01358 && check_balance(node->left) && check_balance(node->right);
01359 }
01360 }
01361
01362
01369 template<class K, class Comp>
01370 bool claw::avl_base<K,Comp>::correct_descendant( const avl_node_ptr node ) const
01371 {
01372 bool valid = true;
01373
01374 if (node != NULL)
01375 {
01376 if (node->father != NULL)
01377 {
01378 valid = (node->father->left == node) ^ (node->father->right == node);
01379 valid = valid && correct_descendant( node->left )
01380 && correct_descendant( node->right );
01381 }
01382 else
01383 valid = false;
01384 }
01385
01386 return valid;
01387 }
01388
01389
01396 template<class K, class Comp>
01397 bool claw::avl_base<K,Comp>::validity_check() const
01398 {
01399 bool valid = true;
01400
01401 if (m_tree != NULL)
01402 {
01403 avl_node *node_min, *node_max;
01404
01405
01406 for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left);
01407 for (node_max = m_tree; node_max->right!=NULL;
01408 node_max = node_max->right);
01409
01410 valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
01411 valid = valid
01412 && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
01413
01414 valid = valid && (m_tree->father == NULL)
01415 && correct_descendant( m_tree->left )
01416 && correct_descendant( m_tree->right );
01417
01418 }
01419
01420 return valid && check_balance(m_tree);
01421 }
01422
01423
01424
01425
01426
01427
01432 template<class K, class Comp>
01433 typename claw::avl_base<K,Comp>::iterator
01434 claw::avl_base<K,Comp>::make_iterator( avl_node_ptr node ) const
01435 {
01436 if (node != NULL)
01437 return iterator(node, false);
01438 else
01439 return end();
01440 }
01441
01442
01447 template<class K, class Comp>
01448 typename claw::avl_base<K,Comp>::const_iterator
01449 claw::avl_base<K,Comp>::make_const_iterator( const_avl_node_ptr node ) const
01450 {
01451 if (node != NULL)
01452 return const_iterator(node, false);
01453 else
01454 return end();
01455 }
01456
01457
01458
01459
01460
01461
01462
01463
01471 template<class K, class Comp>
01472 void claw::avl_base<K,Comp>::rotate_right( avl_node_ptr& node )
01473 {
01474 avl_node_ptr p;
01475 char old_node_balance;
01476 char old_subtree_balance;
01477
01478 assert( node != NULL );
01479 assert( node->left != NULL );
01480 assert( (1 <= node->balance) && (node->balance <= 2) ) ;
01481 assert( (-1 <= node->left->balance) && (node->left->balance <= 2) );
01482 assert( (node->left->balance != 2) || (node->balance == 2) );
01483
01484 old_node_balance = node->balance;
01485 old_subtree_balance = node->left->balance;
01486
01487
01488 p = node->left;
01489 p->father = node->father;
01490
01491 node->left = p->right;
01492
01493 if (p->right)
01494 p->right->father = node;
01495
01496 p->right = node;
01497 node->father = p;
01498
01499 node = p;
01500
01501
01502 switch(old_subtree_balance)
01503 {
01504 case -1 :
01505 node->balance = -2;
01506 node->right->balance = old_node_balance - 1;
01507 break;
01508 case 0 :
01509 node->balance = -1;
01510 node->right->balance = old_node_balance - 1;
01511 break;
01512 case 1 :
01513 node->balance = old_node_balance - 2;
01514 node->right->balance = old_node_balance - 2;
01515 break;
01516 case 2 :
01517
01518 node->balance = 0;
01519 node->right->balance = - 1;
01520 break;
01521 }
01522 }
01523
01524
01532 template<class K, class Comp>
01533 void claw::avl_base<K,Comp>::rotate_left( avl_node_ptr& node )
01534 {
01535 avl_node_ptr p;
01536 char old_node_balance;
01537 char old_subtree_balance;
01538
01539 assert( node != NULL );
01540 assert( node->right != NULL );
01541 assert( (-2 <= node->balance) && (node->balance <= -1) ) ;
01542 assert( (-2 <= node->right->balance) && (node->right->balance <= 1) );
01543 assert( (node->right->balance != -2) || (node->balance == -2) );
01544
01545 old_node_balance = node->balance;
01546 old_subtree_balance = node->right->balance;
01547
01548
01549 p = node->right;
01550 p->father = node->father;
01551
01552 node->right = p->left;
01553
01554 if (p->left)
01555 p->left->father = node;
01556
01557 p->left = node;
01558 node->father = p;
01559
01560 node = p;
01561
01562
01563 switch(old_subtree_balance)
01564 {
01565 case -2 :
01566
01567 node->balance = 0;
01568 node->left->balance = 1;
01569 break;
01570 case -1 :
01571 node->balance = old_node_balance + 2;
01572 node->left->balance = old_node_balance + 2;
01573 break;
01574 case 0 :
01575 node->balance = 1;
01576 node->left->balance = old_node_balance + 1;
01577 break;
01578 case 1 :
01579 node->balance = 2;
01580 node->left->balance = old_node_balance + 1;
01581 break;
01582 }
01583 }
01584
01585
01590 template<class K, class Comp>
01591 void claw::avl_base<K,Comp>::rotate_left_right( avl_node_ptr& node )
01592 {
01593 assert( node != NULL );
01594
01595 rotate_left( node->left );
01596 rotate_right( node );
01597 }
01598
01599
01604 template<class K, class Comp>
01605 void claw::avl_base<K,Comp>::rotate_right_left( avl_node_ptr& node )
01606 {
01607 assert( node != NULL );
01608
01609 rotate_right( node->right );
01610 rotate_left( node );
01611 }
01612
01613
01622 template<class K, class Comp>
01623 void claw::avl_base<K,Comp>::update_balance( avl_node_ptr node, const K& key )
01624 {
01625 assert(node != NULL);
01626 bool done = false;
01627
01628 while (!done)
01629 if ( s_key_less(key, node->key) )
01630 {
01631 ++node->balance;
01632 node = node->left;
01633 }
01634 else if ( s_key_less(node->key, key) )
01635 {
01636 --node->balance;
01637 node = node->right;
01638 }
01639 else
01640 done = true;
01641 }
01642
01643
01650 template<class K, class Comp>
01651 void claw::avl_base<K,Comp>::adjust_balance( avl_node_ptr& node )
01652 {
01653 assert(node != NULL);
01654
01655 if ( node->balance == 2)
01656 adjust_balance_left(node);
01657 else if ( node->balance == -2)
01658 adjust_balance_right(node);
01659 }
01660
01661
01669 template<class K, class Comp>
01670 void claw::avl_base<K,Comp>::adjust_balance_left( avl_node_ptr& node )
01671 {
01672 assert(node != NULL);
01673 assert(node->balance == 2);
01674
01675 if (node->left->balance > -1)
01676 rotate_right( node );
01677 else if ( node->left->balance == -1)
01678 rotate_left_right(node);
01679 }
01680
01681
01689 template<class K, class Comp>
01690 void claw::avl_base<K,Comp>::adjust_balance_right( avl_node_ptr& node )
01691 {
01692 assert(node != NULL);
01693 assert(node->balance == -2);
01694
01695 if (node->right->balance < 1)
01696 rotate_left( node );
01697 else if ( node->right->balance == 1)
01698 rotate_right_left(node);
01699 }
01700
01701
01702
01703
01704
01705
01706
01707
01714 template<class K, class Comp>
01715 void claw::avl_base<K,Comp>::insert_node( const K& key )
01716 {
01717 avl_node_ptr* new_node;
01718 avl_node_ptr node_father;
01719 avl_node_ptr last_imbalanced;
01720 avl_node_ptr last_imbalanced_father;
01721
01722 assert(m_tree != NULL);
01723
01724 new_node = find_node_reference(key, last_imbalanced, node_father );
01725
01726 if (*new_node == NULL)
01727 {
01728 *new_node = new avl_node(key);
01729 (*new_node)->father = node_father;
01730
01731 ++m_size;
01732 last_imbalanced_father = last_imbalanced->father;
01733
01734
01735 update_balance( last_imbalanced, key );
01736
01737 adjust_balance( last_imbalanced );
01738
01739
01740 if ( last_imbalanced_father == NULL )
01741 {
01742 m_tree = last_imbalanced;
01743 m_tree->father = NULL;
01744 }
01745 else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key))
01746
01747 last_imbalanced_father->left = last_imbalanced;
01748 else
01749 last_imbalanced_father->right = last_imbalanced;
01750 }
01751 }
01752
01753
01766 template<class K, class Comp>
01767 typename claw::avl_base<K,Comp>::avl_node_ptr*
01768 claw::avl_base<K,Comp>::find_node_reference
01769 ( const K& key, avl_node_ptr& last_imbalanced, avl_node_ptr& node_father)
01770 {
01771 avl_node_ptr* node;
01772 bool exists = false;
01773
01774 last_imbalanced = m_tree;
01775 node = & m_tree;
01776 node_father = NULL;
01777
01778 while ( ((*node) != NULL) && !exists )
01779 {
01780 if ( (*node)->balance != 0 )
01781 last_imbalanced = *node;
01782
01783
01784
01785 if ( s_key_less(key, (*node)->key) )
01786 {
01787 node_father = *node;
01788 node = & (*node)->left;
01789 }
01790 else if ( s_key_less((*node)->key, key) )
01791 {
01792 node_father = *node;
01793 node = & (*node)->right;
01794 }
01795 else
01796 exists = true;
01797 }
01798
01799 return node;
01800 }
01801
01802
01803
01804
01805
01806
01807
01808
01817 template<class K, class Comp>
01818 bool
01819 claw::avl_base<K,Comp>::recursive_delete( avl_node_ptr& node, const K& key )
01820 {
01821 bool result = false;
01822
01823 if ( node != NULL )
01824 {
01825
01826 if ( s_key_less(key, node->key) )
01827 {
01828 if ( recursive_delete( node->left, key ) )
01829 result = new_balance( node, -1 );
01830 }
01831
01832 else if ( s_key_less(node->key, key) )
01833 {
01834 if ( recursive_delete( node->right, key ) )
01835 result = new_balance( node, 1 );
01836 }
01837 else
01838 {
01839 --m_size;
01840 result = recursive_delete_node( node );
01841 }
01842 }
01843
01844 return result;
01845 }
01846
01847
01848
01858 template<class K, class Comp>
01859 bool claw::avl_base<K,Comp>::new_balance( avl_node_ptr& node, int imbalance )
01860 {
01861 assert( (imbalance==1) || (imbalance==-1) );
01862 assert( node != NULL );
01863
01864 node->balance += imbalance;
01865
01866 switch(node->balance)
01867 {
01868
01869
01870 case 0: return true;
01871
01872
01873
01874
01875
01876
01877 case 2: adjust_balance_left(node); return node->balance == 0;
01878
01879 case -2: adjust_balance_right(node); return node->balance == 0;
01880 default : return false;
01881 }
01882 }
01883
01884
01893 template<class K, class Comp>
01894 bool claw::avl_base<K,Comp>::recursive_delete_node( avl_node_ptr& node )
01895 {
01896 assert( node != NULL );
01897
01898 if ( node->left == NULL)
01899 {
01900
01901 avl_node_ptr right_subtree = node->right;
01902
01903 if (right_subtree)
01904 right_subtree->father = node->father;
01905
01906
01907 node->clear();
01908 delete node;
01909
01910
01911 node = right_subtree;
01912
01913 return true;
01914 }
01915 else
01916 if ( recursive_delete_max( node->left, node ) )
01917 {
01918
01919
01920 --(node->balance);
01921
01922 if ( node->balance == -2 )
01923 {
01924
01925 adjust_balance_right(node);
01926 return node->balance == 0;
01927 }
01928 else if ( node->balance == 0 )
01929
01930
01931 return true;
01932 else
01933
01934
01935
01936
01937
01938
01939
01940
01941
01942
01943 return false;
01944 }
01945 else
01946 return false;
01947 }
01948
01949
01961 template<class K, class Comp>
01962 int claw::avl_base<K,Comp>::recursive_delete_max
01963 ( avl_node_ptr& root, avl_node_ptr node )
01964 {
01965 assert(node!=NULL);
01966 assert(root!=NULL);
01967
01968 if ( root->right == NULL )
01969 {
01970
01971
01972 avl_node_ptr left_subtree;
01973
01974 node->key = root->key;
01975 left_subtree = root->left;
01976
01977 if (left_subtree)
01978 left_subtree->father = root->father;
01979
01980 root->clear();
01981 delete root;
01982
01983
01984 root = left_subtree;
01985
01986
01987 return true;
01988 }
01989 else
01990 if ( recursive_delete_max( root->right, node ) )
01991 {
01992
01993
01994 ++(root->balance);
01995
01996 if (root->balance == 2)
01997 {
01998
01999 adjust_balance_left( root );
02000 return root->balance == 0;
02001 }
02002 else
02003
02004
02005
02006
02007 return root->balance == 0;
02008 }
02009 else
02010 return false;
02011 }