/src/immer/immer/algorithm.hpp

Source
//
// 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 <cassert>
#include <functional>
#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);
}

namespace detail {

template <class Iter, class T>
T accumulate_move(Iter first, Iter last, T init)
{
    for (; first != last; ++first)
        init = std::move(init) + *first;
    return init;
}

template <class Iter, class T, class Fn>
T accumulate_move(Iter first, Iter last, T init, Fn op)
{
    for (; first != last; ++first)
        init = op(std::move(init), *first);
    return init;
}

} // namespace detail

/*!
 * 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 = detail::accumulate_move(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 = detail::accumulate_move(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 = detail::accumulate_move(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 = detail::accumulate_move(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);
    });
}

/*!
 * Object that can be used to process changes as computed by the @a diff
 * algorithm.
 *
 * @tparam AddedFn Unary function that is be called whenever an added element is
 *         found. It is called with the added element as argument.
 *
 * @tparam RemovedFn Unary function that is called whenever a removed element is
 *         found.  It is called with the removed element as argument.
 *
 * @tparam ChangedFn Unary function that is called whenever a changed element is
 *         found.  It is called with the changed element as argument.
 */
template <class AddedFn, class RemovedFn, class ChangedFn>
struct differ
{
    AddedFn added;
    RemovedFn removed;
    ChangedFn changed;
};

/*!
 * Produces a @a differ object with `added`, `removed` and `changed` functions.
 */
template <class AddedFn, class RemovedFn, class ChangedFn>
auto make_differ(AddedFn&& added, RemovedFn&& removed, ChangedFn&& changed)
    -> differ<std::decay_t<AddedFn>,
              std::decay_t<RemovedFn>,
              std::decay_t<ChangedFn>>
{
    return {std::forward<AddedFn>(added),
            std::forward<RemovedFn>(removed),
            std::forward<ChangedFn>(changed)};
}

/*!
 * Produces a @a differ object with `added` and `removed` functions and no
 * `changed` function.
 */
template <class AddedFn, class RemovedFn>
auto make_differ(AddedFn&& added, RemovedFn&& removed)
{
    return make_differ(std::forward<AddedFn>(added),
                       std::forward<RemovedFn>(removed),
                       [](auto&&...) {});
}

/*!
 * Compute the differences between `a` and `b`.
 *
 * Changes detected are notified via the differ object, which should support the
 * following expressions:
 *
 *   - `differ.added(x)`, invoked when element `x` is found in `b` but not in
 *      `a`.
 *
 *   - `differ.removed(x)`, invoked when element `x` is found in `a` but not in
 *      `b`.
 *
 *   - `differ.changed(x, y)`, invoked when element `x` and `y` from `a` and `b`
 *      share the same key but map to a different value.
 *
 * This method leverages structural sharing to offer a complexity @f$ O(|diff|)
 * @f$ when `b` is derived from `a` by performing @f$ |diff| @f$ updates.  This
 * is, this function can detect changes in effectively constant time per update,
 * as oposed to the @f$ O(|a|+|b|) @f$ complexity of a trivial implementation.
 *
 * @rst
 *
 * .. note:: This method is only implemented for ``map`` and ``set``. When sets
 *           are diffed, the ``changed`` function is never called.
 *
 * @endrst
 */
template <typename T, typename Differ>
void diff(const T& a, const T& b, Differ&& differ)
{
    a.impl().template diff<std::equal_to<typename T::value_type>>(
        b.impl(), std::forward<Differ>(differ));
}

/*!
 * Compute the differences between `a` and `b` using the callbacks in `fns` as
 * differ.  Equivalent to `diff(a, b, make_differ(fns)...)`.
 */
template <typename T, typename... Fns>
void diff(const T& a, const T& b, Fns&&... fns)
{
    diff(a, b, make_differ(std::forward<Fns>(fns)...));
}

/** @} */ // group: algorithm

} // namespace immer

Coverage Report

Created: 2025-08-25 06:15

Line	Count	Source
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 <cassert>
13		#include <functional>
14		#include <numeric>
15		#include <type_traits>
16
17		namespace immer {
18
19		/**
20		* @defgroup algorithm
21		* @{
22		*/
23
24		/@{/
25		// Right now these algorithms dispatch directly to the vector
26		// implementations unconditionally. This will be changed in the
27		// future to support other kinds of containers.
28
29		/*!
30		* Apply operation `fn` for every contiguous chunk of data in the
31		* range sequentially. Each time, `Fn` is passed two `value_type`
32		* pointers describing a range over a part of the vector. This allows
33		* iterating over the elements in the most efficient way.
34		*
35		* @rst
36		*
37		* .. tip:: This is a low level method. Most of the time, :doc:`other
38		* wrapper algorithms <algorithms>` should be used instead.
39		*
40		* @endrst
41		*/
42		template <typename Range, typename Fn>
43		void for_each_chunk(const Range& r, Fn&& fn)
44		{
45		r.impl().for_each_chunk(std::forward<Fn>(fn));
46		}
47
48		template <typename Iterator, typename Fn>
49		void for_each_chunk(const Iterator& first, const Iterator& last, Fn&& fn)
50		{
51		assert(&first.impl() == &last.impl());
52		first.impl().for_each_chunk(
53		first.index(), last.index(), std::forward<Fn>(fn));
54		}
55
56		template <typename T, typename Fn>
57		void for_each_chunk(const T* first, const T* last, Fn&& fn)
58		{
59		std::forward<Fn>(fn)(first, last);
60		}
61
62		/*!
63		* Apply operation `fn` for every contiguous chunk of data in the
64		* range sequentially, until `fn` returns `false`. Each time, `Fn` is
65		* passed two `value_type` pointers describing a range over a part of
66		* the vector. This allows iterating over the elements in the most
67		* efficient way.
68		*
69		* @rst
70		*
71		* .. tip:: This is a low level method. Most of the time, :doc:`other
72		* wrapper algorithms <algorithms>` should be used instead.
73		*
74		* @endrst
75		*/
76		template <typename Range, typename Fn>
77		bool for_each_chunk_p(const Range& r, Fn&& fn)
78		{
79		return r.impl().for_each_chunk_p(std::forward<Fn>(fn));
80		}
81
82		template <typename Iterator, typename Fn>
83		bool for_each_chunk_p(const Iterator& first, const Iterator& last, Fn&& fn)
84		{
85		assert(&first.impl() == &last.impl());
86		return first.impl().for_each_chunk_p(
87		first.index(), last.index(), std::forward<Fn>(fn));
88		}
89
90		template <typename T, typename Fn>
91		bool for_each_chunk_p(const T* first, const T* last, Fn&& fn)
92		{
93		return std::forward<Fn>(fn)(first, last);
94		}
95
96		namespace detail {
97
98		template <class Iter, class T>
99		T accumulate_move(Iter first, Iter last, T init)
100		{
101		for (; first != last; ++first)
102		init = std::move(init) + *first;
103		return init;
104		}
105
106		template <class Iter, class T, class Fn>
107		T accumulate_move(Iter first, Iter last, T init, Fn op)
108		{
109		for (; first != last; ++first)
110		init = op(std::move(init), *first);
111		return init;
112		}
113
114		} // namespace detail
115
116		/*!
117		* Equivalent of `std::accumulate` applied to the range `r`.
118		*/
119		template <typename Range, typename T>
120		T accumulate(Range&& r, T init)
121		{
122		for_each_chunk(r, [&](auto first, auto last) {
123		init = detail::accumulate_move(first, last, init);
124		});
125		return init;
126		}
127
128		template <typename Range, typename T, typename Fn>
129		T accumulate(Range&& r, T init, Fn fn)
130		{
131		for_each_chunk(r, [&](auto first, auto last) {
132		init = detail::accumulate_move(first, last, init, fn);
133		});
134		return init;
135		}
136
137		/*!
138		* Equivalent of `std::accumulate` applied to the range @f$ [first,
139		* last) @f$.
140		*/
141		template <typename Iterator, typename T>
142		T accumulate(Iterator first, Iterator last, T init)
143		{
144		for_each_chunk(first, last, [&](auto first, auto last) {
145		init = detail::accumulate_move(first, last, init);
146		});
147		return init;
148		}
149
150		template <typename Iterator, typename T, typename Fn>
151		T accumulate(Iterator first, Iterator last, T init, Fn fn)
152		{
153		for_each_chunk(first, last, [&](auto first, auto last) {
154		init = detail::accumulate_move(first, last, init, fn);
155		});
156		return init;
157		}
158
159		/*!
160		* Equivalent of `std::for_each` applied to the range `r`.
161		*/
162		template <typename Range, typename Fn>
163		Fn&& for_each(Range&& r, Fn&& fn)
164		{
165		for_each_chunk(r, [&](auto first, auto last) {
166		for (; first != last; ++first)
167		fn(*first);
168		});
169		return std::forward<Fn>(fn);
170		}
171
172		/*!
173		* Equivalent of `std::for_each` applied to the range @f$ [first,
174		* last) @f$.
175		*/
176		template <typename Iterator, typename Fn>
177		Fn&& for_each(Iterator first, Iterator last, Fn&& fn)
178		{
179		for_each_chunk(first, last, [&](auto first, auto last) {
180		for (; first != last; ++first)
181		fn(*first);
182		});
183		return std::forward<Fn>(fn);
184		}
185
186		/*!
187		* Equivalent of `std::copy` applied to the range `r`.
188		*/
189		template <typename Range, typename OutIter>
190		OutIter copy(Range&& r, OutIter out)
191		{
192		for_each_chunk(
193		r, [&](auto first, auto last) { out = std::copy(first, last, out); });
194		return out;
195		}
196
197		/*!
198		* Equivalent of `std::copy` applied to the range @f$ [first,
199		* last) @f$.
200		*/
201		template <typename InIter, typename OutIter>
202		OutIter copy(InIter first, InIter last, OutIter out)
203		{
204		for_each_chunk(first, last, [&](auto first, auto last) {
205		out = std::copy(first, last, out);
206		});
207		return out;
208		}
209
210		/*!
211		* Equivalent of `std::all_of` applied to the range `r`.
212		*/
213		template <typename Range, typename Pred>
214		bool all_of(Range&& r, Pred p)
215		{
216		return for_each_chunk_p(
217		r, [&](auto first, auto last) { return std::all_of(first, last, p); });
218		}
219
220		/*!
221		* Equivalent of `std::all_of` applied to the range @f$ [first, last)
222		* @f$.
223		*/
224		template <typename Iter, typename Pred>
225		bool all_of(Iter first, Iter last, Pred p)
226		{
227		return for_each_chunk_p(first, last, [&](auto first, auto last) {
228		return std::all_of(first, last, p);
229		});
230		}
231
232		/*!
233		* Object that can be used to process changes as computed by the @a diff
234		* algorithm.
235		*
236		* @tparam AddedFn Unary function that is be called whenever an added element is
237		* found. It is called with the added element as argument.
238		*
239		* @tparam RemovedFn Unary function that is called whenever a removed element is
240		* found. It is called with the removed element as argument.
241		*
242		* @tparam ChangedFn Unary function that is called whenever a changed element is
243		* found. It is called with the changed element as argument.
244		*/
245		template <class AddedFn, class RemovedFn, class ChangedFn>
246		struct differ
247		{
248		AddedFn added;
249		RemovedFn removed;
250		ChangedFn changed;
251		};
252
253		/*!
254		* Produces a @a differ object with `added`, `removed` and `changed` functions.
255		*/
256		template <class AddedFn, class RemovedFn, class ChangedFn>
257		auto make_differ(AddedFn&& added, RemovedFn&& removed, ChangedFn&& changed)
258		-> differ<std::decay_t<AddedFn>,
259		std::decay_t<RemovedFn>,
260		std::decay_t<ChangedFn>>
261	12.1k	{
262	12.1k	return {std::forward<AddedFn>(added),
263	12.1k	std::forward<RemovedFn>(removed),
264	12.1k	std::forward<ChangedFn>(changed)};
265	12.1k	}
266
267		/*!
268		* Produces a @a differ object with `added` and `removed` functions and no
269		* `changed` function.
270		*/
271		template <class AddedFn, class RemovedFn>
272		auto make_differ(AddedFn&& added, RemovedFn&& removed)
273		{
274		return make_differ(std::forward<AddedFn>(added),
275		std::forward<RemovedFn>(removed),
276		[](auto&&...) {});
277		}
278
279		/*!
280		* Compute the differences between `a` and `b`.
281		*
282		* Changes detected are notified via the differ object, which should support the
283		* following expressions:
284		*
285		* - `differ.added(x)`, invoked when element `x` is found in `b` but not in
286		* `a`.
287		*
288		* - `differ.removed(x)`, invoked when element `x` is found in `a` but not in
289		* `b`.
290		*
291		* - `differ.changed(x, y)`, invoked when element `x` and `y` from `a` and `b`
292		* share the same key but map to a different value.
293		*
294		* This method leverages structural sharing to offer a complexity @f$ O(\|diff\|)
295		* @f$ when `b` is derived from `a` by performing @f$ \|diff\| @f$ updates. This
296		* is, this function can detect changes in effectively constant time per update,
297		* as oposed to the @f$ O(\|a\|+\|b\|) @f$ complexity of a trivial implementation.
298		*
299		* @rst
300		*
301		* .. note:: This method is only implemented for ``map`` and ``set``. When sets
302		* are diffed, the ``changed`` function is never called.
303		*
304		* @endrst
305		*/
306		template <typename T, typename Differ>
307		void diff(const T& a, const T& b, Differ&& differ)
308	12.1k	{
309	12.1k	a.impl().template diff<std::equal_to<typename T::value_type>>(
310	12.1k	b.impl(), std::forward<Differ>(differ));
311	12.1k	}
312
313		/*!
314		* Compute the differences between `a` and `b` using the callbacks in `fns` as
315		* differ. Equivalent to `diff(a, b, make_differ(fns)...)`.
316		*/
317		template <typename T, typename... Fns>
318		void diff(const T& a, const T& b, Fns&&... fns)
319	12.1k	{
320	12.1k	diff(a, b, make_differ(std::forward<Fns>(fns)...));
321	12.1k	}
322
323		/** @} */ // group: algorithm
324
325		} // namespace immer