avl_base.tpp

/*
  CLAW - a C++ Library Absolutely Wonderful

  CLAW is a free library without any particular aim but being useful to 
  anyone.

  Copyright (C) 2005-2011 Julien Jorge

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

  contact: julien.jorge@gamned.org
*/
#include <cassert>

//**************************** avl_base::avl_node ******************************

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K, Comp>::avl_node::avl_node( const K& k ) 
  : super(), key(k), balance(0), father(NULL) 
{
  assert(!super::left);
  assert(!super::right);
} // avl_node::avl_node() [constructeur]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K, Comp>::avl_node::~avl_node() 
{

} // avl_node::~avl_node() [destructeur]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K, Comp>::avl_node*
claw::avl_base<K, Comp>::avl_node::duplicate( unsigned int& count ) const
{
  avl_node* node_copy = new avl_node(key);
  ++count;
  node_copy->balance = balance;
  node_copy->father = NULL;

  if (super::left) 
    {
      node_copy->left = super::left->duplicate(count);
      node_copy->left->father = node_copy;
    }
  else
    node_copy->left = NULL;
  
  if (super::right) 
    {
      node_copy->right = super::right->duplicate(count);
      node_copy->right->father = node_copy;
    }
  else
    node_copy->right = NULL;

  return node_copy;
} // avl_node::duplicate()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K, Comp>::avl_node::del_tree()
{
  if (super::left) 
    {
      delete super::left;
      super::left = NULL;
    }
  if (super::right)
    {
      delete super::right;
      super::right = NULL;
    }
  assert( !super::left );
  assert( !super::right );
} // avl_node::del_tree

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
unsigned int claw::avl_base<K, Comp>::avl_node::depth() const
{
  unsigned int pl=0, pr=0;

  if (super::left)  pl = super::left->depth();
  if (super::right) pr = super::right->depth();

  if (pl > pr)
    return 1 + pl;
  else
    return 1 + pr;
} // avl_node::depth()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::find( const K& key )
{
  bool ok = false;
  avl_node* node = this;

  while (node && !ok)
    if ( avl_base<K, Comp>::s_key_less(key, node->key) )
      node = node->left;
    else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
      node = node->right;
    else
      ok = true;

  return node;
} // avl_base::avl_node::find()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::find( const K& key ) const
{
  bool ok = false;
  const avl_node* node = this;

  while (node && !ok)
    if ( avl_base<K, Comp>::s_key_less(key, node->key) )
      node = node->left;
    else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
      node = node->right;
    else
      ok = true;

  return node;
} // avl_base::avl_node::find()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key )
{
  bool ok = false;
  avl_node* node = this;
  avl_node* prev_node = NULL;

  while (node && !ok)
    if ( avl_base<K, Comp>::s_key_less(key, node->key) )
      {
        prev_node = node;
        node = node->left;
      }
    else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
      {
        prev_node = node;
        node = node->right;
      }
    else
      ok = true;

  if (ok)
    return node->next();
  else if (prev_node)
    {
      if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
        return prev_node->next();
      else
        return prev_node;
    }
  else
    return node;
} // avl_base::find_nearest_greater()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::find_nearest_greater( const K& key ) const
{
  bool ok = false;
  const avl_node* node = this;
  const avl_node* prev_node = NULL;

  while (node && !ok)
    if ( avl_base<K, Comp>::s_key_less(key, node->key) )
      {
        prev_node = node;
        node = node->left;
      }
    else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
      {
        prev_node = node;
        node = node->right;
      }
    else
      ok = true;

  if (ok)
    return node->next();
  else if (prev_node)
    {
      if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
        return prev_node->next();
      else
        return prev_node;
    }
  else
    return node;
} // avl_base::find_nearest_greater()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key )
{
  bool ok = false;
  avl_node* node = this;
  avl_node* prev_node = NULL;

  while (node && !ok)
    if ( s_key_less(key, node->key) )
      {
        prev_node = node;
        node = node->left;
      }
    else if ( s_key_less(node->key, key) )
      {
        prev_node = node;
        node = node->right;
      }
    else
      ok = true;

  if (ok)
    return node->prev();
  else if (prev_node)
    {
      if ( s_key_less(key, prev_node->key) )
        return prev_node;
      else
        return prev_node->prev();
    }
  else
    return node;
} // avl_base::find_nearest_lower()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::find_nearest_lower( const K& key ) const
{
  bool ok = false;
  const avl_node* node = this;
  const avl_node* prev_node = NULL;

  while (node && !ok)
    if ( s_key_less(key, node->key) )
      {
        prev_node = node;
        node = node->left;
      }
    else if ( s_key_less(node->key, key) )
      {
        prev_node = node;
        node = node->right;
      }
    else
      ok = true;

  if (ok)
    return node->prev();
  else if (prev_node)
    {
      if ( s_key_less(key, prev_node->key) )
        return prev_node;
      else
        return prev_node->prev();
    }
  else
    return node;
} // avl_base::find_nearest_lower()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::lower_bound()
{
  avl_node* node = this;

  if (node)
    while (node->left)
      node = node->left;

  return node;
} // avl_base::lower_bound()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::lower_bound() const
{
  const avl_node* node = this;

  if (node)
    while (node->left)
      node = node->left;

  return node;
} // avl_base::lower_bound()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::upper_bound()
{
  avl_node* node = this;

  if (node)
    while (node->right)
      node = node->right;

  return node;
} // avl_base::upper_bound()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::upper_bound() const
{
  const avl_node* node = this;

  if (node)
    while (node->right)
      node = node->right;

  return node;
} // avl_base::upper_bound()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::next()
{
  avl_node* result = this;

  // node have a right subtree : go to the min
  if (result->right != NULL)
    {
      result = result->right;
  
      while (result->left != NULL)
        result = result->left;
    }
  else
    {
      bool done = false;
      avl_node* previous_node = this;

      // get parent node
      while (result->father && !done)
        {
          if (result->father->left == result)
            done = true;

          result = result->father;
        }

      // came back from the max node to the root
      if (!done)
        result = previous_node;
    }
                        
  return result;
} // avl_iterator::avl_node::next()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::next() const
{
  const avl_node* result = this;

  // node have a right subtree : go to the min
  if (result->right != NULL)
    {
      result = result->right;
  
      while (result->left != NULL)
        result = result->left;
    }
  else
    {
      bool done = false;
      const avl_node* previous_node = this;

      // get parent node
      while (result->father && !done)
        {
          if (result->father->left == result)
            done = true;

          result = result->father;
        }

      // came back from the max node to the root
      if (!done)
        result = previous_node;
    }
                        
  return result;
} // avl_iterator::avl_node::next()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::prev()
{
  avl_node* result = this;

  // node have a left subtree : go to the max
  if (result->left != NULL)
    {
      result = result->left;
                
      while (result->right != NULL)
        result = result->right;
    }
  else
    {
      bool done = false;

      // get parent node
      while (result->father && !done)
        {
          if (result->father->right == result)
            done = true;

          result = result->father;
        }
    }
  
  return result;
} // avl_iterator::avl_node::prev()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
const typename claw::avl_base<K,Comp>::avl_node*
claw::avl_base<K,Comp>::avl_node::prev() const
{
  const avl_node* result = this;

  // node have a left subtree : go to the max
  if (result->left != NULL)
    {
      result = result->left;
                
      while (result->right != NULL)
        result = result->right;
    }
  else
    {
      bool done = false;

      // get parent node
      while (result->father && !done)
        {
          if (result->father->right == result)
            done = true;

          result = result->father;
        }
    }
  
  return result;
} // avl_iterator::avl_node::prev()





/*=================================== private ===============================*/



/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K, Comp>::avl_node::avl_node( const avl_node& that )
  : super(that), key(that.key), balance(that.balance), father(NULL) 
{
  assert(0);
} // avl_node::depth()





//**************************** avl_base::avl_iterator **************************



/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K,Comp>::avl_iterator::avl_iterator()
  : m_current(NULL), m_is_final(true)
{

} // avl_iterator::avl_iterator() [constructeur]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K,Comp>::avl_iterator::avl_iterator
( avl_node_ptr node, bool final )
  : m_current(node), m_is_final(final)
{

} // avl_iterator::avl_iterator() [constructeur with node]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_iterator&
claw::avl_base<K,Comp>::avl_iterator::operator++()
{
  assert(!m_is_final);
  assert(m_current);

  avl_node* p = m_current->next();

  if ( m_current == p )
    m_is_final = true;
  else
    m_current = p;

  return *this;
} // avl_iterator::operator++() [preincrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_iterator
claw::avl_base<K,Comp>::avl_iterator::operator++(int)
{
  avl_iterator it = *this;
  ++(*this);
  return it;
} // avl_iterator::operator++ [postincrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_iterator&
claw::avl_base<K,Comp>::avl_iterator::operator--()
{
  assert(m_current);

  if (m_is_final)
    m_is_final = !m_is_final;
  else
    m_current = m_current->prev();

  assert(m_current != NULL);
  
  return *this;
} // avl_iterator::operator--() [predecrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_iterator
claw::avl_base<K,Comp>::avl_iterator::operator--(int)
{
  avl_iterator it = *this;
  --(*this);
  return it;
} // avl_iterator::operator-- [postdecrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_iterator::reference
claw::avl_base<K,Comp>::avl_iterator::operator*() const 
{
  return m_current->key; 
} // avl_iterator::operator*() [dereference]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_iterator::pointer
claw::avl_base<K,Comp>::avl_iterator::operator->() const 
{
  return &m_current->key; 
} // avl_iterator::operator->()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::avl_base<K,Comp>::avl_iterator::operator==(const avl_iterator& it) const 
{
  return (m_current == it.m_current) && (m_is_final == it.m_is_final); 
} // avl_iterator::operator==()

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





//************************* avl_base::avl_const_iterator ***********************



/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator()
  : m_current(NULL), m_is_final(true)
{

} // avl_const_iterator::avl_const_iterator() [constructeur]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K,Comp>::avl_const_iterator::avl_const_iterator
( const_avl_node_ptr node, bool final )
  : m_current(node), m_is_final(final)
{

} // avl_const_iterator::avl_const_iterator() [constructeur with node]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_const_iterator&
claw::avl_base<K,Comp>::avl_const_iterator::operator++()
{
  assert(!m_is_final);
  assert(m_current);

  const_avl_node_ptr p = m_current->next();

  if ( m_current == p )
    m_is_final = true;
  else
    m_current = p;

  return *this;
} // avl_const_iterator::operator++() [preincrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_const_iterator
claw::avl_base<K,Comp>::avl_const_iterator::operator++(int)
{
  avl_const_iterator it = *this;
  ++(*this);
  return it;
} // avl_const_iterator::operator++ [postincrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_const_iterator&
claw::avl_base<K,Comp>::avl_const_iterator::operator--()
{
  assert(m_current);

  if (m_is_final)
    m_is_final = !m_is_final;
  else
    m_current = m_current->prev();

  assert(m_current != NULL);
  
  return *this;
} // avl_const_iterator::operator--() [predecrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_const_iterator
claw::avl_base<K,Comp>::avl_const_iterator::operator--(int)
{
  avl_const_iterator it = *this;
  --(*this);
  return it;
} // avl_const_iterator::operator-- [postdecrement]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_const_iterator::reference
claw::avl_base<K,Comp>::avl_const_iterator::operator*() const 
{
  return m_current->key; 
} // avl_const_iterator::operator*() [dereference]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::avl_const_iterator::pointer
claw::avl_base<K,Comp>::avl_const_iterator::operator->() const 
{
  return &m_current->key; 
} // avl_const_iterator::operator->()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool claw::avl_base<K,Comp>::avl_const_iterator::operator==
(const avl_const_iterator& it) const 
{
  return (m_current == it.m_current) && (m_is_final == it.m_is_final); 
} // avl_const_iterator::operator==()

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





//******************************* avl_base (main) ******************************


/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::key_less claw::avl_base<K,Comp>::s_key_less;

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K,Comp>::avl_base()
  : 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 )
{
  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()
{
  if (m_tree)
    {
      m_tree->del_tree();
      delete m_tree;
    }
} // avl_base::~avl_base() [destructeur]

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K,Comp>::insert( const K& key )
{
  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>
template<typename Iterator>
void claw::avl_base<K,Comp>::insert( Iterator first, Iterator last )
{
  for ( ; first!=last; ++first )
    insert( *first );
} // avl_base::insert()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K,Comp>::erase( const K& key )
{
  assert( validity_check() );

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

  assert( validity_check() );
} // avl_base::erase()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K,Comp>::clear()
{
  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>
inline unsigned int claw::avl_base<K,Comp>::size() const
{
  return m_size; 
} // avl_base::size()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
inline bool claw::avl_base<K,Comp>::empty() const
{
  return m_size == 0; 
} // avl_base::empty()

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

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

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

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::const_iterator
claw::avl_base<K,Comp>::end() const
{
  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>
typename claw::avl_base<K,Comp>::iterator
claw::avl_base<K,Comp>::find( const K& key )
{
  return make_iterator( m_tree->find(key) );
} // avl_base::find()

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

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

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

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::iterator
claw::avl_base<K,Comp>::find_nearest_lower( const K& key )
{
  return make_iterator( m_tree->find_nearest_lower(key) );
} // avl_base::find_nearest_lower()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::const_iterator
claw::avl_base<K,Comp>::find_nearest_lower( const K& key ) const
{
  return make_const_iterator( m_tree->find_nearest_lower(key) );
} // avl_base::find_nearest_lower()

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

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

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

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

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::avl_base<K, Comp>&
claw::avl_base<K, Comp>::operator=( const avl_base<K, Comp>& that )
{
  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
{
  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
{
  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
{
  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
{
  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
{
  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
{
  return !( *this < that );
} // avl_base::operator>=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K, Comp>::swap( avl_base<K, Comp>& that )
{
  std::swap(m_size, that.m_size);
  std::swap(m_tree, that.m_tree);
} // avl_base::swap()

/*================================= private =================================*/

//-----------------------------------------------------------------------------
// We need some methods to check the validity of our trees

/*----------------------------------------------------------------------------*/
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
{
  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>
bool claw::avl_base<K,Comp>::check_balance( const avl_node_ptr node ) const
{
  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>::correct_descendant( const avl_node_ptr node ) const
{
  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>::validity_check() const
{
  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()





/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::iterator
claw::avl_base<K,Comp>::make_iterator( avl_node_ptr node ) const
{
  if (node != NULL)
    return iterator(node, false);
  else
    return end();
} // avl_base::make_iterator()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
typename claw::avl_base<K,Comp>::const_iterator
claw::avl_base<K,Comp>::make_const_iterator( const_avl_node_ptr node ) const
{
  if (node != NULL)
    return const_iterator(node, false);
  else
    return end();
} // avl_base::make_const_iterator()




//-----------------------------------------------------------------------------
// Tree management methods

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K,Comp>::rotate_right( avl_node_ptr& node )
{
  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_left( avl_node_ptr& node )
{
  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 )
{
  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_left( avl_node_ptr& node )
{
  assert( node != NULL );

  rotate_right( node->right );
  rotate_left( node );
} // rotate_right_left()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K,Comp>::update_balance( avl_node_ptr node, const K& key )
{
  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>
void claw::avl_base<K,Comp>::adjust_balance( avl_node_ptr& node )
{
  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 )
{
  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 )
{
  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()


/*----------------------------------------------------------------------------*/
//    Methods for insertion
/*----------------------------------------------------------------------------*/


/*----------------------------------------------------------------------------*/
template<class K, class Comp>
void claw::avl_base<K,Comp>::insert_node( const K& key )
{
  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>
typename 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)
{
  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()


/*----------------------------------------------------------------------------*/
//    Methods for deletion
/*----------------------------------------------------------------------------*/


/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::avl_base<K,Comp>::recursive_delete( avl_node_ptr& node, const K& key )
{
  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>
bool claw::avl_base<K,Comp>::new_balance( avl_node_ptr& node, int imbalance )
{
  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>::recursive_delete_node( avl_node_ptr& node )
{
  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>
int claw::avl_base<K,Comp>::recursive_delete_max
( avl_node_ptr& root, avl_node_ptr node )
{
  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()