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 
18 namespace kdtools
19 {
20 template<typename _Iterator, typename UnaryPredicate>
21 struct 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 
64 private:
65  _Iterator it, last;
66  UnaryPredicate pred;
67 };
68 
69 template<typename _Iterator, typename UnaryPredicate>
70 filter_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 
77 template<typename InputIterator, typename OutputIterator, typename UnaryPredicate>
78 OutputIterator 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 
90 template<typename OutputIterator, typename InputIterator, typename UnaryFunction, typename UnaryPredicate>
91 void 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 
100 template<typename InputIterator, typename OutputIterator, typename Predicate>
101 OutputIterator 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 
116 template<typename InputIterator, typename OutputIterator, typename Predicate>
117 OutputIterator 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 
132 template<typename OutputIterator, typename InputIterator, typename UnaryFunction>
133 OutputIterator 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 
143 template<typename OutputIterator, typename InputIterator, typename UnaryFunction>
144 OutputIterator 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 
154 template<typename Value, typename InputIterator, typename UnaryPredicate>
155 Value 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 
162 template<typename Value, typename InputIterator, typename UnaryPredicate, typename BinaryOperation>
163 Value 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 
171 template<typename Value, typename InputIterator, typename UnaryFunction>
172 Value 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 
182 template<typename Value, typename InputIterator, typename UnaryFunction, typename BinaryOperation>
183 Value 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 
193 template<typename Value, typename InputIterator, typename UnaryFunction, typename UnaryPredicate, typename BinaryOperation>
194 Value 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 
203 template<typename InputIterator, typename BinaryOperation>
204 BinaryOperation 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 
219 template<typename InputIterator, typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate>
220 std::pair<OutputIterator1, OutputIterator2>
221 separate_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 */
240 template<typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
241 OutputIterator 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 
258 template<typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
259 OutputIterator
260 set_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 
278 template<typename ForwardIterator, typename ForwardIterator2, typename BinaryPredicate>
279 bool 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 }
bool operator==(const Qt3DRender::QGraphicsApiFilter &reference, const Qt3DRender::QGraphicsApiFilter &sample)
bool operator!=(const Qt3DRender::QGraphicsApiFilter &reference, const Qt3DRender::QGraphicsApiFilter &sample)
QFuture< void > filter(Sequence &sequence, KeepFunctor filterFunction)
QFuture< void > map(Sequence &sequence, MapFunctor function)
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Thu Feb 15 2024 03:56:14 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.