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 const ValueTypeRB& getValue()
const 61 ValueTypeRB& getValue()
67 const KeyTypeRB& getKey()
const 79 bool isLeftChild()
const 82 return (Parent != 0) && (Parent->getLeftChild()==
this);
85 bool isRightChild()
const 88 return (Parent!=0) && (Parent->getRightChild()==
this);
94 return (LeftChild==0) && (RightChild==0);
97 unsigned int getLevel()
const 102 return getParent()->getLevel() + 1;
134 typedef RBTree<KeyType,ValueType>
Node;
205 Node* getMin(Node* n)
const 207 while(n && n->getLeftChild())
208 n = n->getLeftChild();
212 Node* getMax(Node* n)
const 214 while(n && n->getRightChild())
215 n = n->getRightChild();
225 if (Cur->getRightChild())
229 Cur = getMin(Cur->getRightChild());
231 else if (Cur->isLeftChild())
235 Cur = Cur->getParent();
244 while(Cur->isRightChild())
245 Cur = Cur->getParent();
246 Cur = Cur->getParent();
256 if (Cur->getLeftChild())
260 Cur = getMax(Cur->getLeftChild());
262 else if (Cur->isRightChild())
266 Cur = Cur->getParent();
276 while(Cur->isLeftChild())
277 Cur = Cur->getParent();
278 Cur = Cur->getParent();
354 const Node* getMin(
const Node* n)
const 356 while(n && n->getLeftChild())
357 n = n->getLeftChild();
361 const Node* getMax(
const Node* n)
const 363 while(n && n->getRightChild())
364 n = n->getRightChild();
374 if (Cur->getRightChild())
378 Cur = getMin(Cur->getRightChild());
380 else if (Cur->isLeftChild())
384 Cur = Cur->getParent();
393 while(Cur->isRightChild())
394 Cur = Cur->getParent();
395 Cur = Cur->getParent();
405 if (Cur->getLeftChild())
409 Cur = getMax(Cur->getLeftChild());
411 else if (Cur->isRightChild())
415 Cur = Cur->getParent();
425 while(Cur->isLeftChild())
426 Cur = Cur->getParent();
427 Cur = Cur->getParent();
501 if (Cur->getLeftChild())
503 Cur = Cur->getLeftChild();
505 else if (Cur->getRightChild())
508 Cur = Cur->getRightChild();
520 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
522 Cur = Cur->getParent()->getRightChild();
525 Cur = Cur->getParent();
593 Node* getMin(Node* n)
595 while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
597 if (n->getLeftChild())
598 n = n->getLeftChild();
600 n = n->getRightChild();
616 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
618 Cur = getMin(Cur->getParent()->getRightChild());
621 Cur = Cur->getParent();
638 friend class map<KeyType, ValueType>;
652 Node* node = Tree.find(Key);
658 return node->getValue();
663 AccessClass(
map& tree,
const KeyType& key) : Tree(tree), Key(key) {}
673 map() : Root(0), Size(0) {}
689 bool insert(
const KeyType& keyNew,
const ValueType& v)
692 Node* newNode =
new Node(keyNew,v);
701 while (!newNode->isRoot() && (newNode->getParent()->isRed()))
703 if (newNode->getParent()->isLeftChild())
706 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
707 if ( newNodesUncle!=0 && newNodesUncle->isRed())
710 newNode->getParent()->setBlack();
711 newNodesUncle->setBlack();
712 newNode->getParent()->getParent()->setRed();
714 newNode = newNode->getParent()->getParent();
719 if ( newNode->isRightChild())
723 newNode = newNode->getParent();
727 newNode->getParent()->setBlack();
728 newNode->getParent()->getParent()->setRed();
729 rotateRight(newNode->getParent()->getParent());
735 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
736 if ( newNodesUncle!=0 && newNodesUncle->isRed())
739 newNode->getParent()->setBlack();
740 newNodesUncle->setBlack();
741 newNode->getParent()->getParent()->setRed();
743 newNode = newNode->getParent()->getParent();
748 if (newNode->isLeftChild())
752 newNode = newNode->getParent();
753 rotateRight(newNode);
756 newNode->getParent()->setBlack();
757 newNode->getParent()->getParent()->setRed();
758 rotateLeft(newNode->getParent()->getParent());
771 void set(
const KeyType& k,
const ValueType& v)
792 while(p->getRightChild())
798 Node* left = p->getLeftChild();
801 if (p->isLeftChild())
802 p->getParent()->setLeftChild(left);
804 else if (p->isRightChild())
805 p->getParent()->setRightChild(left);
823 bool remove(
const KeyType& k)
841 while(p->getRightChild())
847 Node* left = p->getLeftChild();
850 if (p->isLeftChild())
851 p->getParent()->setLeftChild(left);
853 else if (p->isRightChild())
854 p->getParent()->setRightChild(left);
904 Node*
find(
const KeyType& keyToFind)
const 910 const KeyType& key=pNode->getKey();
912 if (keyToFind == key)
914 else if (keyToFind < key)
915 pNode = pNode->getLeftChild();
917 pNode = pNode->getRightChild();
1006 explicit map(
const map& src);
1007 map& operator = (
const map& src);
1014 void setRoot(Node* newRoot)
1026 bool insert(Node* newNode)
1038 const KeyType& keyNew = newNode->getKey();
1041 const KeyType& key=pNode->getKey();
1048 else if (keyNew < key)
1050 if (pNode->getLeftChild() == 0)
1052 pNode->setLeftChild(newNode);
1056 pNode = pNode->getLeftChild();
1060 if (pNode->getRightChild()==0)
1062 pNode->setRightChild(newNode);
1067 pNode = pNode->getRightChild();
1082 void rotateLeft(Node* p)
1084 Node* right = p->getRightChild();
1086 p->setRightChild(right->getLeftChild());
1088 if (p->isLeftChild())
1089 p->getParent()->setLeftChild(right);
1090 else if (p->isRightChild())
1091 p->getParent()->setRightChild(right);
1095 right->setLeftChild(p);
1100 void rotateRight(Node* p)
1102 Node* left = p->getLeftChild();
1104 p->setLeftChild(left->getRightChild());
1106 if (p->isLeftChild())
1107 p->getParent()->setLeftChild(left);
1108 else if (p->isRightChild())
1109 p->getParent()->setRightChild(left);
1113 left->setRightChild(p);
1126 #endif // __IRR_MAP_H_INCLUDED__
ConstIterator(const ConstIterator &src)
#define _IRR_DEPRECATED_
Defines a deprecated macro which generates a warning at compile time.
_IRR_DEPRECATED_ bool isEmpty() const
ConstIterator & operator=(const ConstIterator &src)
ParentLastIterator & operator=(const ParentLastIterator &src)
void swap(map< KeyType, ValueType > &other)
Swap the content of this map container with the content of another map.
ParentLastIterator getParentLastIterator() const
map template for associative arrays using a red-black tree
RBTree< KeyType, ValueType > Node
ConstIterator(const Iterator &src)
void clear()
Clear the entire tree.
Everything in the Irrlicht Engine can be found in this namespace.
const Node * operator->()
ParentFirstIterator & operator=(const ParentFirstIterator &src)
Iterator getIterator() const
Returns an iterator.
bool insert(const KeyType &keyNew, const ValueType &v)
Inserts a new node into the tree.
ConstIterator(const Node *root)
unsigned int u32
32 bit unsigned variable.
Iterator(const Iterator &src)
ParentFirstIterator(Node *root)
ParentLastIterator(Node *root)
const Node * getNode() const
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
ConstIterator getConstIterator() const
Returns a Constiterator.
u32 size() const
Returns the number of nodes in the tree.
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Iterator & operator=(const Iterator &src)
#define _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX
Defines a small statement to work around a microsoft compiler bug.
Node * find(const KeyType &keyToFind) const
void reset(bool atLowest=true)
Node * delink(const KeyType &k)
Removes a node from the tree and returns it.
void reset(bool atLowest=true)
void operator=(const ValueType &value)
AccessClass operator[](const KeyType &k)
operator [] for access to elements
CMatrix4< T > operator*(const T scalar, const CMatrix4< T > &mat)
ParentFirstIterator getParentFirstIterator() const