5#ifndef __IRR_MAP_H_INCLUDED__
6#define __IRR_MAP_H_INCLUDED__
17template <
class KeyType,
class ValueType>
21 template <
class KeyTypeRB,
class ValueTypeRB>
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; }
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; }
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;
207 while(
n &&
n->getLeftChild())
208 n =
n->getLeftChild();
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();
356 while(
n &&
n->getLeftChild())
357 n =
n->getLeftChild();
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();
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();
658 return node->getValue();
673 map() : Root(0), Size(0) {}
703 if (
newNode->getParent()->isLeftChild())
710 newNode->getParent()->setBlack();
712 newNode->getParent()->getParent()->setRed();
727 newNode->getParent()->setBlack();
728 newNode->getParent()->getParent()->setRed();
729 rotateRight(
newNode->getParent()->getParent());
739 newNode->getParent()->setBlack();
741 newNode->getParent()->getParent()->setRed();
756 newNode->getParent()->setBlack();
757 newNode->getParent()->getParent()->setRed();
758 rotateLeft(
newNode->getParent()->getParent());
792 while(
p->getRightChild())
801 if (
p->isLeftChild())
802 p->getParent()->setLeftChild(
left);
804 else if (
p->isRightChild())
805 p->getParent()->setRightChild(
left);
841 while(
p->getRightChild())
850 if (
p->isLeftChild())
851 p->getParent()->setLeftChild(
left);
853 else if (
p->isRightChild())
854 p->getParent()->setRightChild(
left);
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);
Axis aligned bounding box in 3d dimensional space.
void operator=(const ValueType &value)
const Node * operator->()
const Node * getNode() const
ConstIterator(const ConstIterator &src)
void reset(bool atLowest=true)
ConstIterator(const Node *root)
ConstIterator(const Iterator &src)
ConstIterator & operator=(const ConstIterator &src)
Iterator(const Iterator &src)
Iterator & operator=(const Iterator &src)
void reset(bool atLowest=true)
ParentFirstIterator(Node *root)
ParentFirstIterator & operator=(const ParentFirstIterator &src)
ParentLastIterator & operator=(const ParentLastIterator &src)
ParentLastIterator(Node *root)
map template for associative arrays using a red-black tree
void clear()
Clear the entire tree.
_IRR_DEPRECATED_ bool isEmpty() const
ParentLastIterator getParentLastIterator() const
AccessClass operator[](const KeyType &k)
operator [] for access to elements
ParentFirstIterator getParentFirstIterator() const
void swap(map< KeyType, ValueType > &other)
Swap the content of this map container with the content of another map.
bool remove(const KeyType &k)
Removes a node from the tree and deletes it.
bool remove(Node *p)
Removes a node from the tree and deletes it.
Node * find(const KeyType &keyToFind) const
u32 size() const
Returns the number of nodes in the tree.
RBTree< KeyType, ValueType > Node
Iterator getIterator() const
Returns an iterator.
ConstIterator getConstIterator() const
Returns a Constiterator.
void set(const KeyType &k, const ValueType &v)
Replaces the value if the key already exists, otherwise inserts a new element.
Node * delink(const KeyType &k)
Removes a node from the tree and returns it.
bool insert(const KeyType &keyNew, const ValueType &v)
Inserts a new node into the tree.
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
#define _IRR_DEPRECATED_
Defines a deprecated macro which generates a warning at compile time.
#define _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX
Defines a small statement to work around a microsoft compiler bug.
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Everything in the Irrlicht Engine can be found in this namespace.
unsigned int u32
32 bit unsigned variable.