GCC Code Coverage Report

Directory: gridformat/
File: gridformat/common/ranges.hpp
Date: 2024-11-10 16:24:00
Exec Total Coverage
Lines: 103 107 96.3%
Functions: 430 444 96.8%
Branches: 29 69 42.0%
Line Branch Exec Source
1 // SPDX-FileCopyrightText: 2022-2023 Dennis Gläser <dennis.glaeser@iws.uni-stuttgart.de>
2 // SPDX-License-Identifier: MIT
3 /*!
4 * \file
5 * \ingroup Common
6 * \brief Helper functions for ranges
7 */
8 #ifndef GRIDFORMAT_COMMON_RANGES_HPP_
9 #define GRIDFORMAT_COMMON_RANGES_HPP_
10
11 #include <ranges>
12 #include <cassert>
13 #include <utility>
14 #include <iterator>
15 #include <concepts>
16 #include <algorithm>
17 #include <functional>
18 #include <type_traits>
19 #include <optional>
20 #include <sstream>
21
22 #include <gridformat/common/concepts.hpp>
23 #include <gridformat/common/exceptions.hpp>
24 #include <gridformat/common/type_traits.hpp>
25 #include <gridformat/common/iterator_facades.hpp>
26
27 namespace GridFormat::Ranges {
28
29 /*!
30 * \ingroup Common
31 * \brief Return the size of a range
32 */
33 template<std::ranges::sized_range R>
34 requires(!Concepts::StaticallySizedRange<R>)
35 6228785 inline constexpr auto size(R&& r) {
36 6228785 return std::ranges::size(r);
37 }
38
39 /*!
40 * \ingroup Common
41 * \brief Return the size of a range
42 * \note This has complexitx O(N), but we also want to support user-given non-sized ranges.
43 */
44 template<std::ranges::range R>
45 requires(!std::ranges::sized_range<R> and
46 !Concepts::StaticallySizedRange<R>)
47 12220 inline constexpr auto size(R&& r) {
48 12220 return std::ranges::distance(r);
49 }
50
51 /*!
52 * \ingroup Common
53 * \brief Return the size of a range with size known at compile time.
54 */
55 template<Concepts::StaticallySizedRange R>
56 110562 inline constexpr auto size(R&&) {
57 110562 return static_size<R>;
58 }
59
60 /*!
61 * \ingroup Common
62 * \brief Return the value at the i-th position of the range.
63 */
64 template<std::integral I, std::ranges::range R>
65 451100 inline constexpr decltype(auto) at(I i, const R& r) {
66 451100 auto it = std::ranges::begin(r);
67 std::advance(it, i);
68 451100 return *it;
69 }
70
71 /*!
72 * \ingroup Common
73 * \brief Return an array of the desired size, filled with the given value.
74 */
75 template<std::size_t dim, typename T>
76 19879 inline constexpr auto filled_array(const T& t = default_value<T>) {
77 std::array<T, dim> result;
78
1/2
✓ Branch 1 taken 2289 times.
✗ Branch 2 not taken.
 19879 std::ranges::fill(result, t);
79 19879 return result;
80 }
81
82 /*!
83 * \ingroup Common
84 * \brief Return an array containing the result of an operation
85 * applied to pairs of elements of the two given ranges.
86 */
87 template<typename TargetType = Automatic,
88 typename Op,
89 Concepts::StaticallySizedRange R1,
90 Concepts::StaticallySizedRange R2>
91 requires(static_size<R1> == static_size<R2> and
92 std::invocable<Op, std::ranges::range_reference_t<R1>, std::ranges::range_reference_t<R2>>)
93 72 inline constexpr auto apply_pairwise(const Op& op, R1&& r1, R2&& r2) {
94 using RR1 = std::ranges::range_reference_t<R1>;
95 using RR2 = std::ranges::range_reference_t<R2>;
96 using T = std::conditional_t<
97 std::is_same_v<TargetType, Automatic>,
98 std::invoke_result_t<Op, RR1, RR2>,
99 TargetType
100 >;
101
1/2
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 72 auto result = filled_array<static_size<R1>, T>();
102 72 std::transform(
103 std::ranges::begin(r1),
104 std::ranges::end(r1),
105 std::ranges::begin(r2),
106 result.begin(),
107 op
108 );
109 72 return result;
110 }
111
112 #ifndef DOXYGEN
113 namespace Detail {
114
115 template<auto N, typename R>
116 struct ResultArraySize : std::integral_constant<std::size_t, N> {};
117
118 template<Concepts::StaticallySizedRange R>
119 struct ResultArraySize<automatic, R> : std::integral_constant<std::size_t, static_size<R>> {};
120
121 } // namespace Detail
122 #endif // DOXYGEN
123
124 /*!
125 * \ingroup Common
126 * \brief Convert the given range into an array with the given dimension.
127 */
128 template<auto n = automatic, typename T = Automatic, std::ranges::range R>
129 669210 inline constexpr auto to_array(const R& r) {
130 using N = std::remove_cvref_t<decltype(n)>;
131 static_assert(std::integral<N> || std::same_as<N, Automatic>);
132 static_assert(Concepts::StaticallySizedRange<R> || !std::same_as<N, Automatic>);
133 669210 constexpr std::size_t result_size = Detail::ResultArraySize<n, R>::value;
134
1/2
✓ Branch 1 taken 178054 times.
✗ Branch 2 not taken.
 669210 const std::size_t range_size = size(r);
135
136 using ValueType = std::conditional_t<std::is_same_v<T, Automatic>, std::ranges::range_value_t<R>, T>;
137 std::array<ValueType, result_size> result;
138
3/5
✓ Branch 2 taken 149414 times.
✓ Branch 3 taken 185413 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 149414 times.
✗ Branch 6 not taken.
 669210 std::ranges::copy_n(std::ranges::begin(r), std::min(range_size, result_size), result.begin());
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 333830 times.
 667000 if (range_size < result_size)
140 300 std::ranges::fill_n(result.begin() + range_size, result_size - range_size, ValueType{0});
141 799730 return result;
142 }
143
144 /*!
145 * \ingroup Common
146 * \brief Create an array of given type and size from a string.
147 */
148 template<typename T, std::size_t N>
149 4792 std::array<T, N> array_from_string(const std::string& values) {
150 4792 auto result = Ranges::filled_array<N>(T{0});
151
1/2
✓ Branch 1 taken 2404 times.
✗ Branch 2 not taken.
 4792 std::stringstream stream;
152
1/2
✓ Branch 1 taken 2404 times.
✗ Branch 2 not taken.
 4792 stream << values;
153 4792 auto stream_view = std::ranges::istream_view<T>(stream);
154
1/2
✓ Branch 1 taken 2404 times.
✗ Branch 2 not taken.
 4792 const auto [_, out] = std::ranges::copy(stream_view, result.begin());
155
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2404 times.
 4792 if (std::ranges::distance(result.begin(), out) != N)
156 ✗ throw IOError("Could not read " + std::to_string(N) + " values from '" + values + "'");
157 9584 return result;
158 4792 }
159
160 /*!
161 * \ingroup Common
162 * \brief Return a copy of the range with each entry incremented by the given value.
163 */
164 template<std::ranges::range R, typename Increment>
165 5830 inline constexpr auto incremented(R&& r, const Increment& inc) {
166 5830 auto result = std::forward<R>(r);
167
1/2
✓ Branch 1 taken 848 times.
✗ Branch 2 not taken.
 13298 std::ranges::for_each(result, [&] (auto& value) { value += inc; });
168 5830 return result;
169 ✗ }
170
171 /*!
172 * \ingroup Common
173 * \brief Return a range that contains the elements of the two given ranges.
174 */
175 template<Concepts::StaticallySizedRange R1, Concepts::StaticallySizedRange R2>
176 requires(std::is_same_v<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>>)
177 530 inline constexpr auto merged(R1&& r1, R2&& r2) {
178 530 constexpr std::size_t merged_size = static_size<R1> + static_size<R2>;
179
1/2
✓ Branch 2 taken 36 times.
✗ Branch 3 not taken.
 530 auto result = filled_array<merged_size>(*std::ranges::begin(r1));
180
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 530 std::ranges::copy(r1, result.begin());
181
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 530 std::ranges::copy(r2, result.begin() + static_size<R1>);
182 530 return result;
183 }
184
185 /*!
186 * \ingroup Common
187 * \brief Flatten the given 2d range into a 1d range.
188 */
189 template<Concepts::MDRange<2> R>
190 requires(Concepts::StaticallySizedMDRange<std::ranges::range_value_t<R>, 1>)
191 12588 inline constexpr auto flat(const R& r) {
192 if constexpr (Concepts::StaticallySizedRange<R>) {
193 constexpr std::size_t element_size = static_size<std::ranges::range_value_t<R>>;
194 constexpr std::size_t flat_size = element_size*static_size<R>;
195 std::array<MDRangeValueType<R>, flat_size> result;
196 auto it = result.begin();
197 std::ranges::for_each(r, [&] (const auto& sub_range) {
198 std::ranges::for_each(sub_range, [&] (const auto& entry) {
199 *it = entry;
200 ++it;
201 });
202 });
203 return result;
204 } else {
205
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 12588 std::vector<MDRangeValueType<R>> result;
206
1/2
✓ Branch 1 taken 6380 times.
✗ Branch 2 not taken.
 12588 result.reserve(size(r)*static_size<std::ranges::range_value_t<R>>);
207
1/2
✓ Branch 1 taken 6380 times.
✗ Branch 2 not taken.
 53996 std::ranges::for_each(r, [&] (const auto& sub_range) {
208 136944 std::ranges::for_each(sub_range, [&] (const auto& entry) {
209 58660 result.push_back(entry);
210 });
211 });
212
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6380 times.
 25176 return result;
213 ✗ }
214 }
215
216 /*!
217 * \ingroup Common
218 * \brief Sort the given range and remove all duplicates.
219 */
220 template<std::ranges::range R,
221 typename Comp = std::ranges::less,
222 typename EqPredicate = std::equal_to<std::ranges::range_value_t<R>>>
223 11914 inline constexpr decltype(auto) sort_and_unique(R&& r,
224 Comp comparator = {},
225 EqPredicate eq = {}) {
226 11914 std::ranges::sort(r, comparator);
227 11914 return std::ranges::unique(std::forward<R>(r), eq);
228 }
229
230
231 #ifndef DOXYGEN
232 namespace FlatViewDetail {
233
234 template<typename Range>
235 using ValueType = GridFormat::MDRangeValueType<Range>;
236
237 template<typename Range>
238 using ReferenceType = GridFormat::MDRangeReferenceType<Range>;
239
240 template<std::ranges::forward_range R>
241 class Iterator;
242
243 template<std::ranges::forward_range R> requires(mdrange_dimension<R> == 1)
244 class Iterator<R> : public ForwardIteratorFacade<Iterator<R>, ValueType<R>, ReferenceType<R>> {
245 public:
246 Iterator() = default;
247 16 Iterator(std::ranges::iterator_t<R> begin, std::ranges::sentinel_t<R> sentinel)
248 16 : _it{begin}
249 12 , _sentinel{sentinel}
250 16 {}
251
252 74 friend bool operator==(const Iterator& self,
253 const std::default_sentinel_t&) noexcept {
254 74 return self._it == self._sentinel;
255 }
256
257 friend bool operator==(const std::default_sentinel_t& s,
258 const Iterator& self) noexcept {
259 return self == s;
260 }
261
262 private:
263 friend class GridFormat::IteratorAccess;
264
265 68 ReferenceType<R> _dereference() const {
266
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 34 times.
 68 assert(_it != _sentinel);
267 68 return *_it;
268 }
269
270 bool _is_equal(const Iterator& other) const {
271 return _it == other._it;
272 }
273
274 68 void _increment() {
275
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 34 times.
 68 assert(_it != _sentinel);
276 68 ++_it;
277 68 }
278
279 std::ranges::iterator_t<R> _it;
280 std::ranges::sentinel_t<R> _sentinel;
281 };
282
283 template<std::ranges::forward_range R> requires(mdrange_dimension<R> > 1)
284 class Iterator<R> : public ForwardIteratorFacade<Iterator<R>, ValueType<R>, ReferenceType<R>> {
285 using RangeValueType = std::remove_reference_t<std::ranges::range_reference_t<R>>;
286 using SubIterator = Iterator<RangeValueType>;
287
288 public:
289 Iterator() = default;
290 4 Iterator(std::ranges::iterator_t<R> begin, std::ranges::sentinel_t<R> sentinel)
291 4 : _it{begin}
292 4 , _sentinel{sentinel} {
293
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 if (_it != _sentinel)
294 4 _make_sub_iterators();
295 4 }
296
297 54 friend bool operator==(const Iterator& self,
298 const std::default_sentinel_t&) noexcept {
299 54 return self._it == self._sentinel;
300 }
301
302 friend bool operator==(const std::default_sentinel_t& s,
303 const Iterator& self) noexcept {
304 return self == s;
305 }
306
307 private:
308 friend class GridFormat::IteratorAccess;
309
310 96 bool _is_sub_end() const {
311 96 return !static_cast<bool>(_sub_it);
312 }
313
314 48 ReferenceType<R> _dereference() const {
315
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
 48 assert(!_is_sub_end());
316 48 return *(*_sub_it);
317 }
318
319 bool _is_equal(const Iterator& other) const {
320 return _it == other._it;
321 }
322
323 48 void _increment() {
324
3/6
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 24 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 24 times.
 48 if (_is_sub_end() || _it == _sentinel)
325 ✗ throw InvalidState("Cannot increment past-the-end iterator");
326
327
2/2
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 18 times.
 48 if (++(*_sub_it); *_sub_it == std::default_sentinel_t{}) {
328
2/2
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 2 times.
 12 if (++_it; _it != _sentinel)
329 8 _make_sub_iterators();
330 else
331 4 _release_sub_iterators();
332 }
333 48 }
334
335 12 void _make_sub_iterators() {
336 12 _sub_it = SubIterator{std::ranges::begin(*_it), std::ranges::end(*_it)};
337 12 }
338
339 4 void _release_sub_iterators() {
340 4 _sub_it.reset();
341 4 }
342
343 std::ranges::iterator_t<R> _it;
344 std::ranges::sentinel_t<R> _sentinel;
345 std::optional<SubIterator> _sub_it;
346 };
347
348 } // namespace FlatViewDetail
349 #endif // DOXYGEN
350
351
352 /*!
353 * \ingroup Common
354 * \brief Adapter to expose a multi-dimensional range as a flat range.
355 */
356 template<std::ranges::forward_range Range>
357 class FlatView : public std::ranges::view_interface<FlatView<Range>> {
358 static constexpr std::size_t dim = mdrange_dimension<Range>;
359 static constexpr bool is_const = std::is_const_v<std::remove_reference_t<Range>>;
360
361 public:
362 8 explicit FlatView(Range& r)
363 8 : _range(r)
364 8 {}
365
366 4 FlatViewDetail::Iterator<Range> begin() requires(!is_const) {
367 4 return {std::ranges::begin(_range.get()), std::ranges::end(_range.get())};
368 }
369
370 4 FlatViewDetail::Iterator<std::add_const_t<Range>> begin() const {
371 4 return {std::ranges::begin(_range.get()), std::ranges::end(_range.get())};
372 }
373
374 8 std::default_sentinel_t end() { return {}; }
375 std::default_sentinel_t end() const { return {}; }
376
377 private:
378 std::reference_wrapper<Range> _range;
379 };
380
381 } // namespace GridFormat::Ranges
382
383 namespace GridFormat::Views {
384
385 #ifndef DOXYGEN
386 namespace Detail {
387
388 struct FlatViewAdapter {
389 template<std::ranges::forward_range R> requires(std::is_lvalue_reference_v<R>)
390 8 constexpr auto operator()(R&& in) const {
391 8 return Ranges::FlatView{std::forward<R>(in)};
392 }
393 };
394
395 template<std::ranges::forward_range R> requires(std::ranges::viewable_range<R>)
396 4 inline constexpr std::ranges::view auto operator|(R&& range, const FlatViewAdapter& adapter) {
397 4 return adapter(std::forward<R>(range));
398 }
399
400 } // namespace Detail
401 #endif // DOXYGEN
402
403 inline constexpr Detail::FlatViewAdapter flat;
404
405 } // namespace GridFormat::Views
406
407
408 // Disable the size semantics for our flat view because checking
409 // the sized_range concept for it results in a problem with recursion
410 namespace std::ranges {
411
412 template<typename R>
413 inline constexpr bool disable_sized_range<GridFormat::Ranges::FlatView<R>> = true;
414
415 } // namespace std::ranges
416
417 #endif // GRIDFORMAT_COMMON_RANGES_HPP_
418