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