array-linked-list 0.2.3

use crate::{ArrayLinkedList, LinkedListNode, id::Id};

impl<T> ArrayLinkedList<T> {
    /// Returns a borrowing iterator over its elements.
    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> {
        Values(Indexed::new(self))
    }

    /// Returns a mutable borrowing iterator over its elements.
    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> {
        ValuesMut(IndexedMut::new(self))
    }

    /// Returns a borrowing iterator over its indexed elements.
    pub fn indexed(&self) -> impl DoubleEndedIterator<Item = (usize, &T)> {
        Indexed::new(self)
    }

    /// Returns a mutable borrowing iterator over its indexed elements.
    pub fn indexed_mut(&mut self) -> impl DoubleEndedIterator<Item = (usize, &mut T)> {
        IndexedMut::new(self)
    }

    /// Returns a borrowing iterator over its indices.
    pub fn indices(&self) -> impl DoubleEndedIterator<Item = usize> + '_ {
        Indices(Indexed::new(self))
    }

    /// Returns a borrowing iterator over its elements, starting after the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn iter_after(&self, index: usize) -> impl DoubleEndedIterator<Item = &T> {
        Values(Indexed::after(self, index))
    }

    /// Returns a mutable borrowing iterator over its elements, starting after the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn iter_mut_after(&mut self, index: usize) -> impl DoubleEndedIterator<Item = &mut T> {
        ValuesMut(IndexedMut::after(self, index))
    }

    /// Returns a borrowing iterator over its indexed elements, starting after the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn indexed_after(&self, index: usize) -> impl DoubleEndedIterator<Item = (usize, &T)> {
        Indexed::after(self, index)
    }

    /// Returns a mutable borrowing iterator over its indexed elements, starting after the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn indexed_mut_after(
        &mut self,
        index: usize,
    ) -> impl DoubleEndedIterator<Item = (usize, &mut T)> {
        IndexedMut::after(self, index)
    }

    /// Returns a borrowing iterator over its indices, starting after the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn indices_after(&self, index: usize) -> impl DoubleEndedIterator<Item = usize> + '_ {
        Indices(Indexed::after(self, index))
    }

    /// Returns a borrowing iterator over its elements, ending before the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn iter_before(&self, index: usize) -> impl DoubleEndedIterator<Item = &T> {
        Values(Indexed::before(self, index))
    }

    /// Returns a mutable borrowing iterator over its elements, ending before the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn iter_mut_before(&mut self, index: usize) -> impl DoubleEndedIterator<Item = &mut T> {
        ValuesMut(IndexedMut::before(self, index))
    }

    /// Returns a borrowing iterator over its indexed elements, ending before the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn indexed_before(&self, index: usize) -> impl DoubleEndedIterator<Item = (usize, &T)> {
        Indexed::before(self, index)
    }

    /// Returns a mutable borrowing iterator over its indexed elements, ending before the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn indexed_mut_before(
        &mut self,
        index: usize,
    ) -> impl DoubleEndedIterator<Item = (usize, &mut T)> {
        IndexedMut::before(self, index)
    }

    /// Returns a borrowing iterator over its indices, ending before the element at the specified index.
    ///
    /// # Panics
    ///
    /// Panics if index >= capacity
    pub fn indices_before(&self, index: usize) -> impl DoubleEndedIterator<Item = usize> + '_ {
        Indices(Indexed::before(self, index))
    }

    /// Returns an owning iterator returning its indexed elements.
    pub fn into_indexed(self) -> impl DoubleEndedIterator<Item = (usize, T)> {
        IntoIndexed(self)
    }

    /// Returns an owning iterator returning its indices.
    pub fn into_indices(self) -> impl DoubleEndedIterator<Item = usize> {
        IntoIndices(IntoIndexed(self))
    }
}

struct Indexed<'a, T> {
    front_index: Id,
    back_index: Id,
    array: &'a ArrayLinkedList<T>,
}

impl<'a, T> Indexed<'a, T> {
    fn empty(array: &'a ArrayLinkedList<T>) -> Self {
        Self {
            front_index: Id::default(),
            back_index: Id::default(),
            array,
        }
    }

    fn new(array: &'a ArrayLinkedList<T>) -> Self {
        Self {
            front_index: array.first_index,
            back_index: array.last_index,
            array,
        }
    }

    fn after(array: &'a ArrayLinkedList<T>, prev_index: usize) -> Self {
        let element = &array.elements[prev_index];
        if element.data.is_some() {
            Self {
                front_index: element.next_index,
                back_index: array.last_index,
                array,
            }
        } else {
            Self::empty(array)
        }
    }

    fn before(array: &'a ArrayLinkedList<T>, next_index: usize) -> Self {
        let element = &array.elements[next_index];
        if element.data.is_some() {
            Self {
                front_index: array.first_index,
                back_index: element.prev_index,
                array,
            }
        } else {
            Self::empty(array)
        }
    }
}

struct IndexedMut<'a, T> {
    front_index: Id,
    back_index: Id,
    elements: &'a mut [LinkedListNode<T>],
}

impl<'a, T> IndexedMut<'a, T> {
    fn empty(array: &'a mut ArrayLinkedList<T>) -> Self {
        Self {
            front_index: Id::default(),
            back_index: Id::default(),
            elements: &mut array.elements,
        }
    }

    fn new(array: &'a mut ArrayLinkedList<T>) -> Self {
        Self {
            front_index: array.first_index,
            back_index: array.last_index,
            elements: &mut array.elements,
        }
    }

    fn after(array: &'a mut ArrayLinkedList<T>, prev_index: usize) -> Self {
        let last_index = array.last_index;
        let element = &array.elements[prev_index];
        if element.data.is_some() {
            let front_index = element.next_index;
            Self {
                front_index,
                back_index: last_index,
                elements: &mut array.elements,
            }
        } else {
            Self::empty(array)
        }
    }

    fn before(array: &'a mut ArrayLinkedList<T>, next_index: usize) -> Self {
        let first_index = array.first_index;
        let element = &array.elements[next_index];
        if element.data.is_some() {
            let back_index = element.prev_index;
            Self {
                front_index: first_index,
                back_index,
                elements: &mut array.elements,
            }
        } else {
            Self::empty(array)
        }
    }
}

struct Indices<'a, T>(Indexed<'a, T>);

/// Borrowing iterator over values of the linked array.
pub struct Values<'a, T>(Indexed<'a, T>);

/// Mutable borrowing iterator over values of the linked array.
pub struct ValuesMut<'a, T>(IndexedMut<'a, T>);

impl<'a, T> Iterator for Indexed<'a, T> {
    type Item = (usize, &'a T);
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let index = self.front_index.index()?;

        let element = &self.array.elements[index];
        if self.front_index == self.back_index {
            self.front_index = Id::default();
            self.back_index = Id::default();
        } else {
            self.front_index = element.next_index;
        }
        Some((index, unsafe { element.data.as_ref().unwrap_unchecked() }))
    }
}

impl<T> DoubleEndedIterator for Indexed<'_, T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        let index = self.back_index.index()?;

        let element = &self.array.elements[index];
        if self.front_index == self.back_index {
            self.front_index = Id::default();
            self.back_index = Id::default();
        } else {
            self.back_index = element.prev_index;
        }
        Some((index, unsafe { element.data.as_ref().unwrap_unchecked() }))
    }
}

impl<'a, T> Iterator for IndexedMut<'a, T> {
    type Item = (usize, &'a mut T);
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let index = self.front_index.index()?;

        let element: *mut LinkedListNode<T> = &raw mut self.elements[index];
        if self.front_index == self.back_index {
            self.front_index = Id::default();
            self.back_index = Id::default();
        } else {
            self.front_index = unsafe { (*element).next_index };
        }
        Some((index, unsafe {
            (*element).data.as_mut().unwrap_unchecked()
        }))
    }
}

impl<T> DoubleEndedIterator for IndexedMut<'_, T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        let index = self.back_index.index()?;

        let element: *mut LinkedListNode<T> = &raw mut self.elements[index];
        if self.front_index == self.back_index {
            self.front_index = Id::default();
            self.back_index = Id::default();
        } else {
            self.back_index = unsafe { (*element).prev_index };
        }
        Some((index, unsafe {
            (*element).data.as_mut().unwrap_unchecked()
        }))
    }
}

impl<T> Iterator for Indices<'_, T> {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(index, _)| index)
    }
}

impl<T> DoubleEndedIterator for Indices<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|(index, _)| index)
    }
}

impl<'a, T> Iterator for Values<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, value)| value)
    }
}

impl<T> DoubleEndedIterator for Values<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|(_, value)| value)
    }
}

impl<'a, T> Iterator for ValuesMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, value)| value)
    }
}

impl<T> DoubleEndedIterator for ValuesMut<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|(_, value)| value)
    }
}

impl<'a, T> IntoIterator for &'a ArrayLinkedList<T> {
    type Item = &'a T;
    type IntoIter = Values<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        Values(Indexed::new(self))
    }
}

impl<'a, T> IntoIterator for &'a mut ArrayLinkedList<T> {
    type Item = &'a mut T;
    type IntoIter = ValuesMut<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        ValuesMut(IndexedMut::new(self))
    }
}

struct IntoIndexed<T>(ArrayLinkedList<T>);
struct IntoIndices<T>(IntoIndexed<T>);

/// Owning iterator over values of the linked array.
pub struct IntoValues<T>(IntoIndexed<T>);

impl<T> Iterator for IntoIndexed<T> {
    type Item = (usize, T);
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let index = self.0.first_index.index()?;

        let element = &mut self.0.elements[index];
        if self.0.first_index == self.0.last_index {
            self.0.first_index = Id::default();
            self.0.last_index = Id::default();
        } else {
            self.0.first_index = element.next_index;
        }
        Some((index, unsafe { element.data.take().unwrap_unchecked() }))
    }
}

impl<T> DoubleEndedIterator for IntoIndexed<T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        let index = self.0.last_index.index()?;

        let element = &mut self.0.elements[index];
        if self.0.first_index == self.0.last_index {
            self.0.first_index = Id::default();
            self.0.last_index = Id::default();
        } else {
            self.0.last_index = element.prev_index;
        }
        Some((index, unsafe { element.data.take().unwrap_unchecked() }))
    }
}

impl<T> Iterator for IntoIndices<T> {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(index, _)| index)
    }
}

impl<T> DoubleEndedIterator for IntoIndices<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|(index, _)| index)
    }
}

impl<T> Iterator for IntoValues<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, value)| value)
    }
}

impl<T> DoubleEndedIterator for IntoValues<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|(_, value)| value)
    }
}

impl<T> IntoIterator for ArrayLinkedList<T> {
    type Item = T;
    type IntoIter = IntoValues<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoValues(IntoIndexed(self))
    }
}