diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/irrlicht-1.8/include/irrMap.h | 2254 |
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 | ||
11 | namespace irr | 11 | namespace irr |
12 | { | 12 | { |
13 | namespace core | 13 | namespace 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 |
17 | template <class KeyType, class ValueType> | 17 | template <class KeyType, class ValueType> |
18 | class map | 18 | class 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 | ||