preCICE v3.1.2
Searching...
No Matches
algorithm.hpp
Go to the documentation of this file.
1#pragma once
2
3#include <algorithm>
4#include <array>
5#include <fmt/ostream.h>
6#include <functional>
7#include <iterator>
8#include <set>
9#include <type_traits>
10#include <utility>
11
12namespace precice {
13namespace utils {
14
33template <class InputIt1, class InputIt2, class OutputIt>
34void set_intersection_indices(InputIt1 ref1, InputIt1 first1, InputIt1 last1,
35 InputIt2 first2, InputIt2 last2, OutputIt d_first)
36{
37 while (first1 != last1 && first2 != last2) {
38 if (*first1 < *first2) {
39 ++first1;
40 } else {
41 if (!(*first2 < *first1)) {
42 *d_first++ = std::distance(ref1, first1++); // *first1 and *first2 are equivalent.
43 }
44 ++first2;
45 }
46 }
47}
48
50template <typename... Elements>
51auto make_array(Elements &&... elements) -> std::array<typename std::common_type<Elements...>::type, sizeof...(Elements)>
52{
53 return {std::forward<Elements>(elements)...};
54}
55
63template <typename Container, typename BinaryPredicate = std::equal_to<typename Container::value_type>>
64bool unique_elements(const Container &c, BinaryPredicate p = {})
65{
66 // This algorithm runs on small containers, so the O(n^2) does not hurt.
67 auto cbegin = c.begin();
68 auto cend = c.end();
69 // An empty set has unique elements
70 if (cbegin == cend) {
71 return true;
72 }
73 auto cstart = cbegin + 1;
74 for (; cstart < cend; ++cbegin, ++cstart) {
75 if (std::find_if(cstart, cend,
76 [&p, cbegin](const typename Container::value_type &v) -> bool {
77 return p(*cbegin, v);
78 }) != cend) {
79 return false;
80 }
81 }
82 return true;
83}
84
92template <class InputIter, class ElementType>
93void intersperse(InputIter first, InputIter last, const ElementType &elem, std::ostream &out)
94{
95 if (first == last)
96 return;
97
98 out << *first++;
99 for (; first != last; ++first) {
100 out << elem << *first;
101 }
102}
103
107template <class InputIt1, class InputIt2>
109mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
110{
111 while (first1 != last1 && first2 != last2 && *first1 == *first2) {
112 ++first1, ++first2;
113 }
114 return std::make_pair(first1, first2);
115}
116
118template <typename InputIter>
122 InputIter begin;
123 InputIter end;
124
125 RangePreview(Size n, InputIter begin, InputIter end)
126 : n(n), begin(begin), end(end) {}
127
128 void print(std::ostream &out) const
129 {
130 if (begin == end) {
131 out << "<Empty Range>";
132 return;
133 }
134
135 out << '[';
136
137 if (n == 0) {
138 out << " ... ";
139 } else {
140 auto dist = std::distance(begin, end);
141 const std::string sep{", "};
142 if (dist <= n * 2) {
143 intersperse(begin, end, sep, out);
144 } else {
145 auto last1 = begin;
147 intersperse(begin, last1, sep, out);
148 out << sep << "... " << sep;
149 auto first2 = begin;
151 intersperse(first2, end, sep, out);
152 }
153 }
154
155 auto mm = std::minmax_element(begin, end);
156 out << "] min:" << *mm.first << " max:" << *mm.second;
157 }
158};
159
161template <typename Iter>
163{
164 rp.print(out);
165 return out;
166}
167
172template <typename Range, typename Iter = typename Range::const_iterator, typename Size = typename std::iterator_traits<Iter>::difference_type>
173const RangePreview<Iter> previewRange(Size n, const Range &range)
174{
175 return {n, std::begin(range), std::end(range)};
176}
177
179template <typename T, typename Index, size_t n>
181{
182 static_assert(n > 0, "Reodering nothing is pointless");
183 std::array<T, n> reordered;
184 for (std::size_t i = 0; i < n; ++i) {
185 reordered[i] = elements[order[i]];
186 }
187 return reordered;
188}
189
190template <class InputIt, class Size, class InOutIt>
191void add_n(InputIt first, Size count, InOutIt result)
192{
193 std::transform(first, std::next(first, count), result, result, std::plus{});
194}
195
197template <class InputIt, class Unary>
198void for_each_unique(InputIt first, InputIt last, Unary func)
199{
200 using Inner = std::remove_cv_t<std::remove_reference_t<decltype(*first)>>;
201 std::set<Inner> seen;
202 std::for_each(first, last, [&seen, &func](const auto &elem) {
203 if (seen.count(elem) == 0) {
204 seen.insert(elem);
205 func(elem);
206 }
207 });
208}
209
211template <class InputIt, class Predicate>
212std::pair<InputIt, InputIt> find_first_range(InputIt first, InputIt last, Predicate p)
213{
214 auto firstMatch = std::find_if(first, last, p);
215 if (firstMatch == last) { // nothing found
216 return {last, last};
217 }
218 auto trailing = firstMatch;
219 auto next = std::next(firstMatch);
220 while (next != last && p(*next)) {
221 ++trailing;
222 ++next;
223 }
224 return {firstMatch, trailing};
225}
226
227} // namespace utils
228} // namespace precice
229
230template <typename Iter>
231struct fmt::formatter<precice::utils::RangePreview<Iter>> : ostream_formatter {
232};
std::ostream & out
T begin(T... args)
T count(T... args)
T distance(T... args)
T end(T... args)
T find_if(T... args)
T for_each(T... args)
T make_pair(T... args)
T minmax_element(T... args)
auto reorder_array(const std::array< Index, n > &order, const std::array< T, n > &elements) -> std::array< T, n >
Reorders an array given an array of unique indices.
void add_n(InputIt first, Size count, InOutIt result)
void for_each_unique(InputIt first, InputIt last, Unary func)
Calls each value in the range of [first, last[ exactly once.
auto make_array(Elements &&... elements) -> std::array< typename std::common_type< Elements... >::type, sizeof...(Elements)>
Function that generates an array from given elements.
Definition algorithm.hpp:51
std::pair< InputIt, InputIt > find_first_range(InputIt first, InputIt last, Predicate p)
Finds the first range in [first, last[ that fulfills a predicate.
void intersperse(InputIter first, InputIter last, const ElementType &elem, std::ostream &out)
Definition algorithm.hpp:93
const RangePreview< Iter > previewRange(Size n, const Range &range)
bool unique_elements(const Container &c, BinaryPredicate p={})
Definition algorithm.hpp:64
std::ostream & operator<<(std::ostream &out, const RangePreview< Iter > &rp)
Allows streaming of RangePreview objects.
void set_intersection_indices(InputIt1 ref1, InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first)
This function is by and large the same as std::set_intersection(). The only difference is that we don...
Definition algorithm.hpp:34
std::pair< InputIt1, InputIt2 > mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
Main namespace of the precice library.
T next(T... args)
The RangePreview object used as a lazy proxy struct for proviewing the content of a Range.
typename std::iterator_traits< InputIter >::difference_type Size
RangePreview(Size n, InputIter begin, InputIter end)
void print(std::ostream &out) const
T transform(T... args)