KSquare Utilities
Public Types | Public Member Functions | Friends | List of all members
KKB::RBTree< Entry, CompareNodes, KeyType > Class Template Reference

#include <RBTree.h>

Public Types

typedef Entry * EntryPtr
 
typedef Iterator< Entry, CompareNodes, KeyType > * IteratorPtr
 
typedef RBnode< Entry > Node
 
typedef Node * NodePtr
 
typedef RBTree< Entry, CompareNodes, KeyType > Tree
 
typedef Tree * TreePtr
 

Public Member Functions

 RBTree (CompareNodes &_comparator, bool _owner)
 
 RBTree (RBTree &tree)
 
 ~RBTree ()
 
void CalcTreeStats ()
 
bool CompareToTree (TreePtr tree)
 
void DeleteCurrentNode ()
 
void DeleteEntry (EntryPtr e)
 
EntryPtr GetEqual (const KeyType &key)
 
EntryPtr GetFirst ()
 
EntryPtr GetGreater (const KeyType &key)
 
EntryPtr GetGreaterOrEqual (const KeyType &key)
 
EntryPtr GetLast ()
 
EntryPtr GetLess (const KeyType &key)
 
EntryPtr GetNext ()
 
EntryPtr GetPrev ()
 
EntryPtr Predecessor ()
 
NodePtr RBInsert (EntryPtr e)
 
kkuint32 Size ()
 
EntryPtr Successor ()
 
bool Validate ()
 
void WalkTree ()
 

Friends

class Iterator< Entry, CompareNodes, KeyType >
 

Detailed Description

template<class Entry, class CompareNodes, typename KeyType>
class KKB::RBTree< Entry, CompareNodes, KeyType >

Definition at line 69 of file RBTree.h.

Member Typedef Documentation

template<class Entry, class CompareNodes, typename KeyType>
typedef Entry* KKB::RBTree< Entry, CompareNodes, KeyType >::EntryPtr

Definition at line 122 of file RBTree.h.

template<class Entry, class CompareNodes, typename KeyType>
typedef Iterator<Entry,CompareNodes,KeyType>* KKB::RBTree< Entry, CompareNodes, KeyType >::IteratorPtr

Definition at line 176 of file RBTree.h.

template<class Entry, class CompareNodes, typename KeyType>
typedef RBnode<Entry> KKB::RBTree< Entry, CompareNodes, KeyType >::Node

Definition at line 123 of file RBTree.h.

template<class Entry, class CompareNodes, typename KeyType>
typedef Node* KKB::RBTree< Entry, CompareNodes, KeyType >::NodePtr

Definition at line 124 of file RBTree.h.

template<class Entry, class CompareNodes, typename KeyType>
typedef RBTree<Entry,CompareNodes,KeyType> KKB::RBTree< Entry, CompareNodes, KeyType >::Tree

Definition at line 126 of file RBTree.h.

template<class Entry, class CompareNodes, typename KeyType>
typedef Tree* KKB::RBTree< Entry, CompareNodes, KeyType >::TreePtr

Definition at line 128 of file RBTree.h.

Constructor & Destructor Documentation

template<class Entry , class CompareNodes, typename KeyType >
KKB::RBTree< Entry, CompareNodes, KeyType >::RBTree ( CompareNodes &  _comparator,
bool  _owner 
)

Definition at line 298 of file RBTree.h.

300  :
301  comparator (_comparator),
302  curNode (NULL),
303  nil (NULL),
304  owner (_owner),
305  root (NULL),
306  size (0),
307  numOfIterators(0),
308  iterators (NULL)
309 {
310  nil = new RBnode<Entry> (NULL, NULL, NULL, RBcolor::Black, NULL);
311  root = nil;
312  curNode = nil;
313 }
template<class Entry , class CompareNodes, typename KeyType >
KKB::RBTree< Entry, CompareNodes, KeyType >::RBTree ( RBTree< Entry, CompareNodes, KeyType > &  tree)

Definition at line 319 of file RBTree.h.

319  :
320 
321  comparator (tree.comparator),
322  size (tree.size),
323  owner (true),
324  root (NULL),
325  nil (NULL),
326  numOfIterators(0),
327  iterators (NULL)
328 {
329  nil = new RBnode<Entry> (NULL, NULL, NULL, Black, NULL);
330  root = CloneSubTree (tree.root, tree.nil, nil);
331 
332  kkint32 x = CountNodesInSubTree (root);
333 
334  curNode = nil;
335 }
KKB::kkint32
__int32 kkint32
Definition: KKBaseTypes.h:88
template<class Entry , class CompareNodes , typename KeyType >
KKB::RBTree< Entry, CompareNodes, KeyType >::~RBTree ( )

Definition at line 370 of file RBTree.h.

371 {
372  if (root != nil)
373  DeleteSubTree (root);
374 
375 
376  for (kkint32 i = 0; i < numOfIterators; i++)
377  {
378  iterators[i]->TreeHasBeenDeleted ();
379  }
380 
381  delete nil;
382 }
KKB::kkint32
__int32 kkint32
Definition: KKBaseTypes.h:88

Member Function Documentation

template<class Entry , class CompareNodes , typename KeyType >
void KKB::RBTree< Entry, CompareNodes, KeyType >::CalcTreeStats ( )

Definition at line 1393 of file RBTree.h.

1394 {
1395  kkint32 numOfLeafs = 0;
1396  kkint32 numOfNodes = 0;
1397  kkint32* leafPaths = new kkint32[size];
1398 
1399  kkint32 shortestPath = INT_MAX;
1400  kkint32 longestPath = INT_MIN;
1401 
1402  CheckNodeStats (root, numOfNodes, numOfLeafs, leafPaths, shortestPath, longestPath, 0);
1403 
1404  kkint32 totalLen = 0;
1405 
1406  for (kkint32 x = 0; x < numOfLeafs; x++)
1407  totalLen += leafPaths[x];
1408 
1409  double avgLen = (double)totalLen / (double)numOfLeafs;
1410 
1411  std::cout << std::endl
1412  << "Number of Nodes [" << numOfNodes << "]" << std::endl
1413  << "Number of Leafs [" << numOfLeafs << "]" << std::endl
1414  << "Shortest Path [" << shortestPath << "]" << std::endl
1415  << "Longest Path [" << longestPath << "]" << std::endl
1416  << "Average Length [" << avgLen << "]" << std::endl;
1417 }
KKB::endl
HTMLReport &__cdecl endl(HTMLReport &htmlReport)
Definition: HTMLReport.cpp:240
KKB::kkint32
__int32 kkint32
Definition: KKBaseTypes.h:88
INT_MAX
#define INT_MAX
Adapted by Kurt Kramer be a &#39;class&#39; definition so as to make it more usable in th ePices software wor...
Definition: UsfCasCor.h:186
template<class Entry , class CompareNodes , typename KeyType >
bool KKB::RBTree< Entry, CompareNodes, KeyType >::CompareToTree ( TreePtr  tree)

Definition at line 409 of file RBTree.h.

410 {
411  return AreSubTreesTheSame (root, nil, tree->root, tree->nil);
412 } /* CompareToTree */
template<class Entry , class CompareNodes , typename KeyType >
void KKB::RBTree< Entry, CompareNodes, KeyType >::DeleteCurrentNode ( )

Definition at line 718 of file RBTree.h.

719 {
720  if ((curNode == nil) || (curNode == NULL))
721  {
722  std::cerr << std::endl;
723  std::cerr << " *** Warning ***" << std::endl;
724  std::cerr << std::endl;
725  std::cerr << "RBTree<Entry,CompareNodes,KeyType>::DeleteCurrentNode - No Current Node Defined." << std::endl;
726  std::cerr << std::endl;
727  return;
728  }
729 
730 
731  EntryPtr entry2Delete = curNode->Data ();
732 
733  NodePtr node2Delete = curNode;
734 
735  curNode = Predecessor (node2Delete);
736  if ((curNode == nil) || (curNode == NULL))
737  curNode = Successor (node2Delete);
738 
739 
740  NodePtr deletedNode = RBDelete (node2Delete);
741 
742  if (deletedNode->Data () != entry2Delete)
743  {
744  std::cerr << std::endl;
745  std::cerr << " *** ERROR ***" << std::endl;
746  std::cerr << std::endl;
747  std::cerr << "RBTree<Entry,CompareNodes,KeyType>::DeleteCurrentNode - Wrong Node was Returned for Deletion." << std::endl;
748  std::cerr << std::endl;
749  }
750  else
751  {
752  if (owner)
753  delete deletedNode->Data ();
754 
755  delete deletedNode;
756  }
757 } /* DeleteCurrentNode */
KKB::endl
HTMLReport &__cdecl endl(HTMLReport &htmlReport)
Definition: HTMLReport.cpp:240
KKB::RBTree::NodePtr
Node * NodePtr
Definition: RBTree.h:124
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
KKB::RBTree::EntryPtr
Entry * EntryPtr
Definition: RBTree.h:122
KKB::RBTree::Successor
EntryPtr Successor()
Definition: RBTree.h:700
KKB::RBTree::Predecessor
EntryPtr Predecessor()
Definition: RBTree.h:682
template<class Entry , class CompareNodes , typename KeyType >
void KKB::RBTree< Entry, CompareNodes, KeyType >::DeleteEntry ( EntryPtr  e)

Definition at line 1382 of file RBTree.h.

1383 {
1384  RBnode<Entry>* node2Delete = SearchForEntry (root, e);
1385  if (node2Delete)
1386  RBDelete (node2Delete);
1387 } /* DeleteEntry */
template<class Entry , class CompareNodes , typename KeyType>
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::GetEqual ( const KeyType &  key)

Definition at line 493 of file RBTree.h.

494 {
495  curNode = GetEqual (root, key);
496 
497  if (curNode == nil)
498  return NULL;
499 
500  return curNode->Data ();
501 }
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
KKB::RBTree::GetEqual
EntryPtr GetEqual(const KeyType &key)
Definition: RBTree.h:493
template<class Entry , class CompareNodes , typename KeyType >
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::GetFirst ( )

Definition at line 763 of file RBTree.h.

764 {
765  if (root == nil)
766  return NULL;
767 
768  curNode = Minimum ();
769  return curNode->Data ();
770 } /* GetFirst () */
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
template<class Entry , class CompareNodes , typename KeyType>
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::GetGreater ( const KeyType &  key)

Definition at line 598 of file RBTree.h.

599 {
600  curNode = GetGreater (root, key);
601  return curNode->Data ();
602 } /* GetGreater */
KKB::RBTree::GetGreater
EntryPtr GetGreater(const KeyType &key)
Definition: RBTree.h:598
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
template<class Entry , class CompareNodes , typename KeyType>
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::GetGreaterOrEqual ( const KeyType &  key)

Definition at line 608 of file RBTree.h.

609 {
610  curNode = GetGreaterOrEqual (root, key);
611  return curNode->Data ();
612 } /* GetGreater */
KKB::RBTree::GetGreaterOrEqual
EntryPtr GetGreaterOrEqual(const KeyType &key)
Definition: RBTree.h:608
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
template<class Entry , class CompareNodes , typename KeyType >
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::GetLast ( )

Definition at line 776 of file RBTree.h.

777 {
778  if (root == nil)
779  return NULL;
780 
781  curNode = Maximum ();
782  return curNode->Data ();
783 } /* GetLast () */
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
template<class Entry , class CompareNodes , typename KeyType>
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::GetLess ( const KeyType &  key)

Definition at line 669 of file RBTree.h.

670 {
671  curNode = GetLess (root, key);
672  return curNode->Data ();
673 } /* GetGreater */
KKB::RBTree::GetLess
EntryPtr GetLess(const KeyType &key)
Definition: RBTree.h:669
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
template<class Entry, class CompareNodes, typename KeyType>
EntryPtr KKB::RBTree< Entry, CompareNodes, KeyType >::GetNext ( )
inline

Definition at line 164 of file RBTree.h.

164 {return Successor ();}
KKB::RBTree::Successor
EntryPtr Successor()
Definition: RBTree.h:700
template<class Entry, class CompareNodes, typename KeyType>
EntryPtr KKB::RBTree< Entry, CompareNodes, KeyType >::GetPrev ( )
inline

Definition at line 166 of file RBTree.h.

166 {return Predecessor ();}
KKB::RBTree::Predecessor
EntryPtr Predecessor()
Definition: RBTree.h:682
template<class Entry , class CompareNodes , typename KeyType >
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::Predecessor ( )

Definition at line 682 of file RBTree.h.

683 {
684  if ((curNode == nil) || (curNode == NULL))
685  return NULL;
686 
687  curNode = Predecessor (curNode);
688 
689  if ((curNode == nil) || (curNode == NULL))
690  return NULL;
691 
692  return curNode->Data ();
693 } /* Predecessor */
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
KKB::RBTree::Predecessor
EntryPtr Predecessor()
Definition: RBTree.h:682
template<class Entry , class CompareNodes , typename KeyType >
KKB::RBnode< Entry > * KKB::RBTree< Entry, CompareNodes, KeyType >::RBInsert ( EntryPtr  e)

Definition at line 1111 of file RBTree.h.

1112 {
1113  NodePtr newNode = Insert (e);
1114 
1115  NodePtr x = newNode;
1116 
1117  NodePtr y = NULL;
1118 
1119  x->Color (RBcolor::Red);
1120 
1121  while ((x != root) && (x->Parent ()->Color () == RBcolor::Red))
1122  {
1123  if (x->Parent () == x->Parent ()->Parent ()->Left ())
1124  {
1125  y = x->Parent ()->Parent ()->Right ();
1126 
1127  if (y->Color () == RBcolor::Red)
1128  {
1129  x->Parent ()->Color (RBcolor::Black); // Case 1
1130  y->Color (RBcolor::Black); // Case 1
1131  x->Parent ()->Parent ()->Color (RBcolor::Red); // Case 1
1132  x = x->Parent ()->Parent (); // Case 1
1133  }
1134 
1135  else
1136  {
1137  if (x == x->Parent ()->Right ())
1138  {
1139  x = x->Parent (); // Case 2
1140  LeftRotate (x); // Case 2
1141  }
1142 
1143  x->Parent ()->Color (RBcolor::Black); // Case 3
1144  x->Parent ()->Parent ()->Color (RBcolor::Red); // Case 3
1145  RightRotate (x->Parent ()->Parent ()); // Case 3
1146  }
1147  }
1148 
1149  else
1150  {
1151  y = x->Parent ()->Parent ()->Left ();
1152 
1153  if (y->Color () == RBcolor::Red)
1154  {
1155  x->Parent ()->Color (RBcolor::Black);
1156  y->Color (RBcolor::Black);
1157  x->Parent ()->Parent ()->Color (RBcolor::Red);
1158  x = x->Parent ()->Parent ();
1159  }
1160 
1161  else
1162  {
1163  if (x == x->Parent ()->Left ())
1164  {
1165  x = x->Parent ();
1166  RightRotate (x);
1167  }
1168 
1169  x->Parent ()->Color (RBcolor::Black);
1170  x->Parent ()->Parent ()->Color (RBcolor::Red);
1171  LeftRotate (x->Parent ()->Parent ());
1172  }
1173  }
1174  }
1175 
1176 
1177  root->Color (RBcolor::Black);
1178  return newNode;
1179 } /* RBInsert */
KKB::RBTree::NodePtr
Node * NodePtr
Definition: RBTree.h:124
KKB::RBnode::Color
RBcolor Color()
Definition: RBTree.h:47
KKB::RBnode::Left
RBnodePtr Left()
Definition: RBTree.h:49
KKB::RBnode::Parent
RBnodePtr Parent()
Definition: RBTree.h:50
template<class Entry, class CompareNodes, typename KeyType>
kkuint32 KKB::RBTree< Entry, CompareNodes, KeyType >::Size ( )
inline

Definition at line 140 of file RBTree.h.

140 {return size;}
template<class Entry , class CompareNodes , typename KeyType >
Entry * KKB::RBTree< Entry, CompareNodes, KeyType >::Successor ( )

Definition at line 700 of file RBTree.h.

701 {
702  if ((curNode == nil) || (curNode == NULL))
703  return NULL;
704 
705  curNode = Successor (curNode);
706 
707  if ((curNode == nil) || (curNode == NULL))
708  return NULL;
709 
710  return curNode->Data ();
711 } /* Successor */
KKB::RBnode::Data
EntryPtr Data()
Definition: RBTree.h:48
KKB::RBTree::Successor
EntryPtr Successor()
Definition: RBTree.h:700
template<class Entry , class CompareNodes , typename KeyType >
bool KKB::RBTree< Entry, CompareNodes, KeyType >::Validate ( )

Definition at line 1483 of file RBTree.h.

1484 {
1485  kkint32 blackNodeHeight = -1;
1486 
1487  kkint32 numOfNodes = ValidateSubTree (root, nil, "Root", 0, blackNodeHeight);
1488 
1489  if (numOfNodes != size)
1490  {
1491  std::cerr << std::endl
1492  << "*** ERROR *** NumOfNodes[" << numOfNodes << "] Does not add up to size[" << size << "]." << std::endl;
1493  return false;
1494  }
1495 
1496  return true;
1497 }
KKB::endl
HTMLReport &__cdecl endl(HTMLReport &htmlReport)
Definition: HTMLReport.cpp:240
KKB::kkint32
__int32 kkint32
Definition: KKBaseTypes.h:88
template<class Entry, class CompareNodes, typename KeyType>
void KKB::RBTree< Entry, CompareNodes, KeyType >::WalkTree ( )
inline

Definition at line 142 of file RBTree.h.

142 {WalkTree (root);}
KKB::RBTree::WalkTree
void WalkTree()
Definition: RBTree.h:142

Friends And Related Function Documentation

template<class Entry, class CompareNodes, typename KeyType>
friend class Iterator< Entry, CompareNodes, KeyType >
friend

Definition at line 130 of file RBTree.h.

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