← Back to branch summary

~baltix/+junk/irrlicht-test

« back to all changes in this revision

Viewing changes to include/irrMap.h

  • Committer: Mantas Kriaučiūnas
  • Date: 2011-07-18 13:06:25 UTC
  • Revision ID: mantas@akl.lt-20110718130625-c5pvifp61e7kj1ol
Included whole irrlicht SVN libraries to work around launchpad recipe issue with quilt, see https://answers.launchpad.net/launchpad/+question/165193

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/irrMap.h
 
1
// Copyright (C) 2006-2011 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
                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
                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
 
 
136
        //! Normal Iterator
 
137
        class Iterator
 
138
        {
 
139
        public:
 
140
 
 
141
                Iterator() : Root(0), Cur(0) {}
 
142
 
 
143
                // Constructor(Node*)
 
144
                Iterator(Node* root) : Root(root)
 
145
                {
 
146
                        reset();
 
147
                }
 
148
 
 
149
                // Copy constructor
 
150
                Iterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}
 
151
 
 
152
                void reset(bool atLowest=true)
 
153
                {
 
154
                        if (atLowest)
 
155
                                Cur = getMin(Root);
 
156
                        else
 
157
                                Cur = getMax(Root);
 
158
                }
 
159
 
 
160
                bool atEnd() const
 
161
                {
 
162
                        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
163
                        return Cur==0;
 
164
                }
 
165
 
 
166
                Node* getNode()
 
167
                {
 
168
                        return Cur;
 
169
                }
 
170
 
 
171
                Iterator& operator=(const Iterator& src)
 
172
                {
 
173
                        Root = src.Root;
 
174
                        Cur = src.Cur;
 
175
                        return (*this);
 
176
                }
 
177
 
 
178
                void operator++(int)
 
179
                {
 
180
                        inc();
 
181
                }
 
182
 
 
183
                void operator--(int)
 
184
                {
 
185
                        dec();
 
186
                }
 
187
 
 
188
 
 
189
                Node* operator -> ()
 
190
                {
 
191
                        return getNode();
 
192
                }
 
193
 
 
194
                Node& operator* ()
 
195
                {
 
196
                        _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
197
 
 
198
                        return *Cur;
 
199
                }
 
200
 
 
201
        private:
 
202
 
 
203
                Node* getMin(Node* n)
 
204
                {
 
205
                        while(n && n->getLeftChild())
 
206
                                n = n->getLeftChild();
 
207
                        return n;
 
208
                }
 
209
 
 
210
                Node* getMax(Node* n)
 
211
                {
 
212
                        while(n && n->getRightChild())
 
213
                                n = n->getRightChild();
 
214
                        return n;
 
215
                }
 
216
 
 
217
                void inc()
 
218
                {
 
219
                        // Already at end?
 
220
                        if (Cur==0)
 
221
                                return;
 
222
 
 
223
                        if (Cur->getRightChild())
 
224
                        {
 
225
                                // If current node has a right child, the next higher node is the
 
226
                                // node with lowest key beneath the right child.
 
227
                                Cur = getMin(Cur->getRightChild());
 
228
                        }
 
229
                        else if (Cur->isLeftChild())
 
230
                        {
 
231
                                // No right child? Well if current node is a left child then
 
232
                                // the next higher node is the parent
 
233
                                Cur = Cur->getParent();
 
234
                        }
 
235
                        else
 
236
                        {
 
237
                                // Current node neither is left child nor has a right child.
 
238
                                // Ie it is either right child or root
 
239
                                // The next higher node is the parent of the first non-right
 
240
                                // child (ie either a left child or the root) up in the
 
241
                                // hierarchy. Root's parent is 0.
 
242
                                while(Cur->isRightChild())
 
243
                                        Cur = Cur->getParent();
 
244
                                Cur = Cur->getParent();
 
245
                        }
 
246
                }
 
247
 
 
248
                void dec()
 
249
                {
 
250
                        // Already at end?
 
251
                        if (Cur==0)
 
252
                                return;
 
253
 
 
254
                        if (Cur->getLeftChild())
 
255
                        {
 
256
                                // If current node has a left child, the next lower node is the
 
257
                                // node with highest key beneath the left child.
 
258
                                Cur = getMax(Cur->getLeftChild());
 
259
                        }
 
260
                        else if (Cur->isRightChild())
 
261
                        {
 
262
                                // No left child? Well if current node is a right child then
 
263
                                // the next lower node is the parent
 
264
                                Cur = Cur->getParent();
 
265
                        }
 
266
                        else
 
267
                        {
 
268
                                // Current node neither is right child nor has a left child.
 
269
                                // Ie it is either left child or root
 
270
                                // The next higher node is the parent of the first non-left
 
271
                                // child (ie either a right child or the root) up in the
 
272
                                // hierarchy. Root's parent is 0.
 
273
 
 
274
                                while(Cur->isLeftChild())
 
275
                                        Cur = Cur->getParent();
 
276
                                Cur = Cur->getParent();
 
277
                        }
 
278
                }
 
279
 
 
280
                Node* Root;
 
281
                Node* Cur;
 
282
        }; // Iterator
 
283
 
 
284
 
 
285
 
 
286
        //! Parent First Iterator.
 
287
        /** Traverses the tree from top to bottom. Typical usage is
 
288
        when storing the tree structure, because when reading it
 
289
        later (and inserting elements) the tree structure will
 
290
        be the same. */
 
291
        class ParentFirstIterator
 
292
        {
 
293
        public:
 
294
 
 
295
 
 
296
        ParentFirstIterator() : Root(0), Cur(0)
 
297
        {
 
298
        }
 
299
 
 
300
 
 
301
        explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)
 
302
        {
 
303
                reset();
 
304
        }
 
305
 
 
306
        void reset()
 
307
        {
 
308
                Cur = Root;
 
309
        }
 
310
 
 
311
 
 
312
        bool atEnd() const
 
313
        {
 
314
                _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
315
                return Cur==0;
 
316
        }
 
317
 
 
318
        Node* getNode()
 
319
        {
 
320
                return Cur;
 
321
        }
 
322
 
 
323
 
 
324
        ParentFirstIterator& operator=(const ParentFirstIterator& src)
 
325
        {
 
326
                Root = src.Root;
 
327
                Cur = src.Cur;
 
328
                return (*this);
 
329
        }
 
330
 
 
331
 
 
332
        void operator++(int)
 
333
        {
 
334
                inc();
 
335
        }
 
336
 
 
337
 
 
338
        Node* operator -> ()
 
339
        {
 
340
                return getNode();
 
341
        }
 
342
 
 
343
        Node& operator* ()
 
344
        {
 
345
                _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
346
 
 
347
                return *getNode();
 
348
        }
 
349
 
 
350
        private:
 
351
 
 
352
        void inc()
 
353
        {
 
354
                // Already at end?
 
355
                if (Cur==0)
 
356
                        return;
 
357
 
 
358
                // First we try down to the left
 
359
                if (Cur->getLeftChild())
 
360
                {
 
361
                        Cur = Cur->getLeftChild();
 
362
                }
 
363
                else if (Cur->getRightChild())
 
364
                {
 
365
                        // No left child? The we go down to the right.
 
366
                        Cur = Cur->getRightChild();
 
367
                }
 
368
                else
 
369
                {
 
370
                        // No children? Move up in the hierarcy until
 
371
                        // we either reach 0 (and are finished) or
 
372
                        // find a right uncle.
 
373
                        while (Cur!=0)
 
374
                        {
 
375
                                // But if parent is left child and has a right "uncle" the parent
 
376
                                // has already been processed but the uncle hasn't. Move to
 
377
                                // the uncle.
 
378
                                if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
 
379
                                {
 
380
                                        Cur = Cur->getParent()->getRightChild();
 
381
                                        return;
 
382
                                }
 
383
                                Cur = Cur->getParent();
 
384
                        }
 
385
                }
 
386
        }
 
387
 
 
388
        Node* Root;
 
389
        Node* Cur;
 
390
 
 
391
        }; // ParentFirstIterator
 
392
 
 
393
 
 
394
        //! Parent Last Iterator
 
395
        /** Traverse the tree from bottom to top.
 
396
        Typical usage is when deleting all elements in the tree
 
397
        because you must delete the children before you delete
 
398
        their parent. */
 
399
        class ParentLastIterator
 
400
        {
 
401
        public:
 
402
 
 
403
                ParentLastIterator() : Root(0), Cur(0) {}
 
404
 
 
405
                explicit ParentLastIterator(Node* root) : Root(root), Cur(0)
 
406
                {
 
407
                        reset();
 
408
                }
 
409
 
 
410
                void reset()
 
411
                {
 
412
                        Cur = getMin(Root);
 
413
                }
 
414
 
 
415
                bool atEnd() const
 
416
                {
 
417
                        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
418
                        return Cur==0;
 
419
                }
 
420
 
 
421
                Node* getNode()
 
422
                {
 
423
                        return Cur;
 
424
                }
 
425
 
 
426
                ParentLastIterator& operator=(const ParentLastIterator& src)
 
427
                {
 
428
                        Root = src.Root;
 
429
                        Cur = src.Cur;
 
430
                        return (*this);
 
431
                }
 
432
 
 
433
                void operator++(int)
 
434
                {
 
435
                        inc();
 
436
                }
 
437
 
 
438
                Node* operator -> ()
 
439
                {
 
440
                        return getNode();
 
441
                }
 
442
 
 
443
                Node& operator* ()
 
444
                {
 
445
                        _IRR_DEBUG_BREAK_IF(atEnd()) // access violation
 
446
 
 
447
                        return *getNode();
 
448
                }
 
449
        private:
 
450
 
 
451
                Node* getMin(Node* n)
 
452
                {
 
453
                        while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
 
454
                        {
 
455
                                if (n->getLeftChild())
 
456
                                        n = n->getLeftChild();
 
457
                                else
 
458
                                        n = n->getRightChild();
 
459
                        }
 
460
                        return n;
 
461
                }
 
462
 
 
463
                void inc()
 
464
                {
 
465
                        // Already at end?
 
466
                        if (Cur==0)
 
467
                                return;
 
468
 
 
469
                        // Note: Starting point is the node as far down to the left as possible.
 
470
 
 
471
                        // If current node has an uncle to the right, go to the
 
472
                        // node as far down to the left from the uncle as possible
 
473
                        // else just go up a level to the parent.
 
474
                        if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
 
475
                        {
 
476
                                Cur = getMin(Cur->getParent()->getRightChild());
 
477
                        }
 
478
                        else
 
479
                                Cur = Cur->getParent();
 
480
                }
 
481
 
 
482
                Node* Root;
 
483
                Node* Cur;
 
484
        }; // ParentLastIterator
 
485
 
 
486
 
 
487
        // AccessClass is a temporary class used with the [] operator.
 
488
        // It makes it possible to have different behavior in situations like:
 
489
        // myTree["Foo"] = 32;
 
490
        // If "Foo" already exists update its value else insert a new element.
 
491
        // int i = myTree["Foo"]
 
492
        // If "Foo" exists return its value.
 
493
        class AccessClass
 
494
        {
 
495
                // Let map be the only one who can instantiate this class.
 
496
                friend class map<KeyType, ValueType>;
 
497
 
 
498
        public:
 
499
 
 
500
                // Assignment operator. Handles the myTree["Foo"] = 32; situation
 
501
                void operator=(const ValueType& value)
 
502
                {
 
503
                        // Just use the Set method, it handles already exist/not exist situation
 
504
                        Tree.set(Key,value);
 
505
                }
 
506
 
 
507
                // ValueType operator
 
508
                operator ValueType()
 
509
                {
 
510
                        Node* node = Tree.find(Key);
 
511
 
 
512
                        // Not found
 
513
                        _IRR_DEBUG_BREAK_IF(node==0) // access violation
 
514
 
 
515
                        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
516
                        return node->getValue();
 
517
                }
 
518
 
 
519
        private:
 
520
 
 
521
                AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}
 
522
 
 
523
                AccessClass();
 
524
 
 
525
                map& Tree;
 
526
                const KeyType& Key;
 
527
        }; // AccessClass
 
528
 
 
529
 
 
530
        // Constructor.
 
531
        map() : Root(0), Size(0) {}
 
532
 
 
533
        // Destructor
 
534
        ~map()
 
535
        {
 
536
                clear();
 
537
        }
 
538
 
 
539
        //------------------------------
 
540
        // Public Commands
 
541
        //------------------------------
 
542
 
 
543
        //! Inserts a new node into the tree
 
544
        /** \param keyNew: the index for this value
 
545
        \param v: the value to insert
 
546
        \return True if successful, false if it fails (already exists) */
 
547
        bool insert(const KeyType& keyNew, const ValueType& v)
 
548
        {
 
549
                // First insert node the "usual" way (no fancy balance logic yet)
 
550
                Node* newNode = new Node(keyNew,v);
 
551
                if (!insert(newNode))
 
552
                {
 
553
                        delete newNode;
 
554
                        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
555
                        return false;
 
556
                }
 
557
 
 
558
                // Then attend a balancing party
 
559
                while (!newNode->isRoot() && (newNode->getParent()->isRed()))
 
560
                {
 
561
                        if (newNode->getParent()->isLeftChild())
 
562
                        {
 
563
                                // If newNode is a left child, get its right 'uncle'
 
564
                                Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
 
565
                                if ( newNodesUncle!=0 && newNodesUncle->isRed())
 
566
                                {
 
567
                                        // case 1 - change the colours
 
568
                                        newNode->getParent()->setBlack();
 
569
                                        newNodesUncle->setBlack();
 
570
                                        newNode->getParent()->getParent()->setRed();
 
571
                                        // Move newNode up the tree
 
572
                                        newNode = newNode->getParent()->getParent();
 
573
                                }
 
574
                                else
 
575
                                {
 
576
                                        // newNodesUncle is a black node
 
577
                                        if ( newNode->isRightChild())
 
578
                                        {
 
579
                                                // and newNode is to the right
 
580
                                                // case 2 - move newNode up and rotate
 
581
                                                newNode = newNode->getParent();
 
582
                                                rotateLeft(newNode);
 
583
                                        }
 
584
                                        // case 3
 
585
                                        newNode->getParent()->setBlack();
 
586
                                        newNode->getParent()->getParent()->setRed();
 
587
                                        rotateRight(newNode->getParent()->getParent());
 
588
                                }
 
589
                        }
 
590
                        else
 
591
                        {
 
592
                                // If newNode is a right child, get its left 'uncle'
 
593
                                Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
 
594
                                if ( newNodesUncle!=0 && newNodesUncle->isRed())
 
595
                                {
 
596
                                        // case 1 - change the colours
 
597
                                        newNode->getParent()->setBlack();
 
598
                                        newNodesUncle->setBlack();
 
599
                                        newNode->getParent()->getParent()->setRed();
 
600
                                        // Move newNode up the tree
 
601
                                        newNode = newNode->getParent()->getParent();
 
602
                                }
 
603
                                else
 
604
                                {
 
605
                                        // newNodesUncle is a black node
 
606
                                        if (newNode->isLeftChild())
 
607
                                        {
 
608
                                                // and newNode is to the left
 
609
                                                // case 2 - move newNode up and rotate
 
610
                                                newNode = newNode->getParent();
 
611
                                                rotateRight(newNode);
 
612
                                        }
 
613
                                        // case 3
 
614
                                        newNode->getParent()->setBlack();
 
615
                                        newNode->getParent()->getParent()->setRed();
 
616
                                        rotateLeft(newNode->getParent()->getParent());
 
617
                                }
 
618
 
 
619
                        }
 
620
                }
 
621
                // Color the root black
 
622
                Root->setBlack();
 
623
                return true;
 
624
        }
 
625
 
 
626
        //! Replaces the value if the key already exists, otherwise inserts a new element.
 
627
        /** \param k The index for this value
 
628
        \param v The new value of */
 
629
        void set(const KeyType& k, const ValueType& v)
 
630
        {
 
631
                Node* p = find(k);
 
632
                if (p)
 
633
                        p->setValue(v);
 
634
                else
 
635
                        insert(k,v);
 
636
        }
 
637
 
 
638
        //! Removes a node from the tree and returns it.
 
639
        /** The returned node must be deleted by the user
 
640
        \param k the key to remove
 
641
        \return A pointer to the node, or 0 if not found */
 
642
        Node* delink(const KeyType& k)
 
643
        {
 
644
                Node* p = find(k);
 
645
                if (p == 0)
 
646
                        return 0;
 
647
 
 
648
                // Rotate p down to the left until it has no right child, will get there
 
649
                // sooner or later.
 
650
                while(p->getRightChild())
 
651
                {
 
652
                        // "Pull up my right child and let it knock me down to the left"
 
653
                        rotateLeft(p);
 
654
                }
 
655
                // p now has no right child but might have a left child
 
656
                Node* left = p->getLeftChild();
 
657
 
 
658
                // Let p's parent point to p's child instead of point to p
 
659
                if (p->isLeftChild())
 
660
                        p->getParent()->setLeftChild(left);
 
661
 
 
662
                else if (p->isRightChild())
 
663
                        p->getParent()->setRightChild(left);
 
664
 
 
665
                else
 
666
                {
 
667
                        // p has no parent => p is the root.
 
668
                        // Let the left child be the new root.
 
669
                        setRoot(left);
 
670
                }
 
671
 
 
672
                // p is now gone from the tree in the sense that
 
673
                // no one is pointing at it, so return it.
 
674
 
 
675
                --Size;
 
676
                return p;
 
677
        }
 
678
 
 
679
        //! Removes a node from the tree and deletes it.
 
680
        /** \return True if the node was found and deleted */
 
681
        bool remove(const KeyType& k)
 
682
        {
 
683
                Node* p = find(k);
 
684
                if (p == 0)
 
685
                {
 
686
                        _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
687
                        return false;
 
688
                }
 
689
 
 
690
                // Rotate p down to the left until it has no right child, will get there
 
691
                // sooner or later.
 
692
                while(p->getRightChild())
 
693
                {
 
694
                        // "Pull up my right child and let it knock me down to the left"
 
695
                        rotateLeft(p);
 
696
                }
 
697
                // p now has no right child but might have a left child
 
698
                Node* left = p->getLeftChild();
 
699
 
 
700
                // Let p's parent point to p's child instead of point to p
 
701
                if (p->isLeftChild())
 
702
                        p->getParent()->setLeftChild(left);
 
703
 
 
704
                else if (p->isRightChild())
 
705
                        p->getParent()->setRightChild(left);
 
706
 
 
707
                else
 
708
                {
 
709
                        // p has no parent => p is the root.
 
710
                        // Let the left child be the new root.
 
711
                        setRoot(left);
 
712
                }
 
713
 
 
714
                // p is now gone from the tree in the sense that
 
715
                // no one is pointing at it. Let's get rid of it.
 
716
                delete p;
 
717
 
 
718
                --Size;
 
719
                return true;
 
720
        }
 
721
 
 
722
        //! Clear the entire tree
 
723
        void clear()
 
724
        {
 
725
                ParentLastIterator i(getParentLastIterator());
 
726
 
 
727
                while(!i.atEnd())
 
728
                {
 
729
                        Node* p = i.getNode();
 
730
                        i++; // Increment it before it is deleted
 
731
                                // else iterator will get quite confused.
 
732
                        delete p;
 
733
                }
 
734
                Root = 0;
 
735
                Size= 0;
 
736
        }
 
737
 
 
738
        //! Is the tree empty?
 
739
        //! \return Returns true if empty, false if not
 
740
        bool empty() const
 
741
        {
 
742
                _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
743
                return Root == 0;
 
744
        }
 
745
 
 
746
        //! \deprecated Use empty() instead. This method may be removed by Irrlicht 1.9 
 
747
        _IRR_DEPRECATED_ bool isEmpty() const
 
748
        {
 
749
                return empty();
 
750
        }
 
751
 
 
752
        //! Search for a node with the specified key.
 
753
        //! \param keyToFind: The key to find
 
754
        //! \return Returns 0 if node couldn't be found.
 
755
        Node* find(const KeyType& keyToFind) const
 
756
        {
 
757
                Node* pNode = Root;
 
758
 
 
759
                while(pNode!=0)
 
760
                {
 
761
                        KeyType key(pNode->getKey());
 
762
 
 
763
                        if (keyToFind == key)
 
764
                                return pNode;
 
765
                        else if (keyToFind < key)
 
766
                                pNode = pNode->getLeftChild();
 
767
                        else //keyToFind > key
 
768
                                pNode = pNode->getRightChild();
 
769
                }
 
770
 
 
771
                return 0;
 
772
        }
 
773
 
 
774
        //! Gets the root element.
 
775
        //! \return Returns a pointer to the root node, or
 
776
        //! 0 if the tree is empty.
 
777
        Node* getRoot() const
 
778
        {
 
779
                return Root;
 
780
        }
 
781
 
 
782
        //! Returns the number of nodes in the tree.
 
783
        u32 size() const
 
784
        {
 
785
                return Size;
 
786
        }
 
787
 
 
788
        //! Swap the content of this map container with the content of another map
 
789
        /** Afterwards this object will contain the content of the other object and the other
 
790
        object will contain the content of this object. Iterators will afterwards be valid for
 
791
        the swapped object.
 
792
        \param other Swap content with this object      */
 
793
        void swap(map<KeyType, ValueType>& other)
 
794
        {
 
795
                core::swap(Root, other.Root);
 
796
                core::swap(Size, other.Size);
 
797
        }
 
798
 
 
799
        //------------------------------
 
800
        // Public Iterators
 
801
        //------------------------------
 
802
 
 
803
        //! Returns an iterator
 
804
        Iterator getIterator()
 
805
        {
 
806
                Iterator it(getRoot());
 
807
                return it;
 
808
        }
 
809
        //! Returns a ParentFirstIterator.
 
810
        //! Traverses the tree from top to bottom. Typical usage is
 
811
        //! when storing the tree structure, because when reading it
 
812
        //! later (and inserting elements) the tree structure will
 
813
        //! be the same.
 
814
        ParentFirstIterator getParentFirstIterator()
 
815
        {
 
816
                ParentFirstIterator it(getRoot());
 
817
                return it;
 
818
        }
 
819
        //! Returns a ParentLastIterator to traverse the tree from
 
820
        //! bottom to top.
 
821
        //! Typical usage is when deleting all elements in the tree
 
822
        //! because you must delete the children before you delete
 
823
        //! their parent.
 
824
        ParentLastIterator getParentLastIterator()
 
825
        {
 
826
                ParentLastIterator it(getRoot());
 
827
                return it;
 
828
        }
 
829
 
 
830
        //------------------------------
 
831
        // Public Operators
 
832
        //------------------------------
 
833
 
 
834
        //! operator [] for access to elements
 
835
        /** for example myMap["key"] */
 
836
        AccessClass operator[](const KeyType& k)
 
837
        {
 
838
                return AccessClass(*this, k);
 
839
        }
 
840
        private:
 
841
 
 
842
        //------------------------------
 
843
        // Disabled methods
 
844
        //------------------------------
 
845
        // Copy constructor and assignment operator deliberately
 
846
        // defined but not implemented. The tree should never be
 
847
        // copied, pass along references to it instead.
 
848
        explicit map(const map& src);
 
849
        map& operator = (const map& src);
 
850
 
 
851
        //! Set node as new root.
 
852
        /** The node will be set to black, otherwise core dumps may arise
 
853
        (patch provided by rogerborg).
 
854
        \param newRoot Node which will be the new root
 
855
        */
 
856
        void setRoot(Node* newRoot)
 
857
        {
 
858
                Root = newRoot;
 
859
                if (Root != 0)
 
860
                {
 
861
                        Root->setParent(0);
 
862
                        Root->setBlack();
 
863
                }
 
864
        }
 
865
 
 
866
        //! Insert a node into the tree without using any fancy balancing logic.
 
867
        /** \return false if that key already exist in the tree. */
 
868
        bool insert(Node* newNode)
 
869
        {
 
870
                bool result=true; // Assume success
 
871
 
 
872
                if (Root==0)
 
873
                {
 
874
                        setRoot(newNode);
 
875
                        Size = 1;
 
876
                }
 
877
                else
 
878
                {
 
879
                        Node* pNode = Root;
 
880
                        KeyType keyNew = newNode->getKey();
 
881
                        while (pNode)
 
882
                        {
 
883
                                KeyType key(pNode->getKey());
 
884
 
 
885
                                if (keyNew == key)
 
886
                                {
 
887
                                        result = false;
 
888
                                        pNode = 0;
 
889
                                }
 
890
                                else if (keyNew < key)
 
891
                                {
 
892
                                        if (pNode->getLeftChild() == 0)
 
893
                                        {
 
894
                                                pNode->setLeftChild(newNode);
 
895
                                                pNode = 0;
 
896
                                        }
 
897
                                        else
 
898
                                                pNode = pNode->getLeftChild();
 
899
                                }
 
900
                                else // keyNew > key
 
901
                                {
 
902
                                        if (pNode->getRightChild()==0)
 
903
                                        {
 
904
                                                pNode->setRightChild(newNode);
 
905
                                                pNode = 0;
 
906
                                        }
 
907
                                        else
 
908
                                        {
 
909
                                                pNode = pNode->getRightChild();
 
910
                                        }
 
911
                                }
 
912
                        }
 
913
 
 
914
                        if (result)
 
915
                                ++Size;
 
916
                }
 
917
 
 
918
                _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
 
919
                return result;
 
920
        }
 
921
 
 
922
        //! Rotate left.
 
923
        //! Pull up node's right child and let it knock node down to the left
 
924
        void rotateLeft(Node* p)
 
925
        {
 
926
                Node* right = p->getRightChild();
 
927
 
 
928
                p->setRightChild(right->getLeftChild());
 
929
 
 
930
                if (p->isLeftChild())
 
931
                        p->getParent()->setLeftChild(right);
 
932
                else if (p->isRightChild())
 
933
                        p->getParent()->setRightChild(right);
 
934
                else
 
935
                        setRoot(right);
 
936
 
 
937
                right->setLeftChild(p);
 
938
        }
 
939
 
 
940
        //! Rotate right.
 
941
        //! Pull up node's left child and let it knock node down to the right
 
942
        void rotateRight(Node* p)
 
943
        {
 
944
                Node* left = p->getLeftChild();
 
945
 
 
946
                p->setLeftChild(left->getRightChild());
 
947
 
 
948
                if (p->isLeftChild())
 
949
                        p->getParent()->setLeftChild(left);
 
950
                else if (p->isRightChild())
 
951
                        p->getParent()->setRightChild(left);
 
952
                else
 
953
                        setRoot(left);
 
954
 
 
955
                left->setRightChild(p);
 
956
        }
 
957
 
 
958
        //------------------------------
 
959
        // Private Members
 
960
        //------------------------------
 
961
        Node* Root; // The top node. 0 if empty.
 
962
        u32 Size; // Number of nodes in the tree
 
963
};
 
964
 
 
965
} // end namespace core
 
966
} // end namespace irr
 
967
 
 
968
#endif // __IRR_MAP_H_INCLUDED__
 
969