ug4
attached_list.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2011-2015: G-CSC, Goethe University Frankfurt
3  * Author: Sebastian Reiter
4  *
5  * This file is part of UG4.
6  *
7  * UG4 is free software: you can redistribute it and/or modify it under the
8  * terms of the GNU Lesser General Public License version 3 (as published by the
9  * Free Software Foundation) with the following additional attribution
10  * requirements (according to LGPL/GPL v3 §7):
11  *
12  * (1) The following notice must be displayed in the Appropriate Legal Notices
13  * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14  *
15  * (2) The following notice must be displayed at a prominent place in the
16  * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17  *
18  * (3) The following bibliography is recommended for citation and must be
19  * preserved in all covered files:
20  * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21  * parallel geometric multigrid solver on hierarchically distributed grids.
22  * Computing and visualization in science 16, 4 (2013), 151-164"
23  * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24  * flexible software system for simulating pde based models on high performance
25  * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26  *
27  * This program is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  */
32 
33 #ifndef __H__UG__attached_list__
34 #define __H__UG__attached_list__
35 
36 #include <iterator>
37 #include "attachment_pipe.h"
38 
39 namespace ug
40 {
41 
43 // predeclarations
44 template <class TAAEntry> class ConstAttachedElementListIterator;
45 
48 template <class TAAEntry>
49 class AttachedElementListIterator : public std::iterator<
50  std::bidirectional_iterator_tag,
51  typename TAAEntry::element>
52 {
53  public:
54  typedef typename TAAEntry::element element;
56 
58  AttachedElementListIterator(element curElem, const TAAEntry& aaEntry) :
59  m_aaEntry(aaEntry), m_curElem(curElem) {}
62 
63  const iterator& operator=(const iterator& iter)
64  {
65  m_aaEntry = iter.m_aaEntry;
66  m_curElem = iter.m_curElem;
67  return *this;
68  }
69 
71  element operator*() const {return m_curElem;}
72  element* operator->() const {return &m_curElem;}
73 
74  iterator operator++() {m_curElem = m_aaEntry[m_curElem].next; return *this;}
76  {// post-increment
77  iterator iter = *this;
79  return iter;
80  }
81 
82  iterator operator--() {m_curElem = m_aaEntry[m_curElem].prev; return *this;}
84  {
85  iterator iter = *this;
87  return iter;
88  }
89 
90  // note that each element may only be in the list once.
91  bool operator==(const iterator& iter) const {return m_curElem == iter.m_curElem;}
92  bool operator!=(const iterator& iter) const {return m_curElem != iter.m_curElem;}
93 
94  private:
95  TAAEntry m_aaEntry;
97 
98  friend class ConstAttachedElementListIterator<TAAEntry>;
99 };
100 
103 template <class TAAEntry>
104 class ConstAttachedElementListIterator : public std::iterator<
105  std::bidirectional_iterator_tag,
106  const typename TAAEntry::element>
107 {
108  public:
109  typedef typename TAAEntry::element element;
111 
113  ConstAttachedElementListIterator(element curElem, const TAAEntry& aaEntry) :
114  m_aaEntry(aaEntry), m_curElem(curElem) {}
119 
120  const iterator& operator=(const iterator& iter)
121  {
122  m_aaEntry = iter.m_aaEntry;
123  m_curElem = iter.m_curElem;
124  return *this;
125  }
126 
128  element operator*() const {return m_curElem;}
129  const element* operator->() const {return &m_curElem;}
130 
131  iterator operator++() {m_curElem = m_aaEntry[m_curElem].next; return *this;}
133  {// post-increment
134  iterator iter = *this;
135  m_curElem = m_aaEntry[m_curElem].next;
136  return iter;
137  }
138 
139  iterator operator--() {m_curElem = m_aaEntry[m_curElem].prev; return *this;}
141  {
142  iterator iter = *this;
143  m_curElem = m_aaEntry[m_curElem].prev;
144  return iter;
145  }
146 
147  // note that each element may only be in the list once.
148  bool operator==(const iterator& iter) const {return m_curElem == iter.m_curElem;}
149  bool operator!=(const iterator& iter) const {return m_curElem != iter.m_curElem;}
150 
151  private:
152  TAAEntry m_aaEntry;
154 };
155 
158 
180 template <class TAttachmentPipe>
182 {
183  public:
184  typedef typename TAttachmentPipe::element element;
185 
186  struct Entry{
187  Entry() : prev(NULL), next(NULL) {}
188  Entry(const element& p, const element& n) : prev(p), next(n) {}
191  };
192 
194  typedef typename TAttachmentPipe::ElementHandler ElemHandler;
196 
199 
200  public:
201  AttachedElementList(TAttachmentPipe* pipe = NULL) :
202  m_pipe(NULL),
203  m_aEntry("AttachedElementList_Entry", false),
204  m_front(NULL),
205  m_back(NULL),
206  m_bSharedAttachment(false)
207  {
208  if(pipe)
209  set_pipe(pipe);
210  }
211 
214  m_pipe(NULL),
215  m_aEntry(aEntry),
216  m_front(NULL),
217  m_back(NULL),
218  m_bSharedAttachment(false)
219  {}
220 
222  AttachedElementList(TAttachmentPipe* pipe, AEntry aEntry) :
223  m_pipe(NULL),
224  m_aEntry(aEntry),
225  m_front(NULL),
226  m_back(NULL),
227  m_bSharedAttachment(true)
228  {
229  if(pipe)
230  set_pipe(pipe);
231  }
232 
234  {
237  m_aEntry = ael.m_aEntry;
238 
239  set_pipe(ael.m_pipe);
240  if(ael.m_front){
241  iterator iter(ael.m_front, m_aaEntry);
242  while(*iter){
243  push_back(*iter);
244  ++iter;
245  }
246  }
247  }
248 
250  {
251  set_pipe(NULL);
252  }
253 
255  {
256  clear();
257 
258  if(ael.m_bSharedAttachment)
259  set_pipe(ael.m_pipe, ael.m_aEntry);
260  else
261  set_pipe(ael.m_pipe);
262 
263  if(ael.m_front){
264  iterator iter(ael.m_front, m_aaEntry);
265  while(*iter){
266  push_back(*iter);
267  ++iter;
268  }
269  }
270 
271  return *this;
272  }
273 
275  void set_pipe(TAttachmentPipe* pipe)
276  {
278  m_pipe->detach(m_aEntry);
280 
281  m_pipe = pipe;
282  if(m_pipe){
283  if(!m_pipe->has_attachment(m_aEntry))
284  m_pipe->attach(m_aEntry);
286  }
287 
288  m_front = m_back = NULL;
289  }
290 
292 
293  void set_pipe(TAttachmentPipe* pipe, AEntry aEntry)
294  {
296  m_pipe->detach(m_aEntry);
298 
299  m_pipe = pipe;
300  m_aEntry = aEntry;
301  m_bSharedAttachment = true;
302 
303  if(m_pipe){
304  // since we use a shared attachment in this case, it may already be
305  // attached to the pipe.
306  if(!m_pipe->has_attachment(m_aEntry))
307  m_pipe->attach(m_aEntry);
309  }
310 
311  m_front = m_back = NULL;
312  }
313 
315  void clear()
316  {
317  if(m_pipe){
318  iterator iter = begin();
319  while(iter != end()){
320  element elem = *iter;
321  iter++;
322  m_aaEntry[elem] = Entry();
323  }
324 
325  m_front = m_back = NULL;
326  }
327  }
328 
329 
331  bool empty() const {return m_front == NULL;}
332 
334  element front() {return m_front;}
336  element back() {return m_back;}
337 
339  const element front() const {return m_front;}
341  const element back() const {return m_back;}
342 
344  void push_back(const element& elem)
345  {
346  m_aaEntry[elem] = Entry(m_back, NULL);
347  if(empty())
348  m_front = elem;
349  else
350  m_aaEntry[m_back].next = elem;
351  m_back = elem;
352  }
353 
355 
357  iterator insert(iterator position, const element& elem)
358  {
359  if(empty() || !(*position))
360  push_back(elem);
361  else{
362  Entry& entry = m_aaEntry[*position];
363 
364  if(entry.prev){
365  m_aaEntry[entry.prev].next = elem;
366  m_aaEntry[elem].prev = entry.prev;
367  }
368  else{
369  m_aaEntry[elem].prev = NULL;
370  m_front = elem;
371  }
372 
373  m_aaEntry[elem].next = *position;
374  entry.prev = elem;
375  }
376 
377  return get_iterator(elem);
378  }
379 
381 
384  {
385  Entry& entry = m_aaEntry[*position];
386  if(entry.prev)
387  m_aaEntry[entry.prev].next = entry.next;
388  else
389  m_front = entry.next;
390 
391  if(entry.next)
392  m_aaEntry[entry.next].prev = entry.prev;
393  else
394  m_back = entry.prev;
395 
396  // get next element and reset entry.
397  element nextElem = entry.next;
398  entry = Entry();
399  return iterator(nextElem, m_aaEntry);
400  }
401 
404  {
405  iterator iter = begin;
406  while(iter != end){
407  iterator titer = iter++;
408  erase(titer);
409  }
410  return iter;
411  }
412 
414 
418  {
419  return iterator(elem, m_aaEntry);
420  }
421 
423 
425  {
426  if(elem == m_front)
427  return &m_front;
428  return &m_aaEntry[m_aaEntry[elem].prev].next;
429  }
430 
432  bool is_in_list(const element& elem)
433  {
434  return (m_front == elem) || (m_aaEntry[elem].prev != NULL);
435  }
438 
440 
441  iterator end() {return iterator(NULL, m_aaEntry);}
442 
445 
447 
448  const_iterator end() const {return const_iterator(NULL, m_aaEntry);}
449 
450  private:
451  // the attachment pipe on which we'll operate
452  TAttachmentPipe* m_pipe;
453 
454  // The entry attachment
456 
457  // the attachment accessor with which the entries are accessed
459 
460  // front and back elements
463 
464  // tells whether the entry attachment is shared with other lists
466 };
467 
468 
469 
470 }// end of namespace
471 
472 #endif
parameterString p
A linked list of elements living in an attachment.
Definition: attached_list.h:182
void set_pipe(TAttachmentPipe *pipe)
set the attachment pipe on which the list shall operate
Definition: attached_list.h:275
bool is_in_list(const element &elem)
returns true if the element is in the list
Definition: attached_list.h:432
void push_back(const element &elem)
pushes an element to the end of the list
Definition: attached_list.h:344
element m_front
Definition: attached_list.h:461
element m_back
Definition: attached_list.h:462
const element front() const
returns the first element in the list (const)
Definition: attached_list.h:339
TAttachmentPipe::element element
Definition: attached_list.h:184
const AttachedElementList & operator=(const AttachedElementList &ael)
Definition: attached_list.h:254
element back()
returns the last element in the list
Definition: attached_list.h:336
bool empty() const
retunrs true if the list is empty
Definition: attached_list.h:331
AEntry m_aEntry
Definition: attached_list.h:455
AAEntry m_aaEntry
Definition: attached_list.h:458
AttachedElementListIterator< AAEntry > iterator
Definition: attached_list.h:197
iterator erase(iterator begin, iterator end)
erases a sequence of entries
Definition: attached_list.h:403
AttachmentAccessor< element, AEntry, ElemHandler > AAEntry
Definition: attached_list.h:195
TAttachmentPipe * m_pipe
Definition: attached_list.h:452
const element back() const
returns the last element in the list (const)
Definition: attached_list.h:341
void set_pipe(TAttachmentPipe *pipe, AEntry aEntry)
Sets the pipe and a shared entry-attachment on which the list will operate.
Definition: attached_list.h:293
iterator end()
returns an iterator to the end of the sequence.
Definition: attached_list.h:441
AttachedElementList(TAttachmentPipe *pipe, AEntry aEntry)
Note that auto-copy on aEntry has to be disabled.
Definition: attached_list.h:222
AttachedElementList(const AttachedElementList &ael)
Definition: attached_list.h:233
ConstAttachedElementListIterator< AAEntry > const_iterator
Definition: attached_list.h:198
Attachment< Entry > AEntry
Definition: attached_list.h:193
void clear()
clears the list. begin() == end() afterwards.
Definition: attached_list.h:315
iterator get_iterator(const element &elem)
returns the iterator to the given element
Definition: attached_list.h:417
~AttachedElementList()
Definition: attached_list.h:249
AttachedElementList(TAttachmentPipe *pipe=NULL)
Definition: attached_list.h:201
iterator erase(iterator position)
erases the element at the given position
Definition: attached_list.h:383
TAttachmentPipe::ElementHandler ElemHandler
Definition: attached_list.h:194
const_iterator end() const
returns an iterator to the end of the sequence.
Definition: attached_list.h:448
iterator begin()
returns an iterator to the beginning of the sequence.
Definition: attached_list.h:437
const_iterator begin() const
returns an iterator to the beginning of the sequence.
Definition: attached_list.h:444
AttachedElementList(AEntry aEntry)
Note that auto-copy on aEntry has to be disabled.
Definition: attached_list.h:213
iterator insert(iterator position, const element &elem)
inserts an element right before the specified position.
Definition: attached_list.h:357
bool m_bSharedAttachment
Definition: attached_list.h:465
element const * get_pointer_to_element(const element &elem)
returns a const pointer to an element.
Definition: attached_list.h:424
element front()
returns the first element in the list
Definition: attached_list.h:334
A special iterator which allows to iterate over elements in a AttachedElementList.
Definition: attached_list.h:52
AttachedElementListIterator(const AttachedElementListIterator &cpy)
Definition: attached_list.h:60
element * operator->() const
Definition: attached_list.h:72
iterator operator++(int)
Definition: attached_list.h:75
element m_curElem
Definition: attached_list.h:96
iterator operator++()
Definition: attached_list.h:74
TAAEntry m_aaEntry
Definition: attached_list.h:95
AttachedElementListIterator()
Definition: attached_list.h:57
AttachedElementListIterator(element curElem, const TAAEntry &aaEntry)
Definition: attached_list.h:58
TAAEntry::element element
Definition: attached_list.h:54
element operator*() const
note that the * operator is read only.
Definition: attached_list.h:71
bool operator!=(const iterator &iter) const
Definition: attached_list.h:92
iterator operator--(int)
Definition: attached_list.h:83
const iterator & operator=(const iterator &iter)
Definition: attached_list.h:63
bool operator==(const iterator &iter) const
Definition: attached_list.h:91
iterator operator--()
Definition: attached_list.h:82
AttachedElementListIterator< TAAEntry > iterator
Definition: attached_list.h:55
void invalidate()
Definition: attachment_pipe.h:556
bool access(attachment_pipe &attachmentPipe, TAttachment &attachment)
Definition: attachment_pipe.hpp:472
A special iterator which allows to iterate over elements in a AttachedElementList.
Definition: attached_list.h:107
const iterator & operator=(const iterator &iter)
Definition: attached_list.h:120
TAAEntry::element element
Definition: attached_list.h:109
TAAEntry m_aaEntry
Definition: attached_list.h:152
ConstAttachedElementListIterator(const AttachedElementListIterator< TAAEntry > &it)
Definition: attached_list.h:117
ConstAttachedElementListIterator()
Definition: attached_list.h:112
bool operator!=(const iterator &iter) const
Definition: attached_list.h:149
iterator operator++()
Definition: attached_list.h:131
const element * operator->() const
Definition: attached_list.h:129
ConstAttachedElementListIterator(element curElem, const TAAEntry &aaEntry)
Definition: attached_list.h:113
bool operator==(const iterator &iter) const
Definition: attached_list.h:148
iterator operator++(int)
Definition: attached_list.h:132
element operator*() const
note that the * operator is read only.
Definition: attached_list.h:128
ConstAttachedElementListIterator(const ConstAttachedElementListIterator &it)
Definition: attached_list.h:115
element m_curElem
Definition: attached_list.h:153
iterator operator--()
Definition: attached_list.h:139
iterator operator--(int)
Definition: attached_list.h:140
ConstAttachedElementListIterator< TAAEntry > iterator
Definition: attached_list.h:110
the ug namespace
Definition: attached_list.h:186
Entry(const element &p, const element &n)
Definition: attached_list.h:188
Entry()
Definition: attached_list.h:187
element prev
Definition: attached_list.h:189
element next
Definition: attached_list.h:190