Irrlicht 3D Engine
 
Loading...
Searching...
No Matches
irrMap.h
Go to the documentation of this file.
1// Copyright (C) 2006-2012 by Kat'Oun
2// This file is part of the "Irrlicht Engine".
3// For conditions of distribution and use, see copyright notice in irrlicht.h
4
5#ifndef __IRR_MAP_H_INCLUDED__
6#define __IRR_MAP_H_INCLUDED__
7
8#include "irrTypes.h"
9#include "irrMath.h"
10
11namespace irr
12{
13namespace core
14{
15
17template <class KeyType, class ValueType>
18class map
19{
21 template <class KeyTypeRB, class ValueTypeRB>
22 class RBTree
23 {
24 public:
25
26 RBTree(const KeyTypeRB& k, const ValueTypeRB& v)
27 : LeftChild(0), RightChild(0), Parent(0), Key(k),
28 Value(v), IsRed(true) {}
29
30 void setLeftChild(RBTree* p)
31 {
32 LeftChild=p;
33 if (p)
34 p->setParent(this);
35 }
36
37 void setRightChild(RBTree* p)
38 {
39 RightChild=p;
40 if (p)
41 p->setParent(this);
42 }
43
44 void setParent(RBTree* p) { Parent=p; }
45
46 void setValue(const ValueTypeRB& v) { Value = v; }
47
48 void setRed() { IsRed = true; }
49 void setBlack() { IsRed = false; }
50
51 RBTree* getLeftChild() const { return LeftChild; }
52 RBTree* getRightChild() const { return RightChild; }
53 RBTree* getParent() const { return Parent; }
54
55 const ValueTypeRB& getValue() const
56 {
58 return Value;
59 }
60
61 ValueTypeRB& getValue()
62 {
64 return Value;
65 }
66
67 const KeyTypeRB& getKey() const
68 {
70 return Key;
71 }
72
73 bool isRoot() const
74 {
76 return Parent==0;
77 }
78
79 bool isLeftChild() const
80 {
82 return (Parent != 0) && (Parent->getLeftChild()==this);
83 }
84
85 bool isRightChild() const
86 {
88 return (Parent!=0) && (Parent->getRightChild()==this);
89 }
90
91 bool isLeaf() const
92 {
94 return (LeftChild==0) && (RightChild==0);
95 }
96
97 unsigned int getLevel() const
98 {
99 if (isRoot())
100 return 1;
101 else
102 return getParent()->getLevel() + 1;
103 }
104
105
106 bool isRed() const
107 {
109 return IsRed;
110 }
111
112 bool isBlack() const
113 {
115 return !IsRed;
116 }
117
118 private:
119 RBTree();
120
121 RBTree* LeftChild;
122 RBTree* RightChild;
123
124 RBTree* Parent;
125
126 KeyTypeRB Key;
127 ValueTypeRB Value;
128
129 bool IsRed;
130 }; // RBTree
131
132 public:
133
135 // We need the forwad declaration for the friend declaration
136 class ConstIterator;
137
140 {
141 friend class ConstIterator;
142 public:
143
144 Iterator() : Root(0), Cur(0) {}
145
146 // Constructor(Node*)
148 {
149 reset();
150 }
151
152 // Copy constructor
153 Iterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}
154
155 void reset(bool atLowest=true)
156 {
157 if (atLowest)
158 Cur = getMin(Root);
159 else
160 Cur = getMax(Root);
161 }
162
163 bool atEnd() const
164 {
166 return Cur==0;
167 }
168
169 Node* getNode() const
170 {
171 return Cur;
172 }
173
175 {
176 Root = src.Root;
177 Cur = src.Cur;
178 return (*this);
179 }
180
181 void operator++(int)
182 {
183 inc();
184 }
185
186 void operator--(int)
187 {
188 dec();
189 }
190
192 {
193 return getNode();
194 }
195
197 {
198 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
199
200 return *Cur;
201 }
202
203 private:
204
205 Node* getMin(Node* n) const
206 {
207 while(n && n->getLeftChild())
208 n = n->getLeftChild();
209 return n;
210 }
211
212 Node* getMax(Node* n) const
213 {
214 while(n && n->getRightChild())
215 n = n->getRightChild();
216 return n;
217 }
218
219 void inc()
220 {
221 // Already at end?
222 if (Cur==0)
223 return;
224
225 if (Cur->getRightChild())
226 {
227 // If current node has a right child, the next higher node is the
228 // node with lowest key beneath the right child.
229 Cur = getMin(Cur->getRightChild());
230 }
231 else if (Cur->isLeftChild())
232 {
233 // No right child? Well if current node is a left child then
234 // the next higher node is the parent
235 Cur = Cur->getParent();
236 }
237 else
238 {
239 // Current node neither is left child nor has a right child.
240 // Ie it is either right child or root
241 // The next higher node is the parent of the first non-right
242 // child (ie either a left child or the root) up in the
243 // hierarchy. Root's parent is 0.
244 while(Cur->isRightChild())
245 Cur = Cur->getParent();
246 Cur = Cur->getParent();
247 }
248 }
249
250 void dec()
251 {
252 // Already at end?
253 if (Cur==0)
254 return;
255
256 if (Cur->getLeftChild())
257 {
258 // If current node has a left child, the next lower node is the
259 // node with highest key beneath the left child.
260 Cur = getMax(Cur->getLeftChild());
261 }
262 else if (Cur->isRightChild())
263 {
264 // No left child? Well if current node is a right child then
265 // the next lower node is the parent
266 Cur = Cur->getParent();
267 }
268 else
269 {
270 // Current node neither is right child nor has a left child.
271 // Ie it is either left child or root
272 // The next higher node is the parent of the first non-left
273 // child (ie either a right child or the root) up in the
274 // hierarchy. Root's parent is 0.
275
276 while(Cur->isLeftChild())
277 Cur = Cur->getParent();
278 Cur = Cur->getParent();
279 }
280 }
281
282 Node* Root;
283 Node* Cur;
284 }; // Iterator
285
288 {
289 friend class Iterator;
290 public:
291
292 ConstIterator() : Root(0), Cur(0) {}
293
294 // Constructor(Node*)
295 ConstIterator(const Node* root) : Root(root)
296 {
297 reset();
298 }
299
300 // Copy constructor
301 ConstIterator(const ConstIterator& src) : Root(src.Root), Cur(src.Cur) {}
302 ConstIterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}
303
304 void reset(bool atLowest=true)
305 {
306 if (atLowest)
307 Cur = getMin(Root);
308 else
309 Cur = getMax(Root);
310 }
311
312 bool atEnd() const
313 {
315 return Cur==0;
316 }
317
318 const Node* getNode() const
319 {
320 return Cur;
321 }
322
324 {
325 Root = src.Root;
326 Cur = src.Cur;
327 return (*this);
328 }
329
330 void operator++(int)
331 {
332 inc();
333 }
334
335 void operator--(int)
336 {
337 dec();
338 }
339
341 {
342 return getNode();
343 }
344
346 {
347 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
348
349 return *Cur;
350 }
351
352 private:
353
354 const Node* getMin(const Node* n) const
355 {
356 while(n && n->getLeftChild())
357 n = n->getLeftChild();
358 return n;
359 }
360
361 const Node* getMax(const Node* n) const
362 {
363 while(n && n->getRightChild())
364 n = n->getRightChild();
365 return n;
366 }
367
368 void inc()
369 {
370 // Already at end?
371 if (Cur==0)
372 return;
373
374 if (Cur->getRightChild())
375 {
376 // If current node has a right child, the next higher node is the
377 // node with lowest key beneath the right child.
378 Cur = getMin(Cur->getRightChild());
379 }
380 else if (Cur->isLeftChild())
381 {
382 // No right child? Well if current node is a left child then
383 // the next higher node is the parent
384 Cur = Cur->getParent();
385 }
386 else
387 {
388 // Current node neither is left child nor has a right child.
389 // Ie it is either right child or root
390 // The next higher node is the parent of the first non-right
391 // child (ie either a left child or the root) up in the
392 // hierarchy. Root's parent is 0.
393 while(Cur->isRightChild())
394 Cur = Cur->getParent();
395 Cur = Cur->getParent();
396 }
397 }
398
399 void dec()
400 {
401 // Already at end?
402 if (Cur==0)
403 return;
404
405 if (Cur->getLeftChild())
406 {
407 // If current node has a left child, the next lower node is the
408 // node with highest key beneath the left child.
409 Cur = getMax(Cur->getLeftChild());
410 }
411 else if (Cur->isRightChild())
412 {
413 // No left child? Well if current node is a right child then
414 // the next lower node is the parent
415 Cur = Cur->getParent();
416 }
417 else
418 {
419 // Current node neither is right child nor has a left child.
420 // Ie it is either left child or root
421 // The next higher node is the parent of the first non-left
422 // child (ie either a right child or the root) up in the
423 // hierarchy. Root's parent is 0.
424
425 while(Cur->isLeftChild())
426 Cur = Cur->getParent();
427 Cur = Cur->getParent();
428 }
429 }
430
431 const Node* Root;
432 const Node* Cur;
433 }; // ConstIterator
434
435
437
442 {
443 public:
444
445 ParentFirstIterator() : Root(0), Cur(0) {}
446
447 explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)
448 {
449 reset();
450 }
451
452 void reset()
453 {
454 Cur = Root;
455 }
456
457 bool atEnd() const
458 {
460 return Cur==0;
461 }
462
464 {
465 return Cur;
466 }
467
469 {
470 Root = src.Root;
471 Cur = src.Cur;
472 return (*this);
473 }
474
475 void operator++(int)
476 {
477 inc();
478 }
479
481 {
482 return getNode();
483 }
484
486 {
487 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
488
489 return *getNode();
490 }
491
492 private:
493
494 void inc()
495 {
496 // Already at end?
497 if (Cur==0)
498 return;
499
500 // First we try down to the left
501 if (Cur->getLeftChild())
502 {
503 Cur = Cur->getLeftChild();
504 }
505 else if (Cur->getRightChild())
506 {
507 // No left child? The we go down to the right.
508 Cur = Cur->getRightChild();
509 }
510 else
511 {
512 // No children? Move up in the hierarcy until
513 // we either reach 0 (and are finished) or
514 // find a right uncle.
515 while (Cur!=0)
516 {
517 // But if parent is left child and has a right "uncle" the parent
518 // has already been processed but the uncle hasn't. Move to
519 // the uncle.
520 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
521 {
522 Cur = Cur->getParent()->getRightChild();
523 return;
524 }
525 Cur = Cur->getParent();
526 }
527 }
528 }
529
530 Node* Root;
531 Node* Cur;
532
533 }; // ParentFirstIterator
534
535
537
542 {
543 public:
544
545 ParentLastIterator() : Root(0), Cur(0) {}
546
547 explicit ParentLastIterator(Node* root) : Root(root), Cur(0)
548 {
549 reset();
550 }
551
552 void reset()
553 {
554 Cur = getMin(Root);
555 }
556
557 bool atEnd() const
558 {
560 return Cur==0;
561 }
562
564 {
565 return Cur;
566 }
567
569 {
570 Root = src.Root;
571 Cur = src.Cur;
572 return (*this);
573 }
574
575 void operator++(int)
576 {
577 inc();
578 }
579
581 {
582 return getNode();
583 }
584
586 {
587 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
588
589 return *getNode();
590 }
591 private:
592
593 Node* getMin(Node* n)
594 {
595 while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
596 {
597 if (n->getLeftChild())
598 n = n->getLeftChild();
599 else
600 n = n->getRightChild();
601 }
602 return n;
603 }
604
605 void inc()
606 {
607 // Already at end?
608 if (Cur==0)
609 return;
610
611 // Note: Starting point is the node as far down to the left as possible.
612
613 // If current node has an uncle to the right, go to the
614 // node as far down to the left from the uncle as possible
615 // else just go up a level to the parent.
616 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
617 {
618 Cur = getMin(Cur->getParent()->getRightChild());
619 }
620 else
621 Cur = Cur->getParent();
622 }
623
624 Node* Root;
625 Node* Cur;
626 }; // ParentLastIterator
627
628
629 // AccessClass is a temporary class used with the [] operator.
630 // It makes it possible to have different behavior in situations like:
631 // myTree["Foo"] = 32;
632 // If "Foo" already exists update its value else insert a new element.
633 // int i = myTree["Foo"]
634 // If "Foo" exists return its value.
636 {
637 // Let map be the only one who can instantiate this class.
638 friend class map<KeyType, ValueType>;
639
640 public:
641
642 // Assignment operator. Handles the myTree["Foo"] = 32; situation
644 {
645 // Just use the Set method, it handles already exist/not exist situation
646 Tree.set(Key,value);
647 }
648
649 // ValueType operator
650 operator ValueType()
651 {
652 Node* node = Tree.find(Key);
653
654 // Not found
655 _IRR_DEBUG_BREAK_IF(node==0) // access violation
656
658 return node->getValue();
659 }
660
661 private:
662
663 AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}
664
665 AccessClass();
666
667 map& Tree;
668 const KeyType& Key;
669 }; // AccessClass
670
671
672 // Constructor.
673 map() : Root(0), Size(0) {}
674
675 // Destructor
677 {
678 clear();
679 }
680
681 //------------------------------
682 // Public Commands
683 //------------------------------
684
686
689 bool insert(const KeyType& keyNew, const ValueType& v)
690 {
691 // First insert node the "usual" way (no fancy balance logic yet)
692 Node* newNode = new Node(keyNew,v);
693 if (!insert(newNode))
694 {
695 delete newNode;
697 return false;
698 }
699
700 // Then attend a balancing party
701 while (!newNode->isRoot() && (newNode->getParent()->isRed()))
702 {
703 if (newNode->getParent()->isLeftChild())
704 {
705 // If newNode is a left child, get its right 'uncle'
706 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
707 if ( newNodesUncle!=0 && newNodesUncle->isRed())
708 {
709 // case 1 - change the colors
710 newNode->getParent()->setBlack();
711 newNodesUncle->setBlack();
712 newNode->getParent()->getParent()->setRed();
713 // Move newNode up the tree
714 newNode = newNode->getParent()->getParent();
715 }
716 else
717 {
718 // newNodesUncle is a black node
719 if ( newNode->isRightChild())
720 {
721 // and newNode is to the right
722 // case 2 - move newNode up and rotate
723 newNode = newNode->getParent();
724 rotateLeft(newNode);
725 }
726 // case 3
727 newNode->getParent()->setBlack();
728 newNode->getParent()->getParent()->setRed();
729 rotateRight(newNode->getParent()->getParent());
730 }
731 }
732 else
733 {
734 // If newNode is a right child, get its left 'uncle'
735 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
736 if ( newNodesUncle!=0 && newNodesUncle->isRed())
737 {
738 // case 1 - change the colors
739 newNode->getParent()->setBlack();
740 newNodesUncle->setBlack();
741 newNode->getParent()->getParent()->setRed();
742 // Move newNode up the tree
743 newNode = newNode->getParent()->getParent();
744 }
745 else
746 {
747 // newNodesUncle is a black node
748 if (newNode->isLeftChild())
749 {
750 // and newNode is to the left
751 // case 2 - move newNode up and rotate
752 newNode = newNode->getParent();
753 rotateRight(newNode);
754 }
755 // case 3
756 newNode->getParent()->setBlack();
757 newNode->getParent()->getParent()->setRed();
758 rotateLeft(newNode->getParent()->getParent());
759 }
760
761 }
762 }
763 // Color the root black
764 Root->setBlack();
765 return true;
766 }
767
769
771 void set(const KeyType& k, const ValueType& v)
772 {
773 Node* p = find(k);
774 if (p)
775 p->setValue(v);
776 else
777 insert(k,v);
778 }
779
781
785 {
786 Node* p = find(k);
787 if (p == 0)
788 return 0;
789
790 // Rotate p down to the left until it has no right child, will get there
791 // sooner or later.
792 while(p->getRightChild())
793 {
794 // "Pull up my right child and let it knock me down to the left"
795 rotateLeft(p);
796 }
797 // p now has no right child but might have a left child
798 Node* left = p->getLeftChild();
799
800 // Let p's parent point to p's child instead of point to p
801 if (p->isLeftChild())
802 p->getParent()->setLeftChild(left);
803
804 else if (p->isRightChild())
805 p->getParent()->setRightChild(left);
806
807 else
808 {
809 // p has no parent => p is the root.
810 // Let the left child be the new root.
811 setRoot(left);
812 }
813
814 // p is now gone from the tree in the sense that
815 // no one is pointing at it, so return it.
816
817 --Size;
818 return p;
819 }
820
822
823 bool remove(const KeyType& k)
824 {
825 Node* p = find(k);
826 return remove(p);
827 }
828
830
831 bool remove(Node* p)
832 {
833 if (p == 0)
834 {
836 return false;
837 }
838
839 // Rotate p down to the left until it has no right child, will get there
840 // sooner or later.
841 while(p->getRightChild())
842 {
843 // "Pull up my right child and let it knock me down to the left"
844 rotateLeft(p);
845 }
846 // p now has no right child but might have a left child
847 Node* left = p->getLeftChild();
848
849 // Let p's parent point to p's child instead of point to p
850 if (p->isLeftChild())
851 p->getParent()->setLeftChild(left);
852
853 else if (p->isRightChild())
854 p->getParent()->setRightChild(left);
855
856 else
857 {
858 // p has no parent => p is the root.
859 // Let the left child be the new root.
860 setRoot(left);
861 }
862
863 // p is now gone from the tree in the sense that
864 // no one is pointing at it. Let's get rid of it.
865 delete p;
866
867 --Size;
868 return true;
869 }
870
872 void clear()
873 {
875
876 while(!i.atEnd())
877 {
878 Node* p = i.getNode();
879 i++; // Increment it before it is deleted
880 // else iterator will get quite confused.
881 delete p;
882 }
883 Root = 0;
884 Size= 0;
885 }
886
889 bool empty() const
890 {
892 return Root == 0;
893 }
894
897 {
898 return empty();
899 }
900
904 Node* find(const KeyType& keyToFind) const
905 {
906 Node* pNode = Root;
907
908 while(pNode!=0)
909 {
910 const KeyType& key=pNode->getKey();
911
912 if (keyToFind == key)
913 return pNode;
914 else if (keyToFind < key)
915 pNode = pNode->getLeftChild();
916 else //keyToFind > key
917 pNode = pNode->getRightChild();
918 }
919
920 return 0;
921 }
922
926 Node* getRoot() const
927 {
928 return Root;
929 }
930
932 u32 size() const
933 {
934 return Size;
935 }
936
938
943 {
944 core::swap(Root, other.Root);
945 core::swap(Size, other.Size);
946 }
947
948 //------------------------------
949 // Public Iterators
950 //------------------------------
951
954 {
956 return it;
957 }
958
961 {
963 return it;
964 }
965
976
987
988 //------------------------------
989 // Public Operators
990 //------------------------------
991
993
995 {
996 return AccessClass(*this, k);
997 }
998 private:
999
1000 //------------------------------
1001 // Disabled methods
1002 //------------------------------
1003 // Copy constructor and assignment operator deliberately
1004 // defined but not implemented. The tree should never be
1005 // copied, pass along references to it instead.
1006 explicit map(const map& src);
1007 map& operator = (const map& src);
1008
1010
1014 void setRoot(Node* newRoot)
1015 {
1016 Root = newRoot;
1017 if (Root != 0)
1018 {
1019 Root->setParent(0);
1020 Root->setBlack();
1021 }
1022 }
1023
1025
1026 bool insert(Node* newNode)
1027 {
1028 bool result=true; // Assume success
1029
1030 if (Root==0)
1031 {
1032 setRoot(newNode);
1033 Size = 1;
1034 }
1035 else
1036 {
1037 Node* pNode = Root;
1038 const KeyType& keyNew = newNode->getKey();
1039 while (pNode)
1040 {
1041 const KeyType& key=pNode->getKey();
1042
1043 if (keyNew == key)
1044 {
1045 result = false;
1046 pNode = 0;
1047 }
1048 else if (keyNew < key)
1049 {
1050 if (pNode->getLeftChild() == 0)
1051 {
1052 pNode->setLeftChild(newNode);
1053 pNode = 0;
1054 }
1055 else
1056 pNode = pNode->getLeftChild();
1057 }
1058 else // keyNew > key
1059 {
1060 if (pNode->getRightChild()==0)
1061 {
1062 pNode->setRightChild(newNode);
1063 pNode = 0;
1064 }
1065 else
1066 {
1067 pNode = pNode->getRightChild();
1068 }
1069 }
1070 }
1071
1072 if (result)
1073 ++Size;
1074 }
1075
1077 return result;
1078 }
1079
1082 void rotateLeft(Node* p)
1083 {
1084 Node* right = p->getRightChild();
1085
1086 p->setRightChild(right->getLeftChild());
1087
1088 if (p->isLeftChild())
1089 p->getParent()->setLeftChild(right);
1090 else if (p->isRightChild())
1091 p->getParent()->setRightChild(right);
1092 else
1093 setRoot(right);
1094
1095 right->setLeftChild(p);
1096 }
1097
1100 void rotateRight(Node* p)
1101 {
1102 Node* left = p->getLeftChild();
1103
1104 p->setLeftChild(left->getRightChild());
1105
1106 if (p->isLeftChild())
1107 p->getParent()->setLeftChild(left);
1108 else if (p->isRightChild())
1109 p->getParent()->setRightChild(left);
1110 else
1111 setRoot(left);
1112
1113 left->setRightChild(p);
1114 }
1115
1116 //------------------------------
1117 // Private Members
1118 //------------------------------
1119 Node* Root; // The top node. 0 if empty.
1120 u32 Size; // Number of nodes in the tree
1121};
1122
1123} // end namespace core
1124} // end namespace irr
1125
1126#endif // __IRR_MAP_H_INCLUDED__
1127
Axis aligned bounding box in 3d dimensional space.
Definition aabbox3d.h:22
void operator=(const ValueType &value)
Definition irrMap.h:643
const Node * operator->()
Definition irrMap.h:340
const Node & operator*()
Definition irrMap.h:345
const Node * getNode() const
Definition irrMap.h:318
ConstIterator(const ConstIterator &src)
Definition irrMap.h:301
void reset(bool atLowest=true)
Definition irrMap.h:304
ConstIterator(const Node *root)
Definition irrMap.h:295
ConstIterator(const Iterator &src)
Definition irrMap.h:302
ConstIterator & operator=(const ConstIterator &src)
Definition irrMap.h:323
Normal Iterator.
Definition irrMap.h:140
Iterator(Node *root)
Definition irrMap.h:147
Iterator(const Iterator &src)
Definition irrMap.h:153
Iterator & operator=(const Iterator &src)
Definition irrMap.h:174
bool atEnd() const
Definition irrMap.h:163
void reset(bool atLowest=true)
Definition irrMap.h:155
Node * getNode() const
Definition irrMap.h:169
Parent First Iterator.
Definition irrMap.h:442
ParentFirstIterator & operator=(const ParentFirstIterator &src)
Definition irrMap.h:468
Parent Last Iterator.
Definition irrMap.h:542
ParentLastIterator & operator=(const ParentLastIterator &src)
Definition irrMap.h:568
map template for associative arrays using a red-black tree
Definition irrMap.h:19
void clear()
Clear the entire tree.
Definition irrMap.h:872
bool empty() const
Definition irrMap.h:889
_IRR_DEPRECATED_ bool isEmpty() const
Definition irrMap.h:896
ParentLastIterator getParentLastIterator() const
Definition irrMap.h:982
AccessClass operator[](const KeyType &k)
operator [] for access to elements
Definition irrMap.h:994
ParentFirstIterator getParentFirstIterator() const
Definition irrMap.h:971
void swap(map< KeyType, ValueType > &other)
Swap the content of this map container with the content of another map.
Definition irrMap.h:942
Node * getRoot() const
Definition irrMap.h:926
bool remove(const KeyType &k)
Removes a node from the tree and deletes it.
Definition irrMap.h:823
bool remove(Node *p)
Removes a node from the tree and deletes it.
Definition irrMap.h:831
Node * find(const KeyType &keyToFind) const
Definition irrMap.h:904
u32 size() const
Returns the number of nodes in the tree.
Definition irrMap.h:932
RBTree< KeyType, ValueType > Node
Definition irrMap.h:134
Iterator getIterator() const
Returns an iterator.
Definition irrMap.h:953
ConstIterator getConstIterator() const
Returns a Constiterator.
Definition irrMap.h:960
void set(const KeyType &k, const ValueType &v)
Replaces the value if the key already exists, otherwise inserts a new element.
Definition irrMap.h:771
Node * delink(const KeyType &k)
Removes a node from the tree and returns it.
Definition irrMap.h:784
bool insert(const KeyType &keyNew, const ValueType &v)
Inserts a new node into the tree.
Definition irrMap.h:689
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition irrTypes.h:178
#define _IRR_DEPRECATED_
Defines a deprecated macro which generates a warning at compile time.
Definition irrTypes.h:195
#define _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX
Defines a small statement to work around a microsoft compiler bug.
Definition irrTypes.h:207
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition irrMath.h:177
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
unsigned int u32
32 bit unsigned variable.
Definition irrTypes.h:58