From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/itertools/src/tuple_impl.rs | 331 +++++++++++++++++++++++++++++++++++++ 1 file changed, 331 insertions(+) create mode 100644 vendor/itertools/src/tuple_impl.rs (limited to 'vendor/itertools/src/tuple_impl.rs') diff --git a/vendor/itertools/src/tuple_impl.rs b/vendor/itertools/src/tuple_impl.rs new file mode 100644 index 000000000..d914e0323 --- /dev/null +++ b/vendor/itertools/src/tuple_impl.rs @@ -0,0 +1,331 @@ +//! Some iterator that produces tuples + +use std::iter::Fuse; +use std::iter::FusedIterator; +use std::iter::Take; +use std::iter::Cycle; +use std::marker::PhantomData; + +// `HomogeneousTuple` is a public facade for `TupleCollect`, allowing +// tuple-related methods to be used by clients in generic contexts, while +// hiding the implementation details of `TupleCollect`. +// See https://github.com/rust-itertools/itertools/issues/387 + +/// Implemented for homogeneous tuples of size up to 12. +pub trait HomogeneousTuple + : TupleCollect +{} + +impl HomogeneousTuple for T {} + +/// An iterator over a incomplete tuple. +/// +/// See [`.tuples()`](crate::Itertools::tuples) and +/// [`Tuples::into_buffer()`]. +#[derive(Clone, Debug)] +pub struct TupleBuffer + where T: HomogeneousTuple +{ + cur: usize, + buf: T::Buffer, +} + +impl TupleBuffer + where T: HomogeneousTuple +{ + fn new(buf: T::Buffer) -> Self { + TupleBuffer { + cur: 0, + buf, + } + } +} + +impl Iterator for TupleBuffer + where T: HomogeneousTuple +{ + type Item = T::Item; + + fn next(&mut self) -> Option { + 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) { + 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_else(|| buffer.len()) + }; + (len, Some(len)) + } +} + +impl ExactSizeIterator for TupleBuffer + where T: HomogeneousTuple +{ +} + +/// An iterator that groups the items in tuples of a specific size. +/// +/// See [`.tuples()`](crate::Itertools::tuples) for more information. +#[derive(Clone, Debug)] +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +pub struct Tuples + where I: Iterator, + T: HomogeneousTuple +{ + iter: Fuse, + buf: T::Buffer, +} + +/// Create a new tuples iterator. +pub fn tuples(iter: I) -> Tuples + where I: Iterator, + T: HomogeneousTuple +{ + Tuples { + iter: iter.fuse(), + buf: Default::default(), + } +} + +impl Iterator for Tuples + where I: Iterator, + T: HomogeneousTuple +{ + type Item = T; + + fn next(&mut self) -> Option { + T::collect_from_iter(&mut self.iter, &mut self.buf) + } +} + +impl Tuples + where I: Iterator, + T: HomogeneousTuple +{ + /// Return a buffer with the produced items that was not enough to be grouped in a tuple. + /// + /// ``` + /// use itertools::Itertools; + /// + /// let mut iter = (0..5).tuples(); + /// assert_eq!(Some((0, 1, 2)), iter.next()); + /// assert_eq!(None, iter.next()); + /// itertools::assert_equal(vec![3, 4], iter.into_buffer()); + /// ``` + pub fn into_buffer(self) -> TupleBuffer { + TupleBuffer::new(self.buf) + } +} + + +/// An iterator over all contiguous windows that produces tuples of a specific size. +/// +/// See [`.tuple_windows()`](crate::Itertools::tuple_windows) for more +/// information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +#[derive(Clone, Debug)] +pub struct TupleWindows + where I: Iterator, + T: HomogeneousTuple +{ + iter: I, + last: Option, +} + +/// Create a new tuple windows iterator. +pub fn tuple_windows(mut iter: I) -> TupleWindows + where I: Iterator, + T: HomogeneousTuple, + T::Item: Clone +{ + use std::iter::once; + + let mut last = None; + if T::num_items() != 1 { + // put in a duplicate item in front of the tuple; this simplifies + // .next() function. + if let Some(item) = iter.next() { + let iter = once(item.clone()).chain(once(item)).chain(&mut iter); + last = T::collect_from_iter_no_buf(iter); + } + } + + TupleWindows { + last, + iter, + } +} + +impl Iterator for TupleWindows + where I: Iterator, + T: HomogeneousTuple + Clone, + T::Item: Clone +{ + type Item = T; + + fn next(&mut self) -> Option { + if T::num_items() == 1 { + return T::collect_from_iter_no_buf(&mut self.iter) + } + if let Some(ref mut last) = self.last { + if let Some(new) = self.iter.next() { + last.left_shift_push(new); + return Some(last.clone()); + } + } + None + } +} + +impl FusedIterator for TupleWindows + where I: FusedIterator, + T: HomogeneousTuple + Clone, + T::Item: Clone +{} + +/// An iterator over all windows,wrapping back to the first elements when the +/// window would otherwise exceed the length of the iterator, producing tuples +/// of a specific size. +/// +/// See [`.circular_tuple_windows()`](crate::Itertools::circular_tuple_windows) for more +/// information. +#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] +#[derive(Debug)] +pub struct CircularTupleWindows + where I: Iterator + Clone, + T: TupleCollect + Clone +{ + iter: Take, T>>, + phantom_data: PhantomData +} + +pub fn circular_tuple_windows(iter: I) -> CircularTupleWindows + where I: Iterator + Clone + ExactSizeIterator, + T: TupleCollect + Clone, + T::Item: Clone +{ + let len = iter.len(); + let iter = tuple_windows(iter.cycle()).take(len); + + CircularTupleWindows { + iter, + phantom_data: PhantomData{} + } +} + +impl Iterator for CircularTupleWindows + where I: Iterator + Clone, + T: TupleCollect + Clone, + T::Item: Clone +{ + type Item = T; + + fn next(&mut self) -> Option { + self.iter.next() + } +} + +pub trait TupleCollect: Sized { + type Item; + type Buffer: Default + AsRef<[Option]> + AsMut<[Option]>; + + fn collect_from_iter(iter: I, buf: &mut Self::Buffer) -> Option + where I: IntoIterator; + + fn collect_from_iter_no_buf(iter: I) -> Option + where I: IntoIterator; + + fn num_items() -> usize; + + fn left_shift_push(&mut self, item: Self::Item); +} + +macro_rules! count_ident{ + () => {0}; + ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)}; +} +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,) => {}; // stop + ($dummy:ident, $($Y:ident,)*) => ( + impl_tuple_collect!($($Y,)*); + impl TupleCollect for ($(ignore_ident!($Y, A),)*) { + type Item = A; + type Buffer = [Option; count_ident!($($Y,)*) - 1]; + + #[allow(unused_assignments, unused_mut)] + fn collect_from_iter(iter: I, buf: &mut Self::Buffer) -> Option + where I: IntoIterator + { + 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(iter: I) -> Option + where I: IntoIterator + { + 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,); -- cgit v1.2.3