breadth_first_zip/
lib.rs

1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
5 */
6
7//! Breadth-first exhaustive `zip` for repeatable iterators.
8//! Behavior matches the following pseudocode specification:
9//! - Initialize a counter `i` at zero.
10//! - When propmted, pull the first element from each iterator.
11//!     - If any iterator is empty, return `None`.
12//! - When prompted again, advance only the last iterator.
13//! - Continue to do so until the last iterator terminates or reaches its `i`th element.
14//!     - When it does so, reset it and pull the next element from the second-to-last iterator.
15//! - Repeat this process until we exhaust the first iterator.
16//!     - When you've done that, increase `i` and repeat.
17//! - Once `i` exceeds the longest iterator's length, we're done: return `None`.
18
19#![cfg_attr(not(test), no_std)]
20#![deny(warnings)]
21#![warn(
22    clippy::all,
23    clippy::missing_docs_in_private_items,
24    clippy::nursery,
25    clippy::pedantic,
26    clippy::restriction,
27    clippy::cargo,
28    missing_docs,
29    rustdoc::all
30)]
31#![allow(
32    clippy::blanket_clippy_restriction_lints,
33    clippy::cognitive_complexity,
34    clippy::expect_used,
35    clippy::implicit_return,
36    clippy::inline_always,
37    clippy::needless_borrowed_reference,
38    clippy::panic,
39    clippy::question_mark_used,
40    clippy::separated_literal_suffix,
41    clippy::string_add,
42    clippy::unwrap_used
43)]
44
45use ::core::{cell::Cell, convert::Infallible, marker::PhantomData};
46use reiterator::{Reiterate, Reiterator};
47
48#[cfg(test)]
49mod test;
50
51/// Flatten a nested tuple like `(A, (B, (C, ())))` to a flat one like `(A, B, C)`
52pub trait Flatten {
53    /// Flat tuple, e.g. `(A, B, C)`, not `(A, (B, (C, ())))`.
54    type Flattened;
55    /// Flatten e.g. `(A, (B, (C, ())))` into `(A, B, C)`.
56    #[must_use]
57    fn flatten(self) -> Self::Flattened;
58}
59
60impl Flatten for () {
61    type Flattened = Self;
62    #[inline(always)]
63    #[must_use]
64    fn flatten(self) -> Self::Flattened {}
65}
66
67breadth_first_zip_macros::implement_flatten!();
68
69/// End of a recursive implementation of a breadth-first exhaustive `zip`.
70#[derive(Clone, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
71pub struct BaseCase(Cell<bool>);
72
73/// Sealed traits.
74mod sealed {
75    /// Either `BaseCase` or a sequence `BreadthFirst<Whatever, ...>` ending in `BaseCase` on the right-hand side.
76    pub trait BreadthFirst {}
77    impl BreadthFirst for super::BaseCase {}
78    impl<'item, Head: Iterator, Tail: super::BreadthFirst<'item>> BreadthFirst
79        for super::BreadthFirstZipped<'item, Head, Tail>
80    {
81    }
82}
83
84/// Helper trait returning a nested list that will be turned into a flat list for a huge but finite range of tuple sizes.
85pub trait BreadthFirst<'item>: sealed::BreadthFirst {
86    /// Depth of recursion.
87    const DEPTH: usize;
88    /// Output of `advance` if successful.
89    type Advance: Flatten;
90    /// Fallibly choose the next output.
91    #[must_use]
92    fn next(&'item self, index_sum: usize) -> Option<Self::Advance>;
93    /// Rewind the iterator back to its starting point
94    fn rewind(&self);
95}
96
97impl<'item> BreadthFirst<'item> for BaseCase {
98    const DEPTH: usize = 0;
99    type Advance = ();
100    #[inline(always)]
101    #[must_use]
102    fn next(&self, index_sum: usize) -> Option<Self::Advance> {
103        (index_sum == 0 && self.0.get()).then(|| {
104            self.0.set(false);
105        })
106    }
107    #[inline(always)]
108    fn rewind(&self) {
109        self.0.set(true);
110    }
111}
112
113/// Recursive implementation of a breadth-first exhaustive `zip`.
114pub struct BreadthFirstZipped<'item, Head: Iterator, Tail: BreadthFirst<'item>> {
115    /// Enumerated caching iterator for this current "index" in the recursive scheme.
116    iter: Reiterator<Head>,
117    /// Implementations for the rest of the list.
118    tail: Tail,
119    /// Representation of this struct's lifetime.
120    lifetime: PhantomData<&'item Infallible>,
121}
122
123impl<'item, Head: Iterator, Tail: BreadthFirst<'item>> BreadthFirstZipped<'item, Head, Tail> {
124    /// Initialize a new recursive node of a breadth-first zip implementation.
125    #[inline(always)]
126    pub fn new(head: Head, tail: Tail) -> Self {
127        Self {
128            iter: head.reiterate(),
129            tail,
130            lifetime: PhantomData,
131        }
132    }
133}
134
135impl<'item, Head: Iterator, Tail: BreadthFirst<'item>> BreadthFirst<'item>
136    for BreadthFirstZipped<'item, Head, Tail>
137where
138    Head::Item: 'item,
139    (&'item Head::Item, Tail::Advance): Flatten,
140{
141    const DEPTH: usize = Tail::DEPTH + 1;
142    type Advance = (&'item Head::Item, Tail::Advance);
143    #[inline(always)]
144    #[must_use]
145    fn next(&'item self, index_sum: usize) -> Option<Self::Advance> {
146        loop {
147            if let Some(tail) = self
148                .tail
149                .next(index_sum.checked_sub(self.iter.index.get())?)
150            {
151                return self.iter.get().map(|indexed| (indexed.value, tail));
152            }
153            (self.iter.index.get() < index_sum).then(|| self.iter.next())??; // Comparison is just an optimization, not logically necessary
154            self.tail.rewind();
155        }
156    }
157    #[inline(always)]
158    fn rewind(&self) {
159        self.iter.restart();
160        self.tail.rewind();
161    }
162}
163
164/// Helper struct for a breadth-first zip: a counter controlling the maximum index sum of the internal recursive implementation.
165#[derive(Clone, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
166pub struct BreadthFirstManager<'item, Tail: BreadthFirst<'item>> {
167    /// Recursive implementation.
168    tail: Tail,
169    /// "Global" counter to allow the maximum possible sum of indices.
170    index_sum: Cell<usize>,
171    /// Representation of this struct's lifetime.
172    lifetime: PhantomData<&'item Infallible>,
173}
174
175impl<'item, Tail: BreadthFirst<'item>> BreadthFirstManager<'item, Tail> {
176    /// Initialize a new breadth-first algorithm.
177    #[inline(always)]
178    #[must_use]
179    pub const fn new(tail: Tail) -> Self {
180        Self {
181            tail,
182            index_sum: Cell::new(0),
183            lifetime: PhantomData,
184        }
185    }
186    /// Like `Iterator::next` but with a generic lifetime.
187    /// Why not implement `Iterator`? <https://stackoverflow.com/questions/68606470/how-to-return-a-reference-when-implementing-an-iterator>
188    #[allow(clippy::should_implement_trait)]
189    #[inline(always)]
190    #[must_use]
191    pub fn next(&'item self) -> Option<<Tail::Advance as Flatten>::Flattened> {
192        self.tail
193            .next(self.index_sum.get())
194            .map_or_else(
195                || {
196                    self.index_sum.set(self.index_sum.get().checked_add(1)?);
197                    self.tail.rewind();
198                    self.tail.next(self.index_sum.get())
199                },
200                Some,
201            )
202            .map(Flatten::flatten)
203    }
204}
205
206/// Zip a tuple into a lazy breadth-first traversal of each possible combination with a monotonically increasing sum of indices.
207pub trait BreadthFirstZip<'item> {
208    /// Rearrangement of input into a nested tuple.
209    type Nested: BreadthFirst<'item>;
210    /// Lazy breadth-first exhaustive `zip` that guarantees a monotonically increasing sum of indices.
211    fn breadth_first(self) -> BreadthFirstManager<'item, Self::Nested>;
212    /// Unflatten a tuple like `(A, B, C)` to `BreadthFirstZipped<A, BreadthFirstZipped<B, BreadthFirstZipped<C, BaseCase>>>`.
213    /// # Errors
214    /// If any iterator is empty.
215    fn unflatten(self) -> Self::Nested;
216}
217
218impl<'item> BreadthFirstZip<'item> for () {
219    type Nested = BaseCase;
220    #[inline(always)]
221    fn breadth_first(self) -> BreadthFirstManager<'item, Self::Nested> {
222        BreadthFirstManager::new(self.unflatten())
223    }
224    #[inline(always)]
225    fn unflatten(self) -> Self::Nested {
226        BaseCase(Cell::new(true))
227    }
228}
229
230breadth_first_zip_macros::implement!(); // Implement traits for (A,), (A, B), (A, B, C), (A, B, C, D), ...
breadth_first_zip/lib.rs

breadth_first_zip/
lib.rs
