intrex 0.1.1

//! Iterators for [`ListAccessor`]
use super::*;

/// Iteration
impl<'head, 'pool, Index, Pool, MapLink, Element> ListAccessor<'head, 'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    /// Iterate over `(Index, &Element)`.
    #[inline]
    pub fn iter(&self) -> Iter<'pool, Index, Pool, &MapLink> {
        Iter {
            indices: self.indices(),
        }
    }

    /// Iterate over `(Index, &Element)` in a given range.
    #[inline]
    pub fn iter_range(
        &self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> Iter<'pool, Index, Pool, &MapLink> {
        Iter {
            indices: self.indices_range(range),
        }
    }

    /// Iterate over `(Index, &Element)` in a given range, consuming `self`.
    #[inline]
    pub fn into_iter_range(
        self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> Iter<'pool, Index, Pool, MapLink> {
        Iter {
            indices: self.into_indices_range(range),
        }
    }

    /// Iterate over `Index`.
    #[inline]
    pub fn indices(&self) -> Indices<'pool, Index, Pool, &MapLink> {
        Indices {
            pool: self.pool,
            map_link: &self.map_link,
            range: self.head.first.clone().map(|x| [x.clone(), x]),
        }
    }

    /// Iterate over `Index`, consuming `self`.
    #[inline]
    pub fn into_indices(self) -> Indices<'pool, Index, Pool, MapLink> {
        Indices {
            pool: self.pool,
            map_link: self.map_link,
            range: self.head.first.clone().map(|x| [x.clone(), x]),
        }
    }

    /// Iterate over `Index` in a given range.
    #[inline]
    pub fn indices_range(
        &self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> Indices<'pool, Index, Pool, &MapLink> {
        let (range, _) = resolve_range(range, |i| link!(self, i).clone(), self.head.first.clone());
        Indices {
            pool: self.pool,
            range: range.map(|[start, end]| [start, link!(self, end).next.clone()]),
            map_link: &self.map_link,
        }
    }

    /// Iterate over `Index` in a given range, consuming `self`.
    #[inline]
    pub fn into_indices_range(
        self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> Indices<'pool, Index, Pool, MapLink> {
        let (range, _) = resolve_range(range, |i| link!(self, i).clone(), self.head.first.clone());
        Indices {
            pool: self.pool,
            range: range.map(|[start, end]| [start, link!(self, end).next.clone()]),
            map_link: self.map_link,
        }
    }

    /// Iterate over `&Element`.
    #[inline]
    pub fn values(&self) -> Values<'pool, Index, Pool, &MapLink> {
        Values {
            indices: self.indices(),
        }
    }

    /// Iterate over `&Element`, consuming `self`.
    #[inline]
    pub fn into_values(self) -> Values<'pool, Index, Pool, MapLink> {
        Values {
            indices: self.into_indices(),
        }
    }

    /// Iterate over `&Element` in a given range.
    #[inline]
    pub fn values_range(
        &self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> Values<'pool, Index, Pool, &MapLink> {
        Values {
            indices: self.indices_range(range),
        }
    }

    /// Iterate over `&Element` in a given range, consuming `self`.
    #[inline]
    pub fn into_values_range(
        self,
        range: impl ops::RangeBounds<Option<Index>>,
    ) -> Values<'pool, Index, Pool, MapLink> {
        Values {
            indices: self.into_indices_range(range),
        }
    }
}

impl<'head, 'pool, Index, Pool, MapLink, Element> IntoIterator
    for ListAccessor<'head, 'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    type Item = (Index, &'pool Element);
    type IntoIter = Iter<'pool, Index, Pool, MapLink>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        Iter {
            indices: self.into_indices(),
        }
    }
}

impl<'a, 'head, 'pool, Index, Pool, MapLink, Element> IntoIterator
    for &'a ListAccessor<'head, 'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    type Item = (Index, &'pool Element);
    type IntoIter = Iter<'pool, Index, Pool, &'a MapLink>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

/// An iterator over the indices and elements of [`ListAccessor`].
#[derive(Debug)]
pub struct Iter<'pool, Index, Pool: ?Sized, MapLink> {
    indices: Indices<'pool, Index, Pool, MapLink>,
}

impl<'pool, Index, Pool, MapLink> Clone for Iter<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized,
    MapLink: Clone,
    Index: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        Self {
            indices: self.indices.clone(),
        }
    }
}

impl<'pool, Index, Pool, MapLink> Default for Iter<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized,
    &'pool Pool: Default,
    MapLink: Default,
{
    #[inline]
    fn default() -> Self {
        Self {
            indices: <_>::default(),
        }
    }
}

impl<'pool, Index, Pool, MapLink, Element> Iterator for Iter<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    type Item = (Index, &'pool Element);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.indices
            .next()
            .map(|i| (i.clone(), self.indices.pool.index(i)))
    }
}

impl<'pool, Index, Pool, MapLink, Element> DoubleEndedIterator for Iter<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.indices
            .next_back()
            .map(|i| (i.clone(), self.indices.pool.index(i)))
    }
}

impl<'pool, Index, Pool, MapLink, Element> core::iter::FusedIterator
    for Iter<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
}

/// An iterator over the elements of [`ListAccessor`].
#[derive(Debug)]
pub struct Values<'pool, Index, Pool: ?Sized, MapLink> {
    indices: Indices<'pool, Index, Pool, MapLink>,
}

impl<'pool, Index, Pool, MapLink> Clone for Values<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized,
    MapLink: Clone,
    Index: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        Self {
            indices: self.indices.clone(),
        }
    }
}

impl<'pool, Index, Pool, MapLink> Default for Values<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized,
    &'pool Pool: Default,
    MapLink: Default,
{
    #[inline]
    fn default() -> Self {
        Self {
            indices: <_>::default(),
        }
    }
}

impl<'pool, Index, Pool, MapLink, Element> Iterator for Values<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    type Item = &'pool Element;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.indices.next().map(|i| self.indices.pool.index(i))
    }
}

impl<'pool, Index, Pool, MapLink, Element> DoubleEndedIterator
    for Values<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.indices.next_back().map(|i| self.indices.pool.index(i))
    }
}

impl<'pool, Index, Pool, MapLink, Element> core::iter::FusedIterator
    for Values<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
}

/// An iterator over the element indices of [`ListAccessor`].
#[derive(Debug)]
pub struct Indices<'pool, Index, Pool: ?Sized, MapLink> {
    pool: &'pool Pool,
    map_link: MapLink,
    range: Option<[Index; 2]>,
}

impl<'pool, Index, Pool, MapLink> Clone for Indices<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized,
    MapLink: Clone,
    Index: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        Self {
            pool: self.pool,
            map_link: self.map_link.clone(),
            range: self.range.clone(),
        }
    }
}

impl<'pool, Index, Pool, MapLink> Default for Indices<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized,
    &'pool Pool: Default,
    MapLink: Default,
{
    #[inline]
    fn default() -> Self {
        Self {
            pool: <_>::default(),
            map_link: <_>::default(),
            range: None,
        }
    }
}

impl<'pool, Index, Pool, MapLink, Element> Iterator for Indices<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    type Item = Index;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if let Some([start, end]) = self.range.take() {
            let new_start = link!(self, start.clone()).next.clone();
            if new_start != end {
                self.range = Some([new_start, end]);
            }
            Some(start)
        } else {
            None
        }
    }
}

impl<'pool, Index, Pool, MapLink, Element> DoubleEndedIterator
    for Indices<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        if let Some([start, end]) = self.range.take() {
            let new_end = link!(self, end.clone()).prev.clone();
            if new_end != start {
                self.range = Some([start, new_end.clone()]);
            }
            Some(new_end)
        } else {
            None
        }
    }
}

impl<'pool, Index, Pool, MapLink, Element> core::iter::FusedIterator
    for Indices<'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;
    use std::{borrow::ToOwned, vec::Vec};

    use super::*;
    use crate::list::tests::push;

    #[test]
    fn iter() {
        for len in 0..4 {
            let pool: Vec<_> = (0..len)
                .map(|i| {
                    Some(Link {
                        prev: (i + len - 1) % len,
                        next: (i + 1) % len,
                    })
                })
                .collect();
            let head = Head {
                first: (len != 0).then_some(0),
            };
            let accessor = head.accessor(&pool, |x| x);

            assert_eq!(
                accessor.iter().map(|x| x.0).collect::<Vec<_>>(),
                (0..len).collect::<Vec<_>>()
            );

            assert_eq!(
                accessor.indices().collect::<Vec<_>>(),
                (0..len).collect::<Vec<_>>()
            );

            assert_eq!(
                accessor.iter().rev().map(|x| x.0).collect::<Vec<_>>(),
                (0..len).rev().collect::<Vec<_>>()
            );
        }
    }

    #[proptest::property_test]
    fn pt_iter_range(elems: Vec<u8>, [start, end]: [prop::sample::Index; 2]) {
        let mut pool: Vec<(u8, Option<Link>)> = Vec::new();
        let mut head = Head::new();

        for &value in &elems {
            let ptr = push(&mut pool, (value, None));
            head.accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
                .push_back(ptr);
        }

        let start = start.index(elems.len() + 1);
        let end = end.index(elems.len() + 1 - start) + start;

        let [start_ind, end_ind] = [start, end].map(|i| (i < elems.len()).then_some(i));

        let expected = elems[start..end].to_owned();

        let got: Vec<u8> = head
            .accessor(&pool, |(_, link)| link)
            .values_range(start_ind..end_ind)
            .map(|&(value, _)| value)
            .collect();

        assert_eq!(got, expected);
    }
}