5 #ifndef __IRR_MAP_H_INCLUDED__
6 #define __IRR_MAP_H_INCLUDED__
17 template <
class KeyType,
class ValueType>
21 template <
class KeyTypeRB,
class ValueTypeRB>
26 RBTree(
const KeyTypeRB& k,
const ValueTypeRB& v)
27 : LeftChild(0), RightChild(0), Parent(0), Key(k),
28 Value(v), IsRed(
true) {}
30 void setLeftChild(RBTree* p)
37 void setRightChild(RBTree* p)
44 void setParent(RBTree* p) { Parent=p; }
46 void setValue(
const ValueTypeRB& v) { Value = v; }
48 void setRed() { IsRed =
true; }
49 void setBlack() { IsRed =
false; }
51 RBTree* getLeftChild()
const {
return LeftChild; }
52 RBTree* getRightChild()
const {
return RightChild; }
53 RBTree* getParent()
const {
return Parent; }
55 ValueTypeRB getValue()
const
61 KeyTypeRB getKey()
const
73 bool isLeftChild()
const
76 return (Parent != 0) && (Parent->getLeftChild()==
this);
79 bool isRightChild()
const
82 return (Parent!=0) && (Parent->getRightChild()==
this);
88 return (LeftChild==0) && (RightChild==0);
91 unsigned int getLevel()
const
96 return getParent()->getLevel() + 1;
128 typedef RBTree<KeyType,ValueType>
Node;
199 while(n && n->getLeftChild())
200 n = n->getLeftChild();
206 while(n && n->getRightChild())
207 n = n->getRightChild();
217 if (Cur->getRightChild())
221 Cur = getMin(Cur->getRightChild());
223 else if (Cur->isLeftChild())
227 Cur = Cur->getParent();
236 while(Cur->isRightChild())
237 Cur = Cur->getParent();
238 Cur = Cur->getParent();
248 if (Cur->getLeftChild())
252 Cur = getMax(Cur->getLeftChild());
254 else if (Cur->isRightChild())
258 Cur = Cur->getParent();
268 while(Cur->isLeftChild())
269 Cur = Cur->getParent();
270 Cur = Cur->getParent();
353 if (Cur->getLeftChild())
355 Cur = Cur->getLeftChild();
357 else if (Cur->getRightChild())
360 Cur = Cur->getRightChild();
372 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
374 Cur = Cur->getParent()->getRightChild();
377 Cur = Cur->getParent();
447 while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
449 if (n->getLeftChild())
450 n = n->getLeftChild();
452 n = n->getRightChild();
468 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
470 Cur = getMin(Cur->getParent()->getRightChild());
473 Cur = Cur->getParent();
490 friend class map<KeyType, ValueType>;
510 return node->getValue();
515 AccessClass(
map& tree,
const KeyType& key) : Tree(tree), Key(key) {}
525 map() : Root(0), Size(0) {}
541 bool insert(
const KeyType& keyNew,
const ValueType& v)
553 while (!newNode->isRoot() && (newNode->getParent()->isRed()))
555 if (newNode->getParent()->isLeftChild())
558 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
559 if ( newNodesUncle!=0 && newNodesUncle->isRed())
562 newNode->getParent()->setBlack();
563 newNodesUncle->setBlack();
564 newNode->getParent()->getParent()->setRed();
566 newNode = newNode->getParent()->getParent();
571 if ( newNode->isRightChild())
575 newNode = newNode->getParent();
579 newNode->getParent()->setBlack();
580 newNode->getParent()->getParent()->setRed();
581 rotateRight(newNode->getParent()->getParent());
587 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
588 if ( newNodesUncle!=0 && newNodesUncle->isRed())
591 newNode->getParent()->setBlack();
592 newNodesUncle->setBlack();
593 newNode->getParent()->getParent()->setRed();
595 newNode = newNode->getParent()->getParent();
600 if (newNode->isLeftChild())
604 newNode = newNode->getParent();
605 rotateRight(newNode);
608 newNode->getParent()->setBlack();
609 newNode->getParent()->getParent()->setRed();
610 rotateLeft(newNode->getParent()->getParent());
623 void set(
const KeyType& k,
const ValueType& v)
644 while(p->getRightChild())
650 Node* left = p->getLeftChild();
653 if (p->isLeftChild())
654 p->getParent()->setLeftChild(left);
656 else if (p->isRightChild())
657 p->getParent()->setRightChild(left);
675 bool remove(
const KeyType& k)
686 while(p->getRightChild())
692 Node* left = p->getLeftChild();
695 if (p->isLeftChild())
696 p->getParent()->setLeftChild(left);
698 else if (p->isRightChild())
699 p->getParent()->setRightChild(left);
755 KeyType key(pNode->getKey());
757 if (keyToFind == key)
759 else if (keyToFind < key)
760 pNode = pNode->getLeftChild();
762 pNode = pNode->getRightChild();
842 explicit map(
const map& src);
843 map& operator = (
const map& src);
850 void setRoot(
Node* newRoot)
874 KeyType keyNew = newNode->getKey();
877 KeyType key(pNode->getKey());
884 else if (keyNew < key)
886 if (pNode->getLeftChild() == 0)
888 pNode->setLeftChild(newNode);
892 pNode = pNode->getLeftChild();
896 if (pNode->getRightChild()==0)
898 pNode->setRightChild(newNode);
903 pNode = pNode->getRightChild();
918 void rotateLeft(
Node* p)
920 Node* right = p->getRightChild();
922 p->setRightChild(right->getLeftChild());
924 if (p->isLeftChild())
925 p->getParent()->setLeftChild(right);
926 else if (p->isRightChild())
927 p->getParent()->setRightChild(right);
931 right->setLeftChild(p);
936 void rotateRight(
Node* p)
938 Node* left = p->getLeftChild();
940 p->setLeftChild(left->getRightChild());
942 if (p->isLeftChild())
943 p->getParent()->setLeftChild(left);
944 else if (p->isRightChild())
945 p->getParent()->setRightChild(left);
949 left->setRightChild(p);
962 #endif // __IRR_MAP_H_INCLUDED__