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_nodeduplicate (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_nodefind (const K &k)
 Get a pointer on the node of the tree with a specified key.
const avl_nodefind (const K &k) const
 Get a pointer on the node of the tree with a specified key.
avl_nodefind_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_nodefind_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_nodefind_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_nodefind_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_nodelower_bound ()
 Get a pointer on the lowest value of the tree.
const avl_nodelower_bound () const
 Get a pointer on the lowest value of the tree.
avl_nodeupper_bound ()
 Get a pointer on the greatest value of the tree.
const avl_nodeupper_bound () const
 Get a pointer on the greatest value of the tree.
avl_nodeprev ()
 Get the node immediately before this.
const avl_nodeprev () const
 Get the node immediately before this.
avl_nodenext ()
 Get the node immediately greater than this.
const avl_nodenext () const
 Get the node immediately greater than this.

Public Attributes

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_nodefather
 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 65 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 70 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  )  [inline, 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().

00041   : super(), key(k), balance(0), father(NULL) 
00042 {
00043   assert(!super::left);
00044   assert(!super::right);
00045 } // avl_node::avl_node() [constructeur]

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

AVL's node destructor.

Definition at line 52 of file avl_base.tpp.

00053 {
00054 
00055 } // avl_node::~avl_node() [destructeur]

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

Copy constructor.

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

Definition at line 588 of file avl_base.tpp.

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


Member Function Documentation

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

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

00098 {
00099   if (super::left) 
00100     {
00101       delete super::left;
00102       super::left = NULL;
00103     }
00104   if (super::right)
00105     {
00106       delete super::right;
00107       super::right = NULL;
00108     }
00109   assert( !super::left );
00110   assert( !super::right );
00111 } // avl_node::del_tree

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

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

00121 {
00122   unsigned int pl=0, pr=0;
00123 
00124   if (super::left)  pl = super::left->depth();
00125   if (super::right) pr = super::right->depth();
00126 
00127   if (pl > pr)
00128     return 1 + pl;
00129   else
00130     return 1 + pr;
00131 } // 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 [inline]

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=().

00066 {
00067   avl_node* node_copy = new avl_node(key);
00068   ++count;
00069   node_copy->balance = balance;
00070   node_copy->father = NULL;
00071 
00072   if (super::left) 
00073     {
00074       node_copy->left = super::left->duplicate(count);
00075       node_copy->left->father = node_copy;
00076     }
00077   else
00078     node_copy->left = NULL;
00079   
00080   if (super::right) 
00081     {
00082       node_copy->right = super::right->duplicate(count);
00083       node_copy->right->father = node_copy;
00084     }
00085   else
00086     node_copy->right = NULL;
00087 
00088   return node_copy;
00089 } // avl_node::duplicate()

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 [inline]

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.

00166 {
00167   bool ok;
00168   const avl_node* node = this;
00169 
00170   ok = false;
00171 
00172   while (node && !ok)
00173     if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00174       node = node->left;
00175     else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00176       node = node->right;
00177     else
00178       ok = true;
00179 
00180   return node;
00181 } // 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 ( const K &  key  )  [inline]

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

00141 {
00142   bool ok;
00143   avl_node* node = this;
00144 
00145   ok = false;
00146 
00147   while (node && !ok)
00148     if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00149       node = node->left;
00150     else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00151       node = node->right;
00152     else
00153       ok = true;
00154 
00155   return node;
00156 } // 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_nearest_greater ( const K &  key  )  const [inline]

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

Parameters:
key Key to find.

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

00235 {
00236   bool ok;
00237   const avl_node* node = this;
00238   const avl_node* prev_node = NULL;
00239 
00240   ok = false;
00241 
00242   while (node && !ok)
00243     if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00244       {
00245         prev_node = node;
00246         node = node->left;
00247       }
00248     else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00249       {
00250         prev_node = node;
00251         node = node->right;
00252       }
00253     else
00254       ok = true;
00255 
00256   if (ok)
00257     return node->next();
00258   else if (prev_node)
00259     {
00260       if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
00261         return prev_node->next();
00262       else
00263         return prev_node;
00264     }
00265   else
00266     return node;
00267 } // 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_greater ( const K &  key  )  [inline]

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

Parameters:
key Key to find.

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

00192 {
00193   bool ok;
00194   avl_node* node = this;
00195   avl_node* prev_node = NULL;
00196 
00197   ok = false;
00198 
00199   while (node && !ok)
00200     if ( avl_base<K, Comp>::s_key_less(key, node->key) )
00201       {
00202         prev_node = node;
00203         node = node->left;
00204       }
00205     else if ( avl_base<K, Comp>::s_key_less(node->key, key) )
00206       {
00207         prev_node = node;
00208         node = node->right;
00209       }
00210     else
00211       ok = true;
00212 
00213   if (ok)
00214     return node->next();
00215   else if (prev_node)
00216     {
00217       if ( avl_base<K, Comp>::s_key_less(key, prev_node->key) )
00218         return prev_node->next();
00219       else
00220         return prev_node;
00221     }
00222   else
00223     return node;
00224 } // 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_lower ( const K &  key  )  const [inline]

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

Parameters:
key Key to find.

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

00321 {
00322   bool ok;
00323   const avl_node* node = this;
00324   const avl_node* prev_node = NULL;
00325 
00326   ok = false;
00327 
00328   while (node && !ok)
00329     if ( s_key_less(key, node->key) )
00330       {
00331         prev_node = node;
00332         node = node->left;
00333       }
00334     else if ( s_key_less(node->key, key) )
00335       {
00336         prev_node = node;
00337         node = node->right;
00338       }
00339     else
00340       ok = true;
00341 
00342   if (ok)
00343     return node->prev();
00344   else if (prev_node)
00345     {
00346       if ( s_key_less(key, prev_node->key) )
00347         return prev_node;
00348       else
00349         return prev_node->prev();
00350     }
00351   else
00352     return node;
00353 } // avl_base::find_nearest_lower()

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  )  [inline]

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

Parameters:
key Key to find.

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

00278 {
00279   bool ok;
00280   avl_node* node = this;
00281   avl_node* prev_node = NULL;
00282 
00283   ok = false;
00284 
00285   while (node && !ok)
00286     if ( s_key_less(key, node->key) )
00287       {
00288         prev_node = node;
00289         node = node->left;
00290       }
00291     else if ( s_key_less(node->key, key) )
00292       {
00293         prev_node = node;
00294         node = node->right;
00295       }
00296     else
00297       ok = true;
00298 
00299   if (ok)
00300     return node->prev();
00301   else if (prev_node)
00302     {
00303       if ( s_key_less(key, prev_node->key) )
00304         return prev_node;
00305       else
00306         return prev_node->prev();
00307     }
00308   else
00309     return node;
00310 } // 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 [inline]

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.

00379 {
00380   const avl_node* node = this;
00381 
00382   if (node)
00383     while (node->left)
00384       node = node->left;
00385 
00386   return node;
00387 } // 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 (  )  [inline]

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

00362 {
00363   avl_node* node = this;
00364 
00365   if (node)
00366     while (node->left)
00367       node = node->left;
00368 
00369   return node;
00370 } // avl_base::lower_bound()

template<class K , class Comp >
const claw::avl_base< K, Comp >::avl_node * claw::avl_base< K, Comp >::avl_node::next (  )  const [inline]

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.

00470 {
00471   const avl_node* result = this;
00472 
00473   // node have a right subtree : go to the min
00474   if (result->right != NULL)
00475     {
00476       result = result->right;
00477   
00478       while (result->left != NULL)
00479         result = result->left;
00480     }
00481   else
00482     {
00483       bool done = false;
00484       const avl_node* previous_node = this;
00485 
00486       // get parent node
00487       while (result->father && !done)
00488         {
00489           if (result->father->left == result)
00490             done = true;
00491 
00492           result = result->father;
00493         }
00494 
00495       // came back from the max node to the root
00496       if (!done)
00497         result = previous_node;
00498     }
00499                         
00500   return result;
00501 } // avl_iterator::avl_node::next()

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

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++().

00430 {
00431   avl_node* result = this;
00432 
00433   // node have a right subtree : go to the min
00434   if (result->right != NULL)
00435     {
00436       result = result->right;
00437   
00438       while (result->left != NULL)
00439         result = result->left;
00440     }
00441   else
00442     {
00443       bool done = false;
00444       avl_node* previous_node = this;
00445 
00446       // get parent node
00447       while (result->father && !done)
00448         {
00449           if (result->father->left == result)
00450             done = true;
00451 
00452           result = result->father;
00453         }
00454 
00455       // came back from the max node to the root
00456       if (!done)
00457         result = previous_node;
00458     }
00459                         
00460   return result;
00461 } // 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::prev (  )  const [inline]

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.

00545 {
00546   const avl_node* result = this;
00547 
00548   // node have a left subtree : go to the max
00549   if (result->left != NULL)
00550     {
00551       result = result->left;
00552                 
00553       while (result->right != NULL)
00554         result = result->right;
00555     }
00556   else
00557     {
00558       bool done = false;
00559 
00560       // get parent node
00561       while (result->father && !done)
00562         {
00563           if (result->father->right == result)
00564             done = true;
00565 
00566           result = result->father;
00567         }
00568     }
00569   
00570   return result;
00571 } // avl_iterator::avl_node::prev()

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

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

00510 {
00511   avl_node* result = this;
00512 
00513   // node have a left subtree : go to the max
00514   if (result->left != NULL)
00515     {
00516       result = result->left;
00517                 
00518       while (result->right != NULL)
00519         result = result->right;
00520     }
00521   else
00522     {
00523       bool done = false;
00524 
00525       // get parent node
00526       while (result->father && !done)
00527         {
00528           if (result->father->right == result)
00529             done = true;
00530 
00531           result = result->father;
00532         }
00533     }
00534   
00535   return result;
00536 } // 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::upper_bound (  )  const [inline]

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.

00413 {
00414   const avl_node* node = this;
00415 
00416   if (node)
00417     while (node->right)
00418       node = node->right;
00419 
00420   return node;
00421 } // avl_base::upper_bound()

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

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

00396 {
00397   avl_node* node = this;
00398 
00399   if (node)
00400     while (node->right)
00401       node = node->right;
00402 
00403   return node;
00404 } // avl_base::upper_bound()


Member Data Documentation

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

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

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