My Project: dynamics.mod/NewtonDynamics/source/core/dgTree.h Source File

My Project

dgTree.h
Go to the documentation of this file.
1 /* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
2 *
3 * This software is provided 'as-is', without any express or implied
4 * warranty. In no event will the authors be held liable for any damages
5 * arising from the use of this software.
6 *
7 * Permission is granted to anyone to use this software for any purpose,
8 * including commercial applications, and to alter it and redistribute it
9 * freely, subject to the following restrictions:
10 *
11 * 1. The origin of this software must not be misrepresented; you must not
12 * claim that you wrote the original software. If you use this software
13 * in a product, an acknowledgment in the product documentation would be
14 * appreciated but is not required.
15 *
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 *
19 * 3. This notice may not be removed or altered from any source distribution.
20 */
21
22 #ifndef __dgTree__
23 #define __dgTree__
24
25 #include "dgStdafx.h"
26 #include "dgRef.h"
27 #include "dgDebug.h"
28 #include "dgMemory.h"
29
30
31
32 // Note: this is a low level class for dgTree use only
33 // unpredictable result will happen if you attempt to manipulate
34 // any member of this class
35 class dgRedBackNode
36 {
37 public:
38 enum REDBLACK_COLOR
39 {
40 RED = true,
41 BLACK = false
42 };
43
44 DG_CLASS_ALLOCATOR(allocator)
45
46 dgRedBackNode()
47 {
48 }
49
50 virtual ~dgRedBackNode ()
51 {
52 }
53
54 void RemoveAllLow ();
55 void RotateLeft(dgRedBackNode** const head);
56 void RotateRight(dgRedBackNode** const head);
57 void RemoveFixup (dgRedBackNode* const node, dgRedBackNode* * const head);
58
59 dgRedBackNode* GetLeft() const;
60 dgRedBackNode* GetRight() const;
61 dgRedBackNode* GetParent() const;
62
63 dgRedBackNode (dgRedBackNode* const parent);
64 inline void Initdata (dgRedBackNode* const parent);
65 inline void SetColor (REDBLACK_COLOR color);
66 REDBLACK_COLOR GetColor () const;
67 dgUnsigned32 IsInTree () const;
68 inline void SetInTreeFlag (dgUnsigned32 flag);
69
70 void RemoveAll ();
71 dgRedBackNode* Prev() const;
72 dgRedBackNode* Next() const;
73 dgRedBackNode* Minimum() const;
74 dgRedBackNode* Maximum() const;
75 void Remove (dgRedBackNode** const head);
76 void Unlink (dgRedBackNode** const head);
77 void InsertFixup(dgRedBackNode** const head);
78
79 dgRedBackNode* m_left;
80 dgRedBackNode* m_right;
81 dgRedBackNode* m_parent;
82 dgUnsigned32 m_color : 1;
83 dgUnsigned32 m_inTree : 1;
84 // dgUnsigned32 m_pad[2];
85 };
86
87 template<class OBJECT, class KEY>
88 class dgTree
89 {
90 public:
91 class dgTreeNode: public dgRedBackNode
92 {
93 dgTreeNode (
94 const OBJECT &info,
95 const KEY &key,
96 dgTreeNode* parentNode)
97 :dgRedBackNode(parentNode), m_info (info), m_key (key)
98 {
99 // dgAssert ((dgUnsigned64 (&m_info) & 0x0f) == 0);
100 }
101
102 ~dgTreeNode ()
103 {
104 }
105
106 dgTreeNode* GetLeft () const
107 {
108 return (dgTreeNode* )dgRedBackNode::m_left;
109 }
110
111 dgTreeNode* GetRight () const
112 {
113 return (dgTreeNode* )dgRedBackNode::m_right;
114 }
115
116 dgTreeNode* GetParent ()
117 {
118 return (dgTreeNode* )dgRedBackNode::m_parent;
119 }
120
121 void SetLeft (dgTreeNode* const node)
122 {
123 dgRedBackNode::m_left = node;
124 }
125
126 void SetRight (dgTreeNode* const node)
127 {
128 dgRedBackNode::m_right = node;
129 }
130
131 void SetParent (dgTreeNode* const node)
132 {
133 dgRedBackNode::m_parent = node;
134 }
135
136 public:
137 const KEY& GetKey() const
138 {
139 return m_key;
140 }
141
142 OBJECT& GetInfo()
143 {
144 return m_info;
145 }
146
147 private:
148 OBJECT m_info;
149 KEY m_key;
150 friend class dgTree<OBJECT, KEY>;
151
152 };
153
154 class Iterator
155 {
156
157 public:
158 Iterator(const dgTree<OBJECT,KEY> &me)
159 {
160 m_ptr = NULL;
161 m_tree = &me;
162 }
163
164 ~Iterator()
165 {
166 }
167
168 void Begin()
169 {
170 m_ptr = m_tree->Minimum();
171 }
172
173 void End()
174 {
175 m_ptr = m_tree->Maximum();
176 }
177
178 void Set (dgTreeNode* const node)
179 {
180 m_ptr = node;
181 }
182
183 operator dgInt32() const
184 {
185 return m_ptr != NULL;
186 }
187
188 void operator++ ()
189 {
190 dgAssert (m_ptr);
191 m_ptr = m_ptr->Next();
192 }
193
194 void operator++ (dgInt32)
195 {
196 dgAssert (m_ptr);
197 m_ptr = m_ptr->Next();
198 }
199
200 void operator-- ()
201 {
202 dgAssert (m_ptr);
203 m_ptr = m_ptr->Prev();
204 }
205
206 void operator-- (dgInt32)
207 {
208 dgAssert (m_ptr);
209 m_ptr = m_ptr->Prev();
210 }
211
212 OBJECT &operator* () const
213 {
214 return ((dgTreeNode*)m_ptr)->GetInfo();
215 }
216
217 dgTreeNode* GetNode() const
218 {
219 return (dgTreeNode*)m_ptr;
220 }
221
222 KEY GetKey () const
223 {
224 dgTreeNode* const tmp = (dgTreeNode*)m_ptr;
225 return tmp ? tmp->GetKey() : KEY(0);
226 }
227
228 private:
229 dgRedBackNode* m_ptr;
230 const dgTree* m_tree;
231
232 };
233
234
235 // ***********************************************************
236 // member functions
237 // ***********************************************************
238 public:
239 DG_CLASS_ALLOCATOR(allocator)
240
241 // dgTree ();
242 dgTree (dgMemoryAllocator* const allocator);
243 virtual ~dgTree ();
244
245 dgMemoryAllocator* GetAllocator () const;
246 void SetAllocator (dgMemoryAllocator* const allocator);
247
248
249 operator dgInt32() const;
250 dgInt32 GetCount() const;
251
252 dgTreeNode* GetRoot () const;
253 dgTreeNode* Minimum () const;
254 dgTreeNode* Maximum () const;
255
256 dgTreeNode* Find (KEY key) const;
257 dgTreeNode* FindGreater (KEY key) const;
258 dgTreeNode* FindGreaterEqual (KEY key) const;
259 dgTreeNode* FindLessEqual (KEY key) const;
260
261 dgTreeNode* GetNodeFromInfo (OBJECT &info) const;
262
263 dgTreeNode* Insert (const OBJECT &element, KEY key, bool& elementWasInTree);
264 dgTreeNode* Insert (const OBJECT &element, KEY key);
265 dgTreeNode* Insert (dgTreeNode* const node, KEY key);
266
267 dgTreeNode* Replace (OBJECT &element, KEY key);
268 dgTreeNode* ReplaceKey (KEY oldKey, KEY newKey);
269 dgTreeNode* ReplaceKey (dgTreeNode* const node, KEY key);
270
271 void Remove (KEY key);
272 void Remove (dgTreeNode* const node);
273 void RemoveAll ();
274
275 void Unlink (dgTreeNode* const node);
276 void SwapInfo (dgTree& tree);
277
278 bool SanityCheck () const;
279
280 // ***********************************************************
281 // member variables
282 // ***********************************************************
283 private:
284 dgInt32 m_count;
285 dgTreeNode* m_head;
286 dgMemoryAllocator* m_allocator;
287
288 dgInt32 CompareKeys (const KEY &key0, const KEY &key1) const;
289 bool SanityCheck (dgTreeNode* const ptr, dgInt32 height) const;
290
291 friend class dgTreeNode;
292 };
293
294
295 inline dgRedBackNode::dgRedBackNode (dgRedBackNode* const parent)
296 {
297 Initdata (parent);
298 }
299
300 inline void dgRedBackNode::Initdata (dgRedBackNode* const parent)
301 {
302 SetColor (RED);
303 SetInTreeFlag (true);
304 m_left = NULL;
305 m_right = NULL;
306 m_parent = parent;
307 }
308
309 inline void dgRedBackNode::SetColor (dgRedBackNode::REDBLACK_COLOR color)
310 {
311 m_color = color;
312 }
313
314
315
316 inline dgRedBackNode::REDBLACK_COLOR dgRedBackNode::GetColor () const
317 {
318 return REDBLACK_COLOR (m_color);
319 }
320
321
322 inline void dgRedBackNode::SetInTreeFlag (dgUnsigned32 flag)
323 {
324 m_inTree = flag;
325 }
326
327 inline dgUnsigned32 dgRedBackNode::IsInTree () const
328 {
329 return m_inTree;
330 }
331
332 /*
333 template<class OBJECT, class KEY>
334 dgTree<OBJECT, KEY>::dgTree ()
335 {
336 m_count = 0;
337 m_head = NULL;
338 m_allocator = NULL;
339 }
340 */
341
342 template<class OBJECT, class KEY>
343 dgTree<OBJECT, KEY>::dgTree (dgMemoryAllocator* const allocator)
344 :m_count(0)
345 ,m_head(NULL)
346 ,m_allocator(allocator)
347 {
348 }
349
350
351 template<class OBJECT, class KEY>
352 dgTree<OBJECT, KEY>::~dgTree ()
353 {
354 RemoveAll();
355 }
356
357 template<class OBJECT, class KEY>
358 dgMemoryAllocator* dgTree<OBJECT, KEY>::GetAllocator () const
359 {
360 return m_allocator;
361 }
362
363 template<class OBJECT, class KEY>
364 void dgTree<OBJECT, KEY>::SetAllocator (dgMemoryAllocator* const allocator)
365 {
366 if ((m_count == 0) && (m_allocator == NULL)) {
367 m_allocator = allocator;
368 }
369 }
370
371
372 template<class OBJECT, class KEY>
373 dgTree<OBJECT, KEY>::operator dgInt32() const
374 {
375 return m_head != NULL;
376 }
377
378 template<class OBJECT, class KEY>
379 dgInt32 dgTree<OBJECT, KEY>::GetCount() const
380 {
381 return m_count;
382 }
383
384 template<class OBJECT, class KEY>
385 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Minimum () const
386 {
387 return m_head ? (dgTreeNode* )m_head->Minimum() : NULL;
388 }
389
390 template<class OBJECT, class KEY>
391 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Maximum () const
392 {
393 return m_head ? (dgTreeNode* )m_head->Maximum() : NULL;
394 }
395
396 template<class OBJECT, class KEY>
397 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::GetRoot () const
398 {
399 return m_head;
400 }
401
402 template<class OBJECT, class KEY>
403 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Find (KEY key) const
404 {
405 if (m_head == NULL) {
406 return NULL;
407 }
408
409 dgTreeNode* ptr = m_head;
410 while (ptr != NULL) {
411 if (key < ptr->m_key) {
412 dgAssert (CompareKeys (ptr->m_key, key) == -1) ;
413 ptr = ptr->GetLeft();
414 } else if (key > ptr->m_key) {
415 dgAssert (CompareKeys (ptr->m_key, key) == 1) ;
416 ptr = ptr->GetRight();
417 } else {
418 dgAssert (CompareKeys (ptr->m_key, key) == 0) ;
419 break;
420 }
421 }
422 return ptr;
423 }
424
425 template<class OBJECT, class KEY>
426 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::GetNodeFromInfo (OBJECT &info) const
427 {
428 dgTreeNode* const node = (dgTreeNode* ) &info;
429 dgInt64 offset = ((char*) &node->m_info) - ((char *) node);
430 dgTreeNode* const retnode = (dgTreeNode* ) (((char *) node) - offset);
431
432 dgAssert (retnode->IsInTree ());
433 dgAssert (&retnode->GetInfo () == &info);
434 return (retnode->IsInTree ()) ? retnode : NULL;
435
436 }
437
438 template<class OBJECT, class KEY>
439 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::FindGreater (KEY key) const
440 {
441 if (m_head == NULL) {
442 return NULL;
443 }
444
445 dgTreeNode* prev = NULL;
446 dgTreeNode* ptr = m_head;
447
448 while (ptr != NULL) {
449 if (key < ptr->m_key) {
450 prev = ptr;
451 ptr = ptr->GetLeft();
452 } else {
453 ptr = ptr->GetRight();
454 }
455 }
456
457 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
458 if (prev) {
459 Iterator iter (*this);
460 for (iter.Begin(); iter.GetNode() != prev; iter ++) {
461 KEY key1 = iter.GetKey();
462 dgAssert (key1 <= key);
463 }
464 for (; iter.GetNode(); iter ++) {
465 KEY key1 = iter.GetKey();
466 dgAssert (key1 > key);
467 }
468 }
469 #endif
470
471 return (dgTreeNode* )prev;
472 }
473
474 template<class OBJECT, class KEY>
475 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::FindGreaterEqual (KEY key) const
476 {
477 if (m_head == NULL) {
478 return NULL;
479 }
480
481 dgTreeNode* prev = NULL;
482 dgTreeNode* ptr = m_head;
483
484 while (ptr != NULL) {
485 if (key == ptr->m_key) {
486 return ptr;
487 }
488 if (key < ptr->m_key) {
489 prev = ptr;
490 ptr = ptr->GetLeft();
491 } else {
492 ptr = ptr->GetRight();
493 }
494 }
495
496 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
497 if (prev) {
498 Iterator iter (*this);
499 for (iter.Begin(); iter.GetNode() != prev; iter ++) {
500 KEY key1 = iter.GetKey();
501 dgAssert (key1 <= key);
502 }
503 for (; iter.GetNode(); iter ++) {
504 KEY key1 = iter.GetKey();
505 dgAssert (key1 >= key);
506 }
507 }
508 #endif
509
510 return (dgTreeNode* )prev;
511 }
512
513 template<class OBJECT, class KEY>
514 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::FindLessEqual (KEY key) const
515 {
516 if (m_head == NULL) {
517 return NULL;
518 }
519
520 dgTreeNode* prev = NULL;
521 dgTreeNode* ptr = m_head;
522
523 while (ptr != NULL) {
524 if (key == ptr->m_key) {
525 return ptr;
526 }
527
528 if (key < ptr->m_key) {
529 ptr = ptr->GetLeft();
530 } else {
531 prev = ptr;
532 ptr = ptr->GetRight();
533 }
534
535 }
536
537 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
538 if (prev) {
539 Iterator iter (*this);
540 for (iter.End(); iter.GetNode() != prev; iter --) {
541 KEY key1 = iter.GetKey();
542 dgAssert (key1 >= key);
543 }
544 for (; iter.GetNode(); iter --) {
545 KEY key1 = iter.GetKey();
546 dgAssert (key1 < key);
547 }
548 }
549 #endif
550
551 return (dgTreeNode* )prev;
552 }
553
554 template<class OBJECT, class KEY>
555 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Insert (const OBJECT &element, KEY key, bool& elementWasInTree)
556 {
557 dgTreeNode* parent = NULL;
558 dgTreeNode* ptr = m_head;
559 dgInt32 val = 0;
560 elementWasInTree = false;
561 while (ptr != NULL) {
562 parent = ptr;
563
564 if (key < ptr->m_key) {
565 dgAssert (CompareKeys (ptr->m_key, key) == -1) ;
566 val = -1;
567 ptr = ptr->GetLeft();
568 } else if (key > ptr->m_key) {
569 dgAssert (CompareKeys (ptr->m_key, key) == 1) ;
570 val = 1;
571 ptr = ptr->GetRight();
572 } else {
573 dgAssert (CompareKeys (ptr->m_key, key) == 0) ;
574 elementWasInTree = true;
575 return ptr;
576 }
577 }
578
579 m_count ++;
580 dgAssert (m_allocator);
581 ptr = new (m_allocator) dgTreeNode (element, key, parent);
582 if (!parent) {
583 m_head = ptr;
584 } else {
585 if (val < 0) {
586 parent->m_left = ptr;
587 } else {
588 parent->m_right = ptr;
589 }
590 }
591
592 dgTreeNode** const headPtr = (dgTreeNode**) &m_head;
593 // ptr->InsertFixup ((dgRedBackNode**)&m_head);
594 ptr->InsertFixup ((dgRedBackNode**)headPtr);
595 return ptr;
596 }
597
598 template<class OBJECT, class KEY>
599 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Insert (const OBJECT &element, KEY key)
600 {
601 bool foundState;
602
603 dgTreeNode* const node = Insert (element, key, foundState);
604 if (foundState) {
605 return NULL;
606 }
607 return node;
608 }
609
610 template<class OBJECT, class KEY>
611 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Insert (typename dgTree<OBJECT, KEY>::dgTreeNode* const node, KEY key)
612 {
613 dgInt32 val = 0;
614 dgTreeNode* ptr = m_head;
615 dgTreeNode* parent = NULL;
616 while (ptr != NULL) {
617 parent = ptr;
618 // val = CompareKeys (ptr->m_key, key);
619 // if (val < 0) {
620 // ptr = ptr->GetLeft();
621 // } else if (val > 0) {
622 // ptr = ptr->GetRight();
623 // } else {
624 // return NULL;
625 // }
626
627 if (key < ptr->m_key) {
628 dgAssert (CompareKeys (ptr->m_key, key) == -1) ;
629 val = -1;
630 ptr = ptr->GetLeft();
631 } else if (key > ptr->m_key) {
632 dgAssert (CompareKeys (ptr->m_key, key) == 1) ;
633 val = 1;
634 ptr = ptr->GetRight();
635 } else {
636 dgAssert (CompareKeys (ptr->m_key, key) == 0) ;
637 return NULL;
638 }
639 }
640
641 m_count ++;
642
643 ptr = node;
644 ptr->m_key = key;
645 ptr->Initdata (parent);
646
647 if (!parent) {
648 m_head = ptr;
649 } else {
650 if (val < 0) {
651 parent->m_left = ptr;
652 } else {
653 parent->m_right = ptr;
654 }
655 }
656
657 dgTreeNode** const headPtr = (dgTreeNode**) &m_head;
658 // ptr->InsertFixup ((dgRedBackNode**)&m_head);
659 ptr->InsertFixup ((dgRedBackNode**)headPtr);
660 return ptr;
661 }
662
663
664 template<class OBJECT, class KEY>
665 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::Replace (OBJECT &element, KEY key)
666 {
667 dgTreeNode* parent = NULL;
668 dgTreeNode* ptr = m_head;
669 dgInt32 val = 0;
670 while (ptr != NULL) {
671 parent = ptr;
672
673 dgAssert (0);
674 val = CompareKeys (ptr->m_key, key);
675 if (val == 0) {
676 ptr->m_info = element;
677 return ptr;
678 }
679 if (val < 0) {
680 ptr = ptr->GetLeft();
681 } else {
682 ptr = ptr->GetRight();
683 }
684 }
685
686 dgAssert (m_allocator);
687 ptr = new (m_allocator) dgTreeNode (element, key, parent);
688 if (!parent) {
689 m_head = ptr;
690 } else {
691 if (val < 0) {
692 parent->m_left = ptr;
693 } else {
694 parent->m_right = ptr;
695 }
696 }
697
698 dgTreeNode** const headPtr = (dgTreeNode**) &m_head;
699 // ptr->InsertFixup ((dgRedBackNode**)&m_head);
700 ptr->InsertFixup ((dgRedBackNode**)headPtr );
701 return ptr;
702 }
703
704
705 template<class OBJECT, class KEY>
706 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::ReplaceKey (typename dgTree<OBJECT, KEY>::dgTreeNode* const node, KEY key)
707 {
708 Unlink (node);
709 dgTreeNode* const ptr = Insert (node, key);
710 dgAssert (ptr);
711 return ptr;
712 }
713
714 template<class OBJECT, class KEY>
715 typename dgTree<OBJECT, KEY>::dgTreeNode* dgTree<OBJECT, KEY>::ReplaceKey (KEY oldKey, KEY newKey)
716 {
717 dgTreeNode* const node = Find (oldKey);
718 return node ? ReplaceKey (node, newKey) : NULL;
719 }
720
721 template<class OBJECT, class KEY>
722 void dgTree<OBJECT, KEY>::Unlink (typename dgTree<OBJECT, KEY>::dgTreeNode* const node)
723 {
724 m_count --;
725
726 dgTreeNode** const headPtr = (dgTreeNode**) &m_head;
727 node->Unlink ((dgRedBackNode**)headPtr);
728 dgAssert (!Find (node->GetKey()));
729 }
730
731
732 template<class OBJECT, class KEY>
733 void dgTree<OBJECT, KEY>::Remove (typename dgTree<OBJECT, KEY>::dgTreeNode* const node)
734 {
735 m_count --;
736 dgTreeNode** const headPtr = (dgTreeNode**) &m_head;
737 node->Remove ((dgRedBackNode**)headPtr);
738 }
739
740 template<class OBJECT, class KEY>
741 void dgTree<OBJECT, KEY>::Remove (KEY key)
742 {
743 dgTreeNode* node;
744
745 // find node in tree
746 node = Find (key);
747 if (node == NULL) {
748 return;
749 }
750 Remove (node);
751 }
752
753 template<class OBJECT, class KEY>
754 void dgTree<OBJECT, KEY>::RemoveAll ()
755 {
756 if (m_head) {
757 m_count = 0;
758 m_head->RemoveAll ();
759 m_head = NULL;
760 }
761 }
762
763 template<class OBJECT, class KEY>
764 bool dgTree<OBJECT, KEY>::SanityCheck () const
765 {
766 return SanityCheck (m_head, 0);
767 }
768
769
770 template<class OBJECT, class KEY>
771 bool dgTree<OBJECT, KEY>::SanityCheck (typename dgTree<OBJECT, KEY>::dgTreeNode* const ptr, dgInt32 height) const
772 {
773 if (!ptr) {
774 return true;
775 }
776
777 if (!ptr->IsInTree()) {
778 return false;
779 }
780
781 if (ptr->m_left) {
782 if (CompareKeys (ptr->m_key, ptr->GetLeft()->m_key) > 0) {
783 return false;
784 }
785 }
786
787 if (ptr->m_right) {
788 if (CompareKeys (ptr->m_key, ptr->GetRight()->m_key) < 0) {
789 return false;
790 }
791 }
792
793 if (ptr->GetColor() == dgTreeNode::BLACK) {
794 height ++;
795 } else if (!((!ptr->m_left || (ptr->m_left->GetColor() == dgTreeNode::BLACK)) &&
796 (!ptr->m_right || (ptr->m_right->GetColor() == dgTreeNode::BLACK)))) {
797 return false;
798 }
799
800 if (!ptr->m_left && !ptr->m_right) {
801 dgInt32 bh = 0;
802 for (dgTreeNode* x = ptr; x; x = x->GetParent()) {
803 if (x->GetColor() == dgTreeNode::BLACK) {
804 bh ++;
805 }
806 }
807 if (bh != height) {
808 return false;
809 }
810 }
811
812 if (ptr->m_left && !SanityCheck (ptr->GetLeft(), height)) {
813 return false;
814 }
815
816 if (ptr->m_right && !SanityCheck (ptr->GetRight(), height)) {
817 return false;
818 }
819 return true;
820 }
821
822
823 template<class OBJECT, class KEY>
824 dgInt32 dgTree<OBJECT, KEY>::CompareKeys (const KEY &key0, const KEY &key1) const
825 {
826 if (key1 < key0) {
827 return - 1;
828 }
829 if (key1 > key0) {
830 return 1;
831 }
832 return 0;
833 }
834
835 template<class OBJECT, class KEY>
836 void dgTree<OBJECT, KEY>::SwapInfo (dgTree<OBJECT, KEY>& tree)
837 {
838 dgSwap (m_head, tree.m_head);
839 dgSwap (m_count, tree.m_count);
840 }
841
842 //template<class OBJECT, class KEY> dgInt32 dgTree<OBJECT,KEY>::m_size = 0;
843 //template<class OBJECT, class KEY> dgMemoryAllocator* dgTree<OBJECT,KEY>::m_staticAllocator = NULL;
844
845
846 #endif
847
848
dgRedBackNode::GetColor
REDBLACK_COLOR GetColor() const
Definition: dgTree.h:316
dgTree::Find
dgTreeNode * Find(KEY key) const
Definition: dgTree.h:403
dgTree::dgTreeNode
Definition: dgTree.h:91
dgTree::Insert
dgTreeNode * Insert(const OBJECT &element, KEY key, bool &elementWasInTree)
Definition: dgTree.h:555
dgInt64
long long dgInt64
Definition: dgTypes.h:222
dgRedBackNode::dgRedBackNode
dgRedBackNode()
Definition: dgTree.h:46
dgMemory.h
dgRedBackNode::Unlink
void Unlink(dgRedBackNode **const head)
Definition: dgTree.cpp:301
dgTree::SwapInfo
void SwapInfo(dgTree &tree)
Definition: dgTree.h:836
dgRedBackNode::GetLeft
dgRedBackNode * GetLeft() const
dgRedBackNode::BLACK
Definition: dgTree.h:41
dgTree::Iterator::~Iterator
~Iterator()
Definition: dgTree.h:164
dgDebug.h
dgRedBackNode::RemoveAll
void RemoveAll()
Definition: dgTree.cpp:416
dgTree::dgTreeNode
friend class dgTreeNode
Definition: dgTree.h:291
dgTree::Maximum
dgTreeNode * Maximum() const
Definition: dgTree.h:391
dgAssert
#define dgAssert(x)
Definition: dgTypes.h:158
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgTree::FindLessEqual
dgTreeNode * FindLessEqual(KEY key) const
Definition: dgTree.h:514
dgTree::GetRoot
dgTreeNode * GetRoot() const
Definition: dgTree.h:397
dgRedBackNode::RemoveFixup
void RemoveFixup(dgRedBackNode *const node, dgRedBackNode **const head)
Definition: dgTree.cpp:201
dgSwap
DG_INLINE void dgSwap(T &A, T &B)
Definition: dgTypes.h:323
dgRedBackNode::m_right
dgRedBackNode * m_right
Definition: dgTree.h:80
dgRedBackNode::Minimum
dgRedBackNode * Minimum() const
Definition: dgTree.cpp:26
dgRedBackNode::IsInTree
dgUnsigned32 IsInTree() const
Definition: dgTree.h:327
dgRedBackNode::SetColor
void SetColor(REDBLACK_COLOR color)
Definition: dgTree.h:309
dgRedBackNode::SetInTreeFlag
void SetInTreeFlag(dgUnsigned32 flag)
Definition: dgTree.h:322
dgRedBackNode::RotateRight
void RotateRight(dgRedBackNode **const head)
Definition: dgTree.cpp:107
DG_CLASS_ALLOCATOR
#define DG_CLASS_ALLOCATOR(allocator)
Definition: dgMemory.h:60
dgRedBackNode::GetRight
dgRedBackNode * GetRight() const
dgRedBackNode::m_color
dgUnsigned32 m_color
Definition: dgTree.h:82
dgTree::Unlink
void Unlink(dgTreeNode *const node)
Definition: dgTree.h:722
dgRedBackNode::m_inTree
dgUnsigned32 m_inTree
Definition: dgTree.h:83
dgRedBackNode::GetParent
dgRedBackNode * GetParent() const
dgTree
Definition: dgTree.h:88
dgRedBackNode::RotateLeft
void RotateLeft(dgRedBackNode **const head)
Definition: dgTree.cpp:72
dgTree::FindGreaterEqual
dgTreeNode * FindGreaterEqual(KEY key) const
Definition: dgTree.h:475
dgTree::Remove
void Remove(KEY key)
Definition: dgTree.h:741
dgTree::dgTreeNode::GetInfo
OBJECT & GetInfo()
Definition: dgTree.h:142
dgStdafx.h
dgTree::Minimum
dgTreeNode * Minimum() const
Definition: dgTree.h:385
dgTree::Iterator::Iterator
Iterator(const dgTree< OBJECT, KEY > &me)
Definition: dgTree.h:158
dgTree::Iterator::Begin
void Begin()
Definition: dgTree.h:168
dgTree::dgTreeNode::GetKey
const KEY & GetKey() const
Definition: dgTree.h:137
dgTree::FindGreater
dgTreeNode * FindGreater(KEY key) const
Definition: dgTree.h:439
dgTree::Iterator::GetKey
KEY GetKey() const
Definition: dgTree.h:222
dgUnsigned32
unsigned dgUnsigned32
Definition: dgTypes.h:219
dgRedBackNode::RED
Definition: dgTree.h:40
iter
int iter
Definition: benchtest1.c:63
dgTree::GetAllocator
dgMemoryAllocator * GetAllocator() const
Definition: dgTree.h:358
dgTree::SetAllocator
void SetAllocator(dgMemoryAllocator *const allocator)
Definition: dgTree.h:364
dgRedBackNode::InsertFixup
void InsertFixup(dgRedBackNode **const head)
Definition: dgTree.cpp:142
dgTree::Iterator
Definition: dgTree.h:154
dgRedBackNode::Maximum
dgRedBackNode * Maximum() const
Definition: dgTree.cpp:33
dgRedBackNode::m_parent
dgRedBackNode * m_parent
Definition: dgTree.h:81
dgTree::Iterator::Set
void Set(dgTreeNode *const node)
Definition: dgTree.h:178
dgTree::Replace
dgTreeNode * Replace(OBJECT &element, KEY key)
Definition: dgTree.h:665
dgRedBackNode::REDBLACK_COLOR
REDBLACK_COLOR
Definition: dgTree.h:38
dgMemoryAllocator
Definition: dgMemory.h:73
dgRedBackNode
Definition: dgTree.h:35
dgRedBackNode::Prev
dgRedBackNode * Prev() const
Definition: dgTree.cpp:41
dgRedBackNode::Initdata
void Initdata(dgRedBackNode *const parent)
Definition: dgTree.h:300
dgRedBackNode::Next
dgRedBackNode * Next() const
Definition: dgTree.cpp:56
dgTree::Iterator::GetNode
dgTreeNode * GetNode() const
Definition: dgTree.h:217
dgTree::GetNodeFromInfo
dgTreeNode * GetNodeFromInfo(OBJECT &info) const
Definition: dgTree.h:426
dgRedBackNode::~dgRedBackNode
virtual ~dgRedBackNode()
Definition: dgTree.h:50
dgRedBackNode::m_left
dgRedBackNode * m_left
Definition: dgTree.h:79
dgRedBackNode::Remove
void Remove(dgRedBackNode **const head)
Definition: dgTree.cpp:396
dgTree::SanityCheck
bool SanityCheck() const
Definition: dgTree.h:764
dgTree::dgTree
dgTree(dgMemoryAllocator *const allocator)
Definition: dgTree.h:343
dgRedBackNode::RemoveAllLow
void RemoveAllLow()
Definition: dgTree.cpp:402
dgTree::ReplaceKey
dgTreeNode * ReplaceKey(KEY oldKey, KEY newKey)
Definition: dgTree.h:715
dgTree::GetCount
dgInt32 GetCount() const
Definition: dgTree.h:379
dgTree::Iterator::End
void End()
Definition: dgTree.h:173
dgTree::RemoveAll
void RemoveAll()
Definition: dgTree.h:754
dgRef.h
dgTree::~dgTree
virtual ~dgTree()
Definition: dgTree.h:352