CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
Classes | Public Types | Public Member Functions | Static Public Attributes | Private Types | Private Member Functions | Private Attributes

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_node * avl_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_ptr * find_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 57 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 123 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 124 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 206 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 204 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 205 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 203 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 201 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 202 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 200 of file avl_base.hpp.

Constructor & Destructor Documentation

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

AVL constructor.

Postcondition:
empty()

Definition at line 891 of file avl_base.tpp.

  : m_size(0), m_tree(NULL) 
{

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

AVL copy constructor.

Parameters:
thatAVL instance to copy from.

Definition at line 903 of file avl_base.tpp.

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

{
  m_size = 0;

  if (that.m_tree)
    m_tree = that.m_tree->duplicate( m_size );
  else
    m_tree = NULL;
} // avl_base::avl_base() [copy constructor]
template<class K , class Comp >
claw::avl_base< K, Comp >::~avl_base ( )

AVL destructor.

Definition at line 918 of file avl_base.tpp.

{
  if (m_tree)
    {
      m_tree->del_tree();
      delete m_tree;
    }
} // 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) [private]

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

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

Definition at line 1651 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance.

{
  assert(node != NULL);

  if ( node->balance == 2)
    adjust_balance_left(node);
  else if ( node->balance == -2)
    adjust_balance_right(node);
} // adjust_balance()
template<class K , class Comp >
void claw::avl_base< K, Comp >::adjust_balance_left ( avl_node_ptr &  node) [private]

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

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

Definition at line 1670 of file avl_base.tpp.

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

{
  assert(node != NULL);
  assert(node->balance == 2);

  if (node->left->balance > -1)
    rotate_right( node );
  else if ( node->left->balance == -1)
    rotate_left_right(node);
} // adjust_balance_left()
template<class K , class Comp >
void claw::avl_base< K, Comp >::adjust_balance_right ( avl_node_ptr &  node) [private]

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

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

Definition at line 1690 of file avl_base.tpp.

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

{
  assert(node != NULL);
  assert(node->balance == -2);

  if (node->right->balance < 1)
    rotate_left( node );
  else if ( node->right->balance == 1)
    rotate_right_left(node);
} // adjust_balance_right()
template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::begin ( )

Get an iterator on the nodes of the tree.

Definition at line 1027 of file avl_base.tpp.

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

{
  if (m_tree == NULL)
    return iterator(NULL, true);
  else
    return lower_bound();
} // avl_base::begin()
template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::begin ( ) const

Get an iterator on the nodes of the tree.

Definition at line 1041 of file avl_base.tpp.

{
  if (m_tree == NULL)
    return const_iterator(NULL, true);
  else
    return lower_bound();
} // avl_base::begin()
template<class K , class Comp >
bool claw::avl_base< K, Comp >::check_balance ( const avl_node_ptr  node) const [private]

This method will check balance in our trees.

Parameters:
nodeRoot 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 1346 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.

{
  int pl=0, pr=0;

  if (node == NULL)
    return true;
  else
    {
      if (node->left) pl = node->left->depth();
      if (node->right) pr = node->right->depth();

      return (pl-pr>=-1) && (pl-pr<=1) && (pl-pr == node->balance)
        && check_balance(node->left) && check_balance(node->right);
    }
} // 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 [private]

This method will check order in our trees.

Parameters:
nodeRoot of the tree to check.
minLower bound of the valid range for tree's nodes.
maxHigher bound of the valid range for tree's nodes.
Remarks:
For validity check.
Returns:
true if bounds are ok, false otherwise.

Definition at line 1320 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.

{
  if (node == NULL)
    return true;
  else if ( !( s_key_less(node->key, min) || s_key_less(min, node->key) ) )
    return (node->left == NULL) 
      && check_in_bounds( node->right, node->key, max );
  else if ( !( s_key_less(node->key, max) || s_key_less(max, node->key) ) )
    return (node->right == NULL) 
      && check_in_bounds( node->left, min, node->key );
  else
    return s_key_less(node->key, max) && s_key_less(min, node->key) 
      && check_in_bounds( node->left, min, node->key )
      && check_in_bounds( node->right, node->key, max );
} // check_less_than()
template<class K , class Comp >
void claw::avl_base< K, Comp >::clear ( )

Clear a tree.

Postcondition:
empty()

Definition at line 988 of file avl_base.tpp.

{
  if (m_tree != NULL)
    {
      m_tree->del_tree();
      delete m_tree;
                        
      m_tree = NULL;
      m_size = 0;
    }
} // avl_base::clear()
template<class K , class Comp >
bool claw::avl_base< K, Comp >::correct_descendant ( const avl_node_ptr  node) const [private]

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

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

Definition at line 1370 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.

{
  bool valid = true;

  if (node != NULL)
    {
      if (node->father != NULL)
        {
          valid = (node->father->left == node) ^ (node->father->right == node);
          valid = valid && correct_descendant( node->left ) 
            && correct_descendant( node->right );
        }
      else
        valid = false;
    }
          
  return valid;
} // 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 1017 of file avl_base.tpp.

{
  return m_size == 0; 
} // avl_base::empty()
template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::end ( )

Get an iterator after the end of the tree.

Definition at line 1054 of file avl_base.tpp.

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

{
  if (m_tree == NULL)
    return iterator(NULL, true);
  else
    return iterator(m_tree->upper_bound(), true);
} // avl_base::end()
template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::end ( ) const

Get an iterator after the end of the tree.

Definition at line 1068 of file avl_base.tpp.

{
  if (m_tree == NULL)
    return const_iterator(NULL, true);
  else
    return const_iterator(m_tree->upper_bound(), true);
} // avl_base::end()
template<class K, class Comp >
void claw::avl_base< K, Comp >::erase ( const K &  key)

Delete a value in a tree.

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

Definition at line 972 of file avl_base.tpp.

{
  assert( validity_check() );

  if (m_tree != NULL)
    recursive_delete( m_tree, key );

  assert( validity_check() );
} // avl_base::erase()
template<class K, class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find ( const K &  key)

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

Parameters:
keyKey to find.

Definition at line 1083 of file avl_base.tpp.

{
  return make_iterator( m_tree->find(key) );
} // avl_base::find()
template<class K, class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find ( const K &  key) const

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

Parameters:
keyKey to find.

Definition at line 1095 of file avl_base.tpp.

{
  return make_const_iterator( m_tree->find(key) );
} // avl_base::find()
template<class K, class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_greater ( const K &  key)

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

Parameters:
keyKey to find.

Definition at line 1108 of file avl_base.tpp.

{
  return make_iterator( m_tree->find_nearest_greater(key) );
} // avl_base::find_nearest_greater()
template<class K, class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::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.

Parameters:
keyKey to find.

Definition at line 1121 of file avl_base.tpp.

{
  return make_const_iterator( m_tree->find_nearest_greater(key) );
} // 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

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

Parameters:
keyKey to find.

Definition at line 1147 of file avl_base.tpp.

{
  return make_const_iterator( m_tree->find_nearest_lower(key) );
} // 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)

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

Parameters:
keyKey to find.

Definition at line 1134 of file avl_base.tpp.

{
  return make_iterator( m_tree->find_nearest_lower(key) );
} // 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 
) [private]

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

Parameters:
keyKey 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 1769 of file avl_base.tpp.

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

{
  avl_node_ptr* node; // node for search
  bool exists = false;        // if this key already exists

  last_imbalanced = m_tree;
  node = & m_tree;
  node_father = NULL;

  while ( ((*node) != NULL) && !exists )
    {
      if ( (*node)->balance != 0 )
        last_imbalanced = *node;

                  
      // find next node
      if ( s_key_less(key, (*node)->key) )
        {
          node_father = *node;
          node = & (*node)->left;
        }
      else if ( s_key_less((*node)->key, key) )
        {
          node_father = *node;
          node = & (*node)->right;
        }
      else
        exists = true;
    }

  return node;
} // find_node_reference()
template<class K , class Comp >
template<typename Iterator >
void claw::avl_base< K, Comp >::insert ( Iterator  first,
Iterator  last 
)

Add a range of items in the tree.

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

Definition at line 959 of file avl_base.tpp.

{
  for ( ; first!=last; ++first )
    insert( *first );
} // avl_base::insert()
template<class K, class Comp >
void claw::avl_base< K, Comp >::insert ( const K &  key)

Add a value in a tree.

Parameters:
keyNode key.
Postcondition:
exists(key)

Definition at line 934 of file avl_base.tpp.

{
  assert( validity_check() );

  if ( m_tree == NULL )
    {
      m_tree = new avl_node(key);
      m_size = 1;
    }
  else
    insert_node(key);

  assert( validity_check() );
} // avl_base::insert()
template<class K, class Comp >
void claw::avl_base< K, Comp >::insert_node ( const K &  key) [private]

Add a node to the tree.

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

Definition at line 1715 of file avl_base.tpp.

References 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.

{
  avl_node_ptr* new_node;
  avl_node_ptr node_father;
  avl_node_ptr last_imbalanced;
  avl_node_ptr last_imbalanced_father;
          
  assert(m_tree != NULL);
  
  new_node = find_node_reference(key, last_imbalanced, node_father  );

  if (*new_node == NULL) // this key isn't in use. Let's create a new node
    {
      *new_node = new avl_node(key);
      (*new_node)->father = node_father;

      ++m_size;
      last_imbalanced_father = last_imbalanced->father;

      // Update balance of the last imbalanced node
      update_balance( last_imbalanced, key );
      // then adjust it to be in range [-1, 1]
      adjust_balance( last_imbalanced );
                  
      // pointer update after rotation
      if ( last_imbalanced_father == NULL )
        {
          m_tree = last_imbalanced;
          m_tree->father = NULL;
        }
      else if (s_key_less(last_imbalanced->key, last_imbalanced_father->key)) 
        // left child
        last_imbalanced_father->left = last_imbalanced;
      else
        last_imbalanced_father->right = last_imbalanced;
    }
} // insert_node()
template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::lower_bound ( )

Get an iterator on the lowest value of the tree.

Definition at line 1157 of file avl_base.tpp.

{
  return make_iterator( m_tree->lower_bound() );
} // avl_base::lower_bound()
template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::lower_bound ( ) const

Get an iterator on the lowest value of the tree.

Definition at line 1168 of file avl_base.tpp.

{
  return make_const_iterator( m_tree->lower_bound() );
} // 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 [private]

Create an iterator from a pointer to a node.

Parameters:
nodeThe node on which we want the iterator.

Definition at line 1449 of file avl_base.tpp.

{
  if (node != NULL)
    return const_iterator(node, false);
  else
    return end();
} // 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 [private]

Create an iterator from a pointer to a node.

Parameters:
nodeThe node on which we want the iterator.

Definition at line 1434 of file avl_base.tpp.

{
  if (node != NULL)
    return iterator(node, false);
  else
    return end();
} // avl_base::make_iterator()
template<class K , class Comp >
bool claw::avl_base< K, Comp >::new_balance ( avl_node_ptr &  node,
int  imbalance 
) [private]

Adjust balance of a node.

Parameters:
nodeNode to balance.
imbalanceImbalance 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 1859 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::balance.

{
  assert( (imbalance==1) || (imbalance==-1) );
  assert( node != NULL );

  node->balance += imbalance;

  switch(node->balance)
    {
      // balance == 0 so as it was != 0 before deletion
      // balance of the tree had changed
    case 0: return true;
      // balance == 2 so it must be 1 before deletion and node
      // was deleted in the right subtree
      // if after ajusting the balance is equal to 1, it means that
      // our subtree got back his old balance (so it's unchanged).
      // if it's equal to -1, it means that subtree now lean to the
      // otherside. But in those cases, depth didn't changed.
    case 2: adjust_balance_left(node); return node->balance == 0;
      // same thing but symetric
    case -2: adjust_balance_right(node); return node->balance == 0;
    default : return false;
    }
} // new_balance()
template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator!= ( const avl_base< K, Comp > &  that) const

Disequality.

Parameters:
thatAVL top compare to.

Definition at line 1242 of file avl_base.tpp.

{
  return !( *this == that );
} // avl_base::operator!=()
template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator< ( const avl_base< K, Comp > &  that) const

Less than operator.

Parameters:
thatAVL top compare to.

Definition at line 1253 of file avl_base.tpp.

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

{
  return std::lexicographical_compare
    ( begin(), end(), that.begin(), that.end(), s_key_less );
} // avl_base::operator<()
template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator<= ( const avl_base< K, Comp > &  that) const

Less or equal operator.

Parameters:
thatAVL top compare to.

Definition at line 1276 of file avl_base.tpp.

{
  return !( that < *this );
} // 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)

Assignment operator.

Parameters:
thatAVL instance to copy from.

Definition at line 1201 of file avl_base.tpp.

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

{
  if (this != &that)
    {
      if (m_tree)
        {
          m_tree->del_tree();
          delete m_tree;
        }

      m_size = 0;

      if (that.m_tree)
        m_tree = that.m_tree->duplicate( m_size );
      else
        m_tree = NULL;
    }

  return *this;
} // avl_base::operator=()
template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator== ( const avl_base< K, Comp > &  that) const

Equality.

Parameters:
thatAVL top compare to.

Definition at line 1228 of file avl_base.tpp.

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

{
  if (m_size != that.m_size)
    return false;
  else
    return std::equal( begin(), end(), that.begin(), s_key_less );
} // avl_base::operator==()
template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator> ( const avl_base< K, Comp > &  that) const

Greater than operator.

Parameters:
thatAVL top compare to.

Definition at line 1265 of file avl_base.tpp.

{
  return that < *this;
} // avl_base::operator>()
template<class K, class Comp>
bool claw::avl_base< K, Comp >::operator>= ( const avl_base< K, Comp > &  that) const

Greater or equal operator.

Parameters:
thatAVL top compare to.

Definition at line 1287 of file avl_base.tpp.

{
  return !( *this < that );
} // avl_base::operator>=()
template<class K, class Comp >
bool claw::avl_base< K, Comp >::recursive_delete ( avl_node_ptr &  node,
const K &  key 
) [private]

Delete a node. Search is done recursively.

Parameters:
nodeTree to which the node is removed.
keyKey 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 1819 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.

{
  bool result = false;

  if ( node != NULL )
    {
      // try to find the key in the left subtree
      if ( s_key_less(key, node->key) ) 
        {
          if ( recursive_delete( node->left, key ) )
            result = new_balance( node, -1 );
        }
      // try to find the key in the right subtree
      else if ( s_key_less(node->key, key) ) 
        {
          if ( recursive_delete( node->right, key ) )
            result = new_balance( node, 1 ); 
        }
      else // we got it !
        {
          --m_size;
          result = recursive_delete_node( node );
        }
    }

  return result;
} // recursive_delete()
template<class K , class Comp >
int claw::avl_base< K, Comp >::recursive_delete_max ( avl_node_ptr &  root,
avl_node_ptr  node 
) [private]

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

Parameters:
rootRoot of the tree in which find new values.
nodeNode 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 1963 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.

{
  assert(node!=NULL);
  assert(root!=NULL);

  if ( root->right == NULL ) // We have the maximum
    {
      // node have only a left subtree if any.
      // This subtree has one node, at most.
      avl_node_ptr left_subtree;

      node->key = root->key;
      left_subtree = root->left;

      if (left_subtree)
        left_subtree->father = root->father;

      root->clear();
      delete root;
                  
      // rise the left subtree
      root = left_subtree;

      // depth have changed
      return true;
    }
  else // try to find the max in the right subtree
    if ( recursive_delete_max( root->right, node ) )
      {
        // depth of the subtree changed (ie. decreased)
        // so root's tree lean to the left
        ++(root->balance);

        if (root->balance == 2) // tree is leaning too much
          {
            // old balance was 1
            adjust_balance_left( root );
            return root->balance == 0; // Say if balance is changed
          }
        else 
          // if balance is 0, it means that old root leant to the left
          // and so his depth changed.
          // The other value for balance is 1, in this case
          // depth didn't change. See recursive_delete_node code comments.
          return root->balance == 0;
      }
    else // depth of the subtree didn't change
      return false;
} // recursive_delete_max()
template<class K , class Comp >
bool claw::avl_base< K, Comp >::recursive_delete_node ( avl_node_ptr &  node) [private]

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

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

Definition at line 1894 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::binary_node< U >::left, and claw::binary_node< U >::right.

{
  assert( node != NULL );

  if ( node->left == NULL) // this node doesn't have a lower descendant
    {
      // Get right subtree of current node
      avl_node_ptr right_subtree = node->right; 

      if (right_subtree)
        right_subtree->father = node->father;

      // Free memory pointed by the current node
      node->clear();
      delete node;

      // then rise the old right subtree
      node = right_subtree;

      return true;
    }
  else // this node has a lower descendant, let's get it
    if ( recursive_delete_max( node->left, node ) )
      {
        // left subtree depth has decreased
        // so reajust balance (rem. balance is not changed by delete_max)
        --(node->balance);

        if ( node->balance == -2 )
          {
            // old balance was -1
            adjust_balance_right(node);
            return node->balance == 0; // tell if depth has changed
          }
        else if ( node->balance == 0 ) 
          // node had at least one subtree and old balance - 1 == 0
          // so old balance = 1
          return true;
        else // node's balance is -1
          // As node's balance is (old balance - 1), node's balance must be -1
          // (otherwise old balance is 2, that's impossible)
          // So old balance is 0.
          // Moreover old node have at least a left subtree. It means that 
          // old node had 2 subtrees and their depths were equals.
          // It means bstn_depth(old node) == bstn_depth((old node)->right) + 1
          // We deleted a node in left subtree and so right subtree is
          // unchanged. So bstn_depth(node) == bstn_depth(node->right) + 1 
          // == bstn_depth( (old node)->right) ) + 1 == bstn_depth(old node)
          // => Node depth is unchanged.
          return false;
      }
    else // depth is unchanged
      return false;
} // recursive_delete_node()
template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_left ( avl_node_ptr &  node) [private]

Node left rotation.

Parameters:
nodeNode 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 1533 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.

{
  avl_node_ptr p;
  char old_node_balance;
  char old_subtree_balance;

  assert( node != NULL );
  assert( node->right != NULL );
  assert( (-2 <= node->balance) && (node->balance <= -1) ) ;
  assert( (-2 <= node->right->balance) && (node->right->balance <= 1) );
  assert( (node->right->balance != -2) || (node->balance == -2) );

  old_node_balance = node->balance;
  old_subtree_balance = node->right->balance;

  // rotate nodes
  p = node->right;
  p->father = node->father;

  node->right = p->left;
          
  if (p->left)
    p->left->father = node;

  p->left = node;
  node->father = p;

  node = p;

  // adjust balance
  switch(old_subtree_balance)
    {
    case  -2 :
      // old_node_balance is -2 too.
      node->balance = 0;
      node->left->balance = 1;
      break;
    case -1 : 
      node->balance = old_node_balance + 2;
      node->left->balance = old_node_balance + 2;
      break;
    case  0 : 
      node->balance = 1;
      node->left->balance = old_node_balance + 1;
      break;
    case  1 : 
      node->balance = 2;
      node->left->balance = old_node_balance + 1;
      break;
    }
} // rotate_left()
template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_left_right ( avl_node_ptr &  node) [private]

Node left-right rotation.

Parameters:
nodeNode to rotate.

Definition at line 1591 of file avl_base.tpp.

References claw::binary_node< U >::left.

{
  assert( node != NULL );

  rotate_left( node->left );
  rotate_right( node );
} // rotate_left_right()
template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_right ( avl_node_ptr &  node) [private]

Node right rotation.

Parameters:
nodeNode 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 1472 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.

{
  avl_node_ptr p;
  char old_node_balance;
  char old_subtree_balance;

  assert( node != NULL );
  assert( node->left != NULL );
  assert( (1 <= node->balance) && (node->balance <= 2) ) ;
  assert( (-1 <= node->left->balance) && (node->left->balance <= 2) );
  assert( (node->left->balance != 2) || (node->balance == 2) );

  old_node_balance = node->balance;
  old_subtree_balance = node->left->balance;

  // rotate nodes
  p = node->left;
  p->father = node->father;

  node->left = p->right;

  if (p->right)
    p->right->father = node;

  p->right = node;
  node->father = p;

  node = p;

  // adjust balance
  switch(old_subtree_balance)
    {
    case -1 : 
      node->balance = -2;
      node->right->balance = old_node_balance - 1;
      break;
    case  0 : 
      node->balance = -1;
      node->right->balance = old_node_balance - 1;
      break;
    case  1 : 
      node->balance = old_node_balance - 2;
      node->right->balance = old_node_balance - 2;
      break;
    case  2 :
      // old_node_balance is 2 too.
      node->balance = 0;
      node->right->balance = - 1;
      break;
    }
} // rotate_right()
template<class K , class Comp >
void claw::avl_base< K, Comp >::rotate_right_left ( avl_node_ptr &  node) [private]

Node right-left rotation.

Parameters:
nodeNode to rotate.

Definition at line 1605 of file avl_base.tpp.

References claw::binary_node< U >::right.

{
  assert( node != NULL );

  rotate_right( node->right );
  rotate_left( node );
} // 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 1006 of file avl_base.tpp.

{
  return m_size; 
} // avl_base::size()
template<class K, class Comp>
void claw::avl_base< K, Comp >::swap ( avl_base< K, Comp > &  that)

Swap the values with an other tree.

Parameters:
thatThe other tree.

Definition at line 1298 of file avl_base.tpp.

References claw::avl_base< K, Comp >::m_size, claw::avl_base< K, Comp >::m_tree, and std::swap().

{
  std::swap(m_size, that.m_size);
  std::swap(m_tree, that.m_tree);
} // avl_base::swap()
template<class K, class Comp >
void claw::avl_base< K, Comp >::update_balance ( avl_node_ptr  node,
const K &  key 
) [private]

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

Parameters:
nodeRoot of the subtree to update.
keyKey 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 1623 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, and claw::binary_node< U >::right.

{
  assert(node != NULL);
  bool done = false;

  while (!done)
    if ( s_key_less(key, node->key) )
      {
        ++node->balance;
        node = node->left;
      }
    else if ( s_key_less(node->key, key) )
      {
        --node->balance;
        node = node->right;
      }
    else
      done = true;
} // update_balance()
template<class K , class Comp >
claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::upper_bound ( )

Get an iterator on the gratest value of the tree.

Definition at line 1178 of file avl_base.tpp.

{
  return make_iterator( m_tree->upper_bound() );
} // avl_base::upper_bound()
template<class K , class Comp >
claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::upper_bound ( ) const

Get an iterator on the gratest value of the tree.

Definition at line 1189 of file avl_base.tpp.

{
  return make_const_iterator( m_tree->upper_bound() );
} // avl_base::upper_bound()
template<class K , class Comp >
bool claw::avl_base< K, Comp >::validity_check ( ) const [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 1397 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.

{
  bool valid = true;

  if (m_tree != NULL)
    {
      avl_node *node_min, *node_max;

      // get lower and higher bounds, hope they are correct
      for (node_min = m_tree; node_min->left!=NULL; node_min = node_min->left);
      for (node_max = m_tree; node_max->right!=NULL; 
           node_max = node_max->right);
                  
      valid = check_in_bounds(m_tree->left, node_min->key, m_tree->key);
      valid = valid 
        && check_in_bounds(m_tree->right, m_tree->key, node_max->key);
                  
      valid = valid && (m_tree->father == NULL) 
        && correct_descendant( m_tree->left ) 
        && correct_descendant( m_tree->right );
                  
    }
  
  return valid && check_balance(m_tree);
} // validity_check()

Member Data Documentation

template<class K, class Comp = std::less<K>>
unsigned int claw::avl_base< K, Comp >::m_size [private]

Nodes count.

Definition at line 311 of file avl_base.hpp.

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

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

Nodes.

Definition at line 314 of file avl_base.hpp.

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

template<class K, class Comp = std::less<K>>
claw::avl_base< K, Comp >::key_less claw::avl_base< K, Comp >::s_key_less [static]

Function object used to compare keys.

Definition at line 307 of file avl_base.hpp.

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

The documentation for this class was generated from the following files:
Generated on Wed Apr 27 2011 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.7.3