Debian Codegraph @

include/deal.II/numerics/history.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2018 - 2023 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_storage_h
16 #define dealii_storage_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/exceptions.h>
21
22 #include <deque>
23 #include <memory>
24 #include <type_traits>
25
26 DEAL_II_NAMESPACE_OPEN
27
28 /**
29 * A helper class to store a finite-size collection of objects of type `T`.
30 * If the number of elements exceeds the specified maximum size of the
31 * container, the oldest element is removed. Additionally, random access and
32 * removal of elements is implemented. Indexing is done relative to the last
33 * added element.
34 *
35 * In order to optimize the container for usage with
36 * memory-demanding objects (i.e. linear algebra vectors), the removal of an
37 * element does not free the memory. Instead the element
38 * is being kept in a separate cache so that subsequent addition does not
39 * require re-allocation of memory.
40 *
41 * The primary usage of this class is in solvers to store a history of vectors.
42 * That is, if at the iteration $k$ we store $m$ vectors from previous
43 * iterations
44 * $\{k-1,k-2,...,k-m\}$, then addition of the new element will make
45 * the object contain elements from iterations $\{k,k-1,k-2,...,k-m+1\}$.
46 */
47 template <typename T>
48 class FiniteSizeHistory
49 {
50 public:
51 static_assert(
52 std::is_default_constructible_v<T>,
53 "This class requires that the elements of type T are default constructible.");
54
55 /**
56 * Constructor.
57 *
58 * @param max_elements maximum number of elements to be stored in the
59 * history.
60 */
61 FiniteSizeHistory(const std::size_t max_elements = 0);
62
63 /**
64 * Add new object by copying.
65 * If the maximum number of elements is reached, the oldest element is
66 * removed.
67 */
68 void
69 add(const T &element);
70
71 /**
72 * Remove an element with index @p index,
73 * counting from the last added element.
74 * `index==0` therefore corresponds to removing
75 * the newset element.
76 */
77 void
78 remove(const std::size_t index);
79
80 /**
81 * Read/write access to an element with index @p index,
82 * counting from the last added element.
83 * `index==0` therefore corresponds to the newset element.
84 */
85 T &
86 operator[](const std::size_t index);
87
88 /**
89 * Read access to an element with index @p index,
90 * counting from the last added element.
91 * `index==0` therefore corresponds to the newset element.
92 */
93 const T &
94 operator[](const std::size_t index) const;
95
96 /**
97 * Return the current size of the history.
98 */
99 std::size_t
100 size() const;
101
102 /**
103 * Return the maximum allowed size of the history.
104 */
105 std::size_t
106 max_size() const;
107
108 /**
109 * Clear the contents, including the cache.
110 */
111 void
112 clear();
113
114 private:
115 /**
116 * Maximum number of elements to be stored.
117 */
118 std::size_t max_n_elements;
119
120 /**
121 * A deque which stores the data.
122 */
123 std::deque<std::unique_ptr<T>> data;
124
125 /**
126 * A deque to cache data, in particular for the case when
127 * removal is followed by addition.
128 */
129 std::deque<std::unique_ptr<T>> cache;
130 };
131
132
133
134 // ------------------- inline and template functions ----------------
135 #ifndef DOXYGEN
136
137
138
139 template <typename T>
140 FiniteSizeHistory<T>::FiniteSizeHistory(const std::size_t max_elements)
141 : max_n_elements(max_elements)
142 {}
143
144
145
146 template <typename T>
147 void
148 FiniteSizeHistory<T>::remove(const std::size_t ind)
149 {
150 AssertIndexRange(ind, data.size());
151 auto el = std::move(data[ind]);
152 data.erase(data.begin() + ind);
153
154 cache.push_back(std::move(el));
155
156 // whatever we do, we shall not store more than the maximum number of
157 // elements
158 Assert(data.size() + cache.size() <= max_n_elements, ExcInternalError());
159 }
160
161
162
163 template <typename T>
164 void
165 FiniteSizeHistory<T>::add(const T &element)
166 {
167 std::unique_ptr<T> new_el;
168 if (data.size() < max_n_elements)
169 // have not reached the maximum number of elements yet
170 {
171 if (cache.empty())
172 // nothing is cached, just copy a given element
173 {
174 new_el = std::make_unique<T>(element);
175 }
176 else
177 // something is cached, take one element and copy
178 // the user provided one there.
179 {
180 new_el = std::move(cache.back());
181 (*new_el) = element;
182
183 cache.pop_back(); // removes a pointer that is now a nullptr anyway
184 }
185 }
186 else
187 // we reached the maximum number of elements and
188 // thus have to re-order/cycle elements currently stored
189 {
190 new_el = std::move(data.back());
191 (*new_el) = element;
192
193 data.pop_back(); // removes a pointer that is now a nullptr anyway
194 }
195
196 // finally insert the new one where appropriate
197 data.push_front(std::move(new_el));
198
199 // whatever we do, we shall not store more than the maximum number of
200 // elements
201 Assert(data.size() + cache.size() <= max_n_elements, ExcInternalError());
202 }
203
204
205
206 template <typename T>
207 T &
208 FiniteSizeHistory<T>::operator[](const std::size_t ind)
209 {
210 AssertIndexRange(ind, data.size());
211 return *data[ind];
212 }
213
214
215
216 template <typename T>
217 const T &
218 FiniteSizeHistory<T>::operator[](const std::size_t ind) const
219 {
220 AssertIndexRange(ind, data.size());
221 return *data[ind];
222 }
223
224
225
226 template <typename T>
227 std::size_t
228 FiniteSizeHistory<T>::size() const
229 {
230 return data.size();
231 }
232
233
234
235 template <typename T>
236 std::size_t
237 FiniteSizeHistory<T>::max_size() const
238 {
239 return max_n_elements;
240 }
241
242
243
244 template <typename T>
245 void
246 FiniteSizeHistory<T>::clear()
247 {
248 data.clear();
249 cache.clear();
250 }
251
252 #endif // Doxygen
253
254 DEAL_II_NAMESPACE_CLOSE
255
256 #endif // dealii_storage_h