Libkleo

stl_util.h
1/****************************************************************************
2** SPDX-FileCopyrightText: 2001-2007 Klarälvdalens Datakonsult AB. All rights reserved.
3**
4** This file is part of the KD Tools library.
5**
6** SPDX-License-Identifier: GPL-2.0-or-later
7**
8**********************************************************************/
9
10#pragma once
11
12#include <algorithm>
13#include <functional>
14#include <iterator>
15#include <numeric>
16#include <utility>
17
18namespace kdtools
19{
20template<typename _Iterator, typename UnaryPredicate>
21struct filter_iterator {
22 using value_type = typename std::iterator_traits<_Iterator>::value_type;
23 using reference = typename std::iterator_traits<_Iterator>::reference;
24 using pointer = typename std::iterator_traits<_Iterator>::pointer;
25 using difference_type = typename std::iterator_traits<_Iterator>::difference_type;
26
27 filter_iterator(UnaryPredicate pred, _Iterator it, _Iterator last)
28 : it(it)
29 , last(last)
30 , pred(pred)
31 {
32 }
33 template<typename _OtherIter>
34 filter_iterator(const filter_iterator<_OtherIter, UnaryPredicate> &other)
35 : it(other.it)
36 , last(other.last)
37 , pred(other.pred)
38 {
39 }
40 filter_iterator &operator++()
41 {
42 while (++it != last && !pred(*it)) { }
43 return *this;
44 }
45 filter_iterator operator++(int)
46 {
47 auto retval = *this;
48 while (++it != last && !pred(*it)) { }
49 return retval;
50 }
51 bool operator==(filter_iterator other) const
52 {
53 return it == other.it;
54 }
55 bool operator!=(filter_iterator other) const
56 {
57 return it != other.it;
58 }
59 typename _Iterator::reference operator*() const
60 {
61 return *it;
62 }
63
64private:
65 _Iterator it, last;
66 UnaryPredicate pred;
67};
68
69template<typename _Iterator, typename UnaryPredicate>
70filter_iterator<typename std::decay<_Iterator>::type, UnaryPredicate> make_filter_iterator(UnaryPredicate &&pred, _Iterator &&it, _Iterator &&last)
71{
72 return filter_iterator<typename std::decay<_Iterator>::type, UnaryPredicate>(std::forward<UnaryPredicate>(pred),
73 std::forward<_Iterator>(it),
74 std::forward<_Iterator>(last));
75}
76
77template<typename InputIterator, typename OutputIterator, typename UnaryPredicate>
78OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred)
79{
80 while (first != last) {
81 if (pred(*first)) {
82 *dest = *first;
83 ++dest;
84 }
85 ++first;
86 }
87 return dest;
88}
89
90template<typename OutputIterator, typename InputIterator, typename UnaryFunction, typename UnaryPredicate>
91void transform_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred, UnaryFunction filter)
92{
93 for (; first != last; ++first) {
94 if (filter(*first)) {
95 *dest++ = pred(*first);
96 }
97 }
98}
99
100template<typename InputIterator, typename OutputIterator, typename Predicate>
101OutputIterator copy_1st_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred)
102{
103 const auto trans = [](typename std::iterator_traits<InputIterator>::reference v) {
104 return std::get<0>(v);
105 };
106 kdtools::transform_if(first, //
107 last,
108 dest,
109 trans,
110 [&pred, &trans](typename std::iterator_traits<InputIterator>::reference v) {
111 return pred(trans(v));
112 });
113 return dest;
114}
115
116template<typename InputIterator, typename OutputIterator, typename Predicate>
117OutputIterator copy_2nd_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred)
118{
119 const auto trans = [](typename std::iterator_traits<InputIterator>::reference v) {
120 return std::get<1>(v);
121 };
122 kdtools::transform_if(first, //
123 last,
124 dest,
125 trans,
126 [&pred, &trans](typename std::iterator_traits<InputIterator>::reference v) {
127 return pred(trans(v));
128 });
129 return dest;
130}
131
132template<typename OutputIterator, typename InputIterator, typename UnaryFunction>
133OutputIterator transform_1st(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func)
134{
135 return std::transform(first, //
136 last,
137 dest,
138 [func](typename std::iterator_traits<InputIterator>::reference v) {
139 return func(std::get<0>(v));
140 });
141}
142
143template<typename OutputIterator, typename InputIterator, typename UnaryFunction>
144OutputIterator transform_2nd(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func)
145{
146 return std::transform(first, //
147 last,
148 dest,
149 [func](typename std::iterator_traits<InputIterator>::reference v) {
150 return func(std::get<1>(v));
151 });
152}
153
154template<typename Value, typename InputIterator, typename UnaryPredicate>
155Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value = Value())
156{
157 return std::accumulate(make_filter_iterator(filter, first, last), //
158 make_filter_iterator(filter, last, last),
159 value);
160}
161
162template<typename Value, typename InputIterator, typename UnaryPredicate, typename BinaryOperation>
163Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value, BinaryOperation op)
164{
165 return std::accumulate(make_filter_iterator(filter, first, last), //
166 make_filter_iterator(filter, last, last),
167 value,
168 op);
169}
170
171template<typename Value, typename InputIterator, typename UnaryFunction>
172Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value = Value())
173{
174 return std::accumulate(first, //
175 last,
176 value,
177 [map](Value lhs, typename std::iterator_traits<InputIterator>::reference rhs) {
178 return lhs + map(rhs);
179 });
180}
181
182template<typename Value, typename InputIterator, typename UnaryFunction, typename BinaryOperation>
183Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value, BinaryOperation op)
184{
185 return std::accumulate(first, //
186 last,
187 value,
188 [map, op](typename InputIterator::reference lhs, typename InputIterator::reference rhs) {
189 return op(map(lhs), map(rhs));
190 });
191}
192
193template<typename Value, typename InputIterator, typename UnaryFunction, typename UnaryPredicate, typename BinaryOperation>
194Value accumulate_transform_if(InputIterator first, InputIterator last, UnaryFunction map, UnaryPredicate filter, const Value &value, BinaryOperation op)
195{
196 return accumulate_transform(make_filter_iterator(filter, first, last), //
197 make_filter_iterator(filter, last, last),
198 map,
199 value,
200 op);
201}
202
203template<typename InputIterator, typename BinaryOperation>
204BinaryOperation for_each_adjacent_pair(InputIterator first, InputIterator last, BinaryOperation op)
205{
206 using ValueType = typename std::iterator_traits<InputIterator>::value_type;
207 if (first == last) {
208 return op;
209 }
210 ValueType value = *first;
211 while (++first != last) {
212 ValueType tmp = *first;
213 op(value, tmp);
214 value = tmp;
215 }
216 return op;
217}
218
219template<typename InputIterator, typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate>
220std::pair<OutputIterator1, OutputIterator2>
221separate_if(InputIterator first, InputIterator last, OutputIterator1 dest1, OutputIterator2 dest2, UnaryPredicate pred)
222{
223 while (first != last) {
224 if (pred(*first)) {
225 *dest1 = *first;
226 ++dest1;
227 } else {
228 *dest2 = *first;
229 ++dest2;
230 }
231 ++first;
232 }
233 return std::make_pair(dest1, dest2);
234}
235
236//@{
237/**
238 Versions of std::set_intersection optimized for ForwardIterator's
239*/
240template<typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
241OutputIterator set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result)
242{
243 while (first1 != last1 && first2 != last2) {
244 if (*first1 < *first2) {
245 first1 = std::lower_bound(++first1, last1, *first2);
246 } else if (*first2 < *first1) {
247 first2 = std::lower_bound(++first2, last2, *first1);
248 } else {
249 *result = *first1;
250 ++first1;
251 ++first2;
252 ++result;
253 }
254 }
255 return result;
256}
257
258template<typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
259OutputIterator
260set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result, BinaryPredicate pred)
261{
262 while (first1 != last1 && first2 != last2) {
263 if (pred(*first1, *first2)) {
264 first1 = std::lower_bound(++first1, last1, *first2, pred);
265 } else if (pred(*first2, *first1)) {
266 first2 = std::lower_bound(++first2, last2, *first1, pred);
267 } else {
268 *result = *first1;
269 ++first1;
270 ++first2;
271 ++result;
272 }
273 }
274 return result;
275}
276//@}
277
278template<typename ForwardIterator, typename ForwardIterator2, typename BinaryPredicate>
279bool set_intersects(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)
280{
281 while (first1 != last1 && first2 != last2) {
282 if (pred(*first1, *first2)) {
283 first1 = std::lower_bound(++first1, last1, *first2, pred);
284 } else if (pred(*first2, *first1)) {
285 first2 = std::lower_bound(++first2, last2, *first1, pred);
286 } else {
287 return true;
288 }
289 }
290 return false;
291}
292
293}
QtConcurrent::filter
QFuture< void > filter(QThreadPool *pool, Sequence &sequence, KeepFunctor &&filterFunction)
QtConcurrent::map
QFuture< void > map(Iterator begin, Iterator end, MapFunctor &&function)
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Mon Nov 18 2024 12:09:14 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.