Indexed Linked List

ill.rs

//! # Index-based doubly-linked list + cursor + task queue
//!
//! This module implements a **doubly-linked list backed by indexable storage**
//! (arenas, slabs, or fixed arrays) rather than raw pointers. It includes:
//!
//! - [`NodeStorage`] — abstraction over the backing store (keys are indices/handles).
//! - [`ILL`] — the index-linked list itself (head/tail + per-node `prev`/`next`).
//! - [`IndexLinkedList`] — trait exposing a cursor and basic push/iterate ops.
//! - [`NodeCursor`] / [`CursorMut`] — **mutable, bidirectional cursor** with a
//!   *gap* (`prev`, `current`, `next`) for true **insert-before/after** and removals.
//! - [`Iter`] — forward iterator yielding `&T` from head to tail.
//! - [`TaskList`] — a simple **future queue** built on [`ILL`]; it polls tasks
//!   in place and drives a user callback when they complete.
//!
//! The design targets arenas, slabs, and fixed-capacity arrays where **indices are
//! stable** until a slot is explicitly removed. No per-node heap allocation is required.
//!
//! ### Visual: storage indices vs list order
//!
//! Storage keys (`NodeStorage::Key`) are along the top; the arena nodes and
//! list order are along the bottom.
//!
//! ```text
//! index:  [0] [1]           [2]    [3]    [4]    [5]
//!           \  |             |      |
//!            \ |             |      |
//!             \|             |      |
//!              \             |      |
//!              |\            |      |
//!              | \           |      |
//!              |  \          |      |
//!              |   \         |      |
//!              |    \        |      |
//!              |     \       |      |
//!              v      v      v      v
//! Data:       [A] -> [C] -> [D] -> [E]
//! ```
//!
//! ---
//!
//! ## Quick start
//!
//! ```rust
//! # use ill::{ILL, IndexLinkedList, ArrayStorage, Node};
//! // A small list backed by a fixed array (capacity = 8):
//! let mut list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 8>>::new(
//!     ArrayStorage::with_capacity()
//! );
//!
//! list.try_push_back(10);
//! list.try_push_back(20);
//! list.try_push_front(5);
//!
//! // Iterate head → tail
//! let v: Vec<_> = list.iter().copied().collect();
//! assert_eq!(v, vec![5, 10, 20]);
//! ```
//!
//! ### Using the mutable cursor
//! The cursor maintains a *gap* between `prev` and `next` and an optional `current`.
//! `is_empty()` means the **cursor is detached** (not that the list is empty).
//!
//! ```rust
//! # use ill::{ILL, IndexLinkedList, ArrayStorage, Node};
//! let mut list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 8>>::new(
//!     ArrayStorage::with_capacity()
//! );
//! list.try_push_back(1);
//! list.try_push_back(2);
//! list.try_push_back(3);
//!
//! let mut c = list.cursor_mut();      // detached: prev=None, next=head
//! assert_eq!(c.next().copied(), Some(1)); // on 1
//!
//! // True after/before relative to *current*
//! c.insert_after(9);                  // [1, 9, 2, 3]; gap kept on the right
//! assert_eq!(c.next().copied(), Some(9));
//!
////! c.insert_before(8);                // [1, 8, 9, 2, 3]; gap kept on the left
//! assert_eq!(c.peek_prev().copied(), Some(8));
//!
//! // Remove the current node and stay detached with the same gap:
//! assert_eq!(c.remove_current(), Some(9)); // [1, 8, 2, 3]
//! ```
//!
//! ---
//!
//! ## Storage backends
//!
//! Implementations of [`NodeStorage`] define how nodes are stored and addressed
//! via a key type (`Self::Key`):
//!
//! - [`ArrayStorage<T, N>`] — fixed capacity (`N`, default `32`), keys are `usize`,
//!   **no allocation**, addresses stable until removal.
//! - <span class="stab portability">Feature `slab`</span>: adapters for
//!   [`slab::Slab<T>`] and `&mut slab::Slab<T>` (effectively unbounded; indices
//!   are stable while occupied and **reused after removal**).
//!
//! You can plug in your own arena/slab by implementing [`NodeStorage`].
//!
//! ---
//!
//! ## Complexity
//!
//! On top of the storage backend:
//!
//! - Cursor movement/peek/insert/remove: **O(1)**
//! - Push front/back: **O(1)**
//! - Iteration: **O(n)**
//!
//! [`ArrayStorage`]’s `try_push` scans for a free hole (**O(N)** in the worst case).
//!
//! ---
//!
//! ## Safety & semantics
//!
//! - Nodes link by **keys**, not pointers. No unsafe pointer juggling here; safety
//!   follows from the storage backend’s guarantees.
//! - **Stability:** A node’s location is stable until that slot is removed. Any
//!   references obtained from `get_node_mut` become invalid when that slot is removed.
//! - **Key reuse:** Some backends (e.g., slab) reuse keys after removal. Don’t hang on
//!   to keys once you’ve removed their node.
//! - **Cursor detachment:** [`NodeCursor::is_empty`] refers to the cursor, not the list.
//!   Use [`IndexLinkedList::is_empty`] for the list itself.
//!
//! ---
//!
//! ## Task queue as a future
//!
//! [`TaskList`] stores futures in an [`ILL`] and polls them **head → tail** each call
//! to `poll`. When a task completes, it is removed and its output is given to a user
//! callback `FnMut(R) -> Poll<R>`. If the callback returns `Ready(r)`, the whole
//! `TaskList` resolves to `Some(r)`. If the list becomes empty, it resolves to `None`.
//!
//! ```rust,no_run
//! # use std::task::Poll;
//! # use tokio::time::{sleep, Duration};
//! # use ill::{TaskList, ArrayStorage, Node, NodeStorage};
//! let storage = ArrayStorage::<Node<tokio::time::Sleep, usize>, 128>::new();
//! let mut tl = TaskList::new(storage, |_out| Poll::Pending);
//!
//! tl.try_push_back(sleep(Duration::from_millis(10))); // tokio::time::Sleep is Unpin
//! // .await resolves to None when all tasks complete
//! # tokio::spawn(async move { let _ = tl.await; });
//! ```
//!
//! > **Non-`Unpin` futures:** store `Pin<Box<F>>` and push `Box::pin(f)`.
//!
//! ---
//!
//! ## Feature flags
//!
//! - **`slab`** — Enables [`NodeStorage`] adapters for `slab::Slab<T>` and `&mut slab::Slab<T>`.
//!
//! ---
//!
//! ## When should I use this?
//! - You want a linked structure without pointer gymnastics.
//! - You need **stable indices** and **O(1)** splices with a small, known upper bound
//!   (use [`ArrayStorage`]) or unbounded growth (use `slab`).
//! - You want fine-grained in-place editing via a **gap cursor** (true before/after).
//!
//! ---
//!
//! ## Key types & names
//!
//! - `T` — element type
//! - `K` — storage key/handle (e.g., `usize` for array indices)
//! - `S` — storage backend implementing `NodeStorage<Node<T, K>>`
//!
//! ---
//!
//! ## See also
//! - [`Node<T, K>`] — node payload + `prev`/`next` keys
//! - [`ILL<T, K, S>`] — the list type
//! - [`IndexLinkedList`] / [`NodeCursor`] — traits
//! - [`ArrayStorage<T, N>`] — fixed-capacity arena
//! - [`TaskList<F, K, S, C, R>`] — future queue over an index-list

use std::{
    marker::PhantomData,
    pin::Pin,
    task::{Context, Poll},
};

/// A mutable, bidirectional cursor for traversing and modifying a node-based list.
///
/// The cursor maintains three positions:
/// - `prev`: the key of the node immediately before the gap,
/// - `current`: the node the cursor is "on" (if any),
/// - `next`: the key of the node immediately after the gap.
///
/// **Detached vs list-empty:** `is_empty()` here means the cursor is *detached*
/// (i.e., `current` is `None`). It does **not** indicate whether the list itself
/// is empty. To check the list, call `list.is_empty()`.
///
/// Semantics:
/// - `next()`/`prev()` move the cursor to the neighbor and return `&mut T`.
/// - `peek_next()`/`peek_prev()` borrow the neighbor in place without moving.
/// - `insert_after(value)` when on a node inserts **after `current`**; the gap is
///   kept on the right so a subsequent `next()` yields the newly inserted node.
///   When detached at tail, this appends.
/// - `insert_before(value)` when on a node inserts **before `current`**; the gap
///   is kept on the left so a subsequent `prev()` (or `peek_prev()`) yields the
///   newly inserted node. When detached at head, this prepends and a subsequent
///   `next()` yields the newly inserted node.
/// - `remove_current()` removes the current node, detaches the cursor (`current = None`)
///   and preserves the gap (`prev`/`next`) so you can continue walking or inserting.
/// - `remove_next()` / `remove_prev()` remove the neighbor on that side and update
///   the adjacent links and cursor gap accordingly.
///
/// `'a` is the borrow duration tied to the underlying list; `T` is the element type.
pub trait NodeCursor<'a, T> {
    /// Returns `true` if the cursor is **detached** (not on any node).
    fn is_detached(&self) -> bool;

    /// Moves to the next node; returns `None` if there is no next node.
    fn next(&mut self) -> Option<&mut T>;

    /// Moves to the previous node; returns `None` if there is no previous node.
    fn prev(&mut self) -> Option<&mut T>;

    /// Borrows the next node without moving; returns `None` if none.
    fn peek_next(&mut self) -> Option<&mut T>;

    /// Borrows the previous node without moving; returns `None` if none.
    fn peek_prev(&mut self) -> Option<&mut T>;

    /// Inserts a new element **after the current node** (or at tail if detached),
    /// keeps the gap on the right, and returns a mutable ref to the inserted value.
    fn insert_after(&mut self, value: T) -> Option<&mut T>;

    /// Inserts a new element **before the current node** (or at head if detached),
    /// keeps the gap on the left, and returns a mutable ref to the inserted value.
    fn insert_before(&mut self, value: T) -> Option<&mut T>;

    /// Removes the current node and returns its value, if any. The cursor becomes
    /// detached (`current = None`) and preserves its `prev`/`next` gap.
    fn remove_current(&mut self) -> Option<T>;

    /// Removes the next node and returns its value (does not move the cursor).
    fn remove_next(&mut self) -> Option<T>;

    /// Removes the previous node and returns its value (does not move the cursor).
    fn remove_prev(&mut self) -> Option<T>;
}

/// An abstract storage interface for index-based, node-driven data structures.
///
/// `NodeStorage` provides a general-purpose API for inserting, accessing,
/// and removing values using a unique key type (`Self::Key`). It supports both
/// fixed-capacity and dynamically-allocated implementations.
///
/// The trait is designed for use in linked or graph-like structures where nodes
/// are connected via indices instead of pointers, enabling the design of
/// allocation-free or arena-based collections.
///
/// # Type Parameters
/// - `T`: The type of value to store
pub trait NodeStorage<T> {
    /// A unique key used to identify values in the storage.
    ///
    /// Typically this is an integer index like `usize`, but it could be a
    /// custom handle (e.g., from `slotmap`, `slab`, or a strongly typed wrapper).
    type Key: Clone + Copy;

    /// Returns `true` if the storage is full and cannot accept any more values.
    ///
    /// For dynamically growing containers (e.g., `Vec`), this may always return `false`.
    fn is_full(&self) -> bool;

    /// Returns `true` if the storage is empty (i.e., contains no values).
    fn is_empty(&self) -> bool;

    /// Attempts to insert a value into the storage.
    ///
    /// Returns `Some(Self::Key)` if the value was successfully inserted, or `None`
    /// if the storage is full (for fixed-capacity backends).
    fn try_push(&mut self, value: T) -> Option<Self::Key>;

    /// Returns an immutable reference to the value at the given key, if it exists.
    ///
    /// Returns `Some(&T)` if the key refers to a valid, occupied slot,
    /// or `None` if the key is invalid or the slot is empty.
    fn get_node(&self, index: Self::Key) -> Option<&T>;

    /// Returns a mutable reference to the value at the given key, if it exists.
    ///
    /// Returns `Some(&mut T)` if the key refers to a valid, occupied slot,
    /// or `None` if the key is invalid or the slot is empty.
    fn get_node_mut(&mut self, index: Self::Key) -> Option<&mut T>;

    /// Removes and returns the value stored at the given key, if any.
    ///
    /// Returns `Some(value)` if the key was valid and contained a value,
    /// or `None` if the slot was empty or the key was invalid.
    fn remove_node_at(&mut self, index: Self::Key) -> Option<T>;
}

/// A trait representing an index-based, node-driven linked list with cursor support.
///
/// This trait defines the interface for a linked list that uses an underlying [`NodeStorage`]
/// backend to store and manage node data. Nodes are accessed and linked using index-based keys
/// (not pointers), enabling efficient implementations that work with arenas, slabs,
/// or preallocated buffers.
///
/// The list exposes a mutable cursor that can traverse and modify nodes in-place,
/// as well as convenience methods for pushing to the front or back.
///
/// # Type Parameters
/// - `T`: The element type stored in the list
pub trait IndexLinkedList<T> {
    type Iter<'a>: Iterator<Item = &'a T>
    where
        T: 'a,
        Self: 'a;

    /// A cursor type that allows mutable traversal and manipulation of the list.
    ///
    /// The cursor is typically implemented to hold a reference to the list and an optional key
    /// representing the "current" node. It provides functionality such as moving, inserting, and
    /// removing nodes at runtime.
    ///
    /// This associated type must implement the [`NodeCursor`] trait.
    type Cursor<'a>: NodeCursor<'a, T>
    where
        Self: 'a;

    /// Returns `true` if the **list** contains no elements.
    ///
    /// This checks the list itself (typically `head.is_none()` / `storage.is_empty()`),
    /// **not** a cursor. For a cursor’s detached state, see [`NodeCursor::is_empty`].
    ///
    /// # Complexity
    /// O(1).
    ///
    /// # Example
    /// ```ignore
    /// # use ill::{ILL, IndexLinkedList, ArrayStorage, Node};
    /// let mut list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 4>>::new(
    ///     ArrayStorage::<Node<i32, usize>>::with_capacity::<4>()
    /// );
    /// assert!(list.is_empty());
    /// list.try_push_back(1);
    /// assert!(!list.is_empty());
    /// ```
    fn is_empty(&self) -> bool;

    /// Returns `true` if the **underlying storage is at capacity** and cannot
    /// accept another node.
    ///
    /// For fixed-capacity backends like [`ArrayStorage<T, N>`] this becomes `true`
    /// once `N` slots are occupied. For growable backends (e.g. `slab::Slab<T>`)
    /// it is effectively always `false`.
    ///
    /// # Complexity
    /// O(1).
    ///
    /// # Example
    /// ```ignore
    /// # use ill::{ILL, IndexLinkedList, ArrayStorage, Node};
    /// let mut list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 2>>::new(
    ///     ArrayStorage::<Node<i32, usize>>::with_capacity::<2>()
    /// );
    /// assert!(!list.is_full());
    /// list.try_push_back(10);
    /// list.try_push_back(20);
    /// assert!(list.is_full()); // storage has no free slot
    /// ```
    fn is_full(&self) -> bool;

    /// Attempts to insert a new value at the front (head) of the list.
    ///
    /// Returns `Some(&mut T)` pointing to the inserted value on success,
    /// or `None` if the underlying storage is full.
    fn try_push_front(&mut self, value: T) -> Option<&mut T>;

    /// Attempts to insert a new value at the back (tail) of the list.
    ///
    /// Returns `Some(&mut T)` pointing to the inserted value on success,
    /// or `None` if the underlying storage is full.
    fn try_push_back(&mut self, value: T) -> Option<&mut T>;

    /// Returns a mutable cursor to traverse and manipulate the list.
    ///
    /// The cursor is initially **detached** (`current = None`) with its gap spanning
    /// the head: `prev = None`, `next = head`. Calling `next()` will land on the head
    /// (if any). When the list is empty, `next()` returns `None`.
    fn cursor_mut(&mut self) -> Self::Cursor<'_>;

    /// Returns an iterator over immutable references to elements in the list.
    ///
    /// The iteration order follows the logical order of the list (from head to tail).
    fn iter(&self) -> Self::Iter<'_>;
}

/// A node in an index-based doubly-linked list.
///
/// This struct represents a single element in a linked list, along with
/// optional keys pointing to its neighboring nodes. Instead of using raw pointers,
/// `Node` uses an abstract key type `K` to refer to other nodes — enabling safe
/// and flexible storage in arenas, arrays, slabs, or other indexable structures.
///
/// # Type Parameters
/// - `T`: The type of the value stored in the node.
/// - `K`: The key type used to refer to neighboring nodes (e.g., `usize` for array index).
#[derive(Clone, Copy)]
pub struct Node<T, K>
where
    K: Clone + Copy + PartialEq,
{
    /// The stored element in this node.
    pub value: T,

    /// The key of the next node in the list, or `None` if this is the tail.
    pub next: Option<K>,

    /// The key of the previous node in the list, or `None` if this is the head.
    pub prev: Option<K>,
}

/// A doubly-linked list built on top of an index-based node storage system.
///
/// `ILL` (IndexLinkedList) provides the structure and logic of a doubly-linked list,
/// while deferring the actual storage of nodes to an implementation of the [`NodeStorage`] trait.
/// This design enables flexible list implementations backed by arenas, fixed-size arrays,
/// or heap-allocated slabs — without relying on pointers or dynamic memory per node.
///
/// The list maintains `head` and `tail` pointers as optional keys (typically `usize`),
/// and links nodes together using the `next` and `prev` fields of the stored [`Node<T, K>`] type.
///
/// # Type Parameters
/// - `T`: The type of data stored in each node.
/// - `K`: The key type used by the underlying storage (e.g., `usize`).
/// - `S`: The node storage type, implementing [`NodeStorage<Node<T, K>>`].
///
/// # Fields
/// - `storage`: The backing storage that contains the node values.
/// - `head`: The key of the first node in the list, or `None` if the list is empty.
/// - `tail`: The key of the last node in the list, or `None` if the list is empty.
/// - `ty`: Marker to retain the `T` type (not stored directly).
pub struct ILL<T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    /// The node storage backend (e.g., slab, arena, or array).
    storage: S,

    /// The key of the head (first) node in the list.
    head: Option<K>,

    /// The key of the tail (last) node in the list.
    tail: Option<K>,

    /// Phantom marker to retain the generic type `T`.
    ty: PhantomData<T>,
}

impl<T, K, S> Default for ILL<T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K> + Default,
{
    #[inline]
    fn default() -> Self {
        Self {
            storage: Default::default(),
            head: None,
            tail: None,
            ty: PhantomData,
        }
    }
}

impl<T, K, S> ILL<T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    /// Creates an empty index-linked list backed by the given storage.
    ///
    /// Initializes the list with `head = None` and `tail = None`. The `storage`
    /// is kept as-is and is expected to be **empty**; this constructor does not
    /// scan or initialize it. If you pass a non-empty storage, the list’s
    /// `head`/`tail` won’t reflect its contents.
    ///
    /// - **Ownership:** `ILL` takes ownership of `storage` (which may itself be
    ///   an owned value like `ArrayStorage<_>` or a borrowed one like `&mut Slab<_>`).
    /// - **Stability:** Elements are not relocated by the list; any relocation
    ///   semantics are defined by the storage backend.
    /// - **Complexity:** O(1).
    ///
    /// # Examples
    /// ```
    /// // Fixed-capacity array-backed list (capacity = 8)
    /// let list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 8>>::new(
    ///     ArrayStorage::with_capacity()
    /// );
    /// assert!(list.is_empty());
    /// ```
    ///
    /// ```ignore
    /// // With slab (requires `slab` feature)
    /// let storage = slab::Slab::<Node<i32, usize>>::new();
    /// let list = ILL::<i32, usize, _>::new(storage);
    /// ```
    #[inline]
    #[must_use]
    pub fn new(storage: S) -> Self {
        Self {
            storage,
            head: None,
            tail: None,
            ty: PhantomData,
        }
    }

    #[inline]
    fn link(&mut self, prev: Option<K>, next: Option<K>, new_key: K) {
        if let Some(p) = prev {
            if let Some(pnode) = self.storage.get_node_mut(p) {
                pnode.next = Some(new_key);
            }
        }

        if let Some(n) = next {
            if let Some(nnode) = self.storage.get_node_mut(n) {
                nnode.prev = Some(new_key);
            }
        }
    }

    #[inline]
    fn splice(&mut self, prev: Option<K>, next: Option<K>) {
        if let Some(p) = prev {
            if let Some(pnode) = self.storage.get_node_mut(p) {
                pnode.next = next;
            }
        }
        if let Some(n) = next {
            if let Some(nnode) = self.storage.get_node_mut(n) {
                nnode.prev = prev;
            }
        }
    }
}

/// A **mutable, bidirectional cursor** over an index-linked list (`ILL`).
///
/// The cursor lets you walk the list, peek neighbors, and insert/remove nodes
/// **in place** while maintaining an internal *gap* described by three keys:
///
/// - `prev`: key of the node immediately to the **left** of the gap,
/// - `current`: key of the node the cursor is **on** (if any),
/// - `next`: key of the node immediately to the **right** of the gap.
///
/// ### Detached vs. empty
/// The cursor starts **detached** (`current = None`, `prev = None`, `next = head`).
/// Calling `next()` lands on the head (if any). `is_empty()` indicates the cursor
/// is detached; it does **not** mean the list itself is empty.
///
/// ### Movement
/// - `next()` moves right: lands on `next` and returns `&mut T`.
/// - `prev()` moves left: lands on `prev` and returns `&mut T`.
/// - `peek_next()` / `peek_prev()` borrow neighbors without moving.
///
/// ### Insertion semantics (true before/after current)
/// - `insert_after(v)`  
///   When `current = Some(cur)`, inserts **after `cur`** (between `cur` and the old `next`)
///   and keeps the **gap on the right** (`next` becomes the newly inserted node), so a
///   subsequent `next()` yields the inserted element. When detached at tail, appends.
/// - `insert_before(v)`  
///   When `current = Some(cur)`, inserts **before `cur`** (between the old `prev` and `cur`)
///   and keeps the **gap on the left** (`prev` becomes the newly inserted node), so a
///   subsequent `prev()`/`peek_prev()` yields the inserted element. When detached at head,
///   prepends and sets `next` to the new head so `next()` yields it.
///
/// ### Removal
/// - `remove_current()` removes the node under the cursor and **detaches** it
///   (`current = None`), preserving the surrounding gap (`prev`/`next`) so you can keep
///   walking or inserting.
/// - `remove_next()` / `remove_prev()` remove the neighbor on that side without moving
///   the cursor and fix up the gap accordingly.
///
/// ### Complexity
/// All operations are O(1) on top of the storage backend.
///
/// ### Example
/// ```ignore
/// let mut list = ILL::<i32, usize, _>::new(ArrayStorage::with_capacity::<8>());
/// list.try_push_back(1);
/// list.try_push_back(2);
/// list.try_push_back(3);
///
/// let mut c = list.cursor_mut();            // detached: prev=None, next=head(=1)
/// assert_eq!(c.next().copied(), Some(1));   // on 1
/// assert_eq!(c.insert_after(9).copied(), Some(9)); // [1,9,2,3], next() will see 9
/// assert_eq!(c.next().copied(), Some(9));   // on 9
/// assert_eq!(c.insert_before(8).copied(), Some(8)); // [1,8,9,2,3], prev() sees 8
/// assert_eq!(c.peek_prev().copied(), Some(8));
/// assert_eq!(c.remove_current(), Some(9));  // remove 9, cursor detaches with gap around it
/// ```
///
/// `'a` is the borrow duration of the underlying list; `T` is the element type; `K` is
/// the storage key type; `S` is the storage backend implementing `NodeStorage`.
pub struct CursorMut<'a, T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    list: &'a mut ILL<T, K, S>,
    current: Option<K>,
    prev: Option<K>,
    next: Option<K>,
    ty: PhantomData<T>,
}

/// Forward iterator over immutable element references in an `ILL`.
///
/// This iterator yields `&T` from **head to tail** by following the `next` links
/// of the underlying nodes. It is a *view* over the list: no allocation, and it
/// does **not** yield `&Node<T, K>`.
///
/// ### Semantics
/// - Starts at the list’s `head`.
/// - Each call to `next()` returns `Some(&T)` for the current node and advances to `node.next`.
/// - Stops when it reaches the end (`None`).
///
/// ### Borrowing & mutation
/// The iterator holds an immutable borrow of the list (`&'a ILL<..>`), so typical
/// safe Rust code cannot mutate the list while the iterator is alive. If the
/// storage uses interior mutability and the list is mutated concurrently, the
/// iteration order/contents may change, but memory safety is preserved.
///
/// ### Complexity
/// - `next()` is O(1).
/// - Iterating the entire list is O(n) in the number of nodes.
///
/// ### Notes
/// - Only iterates **forward**; it does not implement `DoubleEndedIterator`.
/// - It does not promise a fixed length, so it’s not `ExactSizeIterator`.
/// - Consider adding `impl core::iter::FusedIterator for Iter<...>` since it
///   doesn’t yield after returning `None`.
///
/// ### Example
/// ```
/// # use ill::{ILL, ArrayStorage, Node}; // adjust paths
/// let mut list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 8>>::new(
///     ArrayStorage::with_capacity()
/// );
/// list.try_push_back(1);
/// list.try_push_back(2);
/// list.try_push_back(3);
///
/// let vals: Vec<_> = list.iter().copied().collect();
/// assert_eq!(vals, vec![1, 2, 3]);
/// ```
pub struct Iter<'a, T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    list: &'a ILL<T, K, S>,
    current: Option<K>,
}

impl<'a, T, K, S> core::iter::FusedIterator for Iter<'a, T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
}

impl<'a, T, K, S> Iterator for Iter<'a, T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        let Some(current) = self.current else {
            return None;
        };

        let node = self.list.storage.get_node(current)?;
        self.current = node.next;

        Some(&node.value)
    }
}

impl<T, K, S> IndexLinkedList<T> for ILL<T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    type Iter<'a>
        = Iter<'a, T, K, S>
    where
        Self: 'a;

    type Cursor<'a>
        = CursorMut<'a, T, K, S>
    where
        Self: 'a;

    #[inline]
    fn is_empty(&self) -> bool {
        self.storage.is_empty()
    }

    #[inline]
    fn is_full(&self) -> bool {
        self.storage.is_full()
    }

    fn try_push_front(&mut self, value: T) -> Option<&mut T> {
        let index = self.storage.try_push(Node {
            value,
            prev: None,
            next: self.head,
        })?;

        self.link(None, self.head, index);
        self.head = Some(index);

        if self.tail.is_none() {
            self.tail = Some(index);
        }

        self.storage.get_node_mut(index).map(|node| &mut node.value)
    }

    fn try_push_back(&mut self, value: T) -> Option<&mut T> {
        let index = self.storage.try_push(Node {
            value,
            prev: self.tail,
            next: None,
        })?;

        self.link(self.tail, None, index);
        self.tail = Some(index);

        if self.head.is_none() {
            self.head = Some(index);
        }

        self.storage.get_node_mut(index).map(|node| &mut node.value)
    }

    #[inline]
    fn cursor_mut(&mut self) -> Self::Cursor<'_> {
        CursorMut {
            current: None,
            prev: None,
            next: self.head,
            list: self,
            ty: PhantomData,
        }
    }

    #[inline]
    fn iter(&self) -> Self::Iter<'_> {
        Iter {
            current: self.head,
            list: self,
        }
    }
}

impl<'a, T, K, S> NodeCursor<'a, T> for CursorMut<'a, T, K, S>
where
    K: Clone + Copy + PartialEq,
    S: NodeStorage<Node<T, K>, Key = K>,
{
    #[inline]
    fn is_detached(&self) -> bool {
        self.current.is_none()
    }

    #[inline]
    fn next(&mut self) -> Option<&mut T> {
        let next_key = self.next?;

        let (node_prev, node_next) = {
            let n = self.list.storage.get_node(next_key)?;
            (n.prev, n.next)
        };

        self.prev = node_prev;
        self.current = Some(next_key);
        self.next = node_next;

        self.list
            .storage
            .get_node_mut(next_key)
            .map(|n| &mut n.value)
    }

    #[inline]
    fn prev(&mut self) -> Option<&mut T> {
        let prev_key = self.prev?;

        let (node_prev, node_next) = {
            let n = self.list.storage.get_node(prev_key)?;
            (n.prev, n.next)
        };

        self.prev = node_prev;
        self.current = Some(prev_key);
        self.next = node_next;

        self.list
            .storage
            .get_node_mut(prev_key)
            .map(|n| &mut n.value)
    }

    #[inline]
    fn peek_next(&mut self) -> Option<&mut T> {
        let Some(next_key) = self.next else {
            return None;
        };

        self.list
            .storage
            .get_node_mut(next_key)
            .map(|n| &mut n.value)
    }

    #[inline]
    fn peek_prev(&mut self) -> Option<&mut T> {
        let Some(prev_key) = self.prev else {
            return None;
        };

        self.list
            .storage
            .get_node_mut(prev_key)
            .map(|n| &mut n.value)
    }

    #[inline]
    fn insert_after(&mut self, value: T) -> Option<&mut T> {
        let (prev, next) = match self.current {
            Some(cur) => (Some(cur), self.next),
            None => (self.list.tail, None),
        };

        let key = self.list.storage.try_push(Node { value, prev, next })?;

        self.list.link(prev, next, key);
        self.next = Some(key);

        if self.list.tail == prev {
            self.list.tail = Some(key);
        }
        if self.list.head.is_none() {
            self.list.head = Some(key);
        }

        self.list.storage.get_node_mut(key).map(|n| &mut n.value)
    }

    #[inline]
    fn insert_before(&mut self, value: T) -> Option<&mut T> {
        let (prev, next) = match self.current {
            Some(cur) => (self.prev, Some(cur)),
            None => (None, self.next),
        };

        let key = self.list.storage.try_push(Node { value, prev, next })?;

        self.list.link(prev, next, key);

        match self.current {
            Some(_cur) => {
                self.prev = Some(key);
            }
            None => {
                self.next = Some(key);
            }
        }

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

        if self.list.tail.is_none() {
            self.list.tail = Some(key);
        }

        self.list.storage.get_node_mut(key).map(|n| &mut n.value)
    }

    #[inline]
    fn remove_current(&mut self) -> Option<T> {
        let current_key = self.current?;

        let (prev, next) = {
            let node = self.list.storage.get_node(current_key)?;
            (node.prev, node.next)
        };

        self.list.splice(prev, next);

        if self.list.head == Some(current_key) {
            self.list.head = next;
        }
        if self.list.tail == Some(current_key) {
            self.list.tail = prev;
        }

        self.current = None;
        self.prev = prev;
        self.next = next;

        self.list
            .storage
            .remove_node_at(current_key)
            .map(|n| n.value)
    }

    #[inline]
    fn remove_next(&mut self) -> Option<T> {
        let next_key = self.next?;

        let (prev, next) = {
            let node = self.list.storage.get_node(next_key)?;
            (node.prev, node.next)
        };

        self.list.splice(prev, next);

        if self.list.head == Some(next_key) {
            self.list.head = next;
        }
        if self.list.tail == Some(next_key) {
            self.list.tail = prev;
        }

        self.next = next;

        self.list.storage.remove_node_at(next_key).map(|n| n.value)
    }

    #[inline]
    fn remove_prev(&mut self) -> Option<T> {
        let prev_key = self.prev?;

        let (prev, next) = {
            let node = self.list.storage.get_node(prev_key)?;
            (node.prev, node.next)
        };

        self.list.splice(prev, next);

        if self.list.head == Some(prev_key) {
            self.list.head = next;
        }
        if self.list.tail == Some(prev_key) {
            self.list.tail = prev;
        }

        self.prev = prev;

        self.list.storage.remove_node_at(prev_key).map(|n| n.value)
    }
}

/// A list of futures that is itself a `Future`.
///
/// Implementors are expected to poll contained futures in-place. If your future
/// type is not `Unpin`, wrap it as `Pin<Box<F>>` before inserting:
///
/// ```ignore
/// tl.try_push_back(Box::pin(my_future));
/// ```
pub trait FutureList<T, R>: IndexLinkedList<T> + Future<Output = Option<R>> + Send + Sync {}

/// A simple future queue over an index-based linked list.
///
/// The list is polled from head to tail on each `poll()`. When a future resolves,
/// it is removed and its output is fed to `callback`. If the callback returns
/// `Poll::Ready(r)`, `TaskList` resolves to `Some(r)`. When the list becomes empty,
/// it resolves to `None`.
///
/// Note: `F` must be `Unpin` with this type signature. For non-`Unpin` futures,
/// store `Pin<Box<F>>` and push with `Box::pin(...)`.
pub struct TaskList<F, K, S, C, R>
where
    F: Future<Output = R> + Unpin + Send + Sync,
    K: Clone + Copy + PartialEq + Unpin + Send + Sync,
    S: NodeStorage<Node<F, K>, Key = K> + Unpin + Send + Sync,
    C: FnMut(R) -> Poll<R> + Unpin + Send + Sync,
    R: Unpin + Send + Sync,
{
    tasks: ILL<F, K, S>,
    callback: C,
    _marker: PhantomData<R>,
}

impl<F, K, S, C, R> TaskList<F, K, S, C, R>
where
    F: Future<Output = R> + Unpin + Send + Sync,
    K: Clone + Copy + PartialEq + Unpin + Send + Sync,
    S: NodeStorage<Node<F, K>, Key = K> + Unpin + Send + Sync,
    C: FnMut(R) -> Poll<R> + Unpin + Send + Sync,
    R: Unpin + Send + Sync,
{
    /// Creates a new `TaskList` with the given node storage and completion callback.
    ///
    /// This variant stores **`Unpin` futures** directly in the list and polls them in-place.
    /// If your futures are **not `Unpin`** (e.g., from `Box::pin(...)`), either:
    ///
    /// 1) Wrap them so `F = Pin<Box<YourFuture>>` and adjust `TaskList` to store `Pin<Box<F>>`,
    ///    **or**
    /// 2) Keep this signature but ensure `F: Unpin` (e.g., by using combinators that yield Unpin futures).
    ///
    /// The list is polled from head to tail on each `poll()`. When a future resolves, it is
    /// removed and its output is passed to `callback`. If the callback returns `Poll::Ready(r)`,
    /// the `TaskList` resolves to `Some(r)`. When the list becomes empty, it resolves to `None`.
    ///
    /// # Examples
    /// ```no_run
    /// # use std::{future::Future, task::Poll};
    /// # use tokio::time::{sleep, Duration};
    /// # // assuming: TaskList, ILL, ArrayStorage, Node, NodeStorage in scope
    /// let storage = ArrayStorage::<Node<tokio::time::Sleep, usize>, 128>::new();
    ///
    /// // With Unpin futures (tokio::time::Sleep is Unpin):
    /// let mut tl = TaskList::new(storage, |_r| Poll::Pending);
    /// tl.try_push_back(sleep(Duration::from_millis(10)));
    /// // .await resolves to None when all tasks complete
    /// # tokio::spawn(async move { let _ = tl.await; });
    /// ```
    #[inline]
    #[must_use]
    pub fn new(storage: S, callback: C) -> Self {
        Self {
            tasks: ILL::new(storage),
            callback,
            _marker: PhantomData,
        }
    }
}

impl<F, K, S, C, R> FutureList<F, R> for TaskList<F, K, S, C, R>
where
    F: Future<Output = R> + Unpin + Send + Sync,
    K: Clone + Copy + PartialEq + Unpin + Send + Sync,
    S: NodeStorage<Node<F, K>, Key = K> + Unpin + Send + Sync,
    C: FnMut(R) -> Poll<R> + Unpin + Send + Sync,
    R: Unpin + Send + Sync,
{
}

impl<F, K, S, C, R> IndexLinkedList<F> for TaskList<F, K, S, C, R>
where
    F: Future<Output = R> + Unpin + Send + Sync,
    K: Clone + Copy + PartialEq + Unpin + Send + Sync,
    S: NodeStorage<Node<F, K>, Key = K> + Unpin + Send + Sync,
    C: FnMut(R) -> Poll<R> + Unpin + Send + Sync,
    R: Unpin + Send + Sync,
{
    type Iter<'a>
        = Iter<'a, F, K, S>
    where
        F: 'a,
        Self: 'a;

    type Cursor<'a>
        = CursorMut<'a, F, K, S>
    where
        Self: 'a;

    #[inline]
    fn is_empty(&self) -> bool {
        self.tasks.is_empty()
    }

    #[inline]
    fn is_full(&self) -> bool {
        self.tasks.is_full()
    }

    #[inline]
    fn try_push_front(&mut self, value: F) -> Option<&mut F> {
        self.tasks.try_push_front(value)
    }

    #[inline]
    fn try_push_back(&mut self, value: F) -> Option<&mut F> {
        self.tasks.try_push_back(value)
    }

    #[inline]
    fn cursor_mut(&mut self) -> Self::Cursor<'_> {
        self.tasks.cursor_mut()
    }

    #[inline]
    fn iter(&self) -> Self::Iter<'_> {
        self.tasks.iter()
    }
}

impl<F, K, S, C, R> Future for TaskList<F, K, S, C, R>
where
    F: Future<Output = R> + Unpin + Send + Sync,
    K: Clone + Copy + PartialEq + Unpin + Send + Sync,
    S: NodeStorage<Node<F, K>, Key = K> + Unpin + Send + Sync,
    C: FnMut(R) -> Poll<R> + Unpin + Send + Sync,
    R: Unpin + Send + Sync,
{
    type Output = Option<R>;

    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<R>> {
        let TaskList {
            tasks, callback, ..
        } = self.get_mut();

        let mut cursor = tasks.cursor_mut();

        while let Some(fut) = cursor.next() {
            match Pin::new(fut).poll(cx) {
                Poll::Pending => {}
                Poll::Ready(output) => {
                    cursor.remove_current();

                    match (callback)(output) {
                        Poll::Ready(r) => {
                            return Poll::Ready(Some(r));
                        }
                        Poll::Pending => {}
                    }
                }
            }
        }

        if tasks.storage.is_empty() {
            Poll::Ready(None)
        } else {
            Poll::Pending
        }
    }
}

/// `NodeStorage` adapter for [`slab::Slab<T>`].
///
/// This implementation uses the slab index (`usize`) as the storage key and
/// forwards operations to the underlying slab:
///
/// - **Capacity:** effectively unbounded (grows as needed); `is_full()` is always `false`.
/// - **Stability:** indices are stable for the lifetime of an entry and may be
///   **reused after removal**. Any references to a removed entry are invalid.
/// - **Performance:** `insert`, `get`, `get_mut`, and `remove` are O(1) on average.
/// - **Relocation:** entries are not moved on insert/remove, so the address of a
///   value is stable until that specific entry is removed.
/// - **Key type:** `usize`.
///
/// # Examples
/// ```
/// # #[cfg(feature = "slab")]
/// # {
/// use slab::Slab;
/// use ill::{NodeStorage}; // replace with your actual path
///
/// let mut storage: Slab<i32> = Slab::new();
///
/// // Insert returns a stable key
/// let k = storage.try_push(42).unwrap();
/// assert_eq!(storage.get_node(k), Some(&42));
///
/// // Mutable access
/// *storage.get_node_mut(k).unwrap() = 7;
/// assert_eq!(storage.get_node(k), Some(&7));
///
/// // Remove and reuse
/// assert_eq!(storage.remove_node_at(k), Some(7));
/// assert!(storage.get_node(k).is_none()); // key no longer valid
/// # }
/// ```
///
/// This impl is available only with the `slab` feature enabled.
#[cfg(feature = "slab")]
impl<T> NodeStorage<T> for slab::Slab<T> {
    type Key = usize;

    #[inline]
    fn is_full(&self) -> bool {
        false
    }

    #[inline]
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[inline]
    fn try_push<'a>(&mut self, value: T) -> Option<Self::Key> {
        Some(self.insert(value))
    }

    #[inline]
    fn get_node(&self, index: Self::Key) -> Option<&T> {
        self.get(index)
    }

    #[inline]
    fn get_node_mut(&mut self, index: Self::Key) -> Option<&mut T> {
        self.get_mut(index)
    }

    #[inline]
    fn remove_node_at(&mut self, index: Self::Key) -> Option<T> {
        if self.contains(index) {
            return Some(self.remove(index));
        }

        None
    }
}

/// `NodeStorage` adapter for a **mutable reference** to [`slab::Slab<T>`].
///
/// Semantics are identical to the owned `Slab<T>` implementation; this version
/// allows passing a borrowed slab to APIs that expect a `NodeStorage`.
///
/// See the owned impl’s docs for details on capacity, stability, and performance.
#[cfg(feature = "slab")]
impl<T> NodeStorage<T> for &mut slab::Slab<T> {
    type Key = usize;

    #[inline]
    fn is_full(&self) -> bool {
        false
    }

    #[inline]
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[inline]
    fn try_push<'a>(&mut self, value: T) -> Option<Self::Key> {
        Some(self.insert(value))
    }

    #[inline]
    fn get_node(&self, index: Self::Key) -> Option<&T> {
        self.get(index)
    }

    #[inline]
    fn get_node_mut(&mut self, index: Self::Key) -> Option<&mut T> {
        self.get_mut(index)
    }

    #[inline]
    fn remove_node_at(&mut self, index: Self::Key) -> Option<T> {
        if self.contains(index) {
            return Some(self.remove(index));
        }

        None
    }
}

/// A fixed-capacity, index-addressable storage backend.
///
/// `ArrayStorage<T, N>` stores up to `N` elements in a contiguous
/// `[Option<T>; N]`. Indices (`usize`) act as stable keys into the array,
/// which makes it a simple arena for index-linked structures like `ILL`.
///
/// ### Properties
/// - **Capacity:** Compile-time constant `N` (default `32`). When full,
///   [`try_push`](NodeStorage::try_push) returns `None`.
/// - **Keys:** `usize` in `0..N`. Keys are **reused** after removal.
/// - **Stability:** Elements are **never relocated** once inserted; their
///   addresses remain stable until that slot is removed. (References become
///   invalid once the element is removed.)
/// - **Complexity:**
///   - `try_push`: **O(N)** (linear scan for a free hole)  
///   - `get_node` / `get_node_mut`: **O(1)**  
///   - `remove_node_at`: **O(1)**
/// - **No panics on bad keys:** Accessors return `None` for out-of-range or
///   empty slots instead of panicking.
/// - **No allocation:** Uses only stack/inline storage for the `[Option<T>; N]`.
///
/// ### When to use
/// - Small/medium lists with a known upper bound.
/// - Allocator-free or `no_std`-friendly scenarios (subject to your crate’s
///   own `no_std` support).
/// - You want stable indices/addresses without pointer juggling.
///
/// For unbounded or very large collections, prefer a growing backend such as
/// [`slab::Slab`](https://docs.rs/slab) (behind the `slab` feature).
///
/// ### Examples
/// Basic use with an index-linked list:
/// ```ignore
/// // assuming: ILL, Node, NodeStorage, IndexLinkedList are in scope
/// let mut list = ILL::<i32, usize, ArrayStorage<Node<i32, usize>, 8>>::new(
///     ArrayStorage::with_capacity()
/// );
/// assert!(list.try_push_back(10).is_some());
/// assert!(list.try_push_back(20).is_some());
/// assert_eq!(list.iter().copied().collect::<Vec<_>>(), vec![10, 20]);
/// ```
///
/// Creating storages of different sizes:
/// ```ignore
/// let s32  = ArrayStorage::<u64>::new();                 // N = 32
/// let s8   = ArrayStorage::<u64>::with_capacity::<8>();  // N = 8
/// let s128 = ArrayStorage::<u64>::with_capacity::<128>(); // N = 128
/// ```
///
/// ### Trait impls
/// Implements [`NodeStorage<T>`] for both `ArrayStorage<T, N>` and
/// `&mut ArrayStorage<T, N>`, using `usize` as the key type.
pub struct ArrayStorage<T, const N: usize = 32> {
    data: [Option<T>; N],
    len: usize,
}

impl<T, const N: usize> Default for ArrayStorage<T, N> {
    #[inline]
    fn default() -> Self {
        Self {
            data: std::array::from_fn(|_| None),
            len: 0,
        }
    }
}

impl<T, const N: usize> ArrayStorage<T, N> {
    /// Creates a fixed-capacity storage with the **default capacity of 32** slots.
    ///
    /// This uses the const generic default on `ArrayStorage<T, const N: usize = 32>`.
    ///
    /// # Examples
    /// ```
    /// let s = ArrayStorage::<u32>::new(); // capacity = 32
    /// ```
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Default::default()
    }
}

impl<T> ArrayStorage<T> {
    /// Creates a fixed-capacity storage with **compile-time capacity `N`**.
    ///
    /// Note: `N` is a *const generic* parameter (chosen at compile time), not a
    /// runtime argument. If you want `N = 128`, call:
    ///
    /// ```
    /// let s = ArrayStorage::<u32>::with_capacity::<128>();
    /// ```
    ///
    /// # Examples
    /// ```
    /// let s = ArrayStorage::<u32>::with_capacity::<8>();  // capacity = 8
    /// let t = ArrayStorage::<u32>::with_capacity::<64>(); // capacity = 64
    /// ```
    #[inline]
    #[must_use]
    pub fn with_capacity<const N: usize>() -> ArrayStorage<T, N> {
        ArrayStorage {
            data: std::array::from_fn(|_| None),
            len: 0,
        }
    }
}

impl<T, const N: usize> NodeStorage<T> for ArrayStorage<T, N> {
    type Key = usize;

    #[inline]
    fn is_full(&self) -> bool {
        self.len == N
    }

    #[inline]
    fn is_empty(&self) -> bool {
        self.len == 0
    }

    fn try_push(&mut self, value: T) -> Option<Self::Key> {
        for (i, slot) in self.data.iter_mut().enumerate() {
            if slot.is_none() {
                *slot = Some(value);
                self.len += 1;

                return Some(i);
            }
        }

        None
    }

    #[inline]
    fn get_node(&self, index: Self::Key) -> Option<&T> {
        self.data.get(index)?.as_ref()
    }

    #[inline]
    fn get_node_mut(&mut self, index: Self::Key) -> Option<&mut T> {
        self.data.get_mut(index)?.as_mut()
    }

    #[inline]
    fn remove_node_at(&mut self, index: Self::Key) -> Option<T> {
        if let Some(value) = self.data.get_mut(index)?.take() {
            self.len = self.len.saturating_sub(1);

            Some(value)
        } else {
            None
        }
    }
}

impl<T, const N: usize> NodeStorage<T> for &mut ArrayStorage<T, N> {
    type Key = usize;

    #[inline]
    fn is_full(&self) -> bool {
        self.len == N
    }

    #[inline]
    fn is_empty(&self) -> bool {
        self.len == 0
    }

    fn try_push(&mut self, value: T) -> Option<Self::Key> {
        for (i, slot) in self.data.iter_mut().enumerate() {
            if slot.is_none() {
                *slot = Some(value);
                self.len += 1;

                return Some(i);
            }
        }

        None
    }

    #[inline]
    fn get_node(&self, index: Self::Key) -> Option<&T> {
        self.data.get(index)?.as_ref()
    }

    #[inline]
    fn get_node_mut(&mut self, index: Self::Key) -> Option<&mut T> {
        self.data.get_mut(index)?.as_mut()
    }

    #[inline]
    fn remove_node_at(&mut self, index: Self::Key) -> Option<T> {
        if let Some(value) = self.data.get_mut(index)?.take() {
            self.len = self.len.saturating_sub(1);

            Some(value)
        } else {
            None
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Helper to build a small list [1,2,3]
    fn make_list() -> ILL<i32, usize, ArrayStorage<Node<i32, usize>, 5>> {
        let mut list = ILL::new(ArrayStorage::with_capacity());

        assert_eq!(list.try_push_back(1).map(|r| *r), Some(1));
        assert_eq!(list.try_push_back(2).map(|r| *r), Some(2));
        assert_eq!(list.try_push_back(3).map(|r| *r), Some(3));

        list
    }

    #[test]
    fn push_front_and_back() {
        let mut list = ILL::new(ArrayStorage::<Node<i32, usize>>::with_capacity::<3>());
        // push_back
        assert_eq!(list.try_push_back(10).map(|r| *r), Some(10));
        assert_eq!(list.try_push_back(20).map(|r| *r), Some(20));

        // push_front
        assert_eq!(list.try_push_front(5).map(|r| *r), Some(5));

        // list now [5,10,20]
        let vals: Vec<_> = list.iter().cloned().collect();
        assert_eq!(vals, vec![5, 10, 20]);

        // overflow
        assert!(list.try_push_back(30).is_none());
        assert!(list.try_push_front(0).is_none());
    }

    #[test]
    fn cursor_traversal_and_peek() {
        let mut list = make_list(); // [1,2,3]

        {
            let mut c = list.cursor_mut();

            // next() steps
            assert_eq!(c.next().map(|r| *r), Some(1));
            assert_eq!(c.peek_next().map(|r| *r), Some(2));
            assert_eq!(c.next().map(|r| *r), Some(2));

            // prev() and peek_prev
            assert_eq!(c.peek_prev().map(|r| *r), Some(1));
            assert_eq!(c.prev().map(|r| *r), Some(1));

            // at head, prev() returns None
            assert_eq!(c.prev(), None);
        }
    }

    #[test]
    fn iter_order_after_head_tail_inserts() {
        let mut list = ILL::new(ArrayStorage::<Node<i32, usize>>::with_capacity::<8>());

        // start empty
        assert!(list.is_empty());

        // push front/back directly -> [1,2,4,5]
        list.try_push_front(2);
        list.try_push_front(1);
        list.try_push_back(4);
        list.try_push_back(5);
        assert_eq!(list.iter().cloned().collect::<Vec<_>>(), vec![1, 2, 4, 5]);

        {
            let mut c = list.cursor_mut();

            // Insert new head without stepping onto the head (current=None, next=head):
            assert_eq!(c.insert_before(0).map(|x| *x), Some(0));

            // Walk to the old tail (5)
            assert_eq!(c.next().map(|x| *x), Some(0));
            assert_eq!(c.next().map(|x| *x), Some(1));
            assert_eq!(c.next().map(|x| *x), Some(2));
            assert_eq!(c.next().map(|x| *x), Some(4));
            assert_eq!(c.next().map(|x| *x), Some(5));

            // Insert new tail by calling insert_after while sitting on tail
            assert_eq!(c.insert_after(6).map(|x| *x), Some(6));
        }

        let vals: Vec<_> = list.iter().cloned().collect();
        assert_eq!(vals, vec![0, 1, 2, 4, 5, 6]);
    }

    #[test]
    fn insert_before_and_after_keep_gap_correct() {
        let mut list = make_list(); // [1,2,3]
        let mut c = list.cursor_mut();

        // Land on 2
        c.next(); // 1
        c.next(); // 2

        // insert_after(9) -> [1,2,9,3]; next() sees 9
        assert_eq!(c.insert_after(9).map(|x| *x), Some(9));
        assert_eq!(c.next().map(|x| *x), Some(9));

        // insert_before(8) with current=9 -> true-before: [1,2,8,9,3]
        assert_eq!(c.insert_before(8).map(|x| *x), Some(8));

        // now prev of current(9) is 8
        assert_eq!(c.peek_prev().map(|x| *x), Some(8));

        let vals: Vec<_> = list.iter().cloned().collect();
        assert_eq!(vals, vec![1, 2, 8, 9, 3]);
    }

    #[test]
    fn cursor_insert_before_and_after() {
        let mut list = make_list(); // [1,2,3]

        {
            let mut c = list.cursor_mut();
            // position at 2
            c.next(); // 1
            c.next(); // 2

            // insert_after(4): [1,2,4,3]
            assert_eq!(c.insert_after(4).map(|r| *r), Some(4));

            // next() should now see 4
            assert_eq!(c.next().map(|r| *r), Some(4));

            // insert_before(5) while current is 4 -> true-before: [1,2,5,4,3]
            assert_eq!(c.insert_before(5).map(|r| *r), Some(5));

            // with true-before semantics, the node before current(4) is now 5
            assert_eq!(c.peek_prev().map(|r| *r), Some(5));
        }

        let vals: Vec<_> = list.iter().cloned().collect();
        assert_eq!(vals, vec![1, 2, 5, 4, 3]);
    }

    #[test]
    fn remove_current_next_prev() {
        let mut list = make_list(); // [1,2,3]

        // remove next (1) -> returns 1, list [2,3]
        {
            let mut c = list.cursor_mut();

            assert_eq!(c.remove_next(), Some(1));
        }

        assert_eq!(list.iter().cloned().collect::<Vec<_>>(), vec![2, 3]);

        // move to 2, remove current (2) -> [3]
        {
            let mut c = list.cursor_mut();

            assert_eq!(c.next().map(|r| *r), Some(2));
            assert_eq!(c.remove_current(), Some(2));
        }

        assert_eq!(list.iter().cloned().collect::<Vec<_>>(), vec![3]);

        // peek_prev is None, remove_prev returns None
        {
            let mut c = list.cursor_mut();

            assert_eq!(c.peek_prev(), None);
            assert_eq!(c.remove_prev(), None);
        }

        // remove next (3) via cursor at empty current->next=3
        {
            let mut c = list.cursor_mut();

            assert_eq!(c.remove_next(), Some(3));
        }

        assert!(list.iter().next().is_none());

        // now list is empty: head and tail should be None
        assert!(list.cursor_mut().next().is_none());
    }

    #[test]
    fn single_element_edge_cases() {
        let mut list = ILL::new(ArrayStorage::<Node<i32, usize>>::with_capacity::<2>());
        // start empty
        assert!(list.iter().next().is_none());

        // push one element
        list.try_push_back(42).unwrap();

        // cursor_mut.next sees it
        {
            let mut c = list.cursor_mut();

            assert_eq!(c.next().map(|r| *r), Some(42));
            // removing current should empty list
            assert_eq!(c.remove_current(), Some(42));
        }

        assert!(list.iter().next().is_none());

        // re-push to test insert_after on empty cursor
        list.try_push_front(7).unwrap();

        {
            let mut c = list.cursor_mut();
            // at empty current, next=7; insert_after should work
            assert_eq!(c.insert_after(8).map(|r| *r), Some(8));
        }

        let vals = list.iter().cloned().collect::<Vec<_>>();

        assert_eq!(vals, vec![7, 8]);
    }

    #[test]
    fn storage_full_and_empty() {
        let mut storage = ArrayStorage::<i32>::with_capacity::<1>();
        assert!(storage.is_empty());
        assert!(!storage.is_full());

        assert_eq!(storage.try_push(100), Some(0));
        assert!(storage.is_full());
        assert!(!storage.is_empty());

        assert_eq!(storage.get_node(0), Some(&100));
        assert_eq!(storage.remove_node_at(0), Some(100));
        assert!(storage.is_empty());
    }

    // === 2) Perf test: 1,000,000 timers in slab ==================================
    //
    // This is heavy. It’s ignored by default. Run with:
    // cargo test --release --features slab -- --ignored --nocapture
    //
    // NOTE: Uses zero-duration sleeps to complete in the next tick for throughput.
    #[cfg(feature = "slab")]
    #[tokio::test(flavor = "multi_thread", worker_threads = 4)]
    #[ignore]
    async fn tasklist_slab_million_timers_await_all() {
        use std::time::Duration;
        use std::time::Instant;
        use tokio::time::sleep;
        const TIMERS: usize = 10_000;

        let mut counter = 0;
        let storage = slab::Slab::with_capacity(TIMERS);
        let mut tl = TaskList::new(storage, |_| {
            counter += 1;
            Poll::Pending
        });

        for i in 0..TIMERS {
            if (i % (TIMERS as f64 * 0.1) as usize) == 0 {
                println!("Created +{} timers...", (TIMERS as f64 * 0.1) as usize)
            }

            assert!(
                tl.try_push_back(Box::pin(sleep(Duration::from_millis(500))))
                    .is_some()
            );
        }

        let start = Instant::now();
        let res = tl.await; // resolves to None once all timers have fired & been removed
        let elapsed = start.elapsed();

        assert_eq!(res, None);
        assert_eq!(counter, TIMERS);

        eprintln!("completed {:#?} timers in {:?}", TIMERS, elapsed);
    }
}