2 CLAW - a C++ Library Absolutely Wonderful
4 CLAW is a free library without any particular aim but being useful to
7 Copyright (C) 2005-2011 Julien Jorge
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.
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.
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
23 contact: julien.jorge@gamned.org
27 * \brief The avl class implementation.
28 * \author Julien Jorge
32 //**************************** avl_base::avl_node ******************************
34 /*----------------------------------------------------------------------------*/
36 * \brief AVL's node constructor
37 * \param k Value of the node
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)
44 assert(!super::right);
45 } // avl_node::avl_node() [constructeur]
47 /*----------------------------------------------------------------------------*/
49 * \brief AVL's node destructor
51 template<class K, class Comp>
52 claw::avl_base<K, Comp>::avl_node::~avl_node()
55 } // avl_node::~avl_node() [destructeur]
57 /*----------------------------------------------------------------------------*/
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.
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
67 avl_node* node_copy = new avl_node(key);
69 node_copy->balance = balance;
70 node_copy->father = NULL;
74 node_copy->left = super::left->duplicate(count);
75 node_copy->left->father = node_copy;
78 node_copy->left = NULL;
82 node_copy->right = super::right->duplicate(count);
83 node_copy->right->father = node_copy;
86 node_copy->right = NULL;
89 } // avl_node::duplicate()
91 /*----------------------------------------------------------------------------*/
93 * \brief Delete current node and his subtrees.
94 * \post left == NULL && right == NULL
96 template<class K, class Comp>
97 void claw::avl_base<K, Comp>::avl_node::del_tree()
109 assert( !super::left );
110 assert( !super::right );
111 } // avl_node::del_tree
113 /*----------------------------------------------------------------------------*/
115 * \brief Get the depth of a tree.
116 * \remark For validity check.
117 * \return 1 + max( this->left->depth(), this->right->depth() )
119 template<class K, class Comp>
120 unsigned int claw::avl_base<K, Comp>::avl_node::depth() const
122 unsigned int pl=0, pr=0;
124 if (super::left) pl = super::left->depth();
125 if (super::right) pr = super::right->depth();
131 } // avl_node::depth()
133 /*----------------------------------------------------------------------------*/
135 * \brief Get a pointer on the node of the tree with a specified key.
136 * \param key Key to find.
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 )
143 avl_node* node = this;
146 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
148 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
154 } // avl_base::avl_node::find()
156 /*----------------------------------------------------------------------------*/
158 * \brief Get a pointer on the node of the tree with a specified key.
159 * \param key Key to find.
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
166 const avl_node* node = this;
169 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
171 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
177 } // avl_base::avl_node::find()
179 /*----------------------------------------------------------------------------*/
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.
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 )
190 avl_node* node = this;
191 avl_node* prev_node = NULL;
194 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
199 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
211 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
212 return prev_node->next();
218 } // avl_base::find_nearest_greater()
220 /*----------------------------------------------------------------------------*/
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.
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
231 const avl_node* node = this;
232 const avl_node* prev_node = NULL;
235 if ( avl_base<K, Comp>::s_key_less(key, node->key) )
240 else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
252 if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
253 return prev_node->next();
259 } // avl_base::find_nearest_greater()
261 /*----------------------------------------------------------------------------*/
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.
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 )
272 avl_node* node = this;
273 avl_node* prev_node = NULL;
276 if ( s_key_less(key, node->key) )
281 else if ( s_key_less(node->key, key) )
293 if ( s_key_less(key, prev_node->key) )
296 return prev_node->prev();
300 } // avl_base::find_nearest_lower()
302 /*----------------------------------------------------------------------------*/
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.
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
313 const avl_node* node = this;
314 const avl_node* prev_node = NULL;
317 if ( s_key_less(key, node->key) )
322 else if ( s_key_less(node->key, key) )
334 if ( s_key_less(key, prev_node->key) )
337 return prev_node->prev();
341 } // avl_base::find_nearest_lower()
343 /*----------------------------------------------------------------------------*/
345 * \brief Get a pointer on the lowest value of the tree.
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()
351 avl_node* node = this;
358 } // avl_base::lower_bound()
360 /*----------------------------------------------------------------------------*/
362 * \brief Get a pointer on the lowest value of the tree.
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
368 const avl_node* node = this;
375 } // avl_base::lower_bound()
377 /*----------------------------------------------------------------------------*/
379 * \brief Get a pointer on the greatest value of the tree.
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()
385 avl_node* node = this;
392 } // avl_base::upper_bound()
394 /*----------------------------------------------------------------------------*/
396 * \brief Get a pointer on the greatest value of the tree.
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
402 const avl_node* node = this;
409 } // avl_base::upper_bound()
411 /*----------------------------------------------------------------------------*/
413 * \brief Get the node immediately greater than \a this.
415 template<class K, class Comp>
416 typename claw::avl_base<K,Comp>::avl_node*
417 claw::avl_base<K,Comp>::avl_node::next()
419 avl_node* result = this;
421 // node have a right subtree : go to the min
422 if (result->right != NULL)
424 result = result->right;
426 while (result->left != NULL)
427 result = result->left;
432 avl_node* previous_node = this;
435 while (result->father && !done)
437 if (result->father->left == result)
440 result = result->father;
443 // came back from the max node to the root
445 result = previous_node;
449 } // avl_iterator::avl_node::next()
451 /*----------------------------------------------------------------------------*/
453 * \brief Get the node immediately greater than \a this.
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
459 const avl_node* result = this;
461 // node have a right subtree : go to the min
462 if (result->right != NULL)
464 result = result->right;
466 while (result->left != NULL)
467 result = result->left;
472 const avl_node* previous_node = this;
475 while (result->father && !done)
477 if (result->father->left == result)
480 result = result->father;
483 // came back from the max node to the root
485 result = previous_node;
489 } // avl_iterator::avl_node::next()
491 /*----------------------------------------------------------------------------*/
493 * \brief Get the node immediately before \a this.
495 template<class K, class Comp>
496 typename claw::avl_base<K,Comp>::avl_node*
497 claw::avl_base<K,Comp>::avl_node::prev()
499 avl_node* result = this;
501 // node have a left subtree : go to the max
502 if (result->left != NULL)
504 result = result->left;
506 while (result->right != NULL)
507 result = result->right;
514 while (result->father && !done)
516 if (result->father->right == result)
519 result = result->father;
524 } // avl_iterator::avl_node::prev()
526 /*----------------------------------------------------------------------------*/
528 * \brief Get the node immediately before \a this.
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
534 const avl_node* result = this;
536 // node have a left subtree : go to the max
537 if (result->left != NULL)
539 result = result->left;
541 while (result->right != NULL)
542 result = result->right;
549 while (result->father && !done)
551 if (result->father->right == result)
554 result = result->father;
559 } // avl_iterator::avl_node::prev()
565 /*=================================== private ===============================*/
569 /*----------------------------------------------------------------------------*/
571 * \brief Copy constructor.
572 * \param that Node to copy from.
573 * \remark Shouldn't be use.
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)
580 } // avl_node::depth()
586 //**************************** avl_base::avl_iterator **************************
590 /*----------------------------------------------------------------------------*/
592 * \brief Constructor.
594 template<class K, class Comp>
595 claw::avl_base<K,Comp>::avl_iterator::avl_iterator()
596 : m_current(NULL), m_is_final(true)
599 } // avl_iterator::avl_iterator() [constructeur]
601 /*----------------------------------------------------------------------------*/
603 * \brief Constructor.
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)
611 } // avl_iterator::avl_iterator() [constructeur with node]
613 /*----------------------------------------------------------------------------*/
615 * \brief Preincrement.
616 * \pre not final(this).
618 template<class K, class Comp>
619 typename claw::avl_base<K,Comp>::avl_iterator&
620 claw::avl_base<K,Comp>::avl_iterator::operator++()
625 avl_node* p = m_current->next();
627 if ( m_current == p )
633 } // avl_iterator::operator++() [preincrement]
635 /*----------------------------------------------------------------------------*/
637 * \brief Postincrement.
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)
643 avl_iterator it = *this;
646 } // avl_iterator::operator++ [postincrement]
648 /*----------------------------------------------------------------------------*/
650 * \brief Predecrement.
651 * \pre iterator is not at the begining of the container.
653 template<class K, class Comp>
654 typename claw::avl_base<K,Comp>::avl_iterator&
655 claw::avl_base<K,Comp>::avl_iterator::operator--()
660 m_is_final = !m_is_final;
662 m_current = m_current->prev();
664 assert(m_current != NULL);
667 } // avl_iterator::operator--() [predecrement]
669 /*----------------------------------------------------------------------------*/
671 * \brief Postdecrement.
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)
677 avl_iterator it = *this;
680 } // avl_iterator::operator-- [postdecrement]
682 /*----------------------------------------------------------------------------*/
684 * \brief Dereference.
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
690 return m_current->key;
691 } // avl_iterator::operator*() [dereference]
693 /*----------------------------------------------------------------------------*/
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
701 return &m_current->key;
702 } // avl_iterator::operator->()
704 /*----------------------------------------------------------------------------*/
707 * \param it Iterator to compare to.
709 template<class K, class Comp>
711 claw::avl_base<K,Comp>::avl_iterator::operator==(const avl_iterator& it) const
713 return (m_current == it.m_current) && (m_is_final == it.m_is_final);
714 } // avl_iterator::operator==()
716 /*----------------------------------------------------------------------------*/
719 * \param it Iterator to compare to.
721 template<class K, class Comp>
723 claw::avl_base<K,Comp>::avl_iterator::operator!=(const avl_iterator& it) const
725 return !( *this == it );
726 } // avl_iterator::operator!=()
732 //************************* avl_base::avl_const_iterator ***********************
736 /*----------------------------------------------------------------------------*/
738 * \brief Constructor.
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)
745 } // avl_const_iterator::avl_const_iterator() [constructeur]
747 /*----------------------------------------------------------------------------*/
749 * \brief Constructor.
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)
757 } // avl_const_iterator::avl_const_iterator() [constructeur with node]
759 /*----------------------------------------------------------------------------*/
761 * \brief Preincrement.
762 * \pre not final(this).
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++()
771 const_avl_node_ptr p = m_current->next();
773 if ( m_current == p )
779 } // avl_const_iterator::operator++() [preincrement]
781 /*----------------------------------------------------------------------------*/
783 * \brief Postincrement.
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)
789 avl_const_iterator it = *this;
792 } // avl_const_iterator::operator++ [postincrement]
794 /*----------------------------------------------------------------------------*/
796 * \brief Predecrement.
797 * \pre iterator is not at the begining of the container.
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--()
806 m_is_final = !m_is_final;
808 m_current = m_current->prev();
810 assert(m_current != NULL);
813 } // avl_const_iterator::operator--() [predecrement]
815 /*----------------------------------------------------------------------------*/
817 * \brief Postdecrement.
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)
823 avl_const_iterator it = *this;
826 } // avl_const_iterator::operator-- [postdecrement]
828 /*----------------------------------------------------------------------------*/
830 * \brief Dereference.
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
836 return m_current->key;
837 } // avl_const_iterator::operator*() [dereference]
839 /*----------------------------------------------------------------------------*/
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
847 return &m_current->key;
848 } // avl_const_iterator::operator->()
850 /*----------------------------------------------------------------------------*/
853 * \param it Iterator to compare to.
855 template<class K, class Comp>
856 bool claw::avl_base<K,Comp>::avl_const_iterator::operator==
857 (const avl_const_iterator& it) const
859 return (m_current == it.m_current) && (m_is_final == it.m_is_final);
860 } // avl_const_iterator::operator==()
862 /*----------------------------------------------------------------------------*/
865 * \param it Iterator to compare to.
867 template<class K, class Comp>
868 bool claw::avl_base<K,Comp>::avl_const_iterator::operator!=
869 (const avl_const_iterator& it) const
871 return !( *this == it );
872 } // avl_const_iterator::operator!=()
878 //******************************* avl_base (main) ******************************
881 /*----------------------------------------------------------------------------*/
882 template<class K, class Comp>
883 typename claw::avl_base<K,Comp>::key_less claw::avl_base<K,Comp>::s_key_less;
885 /*----------------------------------------------------------------------------*/
887 * \brief AVL constructor.
890 template<class K, class Comp>
891 claw::avl_base<K,Comp>::avl_base()
892 : m_size(0), m_tree(NULL)
895 } // avl_base::avl_base() [constructeur]
897 /*----------------------------------------------------------------------------*/
899 * \brief AVL copy constructor.
900 * \param that AVL instance to copy from.
902 template<class K, class Comp>
903 claw::avl_base<K,Comp>::avl_base( const avl_base<K, Comp>& that )
908 m_tree = that.m_tree->duplicate( m_size );
911 } // avl_base::avl_base() [copy constructor]
913 /*----------------------------------------------------------------------------*/
915 * \brief AVL destructor.
917 template<class K, class Comp>
918 claw::avl_base<K,Comp>::~avl_base()
925 } // avl_base::~avl_base() [destructeur]
927 /*----------------------------------------------------------------------------*/
929 * \brief Add a value in a tree.
930 * \param key Node key.
933 template<class K, class Comp>
934 void claw::avl_base<K,Comp>::insert( const K& key )
936 assert( validity_check() );
938 if ( m_tree == NULL )
940 m_tree = new avl_node(key);
946 assert( validity_check() );
947 } // avl_base::insert()
949 /*----------------------------------------------------------------------------*/
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)
957 template<class K, class Comp>
958 template<typename Iterator>
959 void claw::avl_base<K,Comp>::insert( Iterator first, Iterator last )
961 for ( ; first!=last; ++first )
963 } // avl_base::insert()
965 /*----------------------------------------------------------------------------*/
967 * \brief Delete a value in a tree.
968 * \param key Node key.
969 * \post not exists(key)
971 template<class K, class Comp>
972 void claw::avl_base<K,Comp>::erase( const K& key )
974 assert( validity_check() );
977 recursive_delete( m_tree, key );
979 assert( validity_check() );
980 } // avl_base::erase()
982 /*----------------------------------------------------------------------------*/
984 * \brief Clear a tree.
987 template<class K, class Comp>
988 void claw::avl_base<K,Comp>::clear()
998 } // avl_base::clear()
1000 /*----------------------------------------------------------------------------*/
1002 * \brief Get the size of a tree.
1003 * \return The size of the tree.
1005 template<class K, class Comp>
1006 inline unsigned int claw::avl_base<K,Comp>::size() const
1009 } // avl_base::size()
1011 /*----------------------------------------------------------------------------*/
1013 * \brief Tell if a tree is empty or not.
1014 * \return true if the tree is empty, false otherwise.
1016 template<class K, class Comp>
1017 inline bool claw::avl_base<K,Comp>::empty() const
1020 } // avl_base::empty()
1022 /*----------------------------------------------------------------------------*/
1024 * \brief Get an iterator on the nodes of the tree.
1026 template<class K, class Comp>
1027 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::begin()
1030 return iterator(NULL, true);
1032 return lower_bound();
1033 } // avl_base::begin()
1035 /*----------------------------------------------------------------------------*/
1037 * \brief Get an iterator on the nodes of the tree.
1039 template<class K, class Comp>
1040 typename claw::avl_base<K,Comp>::const_iterator
1041 claw::avl_base<K,Comp>::begin() const
1044 return const_iterator(NULL, true);
1046 return lower_bound();
1047 } // avl_base::begin()
1049 /*----------------------------------------------------------------------------*/
1051 * \brief Get an iterator after the end of the tree.
1053 template<class K, class Comp>
1054 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::end()
1057 return iterator(NULL, true);
1059 return iterator(m_tree->upper_bound(), true);
1060 } // avl_base::end()
1062 /*----------------------------------------------------------------------------*/
1064 * \brief Get an iterator after the end of the tree.
1066 template<class K, class Comp>
1067 typename claw::avl_base<K,Comp>::const_iterator
1068 claw::avl_base<K,Comp>::end() const
1071 return const_iterator(NULL, true);
1073 return const_iterator(m_tree->upper_bound(), true);
1074 } // avl_base::end()
1076 /*----------------------------------------------------------------------------*/
1078 * \brief Get an iterator on the nodes of the tree from a specified key.
1079 * \param key Key to find.
1081 template<class K, class Comp>
1082 typename claw::avl_base<K,Comp>::iterator
1083 claw::avl_base<K,Comp>::find( const K& key )
1085 return make_iterator( m_tree->find(key) );
1086 } // avl_base::find()
1088 /*----------------------------------------------------------------------------*/
1090 * \brief Get an iterator on the nodes of the tree from a specified key.
1091 * \param key Key to find.
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
1097 return make_const_iterator( m_tree->find(key) );
1098 } // avl_base::find()
1100 /*----------------------------------------------------------------------------*/
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.
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 )
1110 return make_iterator( m_tree->find_nearest_greater(key) );
1111 } // avl_base::find_nearest_greater()
1113 /*----------------------------------------------------------------------------*/
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.
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
1123 return make_const_iterator( m_tree->find_nearest_greater(key) );
1124 } // avl_base::find_nearest_greater()
1126 /*----------------------------------------------------------------------------*/
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.
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 )
1136 return make_iterator( m_tree->find_nearest_lower(key) );
1137 } // avl_base::find_nearest_lower()
1139 /*----------------------------------------------------------------------------*/
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.
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
1149 return make_const_iterator( m_tree->find_nearest_lower(key) );
1150 } // avl_base::find_nearest_lower()
1152 /*----------------------------------------------------------------------------*/
1154 * \brief Get an iterator on the lowest value of the tree.
1156 template<class K, class Comp>
1157 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::lower_bound()
1159 return make_iterator( m_tree->lower_bound() );
1160 } // avl_base::lower_bound()
1162 /*----------------------------------------------------------------------------*/
1164 * \brief Get an iterator on the lowest value of the tree.
1166 template<class K, class Comp>
1167 typename claw::avl_base<K,Comp>::const_iterator
1168 claw::avl_base<K,Comp>::lower_bound() const
1170 return make_const_iterator( m_tree->lower_bound() );
1171 } // avl_base::lower_bound()
1173 /*----------------------------------------------------------------------------*/
1175 * \brief Get an iterator on the gratest value of the tree.
1177 template<class K, class Comp>
1178 typename claw::avl_base<K,Comp>::iterator claw::avl_base<K,Comp>::upper_bound()
1180 return make_iterator( m_tree->upper_bound() );
1181 } // avl_base::upper_bound()
1183 /*----------------------------------------------------------------------------*/
1185 * \brief Get an iterator on the gratest value of the tree.
1187 template<class K, class Comp>
1188 typename claw::avl_base<K,Comp>::const_iterator
1189 claw::avl_base<K,Comp>::upper_bound() const
1191 return make_const_iterator( m_tree->upper_bound() );
1192 } // avl_base::upper_bound()
1194 /*----------------------------------------------------------------------------*/
1196 * \brief Assignment operator
1197 * \param that AVL instance to copy from.
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 )
1214 m_tree = that.m_tree->duplicate( m_size );
1220 } // avl_base::operator=()
1222 /*----------------------------------------------------------------------------*/
1225 * \param that AVL top compare to.
1227 template<class K, class Comp>
1228 bool claw::avl_base<K, Comp>::operator==( const avl_base<K, Comp>& that ) const
1230 if (m_size != that.m_size)
1233 return std::equal( begin(), end(), that.begin(), s_key_less );
1234 } // avl_base::operator==()
1236 /*----------------------------------------------------------------------------*/
1238 * \brief Disequality.
1239 * \param that AVL top compare to.
1241 template<class K, class Comp>
1242 bool claw::avl_base<K, Comp>::operator!=( const avl_base<K, Comp>& that ) const
1244 return !( *this == that );
1245 } // avl_base::operator!=()
1247 /*----------------------------------------------------------------------------*/
1249 * \brief Less than operator.
1250 * \param that AVL top compare to.
1252 template<class K, class Comp>
1253 bool claw::avl_base<K, Comp>::operator<( const avl_base<K, Comp>& that ) const
1255 return std::lexicographical_compare
1256 ( begin(), end(), that.begin(), that.end(), s_key_less );
1257 } // avl_base::operator<()
1259 /*----------------------------------------------------------------------------*/
1261 * \brief Greater than operator.
1262 * \param that AVL top compare to.
1264 template<class K, class Comp>
1265 bool claw::avl_base<K, Comp>::operator>( const avl_base<K, Comp>& that ) const
1267 return that < *this;
1268 } // avl_base::operator>()
1270 /*----------------------------------------------------------------------------*/
1272 * \brief Less or equal operator.
1273 * \param that AVL top compare to.
1275 template<class K, class Comp>
1276 bool claw::avl_base<K, Comp>::operator<=( const avl_base<K, Comp>& that ) const
1278 return !( that < *this );
1279 } // avl_base::operator<=()
1281 /*----------------------------------------------------------------------------*/
1283 * \brief Greater or equal operator.
1284 * \param that AVL top compare to.
1286 template<class K, class Comp>
1287 bool claw::avl_base<K, Comp>::operator>=( const avl_base<K, Comp>& that ) const
1289 return !( *this < that );
1290 } // avl_base::operator>=()
1292 /*----------------------------------------------------------------------------*/
1294 * \brief Swap the values with an other tree.
1295 * \param that The other tree.
1297 template<class K, class Comp>
1298 void claw::avl_base<K, Comp>::swap( avl_base<K, Comp>& that )
1300 std::swap(m_size, that.m_size);
1301 std::swap(m_tree, that.m_tree);
1302 } // avl_base::swap()
1304 /*================================= private =================================*/
1306 //-----------------------------------------------------------------------------
1307 // We need some methods to check the validity of our trees
1309 /*----------------------------------------------------------------------------*/
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.
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
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 );
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()
1336 /*----------------------------------------------------------------------------*/
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.
1345 template<class K, class Comp>
1346 bool claw::avl_base<K,Comp>::check_balance( const avl_node_ptr node ) const
1354 if (node->left) pl = node->left->depth();
1355 if (node->right) pr = node->right->depth();
1357 return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
1358 && check_balance(node->left) && check_balance(node->right);
1360 } // check_balance()
1362 /*----------------------------------------------------------------------------*/
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.
1369 template<class K, class Comp>
1370 bool claw::avl_base<K,Comp>::correct_descendant( const avl_node_ptr node ) const
1376 if (node->father != NULL)
1378 valid = (node->father->left == node) ^ (node->father->right == node);
1379 valid = valid && correct_descendant( node->left )
1380 && correct_descendant( node->right );
1387 } // correct_descendant()
1389 /*----------------------------------------------------------------------------*/
1391 * \brief This method will check orderliness in our trees : balance and order.
1393 * \remark For validity check.
1394 * \return true if the AVL is valid, false otherwise.
1396 template<class K, class Comp>
1397 bool claw::avl_base<K,Comp>::validity_check() const
1403 avl_node *node_min, *node_max;
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);
1410 valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
1412 && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
1414 valid = valid && (m_tree->father == NULL)
1415 && correct_descendant( m_tree->left )
1416 && correct_descendant( m_tree->right );
1420 return valid && check_balance(m_tree);
1421 } // validity_check()
1427 /*----------------------------------------------------------------------------*/
1429 * \brief Create an iterator from a pointer to a node.
1430 * \param node The node on which we want the iterator.
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
1437 return iterator(node, false);
1440 } // avl_base::make_iterator()
1442 /*----------------------------------------------------------------------------*/
1444 * \brief Create an iterator from a pointer to a node.
1445 * \param node The node on which we want the iterator.
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
1452 return const_iterator(node, false);
1455 } // avl_base::make_const_iterator()
1460 //-----------------------------------------------------------------------------
1461 // Tree management methods
1463 /*----------------------------------------------------------------------------*/
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)
1471 template<class K, class Comp>
1472 void claw::avl_base<K,Comp>::rotate_right( avl_node_ptr& node )
1475 char old_node_balance;
1476 char old_subtree_balance;
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) );
1484 old_node_balance = node->balance;
1485 old_subtree_balance = node->left->balance;
1489 p->father = node->father;
1491 node->left = p->right;
1494 p->right->father = node;
1502 switch(old_subtree_balance)
1506 node->right->balance = old_node_balance - 1;
1510 node->right->balance = old_node_balance - 1;
1513 node->balance = old_node_balance - 2;
1514 node->right->balance = old_node_balance - 2;
1517 // old_node_balance is 2 too.
1519 node->right->balance = - 1;
1524 /*----------------------------------------------------------------------------*/
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)
1532 template<class K, class Comp>
1533 void claw::avl_base<K,Comp>::rotate_left( avl_node_ptr& node )
1536 char old_node_balance;
1537 char old_subtree_balance;
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) );
1545 old_node_balance = node->balance;
1546 old_subtree_balance = node->right->balance;
1550 p->father = node->father;
1552 node->right = p->left;
1555 p->left->father = node;
1563 switch(old_subtree_balance)
1566 // old_node_balance is -2 too.
1568 node->left->balance = 1;
1571 node->balance = old_node_balance + 2;
1572 node->left->balance = old_node_balance + 2;
1576 node->left->balance = old_node_balance + 1;
1580 node->left->balance = old_node_balance + 1;
1585 /*----------------------------------------------------------------------------*/
1587 * \brief Node left-right rotation
1588 * \param node Node to rotate.
1590 template<class K, class Comp>
1591 void claw::avl_base<K,Comp>::rotate_left_right( avl_node_ptr& node )
1593 assert( node != NULL );
1595 rotate_left( node->left );
1596 rotate_right( node );
1597 } // rotate_left_right()
1599 /*----------------------------------------------------------------------------*/
1601 * \brief Node right-left rotation
1602 * \param node Node to rotate.
1604 template<class K, class Comp>
1605 void claw::avl_base<K,Comp>::rotate_right_left( avl_node_ptr& node )
1607 assert( node != NULL );
1609 rotate_right( node->right );
1610 rotate_left( node );
1611 } // rotate_right_left()
1613 /*----------------------------------------------------------------------------*/
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
1622 template<class K, class Comp>
1623 void claw::avl_base<K,Comp>::update_balance( avl_node_ptr node, const K& key )
1625 assert(node != NULL);
1629 if ( s_key_less(key, node->key) )
1634 else if ( s_key_less(node->key, key) )
1641 } // update_balance()
1643 /*----------------------------------------------------------------------------*/
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]
1650 template<class K, class Comp>
1651 void claw::avl_base<K,Comp>::adjust_balance( avl_node_ptr& node )
1653 assert(node != NULL);
1655 if ( node->balance == 2)
1656 adjust_balance_left(node);
1657 else if ( node->balance == -2)
1658 adjust_balance_right(node);
1659 } // adjust_balance()
1661 /*----------------------------------------------------------------------------*/
1663 * \brief Adjust balance of a node leaning on the left so it will be
1665 * \param node Node to adjust.
1666 * \pre (node != NULL) && (*node != NULL) && ( (*node)->balance == 2).
1667 * \post node->balance is in range [-1;1]
1669 template<class K, class Comp>
1670 void claw::avl_base<K,Comp>::adjust_balance_left( avl_node_ptr& node )
1672 assert(node != NULL);
1673 assert(node->balance == 2);
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()
1681 /*----------------------------------------------------------------------------*/
1683 * \brief Adjust balance of a node leaning on the right so it will be
1685 * \param node Node to adjust.
1686 * \pre (node != NULL) && (*node != NULL) && ( (*node)->balance == -2).
1687 * \post node->balance is in range [-1;1]
1689 template<class K, class Comp>
1690 void claw::avl_base<K,Comp>::adjust_balance_right( avl_node_ptr& node )
1692 assert(node != NULL);
1693 assert(node->balance == -2);
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()
1702 /*----------------------------------------------------------------------------*/
1703 // Methods for insertion
1704 /*----------------------------------------------------------------------------*/
1707 /*----------------------------------------------------------------------------*/
1709 * \brief Add a node to the tree.
1710 * \param key Key for the new value.
1712 * && (exists(old this, key)==0 => size(this) == size(old this) + 1 )
1714 template<class K, class Comp>
1715 void claw::avl_base<K,Comp>::insert_node( const K& key )
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;
1722 assert(m_tree != NULL);
1724 new_node = find_node_reference(key, last_imbalanced, node_father );
1726 if (*new_node == NULL) // this key isn't in use. Let's create a new node
1728 *new_node = new avl_node(key);
1729 (*new_node)->father = node_father;
1732 last_imbalanced_father = last_imbalanced->father;
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 );
1739 // pointer update after rotation
1740 if ( last_imbalanced_father == NULL )
1742 m_tree = last_imbalanced;
1743 m_tree->father = NULL;
1745 else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key))
1747 last_imbalanced_father->left = last_imbalanced;
1749 last_imbalanced_father->right = last_imbalanced;
1753 /*----------------------------------------------------------------------------*/
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 )
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)
1771 avl_node_ptr* node; // node for search
1772 bool exists = false; // if this key already exists
1774 last_imbalanced = m_tree;
1778 while ( ((*node) != NULL) && !exists )
1780 if ( (*node)->balance != 0 )
1781 last_imbalanced = *node;
1785 if ( s_key_less(key, (*node)->key) )
1787 node_father = *node;
1788 node = & (*node)->left;
1790 else if ( s_key_less((*node)->key, key) )
1792 node_father = *node;
1793 node = & (*node)->right;
1800 } // find_node_reference()
1803 /*----------------------------------------------------------------------------*/
1804 // Methods for deletion
1805 /*----------------------------------------------------------------------------*/
1808 /*----------------------------------------------------------------------------*/
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.
1815 * \post (exists(this, key) == 0)
1817 template<class K, class Comp>
1819 claw::avl_base<K,Comp>::recursive_delete( avl_node_ptr& node, const K& key )
1821 bool result = false;
1825 // try to find the key in the left subtree
1826 if ( s_key_less(key, node->key) )
1828 if ( recursive_delete( node->left, key ) )
1829 result = new_balance( node, -1 );
1831 // try to find the key in the right subtree
1832 else if ( s_key_less(node->key, key) )
1834 if ( recursive_delete( node->right, key ) )
1835 result = new_balance( node, 1 );
1840 result = recursive_delete_node( node );
1845 } // recursive_delete()
1848 /*----------------------------------------------------------------------------*/
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.
1855 * \pre (imbalance==1) || (imbalance==-1)
1856 * \post node tree is an AVL
1858 template<class K, class Comp>
1859 bool claw::avl_base<K,Comp>::new_balance( avl_node_ptr& node, int imbalance )
1861 assert( (imbalance==1) || (imbalance==-1) );
1862 assert( node != NULL );
1864 node->balance += imbalance;
1866 switch(node->balance)
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;
1884 /*----------------------------------------------------------------------------*/
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.
1891 * \post node tree is an AVL
1893 template<class K, class Comp>
1894 bool claw::avl_base<K,Comp>::recursive_delete_node( avl_node_ptr& node )
1896 assert( node != NULL );
1898 if ( node->left == NULL) // this node doesn't have a lower descendant
1900 // Get right subtree of current node
1901 avl_node_ptr right_subtree = node->right;
1904 right_subtree->father = node->father;
1906 // Free memory pointed by the current node
1910 // then rise the old right subtree
1911 node = right_subtree;
1915 else // this node has a lower descendant, let's get it
1916 if ( recursive_delete_max( node->left, node ) )
1918 // left subtree depth has decreased
1919 // so reajust balance (rem. balance is not changed by delete_max)
1922 if ( node->balance == -2 )
1924 // old balance was -1
1925 adjust_balance_right(node);
1926 return node->balance == 0; // tell if depth has changed
1928 else if ( node->balance == 0 )
1929 // node had at least one subtree and old balance - 1 == 0
1930 // so old balance = 1
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.
1945 else // depth is unchanged
1947 } // recursive_delete_node()
1949 /*----------------------------------------------------------------------------*/
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.
1958 * \pre root is an AVL
1959 * \post (root tree is an AVL) && (find(root, max(old root)) == 0)
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 )
1968 if ( root->right == NULL ) // We have the maximum
1970 // node have only a left subtree if any.
1971 // This subtree has one node, at most.
1972 avl_node_ptr left_subtree;
1974 node->key = root->key;
1975 left_subtree = root->left;
1978 left_subtree->father = root->father;
1983 // rise the left subtree
1984 root = left_subtree;
1986 // depth have changed
1989 else // try to find the max in the right subtree
1990 if ( recursive_delete_max( root->right, node ) )
1992 // depth of the subtree changed (ie. decreased)
1993 // so root's tree lean to the left
1996 if (root->balance == 2) // tree is leaning too much
1998 // old balance was 1
1999 adjust_balance_left( root );
2000 return root->balance == 0; // Say if balance is changed
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;
2009 else // depth of the subtree didn't change
2011 } // recursive_delete_max()