Claw
1.7.0
|
00001 /* 00002 CLAW - a C++ Library Absolutely Wonderful 00003 00004 CLAW is a free library without any particular aim but being useful to 00005 anyone. 00006 00007 Copyright (C) 2005-2011 Julien Jorge 00008 00009 This library is free software; you can redistribute it and/or 00010 modify it under the terms of the GNU Lesser General Public 00011 License as published by the Free Software Foundation; either 00012 version 2.1 of the License, or (at your option) any later version. 00013 00014 This library is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public 00020 License along with this library; if not, write to the Free Software 00021 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 00023 contact: julien.jorge@gamned.org 00024 */ 00030 #include <cassert> 00031 00032 //**************************** avl_base::avl_node ****************************** 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 } // avl_node::avl_node() [constructeur] 00046 00047 /*----------------------------------------------------------------------------*/ 00051 template<class K, class Comp> 00052 claw::avl_base<K, Comp>::avl_node::~avl_node() 00053 { 00054 00055 } // avl_node::~avl_node() [destructeur] 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 } // avl_node::duplicate() 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 } // avl_node::del_tree 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 } // avl_node::depth() 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 } // avl_base::avl_node::find() 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 } // avl_base::avl_node::find() 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 } // avl_base::find_nearest_greater() 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 } // avl_base::find_nearest_greater() 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 } // avl_base::find_nearest_lower() 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 } // avl_base::find_nearest_lower() 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 } // avl_base::lower_bound() 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 } // avl_base::lower_bound() 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 } // avl_base::upper_bound() 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 } // avl_base::upper_bound() 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 // node have a right subtree : go to the min 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 // get parent node 00435 while (result->father && !done) 00436 { 00437 if (result->father->left == result) 00438 done = true; 00439 00440 result = result->father; 00441 } 00442 00443 // came back from the max node to the root 00444 if (!done) 00445 result = previous_node; 00446 } 00447 00448 return result; 00449 } // avl_iterator::avl_node::next() 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 // node have a right subtree : go to the min 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 // get parent node 00475 while (result->father && !done) 00476 { 00477 if (result->father->left == result) 00478 done = true; 00479 00480 result = result->father; 00481 } 00482 00483 // came back from the max node to the root 00484 if (!done) 00485 result = previous_node; 00486 } 00487 00488 return result; 00489 } // avl_iterator::avl_node::next() 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 // node have a left subtree : go to the max 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 // get parent node 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 } // avl_iterator::avl_node::prev() 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 // node have a left subtree : go to the max 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 // get parent node 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 } // avl_iterator::avl_node::prev() 00560 00561 00562 00563 00564 00565 /*=================================== private ===============================*/ 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 } // avl_node::depth() 00581 00582 00583 00584 00585 00586 //**************************** avl_base::avl_iterator ************************** 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 } // avl_iterator::avl_iterator() [constructeur] 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 } // avl_iterator::avl_iterator() [constructeur with node] 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 } // avl_iterator::operator++() [preincrement] 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 } // avl_iterator::operator++ [postincrement] 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 } // avl_iterator::operator--() [predecrement] 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 } // avl_iterator::operator-- [postdecrement] 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 } // avl_iterator::operator*() [dereference] 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 } // avl_iterator::operator->() 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 } // avl_iterator::operator==() 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 } // avl_iterator::operator!=() 00727 00728 00729 00730 00731 00732 //************************* avl_base::avl_const_iterator *********************** 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 } // avl_const_iterator::avl_const_iterator() [constructeur] 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 } // avl_const_iterator::avl_const_iterator() [constructeur with node] 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 } // avl_const_iterator::operator++() [preincrement] 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 } // avl_const_iterator::operator++ [postincrement] 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 } // avl_const_iterator::operator--() [predecrement] 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 } // avl_const_iterator::operator-- [postdecrement] 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 } // avl_const_iterator::operator*() [dereference] 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 } // avl_const_iterator::operator->() 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 } // avl_const_iterator::operator==() 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 } // avl_const_iterator::operator!=() 00873 00874 00875 00876 00877 00878 //******************************* avl_base (main) ****************************** 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 } // avl_base::avl_base() [constructeur] 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 } // avl_base::avl_base() [copy constructor] 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 } // avl_base::~avl_base() [destructeur] 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 } // avl_base::insert() 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 } // avl_base::insert() 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 } // avl_base::erase() 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 } // avl_base::clear() 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 } // avl_base::size() 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 } // avl_base::empty() 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 } // avl_base::begin() 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 } // avl_base::begin() 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 } // avl_base::end() 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 } // avl_base::end() 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 } // avl_base::find() 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 } // avl_base::find() 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 } // avl_base::find_nearest_greater() 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 } // avl_base::find_nearest_greater() 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 } // avl_base::find_nearest_lower() 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 } // avl_base::find_nearest_lower() 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 } // avl_base::lower_bound() 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 } // avl_base::lower_bound() 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 } // avl_base::upper_bound() 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 } // avl_base::upper_bound() 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 } // avl_base::operator=() 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 } // avl_base::operator==() 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 } // avl_base::operator!=() 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 } // avl_base::operator<() 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 } // avl_base::operator>() 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 } // avl_base::operator<=() 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 } // avl_base::operator>=() 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 } // avl_base::swap() 01303 01304 /*================================= private =================================*/ 01305 01306 //----------------------------------------------------------------------------- 01307 // We need some methods to check the validity of our trees 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 } // check_less_than() 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 } // check_balance() 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 } // correct_descendant() 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 // get lower and higher bounds, hope they are correct 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 } // validity_check() 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 } // avl_base::make_iterator() 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 } // avl_base::make_const_iterator() 01456 01457 01458 01459 01460 //----------------------------------------------------------------------------- 01461 // Tree management methods 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 // rotate nodes 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 // adjust balance 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 // old_node_balance is 2 too. 01518 node->balance = 0; 01519 node->right->balance = - 1; 01520 break; 01521 } 01522 } // rotate_right() 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 // rotate nodes 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 // adjust balance 01563 switch(old_subtree_balance) 01564 { 01565 case -2 : 01566 // old_node_balance is -2 too. 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 } // rotate_left() 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 } // rotate_left_right() 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 } // rotate_right_left() 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 } // update_balance() 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 } // adjust_balance() 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 } // adjust_balance_left() 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 } // adjust_balance_right() 01700 01701 01702 /*----------------------------------------------------------------------------*/ 01703 // Methods for insertion 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) // this key isn't in use. Let's create a new node 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 // Update balance of the last imbalanced node 01735 update_balance( last_imbalanced, key ); 01736 // then adjust it to be in range [-1, 1] 01737 adjust_balance( last_imbalanced ); 01738 01739 // pointer update after rotation 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 // left child 01747 last_imbalanced_father->left = last_imbalanced; 01748 else 01749 last_imbalanced_father->right = last_imbalanced; 01750 } 01751 } // insert_node() 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; // node for search 01772 bool exists = false; // if this key already exists 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 // find next node 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 } // find_node_reference() 01801 01802 01803 /*----------------------------------------------------------------------------*/ 01804 // Methods for deletion 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 // try to find the key in the left subtree 01826 if ( s_key_less(key, node->key) ) 01827 { 01828 if ( recursive_delete( node->left, key ) ) 01829 result = new_balance( node, -1 ); 01830 } 01831 // try to find the key in the right subtree 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 // we got it ! 01838 { 01839 --m_size; 01840 result = recursive_delete_node( node ); 01841 } 01842 } 01843 01844 return result; 01845 } // recursive_delete() 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 // balance == 0 so as it was != 0 before deletion 01869 // balance of the tree had changed 01870 case 0: return true; 01871 // balance == 2 so it must be 1 before deletion and node 01872 // was deleted in the right subtree 01873 // if after ajusting the balance is equal to 1, it means that 01874 // our subtree got back his old balance (so it's unchanged). 01875 // if it's equal to -1, it means that subtree now lean to the 01876 // otherside. But in those cases, depth didn't changed. 01877 case 2: adjust_balance_left(node); return node->balance == 0; 01878 // same thing but symetric 01879 case -2: adjust_balance_right(node); return node->balance == 0; 01880 default : return false; 01881 } 01882 } // new_balance() 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) // this node doesn't have a lower descendant 01899 { 01900 // Get right subtree of current node 01901 avl_node_ptr right_subtree = node->right; 01902 01903 if (right_subtree) 01904 right_subtree->father = node->father; 01905 01906 // Free memory pointed by the current node 01907 node->clear(); 01908 delete node; 01909 01910 // then rise the old right subtree 01911 node = right_subtree; 01912 01913 return true; 01914 } 01915 else // this node has a lower descendant, let's get it 01916 if ( recursive_delete_max( node->left, node ) ) 01917 { 01918 // left subtree depth has decreased 01919 // so reajust balance (rem. balance is not changed by delete_max) 01920 --(node->balance); 01921 01922 if ( node->balance == -2 ) 01923 { 01924 // old balance was -1 01925 adjust_balance_right(node); 01926 return node->balance == 0; // tell if depth has changed 01927 } 01928 else if ( node->balance == 0 ) 01929 // node had at least one subtree and old balance - 1 == 0 01930 // so old balance = 1 01931 return true; 01932 else // node's balance is -1 01933 // As node's balance is (old balance - 1), node's balance must be -1 01934 // (otherwise old balance is 2, that's impossible) 01935 // So old balance is 0. 01936 // Moreover old node have at least a left subtree. It means that 01937 // old node had 2 subtrees and their depths were equals. 01938 // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1 01939 // We deleted a node in left subtree and so right subtree is 01940 // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1 01941 // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node) 01942 // => Node depth is unchanged. 01943 return false; 01944 } 01945 else // depth is unchanged 01946 return false; 01947 } // recursive_delete_node() 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 ) // We have the maximum 01969 { 01970 // node have only a left subtree if any. 01971 // This subtree has one node, at most. 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 // rise the left subtree 01984 root = left_subtree; 01985 01986 // depth have changed 01987 return true; 01988 } 01989 else // try to find the max in the right subtree 01990 if ( recursive_delete_max( root->right, node ) ) 01991 { 01992 // depth of the subtree changed (ie. decreased) 01993 // so root's tree lean to the left 01994 ++(root->balance); 01995 01996 if (root->balance == 2) // tree is leaning too much 01997 { 01998 // old balance was 1 01999 adjust_balance_left( root ); 02000 return root->balance == 0; // Say if balance is changed 02001 } 02002 else 02003 // if balance is 0, it means that old root leant to the left 02004 // and so his depth changed. 02005 // The other value for balance is 1, in this case 02006 // depth didn't change. See recursive_delete_node code comments. 02007 return root->balance == 0; 02008 } 02009 else // depth of the subtree didn't change 02010 return false; 02011 } // recursive_delete_max()