Line data Source code
1 : /*
2 : * Copyright (c) 2009-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 __UTIL__SECTION_CONTAINER__IMPL__
34 : #define __UTIL__SECTION_CONTAINER__IMPL__
35 :
36 : #include <cassert>
37 : #include "section_container.h"
38 :
39 : /*
40 : I began work on reverse iterators. All associated code is in comments.
41 : The method erase has not yet been adjusted.
42 : I stopped implementing those reverse-iterators, since they would require quite
43 : some additional instructions during element insertion (Each time the rbegin
44 : iterator of the current and rend iterator of the next section would
45 : have to be adjusted).
46 : If reverse iterators are required, one should think about constructing them
47 : directly from normal iterators in the rbegin / rend calls. This is done
48 : similar in the current implementation of back.
49 : */
50 :
51 : namespace ug
52 : {
53 :
54 : template <class TValue, class TContainer>
55 4 : SectionContainer<TValue, TContainer>::
56 4 : SectionContainer() : m_numElements(0)
57 : {
58 : }
59 :
60 : template <class TValue, class TContainer>
61 : void
62 0 : SectionContainer<TValue, TContainer>::
63 : clear()
64 : {
65 : // clear the container. correct all sections afterwards.
66 : m_container.clear();
67 0 : m_numElements = 0;
68 0 : for(typename SectionVec::iterator iter = m_vSections.begin();
69 0 : iter != m_vSections.end(); ++iter)
70 : {
71 : Section& sec = *iter;
72 : sec.m_elemsBegin = sec.m_elemsEnd = m_container.end();
73 : // sec.m_elemsRBegin = sec.m_elemsREnd = m_container.rend();
74 0 : sec.m_numElements = 0;
75 : }
76 0 : }
77 :
78 : template <class TValue, class TContainer>
79 : void
80 : SectionContainer<TValue, TContainer>::
81 : clear_section(int sectionIndex)
82 : {
83 : assert((sectionIndex >= 0) && (sectionIndex < num_sections()) &&
84 : "ERROR in SectionContainer::clear_section(): bad sectionIndex");
85 :
86 : iterator iterStart = section_begin(sectionIndex);
87 : iterator iterEnd = section_end(sectionIndex);
88 : if(iterStart != iterEnd)
89 : {
90 : m_container.erase(iterStart, iterEnd);
91 : m_vSections[sectionIndex].m_elemsBegin = m_vSections[sectionIndex].m_elemsEnd;
92 : // m_vSections[sectionIndex].m_elemsRBegin = m_vSections[sectionIndex].m_elemsREnd;
93 : m_numElements -= m_vSections[sectionIndex].m_numElements;
94 : m_vSections[sectionIndex].m_numElements = 0;
95 :
96 : // iterators of previous sections have to be adjusted
97 : for(int i = sectionIndex - 1; i >= 0; --i){
98 : if(m_vSections[i].m_numElements > 0){
99 : m_vSections[i].m_elemsEnd = m_vSections[sectionIndex].m_elemsBegin;
100 : break;// we don't have to correct any more sections
101 : }
102 : }
103 :
104 : // same for iterators of following sections
105 : // for(int i = sectionIndex + 1; i < num_sections(); ++i){
106 : // if(m_vSections[i].m_numElements > 0){
107 : // m_vSections[i].m_elemsREnd = m_vSections[sectionIndex].m_elemsRBegin;
108 : // break;// we don't have to correct any more sections
109 : // }
110 : // }
111 : }
112 : }
113 :
114 : template <class TValue, class TContainer>
115 : typename SectionContainer<TValue, TContainer>::iterator
116 : SectionContainer<TValue, TContainer>::
117 : section_begin(int sectionIndex)
118 : {
119 : if(sectionIndex < 0)
120 : return m_container.begin();
121 0 : else if(sectionIndex >= num_sections())
122 : return m_container.end();
123 :
124 0 : return m_vSections[sectionIndex].m_elemsBegin;
125 : }
126 :
127 : template <class TValue, class TContainer>
128 : typename SectionContainer<TValue, TContainer>::const_iterator
129 : SectionContainer<TValue, TContainer>::
130 : section_begin(int sectionIndex) const
131 : {
132 : if(sectionIndex < 0)
133 : return m_container.begin();
134 0 : else if(sectionIndex >= num_sections())
135 : return m_container.end();
136 :
137 0 : return m_vSections[sectionIndex].m_elemsBegin;
138 : }
139 :
140 : template <class TValue, class TContainer>
141 : typename SectionContainer<TValue, TContainer>::iterator
142 : SectionContainer<TValue, TContainer>::
143 : section_end(int sectionIndex)
144 : {
145 0 : if(sectionIndex >= num_sections() || sectionIndex < 0)
146 : return m_container.end();
147 :
148 0 : return m_vSections[sectionIndex].m_elemsEnd;
149 : }
150 :
151 : template <class TValue, class TContainer>
152 : typename SectionContainer<TValue, TContainer>::const_iterator
153 : SectionContainer<TValue, TContainer>::
154 : section_end(int sectionIndex) const
155 : {
156 0 : if(sectionIndex >= num_sections() || sectionIndex < 0)
157 : return m_container.end();
158 :
159 0 : return m_vSections[sectionIndex].m_elemsEnd;
160 : }
161 :
162 : template <class TValue, class TContainer>
163 : typename SectionContainer<TValue, TContainer>::value_type&
164 : SectionContainer<TValue, TContainer>::
165 : front(int secIndex)
166 : {
167 : assert((secIndex >= -1) && (secIndex < num_sections()) && "Bad section index");
168 : if(secIndex == -1)
169 : return m_container.front();
170 : return *m_vSections[secIndex].m_elemsBegin;
171 : }
172 :
173 : template <class TValue, class TContainer>
174 : typename SectionContainer<TValue, TContainer>::value_type&
175 : SectionContainer<TValue, TContainer>::
176 : back(int secIndex)
177 : {
178 : assert((secIndex >= -1) && (secIndex < num_sections()) && "Bad section index");
179 : if(secIndex == -1)
180 : return m_container.back();
181 :
182 : // things are a little more complicated here, since there is no rbegin
183 : // check whether the last element is the last element of the underlying
184 : // container, too. If so, we'll return the last element of this container.
185 : if(m_vSections[secIndex].m_elemsEnd == m_container.end())
186 : return m_container.back();
187 :
188 : // since it is not, it points to the element in m_container, which
189 : // directly follows the last element of this section.
190 : // we'll thus create a reverse iterator on m_elemsEnd, increase it
191 : // once, and return the element, to which the iterator now points.
192 : iterator titer(m_vSections[secIndex].m_elemsEnd);
193 : --titer;
194 : return *titer;
195 : }
196 :
197 : template <class TValue, class TContainer>
198 : void
199 3 : SectionContainer<TValue, TContainer>::
200 : add_sections(int num)
201 : {
202 6 : for(int i = 0; i < num; ++i)
203 3 : m_vSections.push_back(Section(m_container.end(), m_container.end(),
204 : //m_container.rend(), m_container.rend(),
205 : 0));
206 3 : }
207 :
208 : template <class TValue, class TContainer>
209 : uint
210 : SectionContainer<TValue, TContainer>::
211 : num_elements(int sectionIndex) const
212 : {
213 : assert((sectionIndex >= 0) &&
214 : "ERROR in SectionContainer::num_elements(): bad sectionIndex");
215 :
216 7 : if(sectionIndex >= num_sections())
217 : return 0;
218 7 : return m_vSections[sectionIndex].m_numElements;
219 : }
220 :
221 : template <class TValue, class TContainer>
222 : typename SectionContainer<TValue, TContainer>::iterator
223 7 : SectionContainer<TValue, TContainer>::
224 : insert(const TValue& val, int sectionIndex)
225 : {
226 : assert((sectionIndex >= 0) &&
227 : "ERROR in SectionContainer::insert(): bad sectionIndex");
228 :
229 : iterator nHandle;
230 :
231 : // check if a new section has to be created.
232 7 : if(sectionIndex >= num_sections())
233 3 : add_sections(sectionIndex - num_sections() + 1);
234 :
235 : // if the current section is empty, we have to initialize it.
236 7 : if(num_elements(sectionIndex) == 0)
237 : {
238 : // it's the first element in this section.
239 : // iterate through the sections and find the next one which is not empty
240 : int nextValidSection = -1;
241 3 : for(int i = sectionIndex + 1; i < num_sections(); ++i){
242 0 : if(num_elements(i) > 0){
243 : nextValidSection = i;
244 : break;
245 : }
246 : }
247 :
248 : // we have to find the previous valid section, too
249 : int prevValidSection = -1;
250 3 : for(int i = sectionIndex - 1; i >= 0; --i){
251 0 : if(num_elements(i) > 0){
252 : prevValidSection = i;
253 : break;
254 : }
255 : }
256 :
257 : // get the iterator before which the element shall be inserted.
258 3 : if(nextValidSection != -1){
259 0 : m_vSections[sectionIndex].m_elemsEnd = m_vSections[nextValidSection].m_elemsBegin;
260 : }
261 : else
262 3 : m_vSections[sectionIndex].m_elemsEnd = m_container.end();
263 :
264 : // insert the element
265 3 : nHandle = m_vSections[sectionIndex].m_elemsBegin = m_container.insert(m_vSections[sectionIndex].m_elemsEnd, val);
266 3 : m_vSections[sectionIndex].m_numElements++;
267 : // m_vSections[sectionIndex].m_elemsRBegin = reverse_iterator(nHandle);
268 :
269 : // adjust rend iterator of the next section
270 : // if(nextValidSection != -1)
271 : // m_vSections[nextValidSection].m_elemsREnd = m_vSections[sectionIndex].m_elemsRBegin;
272 :
273 : // adjust the end-iterator of the previous valid section.
274 3 : if(prevValidSection != -1){
275 0 : m_vSections[prevValidSection].m_elemsEnd = m_vSections[sectionIndex].m_elemsBegin;
276 : // m_vSections[sectionIndex].m_elemsREnd = m_vSections[prevValidSection].m_elemsRBegin;
277 : }
278 : // else
279 : // m_vSections[sectionIndex].m_elemsREnd = m_container.rend();
280 : }
281 : else
282 : {
283 : // the section is not empty. Simply insert the element before the sections end-iterator.
284 4 : nHandle = m_container.insert(m_vSections[sectionIndex].m_elemsEnd, val);
285 4 : m_vSections[sectionIndex].m_numElements++;
286 : }
287 :
288 7 : m_numElements++;
289 :
290 7 : return nHandle;
291 : }
292 :
293 : template <class TValue, class TContainer>
294 : void
295 7 : SectionContainer<TValue, TContainer>::
296 : erase(const typename ug::SectionContainer<TValue, TContainer>::iterator& elemHandle, int sectionIndex)
297 : {
298 : assert((sectionIndex >= 0) && (sectionIndex < num_sections()) &&
299 : "ERROR in SectionContainer::erase(): bad sectionIndex");
300 :
301 : iterator hNext;
302 :
303 : // check if the element is the first in the section.
304 : // if this is the case, we have to update the begin-handle of this section
305 7 : if(elemHandle == m_vSections[sectionIndex].m_elemsBegin)
306 : {
307 : // erase the element
308 7 : hNext = m_container.erase(elemHandle);
309 7 : m_vSections[sectionIndex].m_numElements--;
310 :
311 : // update the current section and the previous valid one.
312 : m_vSections[sectionIndex].m_elemsBegin = hNext;
313 :
314 : // change begin and end iterators in all preceding empty sections
315 : // and end iterator in the preceding non-empty section
316 7 : for (int i = sectionIndex - 1; i >= 0; --i)
317 : {
318 0 : if (num_elements(i) <= 0)
319 : {
320 0 : m_vSections[i].m_elemsBegin = m_vSections[i].m_elemsEnd = hNext;
321 : continue;
322 : }
323 : m_vSections[i].m_elemsEnd = hNext;
324 : break;
325 : }
326 : }
327 : else
328 : {
329 : // erase the element
330 0 : hNext = m_container.erase(elemHandle);
331 0 : m_vSections[sectionIndex].m_numElements--;
332 : }
333 :
334 7 : m_numElements--;
335 :
336 : // check if hNext points to the end of the container. If so we will adjust the
337 : // m_elemsEnd iterator of the section.
338 : // included for safety reasons. Shouldn't be needed...
339 :
340 7 : if(hNext == m_container.end())
341 : m_vSections[sectionIndex].m_elemsEnd = m_container.end();
342 7 : }
343 :
344 : template <class TValue, class TContainer>
345 : void
346 0 : SectionContainer<TValue, TContainer>::
347 : append(const SectionContainer& c)
348 : {
349 0 : for(int i = 0; i < c.num_sections(); ++i){
350 0 : for(const_iterator iter = c.section_begin(i); iter != c.section_end(i);){
351 0 : const TValue& val = *iter;
352 : ++iter;
353 0 : insert(val, i);
354 : }
355 : }
356 0 : }
357 :
358 : template <class TValue, class TContainer>
359 : void
360 0 : SectionContainer<TValue, TContainer>::
361 : transfer_elements(SectionContainer& c)
362 : {
363 0 : for(int i = 0; i < c.num_sections(); ++i){
364 0 : for(iterator iter = c.section_begin(i); iter != c.section_end(i);){
365 0 : const TValue& val = *iter;
366 : iterator iterOld = iter;
367 : ++iter;
368 0 : c.erase(iterOld, i);
369 0 : insert(val, i);
370 : }
371 : }
372 0 : }
373 :
374 : }
375 :
376 : #endif
|
