claw::avl_base< K, Comp > Class Template Reference

Binary search tree base AVL implementation. More...

#include <avl_base.hpp>

List of all members.

Classes

class  avl_const_iterator
 AVL iterator. More...
class  avl_iterator
 AVL iterator. More...
class  avl_node
 Node of a binary search tree (AVL). More...

Public Types

typedef K value_type
typedef K key_type
typedef K referent_type
typedef Comp key_less
typedef const K & const_reference
typedef avl_iterator iterator
typedef avl_const_iterator const_iterator

Public Member Functions

 avl_base ()
 AVL constructor.
 avl_base (const avl_base< K, Comp > &that)
 AVL copy constructor.
 ~avl_base ()
 AVL destructor.
void insert (const K &key)
 Add a value in a tree.
template<typename Iterator >
void insert (Iterator first, Iterator last)
 Add a range of items in the tree.
void erase (const K &key)
 Delete a value in a tree.
void clear ()
 Clear a tree.
unsigned int size () const
 Get the size of a tree.
bool empty () const
 Tell if a tree is empty or not.
iterator begin ()
 Get an iterator on the nodes of the tree.
const_iterator begin () const
 Get an iterator on the nodes of the tree.
iterator end ()
 Get an iterator after the end of the tree.
const_iterator end () const
 Get an iterator after the end of the tree.
iterator find (const K &key)
 Get an iterator on the nodes of the tree from a specified key.
const_iterator find (const K &key) const
 Get an iterator on the nodes of the tree from a specified key.
iterator find_nearest_greater (const K &key)
 Get an iterator on the nodes of the tree on the key imediatly after from a specified key.
const_iterator find_nearest_greater (const K &key) const
 Get an iterator on the nodes of the tree on the key imediatly after from a specified key.
iterator find_nearest_lower (const K &key)
 Get an iterator on the nodes of the tree on the key imediatly before from a specified key.
const_iterator find_nearest_lower (const K &key) const
 Get an iterator on the nodes of the tree on the key imediatly before from a specified key.
iterator lower_bound ()
 Get an iterator on the lowest value of the tree.
const_iterator lower_bound () const
 Get an iterator on the lowest value of the tree.
iterator upper_bound ()
 Get an iterator on the gratest value of the tree.
const_iterator upper_bound () const
 Get an iterator on the gratest value of the tree.
avl_base< K, Comp > & operator= (const avl_base< K, Comp > &that)
 Assignment operator.
bool operator== (const avl_base< K, Comp > &that) const
 Equality.
bool operator!= (const avl_base< K, Comp > &that) const
 Disequality.
bool operator< (const avl_base< K, Comp > &that) const
 Less than operator.
bool operator> (const avl_base< K, Comp > &that) const
 Greater than operator.
bool operator<= (const avl_base< K, Comp > &that) const
 Less or equal operator.
bool operator>= (const avl_base< K, Comp > &that) const
 Greater or equal operator.
void swap (avl_base< K, Comp > &that)
 Swap the values with an other tree.

Static Public Attributes

static key_less s_key_less
 Function object used to compare keys.

Private Types

typedef avl_nodeavl_node_ptr
typedef avl_node const * const_avl_node_ptr

Private Member Functions

bool check_in_bounds (const avl_node_ptr node, const K &min, const K &max) const
 This method will check order in our trees.
bool check_balance (const avl_node_ptr node) const
 This method will check balance in our trees.
bool correct_descendant (const avl_node_ptr node) const
 This method will check if each node is a son of his father.
bool validity_check () const
 This method will check orderliness in our trees : balance and order.
iterator make_iterator (avl_node_ptr node) const
 Create an iterator from a pointer to a node.
const_iterator make_const_iterator (const_avl_node_ptr node) const
 Create an iterator from a pointer to a node.
void rotate_right (avl_node_ptr &node)
 Node right rotation.
void rotate_left (avl_node_ptr &node)
 Node left rotation.
void rotate_left_right (avl_node_ptr &node)
 Node left-right rotation.
void rotate_right_left (avl_node_ptr &node)
 Node right-left rotation.
void update_balance (avl_node_ptr node, const K &key)
 Update balance of each node by increasing depth of the substree containing key, from node to the node key.
void adjust_balance (avl_node_ptr &node)
 Adjust balance of a node so it will be in range [-1;1].
void adjust_balance_left (avl_node_ptr &node)
 Adjust balance of a node leaning on the left so it will be in range [-1;1].
void adjust_balance_right (avl_node_ptr &node)
 Adjust balance of a node leaning on the right so it will be in range [-1;1].
void insert_node (const K &key)
 Add a node to the tree.
avl_node_ptrfind_node_reference (const K &key, avl_node_ptr &last_imbalanced, avl_node_ptr &node_father)
 Find the node where to insert a new value at key.
bool recursive_delete (avl_node_ptr &node, const K &key)
 Delete a node. Search is done recursively.
bool new_balance (avl_node_ptr &node, int imbalance)
 Adjust balance of a node.
bool recursive_delete_node (avl_node_ptr &node)
 Remove the root of an AVL (exchange with the descendant immediatly lower).
int recursive_delete_max (avl_node_ptr &root, avl_node_ptr node)
 Replace a node key and data by the one of the node with the maximum key in tree.

Private Attributes

unsigned int m_size
 Nodes count.
avl_node_ptr m_tree
 Nodes.

Detailed Description

template<class K, class Comp = std::less<K>>
class claw::avl_base< K, Comp >

Binary search tree base AVL implementation.

Each key appears only once. Nodes are sorted as left_child < node < right_child.

Invariant:
this->empty() <==> (this->size() == 0)
this is an AVL.
Remarks:
Type requirements :
  • K is LessThanComparable ;
  • Comp is a binary predicate such that Comp(K a, K b) == true if a < b.
Code is taken from a C implementation, so perhaps it doesn't really look nice for C++. Nevertheless it works perfectly and it's fast conversion : that good things.
Author:
Julien Jorge

Definition at line 56 of file avl_base.hpp.


Member Typedef Documentation

template<class K, class Comp = std::less<K>>
typedef avl_node* claw::avl_base< K, Comp >::avl_node_ptr [private]

Definition at line 122 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef avl_node const* claw::avl_base< K, Comp >::const_avl_node_ptr [private]

Definition at line 123 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef avl_const_iterator claw::avl_base< K, Comp >::const_iterator

Definition at line 205 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef const K& claw::avl_base< K, Comp >::const_reference

Definition at line 203 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef avl_iterator claw::avl_base< K, Comp >::iterator

Definition at line 204 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef Comp claw::avl_base< K, Comp >::key_less

Definition at line 202 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef K claw::avl_base< K, Comp >::key_type

Definition at line 200 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef K claw::avl_base< K, Comp >::referent_type

Definition at line 201 of file avl_base.hpp.

template<class K, class Comp = std::less<K>>
typedef K claw::avl_base< K, Comp >::value_type

Definition at line 199 of file avl_base.hpp.


Constructor & Destructor Documentation

template<class K , class Comp >
claw::avl_base< K, Comp >::avl_base (  )  [inline]

AVL constructor.

Postcondition:
empty()

Definition at line 903 of file avl_base.tpp.

00904   : m_size(0), m_tree(NULL) 
00905 {
00906 
00907 } // avl_base::avl_base() [constructeur]

template<class K, class Comp>
claw::avl_base< K, Comp >::avl_base ( const avl_base< K, Comp > &  that  )  [inline, explicit]

AVL copy constructor.

Parameters:
that AVL instance to copy from.

Definition at line 915 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.

00916 {
00917   m_size = 0;
00918 
00919   if (that.m_tree)
00920     m_tree = that.m_tree->duplicate( m_size );
00921   else
00922     m_tree = NULL;
00923 } // avl_base::avl_base() [copy constructor]

template<class K , class Comp >
claw::avl_base< K, Comp >::~avl_base (  )  [inline]

AVL destructor.

Definition at line 930 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::del_tree(), and claw::avl_base< K, Comp >::m_tree.

00931 {
00932   if (m_tree)
00933     {
00934       m_tree->del_tree();
00935       delete m_tree;
00936     }
00937 } // avl_base::~avl_base() [destructeur]


Member Function Documentation

template<class K , class Comp >
void claw::avl_base< K, Comp >::adjust_balance ( avl_node_ptr node  )  [inline, private]

Adjust balance of a node so it will be in range [-1;1].

Parameters:
node Node to adjust.
Precondition:
(node != NULL).
Postcondition:
node->balance is in range [-1;1]

Definition at line 1663 of file avl_base.tpp.

References claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::adjust_balance_right(), and claw::avl_base< K, Comp >::avl_node::balance.

Referenced by claw::avl_base< K, Comp >::insert_node().

01664 {
01665   assert(node != NULL);
01666 
01667   if ( node->balance == 2)
01668     adjust_balance_left(node);
01669   else if ( node->balance == -2)
01670     adjust_balance_right(node);
01671 } // adjust_balance()

template<class K , class Comp >
void claw::avl_base< K, Comp >::adjust_balance_left ( avl_node_ptr node  )  [inline, private]

Adjust balance of a node leaning on the left so it will be in range [-1;1].

Parameters:
node Node to adjust.
Precondition:
(node != NULL) && (*node != NULL) && ( (*node)->balance == 2).
Postcondition:
node->balance is in range [-1;1]

Definition at line 1682 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::left, claw::avl_base< K, Comp >::rotate_left_right(), and claw::avl_base< K, Comp >::rotate_right().

Referenced by claw::avl_base< K, Comp >::adjust_balance(), and claw::avl_base< K, Comp >::new_balance().

01683 {
01684   assert(node != NULL);
01685   assert(node->balance == 2);
01686 
01687   if (node->left->balance > -1)
01688     rotate_right( node );
01689   else if ( node->left->balance == -1)
01690     rotate_left_right(node);
01691 } // adjust_balance_left()

template<class K , class Comp >
void claw::avl_base< K, Comp >::adjust_balance_right ( avl_node_ptr node  )  [inline, private]

Adjust balance of a node leaning on the right so it will be in range [-1;1].

Parameters:
node Node to adjust.
Precondition:
(node != NULL) && (*node != NULL) && ( (*node)->balance == -2).
Postcondition:
node->balance is in range [-1;1]

Definition at line 1702 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::right, claw::avl_base< K, Comp >::rotate_left(), and claw::avl_base< K, Comp >::rotate_right_left().

Referenced by claw::avl_base< K, Comp >::adjust_balance(), claw::avl_base< K, Comp >::new_balance(), and claw::avl_base< K, Comp >::recursive_delete_node().

01703 {
01704   assert(node != NULL);
01705   assert(node->balance == -2);
01706 
01707   if (node->right->balance < 1)
01708     rotate_left( node );
01709   else if ( node->right->balance == 1)
01710     rotate_right_left(node);
01711 } // adjust_balance_right()

template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::begin (  )  const [inline]

Get an iterator on the nodes of the tree.

Definition at line 1053 of file avl_base.tpp.

References claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::m_tree.

01054 {
01055   if (m_tree == NULL)
01056     return const_iterator(NULL, true);
01057   else
01058     return lower_bound();
01059 } // avl_base::begin()

template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::begin (  )  [inline]

Get an iterator on the nodes of the tree.

Definition at line 1039 of file avl_base.tpp.

References claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::m_tree.

Referenced by claw::avl< K, Comp >::begin(), claw::avl_base< K, Comp >::operator<(), and claw::avl_base< K, Comp >::operator==().

01040 {
01041   if (m_tree == NULL)
01042     return iterator(NULL, true);
01043   else
01044     return lower_bound();
01045 } // avl_base::begin()

template<class K , class Comp >
bool claw::avl_base< K, Comp >::check_balance ( const avl_node_ptr  node  )  const [inline, private]

This method will check balance in our trees.

Parameters:
node Root of the tree to check.
Remarks:
For validity check.
Returns:
true if the absolute difference between left subtree's depth and right subtree's depth is 1 for node and each of its subtrees. false otherwise.

Definition at line 1358 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::depth(), claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::validity_check().

01359 {
01360   int pl=0, pr=0;
01361 
01362   if (node == NULL)
01363     return true;
01364   else
01365     {
01366       if (node->left) pl = node->left->depth();
01367       if (node->right) pr = node->right->depth();
01368 
01369       return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
01370         && check_balance(node->left) && check_balance(node->right);
01371     }
01372 } // check_balance()

template<class K, class Comp >
bool claw::avl_base< K, Comp >::check_in_bounds ( const avl_node_ptr  node,
const K &  min,
const K &  max 
) const [inline, private]

This method will check order in our trees.

Parameters:
node Root of the tree to check.
min Lower bound of the valid range for tree's nodes.
max Higher bound of the valid range for tree's nodes.
Remarks:
For validity check.
Returns:
true if bounds are ok, false otherwise.

Definition at line 1332 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::validity_check().

01333 {
01334   if (node == NULL)
01335     return true;
01336   else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) )
01337     return (node->left == NULL) 
01338       && check_in_bounds( node->right, node->key, max );
01339   else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) )
01340     return (node->right == NULL) 
01341       && check_in_bounds( node->left, min, node->key );
01342   else
01343     return s_key_less(node->key, max) && s_key_less(min, node->key) 
01344       && check_in_bounds( node->left, min, node->key )
01345       && check_in_bounds( node->right, node->key, max );
01346 } // check_less_than()

template<class K , class Comp >
void claw::avl_base< K, Comp >::clear (  )  [inline]

Clear a tree.

Postcondition:
empty()

Definition at line 1000 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::del_tree(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.

Referenced by claw::avl< K, Comp >::clear().

01001 {
01002   if (m_tree != NULL)
01003     {
01004       m_tree->del_tree();
01005       delete m_tree;
01006                         
01007       m_tree = NULL;
01008       m_size = 0;
01009     }
01010 } // avl_base::clear()

template<class K , class Comp >
bool claw::avl_base< K, Comp >::correct_descendant ( const avl_node_ptr  node  )  const [inline, private]

This method will check if each node is a son of his father.

Parameters:
node Node to check.
Remarks:
For validity check.
Returns:
true if the AVL is valid, false otherwise.

Definition at line 1382 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::validity_check().

01383 {
01384   bool valid = true;
01385 
01386   if (node != NULL)
01387     {
01388       if (node->father != NULL)
01389         {
01390           valid = (node->father->left == node) ^ (node->father->right == node);
01391           valid = valid && correct_descendant( node->left ) 
01392             && correct_descendant( node->right );
01393         }
01394       else
01395         valid = false;
01396     }
01397           
01398   return valid;
01399 } // correct_descendant()

template<class K , class Comp >
bool claw::avl_base< K, Comp >::empty (  )  const [inline]

Tell if a tree is empty or not.

Returns:
true if the tree is empty, false otherwise.

Definition at line 1029 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_size.

Referenced by claw::avl< K, Comp >::empty().

01030 {
01031   return m_size == 0; 
01032 } // avl_base::empty()

template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::end (  )  const [inline]

Get an iterator after the end of the tree.

Definition at line 1080 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::avl_node::upper_bound().

01081 {
01082   if (m_tree == NULL)
01083     return const_iterator(NULL, true);
01084   else
01085     return const_iterator(m_tree->upper_bound(), true);
01086 } // avl_base::end()

template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::end (  )  [inline]

Get an iterator after the end of the tree.

Definition at line 1066 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::avl_node::upper_bound().

Referenced by claw::avl< K, Comp >::end(), claw::avl_base< K, Comp >::make_const_iterator(), claw::avl_base< K, Comp >::make_iterator(), claw::avl_base< K, Comp >::operator<(), and claw::avl_base< K, Comp >::operator==().

01067 {
01068   if (m_tree == NULL)
01069     return iterator(NULL, true);
01070   else
01071     return iterator(m_tree->upper_bound(), true);
01072 } // avl_base::end()

template<class K, class Comp >
void claw::avl_base< K, Comp >::erase ( const K &  key  )  [inline]

Delete a value in a tree.

Parameters:
key Node key.
Postcondition:
not exists(key)

Definition at line 984 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_tree, claw::avl_base< K, Comp >::recursive_delete(), and claw::avl_base< K, Comp >::validity_check().

Referenced by claw::avl< K, Comp >::erase().

00985 {
00986   assert( validity_check() );
00987 
00988   if (m_tree != NULL)
00989     recursive_delete( m_tree, key );
00990 
00991   assert( validity_check() );
00992 } // avl_base::erase()

template<class K, class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find ( const K &  key  )  const [inline]

Get an iterator on the nodes of the tree from a specified key.

Parameters:
key Key to find.

Definition at line 1107 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::find(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().

01108 {
01109   return make_const_iterator( m_tree->find(key) );
01110 } // avl_base::find()

template<class K, class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find ( const K &  key  )  [inline]

Get an iterator on the nodes of the tree from a specified key.

Parameters:
key Key to find.

Definition at line 1095 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::find(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().

Referenced by claw::avl< K, Comp >::find().

01096 {
01097   return make_iterator( m_tree->find(key) );
01098 } // avl_base::find()

template<class K, class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find_nearest_greater ( const K &  key  )  const [inline]

Get an iterator on the nodes of the tree on the key imediatly after from a specified key.

Parameters:
key Key to find.

Definition at line 1133 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::find_nearest_greater(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().

01134 {
01135   return make_const_iterator( m_tree->find_nearest_greater(key) );
01136 } // avl_base::find_nearest_greater()

template<class K, class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_greater ( const K &  key  )  [inline]

Get an iterator on the nodes of the tree on the key imediatly after from a specified key.

Parameters:
key Key to find.

Definition at line 1120 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::find_nearest_greater(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().

Referenced by claw::avl< K, Comp >::find_nearest_greater().

01121 {
01122   return make_iterator( m_tree->find_nearest_greater(key) );
01123 } // avl_base::find_nearest_greater()

template<class K, class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find_nearest_lower ( const K &  key  )  const [inline]

Get an iterator on the nodes of the tree on the key imediatly before from a specified key.

Parameters:
key Key to find.

Definition at line 1159 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().

01160 {
01161   return make_const_iterator( m_tree->find_nearest_lower(key) );
01162 } // avl_base::find_nearest_lower()

template<class K, class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_lower ( const K &  key  )  [inline]

Get an iterator on the nodes of the tree on the key imediatly before from a specified key.

Parameters:
key Key to find.

Definition at line 1146 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().

Referenced by claw::avl< K, Comp >::find_nearest_lower().

01147 {
01148   return make_iterator( m_tree->find_nearest_lower(key) );
01149 } // avl_base::find_nearest_lower()

template<class K, class Comp >
claw::avl_base< K, Comp >::avl_node_ptr * claw::avl_base< K, Comp >::find_node_reference ( const K &  key,
avl_node_ptr last_imbalanced,
avl_node_ptr node_father 
) [inline, private]

Find the node where to insert a new value at key.

Parameters:
key Key for the new value.
last_imbalanced (out) Pointer to the last imbalanced node seen.
node_father (out) Pointer to the father of the new node.
Returns:
Pointer to the node corresponding of the key (if exists). Otherwise a pointer to a NULL node where to insert the new one.
Postcondition:
( exists(this, key) => *result == find(this, key) ) && ( !exists(this, key) => *result the good node to allocate ) && ( *last_imbalance and *last_imbalance are correct regarding to previous definitions )

Definition at line 1781 of file avl_base.tpp.

References claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::insert_node().

01782 {
01783   avl_node_ptr* node; // node for search
01784   bool exists;        // if this key already exists
01785 
01786   last_imbalanced = m_tree;
01787   node = & m_tree;
01788   node_father = NULL;
01789   exists = false;
01790 
01791   while ( ((*node) != NULL) && !exists )
01792     {
01793       if ( (*node)->balance != 0 )
01794         last_imbalanced = *node;
01795 
01796                   
01797       // find next node
01798       if ( s_key_less(key, (*node)->key) )
01799         {
01800           node_father = *node;
01801           node = & (*node)->left;
01802         }
01803       else if ( s_key_less((*node)->key, key) )
01804         {
01805           node_father = *node;
01806           node = & (*node)->right;
01807         }
01808       else
01809         exists = true;
01810     }
01811 
01812   return node;
01813 } // find_node_reference()

template<class K , class Comp >
template<typename Iterator >
void claw::avl_base< K, Comp >::insert ( Iterator  first,
Iterator  last 
) [inline]

Add a range of items in the tree.

Parameters:
first Iterator on the first item to add.
last Iterator past the last item to add.
Precondition:
Iterator::value_type is K
Postcondition:
exists( *it ) for all it in [first, last)

Definition at line 971 of file avl_base.tpp.

References claw::avl_base< K, Comp >::insert().

00972 {
00973   for ( ; first!=last; ++first )
00974     insert( *first );
00975 } // avl_base::insert()

template<class K, class Comp >
void claw::avl_base< K, Comp >::insert ( const K &  key  )  [inline]

Add a value in a tree.

Parameters:
key Node key.
Postcondition:
exists(key)

Definition at line 946 of file avl_base.tpp.

References claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::validity_check().

Referenced by claw::avl< K, Comp >::avl(), claw::avl_base< K, Comp >::insert(), and claw::avl< K, Comp >::insert().

00947 {
00948   assert( validity_check() );
00949 
00950   if ( m_tree == NULL )
00951     {
00952       m_tree = new avl_node(key);
00953       m_size = 1;
00954     }
00955   else
00956     insert_node(key);
00957 
00958   assert( validity_check() );
00959 } // avl_base::insert()

template<class K, class Comp >
void claw::avl_base< K, Comp >::insert_node ( const K &  key  )  [inline, private]

Add a node to the tree.

Parameters:
key Key for the new value.
Postcondition:
exists(key) && (exists(old this, key)==0 => size(this) == size(old this) + 1 )

Definition at line 1727 of file avl_base.tpp.

References claw::avl_base< K, Comp >::adjust_balance(), claw::avl_base< K, Comp >::avl_node::father, claw::avl_base< K, Comp >::find_node_reference(), claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::m_tree, claw::binary_node< U >::right, claw::avl_base< K, Comp >::s_key_less, and claw::avl_base< K, Comp >::update_balance().

Referenced by claw::avl_base< K, Comp >::insert().

01728 {
01729   avl_node_ptr* new_node;
01730   avl_node_ptr node_father;
01731   avl_node_ptr last_imbalanced;
01732   avl_node_ptr last_imbalanced_father;
01733           
01734   assert(m_tree != NULL);
01735   
01736   new_node = find_node_reference(key, last_imbalanced, node_father  );
01737 
01738   if (*new_node == NULL) // this key isn't in use. Let's create a new node
01739     {
01740       *new_node = new avl_node(key);
01741       (*new_node)->father = node_father;
01742 
01743       ++m_size;
01744       last_imbalanced_father = last_imbalanced->father;
01745 
01746       // Update balance of the last imbalanced node
01747       update_balance( last_imbalanced, key );
01748       // then adjust it to be in range [-1, 1]
01749       adjust_balance( last_imbalanced );
01750                   
01751       // pointer update after rotation
01752       if ( last_imbalanced_father == NULL )
01753         {
01754           m_tree = last_imbalanced;
01755           m_tree->father = NULL;
01756         }
01757       else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key)) 
01758         // left child
01759         last_imbalanced_father->left = last_imbalanced;
01760       else
01761         last_imbalanced_father->right = last_imbalanced;
01762     }
01763 } // insert_node()

template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::lower_bound (  )  const [inline]

Get an iterator on the lowest value of the tree.

Definition at line 1180 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::lower_bound(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_const_iterator().

01181 {
01182   return make_const_iterator( m_tree->lower_bound() );
01183 } // avl_base::lower_bound()

template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::lower_bound (  )  [inline]

Get an iterator on the lowest value of the tree.

Definition at line 1169 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::lower_bound(), claw::avl_base< K, Comp >::m_tree, and claw::avl_base< K, Comp >::make_iterator().

Referenced by claw::avl_base< K, Comp >::begin(), and claw::avl< K, Comp >::lower_bound().

01170 {
01171   return make_iterator( m_tree->lower_bound() );
01172 } // avl_base::lower_bound()

template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::make_const_iterator ( const_avl_node_ptr  node  )  const [inline, private]

Create an iterator from a pointer to a node.

Parameters:
node The node on which we want the iterator.

Definition at line 1461 of file avl_base.tpp.

References claw::avl_base< K, Comp >::end().

Referenced by claw::avl_base< K, Comp >::find(), claw::avl_base< K, Comp >::find_nearest_greater(), claw::avl_base< K, Comp >::find_nearest_lower(), claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::upper_bound().

01462 {
01463   if (node != NULL)
01464     return const_iterator(node, false);
01465   else
01466     return end();
01467 } // avl_base::make_const_iterator()

template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::make_iterator ( avl_node_ptr  node  )  const [inline, private]

Create an iterator from a pointer to a node.

Parameters:
node The node on which we want the iterator.

Definition at line 1446 of file avl_base.tpp.

References claw::avl_base< K, Comp >::end().

Referenced by claw::avl_base< K, Comp >::find(), claw::avl_base< K, Comp >::find_nearest_greater(), claw::avl_base< K, Comp >::find_nearest_lower(), claw::avl_base< K, Comp >::lower_bound(), and claw::avl_base< K, Comp >::upper_bound().

01447 {
01448   if (node != NULL)
01449     return iterator(node, false);
01450   else
01451     return end();
01452 } // avl_base::make_iterator()

template<class K , class Comp >
bool claw::avl_base< K, Comp >::new_balance ( avl_node_ptr node,
int  imbalance 
) [inline, private]

Adjust balance of a node.

Parameters:
node Node to balance.
imbalance Imbalance to add to the node's balance.
Returns:
true if the balance of the node has changed.
Precondition:
node != NULL
(imbalance==1) || (imbalance==-1)
Postcondition:
node tree is an AVL

Definition at line 1872 of file avl_base.tpp.

References claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::adjust_balance_right(), and claw::avl_base< K, Comp >::avl_node::balance.

Referenced by claw::avl_base< K, Comp >::recursive_delete().

01873 {
01874   assert( (imbalance==1) || (imbalance==-1) );
01875   assert( node != NULL );
01876 
01877   node->balance += imbalance;
01878 
01879   switch(node->balance)
01880     {
01881       // balance == 0 so as it was != 0 before deletion
01882       // balance of the tree had changed
01883     case 0: return true;
01884       // balance == 2 so it must be 1 before deletion and node
01885       // was deleted in the right subtree
01886       // if after ajusting the balance is equal to 1, it means that
01887       // our subtree got back his old balance (so it's unchanged).
01888       // if it's equal to -1, it means that subtree now lean to the
01889       // otherside. But in those cases, depth didn't changed.
01890     case 2: adjust_balance_left(node); return node->balance == 0;
01891       // same thing but symetric
01892     case -2: adjust_balance_right(node); return node->balance == 0;
01893     default : return false;
01894     }
01895 } // new_balance()

template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator!= ( const avl_base< K, Comp > &  that  )  const [inline]

Disequality.

Parameters:
that AVL top compare to.

Definition at line 1254 of file avl_base.tpp.

01255 {
01256   return !( *this == that );
01257 } // avl_base::operator!=()

template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator< ( const avl_base< K, Comp > &  that  )  const [inline]

Less than operator.

Parameters:
that AVL top compare to.

Definition at line 1265 of file avl_base.tpp.

References claw::avl_base< K, Comp >::begin(), claw::avl_base< K, Comp >::end(), and claw::avl_base< K, Comp >::s_key_less.

01266 {
01267   return std::lexicographical_compare
01268     ( begin(), end(), that.begin(), that.end(), s_key_less );
01269 } // avl_base::operator<()

template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator<= ( const avl_base< K, Comp > &  that  )  const [inline]

Less or equal operator.

Parameters:
that AVL top compare to.

Definition at line 1288 of file avl_base.tpp.

01289 {
01290   return !( that < *this );
01291 } // avl_base::operator<=()

template<class K, class Comp>
claw::avl_base< K, Comp > & claw::avl_base< K, Comp >::operator= ( const avl_base< K, Comp > &  that  )  [inline]

Assignment operator.

Parameters:
that AVL instance to copy from.

Definition at line 1213 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::del_tree(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.

01214 {
01215   if (this != &that)
01216     {
01217       if (m_tree)
01218         {
01219           m_tree->del_tree();
01220           delete m_tree;
01221         }
01222 
01223       m_size = 0;
01224 
01225       if (that.m_tree)
01226         m_tree = that.m_tree->duplicate( m_size );
01227       else
01228         m_tree = NULL;
01229     }
01230 
01231   return *this;
01232 } // avl_base::operator=()

template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator== ( const avl_base< K, Comp > &  that  )  const [inline]

Equality.

Parameters:
that AVL top compare to.

Definition at line 1240 of file avl_base.tpp.

References claw::avl_base< K, Comp >::begin(), claw::avl_base< K, Comp >::end(), claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::s_key_less.

01241 {
01242   if (m_size != that.m_size)
01243     return false;
01244   else
01245     return std::equal( begin(), end(), that.begin(), s_key_less );
01246 } // avl_base::operator==()

template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator> ( const avl_base< K, Comp > &  that  )  const [inline]

Greater than operator.

Parameters:
that AVL top compare to.

Definition at line 1277 of file avl_base.tpp.

01278 {
01279   return that < *this;
01280 } // avl_base::operator>()

template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator>= ( const avl_base< K, Comp > &  that  )  const [inline]

Greater or equal operator.

Parameters:
that AVL top compare to.

Definition at line 1299 of file avl_base.tpp.

01300 {
01301   return !( *this < that );
01302 } // avl_base::operator>=()

template<class K, class Comp >
bool claw::avl_base< K, Comp >::recursive_delete ( avl_node_ptr node,
const K &  key 
) [inline, private]

Delete a node. Search is done recursively.

Parameters:
node Tree to which the node is removed.
key Key of the node to remove.
Returns:
true if the balance of the node has changed.
Precondition:
node != NULL
Postcondition:
(exists(this, key) == 0)

Definition at line 1832 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::new_balance(), claw::avl_base< K, Comp >::recursive_delete_node(), claw::binary_node< U >::right, and claw::avl_base< K, Comp >::s_key_less.

Referenced by claw::avl_base< K, Comp >::erase().

01833 {
01834   bool result = false;
01835 
01836   if ( node != NULL )
01837     {
01838       // try to find the key in the left subtree
01839       if ( s_key_less(key, node->key) ) 
01840         {
01841           if ( recursive_delete( node->left, key ) )
01842             result = new_balance( node, -1 );
01843         }
01844       // try to find the key in the right subtree
01845       else if ( s_key_less(node->key, key) ) 
01846         {
01847           if ( recursive_delete( node->right, key ) )
01848             result = new_balance( node, 1 ); 
01849         }
01850       else // we got it !
01851         {
01852           --m_size;
01853           result = recursive_delete_node( node );
01854         }
01855     }
01856 
01857   return result;
01858 } // recursive_delete()

template<class K , class Comp >
int claw::avl_base< K, Comp >::recursive_delete_max ( avl_node_ptr root,
avl_node_ptr  node 
) [inline, private]

Replace a node key and data by the one of the node with the maximum key in tree.

Parameters:
root Root of the tree in which find new values.
node Node Wich gets values founded
Returns:
true if the balance of the tree from root has changed.
Precondition:
node != NULL
root != NULL
root is an AVL
Postcondition:
(root tree is an AVL) && (find(root, max(old root)) == 0)

Definition at line 1976 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::clear(), claw::avl_base< K, Comp >::avl_node::father, claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::recursive_delete_node().

01977 {
01978   assert(node!=NULL);
01979   assert(root!=NULL);
01980 
01981   if ( root->right == NULL ) // We have the maximum
01982     {
01983       // node have only a left subtree if any.
01984       // This subtree has one node, at most.
01985       avl_node_ptr left_subtree;
01986 
01987       node->key = root->key;
01988       left_subtree = root->left;
01989 
01990       if (left_subtree)
01991         left_subtree->father = root->father;
01992 
01993       root->clear();
01994       delete root;
01995                   
01996       // rise the left subtree
01997       root = left_subtree;
01998 
01999       // depth have changed
02000       return true;
02001     }
02002   else // try to find the max in the right subtree
02003     if ( recursive_delete_max( root->right, node ) )
02004       {
02005         // depth of the subtree changed (ie. decreased)
02006         // so root's tree lean to the left
02007         ++(root->balance);
02008 
02009         if (root->balance == 2) // tree is leaning too much
02010           {
02011             // old balance was 1
02012             adjust_balance_left( root );
02013             return root->balance == 0; // Say if balance is changed
02014           }
02015         else 
02016           // if balance is 0, it means that old root leant to the left
02017           // and so his depth changed.
02018           // The other value for balance is 1, in this case
02019           // depth didn't change. See recursive_delete_node code comments.
02020           return root->balance == 0;
02021       }
02022     else // depth of the subtree didn't change
02023       return false;
02024 } // recursive_delete_max()

template<class K , class Comp >
bool claw::avl_base< K, Comp >::recursive_delete_node ( avl_node_ptr node  )  [inline, private]

Remove the root of an AVL (exchange with the descendant immediatly lower).

Parameters:
node Node to remove.
Returns:
true if the balance of the subtree has changed.
Precondition:
node != NULL
Postcondition:
node tree is an AVL

Definition at line 1907 of file avl_base.tpp.

References claw::avl_base< K, Comp >::adjust_balance_right(), claw::avl_base< K, Comp >::avl_node::balance, claw::binary_node< U >::clear(), claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, claw::avl_base< K, Comp >::recursive_delete_max(), and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::recursive_delete().

01908 {
01909   assert( node != NULL );
01910 
01911   if ( node->left == NULL) // this node doesn't have a lower descendant
01912     {
01913       // Get right subtree of current node
01914       avl_node_ptr right_subtree = node->right; 
01915 
01916       if (right_subtree)
01917         right_subtree->father = node->father;
01918 
01919       // Free memory pointed by the current node
01920       node->clear();
01921       delete node;
01922 
01923       // then rise the old right subtree
01924       node = right_subtree;
01925 
01926       return true;
01927     }
01928   else // this node has a lower descendant, let's get it
01929     if ( recursive_delete_max( node->left, node ) )
01930       {
01931         // left subtree depth has decreased
01932         // so reajust balance (rem. balance is not changed by delete_max)
01933         --(node->balance);
01934 
01935         if ( node->balance == -2 )
01936           {
01937             // old balance was -1
01938             adjust_balance_right(node);
01939             return node->balance == 0; // tell if depth has changed
01940           }
01941         else if ( node->balance == 0 ) 
01942           // node had at least one subtree and old balance - 1 == 0
01943           // so old balance = 1
01944           return true;
01945         else // node's balance is -1
01946           // As node's balance is (old balance - 1), node's balance must be -1
01947           // (otherwise old balance is 2, that's impossible)
01948           // So old balance is 0.
01949           // Moreover old node have at least a left subtree. It means that 
01950           // old node had 2 subtrees and their depths were equals.
01951           // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1
01952           // We deleted a node in left subtree and so right subtree is
01953           // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1 
01954           // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node)
01955           // => Node depth is unchanged.
01956           return false;
01957       }
01958     else // depth is unchanged
01959       return false;
01960 } // recursive_delete_node()

template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_left ( avl_node_ptr node  )  [inline, private]

Node left rotation.

Parameters:
node Node to rotate.
Precondition:
(node != NULL) && node->right != NULL
node->balance in [-2,-1] and node->right->balance in [-2,1]
(node->right->balance == -2) ==> (node->balance == -2)

Definition at line 1545 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::adjust_balance_right(), claw::avl_base< K, Comp >::rotate_left_right(), and claw::avl_base< K, Comp >::rotate_right_left().

01546 {
01547   avl_node_ptr p;
01548   char old_node_balance;
01549   char old_subtree_balance;
01550 
01551   assert( node != NULL );
01552   assert( node->right != NULL );
01553   assert( (-2 <= node->balance) && (node->balance <= -1) ) ;
01554   assert( (-2 <= node->right->balance) && (node->right->balance <= 1) );
01555   assert( (node->right->balance != -2) || (node->balance == -2) );
01556 
01557   old_node_balance = node->balance;
01558   old_subtree_balance = node->right->balance;
01559 
01560   // rotate nodes
01561   p = node->right;
01562   p->father = node->father;
01563 
01564   node->right = p->left;
01565           
01566   if (p->left)
01567     p->left->father = node;
01568 
01569   p->left = node;
01570   node->father = p;
01571 
01572   node = p;
01573 
01574   // adjust balance
01575   switch(old_subtree_balance)
01576     {
01577     case  -2 :
01578       // old_node_balance is -2 too.
01579       node->balance = 0;
01580       node->left->balance = 1;
01581       break;
01582     case -1 : 
01583       node->balance = old_node_balance + 2;
01584       node->left->balance = old_node_balance + 2;
01585       break;
01586     case  0 : 
01587       node->balance = 1;
01588       node->left->balance = old_node_balance + 1;
01589       break;
01590     case  1 : 
01591       node->balance = 2;
01592       node->left->balance = old_node_balance + 1;
01593       break;
01594     }
01595 } // rotate_left()

template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_left_right ( avl_node_ptr node  )  [inline, private]

Node left-right rotation.

Parameters:
node Node to rotate.

Definition at line 1603 of file avl_base.tpp.

References claw::binary_node< U >::left, claw::avl_base< K, Comp >::rotate_left(), and claw::avl_base< K, Comp >::rotate_right().

Referenced by claw::avl_base< K, Comp >::adjust_balance_left().

01604 {
01605   assert( node != NULL );
01606 
01607   rotate_left( node->left );
01608   rotate_right( node );
01609 } // rotate_left_right()

template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_right ( avl_node_ptr node  )  [inline, private]

Node right rotation.

Parameters:
node Node to rotate.
Precondition:
(node != NULL) && node->left != NULL
node->balance in [1,2] and node->left->balance in [-1,2]
(node->left->balance == 2) ==> (node->balance == 2)

Definition at line 1484 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::father, claw::binary_node< U >::left, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::rotate_left_right(), and claw::avl_base< K, Comp >::rotate_right_left().

01485 {
01486   avl_node_ptr p;
01487   char old_node_balance;
01488   char old_subtree_balance;
01489 
01490   assert( node != NULL );
01491   assert( node->left != NULL );
01492   assert( (1 <= node->balance) && (node->balance <= 2) ) ;
01493   assert( (-1 <= node->left->balance) && (node->left->balance <= 2) );
01494   assert( (node->left->balance != 2) || (node->balance == 2) );
01495 
01496   old_node_balance = node->balance;
01497   old_subtree_balance = node->left->balance;
01498 
01499   // rotate nodes
01500   p = node->left;
01501   p->father = node->father;
01502 
01503   node->left = p->right;
01504 
01505   if (p->right)
01506     p->right->father = node;
01507 
01508   p->right = node;
01509   node->father = p;
01510 
01511   node = p;
01512 
01513   // adjust balance
01514   switch(old_subtree_balance)
01515     {
01516     case -1 : 
01517       node->balance = -2;
01518       node->right->balance = old_node_balance - 1;
01519       break;
01520     case  0 : 
01521       node->balance = -1;
01522       node->right->balance = old_node_balance - 1;
01523       break;
01524     case  1 : 
01525       node->balance = old_node_balance - 2;
01526       node->right->balance = old_node_balance - 2;
01527       break;
01528     case  2 :
01529       // old_node_balance is 2 too.
01530       node->balance = 0;
01531       node->right->balance = - 1;
01532       break;
01533     }
01534 } // rotate_right()

template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_right_left ( avl_node_ptr node  )  [inline, private]

Node right-left rotation.

Parameters:
node Node to rotate.

Definition at line 1617 of file avl_base.tpp.

References claw::binary_node< U >::right, claw::avl_base< K, Comp >::rotate_left(), and claw::avl_base< K, Comp >::rotate_right().

Referenced by claw::avl_base< K, Comp >::adjust_balance_right().

01618 {
01619   assert( node != NULL );
01620 
01621   rotate_right( node->right );
01622   rotate_left( node );
01623 } // rotate_right_left()

template<class K , class Comp >
unsigned int claw::avl_base< K, Comp >::size (  )  const [inline]

Get the size of a tree.

Returns:
The size of the tree.

Definition at line 1018 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_size.

Referenced by claw::avl< K, Comp >::size().

01019 {
01020   return m_size; 
01021 } // avl_base::size()

template<class K, class Comp>
void claw::avl_base< K, Comp >::swap ( avl_base< K, Comp > &  that  )  [inline]

Swap the values with an other tree.

Parameters:
that The other tree.

Definition at line 1310 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_size, and claw::avl_base< K, Comp >::m_tree.

01311 {
01312   std::swap(m_size, that.m_size);
01313   std::swap(m_tree, that.m_tree);
01314 } // avl_base::swap()

template<class K, class Comp >
void claw::avl_base< K, Comp >::update_balance ( avl_node_ptr  node,
const K &  key 
) [inline, private]

Update balance of each node by increasing depth of the substree containing key, from node to the node key.

Parameters:
node Root of the subtree to update.
key Key of the just-added node.
Precondition:
(node != NULL) && ( key is in the tree starting from root node )
Postcondition:
balance is ok for each node from node to key

Definition at line 1635 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance, claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::binary_node< U >::right, and claw::avl_base< K, Comp >::s_key_less.

Referenced by claw::avl_base< K, Comp >::insert_node().

01636 {
01637   assert(node != NULL);
01638   bool done = false;
01639 
01640   while (!done)
01641     if ( s_key_less(key, node->key) )
01642       {
01643         ++node->balance;
01644         node = node->left;
01645       }
01646     else if ( s_key_less(node->key, key) )
01647       {
01648         --node->balance;
01649         node = node->right;
01650       }
01651     else
01652       done = true;
01653 } // update_balance()

template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::upper_bound (  )  const [inline]

Get an iterator on the gratest value of the tree.

Definition at line 1201 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_tree, claw::avl_base< K, Comp >::make_const_iterator(), and claw::avl_base< K, Comp >::avl_node::upper_bound().

01202 {
01203   return make_const_iterator( m_tree->upper_bound() );
01204 } // avl_base::upper_bound()

template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::upper_bound (  )  [inline]

Get an iterator on the gratest value of the tree.

Definition at line 1190 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_tree, claw::avl_base< K, Comp >::make_iterator(), and claw::avl_base< K, Comp >::avl_node::upper_bound().

Referenced by claw::avl< K, Comp >::upper_bound().

01191 {
01192   return make_iterator( m_tree->upper_bound() );
01193 } // avl_base::upper_bound()

template<class K , class Comp >
bool claw::avl_base< K, Comp >::validity_check (  )  const [inline, private]

This method will check orderliness in our trees : balance and order.

Remarks:
For validity check.
Returns:
true if the AVL is valid, false otherwise.

Definition at line 1409 of file avl_base.tpp.

References claw::avl_base< K, Comp >::check_balance(), claw::avl_base< K, Comp >::check_in_bounds(), claw::avl_base< K, Comp >::correct_descendant(), claw::avl_base< K, Comp >::avl_node::father, claw::avl_base< K, Comp >::avl_node::key, claw::binary_node< U >::left, claw::avl_base< K, Comp >::m_tree, and claw::binary_node< U >::right.

Referenced by claw::avl_base< K, Comp >::erase(), and claw::avl_base< K, Comp >::insert().

01410 {
01411   bool valid = true;
01412 
01413   if (m_tree != NULL)
01414     {
01415       avl_node *node_min, *node_max;
01416 
01417       // get lower and higher bounds, hope they are correct
01418       for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left);
01419       for (node_max = m_tree; node_max->right!=NULL; 
01420            node_max = node_max->right);
01421                   
01422       valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
01423       valid = valid 
01424         && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
01425                   
01426       valid = valid && (m_tree->father == NULL) 
01427         && correct_descendant( m_tree->left ) 
01428         && correct_descendant( m_tree->right );
01429                   
01430     }
01431   
01432   return valid && check_balance(m_tree);
01433 } // validity_check()


Member Data Documentation

template<class K, class Comp = std::less<K>>
unsigned int claw::avl_base< K, Comp >::m_size [private]
template<class K, class Comp = std::less<K>>
avl_node_ptr claw::avl_base< K, Comp >::m_tree [private]
template<class K, class Comp = std::less<K>>
claw::avl_base< K, Comp >::key_less claw::avl_base< K, Comp >::s_key_less [inline, static]

The documentation for this class was generated from the following files:

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