astack/

iter.rs

//! This library contains tools used for iterating over a Stack.

use core::{fmt, iter, mem, ptr};

/// A helper struct used to iterate over the items contained in a [`Stack`][crate::Stack]
/// from top to bottom with the syntax `for var in expr { /* code */ }`.
///
/// Being a LIFO system, the [`next`][StackIntoIter::next] method will start from
/// the top and move to the bottom. If you want to iterate in the opposite direction,
/// this struct implements [`DoubleEndedIterator`] as well. Moreover, if you want to
/// [`collect`][Iterator::collect] a [`StackIntoIter`] into a `Vec`, keep
/// in mind that the [`StackIntoIter`] advances from top to bottom: therefore, you
/// will end up with a `Vec` with the items in the inverse order of the original
/// [`Stack`][crate::Stack].
///
/// # Examples
///
/// ```rust
/// use astack::stack;
///
/// let items = stack!{ [i32; 5] = [10, 20, 30, 40, 50] };
///
/// let mut it = items.into_iter();
///
/// assert_eq!(it.next(), Some(50));
/// assert_eq!(it.next_back(), Some(10));
/// assert_eq!(it.collect::<Vec<_>>(), vec![40, 30, 20]);
/// ```
pub struct StackIntoIter<T, const N: usize> {
    items: [mem::MaybeUninit<T>; N],
    top_len: usize,
    bottom_len: usize,
}

impl<T, const N: usize> StackIntoIter<T, N> {
    /// Create a new [`StackIntoIter`].
    #[inline]
    pub(super) const unsafe fn new(items: [mem::MaybeUninit<T>; N], top_len: usize) -> Self {
        // Safety: it is up to the caller (us) to use valid `items` and `top_len`.
        Self {
            items,
            top_len,
            bottom_len: 0,
        }
    }

    /// Implementation of [`Iterator::next`] for [`StackIntoIter`].
    /// It is the same as `Stack::pop`.
    #[inline]
    fn pop_top(&mut self) -> Option<T> {
        debug_assert!(self.bottom_len <= self.top_len);
        if self.top_len == self.bottom_len {
            None
        } else {
            self.top_len -= 1;
            Some(unsafe { ptr::read(self.items.as_ptr().add(self.top_len)).assume_init() })
        }
    }

    /// Implementation of [`DoubleEndedIterator::next_back`] for [`StackIntoIter`].
    #[inline]
    fn pop_bottom(&mut self) -> Option<T> {
        debug_assert!(self.bottom_len <= self.top_len);

        if self.bottom_len == self.top_len {
            None
        } else {
            // bottom_len already points to the value, in contrast with
            // top_len, which points to the next empty slot
            let result =
                Some(unsafe { ptr::read(self.items.as_ptr().add(self.bottom_len)).assume_init() });
            self.bottom_len += 1;
            result
        }
    }
}

impl<T, const N: usize> Iterator for StackIntoIter<T, N> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.pop_top()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.bottom_len, Some(self.top_len))
    }
}

impl<T, const N: usize> iter::DoubleEndedIterator for StackIntoIter<T, N> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.pop_bottom()
    }
}

impl<T, const N: usize> Default for StackIntoIter<T, N> {
    #[inline]
    fn default() -> Self {
        Self {
            top_len: 0,
            bottom_len: 0,

            // SAFETY: Same as `Stack::new()`
            items: unsafe { mem::MaybeUninit::uninit().assume_init() },
        }
    }
}

impl<T, const N: usize> Clone for StackIntoIter<T, N>
where
    T: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        // The good thing about this method is that we only iterate for
        // the number of remaining items.
        //
        // Safety: this comes from `Stack::clone()`.
        unsafe {
            let mut items = mem::MaybeUninit::<[mem::MaybeUninit<T>; N]>::uninit().assume_init();
            self.items
                .get_unchecked(self.bottom_len..self.top_len)
                .iter()
                .zip(items.get_unchecked_mut(self.bottom_len..self.top_len))
                .for_each(|(src, dst)| {
                    dst.write(src.assume_init_ref().clone());
                });
            Self {
                items,
                top_len: self.top_len,
                bottom_len: self.bottom_len,
            }
        }
    }
}

impl<T, const N: usize> Drop for StackIntoIter<T, N> {
    #[inline]
    fn drop(&mut self) {
        debug_assert!(self.bottom_len <= self.top_len);

        // Safety: Same as `Stack::drop()`
        unsafe {
            let items = self.items.get_unchecked_mut(self.bottom_len..self.top_len)
                as *mut [mem::MaybeUninit<T>] as *mut [T];
            ptr::drop_in_place(items);
        }
    }
}

impl<T, const N: usize> fmt::Debug for StackIntoIter<T, N>
where
    T: fmt::Debug,
{
    #[inline]
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut list = f.debug_list();

        unsafe {
            list.entries(
                self.items
                    .get_unchecked(self.bottom_len..self.top_len)
                    .iter()
                    .map(|item| item.assume_init_ref()),
            );
        }

        list.finish()
    }
}

impl<T, const N: usize> iter::FusedIterator for StackIntoIter<T, N> {}

impl<T, const N: usize, const M: usize> PartialEq<StackIntoIter<T, M>> for StackIntoIter<T, N>
where
    T: PartialEq,
{
    #[inline]
    fn eq(&self, other: &StackIntoIter<T, M>) -> bool {
        unsafe {
            let items1 = self.items.get_unchecked(self.bottom_len..self.top_len)
                as *const [mem::MaybeUninit<T>] as *const [T];
            let items2 = other.items.get_unchecked(other.bottom_len..other.top_len)
                as *const [mem::MaybeUninit<T>] as *const [T];
            *items1 == *items2
        }
    }
}

// impl<I: IntoIterator<Item = T>, T, const N: usize> TryFrom<I> for Stack<T, N> {
//     type Error = StackError;

//     fn try_from(iter: I) -> Result<Self, Self::Error> {}
// }