stl_util.h 9.94 KB
Newer Older
1
/****************************************************************************
2
** SPDX-FileCopyrightText: 2001-2007 Klarälvdalens Datakonsult AB. All rights reserved.
3
4
5
**
** This file is part of the KD Tools library.
**
6
** SPDX-License-Identifier: GPL-2.0-or-later
7
8
**
**********************************************************************/
9

10
#pragma once
11
12
13
14
15
16
17
18
19

#include <algorithm>
#include <numeric>
#include <utility>
#include <iterator>
#include <functional>

namespace kdtools
{
20
21
22
23
24
25
26
27
28
29
30
template<typename _Iterator, typename UnaryPredicate>
struct filter_iterator
{
    using value_type = typename std::iterator_traits<_Iterator>::value_type;
    using reference = typename std::iterator_traits<_Iterator>::reference;
    using pointer = typename std::iterator_traits<_Iterator>::pointer;
    using difference_type = typename std::iterator_traits<_Iterator>::difference_type;

    filter_iterator(UnaryPredicate pred, _Iterator it, _Iterator last) : it(it), last(last), pred(pred) {}
    template<typename _OtherIter>
    filter_iterator(const filter_iterator<_OtherIter, UnaryPredicate> &other) : it(other.it), last(other.last), pred(other.pred) {}
Daniel Vrátil's avatar
Daniel Vrátil committed
31
32
    filter_iterator &operator++() { while (++it != last && !pred(*it)){} return *this; }
    filter_iterator operator++(int) { auto retval = *this; while(++it != last && !pred(*it)){} return retval; }
33
34
35
36
37
38
    bool operator==(filter_iterator other) const { return it == other.it; }
    bool operator!=(filter_iterator other) const { return it != other.it; }
    typename _Iterator::reference operator*() const { return *it; }
private:
    _Iterator it, last;
    UnaryPredicate pred;
39
40
};

41
42
43
44
45
46
47
48
49
50
51
template<typename _Iterator, typename UnaryPredicate>
filter_iterator<typename std::decay<_Iterator>::type,
                UnaryPredicate>
make_filter_iterator(UnaryPredicate &&pred, _Iterator &&it, _Iterator &&last)
{
    return filter_iterator<typename std::decay<_Iterator>::type, 
                           UnaryPredicate>(
                std::forward<UnaryPredicate>(pred),
                std::forward<_Iterator>(it),
                std::forward<_Iterator>(last));
}
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

template <typename InputIterator, typename OutputIterator, typename UnaryPredicate>
OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred)
{
    while (first != last) {
        if (pred(*first)) {
            *dest = *first;
            ++dest;
        }
        ++first;
    }
    return dest;
}

template <typename OutputIterator, typename InputIterator, typename UnaryFunction, typename UnaryPredicate>
67
void transform_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred, UnaryFunction filter)
68
{
69
70
71
72
73
    for (; first != last; ++first) {
        if (filter(*first)) {
            *dest++ = pred(*first);
        }
    }
74
75
76
77
78
}

template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_1st_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred)
{
79
80
81
82
83
84
85
86
    const auto trans = [](typename std::iterator_traits<InputIterator>::reference v) {
                            return std::get<0>(v);
                       };
    kdtools::transform_if(first, last, dest, trans,
                          [&pred, &trans](typename std::iterator_traits<InputIterator>::reference v) {
                            return pred(trans(v));
                          });
    return dest;
87
88
89
90
91
}

template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_2nd_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred)
{
92
93
94
95
96
97
98
99
    const auto trans = [](typename std::iterator_traits<InputIterator>::reference v) {
                            return std::get<1>(v);
                       };
    kdtools::transform_if(first, last, dest, trans,
                          [&pred, &trans](typename std::iterator_traits<InputIterator>::reference v) {
                            return pred(trans(v));
                          });
    return dest;
100
101
}

102

103
104
105
template <typename OutputIterator, typename InputIterator, typename UnaryFunction>
OutputIterator transform_1st(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func)
{
106
107
108
109
    return std::transform(first, last, dest,
                          [func](typename std::iterator_traits<InputIterator>::reference v) {
                              return func(std::get<0>(v));
                          });
110
111
112
113
114
}

template <typename OutputIterator, typename InputIterator, typename UnaryFunction>
OutputIterator transform_2nd(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func)
{
115
116
117
118
    return std::transform(first, last, dest,
                          [func](typename std::iterator_traits<InputIterator>::reference v) {
                              return func(std::get<1>(v));
                          });
119
120
121
122
123
}

template <typename Value, typename InputIterator, typename UnaryPredicate>
Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value = Value())
{
124
125
    return std::accumulate(make_filter_iterator(filter, first, last),
                           make_filter_iterator(filter, last,  last), value);
126
127
128
129
130
}

template <typename Value, typename InputIterator, typename UnaryPredicate, typename BinaryOperation>
Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value, BinaryOperation op)
{
131
132
    return std::accumulate(make_filter_iterator(filter, first, last),
                           make_filter_iterator(filter, last,  last), value, op);
133
134
135
136
137
}

template <typename Value, typename InputIterator, typename UnaryFunction>
Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value = Value())
{
138
139
140
141
142
143
    return std::accumulate(first, last, value,
                           [map](Value lhs,
                                 typename std::iterator_traits<InputIterator>::reference rhs)
                           {
                               return lhs + map(rhs);
                           });
144
145
146
147
148
}

template <typename Value, typename InputIterator, typename UnaryFunction, typename BinaryOperation>
Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value, BinaryOperation op)
{
149
150
151
152
153
    return std::accumulate(first, last, value,
                           [map, op](typename InputIterator::reference lhs,
                                     typename InputIterator::reference rhs) {
                               return op(map(lhs), map(rhs));
                           });
154
155
156
157
158
}

template <typename Value, typename InputIterator, typename UnaryFunction, typename UnaryPredicate, typename BinaryOperation>
Value accumulate_transform_if(InputIterator first, InputIterator last, UnaryFunction map, UnaryPredicate filter, const Value &value, BinaryOperation op)
{
159
160
161
    return accumulate_transform(make_filter_iterator(filter, first, last),
                                make_filter_iterator(filter, last, last),
                                map, value, op);
162
163
164
165
166
167
}


template <typename InputIterator, typename BinaryOperation>
BinaryOperation for_each_adjacent_pair(InputIterator first, InputIterator last, BinaryOperation op)
{
Laurent Montel's avatar
Laurent Montel committed
168
    using ValueType = typename std::iterator_traits<InputIterator>::value_type;
169
170
171
172
173
174
175
176
177
178
179
180
    if (first == last) {
        return op;
    }
    ValueType value = *first;
    while (++first != last) {
        ValueType tmp = *first;
        op(value, tmp);
        value = tmp;
    }
    return op;
}

181
182
183

template <typename InputIterator, typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate>
std::pair<OutputIterator1, OutputIterator2> separate_if(InputIterator first, InputIterator last, OutputIterator1 dest1, OutputIterator2 dest2, UnaryPredicate pred)
184
{
185
186
187
188
189
190
191
192
193
194
195
    while (first != last) {
        if (pred(*first)) {
            *dest1 = *first;
            ++dest1;
        } else {
            *dest2 = *first;
            ++dest2;
        }
        ++first;
    }
    return std::make_pair(dest1, dest2);
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
}

//@{
/**
   Versions of std::set_intersection optimized for ForwardIterator's
*/
template <typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
OutputIterator set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            first1 = std::lower_bound(++first1, last1, *first2);
        } else if (*first2 < *first1) {
            first2 = std::lower_bound(++first2, last2, *first1);
        } else {
            *result = *first1;
            ++first1;
            ++first2;
            ++result;
        }
    }
    return result;
}

template <typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate>
OutputIterator set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result, BinaryPredicate pred)
{
    while (first1 != last1 && first2 != last2) {
        if (pred(*first1, *first2)) {
            first1 = std::lower_bound(++first1, last1, *first2, pred);
        } else if (pred(*first2, *first1)) {
            first2 = std::lower_bound(++first2, last2, *first1, pred);
        } else {
            *result = *first1;
            ++first1;
            ++first2;
            ++result;
        }
    }
    return result;
}
//@}

template <typename ForwardIterator, typename ForwardIterator2, typename BinaryPredicate>
bool set_intersects(ForwardIterator first1,  ForwardIterator last1,
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    BinaryPredicate pred)
{
    while (first1 != last1 && first2 != last2) {
        if (pred(*first1, *first2)) {
            first1 = std::lower_bound(++first1, last1, *first2, pred);
        } else if (pred(*first2, *first1)) {
            first2 = std::lower_bound(++first2, last2, *first1, pred);
        } else {
            return true;
        }
    }
    return false;
}

}