diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/irrlicht-1.8/include/irrMap.h | 1127 |
1 files changed, 1127 insertions, 0 deletions
diff --git a/libraries/irrlicht-1.8/include/irrMap.h b/libraries/irrlicht-1.8/include/irrMap.h new file mode 100644 index 0000000..9e9ae73 --- /dev/null +++ b/libraries/irrlicht-1.8/include/irrMap.h | |||
@@ -0,0 +1,1127 @@ | |||
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 | 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 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
58 | return Value; | ||
59 | } | ||
60 | |||
61 | ValueTypeRB& getValue() | ||
62 | { | ||
63 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
64 | return Value; | ||
65 | } | ||
66 | |||
67 | const KeyTypeRB& getKey() const | ||
68 | { | ||
69 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
70 | return Key; | ||
71 | } | ||
72 | |||
73 | bool isRoot() const | ||
74 | { | ||
75 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
76 | return Parent==0; | ||
77 | } | ||
78 | |||
79 | bool isLeftChild() const | ||
80 | { | ||
81 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
82 | return (Parent != 0) && (Parent->getLeftChild()==this); | ||
83 | } | ||
84 | |||
85 | bool isRightChild() const | ||
86 | { | ||
87 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
88 | 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 | bool isRed() const | ||
107 | { | ||
108 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
109 | 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 | 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 | { | ||
559 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
560 | return Cur==0; | ||
561 | } | ||
562 | |||
563 | Node* getNode() | ||
564 | { | ||
565 | 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 | 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. | ||
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 | map() : Root(0), Size(0) {} | ||
674 | |||
675 | // Destructor | ||
676 | ~map() | ||
677 | { | ||
678 | clear(); | ||
679 | } | ||
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 | 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; | ||
696 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
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 | |||
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 | void clear() | ||
873 | { | ||
874 | ParentLastIterator i(getParentLastIterator()); | ||
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 | |||
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 | 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 | |||
923 | //! Gets the root element. | ||
924 | //! \return Returns a pointer to the root node, or | ||
925 | //! 0 if the tree is empty. | ||
926 | Node* getRoot() const | ||
927 | { | ||
928 | 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 | ParentLastIterator getParentLastIterator() const | ||
983 | { | ||
984 | ParentLastIterator it(getRoot()); | ||
985 | 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 | void setRoot(Node* newRoot) | ||
1015 | { | ||
1016 | Root = newRoot; | ||
1017 | if (Root != 0) | ||
1018 | { | ||
1019 | Root->setParent(0); | ||
1020 | Root->setBlack(); | ||
1021 | } | ||
1022 | } | ||
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 | 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 | |||
1076 | _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; | ||
1077 | return result; | ||
1078 | } | ||
1079 | |||
1080 | //! Rotate left. | ||
1081 | //! Pull up node's right child and let it knock node down to the left | ||
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 | |||
1098 | //! Rotate right. | ||
1099 | //! Pull up node's left child and let it knock node down to the right | ||
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 | |||