Chombo + EB  3.0
List.H
Go to the documentation of this file.
1 #ifdef CH_LANG_CC
2 /*
3  * _______ __
4  * / ___/ / ___ __ _ / / ___
5  * / /__/ _ \/ _ \/ V \/ _ \/ _ \
6  * \___/_//_/\___/_/_/_/_.__/\___/
7  * Please refer to Copyright.txt, in Chombo's root directory.
8  */
9 #endif
10 
11 #ifndef _LIST_H_
12 #define _LIST_H_
13 
14 #include "MayDay.H"
15 #include "Pool.H"
16 
17 #include "BaseNamespaceHeader.H"
18 
19 template <class T> class ListLink;
20 template <class T> class ListIterator;
21 template <class T> class List;
22 
23 // this is so this internal class doesn't appear in doxygen documentation
24 #ifndef DOXYGEN
25 
26 // Internal helper class for the List class
27 template <class T>
28 class ListLink
29 {
30 private:
31  friend class List<T>;
32  friend class ListIterator<T>;
33 
34  ListLink (const T& _val,
35  ListLink<T>* _pre,
36  ListLink<T>* _suc)
37  :
38  val(_val),
39  pre(_pre),
40  suc(_suc)
41  {}
42 
43  void swap(ListLink<T>* a);
44 
45  T val;
46  ListLink<T>* pre;
47  ListLink<T>* suc;
48 };
49 
50 #endif // doxygen
51 
52 /// Iterator over a List
53 /**
54  The class ListIterator<T> is an iterator over class List<T>.
55  This class does NOT provide a default constructor or an assignment operator.
56 */
57 template <class T>
58 class ListIterator
59 {
60 public:
61 
62  /// Construct a ListIterator<T> to first element of aList.
63  inline ListIterator (const List<T>& aList);
64 
65  /// The copy constructor.
66  inline ListIterator (const ListIterator<T>& rhs);
67 
68  /// Reset this ListIterator<T> to point to the first element in the List<T>.
69  inline void rewind ();
70 
71  /// Reset this ListIterator<T> to point to the first element in the List<T>.
72  /**
73  Same as rewind(), but included to be consistent with other iterators.
74  */
75  inline void begin();
76 
77  /// Return a constant reference to the object in the List<T> currently pointed to by this ListIterator<T>.
78  inline const T& operator() () const;
79 
80  inline T& operator() () ;
81 
82  /// Return a constant reference to the object in the List<T> currently pointed to by this ListIterator<T>.
83  inline const T& operator* () const;
84 
85  /// This is a conversion operator to makes the iterator look like a pointer
86  /**
87  This operator makes it easy to check if the
88  iterator is pointing to an element on the List<T>. If the
89  iterator has been moved off the List<T> or if the List<T> is
90  empty, this conversion returns the NULL pointer.
91  */
92  inline operator bool () const;
93 
94  /// Return true if the iterator is not past the end of the list.
95  /**
96  Same as bool(), but included to be consistent with other iterators.
97  */
98  inline bool ok() const ;
99 
100  /// Returns true if ListIterator<T> doesn't point to any element on the List<T>.
101  inline bool operator! () const;
102 
103  /// Return a constant reference to the object in the List<T> currently pointed to by the iterator.
104  inline const T& value () const;
105 
106  /// Return a constant reference to the object in the List<T> currently pointed to by the iterator.
107  const T& value ();
108 
109  /// The prefix auto-increment operator.
110  /**
111  Advances the ListIterator<T> to point to the next element on the
112  List<T>. It then returns a reference to itself to allow for chaining
113  with other operators.
114  */
115  inline ListIterator<T>& operator++ ();
116 
117  /// The prefix auto-decrement operator.
118  /**
119  Moves theListIterator<T> to point to the previous element on the
120  List<T>. It then returns a reference to itself to allow for
121  chaining with other operators.
122  */
123  inline ListIterator<T>& operator-- ();
124 
125  /// The postfix auto-decrement operator.
126  /**
127  Moves the ListIterator<T> to point to the previous element on the
128  List<T>. It then returns a ListIterator<T> that points to
129  the old element to allow for chaining with other operators.
130  */
131  inline ListIterator<T> operator-- (int);
132 
133  /// The postfix auto-increment operator.
134  /**
135  This advances the ListIterator<T> to point to the next element
136  on the List<T>. It then returns a ListIterator<T> that points to
137  the old element to allow for chaining with other operators.
138  */
139  inline ListIterator<T> operator++ (int);
140 
141  /// Equality test for two ListIterator<T>s
142  /**
143  Do the two ListIterator<T>s point to the same List<T> and
144  the same element within the List<T>?
145  */
146  inline bool operator== (const ListIterator<T>&) const;
147 
148  /// Are the ListIterator<T>s not equal?
149  inline bool operator!= (const ListIterator<T>&) const;
150 
151 protected:
152 
153  /**
154  Construct a ListIterator<T> to a List<T> and object in that List<T>.
155  */
156  inline ListIterator (const List<T>& _list,
157  ListLink<T>* _p);
158 
159  /**
160  A reference to the List<T> to which we point.
161  */
162  const List<T>& list;
163 
164  /**
165  A pointer to the element in the List<T> to which we point.
166  */
168 
169 private:
170  friend class List<T>;
171  //
172  // These are disallowed.
173  //
174  ListIterator ();
176 };
177 
178 /// A Doubly-Linked List Class
179 /**
180 
181  The List<T> class is a template class that implements a doubly-linked list
182  of objects. A List<T> is a useful container class when the number of
183  objects in the collection is not known ahead of time. A List<T> can
184  contain an arbitrary number of elements; operations such as insertion,
185  deletion, and catenation are easily implemented and inexpensive.
186 
187  The only difficulty when defining a list class is devising a mechanism to
188  access the elements. In an array, an element is accessed using an
189  integer index. Since the elements in a List<T> are ordered by position,
190  we could define an integer indexing operation that walks along the
191  List<T> links from the beginning until the numbered element is found.
192  Unfortunately, this would be very inefficient when accessing elements near
193  the end of a long list. Another solution is to allow user access to the
194  individual link objects that contain the element as well as the forward and
195  backward pointers. This is not a satisfactory solution since it allows
196  user access to the internal representation of the class. The solution
197  chosen is to define a ListIterator<T> template class.
198 
199  Think of a ListIterator<T> as a pointer to an object in the List<T>. You
200  can access the element currently pointed to by the iterator, move the
201  iterator forward and backward through the List<T>, and use it as a
202  mechanism to define where elements should be inserted and deleted. If the
203  iterator is moved off the end of the list it behaves as a null pointer.
204 
205  This is a concrete class, not a polymorphic one.
206 */
207 
208 template <class T>
209 class List
210 {
211 public:
212 
213  /// Construct an empty List<T>.
214  inline List ();
215 
216  inline List (bool usePool);
217 
218  /// The copy constructor.
219  List (const List<T>& rhs);
220 
221  /// The assignment operator.
222  List<T>& operator= (const List<T>& rhs);
223 
224  /// The destructor.
225  inline ~List();
226 
227  /// Adds a copy of the value to the beginning of the List<T>.
228  inline void prepend (const T& value);
229 
230  /// Adds a copy of the value to the end of the List<T>.
231  inline void append (const T& value);
232 
233  /// Adds a copy of the value to the end of the List<T>.
234  void add (const T& value);
235 
236  /// Appends a copy of all items in List<T> src to this List<T>.
237  void join (const List<T>& src);
238 
239  /// Appends a copy of all items in List<T> src to this List<T>.
240  /**
241  This differs from join() in that it unlinks the objects from
242  the List<T> src and glues them to the end of this List<T>,
243  leaving List<T> src empty. This is more efficient that
244  join() if src is no longer needed.
245  */
246  void catenate (List<T>& src);
247 
248  /// Removes all objects from the List<T>.
249  void clear ();
250 
251  /// Returns a copy of this List<T> on the heap.
252  /**
253  It is the user's responsibility to delete this when no longer
254  needed.
255  */
256  inline List<T>* copy () const;
257 
258  /// Returns a reference to the first element in the List<T>.
259  inline T& firstElement () const;
260 
261  /// Returns a reference to the last element in the List<T>.
262  inline T& lastElement () const;
263 
264  /// Returns true if the List<T> contains an object identical to \em value.
265  /**
266  Type T must have an operator==() defined, or be an intrinsic type.
267  */
268  bool includes (const T& value) const;
269 
270  /// Returns true if the this and rhs are memberwise equal.
271  /**
272  Lists are memberwise equal if he two lists are the same size and
273  each of the elements in the list compare equal. Type T must have
274  an operator==() defined, or be an intrinsic type.
275  */
276  bool operator== (const List<T>& rhs) const;
277 
278  /// Returns true if the this and rhs are not equal.
279  bool operator!= (const List<T>& rhs) const;
280 
281  /// Returns true if the List<T> is empty.
282  inline bool isEmpty () const;
283 
284  /// Returns true if the List<T> is not empty.
285  inline bool isNotEmpty () const;
286 
287  /// Returns the number of objects in the List<T>.
288  int length () const;
289 
290  /// Removes the first element in the List<T>.
291  inline void removeFirst ();
292 
293  /// Removes the last element in the List<T>.
294  inline void removeLast ();
295 
296  /// Returns reference to object pointed to by the ListIterator<T>.
297  inline const T& operator[] (const ListIterator<T>& li) const;
298 
299  /// Returns reference to object pointed to by the ListIterator<T>.
300  inline T& operator[] (const ListIterator<T>& li);
301 
302  /// Removes all objects in the List<T> equal to value.
303  void remove (const T& value);
304 
305  /// Removes all objects in the List<T> equal to any of the values in \rm lst.
306  void remove (const List<T>& lst);
307 
308  /// Removes the object pointed to by the ListIterator<T>.
309  void remove (ListIterator<T>& lit);
310 
311  /// Transfer the object pointed to by lit from the List<T> lit is associated with to this one
312  void transfer(ListIterator<T>& lit);
313 
314  /// Replace the value pointed to by the ListIterator<T> by val.
315  inline void replace (ListIterator<T>& li,
316  const T& val);
317 
318  /// Insert val into List<T> after the object pointed to by \em lit.
319  inline void addAfter (ListIterator<T>& lit,
320  const T& val);
321 
322  /// Insert val into List<T> before the object pointed to by \em lit
323  inline void addBefore (ListIterator<T>& lit,
324  const T& val);
325 
326  /// Returns a ListIterator<T> to the first object in this List<T>.
327  inline ListIterator<T> listIterator () const;
328 
329  /// Returns a ListIterator<T> to the first object in this List<T>.
330  inline ListIterator<T> first () const;
331 
332  /// Returns a ListIterator<T> to the last object in this List<T>.
333  inline ListIterator<T> last () const;
334 
335  /// sort according to operator< (note: currently implemented with BubbleSort)
336  void sort();
337 
338  void checkLinks() const;
339 protected:
340 
341  /**
342  A helper function for removing nodes.
343  */
344  void remove (ListLink<T> *ln);
345 
346  void removeLink(ListLink<T> *ln);
347 
348  /**
349  A helper function for adding nodes.
350  */
351  ListLink<T>* addBefore (ListLink<T>* ln,
352  const T& val);
353 
354  /**
355  A helper function for adding nodes.
356  */
357  ListLink<T>* addAfter (ListLink<T>* ln,
358  const T& val);
359 
360  /**
361  The head of the list.
362  */
364 
365  /**
366  The tail of the list.
367  */
369 
370  /**
371  Our good and trusted friend.
372  */
373  friend class ListIterator<T>;
374 
375  /**
376  A new member that hopefully will make our List snappier.
377  In particular when you have a large number of items, like in Particle code.
378  */
379  static Pool linkPool;
380 
381  bool m_usePool;
382 };
383 
384 //
385 // Inlines.
386 //
387 
388 //
389 // The ListIterator stuff.
390 //
391 
392 template <class T>
393 inline
395  ListLink<T>* _p)
396  :
397  list(_list),
398  p(_p)
399 {
400 }
401 
402 template <class T>
403 inline
405  : list(aList)
406 {
407  p = list.head;
408 }
409 
410 template <class T>
411 inline
413  :
414  list(li.list),
415  p(li.p)
416 {
417 }
418 
419 template <class T>
420 inline
421 void
423 {
424  p = list.head;
425 }
426 
427 template <class T>
428 inline
429 void
431 {
432  p = list.head;
433 }
434 
435 template <class T>
436 inline
437 const T&
439 {
440  CH_assert(p != 0);
441  return p->val;
442 }
443 
444 template <class T>
445 inline
446 T&
448 {
449  CH_assert(p != 0);
450  return p->val;
451 }
452 
453 template <class T>
454 inline
455 const T&
457 {
458  CH_assert(p != 0);
459  return p->val;
460 }
461 
462 template <class T>
463 inline
464 bool
466 {
467  return p != 0 ? true : false;
468 }
469 
470 template <class T>
471 inline
473 {
474  return ok() ;
475 }
476 
477 template <class T>
478 inline
479 bool
481 {
482  return p == 0 ? true : false;
483 }
484 
485 template <class T>
486 inline
487 const T&
489 {
490  CH_assert(p != 0);
491  return p->val;
492 }
493 
494 template <class T>
495 inline
498 {
499  if (p)
500  p = p->suc;
501  return *this;
502 }
503 
504 template <class T>
505 inline
508 {
509  if (p)
510  p = p->pre;
511  return *this;
512 }
513 
514 template <class T>
515 inline
518 {
519  const ListIterator<T> li = *this;
520  ++(*this);
521  return li;
522 }
523 
524 template <class T>
525 inline
528 {
529  const ListIterator<T> li = *this;
530  --(*this);
531  return li;
532 }
533 
534 template <class T>
535 inline
536 bool
538 {
539  return (&list == &_li.list && p == _li.p) ? true : false;
540 }
541 
542 template <class T>
543 inline
544 bool
546 {
547  return ! ListIterator<T>::operator==(_li);
548 }
549 
550 //
551 // List stuff.
552 //
553 
554 template <class T>
555 inline
557  :
558  head(0),
559  tail(0),
560  m_usePool(true)
561 {
562 }
563 
564 template <class T>
565 inline
567 {
568  clear();
569 }
570 
571 template <class T>
572 inline
573 void
575 {
576  addBefore(head, value);
577 }
578 
579 template <class T>
580 inline
581 void
583 {
584  addAfter(tail, value);
585 }
586 
587 
588 template <class T>
589 inline
590 List<T>*
592 {
593  List<T>* newlist = new List<T>(*this);
594  if (newlist == 0)
595  MayDay::Error("Out of memory in List::copy ");
596  return newlist;
597 }
598 
599 template <class T>
600 inline
601 T&
603 {
604  CH_assert(head != 0);
605  return head->val;
606 }
607 
608 template <class T>
609 inline
610 T&
612 {
613  CH_assert(tail != 0);
614  return tail->val;
615 }
616 
617 template <class T>
618 inline
619 bool
621 {
622  return head == 0 && tail == 0;
623 }
624 
625 template <class T>
626 inline
627 bool
629 {
630  return !isEmpty();
631 }
632 
633 template <class T>
634 inline
635 void
637 {
638  remove(head);
639 }
640 
641 template <class T>
642 inline
643 void
645 {
646  remove(tail);
647 }
648 
649 template <class T>
650 inline
651 const T&
653 {
654  CH_assert(li.p != 0);
655  return li.p->val;
656 }
657 
658 template <class T>
659 inline
660 T&
662 {
663  CH_assert(li.p != 0);
664  return li.p->val;
665 }
666 
667 template <class T>
668 inline
669 void
671  const T& _val)
672 {
673  CH_assert(li.p != 0);
674  li.p->val = _val;
675 }
676 
677 template <class T>
678 inline
679 void
681  const T& val)
682 {
683  addAfter(lit.p, val);
684 }
685 
686 template <class T>
687 inline
688 void
690  const T& val)
691 {
692  addBefore(lit.p, val);
693 }
694 
695 template <class T>
696 inline
699 {
700  return ListIterator<T>(*this,head);
701 }
702 
703 template <class T>
704 inline
707 {
708  return ListIterator<T>(*this,head); //[NOTE: same as first()]
709 }
710 
711 template <class T>
712 inline
715 {
716  return ListIterator<T>(*this,tail);
717 }
718 
719 #include "BaseNamespaceFooter.H"
720 
721 #include "ListImplem.H"
722 
723 #endif /*_LIST_H_*/
void addAfter(ListIterator< T > &lit, const T &val)
Insert val into List<T> after the object pointed to by lit.
Definition: List.H:680
T & lastElement() const
Returns a reference to the last element in the List<T>.
Definition: List.H:611
bool operator!=(const ListIterator< T > &) const
Are the ListIterator<T>s not equal?
Definition: List.H:545
ListLink< T > * p
Definition: List.H:167
ListIterator< T > listIterator() const
Returns a ListIterator<T> to the first object in this List<T>.
Definition: List.H:706
void prepend(const T &value)
Adds a copy of the value to the beginning of the List<T>.
Definition: List.H:574
#define CH_assert(cond)
Definition: CHArray.H:37
~List()
The destructor.
Definition: List.H:566
List< T > & operator=(const List< T > &rhs)
The assignment operator.
Definition: ListImplem.H:67
const T & value() const
Return a constant reference to the object in the List<T> currently pointed to by the iterator...
Definition: List.H:488
void append(const T &value)
Adds a copy of the value to the end of the List<T>.
Definition: List.H:582
ListLink< T > * tail
Definition: List.H:368
void clear()
Removes all objects from the List<T>.
Definition: ListImplem.H:264
bool operator!() const
Returns true if ListIterator<T> doesn&#39;t point to any element on the List<T>.
Definition: List.H:480
List< T > * copy() const
Returns a copy of this List<T> on the heap.
Definition: List.H:591
void rewind()
Reset this ListIterator<T> to point to the first element in the List<T>.
Definition: List.H:422
ListIterator< T > last() const
Returns a ListIterator<T> to the last object in this List<T>.
Definition: List.H:714
const T & operator*() const
Return a constant reference to the object in the List<T> currently pointed to by this ListIterator<T>...
Definition: List.H:456
ListLink< T > * head
Definition: List.H:363
int isEmpty(const box2d *)
const T & operator()() const
Return a constant reference to the object in the List<T> currently pointed to by this ListIterator<T>...
Definition: List.H:438
const T & operator[](const ListIterator< T > &li) const
Returns reference to object pointed to by the ListIterator<T>.
Definition: List.H:652
void removeFirst()
Removes the first element in the List<T>.
Definition: List.H:636
bool ok() const
Return true if the iterator is not past the end of the list.
Definition: List.H:465
ListIterator< T > & operator--()
The prefix auto-decrement operator.
Definition: List.H:507
void removeLast()
Removes the last element in the List<T>.
Definition: List.H:644
bool m_usePool
Definition: List.H:381
void addBefore(ListIterator< T > &lit, const T &val)
Insert val into List<T> before the object pointed to by lit.
Definition: List.H:689
A Doubly-Linked List Class.
Definition: List.H:21
Iterator over a List.
Definition: List.H:20
Pool is a class to optimize memory allocation.
Definition: Pool.H:63
const List< T > & list
Definition: List.H:162
T & firstElement() const
Returns a reference to the first element in the List<T>.
Definition: List.H:602
ListIterator< T > first() const
Returns a ListIterator<T> to the first object in this List<T>.
Definition: List.H:698
static Pool linkPool
Definition: List.H:379
bool isNotEmpty() const
Returns true if the List<T> is not empty.
Definition: List.H:628
static void Error(const char *const a_msg=m_nullString, int m_exitCode=CH_DEFAULT_ERROR_CODE)
Print out message to cerr and exit with the specified exit code.
void replace(ListIterator< T > &li, const T &val)
Replace the value pointed to by the ListIterator<T> by val.
Definition: List.H:670
C::self_type operator*(const C &, const C &)
Definition: GenericArithmeticI.H:132
bool operator==(const ListIterator< T > &) const
Equality test for two ListIterator<T>s.
Definition: List.H:537
bool isEmpty() const
Returns true if the List<T> is empty.
Definition: List.H:620
void begin()
Reset this ListIterator<T> to point to the first element in the List<T>.
Definition: List.H:430
List()
Construct an empty List<T>.
Definition: List.H:556
ListIterator< T > & operator++()
The prefix auto-increment operator.
Definition: List.H:497