Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials
irrMap.h
Go to the documentation of this file.
1 // Copyright (C) 2006-2010 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  ValueTypeRB getValue() const
56  {
58  return Value;
59  }
60 
61  KeyTypeRB getKey() const
62  {
64  return Key;
65  }
66 
67  bool isRoot() const
68  {
70  return Parent==0;
71  }
72 
73  bool isLeftChild() const
74  {
76  return (Parent != 0) && (Parent->getLeftChild()==this);
77  }
78 
79  bool isRightChild() const
80  {
82  return (Parent!=0) && (Parent->getRightChild()==this);
83  }
84 
85  bool isLeaf() const
86  {
88  return (LeftChild==0) && (RightChild==0);
89  }
90 
91  unsigned int getLevel() const
92  {
93  if (isRoot())
94  return 1;
95  else
96  return getParent()->getLevel() + 1;
97  }
98 
99 
100  bool isRed() const
101  {
103  return IsRed;
104  }
105 
106  bool isBlack() const
107  {
109  return !IsRed;
110  }
111 
112  private:
113  RBTree();
114 
115  RBTree* LeftChild;
116  RBTree* RightChild;
117 
118  RBTree* Parent;
119 
120  KeyTypeRB Key;
121  ValueTypeRB Value;
122 
123  bool IsRed;
124  }; // RBTree
125 
126  public:
127 
128  typedef RBTree<KeyType,ValueType> Node;
129 
131  class Iterator
132  {
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  {
157  return Cur==0;
158  }
159 
161  {
162  return Cur;
163  }
164 
166  {
167  Root = src.Root;
168  Cur = src.Cur;
169  return (*this);
170  }
171 
172  void operator++(int)
173  {
174  inc();
175  }
176 
177  void operator--(int)
178  {
179  dec();
180  }
181 
182 
184  {
185  return getNode();
186  }
187 
189  {
190  _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
191 
192  return *Cur;
193  }
194 
195  private:
196 
197  Node* getMin(Node* n)
198  {
199  while(n && n->getLeftChild())
200  n = n->getLeftChild();
201  return n;
202  }
203 
204  Node* getMax(Node* n)
205  {
206  while(n && n->getRightChild())
207  n = n->getRightChild();
208  return n;
209  }
210 
211  void inc()
212  {
213  // Already at end?
214  if (Cur==0)
215  return;
216 
217  if (Cur->getRightChild())
218  {
219  // If current node has a right child, the next higher node is the
220  // node with lowest key beneath the right child.
221  Cur = getMin(Cur->getRightChild());
222  }
223  else if (Cur->isLeftChild())
224  {
225  // No right child? Well if current node is a left child then
226  // the next higher node is the parent
227  Cur = Cur->getParent();
228  }
229  else
230  {
231  // Current node neither is left child nor has a right child.
232  // Ie it is either right child or root
233  // The next higher node is the parent of the first non-right
234  // child (ie either a left child or the root) up in the
235  // hierarchy. Root's parent is 0.
236  while(Cur->isRightChild())
237  Cur = Cur->getParent();
238  Cur = Cur->getParent();
239  }
240  }
241 
242  void dec()
243  {
244  // Already at end?
245  if (Cur==0)
246  return;
247 
248  if (Cur->getLeftChild())
249  {
250  // If current node has a left child, the next lower node is the
251  // node with highest key beneath the left child.
252  Cur = getMax(Cur->getLeftChild());
253  }
254  else if (Cur->isRightChild())
255  {
256  // No left child? Well if current node is a right child then
257  // the next lower node is the parent
258  Cur = Cur->getParent();
259  }
260  else
261  {
262  // Current node neither is right child nor has a left child.
263  // Ie it is either left child or root
264  // The next higher node is the parent of the first non-left
265  // child (ie either a right child or the root) up in the
266  // hierarchy. Root's parent is 0.
267 
268  while(Cur->isLeftChild())
269  Cur = Cur->getParent();
270  Cur = Cur->getParent();
271  }
272  }
273 
274  Node* Root;
275  Node* Cur;
276  }; // Iterator
277 
278 
279 
281 
286  {
287  public:
288 
289 
290  ParentFirstIterator() : Root(0), Cur(0)
291  {
292  }
293 
294 
295  explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)
296  {
297  reset();
298  }
299 
300  void reset()
301  {
302  Cur = Root;
303  }
304 
305 
306  bool atEnd() const
307  {
309  return Cur==0;
310  }
311 
313  {
314  return Cur;
315  }
316 
317 
319  {
320  Root = src.Root;
321  Cur = src.Cur;
322  return (*this);
323  }
324 
325 
326  void operator++(int)
327  {
328  inc();
329  }
330 
331 
333  {
334  return getNode();
335  }
336 
338  {
339  _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
340 
341  return *getNode();
342  }
343 
344  private:
345 
346  void inc()
347  {
348  // Already at end?
349  if (Cur==0)
350  return;
351 
352  // First we try down to the left
353  if (Cur->getLeftChild())
354  {
355  Cur = Cur->getLeftChild();
356  }
357  else if (Cur->getRightChild())
358  {
359  // No left child? The we go down to the right.
360  Cur = Cur->getRightChild();
361  }
362  else
363  {
364  // No children? Move up in the hierarcy until
365  // we either reach 0 (and are finished) or
366  // find a right uncle.
367  while (Cur!=0)
368  {
369  // But if parent is left child and has a right "uncle" the parent
370  // has already been processed but the uncle hasn't. Move to
371  // the uncle.
372  if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
373  {
374  Cur = Cur->getParent()->getRightChild();
375  return;
376  }
377  Cur = Cur->getParent();
378  }
379  }
380  }
381 
382  Node* Root;
383  Node* Cur;
384 
385  }; // ParentFirstIterator
386 
387 
389 
394  {
395  public:
396 
397  ParentLastIterator() : Root(0), Cur(0) {}
398 
399  explicit ParentLastIterator(Node* root) : Root(root), Cur(0)
400  {
401  reset();
402  }
403 
404  void reset()
405  {
406  Cur = getMin(Root);
407  }
408 
409  bool atEnd() const
410  {
412  return Cur==0;
413  }
414 
416  {
417  return Cur;
418  }
419 
421  {
422  Root = src.Root;
423  Cur = src.Cur;
424  return (*this);
425  }
426 
427  void operator++(int)
428  {
429  inc();
430  }
431 
433  {
434  return getNode();
435  }
436 
438  {
439  _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
440 
441  return *getNode();
442  }
443  private:
444 
445  Node* getMin(Node* n)
446  {
447  while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
448  {
449  if (n->getLeftChild())
450  n = n->getLeftChild();
451  else
452  n = n->getRightChild();
453  }
454  return n;
455  }
456 
457  void inc()
458  {
459  // Already at end?
460  if (Cur==0)
461  return;
462 
463  // Note: Starting point is the node as far down to the left as possible.
464 
465  // If current node has an uncle to the right, go to the
466  // node as far down to the left from the uncle as possible
467  // else just go up a level to the parent.
468  if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
469  {
470  Cur = getMin(Cur->getParent()->getRightChild());
471  }
472  else
473  Cur = Cur->getParent();
474  }
475 
476  Node* Root;
477  Node* Cur;
478  }; // ParentLastIterator
479 
480 
481  // AccessClass is a temporary class used with the [] operator.
482  // It makes it possible to have different behavior in situations like:
483  // myTree["Foo"] = 32;
484  // If "Foo" already exists update its value else insert a new element.
485  // int i = myTree["Foo"]
486  // If "Foo" exists return its value.
488  {
489  // Let map be the only one who can instantiate this class.
490  friend class map<KeyType, ValueType>;
491 
492  public:
493 
494  // Assignment operator. Handles the myTree["Foo"] = 32; situation
495  void operator=(const ValueType& value)
496  {
497  // Just use the Set method, it handles already exist/not exist situation
498  Tree.set(Key,value);
499  }
500 
501  // ValueType operator
502  operator ValueType()
503  {
504  Node* node = Tree.find(Key);
505 
506  // Not found
507  _IRR_DEBUG_BREAK_IF(node==0) // access violation
508 
510  return node->getValue();
511  }
512 
513  private:
514 
515  AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}
516 
517  AccessClass();
518 
519  map& Tree;
520  const KeyType& Key;
521  }; // AccessClass
522 
523 
524  // Constructor.
525  map() : Root(0), Size(0) {}
526 
527  // Destructor
529  {
530  clear();
531  }
532 
533  //------------------------------
534  // Public Commands
535  //------------------------------
536 
538 
541  bool insert(const KeyType& keyNew, const ValueType& v)
542  {
543  // First insert node the "usual" way (no fancy balance logic yet)
544  Node* newNode = new Node(keyNew,v);
545  if (!insert(newNode))
546  {
547  delete newNode;
549  return false;
550  }
551 
552  // Then attend a balancing party
553  while (!newNode->isRoot() && (newNode->getParent()->isRed()))
554  {
555  if (newNode->getParent()->isLeftChild())
556  {
557  // If newNode is a left child, get its right 'uncle'
558  Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
559  if ( newNodesUncle!=0 && newNodesUncle->isRed())
560  {
561  // case 1 - change the colours
562  newNode->getParent()->setBlack();
563  newNodesUncle->setBlack();
564  newNode->getParent()->getParent()->setRed();
565  // Move newNode up the tree
566  newNode = newNode->getParent()->getParent();
567  }
568  else
569  {
570  // newNodesUncle is a black node
571  if ( newNode->isRightChild())
572  {
573  // and newNode is to the right
574  // case 2 - move newNode up and rotate
575  newNode = newNode->getParent();
576  rotateLeft(newNode);
577  }
578  // case 3
579  newNode->getParent()->setBlack();
580  newNode->getParent()->getParent()->setRed();
581  rotateRight(newNode->getParent()->getParent());
582  }
583  }
584  else
585  {
586  // If newNode is a right child, get its left 'uncle'
587  Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
588  if ( newNodesUncle!=0 && newNodesUncle->isRed())
589  {
590  // case 1 - change the colours
591  newNode->getParent()->setBlack();
592  newNodesUncle->setBlack();
593  newNode->getParent()->getParent()->setRed();
594  // Move newNode up the tree
595  newNode = newNode->getParent()->getParent();
596  }
597  else
598  {
599  // newNodesUncle is a black node
600  if (newNode->isLeftChild())
601  {
602  // and newNode is to the left
603  // case 2 - move newNode up and rotate
604  newNode = newNode->getParent();
605  rotateRight(newNode);
606  }
607  // case 3
608  newNode->getParent()->setBlack();
609  newNode->getParent()->getParent()->setRed();
610  rotateLeft(newNode->getParent()->getParent());
611  }
612 
613  }
614  }
615  // Color the root black
616  Root->setBlack();
617  return true;
618  }
619 
621 
623  void set(const KeyType& k, const ValueType& v)
624  {
625  Node* p = find(k);
626  if (p)
627  p->setValue(v);
628  else
629  insert(k,v);
630  }
631 
633 
636  Node* delink(const KeyType& k)
637  {
638  Node* p = find(k);
639  if (p == 0)
640  return 0;
641 
642  // Rotate p down to the left until it has no right child, will get there
643  // sooner or later.
644  while(p->getRightChild())
645  {
646  // "Pull up my right child and let it knock me down to the left"
647  rotateLeft(p);
648  }
649  // p now has no right child but might have a left child
650  Node* left = p->getLeftChild();
651 
652  // Let p's parent point to p's child instead of point to p
653  if (p->isLeftChild())
654  p->getParent()->setLeftChild(left);
655 
656  else if (p->isRightChild())
657  p->getParent()->setRightChild(left);
658 
659  else
660  {
661  // p has no parent => p is the root.
662  // Let the left child be the new root.
663  setRoot(left);
664  }
665 
666  // p is now gone from the tree in the sense that
667  // no one is pointing at it, so return it.
668 
669  --Size;
670  return p;
671  }
672 
674 
675  bool remove(const KeyType& k)
676  {
677  Node* p = find(k);
678  if (p == 0)
679  {
681  return false;
682  }
683 
684  // Rotate p down to the left until it has no right child, will get there
685  // sooner or later.
686  while(p->getRightChild())
687  {
688  // "Pull up my right child and let it knock me down to the left"
689  rotateLeft(p);
690  }
691  // p now has no right child but might have a left child
692  Node* left = p->getLeftChild();
693 
694  // Let p's parent point to p's child instead of point to p
695  if (p->isLeftChild())
696  p->getParent()->setLeftChild(left);
697 
698  else if (p->isRightChild())
699  p->getParent()->setRightChild(left);
700 
701  else
702  {
703  // p has no parent => p is the root.
704  // Let the left child be the new root.
705  setRoot(left);
706  }
707 
708  // p is now gone from the tree in the sense that
709  // no one is pointing at it. Let's get rid of it.
710  delete p;
711 
712  --Size;
713  return true;
714  }
715 
717  void clear()
718  {
720 
721  while(!i.atEnd())
722  {
723  Node* p = i.getNode();
724  i++; // Increment it before it is deleted
725  // else iterator will get quite confused.
726  delete p;
727  }
728  Root = 0;
729  Size= 0;
730  }
731 
734  bool empty() const
735  {
737  return Root == 0;
738  }
739 
742  {
743  return empty();
744  }
745 
749  Node* find(const KeyType& keyToFind) const
750  {
751  Node* pNode = Root;
752 
753  while(pNode!=0)
754  {
755  KeyType key(pNode->getKey());
756 
757  if (keyToFind == key)
758  return pNode;
759  else if (keyToFind < key)
760  pNode = pNode->getLeftChild();
761  else //keyToFind > key
762  pNode = pNode->getRightChild();
763  }
764 
765  return 0;
766  }
767 
771  Node* getRoot() const
772  {
773  return Root;
774  }
775 
777  u32 size() const
778  {
779  return Size;
780  }
781 
783 
788  {
789  core::swap(Root, other.Root);
790  core::swap(Size, other.Size);
791  }
792 
793  //------------------------------
794  // Public Iterators
795  //------------------------------
796 
799  {
800  Iterator it(getRoot());
801  return it;
802  }
809  {
811  return it;
812  }
819  {
821  return it;
822  }
823 
824  //------------------------------
825  // Public Operators
826  //------------------------------
827 
829 
830  AccessClass operator[](const KeyType& k)
831  {
832  return AccessClass(*this, k);
833  }
834  private:
835 
836  //------------------------------
837  // Disabled methods
838  //------------------------------
839  // Copy constructor and assignment operator deliberately
840  // defined but not implemented. The tree should never be
841  // copied, pass along references to it instead.
842  explicit map(const map& src);
843  map& operator = (const map& src);
844 
846 
850  void setRoot(Node* newRoot)
851  {
852  Root = newRoot;
853  if (Root != 0)
854  {
855  Root->setParent(0);
856  Root->setBlack();
857  }
858  }
859 
861 
862  bool insert(Node* newNode)
863  {
864  bool result=true; // Assume success
865 
866  if (Root==0)
867  {
868  setRoot(newNode);
869  Size = 1;
870  }
871  else
872  {
873  Node* pNode = Root;
874  KeyType keyNew = newNode->getKey();
875  while (pNode)
876  {
877  KeyType key(pNode->getKey());
878 
879  if (keyNew == key)
880  {
881  result = false;
882  pNode = 0;
883  }
884  else if (keyNew < key)
885  {
886  if (pNode->getLeftChild() == 0)
887  {
888  pNode->setLeftChild(newNode);
889  pNode = 0;
890  }
891  else
892  pNode = pNode->getLeftChild();
893  }
894  else // keyNew > key
895  {
896  if (pNode->getRightChild()==0)
897  {
898  pNode->setRightChild(newNode);
899  pNode = 0;
900  }
901  else
902  {
903  pNode = pNode->getRightChild();
904  }
905  }
906  }
907 
908  if (result)
909  ++Size;
910  }
911 
913  return result;
914  }
915 
918  void rotateLeft(Node* p)
919  {
920  Node* right = p->getRightChild();
921 
922  p->setRightChild(right->getLeftChild());
923 
924  if (p->isLeftChild())
925  p->getParent()->setLeftChild(right);
926  else if (p->isRightChild())
927  p->getParent()->setRightChild(right);
928  else
929  setRoot(right);
930 
931  right->setLeftChild(p);
932  }
933 
936  void rotateRight(Node* p)
937  {
938  Node* left = p->getLeftChild();
939 
940  p->setLeftChild(left->getRightChild());
941 
942  if (p->isLeftChild())
943  p->getParent()->setLeftChild(left);
944  else if (p->isRightChild())
945  p->getParent()->setRightChild(left);
946  else
947  setRoot(left);
948 
949  left->setRightChild(p);
950  }
951 
952  //------------------------------
953  // Private Members
954  //------------------------------
955  Node* Root; // The top node. 0 if empty.
956  u32 Size; // Number of nodes in the tree
957 };
958 
959 } // end namespace core
960 } // end namespace irr
961 
962 #endif // __IRR_MAP_H_INCLUDED__
963 

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Fri Mar 21 2014 04:40:16 by Doxygen (1.8.1.2)