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 */
39template<class K, class Comp>
40claw::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 */
51template<class K, class Comp>
52claw::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 */
63template<class K, class Comp>
64typename claw::avl_base<K, Comp>::avl_node*
65claw::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 */
96template<class K, class Comp>
97void 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 */
119template<class K, class Comp>
120unsigned 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 */
138template<class K, class Comp>
139typename claw::avl_base<K,Comp>::avl_node*
140claw::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 */
161template<class K, class Comp>
162const typename claw::avl_base<K,Comp>::avl_node*
163claw::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 */
185template<class K, class Comp>
186typename claw::avl_base<K,Comp>::avl_node*
187claw::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 */
226template<class K, class Comp>
227const typename claw::avl_base<K,Comp>::avl_node*
228claw::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 */
267template<class K, class Comp>
268typename claw::avl_base<K,Comp>::avl_node*
269claw::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 */
308template<class K, class Comp>
309const typename claw::avl_base<K,Comp>::avl_node*
310claw::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 */
347template<class K, class Comp>
348typename claw::avl_base<K,Comp>::avl_node*
349claw::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 */
364template<class K, class Comp>
365const typename claw::avl_base<K,Comp>::avl_node*
366claw::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 */
381template<class K, class Comp>
382typename claw::avl_base<K,Comp>::avl_node*
383claw::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 */
398template<class K, class Comp>
399const typename claw::avl_base<K,Comp>::avl_node*
400claw::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 */
415template<class K, class Comp>
416typename claw::avl_base<K,Comp>::avl_node*
417claw::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 */
455template<class K, class Comp>
456const typename claw::avl_base<K,Comp>::avl_node*
457claw::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 */
495template<class K, class Comp>
496typename claw::avl_base<K,Comp>::avl_node*
497claw::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 */
530template<class K, class Comp>
531const typename claw::avl_base<K,Comp>::avl_node*
532claw::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 */
575template<class K, class Comp>
576claw::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 */
594template<class K, class Comp>
595claw::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 */
605template<class K, class Comp>
606claw::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 */
618template<class K, class Comp>
619typename claw::avl_base<K,Comp>::avl_iterator&
620claw::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 */
639template<class K, class Comp>
640typename claw::avl_base<K,Comp>::avl_iterator
641claw::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 */
653template<class K, class Comp>
654typename claw::avl_base<K,Comp>::avl_iterator&
655claw::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 */
673template<class K, class Comp>
674typename claw::avl_base<K,Comp>::avl_iterator
675claw::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 */
686template<class K, class Comp>
687typename claw::avl_base<K,Comp>::avl_iterator::reference
688claw::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 */
697template<class K, class Comp>
698typename claw::avl_base<K,Comp>::avl_iterator::pointer
699claw::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 */
709template<class K, class Comp>
710bool
711claw::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 */
721template<class K, class Comp>
722bool
723claw::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 */
740template<class K, class Comp>
741claw::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 */
751template<class K, class Comp>
752claw::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 */
764template<class K, class Comp>
765typename claw::avl_base<K,Comp>::avl_const_iterator&
766claw::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 */
785template<class K, class Comp>
786typename claw::avl_base<K,Comp>::avl_const_iterator
787claw::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 */
799template<class K, class Comp>
800typename claw::avl_base<K,Comp>::avl_const_iterator&
801claw::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 */
819template<class K, class Comp>
820typename claw::avl_base<K,Comp>::avl_const_iterator
821claw::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 */
832template<class K, class Comp>
833typename claw::avl_base<K,Comp>::avl_const_iterator::reference
834claw::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 */
843template<class K, class Comp>
844typename claw::avl_base<K,Comp>::avl_const_iterator::pointer
845claw::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 */
855template<class K, class Comp>
856bool 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 */
867template<class K, class Comp>
868bool 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/*----------------------------------------------------------------------------*/
882template<class K, class Comp>
883typename 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 */
890template<class K, class Comp>
891claw::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 */
902template<class K, class Comp>
903claw::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 */
917template<class K, class Comp>
918claw::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 */
933template<class K, class Comp>
934void 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 */
957template<class K, class Comp>
958template<typename Iterator>
959void 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 */
971template<class K, class Comp>
972void 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 */
987template<class K, class Comp>
988void 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 */
1005template<class K, class Comp>
1006inline 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 */
1016template<class K, class Comp>
1017inline 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 */
1026template<class K, class Comp>
1027typename 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 */
1039template<class K, class Comp>
1040typename claw::avl_base<K,Comp>::const_iterator
1041claw::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 */
1053template<class K, class Comp>
1054typename 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 */
1066template<class K, class Comp>
1067typename claw::avl_base<K,Comp>::const_iterator
1068claw::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 */
1081template<class K, class Comp>
1082typename claw::avl_base<K,Comp>::iterator
1083claw::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 */
1093template<class K, class Comp>
1094typename claw::avl_base<K,Comp>::const_iterator
1095claw::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 */
1106template<class K, class Comp>
1107typename claw::avl_base<K,Comp>::iterator
1108claw::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 */
1119template<class K, class Comp>
1120typename claw::avl_base<K,Comp>::const_iterator
1121claw::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 */
1132template<class K, class Comp>
1133typename claw::avl_base<K,Comp>::iterator
1134claw::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 */
1145template<class K, class Comp>
1146typename claw::avl_base<K,Comp>::const_iterator
1147claw::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 */
1156template<class K, class Comp>
1157typename 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 */
1166template<class K, class Comp>
1167typename claw::avl_base<K,Comp>::const_iterator
1168claw::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 */
1177template<class K, class Comp>
1178typename 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 */
1187template<class K, class Comp>
1188typename claw::avl_base<K,Comp>::const_iterator
1189claw::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 */
1199template<class K, class Comp>
1200claw::avl_base<K, Comp>&
1201claw::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 */
1227template<class K, class Comp>
1228bool 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 */
1241template<class K, class Comp>
1242bool 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 */
1252template<class K, class Comp>
1253bool 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 */
1264template<class K, class Comp>
1265bool 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 */
1275template<class K, class Comp>
1276bool 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 */
1286template<class K, class Comp>
1287bool 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 */
1297template<class K, class Comp>
1298void 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 */
1318template<class K, class Comp>
1319bool 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 */
1345template<class K, class Comp>
1346bool 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 */
1369template<class K, class Comp>
1370bool 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 */
1396template<class K, class Comp>
1397bool 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 */
1432template<class K, class Comp>
1433typename claw::avl_base<K,Comp>::iterator
1434claw::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 */
1447template<class K, class Comp>
1448typename claw::avl_base<K,Comp>::const_iterator
1449claw::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 */
1471template<class K, class Comp>
1472void 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 */
1532template<class K, class Comp>
1533void 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 */
1590template<class K, class Comp>
1591void 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 */
1604template<class K, class Comp>
1605void 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 */
1622template<class K, class Comp>
1623void 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 */
1650template<class K, class Comp>
1651void 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 */
1669template<class K, class Comp>
1670void 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 */
1689template<class K, class Comp>
1690void 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 */
1714template<class K, class Comp>
1715void 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 */
1766template<class K, class Comp>
1767typename claw::avl_base<K,Comp>::avl_node_ptr*
1768claw::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 */
1817template<class K, class Comp>
1818bool
1819claw::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 */
1858template<class K, class Comp>
1859bool 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 */
1893template<class K, class Comp>
1894bool 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 */
1961template<class K, class Comp>
1962int 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()