Debian Codegraph @

dune/istl/paamg/hierarchy.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 #ifndef DUNE_AMGHIERARCHY_HH
6 #define DUNE_AMGHIERARCHY_HH
7
8 #include <list>
9 #include <memory>
10 #include <limits>
11 #include <dune/common/stdstreams.hh>
12 #include <dune/common/timer.hh>
13 #include <dune/common/bigunsignedint.hh>
14 #include <dune/istl/paamg/construction.hh>
15
16 namespace Dune
17 {
18 namespace Amg
19 {
20 /**
21 * @addtogroup ISTL_PAAMG
22 *
23 * @{
24 */
25
26 /** @file
27 * @author Markus Blatt
28 * @brief Provides a classes representing the hierarchies in AMG.
29 */
30
31 /**
32 * @brief A hierarchy of containers (e.g. matrices or vectors)
33 *
34 * Because sometimes a redistribution of the parallel data might be
35 * advisable one can add redistributed version of the container at
36 * each level.
37 */
38 template<typename T, typename A=std::allocator<T> >
39 class Hierarchy
40 {
41 public:
42 /**
43 * @brief The type of the container we store.
44 */
45 typedef T MemberType;
46
47 template<typename T1, typename T2>
48 class LevelIterator;
49
50 private:
51 /**
52 * @brief An element in the hierarchy.
53 */
54 struct Element
55 {
56 friend class LevelIterator<Hierarchy<T,A>, T>;
57 friend class LevelIterator<const Hierarchy<T,A>, const T>;
58
59 /** @brief The next coarser element in the list. */
60 std::weak_ptr<Element> coarser_;
61
62 /** @brief The next finer element in the list. */
63 std::shared_ptr<Element> finer_;
64
65 /** @brief Pointer to the element. */
66 std::shared_ptr<MemberType> element_;
67
68 /** @brief The redistributed version of the element. */
69 std::shared_ptr<MemberType> redistributed_;
70 };
71 public:
72
73 /**
74 * @brief The allocator to use for the list elements.
75 */
76 using Allocator = typename std::allocator_traits<A>::template rebind_alloc<Element>;
77
78 typedef typename ConstructionTraits<T>::Arguments Arguments;
79
80 /**
81 * @brief Construct a new hierarchy.
82 * @param first std::shared_ptr to the first element in the hierarchy.
83 */
84 Hierarchy(const std::shared_ptr<MemberType> & first);
85
86 /**
87 * @brief Construct an empty hierarchy.
88 */
89 Hierarchy() : levels_(0)
90 {}
91
92 /**
93 * @brief Copy constructor (deep copy!).
94 */
95 Hierarchy(const Hierarchy& other);
96
97 /**
98 * @brief Add an element on a coarser level.
99 * @param args The arguments needed for the construction.
100 */
101 void addCoarser(Arguments& args);
102
103 void addRedistributedOnCoarsest(Arguments& args);
104
105 /**
106 * @brief Add an element on a finer level.
107 * @param args The arguments needed for the construction.
108 */
109 void addFiner(Arguments& args);
110
111 /**
112 * @brief Iterator over the levels in the hierarchy.
113 *
114 * operator++() moves to the next coarser level in the hierarchy.
115 * while operator--() moves to the next finer level in the hierarchy.
116 */
117 template<class C, class T1>
118 class LevelIterator
119 : public BidirectionalIteratorFacade<LevelIterator<C,T1>,T1,T1&>
120 {
121 friend class LevelIterator<typename std::remove_const<C>::type,
122 typename std::remove_const<T1>::type >;
123 friend class LevelIterator<const typename std::remove_const<C>::type,
124 const typename std::remove_const<T1>::type >;
125
126 public:
127 /** @brief Constructor. */
128 LevelIterator() = default;
129
130 LevelIterator(std::shared_ptr<Element> element)
131 : element_(std::move(element))
132 {}
133
134 /** @brief Copy constructor. */
135 template <class C_, class T1_,
136 std::enable_if_t<std::is_same_v<std::remove_const_t<C>, std::remove_const_t<C_>>, int> = 0,
137 std::enable_if_t<std::is_same_v<std::remove_const_t<T1>, std::remove_const_t<T1_>>, int> = 0>
138 LevelIterator(const LevelIterator<C_,T1_>& other)
139 : element_(other.element_)
140 {}
141
142 template <class C_, class T1_,
143 std::enable_if_t<std::is_same_v<std::remove_const_t<C>, std::remove_const_t<C_>>, int> = 0,
144 std::enable_if_t<std::is_same_v<std::remove_const_t<T1>, std::remove_const_t<T1_>>, int> = 0>
145 LevelIterator& operator=(const LevelIterator<C_,T1_>& other)
146 {
147 element_ = other.element_;
148 return *this;
149 }
150
151 /**
152 * @brief Equality check.
153 */
154 bool equals(const LevelIterator<typename std::remove_const<C>::type,
155 typename std::remove_const<T1>::type>& other) const
156 {
157 return element_ == other.element_;
158 }
159
160 /**
161 * @brief Equality check.
162 */
163 bool equals(const LevelIterator<const typename std::remove_const<C>::type,
164 const typename std::remove_const<T1>::type>& other) const
165 {
166 return element_ == other.element_;
167 }
168
169 /** @brief Dereference the iterator. */
170 T1& dereference() const
171 {
172 return *(element_->element_);
173 }
174
175 /** @brief Move to the next coarser level */
176 void increment()
177 {
178 element_ = element_->coarser_.lock();
179 }
180
181 /** @brief Move to the next fine level */
182 void decrement()
183 {
184 element_ = element_->finer_;
185 }
186
187 /**
188 * @brief Check whether there was a redistribution at the current level.
189 * @return True if there is a redistributed version of the container at the current level.
190 */
191 bool isRedistributed() const
192 {
193 return (bool)element_->redistributed_;
194 }
195
196 /**
197 * @brief Get the redistributed container.
198 * @return The redistributed container.
199 */
200 T1& getRedistributed() const
201 {
202 assert(element_->redistributed_);
203 return *element_->redistributed_;
204 }
205 void addRedistributed(std::shared_ptr<T1> t)
206 {
207 element_->redistributed_ = t;
208 }
209
210 void deleteRedistributed()
211 {
212 element_->redistributed_ = nullptr;
213 }
214
215 private:
216 std::shared_ptr<Element> element_ = {};
217 };
218
219 /** @brief Type of the mutable iterator. */
220 typedef LevelIterator<Hierarchy<T,A>,T> Iterator;
221
222 /** @brief Type of the const iterator. */
223 typedef LevelIterator<const Hierarchy<T,A>, const T> ConstIterator;
224
225 /**
226 * @brief Get an iterator positioned at the finest level.
227 * @return An iterator positioned at the finest level.
228 */
229 Iterator finest();
230
231 /**
232 * @brief Get an iterator positioned at the coarsest level.
233 * @return An iterator positioned at the coarsest level.
234 */
235 Iterator coarsest();
236
237
238 /**
239 * @brief Get an iterator positioned at the finest level.
240 * @return An iterator positioned at the finest level.
241 */
242 ConstIterator finest() const;
243
244 /**
245 * @brief Get an iterator positioned at the coarsest level.
246 * @return An iterator positioned at the coarsest level.
247 */
248 ConstIterator coarsest() const;
249
250 /**
251 * @brief Get the number of levels in the hierarchy.
252 * @return The number of levels.
253 */
254 std::size_t levels() const;
255
256 private:
257 /** @brief fix memory management of the finest element in the hierarchy
258
259 This object is passed in from outside, so that we have to
260 deal with shared ownership.
261 */
262 std::shared_ptr<MemberType> originalFinest_;
263 /** @brief The finest element in the hierarchy. */
264 std::shared_ptr<Element> finest_;
265 /** @brief The coarsest element in the hierarchy. */
266 std::shared_ptr<Element> coarsest_;
267 /** @brief The allocator for the list elements. */
268 Allocator allocator_;
269 /** @brief The number of levels in the hierarchy. */
270 int levels_;
271 };
272
273 template<class T, class A>
274 Hierarchy<T,A>::Hierarchy(const std::shared_ptr<MemberType> & first)
275 : originalFinest_(first)
276 {
277 finest_ = std::allocate_shared<Element>(allocator_);
278 finest_->element_ = originalFinest_;
279 coarsest_ = finest_;
280 levels_ = 1;
281 }
282
283 //! \brief deep copy of a given hierarchy
284 //TODO: do we actually want to support this? This might be very expensive?!
285 template<class T, class A>
286 Hierarchy<T,A>::Hierarchy(const Hierarchy& other)
287 : allocator_(other.allocator_),
288 levels_(other.levels_)
289 {
290 if(!other.finest_)
291 {
292 finest_=coarsest_=nullptr;
293 return;
294 }
295 finest_ = std::allocate_shared<Element>(allocator_);
296 std::shared_ptr<Element> finer_;
297 std::shared_ptr<Element> current_ = finest_;
298 std::weak_ptr<Element> otherWeak_ = other.finest_;
299
300 while(! otherWeak_.expired())
301 {
302 // create shared_ptr from weak_ptr, we just checked that this is safe
303 std::shared_ptr<Element> otherCurrent_ = std::shared_ptr<Element>(otherWeak_);
304 // clone current level
305 //TODO: should we use the allocator?
306 current_->element_ =
307 std::make_shared<MemberType>(*(otherCurrent_->element_));
308 current_->finer_=finer_;
309 if(otherCurrent_->redistributed_)
310 current_->redistributed_ =
311 std::make_shared<MemberType>(*(otherCurrent_->redistributed_));
312 finer_=current_;
313 if(not otherCurrent_->coarser_.expired())
314 {
315 auto c = std::allocate_shared<Element>(allocator_);
316 current_->coarser_ = c;
317 current_ = c;
318 }
319 // go to coarser level
320 otherWeak_ = otherCurrent_->coarser_;
321 }
322 coarsest_=current_;
323 }
324
325 template<class T, class A>
326 std::size_t Hierarchy<T,A>::levels() const
327 {
328 return levels_;
329 }
330
331 template<class T, class A>
332 void Hierarchy<T,A>::addRedistributedOnCoarsest(Arguments& args)
333 {
334 coarsest_->redistributed_ = ConstructionTraits<MemberType>::construct(args);
335 }
336
337 template<class T, class A>
338 void Hierarchy<T,A>::addCoarser(Arguments& args)
339 {
340 if(!coarsest_) {
341 // we have no levels at all...
342 assert(!finest_);
343 // allocate into the shared_ptr
344 originalFinest_ = ConstructionTraits<MemberType>::construct(args);
345 coarsest_ = std::allocate_shared<Element>(allocator_);
346 coarsest_->element_ = originalFinest_;
347 finest_ = coarsest_;
348 }else{
349 auto old_coarsest = coarsest_;
350 coarsest_ = std::allocate_shared<Element>(allocator_);
351 coarsest_->finer_ = old_coarsest;
352 coarsest_->element_ = ConstructionTraits<MemberType>::construct(args);
353 old_coarsest->coarser_ = coarsest_;
354 }
355 ++levels_;
356 }
357
358
359 template<class T, class A>
360 void Hierarchy<T,A>::addFiner(Arguments& args)
361 {
362 //TODO: wouldn't it be better to do this in the constructor?'
363 if(!finest_) {
364 // we have no levels at all...
365 assert(!coarsest_);
366 // allocate into the shared_ptr
367 originalFinest_ = ConstructionTraits<MemberType>::construct(args);
368 finest_ = std::allocate_shared<Element>(allocator_);
369 finest_->element = originalFinest_;
370 coarsest_ = finest_;
371 }else{
372 finest_->finer_ = std::allocate_shared<Element>(allocator_);
373 finest_->finer_->coarser_ = finest_;
374 finest_ = finest_->finer_;
375 finest_->element = ConstructionTraits<T>::construct(args);
376 }
377 ++levels_;
378 }
379
380 template<class T, class A>
381 typename Hierarchy<T,A>::Iterator Hierarchy<T,A>::finest()
382 {
383 return Iterator(finest_);
384 }
385
386 template<class T, class A>
387 typename Hierarchy<T,A>::Iterator Hierarchy<T,A>::coarsest()
388 {
389 return Iterator(coarsest_);
390 }
391
392 template<class T, class A>
393 typename Hierarchy<T,A>::ConstIterator Hierarchy<T,A>::finest() const
394 {
395 return ConstIterator(finest_);
396 }
397
398 template<class T, class A>
399 typename Hierarchy<T,A>::ConstIterator Hierarchy<T,A>::coarsest() const
400 {
401 return ConstIterator(coarsest_);
402 }
403 /** @} */
404 } // namespace Amg
405 } // namespace Dune
406
407 #endif