CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5

avl_base.tpp

Go to the documentation of this file.
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-2010 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@yahoo.fr
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()