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

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1