Irrlicht 3D Engine
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 
11 namespace irr
12 {
13 namespace core
14 {
15 
17 template <class KeyType, class ValueType>
18 class 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 
134  typedef RBTree<KeyType,ValueType> Node;
135  // We need the forwad declaration for the friend declaration
136  class ConstIterator;
137 
139  class Iterator
140  {
141  friend class ConstIterator;
142  public:
143 
144  Iterator() : Root(0), Cur(0) {}
145 
146  // Constructor(Node*)
147  Iterator(Node* root) : Root(root)
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 
191  Node* operator->()
192  {
193  return getNode();
194  }
195 
196  Node& operator*()
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 
340  const Node* operator->()
341  {
342  return getNode();
343  }
344 
345  const Node& operator*()
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 
463  Node* getNode()
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 
480  Node* operator -> ()
481  {
482  return getNode();
483  }
484 
485  Node& operator* ()
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 
563  Node* getNode()
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 
580  Node* operator -> ()
581  {
582  return getNode();
583  }
584 
585  Node& operator* ()
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
643  void operator=(const ValueType& value)
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 
784  Node* delink(const KeyType& k)
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  {
955  Iterator it(getRoot());
956  return it;
957  }
958 
961  {
962  Iterator it(getRoot());
963  return it;
964  }
965 
972  {
974  return it;
975  }
976 
983  {
985  return it;
986  }
987 
988  //------------------------------
989  // Public Operators
990  //------------------------------
991 
993 
994  AccessClass operator[](const KeyType& k)
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 
void operator--(int)
Definition: irrMap.h:186
ConstIterator(const ConstIterator &src)
Definition: irrMap.h:301
#define _IRR_DEPRECATED_
Defines a deprecated macro which generates a warning at compile time.
Definition: irrTypes.h:195
_IRR_DEPRECATED_ bool isEmpty() const
Definition: irrMap.h:896
ConstIterator & operator=(const ConstIterator &src)
Definition: irrMap.h:323
ParentLastIterator & operator=(const ParentLastIterator &src)
Definition: irrMap.h:568
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
ParentLastIterator getParentLastIterator() const
Definition: irrMap.h:982
map template for associative arrays using a red-black tree
Definition: irrMap.h:18
RBTree< KeyType, ValueType > Node
Definition: irrMap.h:134
ConstIterator(const Iterator &src)
Definition: irrMap.h:302
Parent First Iterator.
Definition: irrMap.h:441
void clear()
Clear the entire tree.
Definition: irrMap.h:872
Everything in the Irrlicht Engine can be found in this namespace.
Definition: aabbox3d.h:12
bool empty() const
Definition: irrMap.h:889
const Node * operator->()
Definition: irrMap.h:340
Normal Iterator.
Definition: irrMap.h:139
ParentFirstIterator & operator=(const ParentFirstIterator &src)
Definition: irrMap.h:468
Iterator getIterator() const
Returns an iterator.
Definition: irrMap.h:953
bool insert(const KeyType &keyNew, const ValueType &v)
Inserts a new node into the tree.
Definition: irrMap.h:689
Const Iterator.
Definition: irrMap.h:287
ConstIterator(const Node *root)
Definition: irrMap.h:295
Iterator(Node *root)
Definition: irrMap.h:147
unsigned int u32
32 bit unsigned variable.
Definition: irrTypes.h:58
Iterator(const Iterator &src)
Definition: irrMap.h:153
const Node * getNode() const
Definition: irrMap.h:318
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition: irrTypes.h:178
ConstIterator getConstIterator() const
Returns a Constiterator.
Definition: irrMap.h:960
const Node & operator*()
Definition: irrMap.h:345
Parent Last Iterator.
Definition: irrMap.h:541
u32 size() const
Returns the number of nodes in the tree.
Definition: irrMap.h:932
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition: irrMath.h:177
Iterator & operator=(const Iterator &src)
Definition: irrMap.h:174
#define _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX
Defines a small statement to work around a microsoft compiler bug.
Definition: irrTypes.h:207
Node * find(const KeyType &keyToFind) const
Definition: irrMap.h:904
void reset(bool atLowest=true)
Definition: irrMap.h:304
Node * delink(const KeyType &k)
Removes a node from the tree and returns it.
Definition: irrMap.h:784
void reset(bool atLowest=true)
Definition: irrMap.h:155
void operator=(const ValueType &value)
Definition: irrMap.h:643
AccessClass operator[](const KeyType &k)
operator [] for access to elements
Definition: irrMap.h:994
bool atEnd() const
Definition: irrMap.h:163
void operator++(int)
Definition: irrMap.h:181
CMatrix4< T > operator*(const T scalar, const CMatrix4< T > &mat)
Definition: matrix4.h:2228
Node * getNode() const
Definition: irrMap.h:169
ParentFirstIterator getParentFirstIterator() const
Definition: irrMap.h:971