MeVisLabToolboxReference
|
00001 00002 00003 /* 00004 * SbMap is based on BinTree - Binary tree template class written by 00005 * Per Nilsson, It is Freeware and not copyrighted. 00006 * 00007 _______________________________________________________________________ 00008 _______________________________________________________________________ 00009 | 00010 | 00011 | Description: 00012 | SbMap is a container that associates objects of type KeyType with 00013 | objects of type ValueType. No two elements will have the same key. 00014 | SbMap has the important property that inserting a new element into 00015 | a map does not invalidate iterators that point to existing elements. 00016 | Erasing an element from a map also does not invalidate any iterators, 00017 | except, of course, for iterators that actually point to the element 00018 | that is being erased. 00019 | 00020 | Classes: 00021 | 00022 | // The map item class. 00023 | template <class KeyType, class ValueType> class SbMapItem 00024 | 00025 | // The map class 00026 | template <class KeyType, class ValueType> class SbMap 00027 | { 00028 | public: 00029 | 00030 | // Regular low->high (++) and high->low (--) iterator 00031 | class Iterator 00032 | 00033 | // Top to bottom iterator 00034 | class ParentFirstIterator 00035 | 00036 | // Bottom to top iterator 00037 | class ParentLastIterator 00038 | 00039 | // Top to bottom, level by level iterator 00040 | class ByLevelIterator 00041 | } 00042 | 00043 | Requirements: 00044 | 00045 | The KeyType class must support: 00046 | 1. < and == operations. 00047 | 2. Copy construction. 00048 | 00049 | The ValueType must support: 00050 | 1. Copy construction. 00051 | 2. Assignment operation (=) if SbMapItem::setValue is used 00052 | 00053 | 00054 | Author(s) : Per Nilsson, Felix Ritter 00055 | 00056 _______________________________________________________________________ 00057 _______________________________________________________________________ 00058 */ 00059 00060 #ifndef _SB_MAP_ 00061 #define _SB_MAP_ 00062 00063 #include "SoShaderSystem.h" 00064 00066 template <class KeyType, class ValueType> 00067 class SbMapItem 00068 { 00069 public: 00070 00071 // Constructor(Key, Value) 00072 SbMapItem(const KeyType &k, const ValueType &v) 00073 :mKey(k), mValue(v), mLeftChild(0), mRightChild(0), mParent(0), mIsRed(true) { 00074 } 00075 00076 // Destructor 00077 virtual ~SbMapItem() { 00078 } 00079 00080 // Set methods 00081 00082 // set*Child also updates the the child's parent attribute. 00083 void setLeftChild(SbMapItem *p) { 00084 mLeftChild = p; 00085 if(p) 00086 p->setParent(this); 00087 } 00088 void setRightChild(SbMapItem *p) { 00089 mRightChild = p; 00090 if(p) 00091 p->setParent(this); 00092 } 00093 void setParent(SbMapItem *p) { 00094 mParent = p; 00095 } 00096 00097 void setValue(const ValueType &v) { 00098 mValue = v; 00099 } 00100 // Note: Deliberately no SetKey, that could easily screw up the tree. 00101 // If a key shall be changed, delete node from tree and insert a new one instead. 00102 00103 void setRed() { 00104 mIsRed = true; 00105 } 00106 void setBlack() { 00107 mIsRed = false; 00108 } 00109 00110 // Get methods 00111 00112 SbMapItem *getLeftChild() const { 00113 return mLeftChild; 00114 } 00115 SbMapItem *getRightChild() const { 00116 return mRightChild; 00117 } 00118 SbMapItem *getParent() const { 00119 return mParent; 00120 } 00121 00122 ValueType getValue() { 00123 return mValue; 00124 } 00125 const ValueType &getValue() const { 00126 return mValue; 00127 } 00128 KeyType getKey() { 00129 return mKey; 00130 } 00131 const KeyType &getKey() const { 00132 return mKey; 00133 } 00134 00135 // Some more or less useful queries 00136 bool isRoot() const { 00137 return mParent == 0; 00138 } 00139 bool isLeftChild() const { 00140 return mParent != 0 && mParent->getLeftChild() == this; 00141 } 00142 bool isRightChild() const { 00143 return mParent != 0 && mParent->getRightChild() == this; 00144 } 00145 bool isLeaf() const { 00146 return mLeftChild == 0 && mRightChild == 0; 00147 } 00148 unsigned int GetLevel() const { 00149 return (isRoot()) ? 1 : getParent()->GetLevel() + 1; 00150 } 00151 00152 bool isRed() const { 00153 return mIsRed; 00154 }; 00155 bool isBlack() const { 00156 return !mIsRed; 00157 }; 00158 00159 private: 00160 00161 // Default constructor - deliberately not implemented 00162 SbMapItem(); 00163 00164 SbMapItem *mLeftChild; 00165 SbMapItem *mRightChild; 00166 SbMapItem *mParent; 00167 00168 KeyType mKey; 00169 ValueType mValue; 00170 00171 bool mIsRed; 00172 }; 00173 00175 template <class KeyType, class ValueType> 00176 class SbMap 00177 { 00178 public: 00179 00180 typedef SbMapItem<KeyType,ValueType> Node; 00181 00183 class Iterator 00184 { 00185 public: 00186 00187 // Default Constructor 00188 Iterator() : mRoot(0), mCur(0) { 00189 } 00190 00191 // Constructor(Node *) 00192 Iterator(Node *root) : mRoot(root) { 00193 reset(); 00194 } 00195 00196 // Copy constructor 00197 Iterator(const Iterator &src) : mRoot(src.mRoot), mCur(src.mCur) { 00198 } 00199 00200 // reset the iterator 00201 // atLowest : true - reset at lowest key value (and then ++ your way through) 00202 // false - reset at highest key value (and then -- your way through) 00203 void reset(bool atLowest = true) { 00204 mCur = (atLowest) ? minNode(mRoot) : maxNode(mRoot); 00205 } 00206 00207 // Has the iterator reached the end? 00208 bool atEnd() const { 00209 return mCur == 0; 00210 } 00211 Node *getNode() { 00212 return mCur; 00213 } 00214 00215 // Assignment operator 00216 Iterator &operator =(const Iterator &src) { 00217 mRoot = src.mRoot; 00218 mCur = src.mCur; 00219 return *this; 00220 } 00221 00222 // Increment operator 00223 void operator ++(int) { 00224 Inc(); 00225 } 00226 00227 // Decrement operator 00228 void operator --(int) { 00229 Dec(); 00230 } 00231 00232 // Access operators 00233 Node *operator ->() { 00234 return getNode(); 00235 } 00236 Node &operator *() { 00237 if(atEnd()) { 00238 throw "Iterator at end"; 00239 } 00240 return *getNode(); 00241 } 00242 00243 private: 00244 00245 // minNode: Returns node with lowest key from n and down. 00246 // Ie the node all down to the left 00247 Node *minNode(Node *n) { 00248 while(n && n->getLeftChild()) 00249 n = n->getLeftChild(); 00250 return n; 00251 } 00252 // maxNode: Returns node with highest key from n and down. 00253 // Ie the node all down to the right 00254 Node *maxNode(Node *n) { 00255 while(n && n->getRightChild()) 00256 n = n->getRightChild(); 00257 return n; 00258 } 00259 00260 // ++ 00261 void Inc() { 00262 // Already at end? 00263 if(mCur == 0) 00264 return; 00265 00266 if(mCur->getRightChild()) { 00267 // If current node has a right child, the next higher node is the 00268 // node with lowest key beneath the right child. 00269 mCur = minNode(mCur->getRightChild()); 00270 } 00271 else if(mCur->isLeftChild()) { 00272 // No right child? Well if current node is a left child then 00273 // the next higher node is the parent 00274 mCur = mCur->getParent(); 00275 } 00276 else { 00277 // Current node neither is left child nor has a right child. 00278 // Ie it is either right child or root 00279 // The next higher node is the parent of the first non-right 00280 // child (ie either a left child or the root) up in the 00281 // hierarchy. Root's parent is 0. 00282 while(mCur->isRightChild()) 00283 mCur = mCur->getParent(); 00284 mCur = mCur->getParent(); 00285 } 00286 } 00287 00288 // -- 00289 void Dec() { 00290 // Already at end? 00291 if(mCur == 0) 00292 return; 00293 00294 if(mCur->getLeftChild()) { 00295 // If current node has a left child, the next lower node is the 00296 // node with highest key beneath the left child. 00297 mCur = maxNode(mCur->getLeftChild()); 00298 } 00299 else if(mCur->isRightChild()) { 00300 // No left child? Well if current node is a right child then 00301 // the next lower node is the parent 00302 mCur = mCur->getParent(); 00303 } 00304 else { 00305 // Current node neither is right child nor has a left child. 00306 // Ie it is either left child or root 00307 // The next higher node is the parent of the first non-left 00308 // child (ie either a right child or the root) up in the 00309 // hierarchy. Root's parent is 0. 00310 00311 while(mCur->isLeftChild()) 00312 mCur = mCur->getParent(); 00313 mCur = mCur->getParent(); 00314 } 00315 } 00316 00317 Node *mRoot; 00318 Node *mCur; 00319 }; // Iterator 00320 00322 // Traverses the tree from top to bottom. Typical usage is 00323 // when storing the tree structure, because when reading it 00324 // later (and inserting elements) the tree structure will 00325 // be the same. 00326 class ParentFirstIterator 00327 { 00328 public: 00329 00330 // Default constructor 00331 ParentFirstIterator() : mRoot(0), mCur(0) { 00332 } 00333 00334 // Constructor(Node*) 00335 explicit ParentFirstIterator(Node *root) : mRoot(root), mCur(0) { 00336 reset(); 00337 } 00338 00339 void reset() { 00340 mCur = mRoot; 00341 }; 00342 00343 // Has the iterator reached the end? 00344 bool atEnd() const { 00345 return mCur==0; 00346 } 00347 Node *getNode() { 00348 return mCur; 00349 } 00350 00351 // Assignment operator 00352 ParentFirstIterator &operator =(const ParentFirstIterator &src) { 00353 mRoot = src.mRoot; 00354 mCur = src.mCur; 00355 return *this; 00356 } 00357 00358 // Increment operator 00359 void operator ++(int) { 00360 Inc(); 00361 } 00362 00363 // Access operators 00364 Node *operator ->() { 00365 return getNode(); 00366 } 00367 Node &operator *() { 00368 if(atEnd()) 00369 throw "ParentFirstIterator at end"; 00370 return *getNode(); 00371 } 00372 00373 private: 00374 00375 void Inc() { 00376 // Already at end? 00377 if(mCur == 0) 00378 return; 00379 00380 // First we try down to the left 00381 if(mCur->getLeftChild()) { 00382 mCur = mCur->getLeftChild(); 00383 } 00384 else if(mCur->getRightChild()) { 00385 // No left child? The we go down to the right. 00386 mCur = mCur->getRightChild(); 00387 } 00388 else { 00389 // No children? Move up in the hierarcy until 00390 // we either reach 0 (and are finished) or 00391 // find a right uncle. 00392 while(mCur != 0) { 00393 // But if parent is left child and has a right "uncle" the parent 00394 // has already been processed but the uncle hasn't. Move to 00395 // the uncle. 00396 if(mCur->isLeftChild() && mCur->getParent()->getRightChild()) { 00397 mCur = mCur->getParent()->getRightChild(); 00398 return; 00399 } 00400 mCur = mCur->getParent(); 00401 } 00402 } 00403 } 00404 00405 Node *mRoot; 00406 Node *mCur; 00407 00408 }; // ParentFirstIterator 00409 00411 // Typical usage is when deleting all elements in the tree 00412 // because you must delete the children before you delete 00413 // their parent. 00414 class ParentLastIterator 00415 { 00416 public: 00417 00418 // Default constructor 00419 ParentLastIterator() : mRoot(0), mCur(0) { 00420 } 00421 00422 // Constructor(Node*) 00423 explicit ParentLastIterator(Node *root) : mRoot(root), mCur(0) { 00424 reset(); 00425 } 00426 00427 void reset() { 00428 mCur = minNode(mRoot); 00429 } 00430 00431 // Has the iterator reached the end? 00432 bool atEnd() const { 00433 return mCur == 0; 00434 } 00435 Node *getNode() { 00436 return mCur; 00437 } 00438 00439 // Assignment operator 00440 ParentLastIterator &operator =(const ParentLastIterator &src) { 00441 mRoot = src.mRoot; 00442 mCur = src.mCur; 00443 return *this; 00444 } 00445 00446 // Increment operator 00447 void operator ++(int) { 00448 Inc(); 00449 } 00450 00451 // Access operators 00452 Node *operator ->() { 00453 return getNode(); 00454 } 00455 Node &operator *() { 00456 if(atEnd()) 00457 throw "ParentLastIterator at end"; 00458 return *getNode(); 00459 } 00460 00461 private: 00462 00463 // minNode: Returns the node as far down to the left as possible. 00464 Node *minNode(Node *n) { 00465 while(n != 0 && (n->getLeftChild() != 0 || n->getRightChild() != 0)) { 00466 n = (n->getLeftChild()) ? n->getLeftChild() : n->getRightChild(); 00467 } 00468 return n; 00469 } 00470 00471 void Inc() { 00472 // Already at end? 00473 if(mCur == 0) 00474 return; 00475 00476 // Note: Starting point is the node as far down to the left as possible. 00477 00478 // If current node has an uncle to the right, go to the 00479 // node as far down to the left from the uncle as possible 00480 // else just go up a level to the parent. 00481 if(mCur->isLeftChild() && mCur->getParent()->getRightChild()) { 00482 mCur = minNode(mCur->getParent()->getRightChild()); 00483 } 00484 else { 00485 mCur = mCur->getParent(); 00486 } 00487 } 00488 00489 Node *mRoot; 00490 Node *mCur; 00491 }; // ParentLastIterator 00492 00494 // ByLevelIterator. Traverse tree top to bottom, level by level left to right. 00495 // Typical usage : I don't know. Perhaps if the tree should be displayed 00496 // in some fancy way. 00497 // It is the most memory consuming of all iterators as it will allocate an 00498 // array of (size()+1)/2 Node*s. 00499 // Impl. desc: 00500 // mArray[0] is the current node we're looking at, initially set to mRoot. 00501 // When ++:ing the children of mArray[0] (if any) are put last in the 00502 // array and the array is shifted down 1 step 00503 class ByLevelIterator 00504 { 00505 public: 00506 00507 // Default constructor 00508 ByLevelIterator() : mRoot(0), mArray(0), mSize(0) { 00509 } 00510 00511 // Constructor(treeRoot, elementsInTree) 00512 ByLevelIterator(Node *root, unsigned int size) : mRoot(root), mSize(size), mArray(0) { 00513 reset(); 00514 } 00515 00516 // Copy constructor 00517 ByLevelIterator(const ByLevelIterator &src) : mRoot(src.mRoot), mSize(src.mSize), mEndPos(src.mEndPos) { 00518 if(src.mArray != 0) { 00519 mArray = new Node*[(mSize+1)/2]; 00520 memcpy(mArray, src.mArray, sizeof(Node*)*(mSize+1)/2); 00521 } 00522 else 00523 mArray = 0; 00524 } 00525 00526 // Destructor 00527 ~ByLevelIterator() { 00528 if(mArray != 0) { 00529 delete [] mArray; 00530 mArray = 0; 00531 } 00532 } 00533 00534 void reset() { 00535 if(mSize > 0) { 00536 // Only allocate the first time reset is called 00537 if(mArray == 0) { 00538 // mArray must be able to hold the maximum "width" of the tree which 00539 // at most can be (NumberOfNodesInTree + 1 ) / 2 00540 mArray = new Node*[(mSize+1)/2]; 00541 } 00542 // Initialize the array with 1 element, the mRoot. 00543 mArray[0] = mRoot; 00544 mEndPos = 1; 00545 } 00546 else 00547 mEndPos=0; 00548 } 00549 00550 // Has the iterator reached the end? 00551 bool atEnd() const { 00552 return mEndPos == 0; 00553 } 00554 Node *getNode() { 00555 return mArray[0]; 00556 } 00557 00558 // Assignment Operator 00559 ByLevelIterator &operator =(const ByLevelIterator &src) { 00560 mRoot = src.mRoot; 00561 mSize = src.mSize; 00562 if(src.mArray != 0) { 00563 mArray = new Node*[(mSize+1)/2]; 00564 memcpy(mArray, src.mArray, sizeof(Node*)*(mSize+1)/2); 00565 } 00566 else 00567 mArray = 0; 00568 00569 return *this; 00570 } 00571 00572 // Increment operator 00573 void operator ++(int) { 00574 Inc(); 00575 } 00576 00577 // Access operators 00578 Node *operator ->() { 00579 return getNode(); 00580 } 00581 Node &operator *() { 00582 if(atEnd()) 00583 throw "ParentLastIterator at end"; 00584 return *getNode(); 00585 } 00586 00587 private: 00588 00589 void Inc() { 00590 if(mEndPos == 0) 00591 return; 00592 00593 // Current node is mArray[0] 00594 Node *pNode = mArray[0]; 00595 00596 // Move the array down one notch, ie we have a new current node 00597 // (the one than just was mArray[1]) 00598 for(unsigned int i = 0; i < mEndPos; i++) { 00599 mArray[i] = mArray[i+1]; 00600 } 00601 mEndPos--; 00602 00603 Node *pChild=pNode->getLeftChild(); 00604 if(pChild) { // Append the left child of the former current node 00605 mArray[mEndPos] = pChild; 00606 mEndPos++; 00607 } 00608 00609 pChild = pNode->getRightChild(); 00610 if(pChild) { // Append the right child of the former current node 00611 mArray[mEndPos] = pChild; 00612 mEndPos++; 00613 } 00614 00615 } 00616 00617 Node **mArray; 00618 Node *mRoot; 00619 unsigned int mSize; 00620 unsigned int mEndPos; 00621 }; // ByLevelIterator 00622 00624 // It makes it possible to have different behavior in situations like: 00625 // myTree["Foo"] = 32; 00626 // If "Foo" already exist, just update its value else insert a new 00627 // element. 00628 // int i = myTree["Foo"] 00629 // If "Foo" exists return its value, else throw an exception. 00630 // 00631 class AccessClass 00632 { 00633 // Let SbMap be the only one who can instantiate this class. 00634 friend class SbMap<KeyType, ValueType>; 00635 00636 public: 00637 00638 // Assignment operator. Handles the myTree["Foo"] = 32; situation 00639 operator =(const ValueType &value) { 00640 // Just use the set method, it handles already exist/not exist situation 00641 mTree.set(mKey, value); 00642 } 00643 00644 // ValueType operator 00645 operator ValueType() { 00646 Node *node = mTree.find(mKey); 00647 00648 // Not found 00649 if(node == 0) { 00650 throw "Item not found"; 00651 } 00652 00653 return node->getValue(); 00654 } 00655 00656 00657 private: 00658 00659 // Private Construction 00660 AccessClass(SbMap &tree, const KeyType &key) : mTree(tree), mKey(key) { 00661 } 00662 00663 // Default constructor 00664 AccessClass(); 00665 00666 SbMap &mTree; 00667 const KeyType &mKey; 00668 }; // AccessClass 00669 00670 00671 // Constructor. 00672 SbMap() : mRoot(0), mSize(0) {} 00673 00674 // Copy constructor 00675 explicit SbMap(const SbMap &src) : mRoot(0), mSize(0) { 00676 *this = src; 00677 } 00678 00679 // Destructor 00680 ~SbMap() { 00681 clear(); 00682 } 00683 00684 // Assignment operator 00685 SbMap &operator = (const SbMap &src) { 00686 clear(); 00687 00688 for(ParentFirstIterator i(src.getParentFirstIterator()); !i.atEnd(); i++) { 00689 set(i->getKey(), i->getValue()); 00690 } 00691 } 00692 00693 00694 bool insert(const KeyType &keyNew, const ValueType &v) { 00695 // First insert node the "usual" way (no fancy balance logic yet) 00696 Node *newNode = new Node(keyNew, v); 00697 if(!insert(newNode)) { 00698 delete newNode; 00699 return false; 00700 } 00701 00702 // Then attend a balancing party 00703 while(!newNode->isRoot() && (newNode->getParent()->isRed())) { 00704 if(newNode->getParent()->isLeftChild()) { 00705 // If newNode is a left child, get its right 'uncle' 00706 Node *newNodesUncle = newNode->getParent()->getParent()->getRightChild(); 00707 if(newNodesUncle != 0 && newNodesUncle->isRed()) { 00708 // case 1 - change the colours 00709 newNode->getParent()->setBlack(); 00710 newNodesUncle->setBlack(); 00711 newNode->getParent()->getParent()->setRed(); 00712 // Move newNode up the tree 00713 newNode = newNode->getParent()->getParent(); 00714 } 00715 else { 00716 // newNodesUncle is a black node 00717 if(newNode->isRightChild()) { 00718 // and newNode is to the right 00719 // case 2 - move newNode up and rotate 00720 newNode = newNode->getParent(); 00721 RotateLeft(newNode); 00722 } 00723 // case 3 00724 newNode->getParent()->setBlack(); 00725 newNode->getParent()->getParent()->setRed(); 00726 RotateRight(newNode->getParent()->getParent()); 00727 } 00728 } 00729 else { 00730 // If newNode is a right child, get its left 'uncle' 00731 Node *newNodesUncle = newNode->getParent()->getParent()->getLeftChild(); 00732 if(newNodesUncle != 0 && newNodesUncle->isRed()) { 00733 // case 1 - change the colours 00734 newNode->getParent()->setBlack(); 00735 newNodesUncle->setBlack(); 00736 newNode->getParent()->getParent()->setRed(); 00737 // Move newNode up the tree 00738 newNode = newNode->getParent()->getParent(); 00739 } 00740 else { 00741 // newNodesUncle is a black node 00742 if(newNode->isLeftChild()) { 00743 // and newNode is to the left 00744 // case 2 - move newNode up and rotate 00745 newNode = newNode->getParent(); 00746 RotateRight(newNode); 00747 } 00748 // case 3 00749 newNode->getParent()->setBlack(); 00750 newNode->getParent()->getParent()->setRed(); 00751 RotateLeft(newNode->getParent()->getParent()); 00752 } 00753 } 00754 } 00755 // Color the root black 00756 mRoot->setBlack(); 00757 return true; 00758 } 00759 00760 // set. If the key already exist just replace the value 00761 // else insert a new element. 00762 void set(const KeyType &k, const ValueType &v) { 00763 Node *p = find(k); 00764 if(p) { 00765 p->setValue(v); 00766 } 00767 else 00768 insert(k,v); 00769 } 00770 00771 // Remove a node.Return true if the node could 00772 // be found (and was removed) in the tree. 00773 bool remove(const KeyType &k) { 00774 Node *p = find(k); 00775 if(p == 0) 00776 return false; 00777 00778 // Rotate p down to the left until it has no right child, will get there 00779 // sooner or later. 00780 while(p->getRightChild()) { 00781 // "Pull up my right child and let it knock me down to the left" 00782 RotateLeft(p); 00783 } 00784 // p now has no right child but might have a left child 00785 Node *left = p->getLeftChild(); 00786 00787 // Let p's parent point to p's child instead of point to p 00788 if(p->isLeftChild()) { 00789 p->getParent()->setLeftChild(left); 00790 } 00791 else if(p->isRightChild()) { 00792 p->getParent()->setRightChild(left); 00793 } 00794 else { 00795 // p has no parent => p is the root. 00796 // Let the left child be the new root. 00797 setRoot(left); 00798 } 00799 00800 // p is now gone from the tree in the sense that 00801 // no one is pointing at it. Let's get rid of it. 00802 delete p; 00803 00804 mSize--; 00805 return true; 00806 } 00807 00808 // Wipe out the entire tree. 00809 void clear() { 00810 ParentLastIterator i(getParentLastIterator()); 00811 00812 while(!i.atEnd()) { 00813 Node *p = i.getNode(); 00814 i++; // Increment it before it is deleted 00815 // else iterator will get quite confused. 00816 delete p; 00817 } 00818 mRoot = 0; 00819 mSize = 0; 00820 } 00821 00822 // Is the tree empty? 00823 bool isEmpty() const { 00824 return mRoot == 0; 00825 } 00826 00827 // Search for the node. 00828 // Returns 0 if node couldn't be found. 00829 Node *find(const KeyType &keyToFind) const { 00830 Node *pNode = mRoot; 00831 00832 while(pNode != 0) { 00833 KeyType key(pNode->getKey()); 00834 00835 if(keyToFind == key) { 00836 // Found it! Return it! Wheee! 00837 return pNode; 00838 } 00839 else if(keyToFind < key) { 00840 pNode = pNode->getLeftChild(); 00841 } 00842 else { // keyToFind > key 00843 pNode = pNode->getRightChild(); 00844 } 00845 } 00846 00847 return 0; 00848 } 00849 00850 // Get the root element. 0 if tree is empty. 00851 Node *getRoot() const { 00852 return mRoot; 00853 } 00854 00855 // Number of nodes in the tree. 00856 unsigned int size() const { 00857 return mSize; 00858 } 00859 00860 Iterator getIterator() { 00861 Iterator it(getRoot()); 00862 return it; 00863 } 00864 ParentFirstIterator getParentFirstIterator() { 00865 ParentFirstIterator it(getRoot()); 00866 return it; 00867 } 00868 ParentLastIterator getParentLastIterator() { 00869 ParentLastIterator it(getRoot()); 00870 return it; 00871 } 00872 ByLevelIterator getByLevelIterator() { 00873 ByLevelIterator it(getRoot(),size()); 00874 return it; 00875 } 00876 00877 // operator [] for access to elements 00878 AccessClass operator [](const KeyType &k) { 00879 return AccessClass(*this, k); 00880 } 00881 00882 private: 00883 00884 void setRoot(Node *newRoot) { 00885 mRoot = newRoot; 00886 if(mRoot != 0) 00887 mRoot->setParent(0); 00888 } 00889 00890 // insert a node into the tree without using any fancy balancing logic. 00891 // Returns false if that key already exist in the tree. 00892 bool insert(Node *newNode) { 00893 bool result = true; // Assume success 00894 00895 if(mRoot == 0) { 00896 setRoot(newNode); 00897 mSize = 1; 00898 } 00899 else { 00900 Node *pNode = mRoot; 00901 KeyType keyNew = newNode->getKey(); 00902 while(pNode) { 00903 KeyType key(pNode->getKey()); 00904 00905 if(keyNew == key) { 00906 result = false; 00907 pNode = 0; 00908 } 00909 else if(keyNew < key) { 00910 if(pNode->getLeftChild() == 0) { 00911 pNode->setLeftChild(newNode); 00912 pNode = 0; 00913 } 00914 else { 00915 pNode = pNode->getLeftChild(); 00916 } 00917 } 00918 else { 00919 // keyNew > key 00920 if(pNode->getRightChild() == 0) { 00921 pNode->setRightChild(newNode); 00922 pNode = 0; 00923 } 00924 else { 00925 pNode = pNode->getRightChild(); 00926 } 00927 } 00928 } 00929 00930 if(result) { 00931 mSize++; 00932 } 00933 } 00934 00935 return result; 00936 } 00937 00938 // Rotate left. 00939 // Pull up node's right child and let it knock node down to the left 00940 void RotateLeft(Node *p) { 00941 Node *right = p->getRightChild(); 00942 00943 p->setRightChild(right->getLeftChild()); 00944 00945 if(p->isLeftChild()) { 00946 p->getParent()->setLeftChild(right); 00947 } 00948 else if(p->isRightChild()) { 00949 p->getParent()->setRightChild(right); 00950 } 00951 else { 00952 setRoot(right); 00953 } 00954 right->setLeftChild(p); 00955 } 00956 00957 // Rotate right. 00958 // Pull up node's left child and let it knock node down to the right 00959 void RotateRight(Node *p) { 00960 Node *left = p->getLeftChild(); 00961 00962 p->setLeftChild(left->getRightChild()); 00963 00964 if(p->isLeftChild()) { 00965 p->getParent()->setLeftChild(left); 00966 } 00967 else if(p->isRightChild()) { 00968 p->getParent()->setRightChild(left); 00969 } 00970 else { 00971 setRoot(left); 00972 } 00973 left->setRightChild(p); 00974 } 00975 00976 Node *mRoot; // The top node. 0 if empty. 00977 unsigned int mSize; // Number of nodes in the tree 00978 }; 00979 00980 #endif // _SB_MAP_