libdpf/doc/pages/iterables.md

<!-- # Iterables {#iterables} -->

Multi-point evaluation returns an iterable over the shares it wrote.
The helpers below walk a subset of that range, or of a `bit_array`,
without copying the underlying storage. Read the iterable while the
buffer it refers to is alive. Walking `k` steps is `Θ(k)` time and
`O(1)` extra memory beyond that buffer. `indices_set_in` inspects the
words of its bit view and skips all-zero words, so a dense view is
linear in the bit length. `offset_iterable`'s constructor is one binary
search on a sorted range. `batch_of` steps one bit at a time across its
arrays.

# dpf::subinterval_iterable

`eval_interval` and `eval_full` return one of these (or a tuple of them,
one per selected output). `begin()` / `end()` walk the inclusive
`[from, to]` in input order.

You can also clip an existing iterator. The constructor is
`(iterator, buf_size, from, to, preclip, outputs_per_leaf)`.
`from` and `to` are indices into that iterator. `preclip` is how many
steps `begin()` skips. `outputs_per_leaf` is the packing width; pass 0
for a plain bit array.

\code{cpp}
auto [buf, leaves] = dpf::eval_interval(k0, std::uint8_t{10}, std::uint8_t{20});
for (auto share : leaves) { /* one share per input */ }

dpf::dynamic_bit_array<> bits(128);
dpf::subinterval_iterable view(bits.begin(), bits.size(),
    0, bits.size() - 1, 0, 0);
\endcode

**Defined in**\n
@ref dpf/subinterval_iterable.hpp

## dpf::subsequence_iterable

`eval_sequence(key, begin, end)` returns one. Each step is the share for
the next listed point, in list order. The recipe overload returns a
`recipe_subsequence_iterable` over `recipe.output_indices()`.

The constructor `(out_it, begin, end)` binds an output iterator and the
point list. The usual way to obtain one is the eval call, which also
owns the buffer.

\code{cpp}
std::vector<std::uint8_t> points{1, 4, 9};
auto [buf, listed] = dpf::eval_sequence(k0, points.begin(), points.end());
for (auto share : listed) { /* one share per listed point */ }
\endcode

**Defined in**\n
@ref dpf/subsequence_iterable.hpp

## dpf::setbit_index_iterable

`indices_set_in(iter)` walks the positions whose bit is set.
`iter` is a `subinterval_iterable` of bit iterators: the iterable
`eval_full` / `eval_interval` returns for a `dpf::bit` output, or a
view of a `dynamic_bit_array`. `for_each_set_index(iter, fn)` calls
`fn` on each index.

\code{cpp}
auto [k0, k1] = dpf::make_dpf(std::uint16_t{0xAAAA}, dpf::bit::one);
auto [buf, leaves] = dpf::eval_full(k0);
for (auto index : dpf::indices_set_in(leaves)) { /* set-bit positions */ }
\endcode

**Defined in**\n
@ref dpf/setbit_index_iterable.hpp

## dpf::zip_iterable

`tuple_as_zip` takes an lvalue `std::tuple` of iterables and walks them
together. Each step is a `std::tuple` of the dereferenced values.
`for_each_in_zip(tuple, fn)` does the same with a callback. The tuple
must stay alive for the walk.

\code{cpp}
auto [k0, k1] = dpf::make_dpf(std::uint8_t{3}, std::uint64_t{7});
auto [buf0, it0] = dpf::eval_full(k0);
auto [buf1, it1] = dpf::eval_full(k1);
auto rows = std::make_tuple(it0, it1);
for (auto [a, b] : dpf::tuple_as_zip(rows))
{
    auto opened = dpf::reconstruct(a, b);
}
\endcode

**Defined in**\n
@ref dpf/zip_iterable.hpp

## dpf::parallel_bit_iterable

`batch_of(a, b, ...)` steps several `bit_array`s in lockstep. Each
value is one bit-column, an `std::array` of the lane elements.
`batch_of<N, Child>(it)` does the same from an iterator of `N` arrays.
`for_each_bit_parallel` applies a function to each column.

\code{cpp}
dpf::dynamic_bit_array<> a(64), b(64);
for (auto column : dpf::batch_of(a, b)) { /* column[0], column[1] */ }
\endcode

**Defined in**\n
@ref dpf/parallel_bit_iterable.hpp

## dpf::advice_bit_iterable

`advice_bits_of(iterable)` yields the least significant bit of each
element. `for_each_advice_bit(iterable, fn)` applies `fn` to each bit.
`bit_array_from_advice_bits` packs those bits into a
`dynamic_bit_array`.

\code{cpp}
std::vector<std::uint64_t> nodes{1, 2, 4};
for (auto bit : dpf::advice_bits_of(nodes)) { /* low bit of each word */ }
auto packed = dpf::bit_array_from_advice_bits(dpf::advice_bits_of(nodes));
\endcode

**Defined in**\n
@ref dpf/advice_bit_iterable.hpp

**Code samples**\n
<div class="tabbed">

  - <b class="tab-title">advice_bit_iterable.cpp</b>  \include{cpp} iterables/advice_bit_iterable.cpp

</div>

## dpf::rotation_iterable

`rotated_by(container, n)` walks `container` starting `n` elements in,
then wraps. `for_each_rotated_by(begin, end, n, fn)` calls
`fn(index, value)` in that order; `index` is the element's original
position. The constructor is `(begin, end, rotate_by)`.

\code{cpp}
std::vector<int> values{1, 2, 3};
for (auto x : dpf::rotated_by(values, 1)) { /* 2, 3, 1 */ }
\endcode

**Defined in**\n
@ref dpf/rotation_iterable.hpp

## grotto::offset_iterable

A sorted range, rotated so the first entry is the first value strictly
greater than `offset`, with `offset` subtracted from each element.
Prefix-parity walks use this view.

\code{cpp}
#include "grotto.hpp"
std::vector<int> knots{0, 10, 40};
grotto::offset_iterable shifted(knots.begin(), knots.end(), 10);
\endcode

**Defined in**\n
@ref grotto/offset_iterable.hpp

\htmlonly
<div class="tldr"><b>TL;DR.</b> eval_interval and eval_full walk a subinterval; eval_sequence walks the listed points. indices_set_in, advice_bits_of, batch_of, tuple_as_zip, and rotated_by only change the step. None of them copy the buffer.</div>
\endhtmlonly