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