use std::iter::Cycle;
use std::iter::Fuse;
use std::iter::FusedIterator;
use crate::size_hint;
pub trait HomogeneousTuple: TupleCollect {}
impl<T: TupleCollect> HomogeneousTuple for T {}
#[derive(Clone, Debug)]
pub struct TupleBuffer<T>
where
T: HomogeneousTuple,
{
cur: usize,
buf: T::Buffer,
}
impl<T> TupleBuffer<T>
where
T: HomogeneousTuple,
{
fn new(buf: T::Buffer) -> Self {
Self { cur: 0, buf }
}
}
impl<T> Iterator for TupleBuffer<T>
where
T: HomogeneousTuple,
{
type Item = T::Item;
fn next(&mut self) -> Option<Self::Item> {
let s = self.buf.as_mut();
if let Some(ref mut item) = s.get_mut(self.cur) {
self.cur += 1;
item.take()
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let buffer = &self.buf.as_ref()[self.cur..];
let len = if buffer.is_empty() {
0
} else {
buffer
.iter()
.position(|x| x.is_none())
.unwrap_or(buffer.len())
};
(len, Some(len))
}
}
impl<T> ExactSizeIterator for TupleBuffer<T> where T: HomogeneousTuple {}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
pub struct Tuples<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple,
{
iter: Fuse<I>,
buf: T::Buffer,
}
pub fn tuples<I, T>(iter: I) -> Tuples<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple,
{
Tuples {
iter: iter.fuse(),
buf: Default::default(),
}
}
impl<I, T> Iterator for Tuples<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple,
{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
T::collect_from_iter(&mut self.iter, &mut self.buf)
}
fn size_hint(&self) -> (usize, Option<usize>) {
let buffered = T::buffer_len(&self.buf);
let (unbuffered_lo, unbuffered_hi) = self.iter.size_hint();
let total_lo = add_then_div(unbuffered_lo, buffered, T::num_items()).unwrap_or(usize::MAX);
let total_hi = unbuffered_hi.and_then(|hi| add_then_div(hi, buffered, T::num_items()));
(total_lo, total_hi)
}
}
fn add_then_div(n: usize, a: usize, d: usize) -> Option<usize> {
debug_assert_ne!(d, 0);
(n / d).checked_add(a / d)?.checked_add((n % d + a % d) / d)
}
impl<I, T> ExactSizeIterator for Tuples<I, T>
where
I: ExactSizeIterator<Item = T::Item>,
T: HomogeneousTuple,
{
}
impl<I, T> Tuples<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple,
{
pub fn into_buffer(self) -> TupleBuffer<T> {
TupleBuffer::new(self.buf)
}
}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[derive(Clone, Debug)]
pub struct TupleWindows<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple,
{
iter: I,
last: Option<T>,
}
pub fn tuple_windows<I, T>(iter: I) -> TupleWindows<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple,
T::Item: Clone,
{
TupleWindows { last: None, iter }
}
impl<I, T> Iterator for TupleWindows<I, T>
where
I: Iterator<Item = T::Item>,
T: HomogeneousTuple + Clone,
T::Item: Clone,
{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if T::num_items() == 1 {
return T::collect_from_iter_no_buf(&mut self.iter);
}
if let Some(new) = self.iter.next() {
if let Some(ref mut last) = self.last {
last.left_shift_push(new);
Some(last.clone())
} else {
use std::iter::once;
let iter = once(new).chain(&mut self.iter);
self.last = T::collect_from_iter_no_buf(iter);
self.last.clone()
}
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let mut sh = self.iter.size_hint();
if self.last.is_none() {
sh = size_hint::sub_scalar(sh, T::num_items() - 1);
}
sh
}
}
impl<I, T> ExactSizeIterator for TupleWindows<I, T>
where
I: ExactSizeIterator<Item = T::Item>,
T: HomogeneousTuple + Clone,
T::Item: Clone,
{
}
impl<I, T> FusedIterator for TupleWindows<I, T>
where
I: FusedIterator<Item = T::Item>,
T: HomogeneousTuple + Clone,
T::Item: Clone,
{
}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[derive(Debug, Clone)]
pub struct CircularTupleWindows<I, T>
where
I: Iterator<Item = T::Item> + Clone,
T: TupleCollect + Clone,
{
iter: TupleWindows<Cycle<I>, T>,
len: usize,
}
pub fn circular_tuple_windows<I, T>(iter: I) -> CircularTupleWindows<I, T>
where
I: Iterator<Item = T::Item> + Clone + ExactSizeIterator,
T: TupleCollect + Clone,
T::Item: Clone,
{
let len = iter.len();
let iter = tuple_windows(iter.cycle());
CircularTupleWindows { iter, len }
}
impl<I, T> Iterator for CircularTupleWindows<I, T>
where
I: Iterator<Item = T::Item> + Clone,
T: TupleCollect + Clone,
T::Item: Clone,
{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.len != 0 {
self.len -= 1;
self.iter.next()
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len, Some(self.len))
}
}
impl<I, T> ExactSizeIterator for CircularTupleWindows<I, T>
where
I: Iterator<Item = T::Item> + Clone,
T: TupleCollect + Clone,
T::Item: Clone,
{
}
impl<I, T> FusedIterator for CircularTupleWindows<I, T>
where
I: Iterator<Item = T::Item> + Clone,
T: TupleCollect + Clone,
T::Item: Clone,
{
}
pub trait TupleCollect: Sized {
type Item;
type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>;
fn buffer_len(buf: &Self::Buffer) -> usize {
let s = buf.as_ref();
s.iter().position(Option::is_none).unwrap_or(s.len())
}
fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
where
I: IntoIterator<Item = Self::Item>;
fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
where
I: IntoIterator<Item = Self::Item>;
fn num_items() -> usize;
fn left_shift_push(&mut self, item: Self::Item);
}
macro_rules! rev_for_each_ident{
($m:ident, ) => {};
($m:ident, $i0:ident, $($i:ident,)*) => {
rev_for_each_ident!($m, $($i,)*);
$m!($i0);
};
}
macro_rules! impl_tuple_collect {
($dummy:ident,) => {}; ($dummy:ident, $($Y:ident,)*) => (
impl_tuple_collect!($($Y,)*);
impl<A> TupleCollect for ($(ignore_ident!($Y, A),)*) {
type Item = A;
type Buffer = [Option<A>; count_ident!($($Y)*) - 1];
#[allow(unused_assignments, unused_mut)]
fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
where I: IntoIterator<Item = A>
{
let mut iter = iter.into_iter();
$(
let mut $Y = None;
)*
loop {
$(
$Y = iter.next();
if $Y.is_none() {
break
}
)*
return Some(($($Y.unwrap()),*,))
}
let mut i = 0;
let mut s = buf.as_mut();
$(
if i < s.len() {
s[i] = $Y;
i += 1;
}
)*
return None;
}
fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
where I: IntoIterator<Item = A>
{
let mut iter = iter.into_iter();
Some(($(
{ let $Y = iter.next()?; $Y },
)*))
}
fn num_items() -> usize {
count_ident!($($Y)*)
}
fn left_shift_push(&mut self, mut item: A) {
use std::mem::replace;
let &mut ($(ref mut $Y),*,) = self;
macro_rules! replace_item{($i:ident) => {
item = replace($i, item);
}}
rev_for_each_ident!(replace_item, $($Y,)*);
drop(item);
}
}
)
}
impl_tuple_collect!(dummy, a, b, c, d, e, f, g, h, i, j, k, l,);