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