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;
00143 avl_node* node = this;
00144
00145 ok = false;
00146
00147 while (node && !ok)
00148 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00149 node = node->left;
00150 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00151 node = node->right;
00152 else
00153 ok = true;
00154
00155 return node;
00156 }
00157
00158
00163 template<class K, class Comp>
00164 const typename claw::avl_base<K,Comp>::avl_node*
00165 claw::avl_base<K,Comp>::avl_node::find( const K& key ) const
00166 {
00167 bool ok;
00168 const avl_node* node = this;
00169
00170 ok = false;
00171
00172 while (node && !ok)
00173 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00174 node = node->left;
00175 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00176 node = node->right;
00177 else
00178 ok = true;
00179
00180 return node;
00181 }
00182
00183
00189 template<class K, class Comp>
00190 typename claw::avl_base<K,Comp>::avl_node*
00191 claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key )
00192 {
00193 bool ok;
00194 avl_node* node = this;
00195 avl_node* prev_node = NULL;
00196
00197 ok = false;
00198
00199 while (node && !ok)
00200 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00201 {
00202 prev_node = node;
00203 node = node->left;
00204 }
00205 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00206 {
00207 prev_node = node;
00208 node = node->right;
00209 }
00210 else
00211 ok = true;
00212
00213 if (ok)
00214 return node->next();
00215 else if (prev_node)
00216 {
00217 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
00218 return prev_node->next();
00219 else
00220 return prev_node;
00221 }
00222 else
00223 return node;
00224 }
00225
00226
00232 template<class K, class Comp>
00233 const typename claw::avl_base<K,Comp>::avl_node*
00234 claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key ) const
00235 {
00236 bool ok;
00237 const avl_node* node = this;
00238 const avl_node* prev_node = NULL;
00239
00240 ok = false;
00241
00242 while (node && !ok)
00243 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00244 {
00245 prev_node = node;
00246 node = node->left;
00247 }
00248 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00249 {
00250 prev_node = node;
00251 node = node->right;
00252 }
00253 else
00254 ok = true;
00255
00256 if (ok)
00257 return node->next();
00258 else if (prev_node)
00259 {
00260 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
00261 return prev_node->next();
00262 else
00263 return prev_node;
00264 }
00265 else
00266 return node;
00267 }
00268
00269
00275 template<class K, class Comp>
00276 typename claw::avl_base<K,Comp>::avl_node*
00277 claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key )
00278 {
00279 bool ok;
00280 avl_node* node = this;
00281 avl_node* prev_node = NULL;
00282
00283 ok = false;
00284
00285 while (node && !ok)
00286 if ( s_key_less(key, node->key) )
00287 {
00288 prev_node = node;
00289 node = node->left;
00290 }
00291 else if ( s_key_less(node->key, key) )
00292 {
00293 prev_node = node;
00294 node = node->right;
00295 }
00296 else
00297 ok = true;
00298
00299 if (ok)
00300 return node->prev();
00301 else if (prev_node)
00302 {
00303 if ( s_key_less(key, prev_node->key) )
00304 return prev_node;
00305 else
00306 return prev_node->prev();
00307 }
00308 else
00309 return node;
00310 }
00311
00312
00318 template<class K, class Comp>
00319 const typename claw::avl_base<K,Comp>::avl_node*
00320 claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key ) const
00321 {
00322 bool ok;
00323 const avl_node* node = this;
00324 const avl_node* prev_node = NULL;
00325
00326 ok = false;
00327
00328 while (node && !ok)
00329 if ( s_key_less(key, node->key) )
00330 {
00331 prev_node = node;
00332 node = node->left;
00333 }
00334 else if ( s_key_less(node->key, key) )
00335 {
00336 prev_node = node;
00337 node = node->right;
00338 }
00339 else
00340 ok = true;
00341
00342 if (ok)
00343 return node->prev();
00344 else if (prev_node)
00345 {
00346 if ( s_key_less(key, prev_node->key) )
00347 return prev_node;
00348 else
00349 return prev_node->prev();
00350 }
00351 else
00352 return node;
00353 }
00354
00355
00359 template<class K, class Comp>
00360 typename claw::avl_base<K,Comp>::avl_node*
00361 claw::avl_base<K,Comp>::avl_node::lower_bound()
00362 {
00363 avl_node* node = this;
00364
00365 if (node)
00366 while (node->left)
00367 node = node->left;
00368
00369 return node;
00370 }
00371
00372
00376 template<class K, class Comp>
00377 const typename claw::avl_base<K,Comp>::avl_node*
00378 claw::avl_base<K,Comp>::avl_node::lower_bound() const
00379 {
00380 const avl_node* node = this;
00381
00382 if (node)
00383 while (node->left)
00384 node = node->left;
00385
00386 return node;
00387 }
00388
00389
00393 template<class K, class Comp>
00394 typename claw::avl_base<K,Comp>::avl_node*
00395 claw::avl_base<K,Comp>::avl_node::upper_bound()
00396 {
00397 avl_node* node = this;
00398
00399 if (node)
00400 while (node->right)
00401 node = node->right;
00402
00403 return node;
00404 }
00405
00406
00410 template<class K, class Comp>
00411 const typename claw::avl_base<K,Comp>::avl_node*
00412 claw::avl_base<K,Comp>::avl_node::upper_bound() const
00413 {
00414 const avl_node* node = this;
00415
00416 if (node)
00417 while (node->right)
00418 node = node->right;
00419
00420 return node;
00421 }
00422
00423
00427 template<class K, class Comp>
00428 typename claw::avl_base<K,Comp>::avl_node*
00429 claw::avl_base<K,Comp>::avl_node::next()
00430 {
00431 avl_node* result = this;
00432
00433
00434 if (result->right != NULL)
00435 {
00436 result = result->right;
00437
00438 while (result->left != NULL)
00439 result = result->left;
00440 }
00441 else
00442 {
00443 bool done = false;
00444 avl_node* previous_node = this;
00445
00446
00447 while (result->father && !done)
00448 {
00449 if (result->father->left == result)
00450 done = true;
00451
00452 result = result->father;
00453 }
00454
00455
00456 if (!done)
00457 result = previous_node;
00458 }
00459
00460 return result;
00461 }
00462
00463
00467 template<class K, class Comp>
00468 const typename claw::avl_base<K,Comp>::avl_node*
00469 claw::avl_base<K,Comp>::avl_node::next() const
00470 {
00471 const avl_node* result = this;
00472
00473
00474 if (result->right != NULL)
00475 {
00476 result = result->right;
00477
00478 while (result->left != NULL)
00479 result = result->left;
00480 }
00481 else
00482 {
00483 bool done = false;
00484 const avl_node* previous_node = this;
00485
00486
00487 while (result->father && !done)
00488 {
00489 if (result->father->left == result)
00490 done = true;
00491
00492 result = result->father;
00493 }
00494
00495
00496 if (!done)
00497 result = previous_node;
00498 }
00499
00500 return result;
00501 }
00502
00503
00507 template<class K, class Comp>
00508 typename claw::avl_base<K,Comp>::avl_node*
00509 claw::avl_base<K,Comp>::avl_node::prev()
00510 {
00511 avl_node* result = this;
00512
00513
00514 if (result->left != NULL)
00515 {
00516 result = result->left;
00517
00518 while (result->right != NULL)
00519 result = result->right;
00520 }
00521 else
00522 {
00523 bool done = false;
00524
00525
00526 while (result->father && !done)
00527 {
00528 if (result->father->right == result)
00529 done = true;
00530
00531 result = result->father;
00532 }
00533 }
00534
00535 return result;
00536 }
00537
00538
00542 template<class K, class Comp>
00543 const typename claw::avl_base<K,Comp>::avl_node*
00544 claw::avl_base<K,Comp>::avl_node::prev() const
00545 {
00546 const avl_node* result = this;
00547
00548
00549 if (result->left != NULL)
00550 {
00551 result = result->left;
00552
00553 while (result->right != NULL)
00554 result = result->right;
00555 }
00556 else
00557 {
00558 bool done = false;
00559
00560
00561 while (result->father && !done)
00562 {
00563 if (result->father->right == result)
00564 done = true;
00565
00566 result = result->father;
00567 }
00568 }
00569
00570 return result;
00571 }
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581
00587 template<class K, class Comp>
00588 claw::avl_base<K, Comp>::avl_node::avl_node( const avl_node& that )
00589 : super(that), key(that.key), balance(that.balance), father(NULL)
00590 {
00591 assert(0);
00592 }
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00606 template<class K, class Comp>
00607 claw::avl_base<K,Comp>::avl_iterator::avl_iterator()
00608 : m_current(NULL), m_is_final(true)
00609 {
00610
00611 }
00612
00613
00617 template<class K, class Comp>
00618 claw::avl_base<K,Comp>::avl_iterator::avl_iterator
00619 ( avl_node_ptr node, bool final )
00620 : m_current(node), m_is_final(final)
00621 {
00622
00623 }
00624
00625
00630 template<class K, class Comp>
00631 typename claw::avl_base<K,Comp>::avl_iterator&
00632 claw::avl_base<K,Comp>::avl_iterator::operator++()
00633 {
00634 assert(!m_is_final);
00635 assert(m_current);
00636
00637 avl_node* p = m_current->next();
00638
00639 if ( m_current == p )
00640 m_is_final = true;
00641 else
00642 m_current = p;
00643
00644 return *this;
00645 }
00646
00647
00651 template<class K, class Comp>
00652 typename claw::avl_base<K,Comp>::avl_iterator
00653 claw::avl_base<K,Comp>::avl_iterator::operator++(int)
00654 {
00655 avl_iterator it = *this;
00656 ++(*this);
00657 return it;
00658 }
00659
00660
00665 template<class K, class Comp>
00666 typename claw::avl_base<K,Comp>::avl_iterator&
00667 claw::avl_base<K,Comp>::avl_iterator::operator--()
00668 {
00669 assert(m_current);
00670
00671 if (m_is_final)
00672 m_is_final = !m_is_final;
00673 else
00674 m_current = m_current->prev();
00675
00676 assert(m_current != NULL);
00677
00678 return *this;
00679 }
00680
00681
00685 template<class K, class Comp>
00686 typename claw::avl_base<K,Comp>::avl_iterator
00687 claw::avl_base<K,Comp>::avl_iterator::operator--(int)
00688 {
00689 avl_iterator it = *this;
00690 --(*this);
00691 return it;
00692 }
00693
00694
00698 template<class K, class Comp>
00699 typename claw::avl_base<K,Comp>::avl_iterator::reference
00700 claw::avl_base<K,Comp>::avl_iterator::operator*() const
00701 {
00702 return m_current->key;
00703 }
00704
00705
00709 template<class K, class Comp>
00710 typename claw::avl_base<K,Comp>::avl_iterator::pointer
00711 claw::avl_base<K,Comp>::avl_iterator::operator->() const
00712 {
00713 return &m_current->key;
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 (m_current == it.m_current) && (m_is_final == it.m_is_final);
00726 }
00727
00728
00733 template<class K, class Comp>
00734 bool
00735 claw::avl_base<K,Comp>::avl_iterator::operator!=(const avl_iterator& it) const
00736 {
00737 return !( *this == it );
00738 }
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00752 template<class K, class Comp>
00753 claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator()
00754 : m_current(NULL), m_is_final(true)
00755 {
00756
00757 }
00758
00759
00763 template<class K, class Comp>
00764 claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator
00765 ( const_avl_node_ptr node, bool final )
00766 : m_current(node), m_is_final(final)
00767 {
00768
00769 }
00770
00771
00776 template<class K, class Comp>
00777 typename claw::avl_base<K,Comp>::avl_const_iterator&
00778 claw::avl_base<K,Comp>::avl_const_iterator::operator++()
00779 {
00780 assert(!m_is_final);
00781 assert(m_current);
00782
00783 const_avl_node_ptr p = m_current->next();
00784
00785 if ( m_current == p )
00786 m_is_final = true;
00787 else
00788 m_current = p;
00789
00790 return *this;
00791 }
00792
00793
00797 template<class K, class Comp>
00798 typename claw::avl_base<K,Comp>::avl_const_iterator
00799 claw::avl_base<K,Comp>::avl_const_iterator::operator++(int)
00800 {
00801 avl_const_iterator it = *this;
00802 ++(*this);
00803 return it;
00804 }
00805
00806
00811 template<class K, class Comp>
00812 typename claw::avl_base<K,Comp>::avl_const_iterator&
00813 claw::avl_base<K,Comp>::avl_const_iterator::operator--()
00814 {
00815 assert(m_current);
00816
00817 if (m_is_final)
00818 m_is_final = !m_is_final;
00819 else
00820 m_current = m_current->prev();
00821
00822 assert(m_current != NULL);
00823
00824 return *this;
00825 }
00826
00827
00831 template<class K, class Comp>
00832 typename claw::avl_base<K,Comp>::avl_const_iterator
00833 claw::avl_base<K,Comp>::avl_const_iterator::operator--(int)
00834 {
00835 avl_const_iterator it = *this;
00836 --(*this);
00837 return it;
00838 }
00839
00840
00844 template<class K, class Comp>
00845 typename claw::avl_base<K,Comp>::avl_const_iterator::reference
00846 claw::avl_base<K,Comp>::avl_const_iterator::operator*() const
00847 {
00848 return m_current->key;
00849 }
00850
00851
00855 template<class K, class Comp>
00856 typename claw::avl_base<K,Comp>::avl_const_iterator::pointer
00857 claw::avl_base<K,Comp>::avl_const_iterator::operator->() const
00858 {
00859 return &m_current->key;
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 (m_current == it.m_current) && (m_is_final == it.m_is_final);
00872 }
00873
00874
00879 template<class K, class Comp>
00880 bool claw::avl_base<K,Comp>::avl_const_iterator::operator!=
00881 (const avl_const_iterator& it) const
00882 {
00883 return !( *this == it );
00884 }
00885
00886
00887
00888
00889
00890
00891
00892
00893
00894 template<class K, class Comp>
00895 typename claw::avl_base<K,Comp>::key_less claw::avl_base<K,Comp>::s_key_less;
00896
00897
00902 template<class K, class Comp>
00903 claw::avl_base<K,Comp>::avl_base()
00904 : m_size(0), m_tree(NULL)
00905 {
00906
00907 }
00908
00909
00914 template<class K, class Comp>
00915 claw::avl_base<K,Comp>::avl_base( const avl_base<K, Comp>& that )
00916 {
00917 m_size = 0;
00918
00919 if (that.m_tree)
00920 m_tree = that.m_tree->duplicate( m_size );
00921 else
00922 m_tree = NULL;
00923 }
00924
00925
00929 template<class K, class Comp>
00930 claw::avl_base<K,Comp>::~avl_base()
00931 {
00932 if (m_tree)
00933 {
00934 m_tree->del_tree();
00935 delete m_tree;
00936 }
00937 }
00938
00939
00945 template<class K, class Comp>
00946 void claw::avl_base<K,Comp>::insert( const K& key )
00947 {
00948 assert( validity_check() );
00949
00950 if ( m_tree == NULL )
00951 {
00952 m_tree = new avl_node(key);
00953 m_size = 1;
00954 }
00955 else
00956 insert_node(key);
00957
00958 assert( validity_check() );
00959 }
00960
00961
00969 template<class K, class Comp>
00970 template<typename Iterator>
00971 void claw::avl_base<K,Comp>::insert( Iterator first, Iterator last )
00972 {
00973 for ( ; first!=last; ++first )
00974 insert( *first );
00975 }
00976
00977
00983 template<class K, class Comp>
00984 void claw::avl_base<K,Comp>::erase( const K& key )
00985 {
00986 assert( validity_check() );
00987
00988 if (m_tree != NULL)
00989 recursive_delete( m_tree, key );
00990
00991 assert( validity_check() );
00992 }
00993
00994
00999 template<class K, class Comp>
01000 void claw::avl_base<K,Comp>::clear()
01001 {
01002 if (m_tree != NULL)
01003 {
01004 m_tree->del_tree();
01005 delete m_tree;
01006
01007 m_tree = NULL;
01008 m_size = 0;
01009 }
01010 }
01011
01012
01017 template<class K, class Comp>
01018 inline unsigned int claw::avl_base<K,Comp>::size() const
01019 {
01020 return m_size;
01021 }
01022
01023
01028 template<class K, class Comp>
01029 inline bool claw::avl_base<K,Comp>::empty() const
01030 {
01031 return m_size == 0;
01032 }
01033
01034
01038 template<class K, class Comp>
01039 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::begin()
01040 {
01041 if (m_tree == NULL)
01042 return iterator(NULL, true);
01043 else
01044 return lower_bound();
01045 }
01046
01047
01051 template<class K, class Comp>
01052 typename claw::avl_base<K,Comp>::const_iterator
01053 claw::avl_base<K,Comp>::begin() const
01054 {
01055 if (m_tree == NULL)
01056 return const_iterator(NULL, true);
01057 else
01058 return lower_bound();
01059 }
01060
01061
01065 template<class K, class Comp>
01066 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::end()
01067 {
01068 if (m_tree == NULL)
01069 return iterator(NULL, true);
01070 else
01071 return iterator(m_tree->upper_bound(), true);
01072 }
01073
01074
01078 template<class K, class Comp>
01079 typename claw::avl_base<K,Comp>::const_iterator
01080 claw::avl_base<K,Comp>::end() const
01081 {
01082 if (m_tree == NULL)
01083 return const_iterator(NULL, true);
01084 else
01085 return const_iterator(m_tree->upper_bound(), true);
01086 }
01087
01088
01093 template<class K, class Comp>
01094 typename claw::avl_base<K,Comp>::iterator
01095 claw::avl_base<K,Comp>::find( const K& key )
01096 {
01097 return make_iterator( m_tree->find(key) );
01098 }
01099
01100
01105 template<class K, class Comp>
01106 typename claw::avl_base<K,Comp>::const_iterator
01107 claw::avl_base<K,Comp>::find( const K& key ) const
01108 {
01109 return make_const_iterator( m_tree->find(key) );
01110 }
01111
01112
01118 template<class K, class Comp>
01119 typename claw::avl_base<K,Comp>::iterator
01120 claw::avl_base<K,Comp>::find_nearest_greater( const K& key )
01121 {
01122 return make_iterator( m_tree->find_nearest_greater(key) );
01123 }
01124
01125
01131 template<class K, class Comp>
01132 typename claw::avl_base<K,Comp>::const_iterator
01133 claw::avl_base<K,Comp>::find_nearest_greater( const K& key ) const
01134 {
01135 return make_const_iterator( m_tree->find_nearest_greater(key) );
01136 }
01137
01138
01144 template<class K, class Comp>
01145 typename claw::avl_base<K,Comp>::iterator
01146 claw::avl_base<K,Comp>::find_nearest_lower( const K& key )
01147 {
01148 return make_iterator( m_tree->find_nearest_lower(key) );
01149 }
01150
01151
01157 template<class K, class Comp>
01158 typename claw::avl_base<K,Comp>::const_iterator
01159 claw::avl_base<K,Comp>::find_nearest_lower( const K& key ) const
01160 {
01161 return make_const_iterator( m_tree->find_nearest_lower(key) );
01162 }
01163
01164
01168 template<class K, class Comp>
01169 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::lower_bound()
01170 {
01171 return make_iterator( m_tree->lower_bound() );
01172 }
01173
01174
01178 template<class K, class Comp>
01179 typename claw::avl_base<K,Comp>::const_iterator
01180 claw::avl_base<K,Comp>::lower_bound() const
01181 {
01182 return make_const_iterator( m_tree->lower_bound() );
01183 }
01184
01185
01189 template<class K, class Comp>
01190 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::upper_bound()
01191 {
01192 return make_iterator( m_tree->upper_bound() );
01193 }
01194
01195
01199 template<class K, class Comp>
01200 typename claw::avl_base<K,Comp>::const_iterator
01201 claw::avl_base<K,Comp>::upper_bound() const
01202 {
01203 return make_const_iterator( m_tree->upper_bound() );
01204 }
01205
01206
01211 template<class K, class Comp>
01212 claw::avl_base<K, Comp>&
01213 claw::avl_base<K, Comp>::operator=( const avl_base<K, Comp>& that )
01214 {
01215 if (this != &that)
01216 {
01217 if (m_tree)
01218 {
01219 m_tree->del_tree();
01220 delete m_tree;
01221 }
01222
01223 m_size = 0;
01224
01225 if (that.m_tree)
01226 m_tree = that.m_tree->duplicate( m_size );
01227 else
01228 m_tree = NULL;
01229 }
01230
01231 return *this;
01232 }
01233
01234
01239 template<class K, class Comp>
01240 bool claw::avl_base<K, Comp>::operator==( const avl_base<K, Comp>& that ) const
01241 {
01242 if (m_size != that.m_size)
01243 return false;
01244 else
01245 return std::equal( begin(), end(), that.begin(), s_key_less );
01246 }
01247
01248
01253 template<class K, class Comp>
01254 bool claw::avl_base<K, Comp>::operator!=( const avl_base<K, Comp>& that ) const
01255 {
01256 return !( *this == that );
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 std::lexicographical_compare
01268 ( begin(), end(), that.begin(), that.end(), s_key_less );
01269 }
01270
01271
01276 template<class K, class Comp>
01277 bool claw::avl_base<K, Comp>::operator>( const avl_base<K, Comp>& that ) const
01278 {
01279 return that < *this;
01280 }
01281
01282
01287 template<class K, class Comp>
01288 bool claw::avl_base<K, Comp>::operator<=( const avl_base<K, Comp>& that ) const
01289 {
01290 return !( that < *this );
01291 }
01292
01293
01298 template<class K, class Comp>
01299 bool claw::avl_base<K, Comp>::operator>=( const avl_base<K, Comp>& that ) const
01300 {
01301 return !( *this < that );
01302 }
01303
01304
01309 template<class K, class Comp>
01310 void claw::avl_base<K, Comp>::swap( avl_base<K, Comp>& that )
01311 {
01312 std::swap(m_size, that.m_size);
01313 std::swap(m_tree, that.m_tree);
01314 }
01315
01316
01317
01318
01319
01320
01321
01330 template<class K, class Comp>
01331 bool claw::avl_base<K,Comp>::check_in_bounds
01332 ( const avl_node_ptr node, const K& min, const K& max ) const
01333 {
01334 if (node == NULL)
01335 return true;
01336 else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) )
01337 return (node->left == NULL)
01338 && check_in_bounds( node->right, node->key, max );
01339 else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) )
01340 return (node->right == NULL)
01341 && check_in_bounds( node->left, min, node->key );
01342 else
01343 return s_key_less(node->key, max) && s_key_less(min, node->key)
01344 && check_in_bounds( node->left, min, node->key )
01345 && check_in_bounds( node->right, node->key, max );
01346 }
01347
01348
01357 template<class K, class Comp>
01358 bool claw::avl_base<K,Comp>::check_balance( const avl_node_ptr node ) const
01359 {
01360 int pl=0, pr=0;
01361
01362 if (node == NULL)
01363 return true;
01364 else
01365 {
01366 if (node->left) pl = node->left->depth();
01367 if (node->right) pr = node->right->depth();
01368
01369 return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
01370 && check_balance(node->left) && check_balance(node->right);
01371 }
01372 }
01373
01374
01381 template<class K, class Comp>
01382 bool claw::avl_base<K,Comp>::correct_descendant( const avl_node_ptr node ) const
01383 {
01384 bool valid = true;
01385
01386 if (node != NULL)
01387 {
01388 if (node->father != NULL)
01389 {
01390 valid = (node->father->left == node) ^ (node->father->right == node);
01391 valid = valid && correct_descendant( node->left )
01392 && correct_descendant( node->right );
01393 }
01394 else
01395 valid = false;
01396 }
01397
01398 return valid;
01399 }
01400
01401
01408 template<class K, class Comp>
01409 bool claw::avl_base<K,Comp>::validity_check() const
01410 {
01411 bool valid = true;
01412
01413 if (m_tree != NULL)
01414 {
01415 avl_node *node_min, *node_max;
01416
01417
01418 for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left);
01419 for (node_max = m_tree; node_max->right!=NULL;
01420 node_max = node_max->right);
01421
01422 valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
01423 valid = valid
01424 && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
01425
01426 valid = valid && (m_tree->father == NULL)
01427 && correct_descendant( m_tree->left )
01428 && correct_descendant( m_tree->right );
01429
01430 }
01431
01432 return valid && check_balance(m_tree);
01433 }
01434
01435
01436
01437
01438
01439
01444 template<class K, class Comp>
01445 typename claw::avl_base<K,Comp>::iterator
01446 claw::avl_base<K,Comp>::make_iterator( avl_node_ptr node ) const
01447 {
01448 if (node != NULL)
01449 return iterator(node, false);
01450 else
01451 return end();
01452 }
01453
01454
01459 template<class K, class Comp>
01460 typename claw::avl_base<K,Comp>::const_iterator
01461 claw::avl_base<K,Comp>::make_const_iterator( const_avl_node_ptr node ) const
01462 {
01463 if (node != NULL)
01464 return const_iterator(node, false);
01465 else
01466 return end();
01467 }
01468
01469
01470
01471
01472
01473
01474
01475
01483 template<class K, class Comp>
01484 void claw::avl_base<K,Comp>::rotate_right( avl_node_ptr& node )
01485 {
01486 avl_node_ptr p;
01487 char old_node_balance;
01488 char old_subtree_balance;
01489
01490 assert( node != NULL );
01491 assert( node->left != NULL );
01492 assert( (1 <= node->balance) && (node->balance <= 2) ) ;
01493 assert( (-1 <= node->left->balance) && (node->left->balance <= 2) );
01494 assert( (node->left->balance != 2) || (node->balance == 2) );
01495
01496 old_node_balance = node->balance;
01497 old_subtree_balance = node->left->balance;
01498
01499
01500 p = node->left;
01501 p->father = node->father;
01502
01503 node->left = p->right;
01504
01505 if (p->right)
01506 p->right->father = node;
01507
01508 p->right = node;
01509 node->father = p;
01510
01511 node = p;
01512
01513
01514 switch(old_subtree_balance)
01515 {
01516 case -1 :
01517 node->balance = -2;
01518 node->right->balance = old_node_balance - 1;
01519 break;
01520 case 0 :
01521 node->balance = -1;
01522 node->right->balance = old_node_balance - 1;
01523 break;
01524 case 1 :
01525 node->balance = old_node_balance - 2;
01526 node->right->balance = old_node_balance - 2;
01527 break;
01528 case 2 :
01529
01530 node->balance = 0;
01531 node->right->balance = - 1;
01532 break;
01533 }
01534 }
01535
01536
01544 template<class K, class Comp>
01545 void claw::avl_base<K,Comp>::rotate_left( avl_node_ptr& node )
01546 {
01547 avl_node_ptr p;
01548 char old_node_balance;
01549 char old_subtree_balance;
01550
01551 assert( node != NULL );
01552 assert( node->right != NULL );
01553 assert( (-2 <= node->balance) && (node->balance <= -1) ) ;
01554 assert( (-2 <= node->right->balance) && (node->right->balance <= 1) );
01555 assert( (node->right->balance != -2) || (node->balance == -2) );
01556
01557 old_node_balance = node->balance;
01558 old_subtree_balance = node->right->balance;
01559
01560
01561 p = node->right;
01562 p->father = node->father;
01563
01564 node->right = p->left;
01565
01566 if (p->left)
01567 p->left->father = node;
01568
01569 p->left = node;
01570 node->father = p;
01571
01572 node = p;
01573
01574
01575 switch(old_subtree_balance)
01576 {
01577 case -2 :
01578
01579 node->balance = 0;
01580 node->left->balance = 1;
01581 break;
01582 case -1 :
01583 node->balance = old_node_balance + 2;
01584 node->left->balance = old_node_balance + 2;
01585 break;
01586 case 0 :
01587 node->balance = 1;
01588 node->left->balance = old_node_balance + 1;
01589 break;
01590 case 1 :
01591 node->balance = 2;
01592 node->left->balance = old_node_balance + 1;
01593 break;
01594 }
01595 }
01596
01597
01602 template<class K, class Comp>
01603 void claw::avl_base<K,Comp>::rotate_left_right( avl_node_ptr& node )
01604 {
01605 assert( node != NULL );
01606
01607 rotate_left( node->left );
01608 rotate_right( node );
01609 }
01610
01611
01616 template<class K, class Comp>
01617 void claw::avl_base<K,Comp>::rotate_right_left( avl_node_ptr& node )
01618 {
01619 assert( node != NULL );
01620
01621 rotate_right( node->right );
01622 rotate_left( node );
01623 }
01624
01625
01634 template<class K, class Comp>
01635 void claw::avl_base<K,Comp>::update_balance( avl_node_ptr node, const K& key )
01636 {
01637 assert(node != NULL);
01638 bool done = false;
01639
01640 while (!done)
01641 if ( s_key_less(key, node->key) )
01642 {
01643 ++node->balance;
01644 node = node->left;
01645 }
01646 else if ( s_key_less(node->key, key) )
01647 {
01648 --node->balance;
01649 node = node->right;
01650 }
01651 else
01652 done = true;
01653 }
01654
01655
01662 template<class K, class Comp>
01663 void claw::avl_base<K,Comp>::adjust_balance( avl_node_ptr& node )
01664 {
01665 assert(node != NULL);
01666
01667 if ( node->balance == 2)
01668 adjust_balance_left(node);
01669 else if ( node->balance == -2)
01670 adjust_balance_right(node);
01671 }
01672
01673
01681 template<class K, class Comp>
01682 void claw::avl_base<K,Comp>::adjust_balance_left( avl_node_ptr& node )
01683 {
01684 assert(node != NULL);
01685 assert(node->balance == 2);
01686
01687 if (node->left->balance > -1)
01688 rotate_right( node );
01689 else if ( node->left->balance == -1)
01690 rotate_left_right(node);
01691 }
01692
01693
01701 template<class K, class Comp>
01702 void claw::avl_base<K,Comp>::adjust_balance_right( avl_node_ptr& node )
01703 {
01704 assert(node != NULL);
01705 assert(node->balance == -2);
01706
01707 if (node->right->balance < 1)
01708 rotate_left( node );
01709 else if ( node->right->balance == 1)
01710 rotate_right_left(node);
01711 }
01712
01713
01714
01715
01716
01717
01718
01719
01726 template<class K, class Comp>
01727 void claw::avl_base<K,Comp>::insert_node( const K& key )
01728 {
01729 avl_node_ptr* new_node;
01730 avl_node_ptr node_father;
01731 avl_node_ptr last_imbalanced;
01732 avl_node_ptr last_imbalanced_father;
01733
01734 assert(m_tree != NULL);
01735
01736 new_node = find_node_reference(key, last_imbalanced, node_father );
01737
01738 if (*new_node == NULL)
01739 {
01740 *new_node = new avl_node(key);
01741 (*new_node)->father = node_father;
01742
01743 ++m_size;
01744 last_imbalanced_father = last_imbalanced->father;
01745
01746
01747 update_balance( last_imbalanced, key );
01748
01749 adjust_balance( last_imbalanced );
01750
01751
01752 if ( last_imbalanced_father == NULL )
01753 {
01754 m_tree = last_imbalanced;
01755 m_tree->father = NULL;
01756 }
01757 else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key))
01758
01759 last_imbalanced_father->left = last_imbalanced;
01760 else
01761 last_imbalanced_father->right = last_imbalanced;
01762 }
01763 }
01764
01765
01778 template<class K, class Comp>
01779 typename claw::avl_base<K,Comp>::avl_node_ptr*
01780 claw::avl_base<K,Comp>::find_node_reference
01781 ( const K& key, avl_node_ptr& last_imbalanced, avl_node_ptr& node_father)
01782 {
01783 avl_node_ptr* node;
01784 bool exists;
01785
01786 last_imbalanced = m_tree;
01787 node = & m_tree;
01788 node_father = NULL;
01789 exists = false;
01790
01791 while ( ((*node) != NULL) && !exists )
01792 {
01793 if ( (*node)->balance != 0 )
01794 last_imbalanced = *node;
01795
01796
01797
01798 if ( s_key_less(key, (*node)->key) )
01799 {
01800 node_father = *node;
01801 node = & (*node)->left;
01802 }
01803 else if ( s_key_less((*node)->key, key) )
01804 {
01805 node_father = *node;
01806 node = & (*node)->right;
01807 }
01808 else
01809 exists = true;
01810 }
01811
01812 return node;
01813 }
01814
01815
01816
01817
01818
01819
01820
01821
01830 template<class K, class Comp>
01831 bool
01832 claw::avl_base<K,Comp>::recursive_delete( avl_node_ptr& node, const K& key )
01833 {
01834 bool result = false;
01835
01836 if ( node != NULL )
01837 {
01838
01839 if ( s_key_less(key, node->key) )
01840 {
01841 if ( recursive_delete( node->left, key ) )
01842 result = new_balance( node, -1 );
01843 }
01844
01845 else if ( s_key_less(node->key, key) )
01846 {
01847 if ( recursive_delete( node->right, key ) )
01848 result = new_balance( node, 1 );
01849 }
01850 else
01851 {
01852 --m_size;
01853 result = recursive_delete_node( node );
01854 }
01855 }
01856
01857 return result;
01858 }
01859
01860
01861
01871 template<class K, class Comp>
01872 bool claw::avl_base<K,Comp>::new_balance( avl_node_ptr& node, int imbalance )
01873 {
01874 assert( (imbalance==1) || (imbalance==-1) );
01875 assert( node != NULL );
01876
01877 node->balance += imbalance;
01878
01879 switch(node->balance)
01880 {
01881
01882
01883 case 0: return true;
01884
01885
01886
01887
01888
01889
01890 case 2: adjust_balance_left(node); return node->balance == 0;
01891
01892 case -2: adjust_balance_right(node); return node->balance == 0;
01893 default : return false;
01894 }
01895 }
01896
01897
01906 template<class K, class Comp>
01907 bool claw::avl_base<K,Comp>::recursive_delete_node( avl_node_ptr& node )
01908 {
01909 assert( node != NULL );
01910
01911 if ( node->left == NULL)
01912 {
01913
01914 avl_node_ptr right_subtree = node->right;
01915
01916 if (right_subtree)
01917 right_subtree->father = node->father;
01918
01919
01920 node->clear();
01921 delete node;
01922
01923
01924 node = right_subtree;
01925
01926 return true;
01927 }
01928 else
01929 if ( recursive_delete_max( node->left, node ) )
01930 {
01931
01932
01933 --(node->balance);
01934
01935 if ( node->balance == -2 )
01936 {
01937
01938 adjust_balance_right(node);
01939 return node->balance == 0;
01940 }
01941 else if ( node->balance == 0 )
01942
01943
01944 return true;
01945 else
01946
01947
01948
01949
01950
01951
01952
01953
01954
01955
01956 return false;
01957 }
01958 else
01959 return false;
01960 }
01961
01962
01974 template<class K, class Comp>
01975 int claw::avl_base<K,Comp>::recursive_delete_max
01976 ( avl_node_ptr& root, avl_node_ptr node )
01977 {
01978 assert(node!=NULL);
01979 assert(root!=NULL);
01980
01981 if ( root->right == NULL )
01982 {
01983
01984
01985 avl_node_ptr left_subtree;
01986
01987 node->key = root->key;
01988 left_subtree = root->left;
01989
01990 if (left_subtree)
01991 left_subtree->father = root->father;
01992
01993 root->clear();
01994 delete root;
01995
01996
01997 root = left_subtree;
01998
01999
02000 return true;
02001 }
02002 else
02003 if ( recursive_delete_max( root->right, node ) )
02004 {
02005
02006
02007 ++(root->balance);
02008
02009 if (root->balance == 2)
02010 {
02011
02012 adjust_balance_left( root );
02013 return root->balance == 0;
02014 }
02015 else
02016
02017
02018
02019
02020 return root->balance == 0;
02021 }
02022 else
02023 return false;
02024 }