circular_doubly_linked_list 0.1.0

//! Iterator module providing forward and backward iteration over the list.
//!
//! This module contains three iterator types for traversing a `CircularDoublyLinkedList`:
//! - [`Iter`]: Immutable reference iterator (yields `&T`)
//! - [`IterMut`]: Mutable reference iterator (yields `&mut T`)
//! - [`IntoIter`]: Owning iterator that consumes the list (yields `T`)

use core::marker::PhantomData;
use core::ptr::NonNull;

use crate::node::Node;

/// An immutable iterator over a `CircularDoublyLinkedList`.
///
/// This iterator yields immutable references (`&T`) to the elements in the list,
/// traversing from front (head) to back (tail) in order.
///
/// # Type Parameters
///
/// * `'a` - The lifetime of the references yielded (tied to the list borrow)
/// * `T` - The type of elements in the list
///
/// # Lifetime
///
/// The iterator borrows the list for its lifetime. The list cannot be modified
/// (except through interior mutability) while this iterator exists.
///
/// # Examples
///
/// ```rust
/// use circular_doubly_linked_list::CircularDoublyLinkedList;
///
/// let mut list = CircularDoublyLinkedList::new();
/// list.push_back(1);
/// list.push_back(2);
/// list.push_back(3);
///
/// // Iterate immutably
/// for item in list.iter() {
///     println!("{}", item);
/// }
/// // Output: 1, 2, 3
///
/// // Can still use list after iteration
/// assert_eq!(list.len(), 3);
/// ```
pub struct Iter<'a, T> {
    /// Current node pointer (next element to yield).
    current: Option<NonNull<Node<T>>>,
    /// Current node pointer (next element to yield from back).
    back: Option<NonNull<Node<T>>>,
    /// Number of remaining elements to iterate.
    remaining: usize,
    /// Phantom data to tie the lifetime to the borrowed list.
    _marker: PhantomData<&'a T>,
}

impl<'a, T> Iter<'a, T> {
    /// Creates a new immutable iterator.
    ///
    /// # Parameters
    ///
    /// * `head` - The head node of the list (starting point for iteration)
    /// * `length` - The number of elements in the list (used for bounds)
    ///
    /// # Returns
    ///
    /// Returns a new `Iter<'a, T>` instance ready to iterate from the head.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `head` accurately represents the list state
    /// and that `length` matches the actual number of nodes in the circular chain.
    pub(crate) fn new(head: Option<NonNull<Node<T>>>, length: usize) -> Self {
        let back = if length > 0 {
            head.map(|h| unsafe { Node::get_prev(h) })
        } else {
            None
        };

        Self {
            current: head,
            back,
            remaining: length,
            _marker: PhantomData,
        }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    /// Advances the iterator and returns the next immutable reference.
    ///
    /// # Returns
    ///
    /// - `Some(&'a T)` - Reference to the next element if available
    /// - `None` - When all elements have been iterated
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// let mut iter = list.iter();
    /// assert_eq!(iter.next(), Some(&1));
    /// assert_eq!(iter.next(), Some(&2));
    /// assert_eq!(iter.next(), None);
    /// ```
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }

        unsafe {
            let current = self.current.unwrap_unchecked();
            let data = Node::data_ref(current);

            self.current = Some(Node::get_next(current));
            self.remaining -= 1;

            Some(data)
        }
    }

    /// Returns the exact remaining length of the iterator.
    ///
    /// # Returns
    ///
    /// Returns a tuple `(min, max)` where both values equal the remaining count.
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<'a, T> ExactSizeIterator for Iter<'a, T> {
    /// Returns the exact number of remaining elements.
    ///
    /// # Returns
    ///
    /// Returns the number of elements yet to be iterated.
    fn len(&self) -> usize {
        self.remaining
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    /// Advances the iterator from the back, returning the last element.
    ///
    /// This enables reverse iteration using `.rev()` or `next_back()`.
    ///
    /// # Returns
    ///
    /// - `Some(&'a T)` - Reference to the back element if available
    /// - `None` - When all elements have been iterated
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    /// list.push_back(3);
    ///
    /// let vec: Vec<_> = list.iter().rev().copied().collect();
    /// assert_eq!(vec, [3, 2, 1]);
    /// ```
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }

        unsafe {
            let back = self.back.unwrap_unchecked();
            let data = Node::data_ref(back);

            self.back = Some(Node::get_prev(back));
            self.remaining -= 1;

            Some(data)
        }
    }
}

impl<'a, T> Clone for Iter<'a, T> {
    /// Creates a clone of the iterator.
    ///
    /// # Returns
    ///
    /// Returns a new `Iter` with the same position and remaining count.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// let mut iter1 = list.iter();
    /// let _ = iter1.next(); // Advance iter1
    ///
    /// let mut iter2 = iter1.clone();
    /// // iter2 starts at the same position as iter1
    /// ```
    fn clone(&self) -> Self {
        Self {
            current: self.current,
            back: self.back,
            remaining: self.remaining,
            _marker: PhantomData,
        }
    }
}

/// A mutable iterator over a `CircularDoublyLinkedList`.
///
/// This iterator yields mutable references (`&mut T`) to the elements in the list,
/// traversing from front (head) to back (tail) in order.
///
/// # Type Parameters
///
/// * `'a` - The lifetime of the references yielded (tied to the list borrow)
/// * `T` - The type of elements in the list
///
/// # Lifetime
///
/// The iterator mutably borrows the list for its lifetime. The list cannot be
/// accessed through other means while this iterator exists (Rust's borrowing rules).
///
/// # Examples
///
/// ```rust
/// use circular_doubly_linked_list::CircularDoublyLinkedList;
///
/// let mut list = CircularDoublyLinkedList::new();
/// list.push_back(1);
/// list.push_back(2);
/// list.push_back(3);
///
/// // Iterate mutably and modify elements
/// for item in list.iter_mut() {
///     *item *= 2;
/// }
///
/// let vec: Vec<_> = list.iter().copied().collect();
/// assert_eq!(vec, [2, 4, 6]);
/// ```
pub struct IterMut<'a, T> {
    /// Current node pointer (next element to yield from front).
    current: Option<NonNull<Node<T>>>,
    /// Current node pointer (next element to yield from back).
    back: Option<NonNull<Node<T>>>,
    /// Number of remaining elements to iterate
    remaining: usize,
    /// Phantom data to tie the lifetime to the mutably borrowed list.
    _marker: PhantomData<&'a mut T>,
}

impl<'a, T> IterMut<'a, T> {
    /// Creates a new mutable iterator.
    ///
    /// # Parameters
    ///
    /// * `head` - The head node of the list (starting point for iteration)
    /// * `length` - The number of elements in the list (used for bounds)
    ///
    /// # Returns
    ///
    /// Returns a new `IterMut<'a, T>` instance ready to iterate from the head.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `head` accurately represents the list state
    /// and that `length` matches the actual number of nodes in the circular chain.
    pub(crate) fn new(head: Option<NonNull<Node<T>>>, length: usize) -> Self {
        let back = if length > 0 {
            head.map(|h| unsafe { Node::get_prev(h) })
        } else {
            None
        };

        Self {
            current: head,
            back,
            remaining: length,
            _marker: PhantomData,
        }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    /// Advances the iterator and returns the next mutable reference.
    ///
    /// # Returns
    ///
    /// - `Some(&'a mut T)` - Mutable reference to the next element if available
    /// - `None` - When all elements have been iterated
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// let mut iter = list.iter_mut();
    /// if let Some(first) = iter.next() {
    ///     *first = 100;
    /// }
    /// ```
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }

        unsafe {
            let current = self.current.unwrap_unchecked();
            let data = Node::data_mut(current);

            self.current = Some(Node::get_next(current));
            self.remaining -= 1;

            Some(data)
        }
    }

    /// Returns the exact remaining length of the iterator.
    ///
    /// # Returns
    ///
    /// Returns a tuple `(min, max)` where both values equal the remaining count.
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
    /// Returns the exact number of remaining elements.
    ///
    /// # Returns
    ///
    /// Returns the number of elements yet to be iterated.
    fn len(&self) -> usize {
        self.remaining
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    /// Advances the iterator from the back, returning the last element.
    ///
    /// # Returns
    ///
    /// - `Some(&'a mut T)` - Mutable reference to the back element if available
    /// - `None` - When all elements have been iterated
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }

        unsafe {
            let back = self.back.unwrap_unchecked();
            let data = Node::data_mut(back);

            self.back = Some(Node::get_prev(back));
            self.remaining -= 1;

            Some(data)
        }
    }
}

/// An owning iterator over a `CircularDoublyLinkedList`.
///
/// This iterator consumes the list and yields owned values (`T`). After iteration
/// completes, the original list is destroyed and cannot be used.
///
/// # Type Parameters
///
/// * `T` - The type of elements in the list
///
/// # Ownership
///
/// This iterator takes ownership of the list. Each call to `next()` removes and
/// returns one element. The `Drop` implementation ensures any remaining elements
/// are properly deallocated if iteration is not completed.
///
/// # Examples
///
/// ```rust
/// use circular_doubly_linked_list::CircularDoublyLinkedList;
///
/// let mut list = CircularDoublyLinkedList::new();
/// list.push_back(1);
/// list.push_back(2);
/// list.push_back(3);
///
/// // Consume the list
/// let vec: Vec<_> = list.into_iter().collect();
/// assert_eq!(vec, [1, 2, 3]);
///
/// // list is now consumed and cannot be used
/// ```
pub struct IntoIter<T> {
    /// Current node pointer (next element to yield and deallocate).
    current: Option<NonNull<Node<T>>>,
    /// Number of remaining elements to iterate.
    remaining: usize,
}

impl<T> IntoIter<T> {
    /// Creates a new owning iterator.
    ///
    /// # Parameters
    ///
    /// * `head` - The head node of the list (starting point for iteration)
    /// * `length` - The number of elements in the list (used for bounds)
    ///
    /// # Returns
    ///
    /// Returns a new `IntoIter<T>` instance that will consume the list.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `head` accurately represents the list state
    /// and that `length` matches the actual number of nodes in the circular chain.
    pub(crate) fn new(head: Option<NonNull<Node<T>>>, length: usize) -> Self {
        Self {
            current: head,
            remaining: length,
        }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    /// Advances the iterator, removes, and returns the next owned value.
    ///
    /// # Returns
    ///
    /// - `Some(T)` - The next element (removed from the list) if available
    /// - `None` - When all elements have been iterated
    ///
    /// # Side Effects
    ///
    /// Each call to `next()` deallocates one node from the list.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// let mut iter = list.into_iter();
    /// assert_eq!(iter.next(), Some(1));
    /// assert_eq!(iter.next(), Some(2));
    /// assert_eq!(iter.next(), None);
    /// ```
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }

        unsafe {
            let current = self.current.unwrap_unchecked();
            let next = Node::get_next(current);

            self.current = if self.remaining == 1 {
                None
            } else {
                Some(next)
            };

            self.remaining -= 1;
            Some(Node::dealloc(current))
        }
    }

    /// Returns the exact remaining length of the iterator.
    ///
    /// # Returns
    ///
    /// Returns a tuple `(min, max)` where both values equal the remaining count.
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<T> ExactSizeIterator for IntoIter<T> {
    /// Returns the exact number of remaining elements.
    ///
    /// # Returns
    ///
    /// Returns the number of elements yet to be iterated and deallocated.
    fn len(&self) -> usize {
        self.remaining
    }
}

impl<T> Drop for IntoIter<T> {
    /// Deallocates any remaining nodes when the iterator is dropped.
    ///
    /// This ensures no memory leaks occur if the iterator is dropped before
    /// all elements are consumed (e.g., early return, panic, or `.take(n)`).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    /// list.push_back(3);
    ///
    /// {
    ///     let mut iter = list.into_iter();
    ///     let _first = iter.next(); // Consume one element
    ///     // iter dropped here - remaining elements are deallocated
    /// }
    /// // No memory leak
    /// ```
    fn drop(&mut self) {
        if self.remaining == 0 {
            return;
        }

        unsafe {
            let mut current = self.current.unwrap();
            let mut count = 0;

            while count < self.remaining {
                let next = Node::get_next(current);
                Node::dealloc(current);
                current = next;
                count += 1;
            }
        }

        self.current = None;
        self.remaining = 0;
    }
}