Line data Source code
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 :
42 : ////////////////////////////////////////////////////////////////////////////////
43 : // predeclarations
44 : template <class TAAEntry> class ConstAttachedElementListIterator;
45 :
46 : ////////////////////////////////////////////////////////////////////////////////
47 : /// A special iterator which allows to iterate over elements in a AttachedElementList.
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;
55 : typedef AttachedElementListIterator<TAAEntry> iterator;
56 :
57 7 : AttachedElementListIterator() : m_curElem(NULL) {}
58 : AttachedElementListIterator(element curElem, const TAAEntry& aaEntry) :
59 21 : m_aaEntry(aaEntry), m_curElem(curElem) {}
60 20 : AttachedElementListIterator(const AttachedElementListIterator& cpy) :
61 21 : m_aaEntry(cpy.m_aaEntry), m_curElem(cpy.m_curElem) {}
62 :
63 : const iterator& operator=(const iterator& iter)
64 : {
65 20 : m_aaEntry = iter.m_aaEntry;
66 20 : m_curElem = iter.m_curElem;
67 0 : return *this;
68 : }
69 :
70 : /// note that the * operator is read only.
71 12 : element operator*() const {return m_curElem;}
72 : element* operator->() const {return &m_curElem;}
73 :
74 0 : iterator operator++() {m_curElem = m_aaEntry[m_curElem].next; return *this;}
75 : iterator operator++(int)
76 : {// post-increment
77 : iterator iter = *this;
78 0 : m_curElem = m_aaEntry[m_curElem].next;
79 : return iter;
80 : }
81 :
82 0 : iterator operator--() {m_curElem = m_aaEntry[m_curElem].prev; return *this;}
83 : iterator operator--(int)
84 : {
85 : iterator iter = *this;
86 : m_curElem = m_aaEntry[m_curElem].prev;
87 : return iter;
88 : }
89 :
90 : // note that each element may only be in the list once.
91 7 : bool operator==(const iterator& iter) const {return m_curElem == iter.m_curElem;}
92 0 : bool operator!=(const iterator& iter) const {return m_curElem != iter.m_curElem;}
93 :
94 : private:
95 : TAAEntry m_aaEntry;
96 : element m_curElem;
97 :
98 : friend class ConstAttachedElementListIterator<TAAEntry>;
99 : };
100 :
101 : ////////////////////////////////////////////////////////////////////////////////
102 : /// A special iterator which allows to iterate over elements in a AttachedElementList.
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;
110 : typedef ConstAttachedElementListIterator<TAAEntry> iterator;
111 :
112 0 : ConstAttachedElementListIterator() : m_curElem(NULL) {}
113 : ConstAttachedElementListIterator(element curElem, const TAAEntry& aaEntry) :
114 : m_aaEntry(aaEntry), m_curElem(curElem) {}
115 0 : ConstAttachedElementListIterator(const ConstAttachedElementListIterator& it) :
116 0 : m_aaEntry(it.m_aaEntry), m_curElem(it.m_curElem) {}
117 : ConstAttachedElementListIterator(const AttachedElementListIterator<TAAEntry>& it) :
118 0 : m_aaEntry(it.m_aaEntry), m_curElem(it.m_curElem) {}
119 :
120 : const iterator& operator=(const iterator& iter)
121 : {
122 0 : m_aaEntry = iter.m_aaEntry;
123 0 : m_curElem = iter.m_curElem;
124 : return *this;
125 : }
126 :
127 : /// note that the * operator is read only.
128 0 : element operator*() const {return m_curElem;}
129 : const element* operator->() const {return &m_curElem;}
130 :
131 0 : iterator operator++() {m_curElem = m_aaEntry[m_curElem].next; return *this;}
132 : iterator operator++(int)
133 : {// post-increment
134 : iterator iter = *this;
135 0 : m_curElem = m_aaEntry[m_curElem].next;
136 : return iter;
137 : }
138 :
139 : iterator operator--() {m_curElem = m_aaEntry[m_curElem].prev; return *this;}
140 : iterator operator--(int)
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 0 : bool operator==(const iterator& iter) const {return m_curElem == iter.m_curElem;}
149 0 : bool operator!=(const iterator& iter) const {return m_curElem != iter.m_curElem;}
150 :
151 : private:
152 : TAAEntry m_aaEntry;
153 : element m_curElem;
154 : };
155 :
156 : ////////////////////////////////////////////////////////////////////////////////
157 : /// A linked list of elements living in an attachment
158 : /** This is a highly specialized linked list mainly (only!) used in the Grid,
159 : * SubsetHandler, Selector, ... classes to maintain a list of GridObjects.
160 : *
161 : * Only elements registered at the underlying attachment pipe may be added
162 : * to the list. Note that each element may only be added once.
163 : *
164 : * Make sure that the attachment pipe on which the list operates
165 : * exists at least as long as the list itself, or call set_pipe(NULL),
166 : * if the pipe is erased before.
167 : *
168 : * This list assumes that TAttachmentPipe::element is a pointer type.
169 : *
170 : * Note that instances of this class are never lightweight, since memory
171 : * for a potentially full list is allocated in the attachment pipe.
172 : *
173 : * If the list operates on a shared attachment, the one who created the
174 : * attachment is responsible for releasing it.
175 : *
176 : * \warning Special care has to be taken with this type of list. It is e.g. not
177 : * possible to insert the same element multiple times into the list.
178 : * Instead upon new insertion, the old entry will be erased.
179 : */
180 : template <class TAttachmentPipe>
181 : class AttachedElementList
182 : {
183 : public:
184 : typedef typename TAttachmentPipe::element element;
185 :
186 : struct Entry{
187 0 : Entry() : prev(NULL), next(NULL) {}
188 7 : Entry(const element& p, const element& n) : prev(p), next(n) {}
189 : element prev;
190 : element next;
191 : };
192 :
193 : typedef Attachment<Entry> AEntry;
194 : typedef typename TAttachmentPipe::ElementHandler ElemHandler;
195 : typedef AttachmentAccessor<element, AEntry, ElemHandler> AAEntry;
196 :
197 : typedef AttachedElementListIterator<AAEntry> iterator;
198 : typedef ConstAttachedElementListIterator<AAEntry> const_iterator;
199 :
200 : public:
201 4 : AttachedElementList(TAttachmentPipe* pipe = NULL) :
202 4 : m_pipe(NULL),
203 : m_aEntry("AttachedElementList_Entry", false),
204 4 : m_front(NULL),
205 4 : m_back(NULL),
206 4 : m_bSharedAttachment(false)
207 : {
208 : if(pipe)
209 : set_pipe(pipe);
210 : }
211 :
212 : /// Note that auto-copy on aEntry has to be disabled.
213 : AttachedElementList(AEntry aEntry) :
214 : m_pipe(NULL),
215 : m_aEntry(aEntry),
216 : m_front(NULL),
217 : m_back(NULL),
218 : m_bSharedAttachment(false)
219 : {}
220 :
221 : /// Note that auto-copy on aEntry has to be disabled.
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 :
233 : AttachedElementList(const AttachedElementList& ael) : m_pipe(NULL)
234 : {
235 : m_bSharedAttachment = ael.m_bSharedAttachment;
236 : if(m_bSharedAttachment)
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 :
249 : ~AttachedElementList()
250 : {
251 4 : set_pipe(NULL);
252 : }
253 :
254 0 : const AttachedElementList& operator=(const AttachedElementList& ael)
255 : {
256 : clear();
257 :
258 0 : if(ael.m_bSharedAttachment)
259 0 : set_pipe(ael.m_pipe, ael.m_aEntry);
260 : else
261 0 : set_pipe(ael.m_pipe);
262 :
263 0 : if(ael.m_front){
264 : iterator iter(ael.m_front, m_aaEntry);
265 0 : while(*iter){
266 : push_back(*iter);
267 : ++iter;
268 : }
269 : }
270 :
271 0 : return *this;
272 : }
273 :
274 : /// set the attachment pipe on which the list shall operate
275 12 : void set_pipe(TAttachmentPipe* pipe)
276 : {
277 12 : if(!m_bSharedAttachment && m_pipe)
278 4 : m_pipe->detach(m_aEntry);
279 : m_aaEntry.invalidate();
280 :
281 12 : m_pipe = pipe;
282 12 : if(m_pipe){
283 4 : if(!m_pipe->has_attachment(m_aEntry))
284 4 : m_pipe->attach(m_aEntry);
285 4 : m_aaEntry.access(*m_pipe, m_aEntry);
286 : }
287 :
288 12 : m_front = m_back = NULL;
289 12 : }
290 :
291 : /// Sets the pipe and a shared entry-attachment on which the list will operate
292 : /** Note that auto-copy on aEntry has to be disabled.*/
293 0 : void set_pipe(TAttachmentPipe* pipe, AEntry aEntry)
294 : {
295 0 : if(!m_bSharedAttachment && m_pipe)
296 0 : m_pipe->detach(m_aEntry);
297 : m_aaEntry.invalidate();
298 :
299 0 : m_pipe = pipe;
300 : m_aEntry = aEntry;
301 0 : m_bSharedAttachment = true;
302 :
303 0 : if(m_pipe){
304 : // since we use a shared attachment in this case, it may already be
305 : // attached to the pipe.
306 0 : if(!m_pipe->has_attachment(m_aEntry))
307 0 : m_pipe->attach(m_aEntry);
308 0 : m_aaEntry.access(*m_pipe, m_aEntry);
309 : }
310 :
311 0 : m_front = m_back = NULL;
312 0 : }
313 :
314 : /// clears the list. begin() == end() afterwards.
315 : void clear()
316 : {
317 0 : if(m_pipe){
318 : iterator iter = begin();
319 0 : while(iter != end()){
320 : element elem = *iter;
321 : iter++;
322 0 : m_aaEntry[elem] = Entry();
323 : }
324 :
325 0 : m_front = m_back = NULL;
326 : }
327 : }
328 :
329 :
330 : /// retunrs true if the list is empty
331 7 : bool empty() const {return m_front == NULL;}
332 :
333 : /// returns the first element in the list
334 : element front() {return m_front;}
335 : /// returns the last element in the list
336 : element back() {return m_back;}
337 :
338 : /// returns the first element in the list (const)
339 : const element front() const {return m_front;}
340 : /// returns the last element in the list (const)
341 : const element back() const {return m_back;}
342 :
343 : /// pushes an element to the end of the list
344 : void push_back(const element& elem)
345 : {
346 7 : m_aaEntry[elem] = Entry(m_back, NULL);
347 7 : if(empty())
348 3 : m_front = elem;
349 : else
350 4 : m_aaEntry[m_back].next = elem;
351 7 : m_back = elem;
352 7 : }
353 :
354 : /// inserts an element right before the specified position.
355 : /** returns the iterator of the newly inserted element.
356 : */
357 7 : iterator insert(iterator position, const element& elem)
358 : {
359 7 : if(empty() || !(*position))
360 : push_back(elem);
361 : else{
362 : Entry& entry = m_aaEntry[*position];
363 :
364 0 : if(entry.prev){
365 0 : m_aaEntry[entry.prev].next = elem;
366 0 : m_aaEntry[elem].prev = entry.prev;
367 : }
368 : else{
369 0 : m_aaEntry[elem].prev = NULL;
370 0 : m_front = elem;
371 : }
372 :
373 0 : m_aaEntry[elem].next = *position;
374 0 : entry.prev = elem;
375 : }
376 :
377 7 : return get_iterator(elem);
378 : }
379 :
380 : /// erases the element at the given position
381 : /** returns an iterator to the element directly behind position.
382 : */
383 7 : iterator erase(iterator position)
384 : {
385 : Entry& entry = m_aaEntry[*position];
386 7 : if(entry.prev)
387 0 : m_aaEntry[entry.prev].next = entry.next;
388 : else
389 7 : m_front = entry.next;
390 :
391 7 : if(entry.next)
392 4 : m_aaEntry[entry.next].prev = entry.prev;
393 : else
394 3 : m_back = entry.prev;
395 :
396 : // get next element and reset entry.
397 : element nextElem = entry.next;
398 7 : entry = Entry();
399 7 : return iterator(nextElem, m_aaEntry);
400 : }
401 :
402 : /// erases a sequence of entries
403 : iterator erase(iterator begin, iterator end)
404 : {
405 : iterator iter = begin;
406 : while(iter != end){
407 : iterator titer = iter++;
408 : erase(titer);
409 : }
410 : return iter;
411 : }
412 :
413 : /// returns the iterator to the given element
414 : /** Note that the return value is undefined if element is not
415 : * a member of the list!
416 : */
417 : iterator get_iterator(const element& elem)
418 : {
419 7 : return iterator(elem, m_aaEntry);
420 : }
421 :
422 : /// returns a const pointer to an element.
423 : /** This pointer is valid until the content of the list is changed.*/
424 : element const* get_pointer_to_element(const element& elem)
425 : {
426 0 : if(elem == m_front)
427 0 : return &m_front;
428 0 : return &m_aaEntry[m_aaEntry[elem].prev].next;
429 : }
430 :
431 : /// returns true if the element is in the list
432 : bool is_in_list(const element& elem)
433 : {
434 : return (m_front == elem) || (m_aaEntry[elem].prev != NULL);
435 : }
436 : /// returns an iterator to the beginning of the sequence.
437 21 : iterator begin() {return iterator(m_front, m_aaEntry);}
438 :
439 : /// returns an iterator to the end of the sequence.
440 : /** Note that this is the iterator to the element behind the last one.*/
441 0 : iterator end() {return iterator(NULL, m_aaEntry);}
442 :
443 : /// returns an iterator to the beginning of the sequence.
444 0 : const_iterator begin() const {return const_iterator(m_front, m_aaEntry);}
445 :
446 : /// returns an iterator to the end of the sequence.
447 : /** Note that this is the iterator to the element behind the last one.*/
448 0 : 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
455 : AEntry m_aEntry;
456 :
457 : // the attachment accessor with which the entries are accessed
458 : AAEntry m_aaEntry;
459 :
460 : // front and back elements
461 : element m_front;
462 : element m_back;
463 :
464 : // tells whether the entry attachment is shared with other lists
465 : bool m_bSharedAttachment;
466 : };
467 :
468 :
469 :
470 : }// end of namespace
471 :
472 : #endif
|
