1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
//
// immer: immutable data structures for C++
// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
//
// This software is distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
//
#pragma once
#include <algorithm>
#include <numeric>
#include <type_traits>
namespace immer {
/**
* @defgroup algorithm
* @{
*/
/*@{*/
// Right now these algorithms dispatch directly to the vector
// implementations unconditionally. This will be changed in the
// future to support other kinds of containers.
/*!
* Apply operation `fn` for every contiguous *chunk* of data in the
* range sequentially. Each time, `Fn` is passed two `value_type`
* pointers describing a range over a part of the vector. This allows
* iterating over the elements in the most efficient way.
*
* @rst
*
* .. tip:: This is a low level method. Most of the time, :doc:`other
* wrapper algorithms <algorithms>` should be used instead.
*
* @endrst
*/
template <typename Range, typename Fn>
void for_each_chunk(const Range& r, Fn&& fn)
{
r.impl().for_each_chunk(std::forward<Fn>(fn));
}
template <typename Iterator, typename Fn>
void for_each_chunk(const Iterator& first, const Iterator& last, Fn&& fn)
{
assert(&first.impl() == &last.impl());
first.impl().for_each_chunk(
first.index(), last.index(), std::forward<Fn>(fn));
}
template <typename T, typename Fn>
void for_each_chunk(const T* first, const T* last, Fn&& fn)
{
std::forward<Fn>(fn)(first, last);
}
/*!
* Apply operation `fn` for every contiguous *chunk* of data in the
* range sequentially, until `fn` returns `false`. Each time, `Fn` is
* passed two `value_type` pointers describing a range over a part of
* the vector. This allows iterating over the elements in the most
* efficient way.
*
* @rst
*
* .. tip:: This is a low level method. Most of the time, :doc:`other
* wrapper algorithms <algorithms>` should be used instead.
*
* @endrst
*/
template <typename Range, typename Fn>
bool for_each_chunk_p(const Range& r, Fn&& fn)
{
return r.impl().for_each_chunk_p(std::forward<Fn>(fn));
}
template <typename Iterator, typename Fn>
bool for_each_chunk_p(const Iterator& first, const Iterator& last, Fn&& fn)
{
assert(&first.impl() == &last.impl());
return first.impl().for_each_chunk_p(
first.index(), last.index(), std::forward<Fn>(fn));
}
template <typename T, typename Fn>
bool for_each_chunk_p(const T* first, const T* last, Fn&& fn)
{
return std::forward<Fn>(fn)(first, last);
}
/*!
* Equivalent of `std::accumulate` applied to the range `r`.
*/
template <typename Range, typename T>
T accumulate(Range&& r, T init)
{
for_each_chunk(r, [&](auto first, auto last) {
init = std::accumulate(first, last, init);
});
return init;
}
template <typename Range, typename T, typename Fn>
T accumulate(Range&& r, T init, Fn fn)
{
for_each_chunk(r, [&](auto first, auto last) {
init = std::accumulate(first, last, init, fn);
});
return init;
}
/*!
* Equivalent of `std::accumulate` applied to the range @f$ [first,
* last) @f$.
*/
template <typename Iterator, typename T>
T accumulate(Iterator first, Iterator last, T init)
{
for_each_chunk(first, last, [&](auto first, auto last) {
init = std::accumulate(first, last, init);
});
return init;
}
template <typename Iterator, typename T, typename Fn>
T accumulate(Iterator first, Iterator last, T init, Fn fn)
{
for_each_chunk(first, last, [&](auto first, auto last) {
init = std::accumulate(first, last, init, fn);
});
return init;
}
/*!
* Equivalent of `std::for_each` applied to the range `r`.
*/
template <typename Range, typename Fn>
Fn&& for_each(Range&& r, Fn&& fn)
{
for_each_chunk(r, [&](auto first, auto last) {
for (; first != last; ++first)
fn(*first);
});
return std::forward<Fn>(fn);
}
/*!
* Equivalent of `std::for_each` applied to the range @f$ [first,
* last) @f$.
*/
template <typename Iterator, typename Fn>
Fn&& for_each(Iterator first, Iterator last, Fn&& fn)
{
for_each_chunk(first, last, [&](auto first, auto last) {
for (; first != last; ++first)
fn(*first);
});
return std::forward<Fn>(fn);
}
/*!
* Equivalent of `std::copy` applied to the range `r`.
*/
template <typename Range, typename OutIter>
OutIter copy(Range&& r, OutIter out)
{
for_each_chunk(
r, [&](auto first, auto last) { out = std::copy(first, last, out); });
return out;
}
/*!
* Equivalent of `std::copy` applied to the range @f$ [first,
* last) @f$.
*/
template <typename InIter, typename OutIter>
OutIter copy(InIter first, InIter last, OutIter out)
{
for_each_chunk(first, last, [&](auto first, auto last) {
out = std::copy(first, last, out);
});
return out;
}
/*!
* Equivalent of `std::all_of` applied to the range `r`.
*/
template <typename Range, typename Pred>
bool all_of(Range&& r, Pred p)
{
return for_each_chunk_p(
r, [&](auto first, auto last) { return std::all_of(first, last, p); });
}
/*!
* Equivalent of `std::all_of` applied to the range @f$ [first, last)
* @f$.
*/
template <typename Iter, typename Pred>
bool all_of(Iter first, Iter last, Pred p)
{
return for_each_chunk_p(first, last, [&](auto first, auto last) {
return std::all_of(first, last, p);
});
}
/** @} */ // group: algorithm
} // namespace immer
|
