circular_doubly_linked_list 0.1.0

//! List module containing the main Circular Doubly Linked List implementation.
//!
//! This module provides the `CircularDoublyLinkedList` struct which is the
//! primary public API for interacting with the data structure. All unsafe
//! operations are encapsulated within safe methods.
//!
//! # Design Decisions
//!
//! This implementation maintains both `head` and `tail` pointers for:
//! - **O(1)** access to both front and back elements
//! - **O(1)** insertion at both ends without pointer traversal
//! - Clearer semantic meaning for list boundaries
//!
//! # Invariants
//!
//! The following invariants are maintained throughout the list's lifetime:
//! - If the list is non-empty, both `head` and `tail` point to valid nodes
//! - If the list is empty, both `head` and `tail` are `None`
//! - If the list has one element, `head == tail`
//! - If the list has multiple elements:
//!   - `tail.next == head` (circular forward link)
//!   - `head.prev == tail` (circular backward link)
//! - The `length` field accurately reflects the number of nodes

use core::ptr::NonNull;

use crate::iter::{IntoIter, Iter, IterMut};
use crate::node::Node;

/// A circular doubly linked list with explicit head and tail pointers.
///
/// This data structure provides O(1) insertion and deletion at both ends,
/// with safe APIs that wrap unsafe pointer operations internally. The circular
/// nature means the last node points back to the first, and vice versa.
///
/// # Type Parameters
///
/// * `T` - The type of elements stored in the list
///
/// # Examples
///
/// ```rust
/// use circular_doubly_linked_list::CircularDoublyLinkedList;
///
/// let mut list = CircularDoublyLinkedList::new();
/// list.push_back(1);
/// list.push_back(2);
/// list.push_front(0);
///
/// assert_eq!(list.len(), 3);
/// assert_eq!(list.front(), Some(&0));
/// assert_eq!(list.back(), Some(&2));
/// ```
///
/// # Safety
///
/// While the public API is safe, the internal implementation uses raw pointers.
/// The list maintains the following invariants:
/// - If the list is non-empty, `head` and `tail` point to valid nodes
/// - All nodes form a proper circular chain
/// - The length accurately reflects the number of nodes
/// - No node is ever accessed after deallocation
pub struct CircularDoublyLinkedList<T> {
    /// Pointer to the head node (front of the list).
    ///
    /// This points to the first element inserted via `push_front` or the
    /// first element when using only `push_back`.
    ///
    /// # Invariants
    ///
    /// - `None` if and only if the list is empty
    /// - Points to a valid allocated `Node<T>` when non-empty
    /// - `head.prev` always points to the tail node (when non-empty)
    head: Option<NonNull<Node<T>>>,

    /// Pointer to the tail node (back of the list).
    ///
    /// This points to the last element inserted via `push_back` or the
    /// last element in the logical order of the list.
    ///
    /// # Invariants
    ///
    /// - `None` if and only if the list is empty
    /// - Points to a valid allocated `Node<T>` when non-empty
    /// - `tail.next` always points to the head node (when non-empty)
    /// - When `length == 1`, `tail == head`
    tail: Option<NonNull<Node<T>>>,

    /// The number of elements in the list.
    ///
    /// This is cached to provide O(1) length queries without traversal.
    ///
    /// # Invariants
    ///
    /// - Always equals the actual number of allocated nodes
    /// - Zero if and only if `head` and `tail` are both `None`
    length: usize,
}

impl<T> CircularDoublyLinkedList<T> {
    /// Creates a new empty circular doubly linked list.
    ///
    /// # Returns
    ///
    /// Returns a new empty `CircularDoublyLinkedList` with `head` and `tail`
    /// set to `None` and `length` set to 0.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let list: CircularDoublyLinkedList<i32> = CircularDoublyLinkedList::new();
    /// assert!(list.is_empty());
    /// assert_eq!(list.len(), 0);
    /// assert_eq!(list.front(), None);
    /// assert_eq!(list.back(), None);
    /// ```
    pub fn new() -> Self {
        Self {
            head: None,
            tail: None,
            length: 0,
        }
    }

    /// Returns the number of elements in the list.
    ///
    /// # Returns
    ///
    /// Returns the length of the list as `usize`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// assert_eq!(list.len(), 0);
    ///
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.len(), 2);
    ///
    /// list.push_front(0);
    /// assert_eq!(list.len(), 3);
    /// ```
    pub fn len(&self) -> usize {
        self.length
    }

    /// Returns `true` if the list contains no elements.
    ///
    /// # Returns
    ///
    /// Returns `true` if the list is empty (length is 0), `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// assert!(list.is_empty());
    ///
    /// list.push_back(1);
    /// assert!(!list.is_empty());
    ///
    /// list.pop_back();
    /// assert!(list.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.length <= 0
    }

    /// Returns a reference to the front element of the list.
    ///
    /// # Returns
    ///
    /// Returns `Some(&T)` containing a reference to the front element if the
    /// list is non-empty, or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// assert_eq!(list.front(), None);
    ///
    /// list.push_front(42);
    /// assert_eq!(list.front(), Some(&42));
    ///
    /// list.push_front(100);
    /// assert_eq!(list.front(), Some(&100));
    /// ```
    pub fn front(&self) -> Option<&T> {
        self.head.map(|head| unsafe { Node::data_ref(head) })
    }

    /// Returns a mutable reference to the front element of the list.
    ///
    /// # Returns
    ///
    /// Returns `Some(&mut T)` containing a mutable reference to the front
    /// element if the list is non-empty, or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_front(42);
    ///
    /// if let Some(front) = list.front_mut() {
    ///     *front = 100;
    /// }
    ///
    /// assert_eq!(list.front(), Some(&100));
    /// ```
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.head.map(|head| unsafe { Node::data_mut(head) })
    }

    /// Returns a reference to the back element of the list.
    ///
    /// # Returns
    ///
    /// Returns `Some(&T)` containing a reference to the back element if the
    /// list is non-empty, or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// assert_eq!(list.back(), None);
    ///
    /// list.push_back(42);
    /// assert_eq!(list.back(), Some(&42));
    ///
    /// list.push_back(100);
    /// assert_eq!(list.back(), Some(&100));
    /// ```
    pub fn back(&self) -> Option<&T> {
        self.tail.map(|tail| unsafe { Node::data_ref(tail) })
    }

    /// Returns a mutable reference to the back element of the list.
    ///
    /// # Returns
    ///
    /// Returns `Some(&mut T)` containing a mutable reference to the back
    /// element if the list is non-empty, or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(42);
    ///
    /// if let Some(back) = list.back_mut() {
    ///     *back = 100;
    /// }
    ///
    /// assert_eq!(list.back(), Some(&100));
    /// ```
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.tail.map(|tail| unsafe { Node::data_mut(tail) })
    }

    /// Inserts an element at the front of the list.
    ///
    /// After this operation, the new element becomes the front element and
    /// can be accessed via `front()` or `front_mut()`.
    ///
    /// # Parameters
    ///
    /// * `value` - The value to insert at the front
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_front(1);
    /// list.push_front(2);
    /// list.push_front(3);
    ///
    /// assert_eq!(list.front(), Some(&3));
    /// assert_eq!(list.back(), Some(&1));
    /// assert_eq!(list.len(), 3);
    /// ```
    pub fn push_front(&mut self, value: T) {
        let new_node = Node::new(value);

        unsafe {
            match (self.head, self.tail) {
                (None, None) => {
                    self.head = Some(new_node);
                    self.tail = Some(new_node);
                }
                (Some(head), Some(tail)) => {
                    Node::set_next(new_node, head);
                    Node::set_prev(new_node, tail);
                    Node::set_prev(head, new_node);
                    Node::set_next(tail, new_node);
                    self.head = Some(new_node);
                }
                _ => unreachable!("head and tail must both be None or both be Some"),
            }
        }

        self.length += 1;
    }

    /// Inserts an element at the back of the list.
    ///
    /// After this operation, the new element becomes the back element and
    /// can be accessed via `back()` or `back_mut()`.
    ///
    /// # Parameters
    ///
    /// * `value` - The value to insert at the back
    ///
    /// # 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);
    ///
    /// assert_eq!(list.front(), Some(&1));
    /// assert_eq!(list.back(), Some(&3));
    /// assert_eq!(list.len(), 3);
    /// ```
    pub fn push_back(&mut self, value: T) {
        let new_node = Node::new(value);

        unsafe {
            match (self.head, self.tail) {
                (None, None) => {
                    self.head = Some(new_node);
                    self.tail = Some(new_node);
                }
                (Some(head), Some(tail)) => {
                    Node::set_next(new_node, head);
                    Node::set_prev(new_node, tail);
                    Node::set_next(tail, new_node);
                    Node::set_prev(head, new_node);
                    self.tail = Some(new_node);
                }
                _ => unreachable!("head and tail must both be None or both be Some"),
            }
        }

        self.length += 1;
    }

    /// Removes and returns the front element of the list.
    ///
    /// # Returns
    ///
    /// Returns `Some(T)` containing the removed front element if the list is
    /// non-empty, or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_front(1);
    /// list.push_front(2);
    ///
    /// assert_eq!(list.pop_front(), Some(2));
    /// assert_eq!(list.pop_front(), Some(1));
    /// assert_eq!(list.pop_front(), None);
    /// ```
    pub fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        unsafe {
            let head = self.head?;
            let tail = self.tail?;
            let next = Node::get_next(head);

            let result = if self.length == 1 {
                self.head = None;
                self.tail = None;
                Some(Node::dealloc(head))
            } else {
                Node::set_next(tail, next);
                Node::set_prev(next, tail);
                self.head = Some(next);
                Some(Node::dealloc(head))
            };

            self.length -= 1;
            result
        }
    }

    /// Removes and returns the back element of the list.
    ///
    /// # Returns
    ///
    /// Returns `Some(T)` containing the removed back element if the list is
    /// non-empty, or `None` if the list is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// assert_eq!(list.pop_back(), Some(2));
    /// assert_eq!(list.pop_back(), Some(1));
    /// assert_eq!(list.pop_back(), None);
    /// ```
    pub fn pop_back(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        unsafe {
            let head = self.head?;
            let tail = self.tail?;
            let prev = Node::get_prev(tail);

            let result = if self.length == 1 {
                self.head = None;
                self.tail = None;
                Some(Node::dealloc(tail))
            } else {
                Node::set_next(prev, head);
                Node::set_prev(head, prev);
                self.tail = Some(prev);
                Some(Node::dealloc(tail))
            };

            self.length -= 1;
            result
        }
    }

    /// Inserts an element after the given position.
    ///
    /// # Parameters
    ///
    /// * `position` - The index after which to insert (0-based). Valid range: `0..length-1`
    /// * `value` - The value to insert
    ///
    /// # Returns
    ///
    /// Returns `true` if insertion was successful, or `false` if the position
    /// is out of bounds (position >= length).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(3);
    ///
    /// assert!(list.insert_after(0, 2));
    ///
    /// let vec: Vec<_> = list.iter().copied().collect();
    /// assert_eq!(vec, [1, 2, 3]);
    ///
    /// // Invalid position
    /// assert!(!list.insert_after(10, 4));
    /// ```
    pub fn insert_after(&mut self, position: usize, value: T) -> bool {
        if position >= self.length {
            return false;
        }

        let target_node = unsafe { self.get_node_at(position).unwrap() };

        unsafe {
            let new_node = Node::new(value);
            let next = Node::get_next(target_node);

            Node::set_next(new_node, next);
            Node::set_prev(new_node, target_node);
            Node::set_next(target_node, new_node);
            Node::set_prev(next, new_node);

            if Some(target_node) == self.tail {
                self.tail = Some(new_node);
            }
        }

        self.length += 1;
        true
    }

    /// Removes the element at the given position.
    ///
    /// # Parameters
    ///
    /// * `position` - The index of the element to remove (0-based)
    ///
    /// # Returns
    ///
    /// Returns `Some(T)` containing the removed element if the position is
    /// valid, or `None` if the position is out of bounds.
    ///
    /// # 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);
    ///
    /// assert_eq!(list.remove_at(1), Some(2));
    ///
    /// let vec: Vec<_> = list.iter().copied().collect();
    /// assert_eq!(vec, [1, 3]);
    ///
    /// // Invalid position
    /// assert_eq!(list.remove_at(10), None);
    /// ```
    pub fn remove_at(&mut self, position: usize) -> Option<T> {
        if self.is_empty() || position >= self.length {
            return None;
        }

        let target_node = unsafe { self.get_node_at(position)? };
        unsafe {
            let next = Node::get_next(target_node);
            let prev = Node::get_prev(target_node);

            if Some(target_node) == self.head {
                self.head = Some(next);
            }

            if Some(target_node) == self.tail {
                self.tail = Some(prev)
            }

            if self.length == 1 {
                self.head = None;
                self.tail = None;
            } else {
                Node::set_next(prev, next);
                Node::set_prev(next, prev);
            }

            self.length -= 1;
            Some(Node::dealloc(target_node))
        }
    }

    /// Clears all elements from the list.
    ///
    /// After this operation, the list will be empty with `head` and `tail`
    /// set to `None` and `length` set to 0.
    ///
    /// # 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);
    ///
    /// list.clear();
    ///
    /// assert!(list.is_empty());
    /// assert_eq!(list.len(), 0);
    /// assert_eq!(list.front(), None);
    /// assert_eq!(list.back(), None);
    /// ```
    pub fn clear(&mut self) {
        while self.pop_front().is_some() {}
    }

    /// Returns an iterator over the list.
    ///
    /// # Returns
    ///
    /// Returns an `Iter<T>` that yields immutable references to elements
    /// in order from front to back.
    ///
    /// # 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);
    ///
    /// for item in list.iter() {
    ///     println!("{}", item);
    /// }
    /// // Output: 1, 2, 3
    /// ```
    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self.head, self.length)
    }

    /// Returns an iterator over the list with mutable references.
    ///
    /// # Returns
    ///
    /// Returns an `IterMut<T>` that yields mutable references to elements
    /// in order from front to back.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// for item in list.iter_mut() {
    ///     *item *= 2;
    /// }
    ///
    /// let vec: Vec<_> = list.iter().copied().collect();
    /// assert_eq!(vec, [2, 4]);
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut::new(self.head, self.length)
    }

    /// Rotates the list by moving the front element to the back.
    ///
    /// This operation is O(1) because it only updates the head and tail
    /// pointers without moving any data.
    ///
    /// # 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);
    ///
    /// list.rotate_left();
    ///
    /// let vec: Vec<_> = list.iter().copied().collect();
    /// assert_eq!(vec, [2, 3, 1]);
    /// ```
    pub fn rotate_left(&mut self) {
        if self.length > 1 {
            unsafe {
                let head = self.head.unwrap();
                let new_head = Node::get_next(head);
                let new_tail = head;

                self.head = Some(new_head);
                self.tail = Some(new_tail);
            }
        }
    }

    /// Rotates the list by moving the back element to the front.
    ///
    /// This operation is O(1) because it only updates the head and tail
    /// pointers without moving any data.
    ///
    /// # 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);
    ///
    /// list.rotate_right();
    ///
    /// let vec: Vec<_> = list.iter().copied().collect();
    /// assert_eq!(vec, [3, 1, 2]);
    /// ```
    pub fn rotate_right(&mut self) {
        if self.length > 1 {
            unsafe {
                let tail = self.tail.unwrap();
                let new_head = tail;
                let new_tail = Node::get_prev(tail);

                self.head = Some(new_head);
                self.tail = Some(new_tail);
            }
        }
    }

    /// Internal helper to get a node at a specific position.
    ///
    /// # Parameters
    ///
    /// * `position` - The 0-based index of the node to retrieve
    ///
    /// # Returns
    ///
    /// Returns `Some(NonNull<Node<T>>)` if the position is valid, `None` otherwise.
    ///
    /// # Safety
    ///
    /// The caller must ensure that:
    /// - The list is not empty
    /// - The position is within bounds (position < length)
    ///
    /// # Optimization
    ///
    /// This method traverses from the closer end (head or tail) to minimize
    /// the number of pointer dereferences.
    unsafe fn get_node_at(&self, position: usize) -> Option<NonNull<Node<T>>> {
        if self.is_empty() || position >= self.length {
            return None;
        }

        if position < self.length / 2 {
            let mut current = self.head?;

            for _ in 0..position {
                current = unsafe { Node::get_next(current) }
            }
            Some(current)
        } else {
            let mut current = self.tail?;
            for _ in position + 1..self.length {
                current = unsafe { Node::get_prev(current) }
            }
            Some(current)
        }
    }
}

impl<T> Default for CircularDoublyLinkedList<T> {
    /// Creates a default (empty) circular doubly linked list.
    ///
    /// # Returns
    ///
    /// Returns a new empty `CircularDoublyLinkedList`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let list: CircularDoublyLinkedList<i32> = CircularDoublyLinkedList::default();
    /// assert!(list.is_empty());
    /// ```
    fn default() -> Self {
        Self::new()
    }
}

impl<T> Drop for CircularDoublyLinkedList<T> {
    /// Drops the list and deallocates all nodes.
    ///
    /// This ensures all allocated memory is properly freed when the list
    /// goes out of scope.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// {
    ///     let mut list = CircularDoublyLinkedList::new();
    ///     list.push_back(1);
    ///     list.push_back(2);
    ///     // List is automatically dropped here
    /// }
    /// ```
    fn drop(&mut self) {
        self.clear();
    }
}

impl<T> Clone for CircularDoublyLinkedList<T>
where
    T: Clone,
{
    /// Creates a deep copy of the list.
    ///
    /// # Returns
    ///
    /// Returns a new `CircularDoublyLinkedList` with cloned elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// let cloned = list.clone();
    ///
    /// assert_eq!(list.len(), cloned.len());
    /// assert!(list.iter().eq(cloned.iter()));
    /// ```
    fn clone(&self) -> Self {
        let mut new_list = CircularDoublyLinkedList::<T>::new();
        for item in self.iter() {
            new_list.push_back(item.clone());
        }
        new_list
    }
}

impl<T> Extend<T> for CircularDoublyLinkedList<T> {
    /// Extends the list with elements from an iterator.
    ///
    /// # Parameters
    ///
    /// * `iter` - An iterator yielding elements to add
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.extend(vec![1, 2, 3]);
    ///
    /// assert_eq!(list.len(), 3);
    /// ```
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for item in iter {
            self.push_back(item);
        }
    }
}

impl<T: core::fmt::Debug> core::fmt::Debug for CircularDoublyLinkedList<T> {
    /// Formats the list for debugging.
    ///
    /// # Parameters
    ///
    /// * `f` - The formatter to write to
    ///
    /// # Returns
    ///
    /// Returns a `Result` indicating success or failure.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// println!("{:?}", list);
    /// // Output: [1, 2]
    /// ```
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl<T> FromIterator<T> for CircularDoublyLinkedList<T> {
    /// Creates a list from an iterator.
    ///
    /// # Parameters
    ///
    /// * `iter` - An iterator yielding elements
    ///
    /// # Returns
    ///
    /// Returns a new `CircularDoublyLinkedList` containing all elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let list: CircularDoublyLinkedList<i32> = vec![1, 2, 3].into_iter().collect();
    ///
    /// assert_eq!(list.len(), 3);
    /// ```
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = CircularDoublyLinkedList::<T>::new();
        list.extend(iter);
        list
    }
}

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

    /// Consumes the list and returns an iterator over its elements.
    ///
    /// # Returns
    ///
    /// Returns an `IntoIter<T>` that yields owned values.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use circular_doubly_linked_list::CircularDoublyLinkedList;
    ///
    /// let mut list = CircularDoublyLinkedList::new();
    /// list.push_back(1);
    /// list.push_back(2);
    ///
    /// for item in list.into_iter() {
    ///     println!("{}", item);
    /// }
    /// ```
    fn into_iter(self) -> Self::IntoIter {
        let iter = IntoIter::new(self.head, self.length);
        core::mem::forget(self);
        iter
    }
}

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

    /// Returns an iterator over immutable references.
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

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

    /// Returns an iterator over mutable references.
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}