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

My Project

dgList.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 __dgList__
23 #define __dgList__
24
25 #include "dgStdafx.h"
26 #include "dgRef.h"
27 #include "dgDebug.h"
28 #include "dgMemory.h"
29
30
31
32 template<class T>
33 class dgList
34 {
35 public:
36 class dgListNode
37 {
38 DG_CLASS_ALLOCATOR(allocator)
39
40 dgListNode (dgListNode* const prev, dgListNode* const next)
41 :m_info ()
42 {
43 // dgAssert ((dgUnsigned64 (&m_info) & 0x0f) == 0);
44 m_prev = prev;
45 m_next = next;
46 if (m_prev) {
47 m_prev->m_next = this;
48 }
49 if (m_next) {
50 m_next->m_prev = this;
51 }
52 }
53
54 dgListNode (const T &info, dgListNode* const prev, dgListNode* const next)
55 :m_info (info)
56 {
57 m_prev = prev;
58 m_next = next;
59 if (m_prev) {
60 m_prev->m_next = this;
61 }
62 if (m_next) {
63 m_next->m_prev = this;
64 }
65 }
66
67 virtual ~dgListNode()
68 {
69 }
70
71 void Unlink ()
72 {
73 if (m_prev) {
74 m_prev->m_next = m_next;
75 }
76
77 if (m_next) {
78 m_next->m_prev = m_prev;
79 }
80 m_prev = NULL;
81 m_next = NULL;
82 }
83
84 void AddLast(dgListNode* const node)
85 {
86 m_next = node;
87 node->m_prev = this;
88 }
89
90 void AddFirst(dgListNode* const node)
91 {
92 m_prev = node;
93 node->m_next = this;
94 }
95
96 public:
97 T& GetInfo()
98 {
99 return m_info;
100 }
101
102 dgListNode *GetNext() const
103 {
104 return m_next;
105 }
106
107 dgListNode *GetPrev() const
108 {
109 return m_prev;
110 }
111
112 private:
113 T m_info;
114 dgListNode *m_next;
115 dgListNode *m_prev;
116 friend class dgList<T>;
117
118 };
119
120 class Iterator
121 {
122 public:
123 Iterator (const dgList<T> &me)
124 {
125 m_ptr = NULL;
126 m_list = (dgList *)&me;
127 }
128
129 ~Iterator ()
130 {
131 }
132
133 operator dgInt32() const
134 {
135 return m_ptr != NULL;
136 }
137
138 bool operator== (const Iterator &target) const
139 {
140 return (m_ptr == target.m_ptr) && (m_list == target.m_list);
141 }
142
143 void Begin()
144 {
145 m_ptr = m_list->GetFirst();
146 }
147
148 void End()
149 {
150 m_ptr = m_list->GetLast();
151 }
152
153 void Set (dgListNode* const node)
154 {
155 m_ptr = node;
156 }
157
158 void operator++ ()
159 {
160 dgAssert (m_ptr);
161 m_ptr = m_ptr->m_next();
162 }
163
164 void operator++ (dgInt32)
165 {
166 dgAssert (m_ptr);
167 m_ptr = m_ptr->GetNext();
168 }
169
170 void operator-- ()
171 {
172 dgAssert (m_ptr);
173 m_ptr = m_ptr->GetPrev();
174 }
175
176 void operator-- (dgInt32)
177 {
178 dgAssert (m_ptr);
179 m_ptr = m_ptr->GetPrev();
180 }
181
182 T &operator* () const
183 {
184 return m_ptr->GetInfo();
185 }
186
187 dgListNode *GetNode() const
188 {
189 return m_ptr;
190 }
191
192 private:
193 dgList *m_list;
194 dgListNode *m_ptr;
195 };
196
197 // ***********************************************************
198 // member functions
199 // ***********************************************************
200 public:
201 DG_CLASS_ALLOCATOR(allocator)
202
203 // dgList ();
204 dgList (dgMemoryAllocator* const allocator);
205 virtual ~dgList ();
206
207 dgMemoryAllocator* GetAllocator () const;
208 void SetAllocator (dgMemoryAllocator* const allocator);
209
210 operator dgInt32() const;
211 dgInt32 GetCount() const;
212 dgListNode *GetLast() const;
213 dgListNode *GetFirst() const;
214 dgListNode *Append ();
215 dgListNode *Append (dgListNode* const node);
216 dgListNode *Append (const T &element);
217 dgListNode *Addtop ();
218 dgListNode *Addtop (dgListNode* const node);
219 dgListNode *Addtop (const T &element);
220
221 void RotateToEnd (dgListNode* const node);
222 void RotateToBegin (dgListNode* const node);
223 void InsertAfter (dgListNode* const root, dgListNode* const node);
224 void InsertBefore (dgListNode* const root, dgListNode* const node);
225
226
227 dgListNode *Find (const T &element) const;
228 dgListNode *GetNodeFromInfo (T &m_info) const;
229 void Remove (dgListNode* const node);
230 void Remove (const T &element);
231 void RemoveAll ();
232
233 void Merge (dgList<T>& list);
234 void Unlink (dgListNode* const node);
235 bool SanityCheck () const;
236
237
238 // ***********************************************************
239 // member variables
240 // ***********************************************************
241 private:
242 dgInt32 m_count;
243 dgListNode *m_first;
244 dgListNode *m_last;
245 dgMemoryAllocator* m_allocator;
246
247 // static dgInt32 m_size;
248 // static dgMemoryAllocator* m_staticAllocator;
249 friend class dgListNode;
250 };
251
252 /*
253 template<class T>
254 dgList<T>::dgList ()
255 {
256 m_count = 0;
257 m_first = NULL;
258 m_last = NULL;
259 m_allocator = NULL;
260 }
261 */
262
263 template<class T>
264 dgList<T>::dgList (dgMemoryAllocator* const allocator)
265 :m_count(0)
266 ,m_first(NULL)
267 ,m_last(NULL)
268 ,m_allocator(allocator)
269 {
270 }
271
272
273 template<class T>
274 dgList<T>::~dgList ()
275 {
276 RemoveAll ();
277 }
278
279 template<class T>
280 void dgList<T>::SetAllocator (dgMemoryAllocator* const allocator)
281 {
282 if ((m_count == 0) && (m_allocator == NULL)) {
283 m_allocator = allocator;
284 }
285 }
286
287 template<class T>
288 dgMemoryAllocator* dgList<T>::GetAllocator () const
289 {
290 return m_allocator;
291 }
292
293
294 template<class T>
295 dgInt32 dgList<T>::GetCount() const
296 {
297 return m_count;
298 }
299
300 template<class T>
301 dgList<T>::operator dgInt32() const
302 {
303 return m_first != NULL;
304 }
305
306 template<class T>
307 typename dgList<T>::dgListNode *dgList<T>::GetFirst() const
308 {
309 return m_first;
310 }
311
312 template<class T>
313 typename dgList<T>::dgListNode *dgList<T>::GetLast() const
314 {
315 return m_last;
316 }
317
318 template<class T>
319 typename dgList<T>::dgListNode *dgList<T>::Append (dgListNode* const node)
320 {
321 dgAssert (node->m_next == NULL);
322 dgAssert (node->m_prev == NULL);
323 m_count ++;
324 if (m_first == NULL) {
325 m_last = node;
326 m_first = node;
327 } else {
328 m_last->AddLast (node);
329 m_last = node;
330 }
331 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
332 dgAssert (SanityCheck ());
333 #endif
334 return m_last;
335 }
336
337 template<class T>
338 typename dgList<T>::dgListNode *dgList<T>::Append ()
339 {
340 m_count ++;
341 if (m_first == NULL) {
342 m_first = new (m_allocator) dgListNode(NULL, NULL);
343 m_last = m_first;
344 } else {
345 m_last = new (m_allocator) dgListNode(m_last, NULL);
346 }
347 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
348 dgAssert (SanityCheck ());
349 #endif
350 return m_last;
351 }
352
353 template<class T>
354 typename dgList<T>::dgListNode *dgList<T>::Append (const T &element)
355 {
356 m_count ++;
357 if (m_first == NULL) {
358 m_first = new (m_allocator) dgListNode(element, NULL, NULL);
359 m_last = m_first;
360 } else {
361 m_last = new (m_allocator) dgListNode(element, m_last, NULL);
362 }
363 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
364 dgAssert (SanityCheck ());
365 #endif
366
367 return m_last;
368 }
369
370 template<class T>
371 typename dgList<T>::dgListNode *dgList<T>::Addtop (dgListNode* const node)
372 {
373 dgAssert (node->m_next == NULL);
374 dgAssert (node->m_prev == NULL);
375 m_count ++;
376 if (m_last == NULL) {
377 m_last = node;
378 m_first = node;
379 } else {
380 m_first->AddFirst(node);
381 m_first = node;
382 }
383 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
384 dgAssert (SanityCheck ());
385 #endif
386 return m_first;
387 }
388
389
390 template<class T>
391 typename dgList<T>::dgListNode *dgList<T>::Addtop ()
392 {
393 m_count ++;
394 if (m_last == NULL) {
395 m_last = new (m_allocator) dgListNode(NULL, NULL);
396 m_first = m_last;
397 } else {
398 m_first = new (m_allocator) dgListNode(NULL, m_first);
399 }
400 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
401 dgAssert (SanityCheck ());
402 #endif
403 return m_first;
404 }
405
406
407 template<class T>
408 typename dgList<T>::dgListNode *dgList<T>::Addtop (const T &element)
409 {
410 m_count ++;
411 if (m_last == NULL) {
412 m_last = new (m_allocator) dgListNode(element, NULL, NULL);
413 m_first = m_last;
414 } else {
415 m_first = new (m_allocator) dgListNode(element, NULL, m_first);
416 }
417 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
418 dgAssert (SanityCheck ());
419 #endif
420 return m_first;
421 }
422
423 template<class T>
424 void dgList<T>::InsertAfter (dgListNode* const root, dgListNode* const node)
425 {
426 dgAssert (root);
427 dgAssert (node != root);
428
429 if (root->m_next != node) {
430 if (node == m_first) {
431 m_first = node->m_next;
432 }
433 if (node == m_last) {
434 m_last = node->m_prev;
435 }
436 node->Unlink ();
437
438 node->m_prev = root;
439 node->m_next = root->m_next;
440 if (root->m_next) {
441 root->m_next->m_prev = node;
442 }
443 root->m_next = node;
444
445 if (node->m_next == NULL) {
446 m_last = node;
447 }
448
449 dgAssert (m_last);
450 dgAssert (!m_last->m_next);
451 dgAssert (m_first);
452 dgAssert (!m_first->m_prev);
453 dgAssert (SanityCheck ());
454 }
455 }
456
457
458 template<class T>
459 void dgList<T>::InsertBefore (dgListNode* const root, dgListNode* const node)
460 {
461 dgAssert (root);
462 dgAssert (node != root);
463
464 if (root->m_prev != node) {
465 if (node == m_last) {
466 m_last = node->m_prev;
467 }
468 if (node == m_first) {
469 m_first = node->m_next;
470 }
471 node->Unlink ();
472
473 node->m_next = root;
474 node->m_prev = root->m_prev;
475 if (root->m_prev) {
476 root->m_prev->m_next = node;
477 }
478 root->m_prev = node;
479
480 if (node->m_prev == NULL) {
481 m_first = node;
482 }
483
484 dgAssert (m_first);
485 dgAssert (!m_first->m_prev);
486 dgAssert (m_last);
487 dgAssert (!m_last->m_next);
488 dgAssert (SanityCheck ());
489 }
490 }
491
492
493 template<class T>
494 void dgList<T>::RotateToEnd (dgListNode* const node)
495 {
496 if (node != m_last) {
497 if (m_last != m_first) {
498 if (node == m_first) {
499 m_first = m_first->GetNext();
500 }
501 node->Unlink();
502 m_last->AddLast(node);
503 m_last = node;
504 }
505 }
506
507 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
508 dgAssert (SanityCheck ());
509 #endif
510 }
511
512 template<class T>
513 void dgList<T>::RotateToBegin (dgListNode* const node)
514 {
515 if (node != m_first) {
516 if (m_last != m_first) {
517 if (node == m_last) {
518 m_last = m_last->GetPrev();
519 }
520 node->Unlink();
521 m_first->AddFirst(node);
522 m_first = node;
523 }
524 }
525
526 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
527 dgAssert (SanityCheck ());
528 #endif
529 }
530
531
532 template<class T>
533 typename dgList<T>::dgListNode *dgList<T>::Find (const T &element) const
534 {
535 dgListNode *node;
536 for (node = m_first; node; node = node->GetNext()) {
537 if (element == node->m_info) {
538 break;
539 }
540 }
541 return node;
542 }
543
544 template<class T>
545 typename dgList<T>::dgListNode *dgList<T>::GetNodeFromInfo (T &info) const
546 {
547 dgListNode* const node = (dgListNode *) &info;
548 dgInt64 offset = ((char*) &node->m_info) - ((char *) node);
549 dgListNode* const retnode = (dgListNode *) (((char *) node) - offset);
550
551 dgAssert (&retnode->GetInfo () == &info);
552 return retnode;
553 }
554
555
556 template<class T>
557 void dgList<T>::Remove (const T &element)
558 {
559 dgListNode *const node = Find (element);
560 if (node) {
561 Remove (node);
562 }
563 }
564
565 template<class T>
566 void dgList<T>::Unlink (dgListNode* const node)
567 {
568 dgAssert (node);
569
570 m_count --;
571 dgAssert (m_count >= 0);
572
573 if (node == m_first) {
574 m_first = m_first->GetNext();
575 }
576 if (node == m_last) {
577 m_last = m_last->GetPrev();
578 }
579 node->Unlink();
580
581 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
582 dgAssert (SanityCheck ());
583 #endif
584 }
585
586 template<class T>
587 void dgList<T>::Merge (dgList<T>& list)
588 {
589 m_count += list.m_count;
590 if (list.m_first) {
591 list.m_first->m_prev = m_last;
592 }
593 if (m_last) {
594 m_last->m_next = list.m_first;
595 }
596 m_last = list.m_last;
597 if (!m_first) {
598 m_first = list.m_first;
599 }
600
601 list.m_count = 0;
602 list.m_last = NULL;
603 list.m_first = NULL;
604 #ifdef __ENABLE_DG_CONTAINERS_SANITY_CHECK
605 dgAssert (SanityCheck ());
606 #endif
607 }
608
609
610 template<class T>
611 void dgList<T>::Remove (dgListNode* const node)
612 {
613 Unlink (node);
614 delete node;
615 }
616
617
618 template<class T>
619 void dgList<T>::RemoveAll ()
620 {
621 for (dgListNode *node = m_first; node; node = m_first) {
622 m_count --;
623 m_first = node->GetNext();
624 node->Unlink();
625 delete node;
626 }
627 dgAssert (m_count == 0);
628 m_last = NULL;
629 m_first = NULL;
630 }
631
632 template<class T>
633 bool dgList<T>::SanityCheck () const
634 {
635 #ifdef _DEBUG
636 dgInt32 tCount = 0;
637 for (dgListNode * node = m_first; node; node = node->GetNext()) {
638 tCount ++;
639 if (node->GetPrev()) {
640 dgAssert (node->GetPrev() != node->GetNext());
641 if (node->GetPrev()->GetNext() != node) {
642 dgAssert (0);
643 return false;
644 }
645 }
646 if (node->GetNext()) {
647 dgAssert (node->GetPrev() != node->GetNext());
648 if (node->GetNext()->GetPrev() != node) {
649 dgAssert (0);
650 return false;
651 }
652 }
653 }
654 if (tCount != m_count) {
655 dgAssert (0);
656 return false;
657 }
658 #endif
659 return true;
660 }
661
662
663 //template<class T>
664 //void dgList<T>::SetAllocator (dgMemoryAllocator * allocator)
665 //{
666 // m_allocator = allocator;
667 //}
668
669 //template<class T>
670 //dgMemoryAllocator* dgList<T>::GetAllocator () const
671 //{
672 // return m_allocator;
673 //}
674 //template<class T> dgInt32 dgList <T>::m_size = 0;
675 //template<class T> dgMemoryAllocator* dgList<T>::m_staticAllocator = NULL;
676
677
678 #endif
679
680
dgList::dgListNode
friend class dgListNode
Definition: dgList.h:249
dgList::InsertAfter
void InsertAfter(dgListNode *const root, dgListNode *const node)
Definition: dgList.h:424
dgList::Find
dgListNode * Find(const T &element) const
Definition: dgList.h:533
dgList::RotateToBegin
void RotateToBegin(dgListNode *const node)
Definition: dgList.h:513
dgInt64
long long dgInt64
Definition: dgTypes.h:222
dgMemory.h
dgList::SanityCheck
bool SanityCheck() const
Definition: dgList.h:633
dgList::Remove
void Remove(dgListNode *const node)
Definition: dgList.h:611
dgDebug.h
dgList::dgListNode
Definition: dgList.h:36
dgAssert
#define dgAssert(x)
Definition: dgTypes.h:158
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgList::GetNodeFromInfo
dgListNode * GetNodeFromInfo(T &m_info) const
Definition: dgList.h:545
dgList::Iterator::GetNode
dgListNode * GetNode() const
Definition: dgList.h:187
dgList::InsertBefore
void InsertBefore(dgListNode *const root, dgListNode *const node)
Definition: dgList.h:459
dgList::Iterator::Iterator
Iterator(const dgList< T > &me)
Definition: dgList.h:123
dgList::RemoveAll
void RemoveAll()
Definition: dgList.h:619
dgList::dgListNode::GetNext
dgListNode * GetNext() const
Definition: dgList.h:102
DG_CLASS_ALLOCATOR
#define DG_CLASS_ALLOCATOR(allocator)
Definition: dgMemory.h:60
dgList
Definition: dgList.h:33
dgList::dgListNode::GetPrev
dgListNode * GetPrev() const
Definition: dgList.h:107
dgList::GetLast
dgListNode * GetLast() const
Definition: dgList.h:313
dgList::Append
dgListNode * Append()
Definition: dgList.h:338
dgList::Iterator::Begin
void Begin()
Definition: dgList.h:143
dgList::RotateToEnd
void RotateToEnd(dgListNode *const node)
Definition: dgList.h:494
dgStdafx.h
dgList::Addtop
dgListNode * Addtop()
Definition: dgList.h:391
dgList::Iterator::End
void End()
Definition: dgList.h:148
dgList::GetCount
dgInt32 GetCount() const
Definition: dgList.h:295
dgList::Iterator
Definition: dgList.h:120
dgList::~dgList
virtual ~dgList()
Definition: dgList.h:274
dgList::Iterator::~Iterator
~Iterator()
Definition: dgList.h:129
dgList::dgList
dgList(dgMemoryAllocator *const allocator)
Definition: dgList.h:264
dgList::Unlink
void Unlink(dgListNode *const node)
Definition: dgList.h:566
dgList::Merge
void Merge(dgList< T > &list)
Definition: dgList.h:587
dgList::Iterator::Set
void Set(dgListNode *const node)
Definition: dgList.h:153
dgList::GetAllocator
dgMemoryAllocator * GetAllocator() const
Definition: dgList.h:288
dgMemoryAllocator
Definition: dgMemory.h:73
dgList::dgListNode::GetInfo
T & GetInfo()
Definition: dgList.h:97
dgList::GetFirst
dgListNode * GetFirst() const
Definition: dgList.h:307
dgList::SetAllocator
void SetAllocator(dgMemoryAllocator *const allocator)
Definition: dgList.h:280
dgRef.h