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
15namespace 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 */
40template <typename Range, typename Fn>
41void for_each_chunk(const Range& r, Fn&& fn)
42{
43 r.impl().for_each_chunk(std::forward<Fn>(fn));
44}
45
46template <typename Iterator, typename Fn>
47void 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
54template <typename T, typename Fn>
55void 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 */
74template <typename Range, typename Fn>
75bool for_each_chunk_p(const Range& r, Fn&& fn)
76{
77 return r.impl().for_each_chunk_p(std::forward<Fn>(fn));
78}
79
80template <typename Iterator, typename Fn>
81bool 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
88template <typename T, typename Fn>
89bool 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 */
97template <typename Range, typename T>
98T 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
106template <typename Range, typename T, typename Fn>
107T 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 */
119template <typename Iterator, typename T>
120T 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
128template <typename Iterator, typename T, typename Fn>
129T 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 */
140template <typename Range, typename Fn>
141Fn&& 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 */
154template <typename Iterator, typename Fn>
155Fn&& 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 */
167template <typename Range, typename OutIter>
168OutIter 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 */
180template <typename InIter, typename OutIter>
181OutIter 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 */
192template <typename Range, typename Pred>
193bool 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 */
204template <typename Iter, typename Pred>
205bool 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