Line data Source code
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 :
16 : //! map template for associative arrays using a red-black tree
17 : template <class KeyType, class ValueType>
18 : class map
19 : {
20 : //! red/black tree for map
21 : template <class KeyTypeRB, class ValueTypeRB>
22 : class RBTree
23 : {
24 : public:
25 :
26 0 : RBTree(const KeyTypeRB& k, const ValueTypeRB& v)
27 : : LeftChild(0), RightChild(0), Parent(0), Key(k),
28 0 : Value(v), IsRed(true) {}
29 :
30 0 : void setLeftChild(RBTree* p)
31 : {
32 0 : LeftChild=p;
33 0 : if (p)
34 0 : p->setParent(this);
35 0 : }
36 :
37 0 : void setRightChild(RBTree* p)
38 : {
39 0 : RightChild=p;
40 0 : if (p)
41 0 : p->setParent(this);
42 0 : }
43 :
44 0 : void setParent(RBTree* p) { Parent=p; }
45 :
46 : void setValue(const ValueTypeRB& v) { Value = v; }
47 :
48 0 : void setRed() { IsRed = true; }
49 0 : void setBlack() { IsRed = false; }
50 :
51 0 : RBTree* getLeftChild() const { return LeftChild; }
52 0 : RBTree* getRightChild() const { return RightChild; }
53 0 : RBTree* getParent() const { return Parent; }
54 :
55 : const ValueTypeRB& getValue() const
56 : {
57 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
58 : return Value;
59 : }
60 :
61 0 : ValueTypeRB& getValue()
62 : {
63 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
64 0 : return Value;
65 : }
66 :
67 0 : const KeyTypeRB& getKey() const
68 : {
69 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
70 0 : return Key;
71 : }
72 :
73 0 : bool isRoot() const
74 : {
75 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
76 0 : return Parent==0;
77 : }
78 :
79 0 : bool isLeftChild() const
80 : {
81 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
82 0 : return (Parent != 0) && (Parent->getLeftChild()==this);
83 : }
84 :
85 0 : bool isRightChild() const
86 : {
87 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
88 0 : return (Parent!=0) && (Parent->getRightChild()==this);
89 : }
90 :
91 : bool isLeaf() const
92 : {
93 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
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 0 : bool isRed() const
107 : {
108 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
109 0 : return IsRed;
110 : }
111 :
112 : bool isBlack() const
113 : {
114 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
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 :
138 : //! Normal Iterator
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 : {
165 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
166 : return Cur==0;
167 : }
168 :
169 : Node* getNode() const
170 : {
171 : return Cur;
172 : }
173 :
174 : Iterator& operator=(const Iterator& src)
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 :
286 : //! Const Iterator
287 : class ConstIterator
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 : {
314 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
315 : return Cur==0;
316 : }
317 :
318 : const Node* getNode() const
319 : {
320 : return Cur;
321 : }
322 :
323 : ConstIterator& operator=(const ConstIterator& src)
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 :
436 : //! Parent First Iterator.
437 : /** Traverses the tree from top to bottom. Typical usage is
438 : when storing the tree structure, because when reading it
439 : later (and inserting elements) the tree structure will
440 : be the same. */
441 : class ParentFirstIterator
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 : {
459 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
460 : return Cur==0;
461 : }
462 :
463 : Node* getNode()
464 : {
465 : return Cur;
466 : }
467 :
468 : ParentFirstIterator& operator=(const ParentFirstIterator& src)
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 :
536 : //! Parent Last Iterator
537 : /** Traverse the tree from bottom to top.
538 : Typical usage is when deleting all elements in the tree
539 : because you must delete the children before you delete
540 : their parent. */
541 : class ParentLastIterator
542 : {
543 : public:
544 :
545 : ParentLastIterator() : Root(0), Cur(0) {}
546 :
547 0 : explicit ParentLastIterator(Node* root) : Root(root), Cur(0)
548 : {
549 0 : reset();
550 0 : }
551 :
552 0 : void reset()
553 : {
554 0 : Cur = getMin(Root);
555 0 : }
556 :
557 0 : bool atEnd() const
558 : {
559 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
560 0 : return Cur==0;
561 : }
562 :
563 0 : Node* getNode()
564 : {
565 0 : return Cur;
566 : }
567 :
568 : ParentLastIterator& operator=(const ParentLastIterator& src)
569 : {
570 : Root = src.Root;
571 : Cur = src.Cur;
572 : return (*this);
573 : }
574 :
575 0 : void operator++(int)
576 : {
577 0 : inc();
578 0 : }
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 0 : Node* getMin(Node* n)
594 : {
595 0 : while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
596 : {
597 0 : if (n->getLeftChild())
598 0 : n = n->getLeftChild();
599 : else
600 0 : n = n->getRightChild();
601 : }
602 0 : return n;
603 : }
604 :
605 0 : void inc()
606 : {
607 : // Already at end?
608 0 : if (Cur==0)
609 0 : 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 0 : if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
617 : {
618 0 : Cur = getMin(Cur->getParent()->getRightChild());
619 : }
620 : else
621 0 : 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.
635 : class AccessClass
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 :
657 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
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 0 : map() : Root(0), Size(0) {}
674 :
675 : // Destructor
676 0 : ~map()
677 : {
678 0 : clear();
679 0 : }
680 :
681 : //------------------------------
682 : // Public Commands
683 : //------------------------------
684 :
685 : //! Inserts a new node into the tree
686 : /** \param keyNew: the index for this value
687 : \param v: the value to insert
688 : \return True if successful, false if it fails (already exists) */
689 0 : bool insert(const KeyType& keyNew, const ValueType& v)
690 : {
691 : // First insert node the "usual" way (no fancy balance logic yet)
692 0 : Node* newNode = new Node(keyNew,v);
693 0 : if (!insert(newNode))
694 : {
695 0 : delete newNode;
696 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
697 0 : return false;
698 : }
699 :
700 : // Then attend a balancing party
701 0 : while (!newNode->isRoot() && (newNode->getParent()->isRed()))
702 : {
703 0 : if (newNode->getParent()->isLeftChild())
704 : {
705 : // If newNode is a left child, get its right 'uncle'
706 0 : Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
707 0 : if ( newNodesUncle!=0 && newNodesUncle->isRed())
708 : {
709 : // case 1 - change the colors
710 0 : newNode->getParent()->setBlack();
711 0 : newNodesUncle->setBlack();
712 0 : newNode->getParent()->getParent()->setRed();
713 : // Move newNode up the tree
714 0 : newNode = newNode->getParent()->getParent();
715 : }
716 : else
717 : {
718 : // newNodesUncle is a black node
719 0 : if ( newNode->isRightChild())
720 : {
721 : // and newNode is to the right
722 : // case 2 - move newNode up and rotate
723 0 : newNode = newNode->getParent();
724 0 : rotateLeft(newNode);
725 : }
726 : // case 3
727 0 : newNode->getParent()->setBlack();
728 0 : newNode->getParent()->getParent()->setRed();
729 0 : rotateRight(newNode->getParent()->getParent());
730 : }
731 : }
732 : else
733 : {
734 : // If newNode is a right child, get its left 'uncle'
735 0 : Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
736 0 : if ( newNodesUncle!=0 && newNodesUncle->isRed())
737 : {
738 : // case 1 - change the colors
739 0 : newNode->getParent()->setBlack();
740 0 : newNodesUncle->setBlack();
741 0 : newNode->getParent()->getParent()->setRed();
742 : // Move newNode up the tree
743 0 : newNode = newNode->getParent()->getParent();
744 : }
745 : else
746 : {
747 : // newNodesUncle is a black node
748 0 : if (newNode->isLeftChild())
749 : {
750 : // and newNode is to the left
751 : // case 2 - move newNode up and rotate
752 0 : newNode = newNode->getParent();
753 0 : rotateRight(newNode);
754 : }
755 : // case 3
756 0 : newNode->getParent()->setBlack();
757 0 : newNode->getParent()->getParent()->setRed();
758 0 : rotateLeft(newNode->getParent()->getParent());
759 : }
760 :
761 : }
762 : }
763 : // Color the root black
764 0 : Root->setBlack();
765 0 : return true;
766 : }
767 :
768 : //! Replaces the value if the key already exists, otherwise inserts a new element.
769 : /** \param k The index for this value
770 : \param v The new value of */
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 :
780 : //! Removes a node from the tree and returns it.
781 : /** The returned node must be deleted by the user
782 : \param k the key to remove
783 : \return A pointer to the node, or 0 if not found */
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 :
821 : //! Removes a node from the tree and deletes it.
822 : /** \return True if the node was found and deleted */
823 : bool remove(const KeyType& k)
824 : {
825 : Node* p = find(k);
826 : return remove(p);
827 : }
828 :
829 : //! Removes a node from the tree and deletes it.
830 : /** \return True if the node was found and deleted */
831 : bool remove(Node* p)
832 : {
833 : if (p == 0)
834 : {
835 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
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 :
871 : //! Clear the entire tree
872 0 : void clear()
873 : {
874 0 : ParentLastIterator i(getParentLastIterator());
875 :
876 0 : while(!i.atEnd())
877 : {
878 0 : Node* p = i.getNode();
879 0 : i++; // Increment it before it is deleted
880 : // else iterator will get quite confused.
881 0 : delete p;
882 : }
883 0 : Root = 0;
884 0 : Size= 0;
885 0 : }
886 :
887 : //! Is the tree empty?
888 : //! \return Returns true if empty, false if not
889 : bool empty() const
890 : {
891 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
892 : return Root == 0;
893 : }
894 :
895 : //! \deprecated Use empty() instead. This method may be removed by Irrlicht 1.9
896 : _IRR_DEPRECATED_ bool isEmpty() const
897 : {
898 : return empty();
899 : }
900 :
901 : //! Search for a node with the specified key.
902 : //! \param keyToFind: The key to find
903 : //! \return Returns 0 if node couldn't be found.
904 0 : Node* find(const KeyType& keyToFind) const
905 : {
906 0 : Node* pNode = Root;
907 :
908 0 : while(pNode!=0)
909 : {
910 0 : const KeyType& key=pNode->getKey();
911 :
912 0 : if (keyToFind == key)
913 0 : return pNode;
914 0 : else if (keyToFind < key)
915 0 : pNode = pNode->getLeftChild();
916 : else //keyToFind > key
917 0 : pNode = pNode->getRightChild();
918 : }
919 :
920 0 : return 0;
921 : }
922 :
923 : //! Gets the root element.
924 : //! \return Returns a pointer to the root node, or
925 : //! 0 if the tree is empty.
926 0 : Node* getRoot() const
927 : {
928 0 : return Root;
929 : }
930 :
931 : //! Returns the number of nodes in the tree.
932 : u32 size() const
933 : {
934 : return Size;
935 : }
936 :
937 : //! Swap the content of this map container with the content of another map
938 : /** Afterwards this object will contain the content of the other object and the other
939 : object will contain the content of this object. Iterators will afterwards be valid for
940 : the swapped object.
941 : \param other Swap content with this object */
942 : void swap(map<KeyType, ValueType>& other)
943 : {
944 : core::swap(Root, other.Root);
945 : core::swap(Size, other.Size);
946 : }
947 :
948 : //------------------------------
949 : // Public Iterators
950 : //------------------------------
951 :
952 : //! Returns an iterator
953 : Iterator getIterator() const
954 : {
955 : Iterator it(getRoot());
956 : return it;
957 : }
958 :
959 : //! Returns a Constiterator
960 : ConstIterator getConstIterator() const
961 : {
962 : Iterator it(getRoot());
963 : return it;
964 : }
965 :
966 : //! Returns a ParentFirstIterator.
967 : //! Traverses the tree from top to bottom. Typical usage is
968 : //! when storing the tree structure, because when reading it
969 : //! later (and inserting elements) the tree structure will
970 : //! be the same.
971 : ParentFirstIterator getParentFirstIterator() const
972 : {
973 : ParentFirstIterator it(getRoot());
974 : return it;
975 : }
976 :
977 : //! Returns a ParentLastIterator to traverse the tree from
978 : //! bottom to top.
979 : //! Typical usage is when deleting all elements in the tree
980 : //! because you must delete the children before you delete
981 : //! their parent.
982 0 : ParentLastIterator getParentLastIterator() const
983 : {
984 0 : ParentLastIterator it(getRoot());
985 0 : return it;
986 : }
987 :
988 : //------------------------------
989 : // Public Operators
990 : //------------------------------
991 :
992 : //! operator [] for access to elements
993 : /** for example myMap["key"] */
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 :
1009 : //! Set node as new root.
1010 : /** The node will be set to black, otherwise core dumps may arise
1011 : (patch provided by rogerborg).
1012 : \param newRoot Node which will be the new root
1013 : */
1014 0 : void setRoot(Node* newRoot)
1015 : {
1016 0 : Root = newRoot;
1017 0 : if (Root != 0)
1018 : {
1019 0 : Root->setParent(0);
1020 0 : Root->setBlack();
1021 : }
1022 0 : }
1023 :
1024 : //! Insert a node into the tree without using any fancy balancing logic.
1025 : /** \return false if that key already exist in the tree. */
1026 0 : bool insert(Node* newNode)
1027 : {
1028 0 : bool result=true; // Assume success
1029 :
1030 0 : if (Root==0)
1031 : {
1032 0 : setRoot(newNode);
1033 0 : Size = 1;
1034 : }
1035 : else
1036 : {
1037 0 : Node* pNode = Root;
1038 0 : const KeyType& keyNew = newNode->getKey();
1039 0 : while (pNode)
1040 : {
1041 0 : const KeyType& key=pNode->getKey();
1042 :
1043 0 : if (keyNew == key)
1044 : {
1045 0 : result = false;
1046 0 : pNode = 0;
1047 : }
1048 0 : else if (keyNew < key)
1049 : {
1050 0 : if (pNode->getLeftChild() == 0)
1051 : {
1052 0 : pNode->setLeftChild(newNode);
1053 0 : pNode = 0;
1054 : }
1055 : else
1056 0 : pNode = pNode->getLeftChild();
1057 : }
1058 : else // keyNew > key
1059 : {
1060 0 : if (pNode->getRightChild()==0)
1061 : {
1062 0 : pNode->setRightChild(newNode);
1063 0 : pNode = 0;
1064 : }
1065 : else
1066 : {
1067 0 : pNode = pNode->getRightChild();
1068 : }
1069 : }
1070 : }
1071 :
1072 0 : if (result)
1073 0 : ++Size;
1074 : }
1075 :
1076 : _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
1077 0 : return result;
1078 : }
1079 :
1080 : //! Rotate left.
1081 : //! Pull up node's right child and let it knock node down to the left
1082 0 : void rotateLeft(Node* p)
1083 : {
1084 0 : Node* right = p->getRightChild();
1085 :
1086 0 : p->setRightChild(right->getLeftChild());
1087 :
1088 0 : if (p->isLeftChild())
1089 0 : p->getParent()->setLeftChild(right);
1090 0 : else if (p->isRightChild())
1091 0 : p->getParent()->setRightChild(right);
1092 : else
1093 0 : setRoot(right);
1094 :
1095 0 : right->setLeftChild(p);
1096 0 : }
1097 :
1098 : //! Rotate right.
1099 : //! Pull up node's left child and let it knock node down to the right
1100 0 : void rotateRight(Node* p)
1101 : {
1102 0 : Node* left = p->getLeftChild();
1103 :
1104 0 : p->setLeftChild(left->getRightChild());
1105 :
1106 0 : if (p->isLeftChild())
1107 0 : p->getParent()->setLeftChild(left);
1108 0 : else if (p->isRightChild())
1109 0 : p->getParent()->setRightChild(left);
1110 : else
1111 0 : setRoot(left);
1112 :
1113 0 : left->setRightChild(p);
1114 0 : }
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 :
|
