Cpp / Qt: Reduce boost usage (memory and tuple)
[gpgme.git] / lang / qt / src / stl_util.h
1 /****************************************************************************
2 ** Copyright (C) 2001-2007 Klarälvdalens Datakonsult AB
3     Copyright (c) 2016 Intevation GmbH.  All rights reserved.
4 **
5 ** This file is part of the KD Tools library.
6 **
7 ** This file may be distributed and/or modified under the terms of the
8 ** GNU General Public License version 2 as published by the Free Software
9 ** Foundation and appearing in the file LICENSE.GPL included in the
10 ** packaging of this file.
11 **
12 ** Licensees holding valid commercial KD Tools licenses may use this file in
13 ** accordance with the KD Tools Commercial License Agreement provided with
14 ** the Software.
15 **
16 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
17 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18 **
19 ** Contact info@klaralvdalens-datakonsult.se if any conditions of this
20 ** licensing are not clear to you.
21 **
22 **********************************************************************/
23 #ifndef __KDTOOLSCORE_STL_UTIL_H__
24 #define __KDTOOLSCORE_STL_UTIL_H__
25
26 #include <boost/range.hpp>
27 #include <boost/iterator/filter_iterator.hpp>
28 #include <boost/iterator/transform_iterator.hpp>
29 #include <boost/call_traits.hpp>
30 #include <boost/version.hpp>
31
32 #include <algorithm>
33 #include <numeric>
34 #include <utility>
35 #include <iterator>
36 #include <functional>
37
38 namespace kdtools
39 {
40
41 struct nodelete {
42     template <typename T>
43     void operator()(const T *) const {}
44 };
45
46 struct identity {
47     template <typename T>
48     T *operator()(T *t) const
49     {
50         return t;
51     }
52     template <typename T>
53     const T *operator()(const T *t) const
54     {
55         return t;
56     }
57     template <typename T>
58     T &operator()(T &t) const
59     {
60         return t;
61     }
62     template <typename T>
63     const T &operator()(const T &t) const
64     {
65         return t;
66     }
67 };
68
69 template <typename Pair>
70 struct select1st;
71
72 template <typename U, typename V>
73 struct select1st< std::pair<U, V> >
74     : std::unary_function<std::pair<U, V>, U> {
75     typename boost::call_traits<U>::param_type
76     operator()(const std::pair<U, V> &pair) const
77     {
78         return pair.first;
79     }
80 };
81
82 template <typename Pair>
83 struct select2nd;
84
85 template <typename U, typename V>
86 struct select2nd< std::pair<U, V> >
87     : std::unary_function<std::pair<U, V>, V> {
88     typename boost::call_traits<V>::param_type
89     operator()(const std::pair<U, V> &pair) const
90     {
91         return pair.second;
92     }
93 };
94
95 template <typename InputIterator, typename OutputIterator, typename UnaryPredicate>
96 OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred)
97 {
98     while (first != last) {
99         if (pred(*first)) {
100             *dest = *first;
101             ++dest;
102         }
103         ++first;
104     }
105     return dest;
106 }
107
108 template <typename OutputIterator, typename InputIterator, typename UnaryFunction, typename UnaryPredicate>
109 OutputIterator transform_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred, UnaryFunction filter)
110 {
111     return std::transform(boost::make_filter_iterator(filter, first, last),
112                           boost::make_filter_iterator(filter, last,  last),
113                           dest, pred);
114 }
115
116 template <typename InputIterator, typename OutputIterator>
117 OutputIterator copy_1st(InputIterator first, InputIterator last, OutputIterator dest)
118 {
119     return std::copy(boost::make_transform_iterator(first, select1st<typename std::iterator_traits<InputIterator>::value_type>()),
120                      boost::make_transform_iterator(last,  select1st<typename std::iterator_traits<InputIterator>::value_type>()),
121                      dest);
122 }
123
124 template <typename InputIterator, typename OutputIterator>
125 OutputIterator copy_2nd(InputIterator first, InputIterator last, OutputIterator dest)
126 {
127     return std::copy(boost::make_transform_iterator(first, select2nd<typename std::iterator_traits<InputIterator>::value_type>()),
128                      boost::make_transform_iterator(last,  select2nd<typename std::iterator_traits<InputIterator>::value_type>()),
129                      dest);
130 }
131
132 template <typename InputIterator, typename OutputIterator, typename Predicate>
133 OutputIterator copy_1st_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred)
134 {
135     return kdtools::copy_if(boost::make_transform_iterator(first, select1st<typename std::iterator_traits<InputIterator>::value_type>()),
136                             boost::make_transform_iterator(last,  select1st<typename std::iterator_traits<InputIterator>::value_type>()),
137                             dest, pred);
138 }
139
140 template <typename InputIterator, typename OutputIterator, typename Predicate>
141 OutputIterator copy_2nd_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred)
142 {
143     return kdtools::copy_if(boost::make_transform_iterator(first, select2nd<typename std::iterator_traits<InputIterator>::value_type>()),
144                             boost::make_transform_iterator(last,  select2nd<typename std::iterator_traits<InputIterator>::value_type>()),
145                             dest, pred);
146 }
147
148 template <typename OutputIterator, typename InputIterator, typename UnaryFunction>
149 OutputIterator transform_1st(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func)
150 {
151     return std::transform(boost::make_transform_iterator(first, select1st<typename std::iterator_traits<InputIterator>::value_type>()),
152                           boost::make_transform_iterator(last,  select1st<typename std::iterator_traits<InputIterator>::value_type>()),
153                           dest, func);
154 }
155
156 template <typename OutputIterator, typename InputIterator, typename UnaryFunction>
157 OutputIterator transform_2nd(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func)
158 {
159     return std::transform(boost::make_transform_iterator(first, select2nd<typename std::iterator_traits<InputIterator>::value_type>()),
160                           boost::make_transform_iterator(last,  select2nd<typename std::iterator_traits<InputIterator>::value_type>()),
161                           dest, func);
162 }
163
164 template <typename Value, typename InputIterator, typename UnaryPredicate>
165 Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value = Value())
166 {
167     return std::accumulate(boost::make_filter_iterator(filter, first, last),
168                            boost::make_filter_iterator(filter, last,  last), value);
169 }
170
171 template <typename Value, typename InputIterator, typename UnaryPredicate, typename BinaryOperation>
172 Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value, BinaryOperation op)
173 {
174     return std::accumulate(boost::make_filter_iterator(filter, first, last),
175                            boost::make_filter_iterator(filter, last,  last), value, op);
176 }
177
178 template <typename Value, typename InputIterator, typename UnaryFunction>
179 Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value = Value())
180 {
181     return std::accumulate(boost::make_transform_iterator(first, map),
182                            boost::make_transform_iterator(last, map), value);
183 }
184
185 template <typename Value, typename InputIterator, typename UnaryFunction, typename BinaryOperation>
186 Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value, BinaryOperation op)
187 {
188     return std::accumulate(boost::make_transform_iterator(first, map),
189                            boost::make_transform_iterator(last, map), value, op);
190 }
191
192 template <typename Value, typename InputIterator, typename UnaryFunction, typename UnaryPredicate>
193 Value accumulate_transform_if(InputIterator first, InputIterator last, UnaryFunction map, UnaryPredicate pred, const Value &value = Value())
194 {
195     return std::accumulate(boost::make_transform_iterator(first, map),
196                            boost::make_transform_iterator(last, map), value);
197 }
198
199 template <typename Value, typename InputIterator, typename UnaryFunction, typename UnaryPredicate, typename BinaryOperation>
200 Value accumulate_transform_if(InputIterator first, InputIterator last, UnaryFunction map, UnaryPredicate filter, const Value &value, BinaryOperation op)
201 {
202     return std::accumulate(boost::make_transform_iterator(boost::make_filter_iterator(filter, first, last), map),
203                            boost::make_transform_iterator(boost::make_filter_iterator(filter, last, last), map), value, op);
204 }
205
206 template <typename InputIterator, typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate>
207 std::pair<OutputIterator1, OutputIterator2> separate_if(InputIterator first, InputIterator last, OutputIterator1 dest1, OutputIterator2 dest2, UnaryPredicate pred)
208 {
209     while (first != last) {
210         if (pred(*first)) {
211             *dest1 = *first;
212             ++dest1;
213         } else {
214             *dest2 = *first;
215             ++dest2;
216         }
217         ++first;
218     }
219     return std::make_pair(dest1, dest2);
220 }
221
222 template <typename InputIterator>
223 bool any(InputIterator first, InputIterator last)
224 {
225     while (first != last)
226         if (*first) {
227             return true;
228         } else {
229             ++first;
230         }
231     return false;
232 }
233
234 template <typename InputIterator, typename UnaryPredicate>
235 bool any(InputIterator first, InputIterator last, UnaryPredicate pred)
236 {
237     while (first != last)
238         if (pred(*first)) {
239             return true;
240         } else {
241             ++first;
242         }
243     return false;
244 }
245
246 template <typename InputIterator>
247 bool all(InputIterator first, InputIterator last)
248 {
249     while (first != last)
250         if (*first) {
251             ++first;
252         } else {
253             return false;
254         }
255     return true;
256 }
257
258 template <typename InputIterator, typename UnaryPredicate>
259 bool all(InputIterator first, InputIterator last, UnaryPredicate pred)
260 {
261     while (first != last)
262         if (pred(*first)) {
263             ++first;
264         } else {
265             return false;
266         }
267     return true;
268 }
269
270 template <typename InputIterator>
271 bool none_of(InputIterator first, InputIterator last)
272 {
273     return !any(first, last);
274 }
275
276 template <typename InputIterator, typename UnaryPredicate>
277 bool none_of(InputIterator first, InputIterator last, UnaryPredicate pred)
278 {
279     return !any(first, last, pred);
280 }
281
282 template <typename InputIterator, typename BinaryOperation>
283 BinaryOperation for_each_adjacent_pair(InputIterator first, InputIterator last, BinaryOperation op)
284 {
285     typedef typename std::iterator_traits<InputIterator>::value_type ValueType;
286     if (first == last) {
287         return op;
288     }
289     ValueType value = *first;
290     while (++first != last) {
291         ValueType tmp = *first;
292         op(value, tmp);
293         value = tmp;
294     }
295     return op;
296 }
297
298 template <typename ForwardIterator, typename UnaryPredicate, typename UnaryFunction>
299 UnaryFunction for_each_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred, UnaryFunction func)
300 {
301     return std::for_each(boost::make_filter_iterator(pred, first, last),
302                          boost::make_filter_iterator(pred, last, last),
303                          func);
304 }
305
306 //@{
307 /**
308    Versions of std::set_intersection optimized for ForwardIterator's
309 */
310 template <typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
311 OutputIterator set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result)
312 {
313     while (first1 != last1 && first2 != last2) {
314         if (*first1 < *first2) {
315             first1 = std::lower_bound(++first1, last1, *first2);
316         } else if (*first2 < *first1) {
317             first2 = std::lower_bound(++first2, last2, *first1);
318         } else {
319             *result = *first1;
320             ++first1;
321             ++first2;
322             ++result;
323         }
324     }
325     return result;
326 }
327
328 template <typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
329 OutputIterator set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result, BinaryPredicate pred)
330 {
331     while (first1 != last1 && first2 != last2) {
332         if (pred(*first1, *first2)) {
333             first1 = std::lower_bound(++first1, last1, *first2, pred);
334         } else if (pred(*first2, *first1)) {
335             first2 = std::lower_bound(++first2, last2, *first1, pred);
336         } else {
337             *result = *first1;
338             ++first1;
339             ++first2;
340             ++result;
341         }
342     }
343     return result;
344 }
345 //@}
346
347 template <typename ForwardIterator, typename ForwardIterator2, typename BinaryPredicate>
348 bool set_intersects(ForwardIterator first1,  ForwardIterator last1,
349                     ForwardIterator2 first2, ForwardIterator2 last2,
350                     BinaryPredicate pred)
351 {
352     while (first1 != last1 && first2 != last2) {
353         if (pred(*first1, *first2)) {
354             first1 = std::lower_bound(++first1, last1, *first2, pred);
355         } else if (pred(*first2, *first1)) {
356             first2 = std::lower_bound(++first2, last2, *first1, pred);
357         } else {
358             return true;
359         }
360     }
361     return false;
362 }
363
364 //@{
365 /*! Versions of std algorithms that take ranges */
366
367 template <typename C, typename V>
368 typename boost::range_iterator<C>::type
369 find(C &c, const V &v)
370 {
371     return std::find(boost::begin(c), boost::end(c), v);
372 }
373
374 #if BOOST_VERSION < 103500
375 template <typename C, typename V>
376 typename boost::range_const_iterator<C>::type
377 find(const C &c, const V &v)
378 {
379     return std::find(boost::begin(c), boost::end(c), v);
380 }
381 #endif
382
383 template <typename C, typename P>
384 typename boost::range_iterator<C>::type
385 find_if(C &c, P p)
386 {
387     return std::find_if(boost::begin(c), boost::end(c), p);
388 }
389
390 #if BOOST_VERSION < 103500
391 template <typename C, typename P>
392 typename boost::range_const_iterator<C>::type
393 find_if(const C &c, P p)
394 {
395     return std::find_if(boost::begin(c), boost::end(c), p);
396 }
397 #endif
398
399 template <typename C, typename V>
400 bool contains(const C &c, const V &v)
401 {
402     return find(c, v) != boost::end(c);
403 }
404
405 template <typename C, typename P>
406 bool contains_if(const C &c, P p)
407 {
408     return find_if(c, p) != boost::end(c);
409 }
410
411 template <typename C, typename V>
412 bool binary_search(const C &c, const V &v)
413 {
414     return std::binary_search(boost::begin(c), boost::end(c), v);
415 }
416
417 template <typename C, typename V>
418 size_t count(const C &c, const V &v)
419 {
420     return std::count(boost::begin(c), boost::end(c), v);
421 }
422
423 template <typename C, typename P>
424 size_t count_if(const C &c, P p)
425 {
426     return std::count_if(boost::begin(c), boost::end(c), p);
427 }
428
429 template <typename O, typename I, typename P>
430 O transform(const I &i, P p)
431 {
432     O o;
433     std::transform(boost::begin(i), boost::end(i),
434                    std::back_inserter(o), p);
435     return o;
436 }
437
438 template <typename I, typename OutputIterator, typename P>
439 OutputIterator transform(const I &i, OutputIterator out, P p)
440 {
441     return std::transform(boost::begin(i), boost::end(i), out, p);
442 }
443
444 template <typename O, typename I, typename P, typename F>
445 O transform_if(const I &i, P p, F f)
446 {
447     O o;
448     transform_if(boost::begin(i), boost::end(i),
449                  std::back_inserter(o), p, f);
450     return o;
451 }
452
453 template <typename V, typename I, typename F>
454 V accumulate_if(const I &i, F f, V v = V())
455 {
456     return accumulate_if(boost::begin(i), boost::end(i), f, v);
457 }
458
459 template <typename V, typename I, typename F, typename B>
460 V accumulate_if(const I &i, F f, V v, B b)
461 {
462     return accumulate_if(boost::begin(i), boost::end(i), f, v, b);
463 }
464
465 template <typename V, typename I, typename F>
466 V accumulate_transform(const I &i, F f, V v = V())
467 {
468     return accumulate_transform(boost::begin(i), boost::end(i), f, v);
469 }
470
471 template <typename V, typename I, typename F, typename B>
472 V accumulate_transform(const I &i, F f, V v, B b)
473 {
474     return accumulate_transform(boost::begin(i), boost::end(i), f, v, b);
475 }
476
477 template <typename V, typename I, typename F, typename P>
478 V accumulate_transform_if(const I &i, F f, P p, V v = V())
479 {
480     return accumulate_transform_if(boost::begin(i), boost::end(i), f, p, v);
481 }
482
483 template <typename V, typename I, typename F, typename P, typename B>
484 V accumulate_transform_if(const I &i, F f, P p, V v, B b)
485 {
486     return accumulate_transform_if(boost::begin(i), boost::end(i), f, p, v, b);
487 }
488
489 template <typename O, typename I>
490 O copy(const I &i)
491 {
492     O o;
493     std::copy(boost::begin(i), boost::end(i), std::back_inserter(o));
494     return o;
495 }
496
497 template <typename O, typename I, typename P>
498 O copy_if(const I &i, P p)
499 {
500     O o;
501     kdtools::copy_if(boost::begin(i), boost::end(i), std::back_inserter(o), p);
502     return o;
503 }
504
505 template <typename I, typename P>
506 P for_each(const I &i, P p)
507 {
508     return std::for_each(boost::begin(i), boost::end(i), p);
509 }
510
511 template <typename I, typename P>
512 P for_each(I &i, P p)
513 {
514     return std::for_each(boost::begin(i), boost::end(i), p);
515 }
516
517 template <typename C1, typename C2>
518 bool equal(const C1 &c1, const C2 &c2)
519 {
520     return boost::size(c1) == boost::size(c2)
521            && std::equal(boost::begin(c1), boost::end(c1),
522                          boost::begin(c2));
523 }
524
525 template <typename C1, typename C2, typename P>
526 bool equal(const C1 &c1, const C2 &c2, P p)
527 {
528     return boost::size(c1) == boost::size(c2)
529            && std::equal(boost::begin(c1), boost::end(c1),
530                          boost::begin(c2), p);
531 }
532
533 template <typename C, typename O1, typename O2, typename P>
534 std::pair<O1, O2> separate_if(const C &c, O1 o1, O2 o2, P p)
535 {
536     return separate_if(boost::begin(c), boost::end(c), o1, o2, p);
537 }
538
539 //@}
540
541 template <typename C>
542 bool any(const C &c)
543 {
544     return any(boost::begin(c), boost::end(c));
545 }
546
547 template <typename C, typename P>
548 bool any(const C &c, P p)
549 {
550     return any(boost::begin(c), boost::end(c), p);
551 }
552
553 template <typename C>
554 bool all(const C &c)
555 {
556     return all(boost::begin(c), boost::end(c));
557 }
558
559 template <typename C, typename P>
560 bool all(const C &c, P p)
561 {
562     return all(boost::begin(c), boost::end(c), p);
563 }
564
565 template <typename C>
566 bool none_of(const C &c)
567 {
568     return none_of(boost::begin(c), boost::end(c));
569 }
570
571 template <typename C, typename P>
572 bool none_of(const C &c, P p)
573 {
574     return kdtools::none_of(boost::begin(c), boost::end(c), p);
575 }
576
577 template <typename C, typename B>
578 B for_each_adjacent_pair(const C &c, B b)
579 {
580     return for_each_adjacent_pair(boost::begin(c), boost::end(c), b);
581 }
582
583 template <typename C, typename B>
584 B for_each_adjacent_pair(C &c, B b)
585 {
586     return for_each_adjacent_pair(boost::begin(c), boost::end(c), b);
587 }
588
589 template <typename C, typename P, typename F>
590 P for_each_if(const C &c, P p, F f)
591 {
592     return for_each_if(boost::begin(c), boost::end(c), p, f);
593 }
594
595 template <typename C, typename P, typename F>
596 P for_each_if(C &c, P p, F f)
597 {
598     return for_each_if(boost::begin(c), boost::end(c), p, f);
599 }
600
601 template <typename C>
602 void sort(C &c)
603 {
604     return std::sort(boost::begin(c), boost::end(c));
605 }
606
607 template <typename C, typename P>
608 void sort(C &c, P p)
609 {
610     return std::sort(boost::begin(c), boost::end(c), p);
611 }
612
613 template <typename C>
614 C sorted(const C &c)
615 {
616     C copy(c);
617     kdtools::sort(copy);
618     return copy;
619 }
620
621 template <typename C, typename P>
622 C sorted(const C &c, P p)
623 {
624     C copy(c);
625     kdtools::sort(copy, p);
626     return copy;
627 }
628
629 }
630
631 #endif /* __KDTOOLSCORE_STL_UTIL_H__ */