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