Chombo + EB  3.2
ListImplem.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 _LISTIMPLEM_H_
12 #define _LISTIMPLEM_H_
13 
14 #include "MayDay.H"
15 #include "BaseNamespaceHeader.H"
16 
17 //
18 // List members
19 //
20 template <class T>
21 Pool List<T>::linkPool(sizeof(ListLink<T>), typeid(T).name(), 300);
22 
23 template <class T>
24 List<T>::List (const List<T>& source)
25  : head(0),
26  tail(0),
27  m_usePool(source.m_usePool)
28 {
29  if (source.isEmpty())
30  tail = head = 0;
31  else
32  for (ListIterator<T> li(source); li; ++li)
33  append(li());
34 }
35 template <class T>
36 List<T>::List (bool usePool)
37  : head(0),
38  tail(0),
39  m_usePool(usePool)
40 {
41 }
42 
43 //
44 // This isn't inlined as it's declared virtual.
45 //
46 
47 template <class T>
48 void
49 List<T>::add (const T& value)
50 {
51  append(value);
52 }
53 
54 template <class T>
55 int
57 {
58  int len = 0;
59  for (ListIterator<T> li(*this); li; ++li)
60  len++;
61  return len;
62 }
63 
64 template <class T>
65 List<T>&
67 {
68  if (!(this == &source))
69  {
70  clear();
71  for (ListIterator<T> li(source); li; ++li)
72  append(li());
73  }
74  return *this;
75 }
76 
77 template <class T>
80  const T& val)
81 {
82  CH_assert(ln != 0 || head == 0);
83 
84  ListLink<T>* newlink;
85 
86  if (ln == head)
87  {
88  //head = newlink = new ListLink<T>(val, 0, head);
89  if (m_usePool)
90  head = newlink = new (linkPool.getPtr()) ListLink<T>(val, 0, head);
91  else
92  head = newlink = new ListLink<T>(val, 0, head);
93 
94  if (tail == 0)
95  tail = head;
96  else
97  head->suc->pre = newlink;
98  }
99  else
100  {
101  //newlink = new ListLink<T>(val, ln->pre, ln);
102  if (m_usePool)
103  newlink = new (linkPool.getPtr()) ListLink<T>(val, ln->pre, ln);
104  else
105  newlink = new ListLink<T>(val, ln->pre, ln);
106 
107  ln->pre->suc = newlink;
108  ln->pre = newlink;
109  }
110 
111  if (newlink == 0)
112  MayDay::Error("Out of memory in ListLink::addBefore");
113 
114  return newlink;
115 }
116 
117 // g1 <=> this <=> g2 . . . k1 <=> a <=> k2
118 // to
119 // g1 <=> a <=> g2 . . . k1 <=> this <=> k2
120 template <class T>
121 void
123 {
124  CH_assert(a!= NULL);
125  if (a->pre == this)// if a and this are neighbours, need to use different logic
126  {
127  a->pre = this->pre;
128  if (this->pre != NULL) pre->suc = a;
129  this->pre = a;
130  this->suc = a->suc;
131  if (this->suc != NULL) suc->pre = this;
132  a->suc = this;
133  }
134  else if (a->suc == this)
135  {
136  a->swap(this);
137  }
138  else
139  {
140  ListLink<T>* tmp = a->pre; //tmp = k1
141  a->pre = this->pre; //a.pre = g1
142  if (this->pre != NULL)
143  {
144  pre->suc = a; //g1.suc = a
145  }
146  this->pre = tmp; //this.pre = k1
147  tmp = a->suc; //tmp=k2
148  a->suc = this->suc; //a.suc = g2
149  if (this->suc != NULL)
150  {
151  suc->pre = a; //g2.pre = a
152  }
153  if (this->pre!= NULL)
154  {
155  pre->suc = this; //k1.suc = this
156  }
157  this->suc = tmp; //this.suc = k2
158  if (suc != NULL)
159  {
160  suc->pre = this; //k2.pre = this
161  }
162  }
163 }
164 
165 template <class T>
168  const T& val)
169 {
170  CH_assert(ln != 0 || tail == 0);
171 
172  ListLink<T>* newlink;
173 
174  if (ln == tail)
175  {
176  if (!m_usePool)
177  tail = newlink = new ListLink<T>(val,tail,0);
178  else
179  tail = newlink = new (linkPool.getPtr()) ListLink<T>(val,tail,0);
180  if (head == 0)
181  head = tail;
182  else
183  tail->pre->suc = newlink;
184  }
185  else
186  {
187  if (!m_usePool)
188  newlink = new ListLink<T>(val, ln, ln->suc);
189  else
190  newlink = new (linkPool.getPtr()) ListLink<T>(val, ln, ln->suc);
191  ln->suc->pre = newlink;
192  ln->suc = newlink;
193  }
194 
195  if (newlink == 0)
196  MayDay::Error("Out of memory in ListLink::addAfter");
197 
198  return newlink;
199 }
200 
201 template <class T>
202 void
203 List<T>::join (const List<T>& list2)
204 {
205  for (ListIterator<T> li2(list2); li2; ++li2)
206  append(li2());
207 }
208 
209 template <class T>
210 void
212 {
213  if (list2.isEmpty())
214  //
215  // Do nothing.
216  //
217  ;
218  else if (isEmpty())
219  {
220  head = list2.head;
221  tail = list2.tail;
222  list2.head = 0;
223  list2.tail = 0;
224  }
225  else
226  {
227  tail->suc = list2.head;
228  list2.head->pre = tail;
229  tail = list2.tail;
230  list2.head = 0;
231  list2.tail = 0;
232  }
233 }
234 
235 template <class T>
237 {
238  ListLink<T>* next = 0;
239 
240  for (ListLink<T>* p = head; p != 0; p = next)
241  {
242  next = p->suc;
243  if (next != NULL)
244  {
245  if (next->pre != p)
246  {
247  MayDay::Abort("next->pre != this");
248  }
249  }
250  else
251  {
252  if (p != tail)
253  {
254  MayDay::Abort("link terminated and is not tail");
255  }
256  }
257 
258  }
259 }
260 
261 template <class T>
262 void
264 {
265  ListLink<T>* next = 0;
266 
267  for (ListLink<T>* p = head; p != 0; p = next)
268  {
269  next = p->suc;
270  p->suc = 0;
271  //delete p;
272  p->val.~T();
273  if (m_usePool)
275  else
276  delete p;
277 
278  }
279  tail = head = 0;
280 }
281 
282 template <class T>
283 bool
284 List<T>::includes (const T& v) const
285 {
286  bool rc = false;
287  for (ListIterator<T> li(*this); li && !rc; ++li)
288  if (v == li())
289  rc = true;
290  return rc;
291 }
292 
293 template<class T>
294 bool
295 List<T>::operator== (const List<T>& rhs) const
296 {
297  if (length() == rhs.length())
298  {
299  for (ListIterator<T> li(*this), ri(rhs); li; ++li, ++ri)
300  if (li() != ri())
301  return false;
302  return true;
303  }
304 
305  return false;
306 }
307 
308 template<class T>
309 bool
310 List<T>::operator!= (const List<T>& rhs) const
311 {
312  return !operator==(rhs);
313 }
314 
315 template <class T>
316 void
318 {
319 
320  CH_assert(&(li.list) != this);
321  List<T>& other = (List<T>&)(li.list);
322 
323  ListLink<T>* p = li.p;
324  li.p = p->suc; //push iterator ahead;
325 
326  // remove p from other list.
327  other.removeLink(p);
328 
329  if (head == 0)
330  {
331  head = tail = p;
332  p->pre=0;
333  p->suc=0;
334  }
335  else
336  {
337  p->suc=0;
338  tail->suc = p;
339  p->pre = tail;
340  tail = p;
341  }
342 
343 }
344 
345 template <class T>
346 void
348 {
349  ListLink<T> *np = li.p->suc;
350  remove(li.p);
351  li.p = np;
352 }
353 
354 template <class T>
355 void
356 List<T>::remove (const T& _v)
357 {
358  for (ListIterator<T> litr(*this); litr; ++litr)
359  if (litr() == _v)
360  remove(litr);
361 }
362 
363 template <class T>
364 void
366 {
367  for (ListIterator<T> litr(_lv); litr; ++litr)
368  remove(litr());
369 }
370 
371 template <class T>
372 void
374 {
375  CH_assert(head !=0 && tail != 0);
376 
377  if (head == tail)
378  {
379  CH_assert(head == ln);
380  head = tail = 0;
381  }
382  else if (head == ln)
383  {
384  CH_assert(ln->pre == 0);
385  head = ln->suc;
386  head->pre = 0;
387  }
388  else if (tail == ln)
389  {
390  CH_assert(ln->suc == 0);
391  tail = ln->pre;
392  tail->suc = 0;
393  }
394  else
395  {
396  CH_assert(ln->suc != 0 && ln->pre != 0);
397  ln->suc->pre = ln->pre;
398  ln->pre->suc = ln->suc;
399  }
400 
401 }
402 
403 template <class T>
404 void
406 {
407  removeLink(ln);
408  //delete ln;
409  ln->val.~T();
410  if (m_usePool)
411  linkPool.returnPtr(ln);
412  else
413  delete ln;
414 
415  ln = 0;
416 }
417 
418 template <class T>
419 void
421 {
422  if (head == NULL) return;
423 
424  ListLink<T>* next = 0;
425  bool swapped = true;
426  while (swapped)
427  {
428  swapped = false;
429  for (ListLink<T>* p = head; p != 0;)
430  {
431  next = p->suc;
432  if (next != NULL && next->val < p->val)
433  {
434  swapped = true;
435  p->swap(next);
436  if (head == p) head = next;
437  if (tail == next) tail = p;
438  }
439  else
440  {
441  p = next;
442  }
443  }
444  }
445  //checkLinks();
446 }
447 
448 #include "BaseNamespaceFooter.H"
449 #endif /* CH_LISTIMPLEM_H */
void catenate(List< T > &src)
Appends a copy of all items in List<T> src to this List<T>.
Definition: ListImplem.H:211
void addAfter(ListIterator< T > &lit, const T &val)
Insert val into List<T> after the object pointed to by lit.
Definition: List.H:679
ListLink< T > * p
Definition: List.H:167
#define CH_assert(cond)
Definition: CHArray.H:37
List< T > & operator=(const List< T > &rhs)
The assignment operator.
Definition: ListImplem.H:66
void transfer(ListIterator< T > &lit)
Transfer the object pointed to by lit from the List<T> lit is associated with to this one...
Definition: ListImplem.H:317
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 remove(const T &value)
Removes all objects in the List<T> equal to value.
Definition: ListImplem.H:356
void * getPtr()
request a section of memory of ptrSize_ contiguous bytes.
Definition: Pool.H:157
void removeLink(ListLink< T > *ln)
Definition: ListImplem.H:373
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:263
void returnPtr(void *a_ptr)
return memory previous acquired with the getPtr() function.
ListLink< T > * head
Definition: List.H:363
void join(const List< T > &src)
Appends a copy of all items in List<T> src to this List<T>.
Definition: ListImplem.H:203
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:688
A Doubly-Linked List Class.
Definition: List.H:21
const char * name(const FArrayBox &a_dummySpecializationArg)
Definition: CH_HDF5.H:907
Iterator over a List.
Definition: List.H:20
void add(const T &value)
Adds a copy of the value to the end of the List<T>.
Definition: ListImplem.H:49
Pool is a class to optimize memory allocation.
Definition: Pool.H:63
const List< T > & list
Definition: List.H:162
static Pool linkPool
Definition: List.H:379
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.
int length() const
Returns the number of objects in the List<T>.
Definition: ListImplem.H:56
bool operator==(const List< T > &rhs) const
Returns true if the this and rhs are memberwise equal.
Definition: ListImplem.H:295
bool operator!=(const List< T > &rhs) const
Returns true if the this and rhs are not equal.
Definition: ListImplem.H:310
bool isEmpty() const
Returns true if the List<T> is empty.
Definition: List.H:619
bool includes(const T &value) const
Returns true if the List<T> contains an object identical to value.
Definition: ListImplem.H:284
List()
Construct an empty List<T>.
Definition: List.H:556
void checkLinks() const
Definition: ListImplem.H:236
void sort()
sort according to operator< (note: currently implemented with BubbleSort)
Definition: ListImplem.H:420
static void Abort(const char *const a_msg=m_nullString)
Print out message to cerr and exit via abort() (if serial) or MPI_Abort() (if parallel).