Claw  1.7.3
avl_base.tpp
1 /*
2  CLAW - a C++ Library Absolutely Wonderful
3 
4  CLAW is a free library without any particular aim but being useful to
5  anyone.
6 
7  Copyright (C) 2005-2011 Julien Jorge
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 
23  contact: julien.jorge@gamned.org
24 */
25 /**
26  * \file avl.tpp
27  * \brief The avl class implementation.
28  * \author Julien Jorge
29  */
30 #include <cassert>
31 
32 //**************************** avl_base::avl_node ******************************
33 
34 /*----------------------------------------------------------------------------*/
35 /**
36  * \brief AVL's node constructor
37  * \param k Value of the node
38  */
39 template<class K, class Comp>
40 claw::avl_base<K, Comp>::avl_node::avl_node( const K& k )
41  : super(), key(k), balance(0), father(NULL)
42 {
43  assert(!super::left);
44  assert(!super::right);
45 } // avl_node::avl_node() [constructeur]
46 
47 /*----------------------------------------------------------------------------*/
48 /**
49  * \brief AVL's node destructor
50  */
51 template<class K, class Comp>
52 claw::avl_base<K, Comp>::avl_node::~avl_node()
53 {
54 
55 } // avl_node::~avl_node() [destructeur]
56 
57 /*----------------------------------------------------------------------------*/
58 /**
59  * \brief Duplicate node and his subtrees.
60  * \param count (out) Count of duplicated nodes.
61  * \remark Count isn't initialized. You should call duplicate with count = 0.
62  */
63 template<class K, class Comp>
64 typename claw::avl_base<K, Comp>::avl_node*
65 claw::avl_base<K, Comp>::avl_node::duplicate( unsigned int& count ) const
66 {
67  avl_node* node_copy = new avl_node(key);
68  ++count;
69  node_copy->balance = balance;
70  node_copy->father = NULL;
71 
72  if (super::left)
73  {
74  node_copy->left = super::left->duplicate(count);
75  node_copy->left->father = node_copy;
76  }
77  else
78  node_copy->left = NULL;
79 
80  if (super::right)
81  {
82  node_copy->right = super::right->duplicate(count);
83  node_copy->right->father = node_copy;
84  }
85  else
86  node_copy->right = NULL;
87 
88  return node_copy;
89 } // avl_node::duplicate()
90 
91 /*----------------------------------------------------------------------------*/
92 /**
93  * \brief Delete current node and his subtrees.
94  * \post left == NULL && right == NULL
95  */
96 template<class K, class Comp>
97 void claw::avl_base<K, Comp>::avl_node::del_tree()
98 {
99  if (super::left)
100  {
101  delete super::left;
102  super::left = NULL;
103  }
104  if (super::right)
105  {
106  delete super::right;
107  super::right = NULL;
108  }
109  assert( !super::left );
110  assert( !super::right );
111 } // avl_node::del_tree
112 
113 /*----------------------------------------------------------------------------*/
114 /**
115  * \brief Get the depth of a tree.
116  * \remark For validity check.
117  * \return 1 + max( this->left->depth(), this->right->depth() )
118  */
119 template<class K, class Comp>
120 unsigned int claw::avl_base<K, Comp>::avl_node::depth() const
121 {
122  unsigned int pl=0, pr=0;
123 
124  if (super::left) pl = super::left->depth();
125  if (super::right) pr = super::right->depth();
126 
127  if (pl > pr)
128  return 1 + pl;
129  else
130  return 1 + pr;
131 } // avl_node::depth()
132 
133 /*----------------------------------------------------------------------------*/
134 /**
135  * \brief Get a pointer on the node of the tree with a specified key.
136  * \param key Key to find.
137  */
138 template<class K, class Comp>
139 typename claw::avl_base<K,Comp>::avl_node*
140 claw::avl_base<K,Comp>::avl_node::find( const K& key )
141 {
142  bool ok = false;
143  avl_node* node = this;
144 
145  while (node && !ok)
146  if ( avl_base<K, Comp>::s_key_less(key, node->key) )
147  node = node->left;
148  else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
149  node = node->right;
150  else
151  ok = true;
152 
153  return node;
154 } // avl_base::avl_node::find()
155 
156 /*----------------------------------------------------------------------------*/
157 /**
158  * \brief Get a pointer on the node of the tree with a specified key.
159  * \param key Key to find.
160  */
161 template<class K, class Comp>
162 const typename claw::avl_base<K,Comp>::avl_node*
163 claw::avl_base<K,Comp>::avl_node::find( const K& key ) const
164 {
165  bool ok = false;
166  const avl_node* node = this;
167 
168  while (node && !ok)
169  if ( avl_base<K, Comp>::s_key_less(key, node->key) )
170  node = node->left;
171  else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
172  node = node->right;
173  else
174  ok = true;
175 
176  return node;
177 } // avl_base::avl_node::find()
178 
179 /*----------------------------------------------------------------------------*/
180 /**
181  * \brief Get an iterator on the nodes of the tree on the key imediatly after
182  * from a specified key.
183  * \param key Key to find.
184  */
185 template<class K, class Comp>
186 typename claw::avl_base<K,Comp>::avl_node*
187 claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key )
188 {
189  bool ok = false;
190  avl_node* node = this;
191  avl_node* prev_node = NULL;
192 
193  while (node && !ok)
194  if ( avl_base<K, Comp>::s_key_less(key, node->key) )
195  {
196  prev_node = node;
197  node = node->left;
198  }
199  else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
200  {
201  prev_node = node;
202  node = node->right;
203  }
204  else
205  ok = true;
206 
207  if (ok)
208  return node->next();
209  else if (prev_node)
210  {
211  if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
212  return prev_node->next();
213  else
214  return prev_node;
215  }
216  else
217  return node;
218 } // avl_base::find_nearest_greater()
219 
220 /*----------------------------------------------------------------------------*/
221 /**
222  * \brief Get an iterator on the nodes of the tree on the key imediatly after
223  * from a specified key.
224  * \param key Key to find.
225  */
226 template<class K, class Comp>
227 const typename claw::avl_base<K,Comp>::avl_node*
228 claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key ) const
229 {
230  bool ok = false;
231  const avl_node* node = this;
232  const avl_node* prev_node = NULL;
233 
234  while (node && !ok)
235  if ( avl_base<K, Comp>::s_key_less(key, node->key) )
236  {
237  prev_node = node;
238  node = node->left;
239  }
240  else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
241  {
242  prev_node = node;
243  node = node->right;
244  }
245  else
246  ok = true;
247 
248  if (ok)
249  return node->next();
250  else if (prev_node)
251  {
252  if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
253  return prev_node->next();
254  else
255  return prev_node;
256  }
257  else
258  return node;
259 } // avl_base::find_nearest_greater()
260 
261 /*----------------------------------------------------------------------------*/
262 /**
263  * \brief Get an iterator on the nodes of the tree on the key imediatly before
264  * from a specified key.
265  * \param key Key to find.
266  */
267 template<class K, class Comp>
268 typename claw::avl_base<K,Comp>::avl_node*
269 claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key )
270 {
271  bool ok = false;
272  avl_node* node = this;
273  avl_node* prev_node = NULL;
274 
275  while (node && !ok)
276  if ( s_key_less(key, node->key) )
277  {
278  prev_node = node;
279  node = node->left;
280  }
281  else if ( s_key_less(node->key, key) )
282  {
283  prev_node = node;
284  node = node->right;
285  }
286  else
287  ok = true;
288 
289  if (ok)
290  return node->prev();
291  else if (prev_node)
292  {
293  if ( s_key_less(key, prev_node->key) )
294  return prev_node;
295  else
296  return prev_node->prev();
297  }
298  else
299  return node;
300 } // avl_base::find_nearest_lower()
301 
302 /*----------------------------------------------------------------------------*/
303 /**
304  * \brief Get an iterator on the nodes of the tree on the key imediatly before
305  * from a specified key.
306  * \param key Key to find.
307  */
308 template<class K, class Comp>
309 const typename claw::avl_base<K,Comp>::avl_node*
310 claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key ) const
311 {
312  bool ok = false;
313  const avl_node* node = this;
314  const avl_node* prev_node = NULL;
315 
316  while (node && !ok)
317  if ( s_key_less(key, node->key) )
318  {
319  prev_node = node;
320  node = node->left;
321  }
322  else if ( s_key_less(node->key, key) )
323  {
324  prev_node = node;
325  node = node->right;
326  }
327  else
328  ok = true;
329 
330  if (ok)
331  return node->prev();
332  else if (prev_node)
333  {
334  if ( s_key_less(key, prev_node->key) )
335  return prev_node;
336  else
337  return prev_node->prev();
338  }
339  else
340  return node;
341 } // avl_base::find_nearest_lower()
342 
343 /*----------------------------------------------------------------------------*/
344 /**
345  * \brief Get a pointer on the lowest value of the tree.
346  */
347 template<class K, class Comp>
348 typename claw::avl_base<K,Comp>::avl_node*
349 claw::avl_base<K,Comp>::avl_node::lower_bound()
350 {
351  avl_node* node = this;
352 
353  if (node)
354  while (node->left)
355  node = node->left;
356 
357  return node;
358 } // avl_base::lower_bound()
359 
360 /*----------------------------------------------------------------------------*/
361 /**
362  * \brief Get a pointer on the lowest value of the tree.
363  */
364 template<class K, class Comp>
365 const typename claw::avl_base<K,Comp>::avl_node*
366 claw::avl_base<K,Comp>::avl_node::lower_bound() const
367 {
368  const avl_node* node = this;
369 
370  if (node)
371  while (node->left)
372  node = node->left;
373 
374  return node;
375 } // avl_base::lower_bound()
376 
377 /*----------------------------------------------------------------------------*/
378 /**
379  * \brief Get a pointer on the greatest value of the tree.
380  */
381 template<class K, class Comp>
382 typename claw::avl_base<K,Comp>::avl_node*
383 claw::avl_base<K,Comp>::avl_node::upper_bound()
384 {
385  avl_node* node = this;
386 
387  if (node)
388  while (node->right)
389  node = node->right;
390 
391  return node;
392 } // avl_base::upper_bound()
393 
394 /*----------------------------------------------------------------------------*/
395 /**
396  * \brief Get a pointer on the greatest value of the tree.
397  */
398 template<class K, class Comp>
399 const typename claw::avl_base<K,Comp>::avl_node*
400 claw::avl_base<K,Comp>::avl_node::upper_bound() const
401 {
402  const avl_node* node = this;
403 
404  if (node)
405  while (node->right)
406  node = node->right;
407 
408  return node;
409 } // avl_base::upper_bound()
410 
411 /*----------------------------------------------------------------------------*/
412 /**
413  * \brief Get the node immediately greater than \a this.
414  */
415 template<class K, class Comp>
416 typename claw::avl_base<K,Comp>::avl_node*
417 claw::avl_base<K,Comp>::avl_node::next()
418 {
419  avl_node* result = this;
420 
421  // node have a right subtree : go to the min
422  if (result->right != NULL)
423  {
424  result = result->right;
425 
426  while (result->left != NULL)
427  result = result->left;
428  }
429  else
430  {
431  bool done = false;
432  avl_node* previous_node = this;
433 
434  // get parent node
435  while (result->father && !done)
436  {
437  if (result->father->left == result)
438  done = true;
439 
440  result = result->father;
441  }
442 
443  // came back from the max node to the root
444  if (!done)
445  result = previous_node;
446  }
447 
448  return result;
449 } // avl_iterator::avl_node::next()
450 
451 /*----------------------------------------------------------------------------*/
452 /**
453  * \brief Get the node immediately greater than \a this.
454  */
455 template<class K, class Comp>
456 const typename claw::avl_base<K,Comp>::avl_node*
457 claw::avl_base<K,Comp>::avl_node::next() const
458 {
459  const avl_node* result = this;
460 
461  // node have a right subtree : go to the min
462  if (result->right != NULL)
463  {
464  result = result->right;
465 
466  while (result->left != NULL)
467  result = result->left;
468  }
469  else
470  {
471  bool done = false;
472  const avl_node* previous_node = this;
473 
474  // get parent node
475  while (result->father && !done)
476  {
477  if (result->father->left == result)
478  done = true;
479 
480  result = result->father;
481  }
482 
483  // came back from the max node to the root
484  if (!done)
485  result = previous_node;
486  }
487 
488  return result;
489 } // avl_iterator::avl_node::next()
490 
491 /*----------------------------------------------------------------------------*/
492 /**
493  * \brief Get the node immediately before \a this.
494  */
495 template<class K, class Comp>
496 typename claw::avl_base<K,Comp>::avl_node*
497 claw::avl_base<K,Comp>::avl_node::prev()
498 {
499  avl_node* result = this;
500 
501  // node have a left subtree : go to the max
502  if (result->left != NULL)
503  {
504  result = result->left;
505 
506  while (result->right != NULL)
507  result = result->right;
508  }
509  else
510  {
511  bool done = false;
512 
513  // get parent node
514  while (result->father && !done)
515  {
516  if (result->father->right == result)
517  done = true;
518 
519  result = result->father;
520  }
521  }
522 
523  return result;
524 } // avl_iterator::avl_node::prev()
525 
526 /*----------------------------------------------------------------------------*/
527 /**
528  * \brief Get the node immediately before \a this.
529  */
530 template<class K, class Comp>
531 const typename claw::avl_base<K,Comp>::avl_node*
532 claw::avl_base<K,Comp>::avl_node::prev() const
533 {
534  const avl_node* result = this;
535 
536  // node have a left subtree : go to the max
537  if (result->left != NULL)
538  {
539  result = result->left;
540 
541  while (result->right != NULL)
542  result = result->right;
543  }
544  else
545  {
546  bool done = false;
547 
548  // get parent node
549  while (result->father && !done)
550  {
551  if (result->father->right == result)
552  done = true;
553 
554  result = result->father;
555  }
556  }
557 
558  return result;
559 } // avl_iterator::avl_node::prev()
560 
561 
562 
563 
564 
565 /*=================================== private ===============================*/
566 
567 
568 
569 /*----------------------------------------------------------------------------*/
570 /**
571  * \brief Copy constructor.
572  * \param that Node to copy from.
573  * \remark Shouldn't be use.
574  */
575 template<class K, class Comp>
576 claw::avl_base<K, Comp>::avl_node::avl_node( const avl_node& that )
577  : super(that), key(that.key), balance(that.balance), father(NULL)
578 {
579  assert(0);
580 } // avl_node::depth()
581 
582 
583 
584 
585 
586 //**************************** avl_base::avl_iterator **************************
587 
588 
589 
590 /*----------------------------------------------------------------------------*/
591 /**
592  * \brief Constructor.
593  */
594 template<class K, class Comp>
595 claw::avl_base<K,Comp>::avl_iterator::avl_iterator()
596  : m_current(NULL), m_is_final(true)
597 {
598 
599 } // avl_iterator::avl_iterator() [constructeur]
600 
601 /*----------------------------------------------------------------------------*/
602 /**
603  * \brief Constructor.
604  */
605 template<class K, class Comp>
606 claw::avl_base<K,Comp>::avl_iterator::avl_iterator
607 ( avl_node_ptr node, bool final )
608  : m_current(node), m_is_final(final)
609 {
610 
611 } // avl_iterator::avl_iterator() [constructeur with node]
612 
613 /*----------------------------------------------------------------------------*/
614 /**
615  * \brief Preincrement.
616  * \pre not final(this).
617  */
618 template<class K, class Comp>
619 typename claw::avl_base<K,Comp>::avl_iterator&
620 claw::avl_base<K,Comp>::avl_iterator::operator++()
621 {
622  assert(!m_is_final);
623  assert(m_current);
624 
625  avl_node* p = m_current->next();
626 
627  if ( m_current == p )
628  m_is_final = true;
629  else
630  m_current = p;
631 
632  return *this;
633 } // avl_iterator::operator++() [preincrement]
634 
635 /*----------------------------------------------------------------------------*/
636 /**
637  * \brief Postincrement.
638  */
639 template<class K, class Comp>
640 typename claw::avl_base<K,Comp>::avl_iterator
641 claw::avl_base<K,Comp>::avl_iterator::operator++(int)
642 {
643  avl_iterator it = *this;
644  ++(*this);
645  return it;
646 } // avl_iterator::operator++ [postincrement]
647 
648 /*----------------------------------------------------------------------------*/
649 /**
650  * \brief Predecrement.
651  * \pre iterator is not at the begining of the container.
652  */
653 template<class K, class Comp>
654 typename claw::avl_base<K,Comp>::avl_iterator&
655 claw::avl_base<K,Comp>::avl_iterator::operator--()
656 {
657  assert(m_current);
658 
659  if (m_is_final)
660  m_is_final = !m_is_final;
661  else
662  m_current = m_current->prev();
663 
664  assert(m_current != NULL);
665 
666  return *this;
667 } // avl_iterator::operator--() [predecrement]
668 
669 /*----------------------------------------------------------------------------*/
670 /**
671  * \brief Postdecrement.
672  */
673 template<class K, class Comp>
674 typename claw::avl_base<K,Comp>::avl_iterator
675 claw::avl_base<K,Comp>::avl_iterator::operator--(int)
676 {
677  avl_iterator it = *this;
678  --(*this);
679  return it;
680 } // avl_iterator::operator-- [postdecrement]
681 
682 /*----------------------------------------------------------------------------*/
683 /**
684  * \brief Dereference.
685  */
686 template<class K, class Comp>
687 typename claw::avl_base<K,Comp>::avl_iterator::reference
688 claw::avl_base<K,Comp>::avl_iterator::operator*() const
689 {
690  return m_current->key;
691 } // avl_iterator::operator*() [dereference]
692 
693 /*----------------------------------------------------------------------------*/
694 /**
695  * \brief Reference.
696  */
697 template<class K, class Comp>
698 typename claw::avl_base<K,Comp>::avl_iterator::pointer
699 claw::avl_base<K,Comp>::avl_iterator::operator->() const
700 {
701  return &m_current->key;
702 } // avl_iterator::operator->()
703 
704 /*----------------------------------------------------------------------------*/
705 /**
706  * \brief Equality.
707  * \param it Iterator to compare to.
708  */
709 template<class K, class Comp>
710 bool
711 claw::avl_base<K,Comp>::avl_iterator::operator==(const avl_iterator& it) const
712 {
713  return (m_current == it.m_current) && (m_is_final == it.m_is_final);
714 } // avl_iterator::operator==()
715 
716 /*----------------------------------------------------------------------------*/
717 /**
718  * \brief Difference.
719  * \param it Iterator to compare to.
720  */
721 template<class K, class Comp>
722 bool
723 claw::avl_base<K,Comp>::avl_iterator::operator!=(const avl_iterator& it) const
724 {
725  return !( *this == it );
726 } // avl_iterator::operator!=()
727 
728 
729 
730 
731 
732 //************************* avl_base::avl_const_iterator ***********************
733 
734 
735 
736 /*----------------------------------------------------------------------------*/
737 /**
738  * \brief Constructor.
739  */
740 template<class K, class Comp>
741 claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator()
742  : m_current(NULL), m_is_final(true)
743 {
744 
745 } // avl_const_iterator::avl_const_iterator() [constructeur]
746 
747 /*----------------------------------------------------------------------------*/
748 /**
749  * \brief Constructor.
750  */
751 template<class K, class Comp>
752 claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator
753 ( const_avl_node_ptr node, bool final )
754  : m_current(node), m_is_final(final)
755 {
756 
757 } // avl_const_iterator::avl_const_iterator() [constructeur with node]
758 
759 /*----------------------------------------------------------------------------*/
760 /**
761  * \brief Preincrement.
762  * \pre not final(this).
763  */
764 template<class K, class Comp>
765 typename claw::avl_base<K,Comp>::avl_const_iterator&
766 claw::avl_base<K,Comp>::avl_const_iterator::operator++()
767 {
768  assert(!m_is_final);
769  assert(m_current);
770 
771  const_avl_node_ptr p = m_current->next();
772 
773  if ( m_current == p )
774  m_is_final = true;
775  else
776  m_current = p;
777 
778  return *this;
779 } // avl_const_iterator::operator++() [preincrement]
780 
781 /*----------------------------------------------------------------------------*/
782 /**
783  * \brief Postincrement.
784  */
785 template<class K, class Comp>
786 typename claw::avl_base<K,Comp>::avl_const_iterator
787 claw::avl_base<K,Comp>::avl_const_iterator::operator++(int)
788 {
789  avl_const_iterator it = *this;
790  ++(*this);
791  return it;
792 } // avl_const_iterator::operator++ [postincrement]
793 
794 /*----------------------------------------------------------------------------*/
795 /**
796  * \brief Predecrement.
797  * \pre iterator is not at the begining of the container.
798  */
799 template<class K, class Comp>
800 typename claw::avl_base<K,Comp>::avl_const_iterator&
801 claw::avl_base<K,Comp>::avl_const_iterator::operator--()
802 {
803  assert(m_current);
804 
805  if (m_is_final)
806  m_is_final = !m_is_final;
807  else
808  m_current = m_current->prev();
809 
810  assert(m_current != NULL);
811 
812  return *this;
813 } // avl_const_iterator::operator--() [predecrement]
814 
815 /*----------------------------------------------------------------------------*/
816 /**
817  * \brief Postdecrement.
818  */
819 template<class K, class Comp>
820 typename claw::avl_base<K,Comp>::avl_const_iterator
821 claw::avl_base<K,Comp>::avl_const_iterator::operator--(int)
822 {
823  avl_const_iterator it = *this;
824  --(*this);
825  return it;
826 } // avl_const_iterator::operator-- [postdecrement]
827 
828 /*----------------------------------------------------------------------------*/
829 /**
830  * \brief Dereference.
831  */
832 template<class K, class Comp>
833 typename claw::avl_base<K,Comp>::avl_const_iterator::reference
834 claw::avl_base<K,Comp>::avl_const_iterator::operator*() const
835 {
836  return m_current->key;
837 } // avl_const_iterator::operator*() [dereference]
838 
839 /*----------------------------------------------------------------------------*/
840 /**
841  * \brief Reference.
842  */
843 template<class K, class Comp>
844 typename claw::avl_base<K,Comp>::avl_const_iterator::pointer
845 claw::avl_base<K,Comp>::avl_const_iterator::operator->() const
846 {
847  return &m_current->key;
848 } // avl_const_iterator::operator->()
849 
850 /*----------------------------------------------------------------------------*/
851 /**
852  * \brief Equality.
853  * \param it Iterator to compare to.
854  */
855 template<class K, class Comp>
856 bool claw::avl_base<K,Comp>::avl_const_iterator::operator==
857 (const avl_const_iterator& it) const
858 {
859  return (m_current == it.m_current) && (m_is_final == it.m_is_final);
860 } // avl_const_iterator::operator==()
861 
862 /*----------------------------------------------------------------------------*/
863 /**
864  * \brief Difference.
865  * \param it Iterator to compare to.
866  */
867 template<class K, class Comp>
868 bool claw::avl_base<K,Comp>::avl_const_iterator::operator!=
869 (const avl_const_iterator& it) const
870 {
871  return !( *this == it );
872 } // avl_const_iterator::operator!=()
873 
874 
875 
876 
877 
878 //******************************* avl_base (main) ******************************
879 
880 
881 /*----------------------------------------------------------------------------*/
882 template<class K, class Comp>
883 typename claw::avl_base<K,Comp>::key_less claw::avl_base<K,Comp>::s_key_less;
884 
885 /*----------------------------------------------------------------------------*/
886 /**
887  * \brief AVL constructor.
888  * \post empty()
889  */
890 template<class K, class Comp>
891 claw::avl_base<K,Comp>::avl_base()
892  : m_size(0), m_tree(NULL)
893 {
894 
895 } // avl_base::avl_base() [constructeur]
896 
897 /*----------------------------------------------------------------------------*/
898 /**
899  * \brief AVL copy constructor.
900  * \param that AVL instance to copy from.
901  */
902 template<class K, class Comp>
903 claw::avl_base<K,Comp>::avl_base( const avl_base<K, Comp>& that )
904 {
905  m_size = 0;
906 
907  if (that.m_tree)
908  m_tree = that.m_tree->duplicate( m_size );
909  else
910  m_tree = NULL;
911 } // avl_base::avl_base() [copy constructor]
912 
913 /*----------------------------------------------------------------------------*/
914 /**
915  * \brief AVL destructor.
916  */
917 template<class K, class Comp>
918 claw::avl_base<K,Comp>::~avl_base()
919 {
920  if (m_tree)
921  {
922  m_tree->del_tree();
923  delete m_tree;
924  }
925 } // avl_base::~avl_base() [destructeur]
926 
927 /*----------------------------------------------------------------------------*/
928 /**
929  * \brief Add a value in a tree.
930  * \param key Node key.
931  * \post exists(key)
932  */
933 template<class K, class Comp>
934 void claw::avl_base<K,Comp>::insert( const K& key )
935 {
936  assert( validity_check() );
937 
938  if ( m_tree == NULL )
939  {
940  m_tree = new avl_node(key);
941  m_size = 1;
942  }
943  else
944  insert_node(key);
945 
946  assert( validity_check() );
947 } // avl_base::insert()
948 
949 /*----------------------------------------------------------------------------*/
950 /**
951  * \brief Add a range of items in the tree.
952  * \param first Iterator on the first item to add.
953  * \param last Iterator past the last item to add.
954  * \pre Iterator::value_type is K
955  * \post exists( *it ) for all it in [first, last)
956  */
957 template<class K, class Comp>
958 template<typename Iterator>
959 void claw::avl_base<K,Comp>::insert( Iterator first, Iterator last )
960 {
961  for ( ; first!=last; ++first )
962  insert( *first );
963 } // avl_base::insert()
964 
965 /*----------------------------------------------------------------------------*/
966 /**
967  * \brief Delete a value in a tree.
968  * \param key Node key.
969  * \post not exists(key)
970  */
971 template<class K, class Comp>
972 void claw::avl_base<K,Comp>::erase( const K& key )
973 {
974  assert( validity_check() );
975 
976  if (m_tree != NULL)
977  recursive_delete( m_tree, key );
978 
979  assert( validity_check() );
980 } // avl_base::erase()
981 
982 /*----------------------------------------------------------------------------*/
983 /**
984  * \brief Clear a tree.
985  * \post empty()
986  */
987 template<class K, class Comp>
988 void claw::avl_base<K,Comp>::clear()
989 {
990  if (m_tree != NULL)
991  {
992  m_tree->del_tree();
993  delete m_tree;
994 
995  m_tree = NULL;
996  m_size = 0;
997  }
998 } // avl_base::clear()
999 
1000 /*----------------------------------------------------------------------------*/
1001 /**
1002  * \brief Get the size of a tree.
1003  * \return The size of the tree.
1004  */
1005 template<class K, class Comp>
1006 inline unsigned int claw::avl_base<K,Comp>::size() const
1007 {
1008  return m_size;
1009 } // avl_base::size()
1010 
1011 /*----------------------------------------------------------------------------*/
1012 /**
1013  * \brief Tell if a tree is empty or not.
1014  * \return true if the tree is empty, false otherwise.
1015  */
1016 template<class K, class Comp>
1017 inline bool claw::avl_base<K,Comp>::empty() const
1018 {
1019  return m_size == 0;
1020 } // avl_base::empty()
1021 
1022 /*----------------------------------------------------------------------------*/
1023 /**
1024  * \brief Get an iterator on the nodes of the tree.
1025  */
1026 template<class K, class Comp>
1027 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::begin()
1028 {
1029  if (m_tree == NULL)
1030  return iterator(NULL, true);
1031  else
1032  return lower_bound();
1033 } // avl_base::begin()
1034 
1035 /*----------------------------------------------------------------------------*/
1036 /**
1037  * \brief Get an iterator on the nodes of the tree.
1038  */
1039 template<class K, class Comp>
1040 typename claw::avl_base<K,Comp>::const_iterator
1041 claw::avl_base<K,Comp>::begin() const
1042 {
1043  if (m_tree == NULL)
1044  return const_iterator(NULL, true);
1045  else
1046  return lower_bound();
1047 } // avl_base::begin()
1048 
1049 /*----------------------------------------------------------------------------*/
1050 /**
1051  * \brief Get an iterator after the end of the tree.
1052  */
1053 template<class K, class Comp>
1054 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::end()
1055 {
1056  if (m_tree == NULL)
1057  return iterator(NULL, true);
1058  else
1059  return iterator(m_tree->upper_bound(), true);
1060 } // avl_base::end()
1061 
1062 /*----------------------------------------------------------------------------*/
1063 /**
1064  * \brief Get an iterator after the end of the tree.
1065  */
1066 template<class K, class Comp>
1067 typename claw::avl_base<K,Comp>::const_iterator
1068 claw::avl_base<K,Comp>::end() const
1069 {
1070  if (m_tree == NULL)
1071  return const_iterator(NULL, true);
1072  else
1073  return const_iterator(m_tree->upper_bound(), true);
1074 } // avl_base::end()
1075 
1076 /*----------------------------------------------------------------------------*/
1077 /**
1078  * \brief Get an iterator on the nodes of the tree from a specified key.
1079  * \param key Key to find.
1080  */
1081 template<class K, class Comp>
1082 typename claw::avl_base<K,Comp>::iterator
1083 claw::avl_base<K,Comp>::find( const K& key )
1084 {
1085  return make_iterator( m_tree->find(key) );
1086 } // avl_base::find()
1087 
1088 /*----------------------------------------------------------------------------*/
1089 /**
1090  * \brief Get an iterator on the nodes of the tree from a specified key.
1091  * \param key Key to find.
1092  */
1093 template<class K, class Comp>
1094 typename claw::avl_base<K,Comp>::const_iterator
1095 claw::avl_base<K,Comp>::find( const K& key ) const
1096 {
1097  return make_const_iterator( m_tree->find(key) );
1098 } // avl_base::find()
1099 
1100 /*----------------------------------------------------------------------------*/
1101 /**
1102  * \brief Get an iterator on the nodes of the tree on the key imediatly after
1103  * from a specified key.
1104  * \param key Key to find.
1105  */
1106 template<class K, class Comp>
1107 typename claw::avl_base<K,Comp>::iterator
1108 claw::avl_base<K,Comp>::find_nearest_greater( const K& key )
1109 {
1110  return make_iterator( m_tree->find_nearest_greater(key) );
1111 } // avl_base::find_nearest_greater()
1112 
1113 /*----------------------------------------------------------------------------*/
1114 /**
1115  * \brief Get an iterator on the nodes of the tree on the key imediatly after
1116  * from a specified key.
1117  * \param key Key to find.
1118  */
1119 template<class K, class Comp>
1120 typename claw::avl_base<K,Comp>::const_iterator
1121 claw::avl_base<K,Comp>::find_nearest_greater( const K& key ) const
1122 {
1123  return make_const_iterator( m_tree->find_nearest_greater(key) );
1124 } // avl_base::find_nearest_greater()
1125 
1126 /*----------------------------------------------------------------------------*/
1127 /**
1128  * \brief Get an iterator on the nodes of the tree on the key imediatly before
1129  * from a specified key.
1130  * \param key Key to find.
1131  */
1132 template<class K, class Comp>
1133 typename claw::avl_base<K,Comp>::iterator
1134 claw::avl_base<K,Comp>::find_nearest_lower( const K& key )
1135 {
1136  return make_iterator( m_tree->find_nearest_lower(key) );
1137 } // avl_base::find_nearest_lower()
1138 
1139 /*----------------------------------------------------------------------------*/
1140 /**
1141  * \brief Get an iterator on the nodes of the tree on the key imediatly before
1142  * from a specified key.
1143  * \param key Key to find.
1144  */
1145 template<class K, class Comp>
1146 typename claw::avl_base<K,Comp>::const_iterator
1147 claw::avl_base<K,Comp>::find_nearest_lower( const K& key ) const
1148 {
1149  return make_const_iterator( m_tree->find_nearest_lower(key) );
1150 } // avl_base::find_nearest_lower()
1151 
1152 /*----------------------------------------------------------------------------*/
1153 /**
1154  * \brief Get an iterator on the lowest value of the tree.
1155  */
1156 template<class K, class Comp>
1157 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::lower_bound()
1158 {
1159  return make_iterator( m_tree->lower_bound() );
1160 } // avl_base::lower_bound()
1161 
1162 /*----------------------------------------------------------------------------*/
1163 /**
1164  * \brief Get an iterator on the lowest value of the tree.
1165  */
1166 template<class K, class Comp>
1167 typename claw::avl_base<K,Comp>::const_iterator
1168 claw::avl_base<K,Comp>::lower_bound() const
1169 {
1170  return make_const_iterator( m_tree->lower_bound() );
1171 } // avl_base::lower_bound()
1172 
1173 /*----------------------------------------------------------------------------*/
1174 /**
1175  * \brief Get an iterator on the gratest value of the tree.
1176  */
1177 template<class K, class Comp>
1178 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::upper_bound()
1179 {
1180  return make_iterator( m_tree->upper_bound() );
1181 } // avl_base::upper_bound()
1182 
1183 /*----------------------------------------------------------------------------*/
1184 /**
1185  * \brief Get an iterator on the gratest value of the tree.
1186  */
1187 template<class K, class Comp>
1188 typename claw::avl_base<K,Comp>::const_iterator
1189 claw::avl_base<K,Comp>::upper_bound() const
1190 {
1191  return make_const_iterator( m_tree->upper_bound() );
1192 } // avl_base::upper_bound()
1193 
1194 /*----------------------------------------------------------------------------*/
1195 /**
1196  * \brief Assignment operator
1197  * \param that AVL instance to copy from.
1198  */
1199 template<class K, class Comp>
1200 claw::avl_base<K, Comp>&
1201 claw::avl_base<K, Comp>::operator=( const avl_base<K, Comp>& that )
1202 {
1203  if (this != &that)
1204  {
1205  if (m_tree)
1206  {
1207  m_tree->del_tree();
1208  delete m_tree;
1209  }
1210 
1211  m_size = 0;
1212 
1213  if (that.m_tree)
1214  m_tree = that.m_tree->duplicate( m_size );
1215  else
1216  m_tree = NULL;
1217  }
1218 
1219  return *this;
1220 } // avl_base::operator=()
1221 
1222 /*----------------------------------------------------------------------------*/
1223 /**
1224  * \brief Equality.
1225  * \param that AVL top compare to.
1226  */
1227 template<class K, class Comp>
1228 bool claw::avl_base<K, Comp>::operator==( const avl_base<K, Comp>& that ) const
1229 {
1230  if (m_size != that.m_size)
1231  return false;
1232  else
1233  return std::equal( begin(), end(), that.begin(), s_key_less );
1234 } // avl_base::operator==()
1235 
1236 /*----------------------------------------------------------------------------*/
1237 /**
1238  * \brief Disequality.
1239  * \param that AVL top compare to.
1240  */
1241 template<class K, class Comp>
1242 bool claw::avl_base<K, Comp>::operator!=( const avl_base<K, Comp>& that ) const
1243 {
1244  return !( *this == that );
1245 } // avl_base::operator!=()
1246 
1247 /*----------------------------------------------------------------------------*/
1248 /**
1249  * \brief Less than operator.
1250  * \param that AVL top compare to.
1251  */
1252 template<class K, class Comp>
1253 bool claw::avl_base<K, Comp>::operator<( const avl_base<K, Comp>& that ) const
1254 {
1255  return std::lexicographical_compare
1256  ( begin(), end(), that.begin(), that.end(), s_key_less );
1257 } // avl_base::operator<()
1258 
1259 /*----------------------------------------------------------------------------*/
1260 /**
1261  * \brief Greater than operator.
1262  * \param that AVL top compare to.
1263  */
1264 template<class K, class Comp>
1265 bool claw::avl_base<K, Comp>::operator>( const avl_base<K, Comp>& that ) const
1266 {
1267  return that < *this;
1268 } // avl_base::operator>()
1269 
1270 /*----------------------------------------------------------------------------*/
1271 /**
1272  * \brief Less or equal operator.
1273  * \param that AVL top compare to.
1274  */
1275 template<class K, class Comp>
1276 bool claw::avl_base<K, Comp>::operator<=( const avl_base<K, Comp>& that ) const
1277 {
1278  return !( that < *this );
1279 } // avl_base::operator<=()
1280 
1281 /*----------------------------------------------------------------------------*/
1282 /**
1283  * \brief Greater or equal operator.
1284  * \param that AVL top compare to.
1285  */
1286 template<class K, class Comp>
1287 bool claw::avl_base<K, Comp>::operator>=( const avl_base<K, Comp>& that ) const
1288 {
1289  return !( *this < that );
1290 } // avl_base::operator>=()
1291 
1292 /*----------------------------------------------------------------------------*/
1293 /**
1294  * \brief Swap the values with an other tree.
1295  * \param that The other tree.
1296  */
1297 template<class K, class Comp>
1298 void claw::avl_base<K, Comp>::swap( avl_base<K, Comp>& that )
1299 {
1300  std::swap(m_size, that.m_size);
1301  std::swap(m_tree, that.m_tree);
1302 } // avl_base::swap()
1303 
1304 /*================================= private =================================*/
1305 
1306 //-----------------------------------------------------------------------------
1307 // We need some methods to check the validity of our trees
1308 
1309 /*----------------------------------------------------------------------------*/
1310 /**
1311  * \brief This method will check order in our trees.
1312  * \param node Root of the tree to check.
1313  * \param min Lower bound of the valid range for tree's nodes.
1314  * \param max Higher bound of the valid range for tree's nodes.
1315  * \remark For validity check.
1316  * \return true if bounds are ok, false otherwise.
1317  */
1318 template<class K, class Comp>
1319 bool claw::avl_base<K,Comp>::check_in_bounds
1320 ( const avl_node_ptr node, const K& min, const K& max ) const
1321 {
1322  if (node == NULL)
1323  return true;
1324  else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) )
1325  return (node->left == NULL)
1326  && check_in_bounds( node->right, node->key, max );
1327  else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) )
1328  return (node->right == NULL)
1329  && check_in_bounds( node->left, min, node->key );
1330  else
1331  return s_key_less(node->key, max) && s_key_less(min, node->key)
1332  && check_in_bounds( node->left, min, node->key )
1333  && check_in_bounds( node->right, node->key, max );
1334 } // check_less_than()
1335 
1336 /*----------------------------------------------------------------------------*/
1337 /**
1338  * \brief This method will check balance in our trees.
1339  * \param node Root of the tree to check.
1340  * \remark For validity check.
1341  * \return true if the absolute difference between left subtree's depth and
1342  * right subtree's depth is 1 for node and each of its subtrees.
1343  * false otherwise.
1344  */
1345 template<class K, class Comp>
1346 bool claw::avl_base<K,Comp>::check_balance( const avl_node_ptr node ) const
1347 {
1348  int pl=0, pr=0;
1349 
1350  if (node == NULL)
1351  return true;
1352  else
1353  {
1354  if (node->left) pl = node->left->depth();
1355  if (node->right) pr = node->right->depth();
1356 
1357  return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
1358  && check_balance(node->left) && check_balance(node->right);
1359  }
1360 } // check_balance()
1361 
1362 /*----------------------------------------------------------------------------*/
1363 /**
1364  * \brief This method will check if each node is a son of his father.
1365  * \param node Node to check.
1366  * \remark For validity check.
1367  * \return true if the AVL is valid, false otherwise.
1368  */
1369 template<class K, class Comp>
1370 bool claw::avl_base<K,Comp>::correct_descendant( const avl_node_ptr node ) const
1371 {
1372  bool valid = true;
1373 
1374  if (node != NULL)
1375  {
1376  if (node->father != NULL)
1377  {
1378  valid = (node->father->left == node) ^ (node->father->right == node);
1379  valid = valid && correct_descendant( node->left )
1380  && correct_descendant( node->right );
1381  }
1382  else
1383  valid = false;
1384  }
1385 
1386  return valid;
1387 } // correct_descendant()
1388 
1389 /*----------------------------------------------------------------------------*/
1390 /**
1391  * \brief This method will check orderliness in our trees : balance and order.
1392  *
1393  * \remark For validity check.
1394  * \return true if the AVL is valid, false otherwise.
1395  */
1396 template<class K, class Comp>
1397 bool claw::avl_base<K,Comp>::validity_check() const
1398 {
1399  bool valid = true;
1400 
1401  if (m_tree != NULL)
1402  {
1403  avl_node *node_min, *node_max;
1404 
1405  // get lower and higher bounds, hope they are correct
1406  for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left);
1407  for (node_max = m_tree; node_max->right!=NULL;
1408  node_max = node_max->right);
1409 
1410  valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
1411  valid = valid
1412  && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
1413 
1414  valid = valid && (m_tree->father == NULL)
1415  && correct_descendant( m_tree->left )
1416  && correct_descendant( m_tree->right );
1417 
1418  }
1419 
1420  return valid && check_balance(m_tree);
1421 } // validity_check()
1422 
1423 
1424 
1425 
1426 
1427 /*----------------------------------------------------------------------------*/
1428 /**
1429  * \brief Create an iterator from a pointer to a node.
1430  * \param node The node on which we want the iterator.
1431  */
1432 template<class K, class Comp>
1433 typename claw::avl_base<K,Comp>::iterator
1434 claw::avl_base<K,Comp>::make_iterator( avl_node_ptr node ) const
1435 {
1436  if (node != NULL)
1437  return iterator(node, false);
1438  else
1439  return end();
1440 } // avl_base::make_iterator()
1441 
1442 /*----------------------------------------------------------------------------*/
1443 /**
1444  * \brief Create an iterator from a pointer to a node.
1445  * \param node The node on which we want the iterator.
1446  */
1447 template<class K, class Comp>
1448 typename claw::avl_base<K,Comp>::const_iterator
1449 claw::avl_base<K,Comp>::make_const_iterator( const_avl_node_ptr node ) const
1450 {
1451  if (node != NULL)
1452  return const_iterator(node, false);
1453  else
1454  return end();
1455 } // avl_base::make_const_iterator()
1456 
1457 
1458 
1459 
1460 //-----------------------------------------------------------------------------
1461 // Tree management methods
1462 
1463 /*----------------------------------------------------------------------------*/
1464 /**
1465  * \brief Node right rotation
1466  * \param node Node to rotate.
1467  * \pre (node != NULL) && node->left != NULL
1468  * \pre node->balance in [1,2] and node->left->balance in [-1,2]
1469  * \pre (node->left->balance == 2) ==> (node->balance == 2)
1470  */
1471 template<class K, class Comp>
1472 void claw::avl_base<K,Comp>::rotate_right( avl_node_ptr& node )
1473 {
1474  avl_node_ptr p;
1475  char old_node_balance;
1476  char old_subtree_balance;
1477 
1478  assert( node != NULL );
1479  assert( node->left != NULL );
1480  assert( (1 <= node->balance) && (node->balance <= 2) ) ;
1481  assert( (-1 <= node->left->balance) && (node->left->balance <= 2) );
1482  assert( (node->left->balance != 2) || (node->balance == 2) );
1483 
1484  old_node_balance = node->balance;
1485  old_subtree_balance = node->left->balance;
1486 
1487  // rotate nodes
1488  p = node->left;
1489  p->father = node->father;
1490 
1491  node->left = p->right;
1492 
1493  if (p->right)
1494  p->right->father = node;
1495 
1496  p->right = node;
1497  node->father = p;
1498 
1499  node = p;
1500 
1501  // adjust balance
1502  switch(old_subtree_balance)
1503  {
1504  case -1 :
1505  node->balance = -2;
1506  node->right->balance = old_node_balance - 1;
1507  break;
1508  case 0 :
1509  node->balance = -1;
1510  node->right->balance = old_node_balance - 1;
1511  break;
1512  case 1 :
1513  node->balance = old_node_balance - 2;
1514  node->right->balance = old_node_balance - 2;
1515  break;
1516  case 2 :
1517  // old_node_balance is 2 too.
1518  node->balance = 0;
1519  node->right->balance = - 1;
1520  break;
1521  }
1522 } // rotate_right()
1523 
1524 /*----------------------------------------------------------------------------*/
1525 /**
1526  * \brief Node left rotation
1527  * \param node Node to rotate.
1528  * \pre (node != NULL) && node->right != NULL
1529  * \pre node->balance in [-2,-1] and node->right->balance in [-2,1]
1530  * \pre (node->right->balance == -2) ==> (node->balance == -2)
1531  */
1532 template<class K, class Comp>
1533 void claw::avl_base<K,Comp>::rotate_left( avl_node_ptr& node )
1534 {
1535  avl_node_ptr p;
1536  char old_node_balance;
1537  char old_subtree_balance;
1538 
1539  assert( node != NULL );
1540  assert( node->right != NULL );
1541  assert( (-2 <= node->balance) && (node->balance <= -1) ) ;
1542  assert( (-2 <= node->right->balance) && (node->right->balance <= 1) );
1543  assert( (node->right->balance != -2) || (node->balance == -2) );
1544 
1545  old_node_balance = node->balance;
1546  old_subtree_balance = node->right->balance;
1547 
1548  // rotate nodes
1549  p = node->right;
1550  p->father = node->father;
1551 
1552  node->right = p->left;
1553 
1554  if (p->left)
1555  p->left->father = node;
1556 
1557  p->left = node;
1558  node->father = p;
1559 
1560  node = p;
1561 
1562  // adjust balance
1563  switch(old_subtree_balance)
1564  {
1565  case -2 :
1566  // old_node_balance is -2 too.
1567  node->balance = 0;
1568  node->left->balance = 1;
1569  break;
1570  case -1 :
1571  node->balance = old_node_balance + 2;
1572  node->left->balance = old_node_balance + 2;
1573  break;
1574  case 0 :
1575  node->balance = 1;
1576  node->left->balance = old_node_balance + 1;
1577  break;
1578  case 1 :
1579  node->balance = 2;
1580  node->left->balance = old_node_balance + 1;
1581  break;
1582  }
1583 } // rotate_left()
1584 
1585 /*----------------------------------------------------------------------------*/
1586 /**
1587  * \brief Node left-right rotation
1588  * \param node Node to rotate.
1589  */
1590 template<class K, class Comp>
1591 void claw::avl_base<K,Comp>::rotate_left_right( avl_node_ptr& node )
1592 {
1593  assert( node != NULL );
1594 
1595  rotate_left( node->left );
1596  rotate_right( node );
1597 } // rotate_left_right()
1598 
1599 /*----------------------------------------------------------------------------*/
1600 /**
1601  * \brief Node right-left rotation
1602  * \param node Node to rotate.
1603  */
1604 template<class K, class Comp>
1605 void claw::avl_base<K,Comp>::rotate_right_left( avl_node_ptr& node )
1606 {
1607  assert( node != NULL );
1608 
1609  rotate_right( node->right );
1610  rotate_left( node );
1611 } // rotate_right_left()
1612 
1613 /*----------------------------------------------------------------------------*/
1614 /**
1615  * \brief Update balance of each node by increasing depth of the substree
1616  * containing key, from node to the node key.
1617  * \param node Root of the subtree to update.
1618  * \param key Key of the just-added node.
1619  * \pre (node != NULL) && ( key is in the tree starting from root node )
1620  * \post balance is ok for each node from node to key
1621  */
1622 template<class K, class Comp>
1623 void claw::avl_base<K,Comp>::update_balance( avl_node_ptr node, const K& key )
1624 {
1625  assert(node != NULL);
1626  bool done = false;
1627 
1628  while (!done)
1629  if ( s_key_less(key, node->key) )
1630  {
1631  ++node->balance;
1632  node = node->left;
1633  }
1634  else if ( s_key_less(node->key, key) )
1635  {
1636  --node->balance;
1637  node = node->right;
1638  }
1639  else
1640  done = true;
1641 } // update_balance()
1642 
1643 /*----------------------------------------------------------------------------*/
1644 /**
1645  * \brief Adjust balance of a node so it will be in range [-1;1].
1646  * \param node Node to adjust.
1647  * \pre (node != NULL).
1648  * \post node->balance is in range [-1;1]
1649  */
1650 template<class K, class Comp>
1651 void claw::avl_base<K,Comp>::adjust_balance( avl_node_ptr& node )
1652 {
1653  assert(node != NULL);
1654 
1655  if ( node->balance == 2)
1656  adjust_balance_left(node);
1657  else if ( node->balance == -2)
1658  adjust_balance_right(node);
1659 } // adjust_balance()
1660 
1661 /*----------------------------------------------------------------------------*/
1662 /**
1663  * \brief Adjust balance of a node leaning on the left so it will be
1664  * in range [-1;1].
1665  * \param node Node to adjust.
1666  * \pre (node != NULL) && (*node != NULL) && ( (*node)->balance == 2).
1667  * \post node->balance is in range [-1;1]
1668  */
1669 template<class K, class Comp>
1670 void claw::avl_base<K,Comp>::adjust_balance_left( avl_node_ptr& node )
1671 {
1672  assert(node != NULL);
1673  assert(node->balance == 2);
1674 
1675  if (node->left->balance > -1)
1676  rotate_right( node );
1677  else if ( node->left->balance == -1)
1678  rotate_left_right(node);
1679 } // adjust_balance_left()
1680 
1681 /*----------------------------------------------------------------------------*/
1682 /**
1683  * \brief Adjust balance of a node leaning on the right so it will be
1684  * in range [-1;1].
1685  * \param node Node to adjust.
1686  * \pre (node != NULL) && (*node != NULL) && ( (*node)->balance == -2).
1687  * \post node->balance is in range [-1;1]
1688  */
1689 template<class K, class Comp>
1690 void claw::avl_base<K,Comp>::adjust_balance_right( avl_node_ptr& node )
1691 {
1692  assert(node != NULL);
1693  assert(node->balance == -2);
1694 
1695  if (node->right->balance < 1)
1696  rotate_left( node );
1697  else if ( node->right->balance == 1)
1698  rotate_right_left(node);
1699 } // adjust_balance_right()
1700 
1701 
1702 /*----------------------------------------------------------------------------*/
1703 // Methods for insertion
1704 /*----------------------------------------------------------------------------*/
1705 
1706 
1707 /*----------------------------------------------------------------------------*/
1708 /**
1709  * \brief Add a node to the tree.
1710  * \param key Key for the new value.
1711  * \post exists(key)
1712  * && (exists(old this, key)==0 => size(this) == size(old this) + 1 )
1713  */
1714 template<class K, class Comp>
1715 void claw::avl_base<K,Comp>::insert_node( const K& key )
1716 {
1717  avl_node_ptr* new_node;
1718  avl_node_ptr node_father;
1719  avl_node_ptr last_imbalanced;
1720  avl_node_ptr last_imbalanced_father;
1721 
1722  assert(m_tree != NULL);
1723 
1724  new_node = find_node_reference(key, last_imbalanced, node_father );
1725 
1726  if (*new_node == NULL) // this key isn't in use. Let's create a new node
1727  {
1728  *new_node = new avl_node(key);
1729  (*new_node)->father = node_father;
1730 
1731  ++m_size;
1732  last_imbalanced_father = last_imbalanced->father;
1733 
1734  // Update balance of the last imbalanced node
1735  update_balance( last_imbalanced, key );
1736  // then adjust it to be in range [-1, 1]
1737  adjust_balance( last_imbalanced );
1738 
1739  // pointer update after rotation
1740  if ( last_imbalanced_father == NULL )
1741  {
1742  m_tree = last_imbalanced;
1743  m_tree->father = NULL;
1744  }
1745  else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key))
1746  // left child
1747  last_imbalanced_father->left = last_imbalanced;
1748  else
1749  last_imbalanced_father->right = last_imbalanced;
1750  }
1751 } // insert_node()
1752 
1753 /*----------------------------------------------------------------------------*/
1754 /**
1755  * \brief Find the node where to insert a new value at key.
1756  * \param key Key for the new value.
1757  * \param last_imbalanced (out) Pointer to the last imbalanced node seen.
1758  * \param node_father (out) Pointer to the father of the new node.
1759  * \return Pointer to the node corresponding of the key (if exists). Otherwise
1760  * a pointer to a NULL node where to insert the new one.
1761  * \post ( exists(this, key) => *result == find(this, key) )
1762  * && ( !exists(this, key) => *result the good node to allocate )
1763  * && ( *last_imbalance and *last_imbalance are correct regarding to
1764  * previous definitions )
1765  */
1766 template<class K, class Comp>
1767 typename claw::avl_base<K,Comp>::avl_node_ptr*
1768 claw::avl_base<K,Comp>::find_node_reference
1769 ( const K& key, avl_node_ptr& last_imbalanced, avl_node_ptr& node_father)
1770 {
1771  avl_node_ptr* node; // node for search
1772  bool exists = false; // if this key already exists
1773 
1774  last_imbalanced = m_tree;
1775  node = & m_tree;
1776  node_father = NULL;
1777 
1778  while ( ((*node) != NULL) && !exists )
1779  {
1780  if ( (*node)->balance != 0 )
1781  last_imbalanced = *node;
1782 
1783 
1784  // find next node
1785  if ( s_key_less(key, (*node)->key) )
1786  {
1787  node_father = *node;
1788  node = & (*node)->left;
1789  }
1790  else if ( s_key_less((*node)->key, key) )
1791  {
1792  node_father = *node;
1793  node = & (*node)->right;
1794  }
1795  else
1796  exists = true;
1797  }
1798 
1799  return node;
1800 } // find_node_reference()
1801 
1802 
1803 /*----------------------------------------------------------------------------*/
1804 // Methods for deletion
1805 /*----------------------------------------------------------------------------*/
1806 
1807 
1808 /*----------------------------------------------------------------------------*/
1809 /**
1810  * \brief Delete a node. Search is done recursively.
1811  * \param node Tree to which the node is removed.
1812  * \param key Key of the node to remove.
1813  * \return true if the balance of the node has changed.
1814  * \pre node != NULL
1815  * \post (exists(this, key) == 0)
1816  */
1817 template<class K, class Comp>
1818 bool
1819 claw::avl_base<K,Comp>::recursive_delete( avl_node_ptr& node, const K& key )
1820 {
1821  bool result = false;
1822 
1823  if ( node != NULL )
1824  {
1825  // try to find the key in the left subtree
1826  if ( s_key_less(key, node->key) )
1827  {
1828  if ( recursive_delete( node->left, key ) )
1829  result = new_balance( node, -1 );
1830  }
1831  // try to find the key in the right subtree
1832  else if ( s_key_less(node->key, key) )
1833  {
1834  if ( recursive_delete( node->right, key ) )
1835  result = new_balance( node, 1 );
1836  }
1837  else // we got it !
1838  {
1839  --m_size;
1840  result = recursive_delete_node( node );
1841  }
1842  }
1843 
1844  return result;
1845 } // recursive_delete()
1846 
1847 
1848 /*----------------------------------------------------------------------------*/
1849 /**
1850  * \brief Adjust balance of a node.
1851  * \param node Node to balance.
1852  * \param imbalance Imbalance to add to the node's balance.
1853  * \return true if the balance of the node has changed.
1854  * \pre node != NULL
1855  * \pre (imbalance==1) || (imbalance==-1)
1856  * \post node tree is an AVL
1857  */
1858 template<class K, class Comp>
1859 bool claw::avl_base<K,Comp>::new_balance( avl_node_ptr& node, int imbalance )
1860 {
1861  assert( (imbalance==1) || (imbalance==-1) );
1862  assert( node != NULL );
1863 
1864  node->balance += imbalance;
1865 
1866  switch(node->balance)
1867  {
1868  // balance == 0 so as it was != 0 before deletion
1869  // balance of the tree had changed
1870  case 0: return true;
1871  // balance == 2 so it must be 1 before deletion and node
1872  // was deleted in the right subtree
1873  // if after ajusting the balance is equal to 1, it means that
1874  // our subtree got back his old balance (so it's unchanged).
1875  // if it's equal to -1, it means that subtree now lean to the
1876  // otherside. But in those cases, depth didn't changed.
1877  case 2: adjust_balance_left(node); return node->balance == 0;
1878  // same thing but symetric
1879  case -2: adjust_balance_right(node); return node->balance == 0;
1880  default : return false;
1881  }
1882 } // new_balance()
1883 
1884 /*----------------------------------------------------------------------------*/
1885 /**
1886  * \brief Remove the root of an AVL
1887  * (exchange with the descendant immediatly lower).
1888  * \param node Node to remove.
1889  * \return true if the balance of the subtree has changed.
1890  * \pre node != NULL
1891  * \post node tree is an AVL
1892  */
1893 template<class K, class Comp>
1894 bool claw::avl_base<K,Comp>::recursive_delete_node( avl_node_ptr& node )
1895 {
1896  assert( node != NULL );
1897 
1898  if ( node->left == NULL) // this node doesn't have a lower descendant
1899  {
1900  // Get right subtree of current node
1901  avl_node_ptr right_subtree = node->right;
1902 
1903  if (right_subtree)
1904  right_subtree->father = node->father;
1905 
1906  // Free memory pointed by the current node
1907  node->clear();
1908  delete node;
1909 
1910  // then rise the old right subtree
1911  node = right_subtree;
1912 
1913  return true;
1914  }
1915  else // this node has a lower descendant, let's get it
1916  if ( recursive_delete_max( node->left, node ) )
1917  {
1918  // left subtree depth has decreased
1919  // so reajust balance (rem. balance is not changed by delete_max)
1920  --(node->balance);
1921 
1922  if ( node->balance == -2 )
1923  {
1924  // old balance was -1
1925  adjust_balance_right(node);
1926  return node->balance == 0; // tell if depth has changed
1927  }
1928  else if ( node->balance == 0 )
1929  // node had at least one subtree and old balance - 1 == 0
1930  // so old balance = 1
1931  return true;
1932  else // node's balance is -1
1933  // As node's balance is (old balance - 1), node's balance must be -1
1934  // (otherwise old balance is 2, that's impossible)
1935  // So old balance is 0.
1936  // Moreover old node have at least a left subtree. It means that
1937  // old node had 2 subtrees and their depths were equals.
1938  // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1
1939  // We deleted a node in left subtree and so right subtree is
1940  // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1
1941  // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node)
1942  // => Node depth is unchanged.
1943  return false;
1944  }
1945  else // depth is unchanged
1946  return false;
1947 } // recursive_delete_node()
1948 
1949 /*----------------------------------------------------------------------------*/
1950 /**
1951  * \brief Replace a node key and data by the one of the node with the
1952  * maximum key in tree.
1953  * \param root Root of the tree in which find new values.
1954  * \param node Node Wich gets values founded
1955  * \return true if the balance of the tree from root has changed.
1956  * \pre node != NULL
1957  * \pre root != NULL
1958  * \pre root is an AVL
1959  * \post (root tree is an AVL) && (find(root, max(old root)) == 0)
1960  */
1961 template<class K, class Comp>
1962 int claw::avl_base<K,Comp>::recursive_delete_max
1963 ( avl_node_ptr& root, avl_node_ptr node )
1964 {
1965  assert(node!=NULL);
1966  assert(root!=NULL);
1967 
1968  if ( root->right == NULL ) // We have the maximum
1969  {
1970  // node have only a left subtree if any.
1971  // This subtree has one node, at most.
1972  avl_node_ptr left_subtree;
1973 
1974  node->key = root->key;
1975  left_subtree = root->left;
1976 
1977  if (left_subtree)
1978  left_subtree->father = root->father;
1979 
1980  root->clear();
1981  delete root;
1982 
1983  // rise the left subtree
1984  root = left_subtree;
1985 
1986  // depth have changed
1987  return true;
1988  }
1989  else // try to find the max in the right subtree
1990  if ( recursive_delete_max( root->right, node ) )
1991  {
1992  // depth of the subtree changed (ie. decreased)
1993  // so root's tree lean to the left
1994  ++(root->balance);
1995 
1996  if (root->balance == 2) // tree is leaning too much
1997  {
1998  // old balance was 1
1999  adjust_balance_left( root );
2000  return root->balance == 0; // Say if balance is changed
2001  }
2002  else
2003  // if balance is 0, it means that old root leant to the left
2004  // and so his depth changed.
2005  // The other value for balance is 1, in this case
2006  // depth didn't change. See recursive_delete_node code comments.
2007  return root->balance == 0;
2008  }
2009  else // depth of the subtree didn't change
2010  return false;
2011 } // recursive_delete_max()