Public Member Functions | Public Attributes | Private Types | Private Member Functions

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

Node of a binary search tree (AVL). More...

Inheritance diagram for claw::avl_base< K, Comp >::avl_node:
claw::binary_node< claw::avl_base< K, Comp >::avl_node >

List of all members.

Public Member Functions

 avl_node (const K &k)
 AVL's node constructor.
 ~avl_node ()
 AVL's node destructor.
avl_node * duplicate (unsigned int &count) const
 Duplicate node and his subtrees.
void del_tree ()
 Delete current node and his subtrees.
unsigned int depth () const
 Get the depth of a tree.
avl_node * find (const K &k)
 Get a pointer on the node of the tree with a specified key.
const avl_node * find (const K &k) const
 Get a pointer on the node of the tree with a specified key.
avl_node * 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 avl_node * 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.
avl_node * 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 avl_node * 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.
avl_node * lower_bound ()
 Get a pointer on the lowest value of the tree.
const avl_node * lower_bound () const
 Get a pointer on the lowest value of the tree.
avl_node * upper_bound ()
 Get a pointer on the greatest value of the tree.
const avl_node * upper_bound () const
 Get a pointer on the greatest value of the tree.
avl_node * prev ()
 Get the node immediately before this.
const avl_node * prev () const
 Get the node immediately before this.
avl_node * next ()
 Get the node immediately greater than this.
const avl_node * next () const
 Get the node immediately greater than this.

Public Attributes

K key
 Node key.
char balance
 Balance of the node is -1, 0 or 1. Equals to the difference between left child depth and right child depth.
avl_node * father
 Father of the node. Null if this node is root.

Private Types

typedef binary_node< typename
claw::avl_base< K, Comp >
::avl_node > 		super
 The type of the parent class.

Private Member Functions

 avl_node (const avl_node &that)
 Copy constructor.

Detailed Description

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

Node of a binary search tree (AVL).

Definition at line 66 of file avl_base.hpp.

Member Typedef Documentation

template<class K, class Comp = std::less<K>>
typedef binary_node< typename claw::avl_base<K,Comp>::avl_node > claw::avl_base< K, Comp >::avl_node::super [private]

The type of the parent class.

Definition at line 71 of file avl_base.hpp.

Constructor & Destructor Documentation

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

AVL's node constructor.

Parameters:
k Value of the node

Definition at line 40 of file avl_base.tpp.

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

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

  : 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's node destructor.

Definition at line 52 of file avl_base.tpp.

{

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

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

Copy constructor.

Parameters:
that Node to copy from.
Remarks:
Shouldn't be use.

Definition at line 588 of file avl_base.tpp.

  : super(that), key(that.key), balance(that.balance), father(NULL) 
{
  assert(0);
} // avl_node::depth()

Member Function Documentation

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

Delete current node and his subtrees.

Postcondition:
left == NULL && right == NULL

Definition at line 97 of file avl_base.tpp.

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

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

{
  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

Get the depth of a tree.

Remarks:
For validity check.
Returns:
1 + max( this->left->depth(), this->right->depth() )

Definition at line 120 of file avl_base.tpp.

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

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

{
  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 >
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::duplicate ( unsigned int &  count  )  const

Duplicate node and his subtrees.

Parameters:
count (out) Count of duplicated nodes.
Remarks:
Count isn't initialized. You should call duplicate with count = 0.

Definition at line 65 of file avl_base.tpp.

References claw::avl_base< K, Comp >::avl_node::avl_node(), claw::avl_base< K, Comp >::avl_node::balance, 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 >::avl_base(), and claw::avl_base< K, Comp >::operator=().

{
  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 >
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find ( const K &  key  ) 

Get a pointer on the node of the tree with a specified key.

Parameters:
key Key to find.

Definition at line 140 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 >::find().

{
  bool ok;
  avl_node* node = this;

  ok = false;

  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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::find ( const K &  key  )  const

Get a pointer on the node of the tree with a specified key.

Parameters:
key Key to find.

Definition at line 165 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 ok;
  const avl_node* node = this;

  ok = false;

  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 >
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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:
key Key to find.

Definition at line 191 of file avl_base.tpp.

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

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

{
  bool ok;
  avl_node* node = this;
  avl_node* prev_node = NULL;

  ok = false;

  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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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:
key Key to find.

Definition at line 234 of file avl_base.tpp.

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

{
  bool ok;
  const avl_node* node = this;
  const avl_node* prev_node = NULL;

  ok = false;

  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 >
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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:
key Key to find.

Definition at line 277 of file avl_base.tpp.

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

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

{
  bool ok;
  avl_node* node = this;
  avl_node* prev_node = NULL;

  ok = false;

  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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::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:
key Key to find.

Definition at line 320 of file avl_base.tpp.

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

{
  bool ok;
  const avl_node* node = this;
  const avl_node* prev_node = NULL;

  ok = false;

  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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::lower_bound (  )  const

Get a pointer on the lowest value of the tree.

Definition at line 378 of file avl_base.tpp.

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

{
  const avl_node* node = this;

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

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

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

Get a pointer on the lowest value of the tree.

Definition at line 361 of file avl_base.tpp.

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

Referenced by claw::avl_base< K, Comp >::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 >
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next (  ) 

Get the node immediately greater than this.

Definition at line 429 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 >::avl_node::find_nearest_greater(), and claw::avl_base< K, Comp >::avl_iterator::operator++().

{
  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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next (  )  const

Get the node immediately greater than this.

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

{
  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 >
claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::prev (  ) 

Get the node immediately before this.

Definition at line 509 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 >::avl_node::find_nearest_lower(), and claw::avl_base< K, Comp >::avl_iterator::operator--().

{
  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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::prev (  )  const

Get the node immediately before this.

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

{
  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()

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

Get a pointer on the greatest value of the tree.

Definition at line 395 of file avl_base.tpp.

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

Referenced by claw::avl_base< K, Comp >::end(), and claw::avl_base< K, Comp >::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 claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::upper_bound (  )  const

Get a pointer on the greatest value of the tree.

Definition at line 412 of file avl_base.tpp.

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

{
  const avl_node* node = this;

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

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

Member Data Documentation

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

Balance of the node is -1, 0 or 1. Equals to the difference between left child depth and right child depth.

Definition at line 115 of file avl_base.hpp.

Referenced by claw::avl_base< K, Comp >::adjust_balance(), claw::avl_base< K, Comp >::adjust_balance_left(), claw::avl_base< K, Comp >::adjust_balance_right(), claw::avl_base< K, Comp >::check_balance(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::new_balance(), claw::avl_base< K, Comp >::recursive_delete_max(), claw::avl_base< K, Comp >::recursive_delete_node(), claw::avl_base< K, Comp >::rotate_left(), claw::avl_base< K, Comp >::rotate_right(), and claw::avl_base< K, Comp >::update_balance().

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

Father of the node. Null if this node is root.

Definition at line 118 of file avl_base.hpp.

Referenced by claw::avl_base< K, Comp >::correct_descendant(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::avl_node::next(), claw::avl_base< K, Comp >::avl_node::prev(), claw::avl_base< K, Comp >::recursive_delete_max(), claw::avl_base< K, Comp >::recursive_delete_node(), claw::avl_base< K, Comp >::rotate_left(), claw::avl_base< K, Comp >::rotate_right(), and claw::avl_base< K, Comp >::validity_check().

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

Node key.

Definition at line 108 of file avl_base.hpp.

Referenced by claw::avl_base< K, Comp >::check_in_bounds(), claw::avl_base< K, Comp >::avl_node::duplicate(), claw::avl_base< K, Comp >::avl_node::find(), claw::avl_base< K, Comp >::avl_node::find_nearest_greater(), claw::avl_base< K, Comp >::avl_node::find_nearest_lower(), claw::avl_base< K, Comp >::insert_node(), claw::avl_base< K, Comp >::avl_iterator::operator*(), claw::avl_base< K, Comp >::avl_iterator::operator->(), claw::avl_base< K, Comp >::recursive_delete(), claw::avl_base< K, Comp >::recursive_delete_max(), claw::avl_base< K, Comp >::update_balance(), and claw::avl_base< K, Comp >::validity_check().

The documentation for this class was generated from the following files:
Generated on Sun Mar 20 2011 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.7.1