Nebula
Loading...
Searching...
No Matches
list.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
14#include "core/types.h"
15
16//------------------------------------------------------------------------------
17namespace Util
18{
19template<class TYPE> class List
20{
21private:
22 class Node;
23public:
24 class Iterator;
25
29 List(const List<TYPE>& rhs);
35 void operator=(const List<TYPE>& rhs);
37 void operator=(List<TYPE>&& rhs);
38
40 bool IsEmpty() const;
42 SizeT Size() const;
44 void Clear();
46 void AddList(const List<TYPE>& l);
48 Iterator AddAfter(Iterator iter, const TYPE& e);
50 Iterator AddBefore(Iterator iter, const TYPE& e);
52 Iterator AddFront(const TYPE& e);
54 Iterator AddBack(const TYPE& e);
58 TYPE RemoveBack();
60 TYPE Remove(Iterator iter);
62 TYPE& Front() const;
64 TYPE& Back() const;
66 Iterator Begin() const;
68 Iterator End() const;
70 Iterator Last() const;
72 Iterator Find(const TYPE& e, Iterator start) const;
73
76 {
77 public:
81 Iterator(Node* node);
83 Iterator(const Iterator& rhs);
85 const Iterator& operator=(const Iterator& rhs);
87 bool operator==(const Iterator& rhs) const;
89 bool operator!=(const Iterator& rhs) const;
91 const Iterator& operator++();
93 Iterator operator++(int);
95 const Iterator& operator--();
97 Iterator operator--(int);
99 operator bool() const;
101 TYPE* operator->() const;
103 TYPE& operator*() const;
104 private:
105 friend class List<TYPE>;
106
108 Node* GetNode() const;
109
111 };
112
113private:
115 class Node
116 {
117 friend class List;
118 friend class Iterator;
119
121 Node(const TYPE& v);
125 void SetNext(Node* n);
127 Node* GetNext() const;
129 void SetPrev(Node* p);
131 Node* GetPrev() const;
133 TYPE& Value();
134
137 TYPE value;
138 };
139
142};
143
144//------------------------------------------------------------------------------
147template<class TYPE>
148List<TYPE>::Node::Node(const TYPE& val) :
149 next(0),
150 prev(0),
151 value(val)
152{
153 // empty
154}
155
156//------------------------------------------------------------------------------
159template<class TYPE>
161{
162 #if NEBULA_BOUNDSCHECKS
163 n_assert(0 == this->next);
164 n_assert(0 == this->prev);
165 #endif
166}
167
168//------------------------------------------------------------------------------
171template<class TYPE>
172void
174{
175 this->next = n;
176}
177
178//------------------------------------------------------------------------------
181template<class TYPE>
182typename List<TYPE>::Node*
184{
185 return this->next;
186}
187
188//------------------------------------------------------------------------------
191template<class TYPE>
192void
194{
195 this->prev = p;
196}
197
198//------------------------------------------------------------------------------
201template<class TYPE>
202typename List<TYPE>::Node*
204{
205 return this->prev;
206}
207
208//------------------------------------------------------------------------------
211template<class TYPE>
212TYPE&
214{
215 return this->value;
216}
217
218//------------------------------------------------------------------------------
221template<class TYPE>
223 node(0)
224{
225 // empty
226}
227
228//------------------------------------------------------------------------------
231template<class TYPE>
233 node(n)
234{
235 // empty
236}
237
238//------------------------------------------------------------------------------
241template<class TYPE>
243 node(rhs.node)
244{
245 // empty
246}
247
248//------------------------------------------------------------------------------
251template<class TYPE>
252const typename List<TYPE>::Iterator&
254{
255 if (&rhs != this)
256 {
257 this->node = rhs.node;
258 }
259 return *this;
260}
261
262//------------------------------------------------------------------------------
265template<class TYPE>
266bool
268{
269 return (this->node == rhs.node);
270}
271
272//------------------------------------------------------------------------------
275template<class TYPE>
276bool
278{
279 return (this->node != rhs.node);
280}
281
282//------------------------------------------------------------------------------
285template<class TYPE>
286const typename List<TYPE>::Iterator&
288{
289 #if NEBULA_BOUNDSCHECKS
290 n_assert(0 != this->node);
291 #endif
292 this->node = this->node->GetNext();
293 return *this;
294}
295
296//------------------------------------------------------------------------------
299template<class TYPE>
302{
303 #if NEBULA_BOUNDSCHECKS
304 n_assert(0 != this->node);
305 #endif
306 Iterator temp(this->node);
307 this->node = this->node->GetNext();
308 return temp;
309}
310
311//------------------------------------------------------------------------------
314template<class TYPE>
315const typename List<TYPE>::Iterator&
317{
318 #if NEBULA_BOUNDSCHECKS
319 n_assert(0 != this->node);
320 #endif
321 this->node = this->node->GetPrev();
322 return *this;
323}
324
325//------------------------------------------------------------------------------
328template<class TYPE>
331{
332 #if NEBULA_BOUNDSCHECKS
333 n_assert(0 != this->node);
334 #endif
335 Iterator temp(this->node);
336 this->node = this->node->GetPrev();
337 return temp;
338}
339
340//------------------------------------------------------------------------------
343template<class TYPE>
345{
346 return (0 != this->node);
347}
348
349//------------------------------------------------------------------------------
352template<class TYPE>
353TYPE*
355{
356 #if NEBULA_BOUNDSCHECKS
357 n_assert(this->node);
358 #endif
359 return &(this->node->Value());
360}
361
362//------------------------------------------------------------------------------
365template<class TYPE>
366TYPE&
368{
369 #if NEBULA_BOUNDSCHECKS
370 n_assert(this->node);
371 #endif
372 return this->node->Value();
373}
374
375//------------------------------------------------------------------------------
378template<class TYPE>
379typename List<TYPE>::Node*
381{
382 return this->node;
383}
384
385//------------------------------------------------------------------------------
388template<class TYPE>
390 front(0),
391 back(0)
392{
393 // empty
394}
395
396//------------------------------------------------------------------------------
399template<class TYPE>
401 front(0),
402 back(0)
403{
404 this->AddList(rhs);
405}
406
407//------------------------------------------------------------------------------
410template<class TYPE>
412 front(rhs.front),
413 back(rhs.back)
414{
415 rhs.front = nullptr;
416 rhs.back = nullptr;
417}
418
419//------------------------------------------------------------------------------
422template<class TYPE>
424{
425 this->Clear();
426}
427
428//------------------------------------------------------------------------------
431template<class TYPE>
432void
434{
435 this->Clear();
436 this->AddList(rhs);
437}
438
439//------------------------------------------------------------------------------
442template<class TYPE>
443bool
445{
446 return (0 == this->front);
447}
448
449//------------------------------------------------------------------------------
452template<class TYPE>
453SizeT
455{
456 Iterator iter;
457 SizeT size = 0;
458 for (iter = this->Begin(); iter != this->End(); ++iter)
459 {
460 size++;
461 }
462 return size;
463}
464
465//------------------------------------------------------------------------------
468template<class TYPE>
469void
471{
472 while (this->back)
473 {
474 this->RemoveBack();
475 }
476}
477
478//------------------------------------------------------------------------------
481template<class TYPE>
482void
484{
485 Iterator iter;
486 for (iter = rhs.Begin(); iter != rhs.End(); ++iter)
487 {
488 this->AddBack(*iter);
489 }
490}
491
492//------------------------------------------------------------------------------
495template<class TYPE>
497List<TYPE>::AddAfter(Iterator iter, const TYPE& e)
498{
499 Node* node = new Node(e);
500 if (0 == iter.GetNode())
501 {
502 #if NEBULA_BOUNDSCHECKS
503 n_assert((0 == this->front) && (0 == this->back));
504 #endif
505 this->front = node;
506 this->back = node;
507 }
508 else
509 {
510 if (iter.GetNode() == this->back)
511 {
512 this->back = node;
513 }
514 if (0 != iter.GetNode()->GetNext())
515 {
516 iter.GetNode()->GetNext()->SetPrev(node);
517 }
518 node->SetNext(iter.GetNode()->GetNext());
519 iter.GetNode()->SetNext(node);
520 node->SetPrev(iter.GetNode());
521 }
522 return Iterator(node);
523}
524
525//------------------------------------------------------------------------------
528template<class TYPE>
530List<TYPE>::AddBefore(Iterator iter, const TYPE& e)
531{
532 Node *node = new Node(e);
533 if (0 == iter.GetNode())
534 {
535 #if NEBULA_BOUNDSCHECKS
536 n_assert((0 == this->front) && (0 == this->back));
537 #endif
538 this->front = node;
539 this->back = node;
540 }
541 else
542 {
543 if (iter.GetNode() == this->front)
544 {
545 this->front = node;
546 }
547 if (0 != iter.GetNode()->GetPrev())
548 {
549 iter.GetNode()->GetPrev()->SetNext(node);
550 }
551 node->SetPrev(iter.GetNode()->GetPrev());
552 iter.GetNode()->SetPrev(node);
553 node->SetNext(iter.GetNode());
554 }
555 return Iterator(node);
556}
557
558//------------------------------------------------------------------------------
561template<class TYPE>
564{
565 return this->AddBefore(this->front, e);
566}
567
568//------------------------------------------------------------------------------
571template<class TYPE>
574{
575 return this->AddAfter(this->back, e);
576}
577
578//------------------------------------------------------------------------------
581template<class TYPE>
582TYPE
584{
585 #if NEBULA_BOUNDSCHECKS
586 n_assert(iter.GetNode());
587 #endif
588 Node* node = iter.GetNode();
589 if (node->GetPrev())
590 {
591 node->GetPrev()->SetNext(node->GetNext());
592 }
593 if (node->GetNext())
594 {
595 node->GetNext()->SetPrev(node->GetPrev());
596 }
597 if (node == this->front)
598 {
599 this->front = node->GetNext();
600 }
601 if (node == this->back)
602 {
603 this->back = node->GetPrev();
604 }
605 node->SetNext(0);
606 node->SetPrev(0);
607 TYPE elm = node->Value();
608 delete node;
609 return elm;
610}
611
612//------------------------------------------------------------------------------
615template<class TYPE>
616TYPE
618{
619 #if NEBULA_BOUNDSCHECKS
620 n_assert(0 != this->front);
621 #endif
622 return this->Remove(this->front);
623}
624
625//------------------------------------------------------------------------------
628template<class TYPE>
629TYPE
631{
632 #if NEBULA_BOUNDSCHECKS
633 n_assert(0 != this->back);
634 #endif
635 return this->Remove(this->back);
636}
637
638//------------------------------------------------------------------------------
641template<class TYPE>
642TYPE&
644{
645 #if NEBULA_BOUNDSCHECKS
646 n_assert(0 != this->front);
647 #endif
648 return this->front->Value();
649}
650
651//------------------------------------------------------------------------------
654template<class TYPE>
655TYPE&
657{
658 #if NEBULA_BOUNDSCHECKS
659 n_assert(0 != this->back);
660 #endif
661 return this->back->Value();
662}
663
664//------------------------------------------------------------------------------
667template<class TYPE>
670{
671 return Iterator(this->front);
672}
673
674//------------------------------------------------------------------------------
677template<class TYPE>
680{
681 return 0;
682}
683
684//------------------------------------------------------------------------------
687template<class TYPE>
690{
691 return Iterator(this->back);
692}
693
694//------------------------------------------------------------------------------
697template<class TYPE>
699List<TYPE>::Find(const TYPE& e, Iterator start) const
700{
701 for (; start != this->End(); ++start)
702 {
703 if (*start == e)
704 {
705 return start;
706 }
707 }
708 return 0;
709}
710
711} // namespace Util
712//------------------------------------------------------------------------------
the list iterator
Definition list.h:76
Node * node
Definition list.h:110
TYPE * operator->() const
safe -> operator
Definition list.h:354
bool operator!=(const Iterator &rhs) const
inequality operator
Definition list.h:277
bool operator==(const Iterator &rhs) const
equality operator
Definition list.h:267
const Iterator & operator=(const Iterator &rhs)
assignment operator
Definition list.h:253
Iterator()
default constructor
Definition list.h:222
Node * GetNode() const
access to node
Definition list.h:380
const Iterator & operator++()
pre-increment operator
Definition list.h:287
const Iterator & operator--()
pre-decrement operator
Definition list.h:316
TYPE & operator*() const
safe dereference operator
Definition list.h:367
a node in the list
Definition list.h:116
Node * GetPrev() const
get pointer to previous node
Definition list.h:203
Node * next
Definition list.h:135
Node(const TYPE &v)
constructor
Definition list.h:148
Node * GetNext() const
get pointer to next node
Definition list.h:183
Node * prev
Definition list.h:136
~Node()
destructor
Definition list.h:160
void SetNext(Node *n)
set pointer to next node
Definition list.h:173
void SetPrev(Node *p)
set pointer to previous node
Definition list.h:193
TYPE value
Definition list.h:137
TYPE & Value()
get value reference
Definition list.h:213
Implements a doubly linked list.
Definition list.h:20
void operator=(const List< TYPE > &rhs)
assignment operator
Definition list.h:433
void operator=(List< TYPE > &&rhs)
assignment operator
bool IsEmpty() const
return true if the list is empty
Definition list.h:444
Node * back
Definition list.h:141
TYPE & Back() const
get last element
Definition list.h:656
void AddList(const List< TYPE > &l)
add contents of other list to this list
Definition list.h:483
Iterator Find(const TYPE &e, Iterator start) const
find element in array (slow)
Definition list.h:699
Iterator AddBefore(Iterator iter, const TYPE &e)
add element before given element
Definition list.h:530
Iterator AddBack(const TYPE &e)
add element to end of list
Definition list.h:573
Iterator AddAfter(Iterator iter, const TYPE &e)
add element after given element
Definition list.h:497
List(List< TYPE > &&rhs)
move constructor
Definition list.h:411
TYPE RemoveBack()
remove last element of list
Definition list.h:630
void Clear()
clear list
Definition list.h:470
Iterator Begin() const
get iterator to first element
Definition list.h:669
Iterator End() const
get iterator past the last element
Definition list.h:679
Iterator Last() const
get iterator to last element
Definition list.h:689
Iterator AddFront(const TYPE &e)
add element to beginning of list
Definition list.h:563
TYPE Remove(Iterator iter)
remove given element
Definition list.h:583
List()
constructor
Definition list.h:389
Node * front
Definition list.h:140
List(const List< TYPE > &rhs)
copy constructor
Definition list.h:400
TYPE & Front() const
get first element
Definition list.h:643
TYPE RemoveFront()
remove first element of list
Definition list.h:617
SizeT Size() const
get number of elements in list (slow)
Definition list.h:454
~List()
destructor
Definition list.h:423
#define n_assert(exp)
Definition debug.h:50
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
int SizeT
Definition types.h:49