//! Slot arena with stable [`SlotId`] handles.
//!
//! Provides arena-style allocation where elements are stored in a `Vec<Option<T>>`
//! and freed slots are tracked in a free list for reuse. Handles ([`SlotId`]) remain
//! stable across insertions and deletions, making this ideal for graph structures,
//! linked lists, and policy metadata.
//!
//! ## Architecture
//!
//! ```text
//! ┌────────────────────────────────────────────────────────────────────────────┐
//! │                           SlotArena Layout                                 │
//! │                                                                            │
//! │   ┌───────────────────────────────────────────────────────────────────┐    │
//! │   │  slots: Vec<Option<T>>                                            │    │
//! │   │                                                                   │    │
//! │   │    index:   0        1        2        3        4        5        │    │
//! │   │           ┌────┐  ┌────┐  ┌────┐  ┌────┐  ┌────┐  ┌────┐          │    │
//! │   │           │ T  │  │None│  │ T  │  │None│  │ T  │  │None│          │    │
//! │   │           │"a" │  │    │  │"c" │  │    │  │"e" │  │    │          │    │
//! │   │           └────┘  └────┘  └────┘  └────┘  └────┘  └────┘          │    │
//! │   │              ▲       │       ▲       │       ▲       │            │    │
//! │   │              │       │       │       │       │       │            │    │
//! │   │           SlotId(0)  │   SlotId(2)   │   SlotId(4)   │            │    │
//! │   │                      │               │               │            │    │
//! │   └──────────────────────┼───────────────┼───────────────┼────────────┘    │
//! │                          │               │               │                 │
//! │   ┌──────────────────────┼───────────────┼───────────────┼────────────┐    │
//! │   │  free_list: Vec<usize>               │               │            │    │
//! │   │                      │               │               │            │    │
//! │   │              ┌───────┴───────┬───────┴───────┬───────┴───────┐    │    │
//! │   │              │       1       │       3       │       5       │    │    │
//! │   │              └───────────────┴───────────────┴───────────────┘    │    │
//! │   │                                                                   │    │
//! │   │              ◄─────── pop() returns 5 for next insert ──────►     │    │
//! │   └───────────────────────────────────────────────────────────────────┘    │
//! │                                                                            │
//! │   len: 3  (number of live entries, not slots.len())                        │
//! └────────────────────────────────────────────────────────────────────────────┘
//!
//! Slot Lifecycle
//! ──────────────
//!
//!   insert("x"):
//!     ├─► free_list.pop() ──► Some(idx) ──► slots[idx] = Some("x")
//!     │                                      return SlotId(idx)
//!     │
//!     └─► None ──► slots.push(Some("x"))
//!                  return SlotId(slots.len() - 1)
//!
//!   remove(SlotId(2)):
//!     slots[2].take() ──► Some("c") ──► free_list.push(2)
//!                                       return Some("c")
//!
//!   get(SlotId(2)):
//!     slots.get(2) ──► Some(&slot) ──► slot.as_ref() ──► Option<&T>
//!
//! Arena Variants
//! ──────────────
//!
//!   ┌─────────────────────────────────────────────────────────────────────┐
//!   │ SlotArena<T>              Single-threaded, direct &T access         │
//!   ├─────────────────────────────────────────────────────────────────────┤
//!   │ ConcurrentSlotArena<T>    Thread-safe via RwLock                    │
//!   │                           Uses closures: get_with(id, |v| ...)      │
//!   ├─────────────────────────────────────────────────────────────────────┤
//!   │ ShardedSlotArena<T>       Multiple RwLock-protected arenas          │
//!   │                           Round-robin insert, ShardedSlotId handle  │
//!   └─────────────────────────────────────────────────────────────────────┘
//! ```
//!
//! ## Key Components
//!
//! - [`SlotId`]: Stable handle wrapping a `usize` index
//! - [`SlotArena`]: Single-threaded arena with O(1) operations
//! - [`ConcurrentSlotArena`]: Thread-safe wrapper with closure-based access
//! - [`ShardedSlotArena`]: Sharded arena for high-concurrency workloads
//! - [`ShardedSlotId`]: Handle containing shard index + slot id
//!
//! ## Operations
//!
//! | Operation     | Description                              | Complexity |
//! |---------------|------------------------------------------|------------|
//! | [`insert`]    | Add value, reuse free slot if available  | O(1)       |
//! | [`remove`]    | Remove and return value, free the slot   | O(1)       |
//! | [`get`]       | Get reference by SlotId                  | O(1)       |
//! | [`get_mut`]   | Get mutable reference by SlotId          | O(1)       |
//! | [`contains`]  | Check if SlotId is valid                 | O(1)       |
//! | [`iter`] / [`iter_mut`] | Iterate over live entries      | O(n)       |
//! | [`into_iter`] | Consuming iteration over entries         | O(n)       |
//!
//! [`insert`]: SlotArena::insert
//! [`remove`]: SlotArena::remove
//! [`get`]: SlotArena::get
//! [`get_mut`]: SlotArena::get_mut
//! [`contains`]: SlotArena::contains
//! [`iter`]: SlotArena::iter
//! [`iter_mut`]: SlotArena::iter_mut
//! [`into_iter`]: SlotArena#impl-IntoIterator
//!
//! ## Performance Characteristics
//!
//! - **No per-operation allocation**: Slots are reused, Vec grows as needed
//! - **Cache-friendly**: Elements stored contiguously in memory
//! - **Stable handles**: SlotId values remain valid until removed
//! - **O(1) operations**: All single-element operations are constant time
//!
//! ## When to Use
//!
//! - Intrusive data structures (linked lists, trees, graphs)
//! - Policy metadata storage (LRU list nodes, frequency counters)
//! - Any scenario requiring stable handles that survive mutations
//! - Memory pools where allocation churn is a concern
//!
//! ## Example Usage
//!
//! ```
//! use cachekit::ds::SlotArena;
//!
//! let mut arena = SlotArena::new();
//!
//! // Insert values and get stable handles
//! let id_a = arena.insert("alice");
//! let id_b = arena.insert("bob");
//!
//! // Access by handle
//! assert_eq!(arena.get(id_a), Some(&"alice"));
//!
//! // Remove frees the slot
//! assert_eq!(arena.remove(id_b), Some("bob"));
//!
//! // Next insert reuses freed slot
//! let id_c = arena.insert("carol");
//! assert_eq!(id_b.index(), id_c.index());  // Same underlying index
//! ```
//!
//! ## Thread Safety
//!
//! - [`SlotArena`]: Not thread-safe, use in single-threaded contexts
//! - [`ConcurrentSlotArena`]: Thread-safe via `parking_lot::RwLock`
//! - [`ShardedSlotArena`]: Thread-safe with per-shard locks
//!
//! ## Implementation Notes
//!
//! - `SlotId` stores the generation value assigned by the arena; the arena
//!   maintains the authoritative generation counter and validates `SlotId`s
//!   against it so that stale handles return `None`
//! - Physical slot indices may be reused after removal, but the
//!   generation counter prevents ABA hazards
//! - `len()` tracks live entries, not `slots.len()`
//! - `debug_validate_invariants()` available in debug/test builds

/// Stable, generation-checked handle into a [`SlotArena`].
///
/// Wraps a `usize` slot index together with a `u32` generation counter.
/// The generation is bumped every time a slot is freed, so a stale handle
/// whose slot has been reused will fail the generation check and return
/// `None` instead of silently accessing the wrong value.
///
/// # Example
///
/// ```
/// use cachekit::ds::SlotArena;
///
/// let mut arena = SlotArena::new();
/// let id = arena.insert(42);
///
/// // SlotId provides O(1) access
/// assert_eq!(arena.get(id), Some(&42));
///
/// // Inspect raw index for debugging
/// println!("Value stored at index {}", id.index());
///
/// // After removal, same index may be reused but stale handle is invalid
/// arena.remove(id);
/// let new_id = arena.insert(100);
/// assert_eq!(id.index(), new_id.index());
/// assert_eq!(arena.get(id), None);       // stale handle → None
/// assert_eq!(arena.get(new_id), Some(&100));
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
pub struct SlotId {
    pub(crate) index: usize,
    pub(crate) generation: u32,
}

impl SlotId {
    /// Returns the underlying slot index.
    ///
    /// Useful for debugging, logging, or custom data structures that need
    /// to work with raw indices.
    pub fn index(self) -> usize {
        self.index
    }

    /// Returns the generation counter.
    ///
    /// A higher generation means the physical slot has been reused more
    /// times. Two `SlotId`s with the same index but different generations
    /// refer to different logical entries.
    pub fn generation(self) -> u32 {
        self.generation
    }
}

impl std::fmt::Display for SlotId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "slot[{}:gen{}]", self.index, self.generation)
    }
}

/// Single-threaded arena with stable [`SlotId`] handles and O(1) operations.
///
/// Stores values in a `Vec<Option<T>>` and reuses freed slots via a free list.
/// Ideal for graph structures, linked lists, and policy metadata where stable
/// handles are needed.
///
/// # Example
///
/// ```
/// use cachekit::ds::SlotArena;
///
/// let mut arena = SlotArena::new();
///
/// // Insert returns stable handles
/// let a = arena.insert("first");
/// let b = arena.insert("second");
/// let c = arena.insert("third");
///
/// assert_eq!(arena.len(), 3);
/// assert_eq!(arena.get(b), Some(&"second"));
///
/// // Remove frees the slot
/// arena.remove(b);
/// assert_eq!(arena.len(), 2);
/// assert_eq!(arena.get(b), None);
///
/// // Next insert reuses the freed slot
/// let d = arena.insert("fourth");
/// assert_eq!(b.index(), d.index());
///
/// // Iterate over live entries
/// for (id, value) in arena.iter() {
///     println!("{}: {}", id.index(), value);
/// }
/// ```
///
/// # Use Case: Intrusive Linked List
///
/// ```
/// use cachekit::ds::{SlotArena, SlotId};
///
/// struct Node {
///     value: i32,
///     next: Option<SlotId>,
/// }
///
/// let mut arena = SlotArena::new();
///
/// // Build a linked list: 1 -> 2 -> 3
/// let c = arena.insert(Node { value: 3, next: None });
/// let b = arena.insert(Node { value: 2, next: Some(c) });
/// let a = arena.insert(Node { value: 1, next: Some(b) });
///
/// // Traverse
/// let mut current = Some(a);
/// while let Some(id) = current {
///     let node = arena.get(id).unwrap();
///     println!("{}", node.value);
///     current = node.next;
/// }
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SlotArena<T> {
    slots: Vec<Option<T>>,
    generations: Vec<u32>,
    free_list: Vec<usize>,
    len: usize,
}

impl<T> SlotArena<T> {
    /// Creates an empty arena.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let arena: SlotArena<String> = SlotArena::new();
    /// assert!(arena.is_empty());
    /// ```
    pub fn new() -> Self {
        Self {
            slots: Vec::new(),
            generations: Vec::new(),
            free_list: Vec::new(),
            len: 0,
        }
    }

    /// Creates an empty arena with pre-allocated capacity.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let arena: SlotArena<i32> = SlotArena::with_capacity(100);
    /// assert!(arena.capacity() >= 100);
    /// assert!(arena.is_empty());
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            slots: Vec::with_capacity(capacity),
            generations: Vec::with_capacity(capacity),
            free_list: Vec::new(),
            len: 0,
        }
    }

    /// Inserts a value and returns its [`SlotId`].
    ///
    /// Reuses a freed slot if available, otherwise grows the internal Vec.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let id = arena.insert("hello");
    /// assert_eq!(arena.get(id), Some(&"hello"));
    /// ```
    #[inline]
    pub fn insert(&mut self, value: T) -> SlotId {
        let idx = if let Some(idx) = self.free_list.pop() {
            self.slots[idx] = Some(value);
            idx
        } else {
            self.slots.push(Some(value));
            self.generations.push(0);
            self.slots.len() - 1
        };
        self.len += 1;
        SlotId {
            index: idx,
            generation: self.generations[idx],
        }
    }

    /// Removes and returns the value at `id`, freeing the slot for reuse.
    ///
    /// Returns `None` if the slot is empty or out of bounds.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let id = arena.insert(42);
    ///
    /// assert_eq!(arena.remove(id), Some(42));
    /// assert_eq!(arena.remove(id), None);  // Already removed
    /// ```
    #[inline]
    pub fn remove(&mut self, id: SlotId) -> Option<T> {
        let idx = id.index;
        if *self.generations.get(idx)? != id.generation {
            return None;
        }
        let value = self.slots[idx].take()?;
        self.generations[idx] = self.generations[idx].wrapping_add(1);
        self.free_list.push(idx);
        self.len -= 1;
        Some(value)
    }

    /// Returns a shared reference to the value at `id`.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let id = arena.insert("value");
    ///
    /// assert_eq!(arena.get(id), Some(&"value"));
    /// ```
    #[inline]
    pub fn get(&self, id: SlotId) -> Option<&T> {
        let idx = id.index;
        if *self.generations.get(idx)? != id.generation {
            return None;
        }
        self.slots[idx].as_ref()
    }

    /// Returns a mutable reference to the value at `id`.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let id = arena.insert(1);
    ///
    /// if let Some(v) = arena.get_mut(id) {
    ///     *v = 2;
    /// }
    /// assert_eq!(arena.get(id), Some(&2));
    /// ```
    #[inline]
    pub fn get_mut(&mut self, id: SlotId) -> Option<&mut T> {
        let idx = id.index;
        if *self.generations.get(idx)? != id.generation {
            return None;
        }
        self.slots[idx].as_mut()
    }

    /// Returns `true` if `id` refers to a live slot.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let id = arena.insert(1);
    ///
    /// assert!(arena.contains(id));
    /// arena.remove(id);
    /// assert!(!arena.contains(id));
    /// ```
    #[inline]
    pub fn contains(&self, id: SlotId) -> bool {
        let idx = id.index;
        self.generations
            .get(idx)
            .is_some_and(|&g| g == id.generation && self.slots[idx].is_some())
    }

    /// Returns `true` if the raw `index` is in bounds and occupied.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let id = arena.insert("value");
    ///
    /// assert!(arena.contains_index(id.index()));
    /// assert!(!arena.contains_index(999));
    /// ```
    pub fn contains_index(&self, index: usize) -> bool {
        self.slots
            .get(index)
            .map(|slot| slot.is_some())
            .unwrap_or(false)
    }

    /// Returns the number of live entries.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// assert_eq!(arena.len(), 0);
    ///
    /// arena.insert("a");
    /// arena.insert("b");
    /// assert_eq!(arena.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the arena has no live entries.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// assert!(arena.is_empty());
    ///
    /// let id = arena.insert(1);
    /// assert!(!arena.is_empty());
    ///
    /// arena.remove(id);
    /// assert!(arena.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the backing Vec capacity (slots that fit without reallocation).
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let arena: SlotArena<i32> = SlotArena::with_capacity(100);
    /// assert!(arena.capacity() >= 100);
    /// ```
    pub fn capacity(&self) -> usize {
        self.slots.capacity()
    }

    /// Reserves capacity for at least `additional` more slots.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena: SlotArena<i32> = SlotArena::new();
    /// arena.reserve(100);
    /// assert!(arena.capacity() >= 100);
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        self.slots.reserve(additional);
        self.generations.reserve(additional);
    }

    /// Shrinks internal storage to fit the current state.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena: SlotArena<i32> = SlotArena::with_capacity(1000);
    /// arena.insert(1);
    /// arena.shrink_to_fit();
    /// // Capacity reduced (exact value is implementation-defined)
    /// ```
    pub fn shrink_to_fit(&mut self) {
        self.slots.shrink_to_fit();
        self.generations.shrink_to_fit();
        self.free_list.shrink_to_fit();
    }

    /// Clears all entries and shrinks internal storage.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::with_capacity(100);
    /// arena.insert("a");
    /// arena.insert("b");
    ///
    /// arena.clear_shrink();
    /// assert!(arena.is_empty());
    /// ```
    pub fn clear_shrink(&mut self) {
        self.clear();
        self.shrink_to_fit();
    }

    /// Removes all entries and resets internal state.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let a = arena.insert("a");
    /// let b = arena.insert("b");
    ///
    /// arena.clear();
    /// assert!(arena.is_empty());
    /// assert!(!arena.contains(a));
    /// assert!(!arena.contains(b));
    /// ```
    pub fn clear(&mut self) {
        self.slots.clear();
        self.generations.clear();
        self.free_list.clear();
        self.len = 0;
    }

    /// Returns an iterator over live `(SlotId, &T)` pairs in slot order.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// arena.insert("a");
    /// arena.insert("b");
    ///
    /// let values: Vec<_> = arena.iter().map(|(_, v)| *v).collect();
    /// assert_eq!(values, vec!["a", "b"]);
    /// ```
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            inner: self.slots.iter().enumerate(),
            generations: &self.generations,
        }
    }

    /// Returns an iterator over live `(SlotId, &mut T)` pairs in slot order.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// arena.insert(1);
    /// arena.insert(2);
    ///
    /// for (_, v) in arena.iter_mut() {
    ///     *v += 10;
    /// }
    ///
    /// let vals: Vec<_> = arena.iter().map(|(_, v)| *v).collect();
    /// assert_eq!(vals, vec![11, 12]);
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            inner: self.slots.iter_mut().enumerate(),
            generations: &self.generations,
        }
    }

    /// Returns an iterator over live [`SlotId`]s only.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// let a = arena.insert("a");
    /// let b = arena.insert("b");
    /// arena.remove(a);
    ///
    /// let ids: Vec<_> = arena.iter_ids().collect();
    /// assert_eq!(ids.len(), 1);
    /// assert!(ids.contains(&b));
    /// ```
    pub fn iter_ids(&self) -> IterIds<'_, T> {
        IterIds { inner: self.iter() }
    }

    #[cfg(any(test, debug_assertions))]
    /// Returns a debug snapshot of arena internals.
    pub fn debug_snapshot(&self) -> SlotArenaSnapshot {
        let mut free_list = self.free_list.clone();
        free_list.sort_unstable();
        let mut live_ids: Vec<_> = self.iter_ids().collect();
        live_ids.sort_by_key(|id| id.index());
        SlotArenaSnapshot {
            len: self.len,
            slots_len: self.slots.len(),
            free_list,
            live_ids,
        }
    }

    /// Returns an approximate memory footprint in bytes.
    ///
    /// Includes the struct itself, slot storage, and free list.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena: SlotArena<u64> = SlotArena::with_capacity(100);
    /// let bytes = arena.approx_bytes();
    /// assert!(bytes > 0);
    /// ```
    pub fn approx_bytes(&self) -> usize {
        std::mem::size_of::<Self>()
            + self.slots.capacity() * std::mem::size_of::<Option<T>>()
            + self.generations.capacity() * std::mem::size_of::<u32>()
            + self.free_list.capacity() * std::mem::size_of::<usize>()
    }

    #[cfg(any(test, debug_assertions))]
    /// Validates internal invariants (debug/test builds only).
    pub fn debug_validate_invariants(&self) {
        assert_eq!(self.slots.len(), self.generations.len());

        let live_count = self.slots.iter().filter(|slot| slot.is_some()).count();
        assert_eq!(self.len, live_count);
        assert!(self.len <= self.slots.len());

        let mut seen_free = std::collections::HashSet::new();
        for &idx in &self.free_list {
            assert!(idx < self.slots.len());
            assert!(self.slots[idx].is_none());
            assert!(seen_free.insert(idx));
        }

        assert_eq!(self.slots.len(), self.free_list.len() + self.len);
    }
}

#[cfg(any(test, debug_assertions))]
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct SlotArenaSnapshot {
    pub len: usize,
    pub slots_len: usize,
    pub free_list: Vec<usize>,
    pub live_ids: Vec<SlotId>,
}

/// Stable handle into a [`ShardedSlotArena`].
///
/// Contains both the shard index and the [`SlotId`] within that shard.
/// Required for O(1) access since the shard must be known to locate the value.
///
/// # Example
///
/// ```
/// use cachekit::ds::ShardedSlotArena;
///
/// let arena = ShardedSlotArena::new(4);
/// let id = arena.insert(42);
///
/// // Inspect shard and slot
/// println!("Shard {}, Slot {}", id.shard(), id.slot().index());
///
/// // Access value
/// assert_eq!(arena.get_with(id, |v| *v), Some(42));
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
#[cfg(feature = "concurrency")]
pub struct ShardedSlotId {
    shard: usize,
    slot: SlotId,
}

#[cfg(feature = "concurrency")]
impl ShardedSlotId {
    /// Returns the shard index.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(4);
    /// let id = arena.insert(42);
    /// assert!(id.shard() < 4);
    /// ```
    pub fn shard(self) -> usize {
        self.shard
    }

    /// Returns the [`SlotId`] within the shard.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// let id = arena.insert("value");
    /// let slot = id.slot();
    /// // slot.index() is the position within the shard
    /// ```
    pub fn slot(self) -> SlotId {
        self.slot
    }
}

#[cfg(feature = "concurrency")]
impl std::fmt::Display for ShardedSlotId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "slot[shard{}:{}:gen{}]",
            self.shard, self.slot.index, self.slot.generation
        )
    }
}

/// Thread-safe sharded arena with multiple `RwLock`-protected [`SlotArena`]s.
///
/// Distributes inserts across shards in round-robin fashion to reduce
/// contention. Each shard has its own lock, so operations on different
/// shards can proceed in parallel.
///
/// # Use Cases
///
/// - High-concurrency metadata storage
/// - When a single `ConcurrentSlotArena` becomes a bottleneck
/// - Workloads with many concurrent writers
///
/// # Example
///
/// ```
/// use std::sync::Arc;
/// use std::thread;
/// use cachekit::ds::ShardedSlotArena;
///
/// let arena = Arc::new(ShardedSlotArena::new(4));
///
/// // Spawn writers
/// let handles: Vec<_> = (0..4).map(|_| {
///     let arena = Arc::clone(&arena);
///     thread::spawn(move || {
///         for i in 0..100 {
///             arena.insert(i);
///         }
///     })
/// }).collect();
///
/// for h in handles {
///     h.join().unwrap();
/// }
///
/// assert_eq!(arena.len(), 400);
/// assert_eq!(arena.shard_count(), 4);
/// ```
#[cfg(feature = "concurrency")]
#[derive(Debug)]
pub struct ShardedSlotArena<T> {
    shards: Vec<parking_lot::RwLock<SlotArena<T>>>,
    selector: crate::ds::ShardSelector,
    next_shard: std::sync::atomic::AtomicUsize,
}

#[cfg(feature = "concurrency")]
impl<T> ShardedSlotArena<T> {
    /// Creates a sharded arena with the specified number of shards.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<i32> = ShardedSlotArena::new(8);
    /// assert_eq!(arena.shard_count(), 8);
    /// ```
    pub fn new(shards: usize) -> Self {
        let shards = shards.max(1);
        let mut arenas = Vec::with_capacity(shards);
        for _ in 0..shards {
            arenas.push(parking_lot::RwLock::new(SlotArena::new()));
        }
        Self {
            shards: arenas,
            selector: crate::ds::ShardSelector::new(shards, 0),
            next_shard: std::sync::atomic::AtomicUsize::new(0),
        }
    }

    /// Creates a sharded arena with pre-allocated capacity per shard.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// // 4 shards, each pre-allocated for 1000 entries
    /// let arena: ShardedSlotArena<String> = ShardedSlotArena::with_capacity(4, 1000);
    /// assert_eq!(arena.shard_count(), 4);
    /// ```
    pub fn with_capacity(shards: usize, capacity: usize) -> Self {
        let shards = shards.max(1);
        let mut arenas = Vec::with_capacity(shards);
        for _ in 0..shards {
            arenas.push(parking_lot::RwLock::new(SlotArena::with_capacity(capacity)));
        }
        Self {
            shards: arenas,
            selector: crate::ds::ShardSelector::new(shards, 0),
            next_shard: std::sync::atomic::AtomicUsize::new(0),
        }
    }

    /// Alias for [`with_capacity`](Self::with_capacity).
    #[deprecated(since = "0.6.0", note = "use `with_capacity` instead")]
    pub fn with_shards(shards: usize, capacity_per_shard: usize) -> Self {
        Self::with_capacity(shards, capacity_per_shard)
    }

    /// Creates a sharded arena with a custom hash seed for shard selection.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// // Custom seed for deterministic shard selection
    /// let arena: ShardedSlotArena<i32> = ShardedSlotArena::with_shards_seed(4, 100, 42);
    /// assert_eq!(arena.shard_count(), 4);
    /// ```
    pub fn with_shards_seed(shards: usize, capacity_per_shard: usize, seed: u64) -> Self {
        let shards = shards.max(1);
        let mut arenas = Vec::with_capacity(shards);
        for _ in 0..shards {
            arenas.push(parking_lot::RwLock::new(SlotArena::with_capacity(
                capacity_per_shard,
            )));
        }
        Self {
            shards: arenas,
            selector: crate::ds::ShardSelector::new(shards, seed),
            next_shard: std::sync::atomic::AtomicUsize::new(0),
        }
    }

    /// Returns the shard index for a key using the configured hash selector.
    ///
    /// Useful for co-locating related data in the same shard.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<String> = ShardedSlotArena::new(8);
    /// let shard = arena.shard_for_key(&"my_key");
    /// assert!(shard < 8);
    /// ```
    pub fn shard_for_key<K: std::hash::Hash>(&self, key: &K) -> usize {
        self.selector.shard_for_key(key)
    }

    /// Returns the number of shards.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<i32> = ShardedSlotArena::new(16);
    /// assert_eq!(arena.shard_count(), 16);
    /// ```
    pub fn shard_count(&self) -> usize {
        self.shards.len()
    }

    /// Inserts a value into the next shard (round-robin) and returns its handle.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// let a = arena.insert("first");
    /// let b = arena.insert("second");
    ///
    /// // Inserts alternate between shards
    /// assert_ne!(a.shard(), b.shard());
    /// ```
    pub fn insert(&self, value: T) -> ShardedSlotId {
        let shard = self
            .next_shard
            .fetch_add(1, std::sync::atomic::Ordering::Relaxed)
            % self.shards.len();
        let mut arena = self.shards[shard].write();
        let slot = arena.insert(value);
        ShardedSlotId { shard, slot }
    }

    /// Removes and returns the value at `id`.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// let id = arena.insert(42);
    ///
    /// assert_eq!(arena.remove(id), Some(42));
    /// assert_eq!(arena.remove(id), None);  // Already removed
    /// ```
    pub fn remove(&self, id: ShardedSlotId) -> Option<T> {
        let mut arena = self.shards.get(id.shard)?.write();
        arena.remove(id.slot)
    }

    /// Runs a closure on a shared reference to the value at `id`.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// let id = arena.insert(vec![1, 2, 3]);
    ///
    /// let len = arena.get_with(id, |v| v.len());
    /// assert_eq!(len, Some(3));
    /// ```
    pub fn get_with<R>(&self, id: ShardedSlotId, f: impl FnOnce(&T) -> R) -> Option<R> {
        let arena = self.shards.get(id.shard)?.read();
        arena.get(id.slot).map(f)
    }

    /// Runs a closure on a mutable reference to the value at `id`.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// let id = arena.insert(10);
    ///
    /// arena.get_mut_with(id, |v| *v += 5);
    /// assert_eq!(arena.get_with(id, |v| *v), Some(15));
    /// ```
    pub fn get_mut_with<R>(&self, id: ShardedSlotId, f: impl FnOnce(&mut T) -> R) -> Option<R> {
        let mut arena = self.shards.get(id.shard)?.write();
        arena.get_mut(id.slot).map(f)
    }

    /// Returns `true` if `id` refers to a live slot.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// let id = arena.insert("value");
    ///
    /// assert!(arena.contains(id));
    /// arena.remove(id);
    /// assert!(!arena.contains(id));
    /// ```
    pub fn contains(&self, id: ShardedSlotId) -> bool {
        self.shards
            .get(id.shard)
            .map(|arena| arena.read().contains(id.slot))
            .unwrap_or(false)
    }

    /// Returns the total number of live entries across all shards.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(4);
    /// arena.insert(1);
    /// arena.insert(2);
    /// arena.insert(3);
    ///
    /// assert_eq!(arena.len(), 3);
    /// ```
    pub fn len(&self) -> usize {
        self.shards.iter().map(|arena| arena.read().len()).sum()
    }

    /// Returns `true` if all shards are empty.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<i32> = ShardedSlotArena::new(2);
    /// assert!(arena.is_empty());
    ///
    /// arena.insert(1);
    /// assert!(!arena.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.shards.iter().all(|s| s.read().is_empty())
    }

    /// Reserves capacity in each shard.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<i32> = ShardedSlotArena::new(4);
    /// arena.reserve(100);  // Each shard gets 100 additional capacity
    /// ```
    pub fn reserve(&self, additional: usize) {
        for arena in &self.shards {
            arena.write().reserve(additional);
        }
    }

    /// Shrinks all shards to fit their current state.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<i32> = ShardedSlotArena::with_capacity(4, 1000);
    /// arena.insert(1);
    /// arena.shrink_to_fit();
    /// ```
    pub fn shrink_to_fit(&self) {
        for arena in &self.shards {
            arena.write().shrink_to_fit();
        }
    }

    /// Clears all shards and shrinks storage.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// arena.insert(1);
    /// arena.insert(2);
    ///
    /// arena.clear_shrink();
    /// assert!(arena.is_empty());
    /// ```
    pub fn clear_shrink(&self) {
        for arena in &self.shards {
            arena.write().clear_shrink();
        }
    }

    /// Returns approximate memory footprint across all shards.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena: ShardedSlotArena<u64> = ShardedSlotArena::with_capacity(4, 100);
    /// let bytes = arena.approx_bytes();
    /// assert!(bytes > 0);
    /// ```
    pub fn approx_bytes(&self) -> usize {
        self.shards
            .iter()
            .map(|arena| arena.read().approx_bytes())
            .sum()
    }
}

impl<T> Default for SlotArena<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> FromIterator<T> for SlotArena<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let (lower, _) = iter.size_hint();
        let mut arena = SlotArena::with_capacity(lower);
        for value in iter {
            arena.insert(value);
        }
        arena
    }
}

impl<T> Extend<T> for SlotArena<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let iter = iter.into_iter();
        let (lower, _) = iter.size_hint();
        self.reserve(lower);
        for value in iter {
            self.insert(value);
        }
    }
}

/// # Panics
///
/// Panics if `id` is invalid, out of bounds, or refers to a slot that has
/// been removed and reused (stale generation).
impl<T> std::ops::Index<SlotId> for SlotArena<T> {
    type Output = T;

    fn index(&self, id: SlotId) -> &T {
        self.get(id).expect("invalid or stale SlotId")
    }
}

/// # Panics
///
/// Panics if `id` is invalid, out of bounds, or refers to a slot that has
/// been removed and reused (stale generation).
impl<T> std::ops::IndexMut<SlotId> for SlotArena<T> {
    fn index_mut(&mut self, id: SlotId) -> &mut T {
        self.get_mut(id).expect("invalid or stale SlotId")
    }
}

// ---------------------------------------------------------------------------
// Iterator types (C-ITER-TY: names match the methods that produce them)
// ---------------------------------------------------------------------------

/// Iterator over `(SlotId, &T)` pairs of a [`SlotArena`].
///
/// Created by [`SlotArena::iter`].
#[derive(Debug, Clone)]
pub struct Iter<'a, T> {
    inner: std::iter::Enumerate<std::slice::Iter<'a, Option<T>>>,
    generations: &'a [u32],
}

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

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.inner.next() {
                Some((idx, Some(value))) => {
                    let id = SlotId {
                        index: idx,
                        generation: self.generations[idx],
                    };
                    return Some((id, value));
                },
                Some((_, None)) => continue,
                None => return None,
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, self.inner.size_hint().1)
    }
}

/// Mutable iterator over `(SlotId, &mut T)` pairs of a [`SlotArena`].
///
/// Created by [`SlotArena::iter_mut`].
#[derive(Debug)]
pub struct IterMut<'a, T> {
    inner: std::iter::Enumerate<std::slice::IterMut<'a, Option<T>>>,
    generations: &'a [u32],
}

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

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.inner.next() {
                Some((idx, Some(value))) => {
                    let id = SlotId {
                        index: idx,
                        generation: self.generations[idx],
                    };
                    return Some((id, value));
                },
                Some((_, None)) => continue,
                None => return None,
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, self.inner.size_hint().1)
    }
}

/// Owning iterator over `(SlotId, T)` pairs of a [`SlotArena`].
///
/// Created by calling [`IntoIterator::into_iter`] on a `SlotArena`.
#[derive(Debug)]
pub struct IntoIter<T> {
    inner: std::iter::Enumerate<std::vec::IntoIter<Option<T>>>,
    generations: Vec<u32>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = (SlotId, T);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.inner.next() {
                Some((idx, Some(value))) => {
                    let id = SlotId {
                        index: idx,
                        generation: self.generations[idx],
                    };
                    return Some((id, value));
                },
                Some((_, None)) => continue,
                None => return None,
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, self.inner.size_hint().1)
    }
}

/// Iterator over live [`SlotId`]s of a [`SlotArena`].
///
/// Created by [`SlotArena::iter_ids`].
#[derive(Debug, Clone)]
pub struct IterIds<'a, T> {
    inner: Iter<'a, T>,
}

impl<'a, T> Iterator for IterIds<'a, T> {
    type Item = SlotId;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(id, _)| id)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

// ---------------------------------------------------------------------------
// IntoIterator impls (C-ITER: iter, iter_mut, into_iter)
// ---------------------------------------------------------------------------

impl<T> IntoIterator for SlotArena<T> {
    type Item = (SlotId, T);
    type IntoIter = IntoIter<T>;

    /// Consumes the arena, returning an iterator over all `(SlotId, T)` pairs.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::SlotArena;
    ///
    /// let mut arena = SlotArena::new();
    /// arena.insert("a");
    /// arena.insert("b");
    ///
    /// let pairs: Vec<_> = arena.into_iter().collect();
    /// assert_eq!(pairs.len(), 2);
    /// ```
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            inner: self.slots.into_iter().enumerate(),
            generations: self.generations,
        }
    }
}

impl<'a, T> IntoIterator for &'a SlotArena<T> {
    type Item = (SlotId, &'a T);
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> IntoIterator for &'a mut SlotArena<T> {
    type Item = (SlotId, &'a mut T);
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

// ---------------------------------------------------------------------------
// FusedIterator (all iterators yield None permanently after exhaustion)
// ---------------------------------------------------------------------------

impl<T> std::iter::FusedIterator for Iter<'_, T> {}
impl<T> std::iter::FusedIterator for IterMut<'_, T> {}
impl<T> std::iter::FusedIterator for IntoIter<T> {}
impl<T> std::iter::FusedIterator for IterIds<'_, T> {}

/// Thread-safe [`SlotArena`] wrapper using `parking_lot::RwLock`.
///
/// Provides the same functionality as [`SlotArena`] but safe for concurrent
/// access. Uses closure-based access (`get_with`, `get_mut_with`) since
/// references cannot outlive lock guards.
///
/// For high-contention workloads, consider [`ShardedSlotArena`] instead.
///
/// # Example
///
/// ```
/// use std::sync::Arc;
/// use std::thread;
/// use cachekit::ds::ConcurrentSlotArena;
///
/// let arena = Arc::new(ConcurrentSlotArena::new());
///
/// // Insert from main thread
/// let id = arena.insert(0);
///
/// // Spawn readers and writers
/// let handles: Vec<_> = (0..4).map(|i| {
///     let arena = Arc::clone(&arena);
///     thread::spawn(move || {
///         // Read
///         let val = arena.get_with(id, |v| *v);
///
///         // Write (increment)
///         arena.get_mut_with(id, |v| *v += 1);
///     })
/// }).collect();
///
/// for h in handles {
///     h.join().unwrap();
/// }
///
/// assert_eq!(arena.get_with(id, |v| *v), Some(4));
/// ```
#[cfg(feature = "concurrency")]
#[derive(Debug)]
pub struct ConcurrentSlotArena<T> {
    inner: parking_lot::RwLock<SlotArena<T>>,
}

#[cfg(feature = "concurrency")]
impl<T> ConcurrentSlotArena<T> {
    /// Creates an empty concurrent arena.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<String> = ConcurrentSlotArena::new();
    /// assert!(arena.is_empty());
    /// ```
    pub fn new() -> Self {
        Self {
            inner: parking_lot::RwLock::new(SlotArena::new()),
        }
    }

    /// Creates a concurrent arena with pre-allocated capacity.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<i32> = ConcurrentSlotArena::with_capacity(1000);
    /// assert!(arena.capacity() >= 1000);
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            inner: parking_lot::RwLock::new(SlotArena::with_capacity(capacity)),
        }
    }

    /// Inserts a value and returns its [`SlotId`].
    ///
    /// Acquires write lock.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert(42);
    /// assert!(arena.contains(id));
    /// ```
    pub fn insert(&self, value: T) -> SlotId {
        let mut arena = self.inner.write();
        arena.insert(value)
    }

    /// Removes and returns the value at `id`.
    ///
    /// Acquires write lock.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert(42);
    ///
    /// assert_eq!(arena.remove(id), Some(42));
    /// assert_eq!(arena.remove(id), None);
    /// ```
    pub fn remove(&self, id: SlotId) -> Option<T> {
        let mut arena = self.inner.write();
        arena.remove(id)
    }

    /// Runs a closure on a shared reference to the value at `id`.
    ///
    /// Acquires read lock. The closure's return value is returned.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert(vec![1, 2, 3]);
    ///
    /// let sum = arena.get_with(id, |v| v.iter().sum::<i32>());
    /// assert_eq!(sum, Some(6));
    /// ```
    pub fn get_with<R>(&self, id: SlotId, f: impl FnOnce(&T) -> R) -> Option<R> {
        let arena = self.inner.read();
        arena.get(id).map(f)
    }

    /// Non-blocking version of [`get_with`](Self::get_with).
    ///
    /// Returns `None` if the lock cannot be acquired immediately.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert(100);
    ///
    /// // Returns Some if lock is available
    /// if let Some(val) = arena.try_get_with(id, |v| *v) {
    ///     assert_eq!(val, 100);
    /// }
    /// ```
    pub fn try_get_with<R>(&self, id: SlotId, f: impl FnOnce(&T) -> R) -> Option<R> {
        let arena = self.inner.try_read()?;
        arena.get(id).map(f)
    }

    /// Runs a closure on a mutable reference to the value at `id`.
    ///
    /// Acquires write lock.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert(1);
    ///
    /// arena.get_mut_with(id, |v| *v = 2);
    /// assert_eq!(arena.get_with(id, |v| *v), Some(2));
    /// ```
    pub fn get_mut_with<R>(&self, id: SlotId, f: impl FnOnce(&mut T) -> R) -> Option<R> {
        let mut arena = self.inner.write();
        arena.get_mut(id).map(f)
    }

    /// Non-blocking version of [`get_mut_with`](Self::get_mut_with).
    ///
    /// Returns `None` if the lock cannot be acquired immediately.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert(5);
    ///
    /// // Attempt non-blocking write
    /// if arena.try_get_mut_with(id, |v| *v += 1).is_some() {
    ///     assert_eq!(arena.get_with(id, |v| *v), Some(6));
    /// }
    /// ```
    pub fn try_get_mut_with<R>(&self, id: SlotId, f: impl FnOnce(&mut T) -> R) -> Option<R> {
        let mut arena = self.inner.try_write()?;
        arena.get_mut(id).map(f)
    }

    /// Returns `true` if `id` refers to a live slot.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let id = arena.insert("value");
    ///
    /// assert!(arena.contains(id));
    /// arena.remove(id);
    /// assert!(!arena.contains(id));
    /// ```
    pub fn contains(&self, id: SlotId) -> bool {
        let arena = self.inner.read();
        arena.contains(id)
    }

    /// Returns the number of live entries.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// assert_eq!(arena.len(), 0);
    ///
    /// arena.insert(1);
    /// arena.insert(2);
    /// assert_eq!(arena.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        let arena = self.inner.read();
        arena.len()
    }

    /// Returns `true` if there are no live entries.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<i32> = ConcurrentSlotArena::new();
    /// assert!(arena.is_empty());
    ///
    /// let id = arena.insert(1);
    /// assert!(!arena.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        let arena = self.inner.read();
        arena.is_empty()
    }

    /// Returns the backing Vec capacity.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<i32> = ConcurrentSlotArena::with_capacity(100);
    /// assert!(arena.capacity() >= 100);
    /// ```
    pub fn capacity(&self) -> usize {
        let arena = self.inner.read();
        arena.capacity()
    }

    /// Reserves capacity for additional slots.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<i32> = ConcurrentSlotArena::new();
    /// arena.reserve(100);
    /// assert!(arena.capacity() >= 100);
    /// ```
    pub fn reserve(&self, additional: usize) {
        let mut arena = self.inner.write();
        arena.reserve(additional);
    }

    /// Shrinks internal storage to fit current state.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<i32> = ConcurrentSlotArena::with_capacity(1000);
    /// arena.insert(1);
    /// arena.shrink_to_fit();
    /// ```
    pub fn shrink_to_fit(&self) {
        let mut arena = self.inner.write();
        arena.shrink_to_fit();
    }

    /// Clears all entries and shrinks storage.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::with_capacity(100);
    /// arena.insert("a");
    /// arena.insert("b");
    ///
    /// arena.clear_shrink();
    /// assert!(arena.is_empty());
    /// ```
    pub fn clear_shrink(&self) {
        let mut arena = self.inner.write();
        arena.clear_shrink();
    }

    /// Clears all entries.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// let a = arena.insert(1);
    /// let b = arena.insert(2);
    ///
    /// arena.clear();
    /// assert!(arena.is_empty());
    /// assert!(!arena.contains(a));
    /// ```
    pub fn clear(&self) {
        let mut arena = self.inner.write();
        arena.clear();
    }

    /// Returns approximate memory footprint in bytes.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena: ConcurrentSlotArena<u64> = ConcurrentSlotArena::with_capacity(100);
    /// let bytes = arena.approx_bytes();
    /// assert!(bytes > 0);
    /// ```
    pub fn approx_bytes(&self) -> usize {
        let arena = self.inner.read();
        arena.approx_bytes()
    }
}

#[cfg(feature = "concurrency")]
impl<T> Default for ConcurrentSlotArena<T> {
    fn default() -> Self {
        Self::new()
    }
}

// ---------------------------------------------------------------------------
// into_inner (C-CONV: into_ for owned → owned)
// ---------------------------------------------------------------------------

#[cfg(feature = "concurrency")]
impl<T> ConcurrentSlotArena<T> {
    /// Consumes the concurrent wrapper, returning the inner [`SlotArena`].
    ///
    /// Useful when iteration or bulk inspection is needed after all shared
    /// references have been dropped.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ConcurrentSlotArena;
    ///
    /// let arena = ConcurrentSlotArena::new();
    /// arena.insert("a");
    /// arena.insert("b");
    ///
    /// let inner = arena.into_inner();
    /// let values: Vec<_> = inner.iter().map(|(_, v)| *v).collect();
    /// assert_eq!(values.len(), 2);
    /// ```
    pub fn into_inner(self) -> SlotArena<T> {
        self.inner.into_inner()
    }
}

#[cfg(feature = "concurrency")]
impl<T> ShardedSlotArena<T> {
    /// Consumes the sharded arena, returning the inner [`SlotArena`]s.
    ///
    /// Returns one `SlotArena` per shard in shard order.
    ///
    /// # Example
    ///
    /// ```
    /// use cachekit::ds::ShardedSlotArena;
    ///
    /// let arena = ShardedSlotArena::new(2);
    /// arena.insert("a");
    /// arena.insert("b");
    ///
    /// let shards = arena.into_inner();
    /// let total: usize = shards.iter().map(|s| s.len()).sum();
    /// assert_eq!(total, 2);
    /// ```
    pub fn into_inner(self) -> Vec<SlotArena<T>> {
        self.shards
            .into_iter()
            .map(|lock| lock.into_inner())
            .collect()
    }
}

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

    #[test]
    fn slot_arena_insert_remove_reuse() {
        let mut arena = SlotArena::new();
        let id1 = arena.insert("a");
        let id2 = arena.insert("b");
        assert_eq!(arena.len(), 2);
        assert_eq!(arena.get(id1), Some(&"a"));
        assert_eq!(arena.get(id2), Some(&"b"));

        assert_eq!(arena.remove(id1), Some("a"));
        assert_eq!(arena.len(), 1);

        let id3 = arena.insert("c");
        assert_eq!(arena.len(), 2);
        assert_eq!(arena.get(id3), Some(&"c"));
        assert_eq!(id1.index(), id3.index());
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn concurrent_slot_arena_basic_ops() {
        let arena = ConcurrentSlotArena::new();
        let id = arena.insert(10);
        assert_eq!(arena.get_with(id, |v| *v), Some(10));
        assert!(arena.contains(id));
        assert_eq!(arena.len(), 1);

        arena.get_mut_with(id, |v| *v = 20);
        assert_eq!(arena.get_with(id, |v| *v), Some(20));
        assert_eq!(arena.remove(id), Some(20));
        assert!(!arena.contains(id));
        assert!(arena.is_empty());
    }

    #[test]
    fn slot_arena_remove_invalid_id_is_none() {
        let mut arena: SlotArena<i32> = SlotArena::new();
        let id = SlotId {
            index: 0,
            generation: 0,
        };
        assert_eq!(arena.remove(id), None);
        assert!(!arena.contains(id));
        assert!(arena.is_empty());
    }

    #[test]
    fn slot_arena_clear_resets_state() {
        let mut arena = SlotArena::with_capacity(4);
        let a = arena.insert("a");
        let b = arena.insert("b");
        assert_eq!(arena.len(), 2);
        assert!(arena.contains(a));
        assert!(arena.contains(b));

        arena.clear();
        assert_eq!(arena.len(), 0);
        assert!(arena.is_empty());
        assert!(!arena.contains(a));
        assert!(!arena.contains(b));
        assert_eq!(arena.iter().count(), 0);
    }

    #[test]
    fn slot_arena_iter_skips_empty_slots() {
        let mut arena = SlotArena::new();
        let a = arena.insert("a");
        let b = arena.insert("b");
        let c = arena.insert("c");
        assert_eq!(arena.remove(b), Some("b"));

        let mut values: Vec<_> = arena.iter().map(|(_, v)| *v).collect();
        values.sort();
        assert_eq!(values, vec!["a", "c"]);
        assert!(arena.contains(a));
        assert!(arena.contains(c));
    }

    #[test]
    fn slot_arena_get_mut_updates_value() {
        let mut arena = SlotArena::new();
        let id = arena.insert(1);
        if let Some(value) = arena.get_mut(id) {
            *value = 2;
        }
        assert_eq!(arena.get(id), Some(&2));
    }

    #[test]
    fn slot_arena_capacity_tracking() {
        let arena: SlotArena<i32> = SlotArena::with_capacity(16);
        assert!(arena.capacity() >= 16);
        assert_eq!(arena.len(), 0);
    }

    #[test]
    fn slot_arena_contains_index_and_iter_ids() {
        let mut arena = SlotArena::new();
        let a = arena.insert("a");
        let b = arena.insert("b");
        assert!(arena.contains_index(a.index()));
        assert!(arena.contains_index(b.index()));
        arena.remove(a);
        assert!(!arena.contains_index(a.index()));

        let ids: Vec<_> = arena.iter_ids().collect();
        assert_eq!(ids, vec![b]);
    }

    #[test]
    fn slot_arena_reserve_grows_capacity() {
        let mut arena: SlotArena<i32> = SlotArena::new();
        let before = arena.capacity();
        arena.reserve(32);
        assert!(arena.capacity() >= before + 32);
    }

    #[test]
    fn slot_arena_debug_snapshot() {
        let mut arena = SlotArena::new();
        let a = arena.insert("a");
        let b = arena.insert("b");
        arena.remove(a);
        let snapshot = arena.debug_snapshot();
        assert_eq!(snapshot.len, 1);
        assert!(snapshot.live_ids.contains(&b));
        assert!(snapshot.free_list.contains(&a.index()));
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn sharded_slot_arena_basic_ops() {
        let arena = ShardedSlotArena::new(2);
        let a = arena.insert(1);
        let b = arena.insert(2);
        assert!(arena.contains(a));
        assert!(arena.contains(b));
        assert_eq!(arena.get_with(a, |v| *v), Some(1));
        assert_eq!(arena.remove(b), Some(2));
        assert!(!arena.contains(b));
        assert_eq!(arena.len(), 1);
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn sharded_slot_arena_shard_for_key() {
        let arena: ShardedSlotArena<i32> = ShardedSlotArena::new(4);
        let shard = arena.shard_for_key(&"alpha");
        assert!(shard < arena.shard_count());
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn sharded_slot_arena_with_seed() {
        let arena: ShardedSlotArena<i32> = ShardedSlotArena::with_shards_seed(4, 0, 99);
        let shard = arena.shard_for_key(&"alpha");
        assert!(shard < arena.shard_count());
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn concurrent_slot_arena_try_ops() {
        let arena = ConcurrentSlotArena::new();
        let id = arena.insert(1);
        assert_eq!(arena.try_get_with(id, |v| *v), Some(1));
        arena.try_get_mut_with(id, |v| *v = 2);
        assert_eq!(arena.get_with(id, |v| *v), Some(2));
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn concurrent_slot_arena_clear_and_accessors() {
        let arena = ConcurrentSlotArena::new();
        let a = arena.insert(1);
        let b = arena.insert(2);
        assert_eq!(arena.get_with(a, |v| *v), Some(1));
        assert_eq!(arena.get_with(b, |v| *v), Some(2));

        arena.clear();
        assert!(arena.is_empty());
        assert!(!arena.contains(a));
        assert!(!arena.contains(b));
        assert_eq!(arena.get_with(a, |v| *v), None);
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn concurrent_slot_arena_get_mut_with_updates_value() {
        let arena = ConcurrentSlotArena::new();
        let id = arena.insert(5);
        arena.get_mut_with(id, |v| *v = 10);
        assert_eq!(arena.get_with(id, |v| *v), Some(10));
    }

    // -----------------------------------------------------------------------
    // ABA / generational safety tests
    // -----------------------------------------------------------------------

    #[test]
    fn stale_id_get_returns_none_after_reuse() {
        let mut arena = SlotArena::new();
        let id_a = arena.insert("alice");
        arena.remove(id_a);
        let _id_b = arena.insert("bob"); // reuses same physical slot

        // Stale handle must NOT see the new occupant
        assert_eq!(arena.get(id_a), None);
        assert!(!arena.contains(id_a));
    }

    #[test]
    fn stale_id_get_mut_returns_none_after_reuse() {
        let mut arena = SlotArena::new();
        let id_a = arena.insert(1);
        arena.remove(id_a);
        let id_b = arena.insert(2); // reuses same physical slot

        assert_eq!(arena.get_mut(id_a), None);
        // New handle still works
        assert_eq!(arena.get(id_b), Some(&2));
    }

    #[test]
    fn stale_id_remove_returns_none_after_reuse() {
        let mut arena = SlotArena::new();
        let id_a = arena.insert(42);
        arena.remove(id_a);
        let id_b = arena.insert(99); // reuses same physical slot

        // Must not remove the new occupant via a stale handle
        assert_eq!(arena.remove(id_a), None);
        assert_eq!(arena.get(id_b), Some(&99));
        assert_eq!(arena.len(), 1);
    }

    #[test]
    fn stale_id_after_multiple_reuse_cycles() {
        let mut arena = SlotArena::new();

        let id_gen0 = arena.insert("gen0");
        arena.remove(id_gen0);

        let id_gen1 = arena.insert("gen1");
        arena.remove(id_gen1);

        let id_gen2 = arena.insert("gen2");

        // All three share the same physical index
        assert_eq!(id_gen0.index(), id_gen1.index());
        assert_eq!(id_gen1.index(), id_gen2.index());

        // Only the latest generation handle is valid
        assert_eq!(arena.get(id_gen0), None);
        assert_eq!(arena.get(id_gen1), None);
        assert_eq!(arena.get(id_gen2), Some(&"gen2"));
    }

    #[test]
    fn stale_id_contains_returns_false_after_reuse() {
        let mut arena = SlotArena::new();
        let stale = arena.insert(1);
        arena.remove(stale);
        let _new = arena.insert(2);

        assert!(!arena.contains(stale));
    }

    #[test]
    fn slot_arena_debug_invariants_hold() {
        let mut arena = SlotArena::new();
        let a = arena.insert(1);
        let b = arena.insert(2);
        arena.remove(a);
        let _ = arena.insert(3);
        assert!(arena.contains(b));
        arena.debug_validate_invariants();
    }

    // -----------------------------------------------------------------------
    // Named iterator type tests
    // -----------------------------------------------------------------------

    #[test]
    fn iter_yields_all_live_entries() {
        let mut arena = SlotArena::new();
        let a = arena.insert(10);
        let b = arena.insert(20);
        let c = arena.insert(30);

        let mut pairs: Vec<_> = arena.iter().collect();
        pairs.sort_by_key(|(id, _)| *id);
        assert_eq!(pairs, vec![(a, &10), (b, &20), (c, &30)]);
    }

    #[test]
    fn iter_skips_removed_slots() {
        let mut arena = SlotArena::new();
        let a = arena.insert(10);
        let b = arena.insert(20);
        let c = arena.insert(30);
        arena.remove(b);

        let mut pairs: Vec<_> = arena.iter().collect();
        pairs.sort_by_key(|(id, _)| *id);
        assert_eq!(pairs, vec![(a, &10), (c, &30)]);
    }

    #[test]
    fn iter_on_empty_arena() {
        let arena = SlotArena::<i32>::new();
        assert_eq!(arena.iter().count(), 0);
    }

    #[test]
    fn iter_mut_modifies_values() {
        let mut arena = SlotArena::new();
        let a = arena.insert(1);
        let b = arena.insert(2);

        for (_, v) in arena.iter_mut() {
            *v += 100;
        }

        assert_eq!(arena.get(a), Some(&101));
        assert_eq!(arena.get(b), Some(&102));
    }

    #[test]
    fn iter_mut_skips_removed_slots() {
        let mut arena = SlotArena::new();
        let a = arena.insert(1);
        let b = arena.insert(2);
        let c = arena.insert(3);
        arena.remove(b);

        let ids: Vec<_> = arena.iter_mut().map(|(id, _)| id).collect();
        assert_eq!(ids.len(), 2);
        assert!(ids.contains(&a));
        assert!(ids.contains(&c));
    }

    #[test]
    fn iter_ids_matches_iter_keys() {
        let mut arena = SlotArena::new();
        let a = arena.insert("x");
        let b = arena.insert("y");
        arena.remove(a);
        let c = arena.insert("z");

        let ids_from_iter: Vec<_> = arena.iter().map(|(id, _)| id).collect();
        let ids_from_iter_ids: Vec<_> = arena.iter_ids().collect();
        assert_eq!(ids_from_iter, ids_from_iter_ids);
        assert!(ids_from_iter_ids.contains(&b));
        assert!(ids_from_iter_ids.contains(&c));
    }

    #[test]
    fn into_iter_consumes_arena() {
        let mut arena = SlotArena::new();
        arena.insert("a");
        arena.insert("b");
        arena.insert("c");

        let pairs: Vec<_> = arena.into_iter().collect();
        assert_eq!(pairs.len(), 3);
    }

    #[test]
    fn into_iter_skips_removed_slots() {
        let mut arena = SlotArena::new();
        let a = arena.insert(10);
        arena.insert(20);
        arena.insert(30);
        arena.remove(a);

        let pairs: Vec<_> = arena.into_iter().collect();
        assert_eq!(pairs.len(), 2);
    }

    #[test]
    fn into_iter_empty() {
        let arena = SlotArena::<i32>::new();
        assert_eq!(arena.into_iter().count(), 0);
    }

    #[test]
    fn into_iter_preserves_slot_ids() {
        let mut arena = SlotArena::new();
        let a = arena.insert("first");
        let b = arena.insert("second");

        let mut pairs: Vec<_> = arena.into_iter().collect();
        pairs.sort_by_key(|(id, _)| *id);
        assert_eq!(pairs, vec![(a, "first"), (b, "second")]);
    }

    #[test]
    fn for_loop_ref_borrow() {
        let mut arena = SlotArena::new();
        arena.insert(1);
        arena.insert(2);

        let mut sum = 0;
        for (_, v) in &arena {
            sum += v;
        }
        assert_eq!(sum, 3);
        assert_eq!(arena.len(), 2); // not consumed
    }

    #[test]
    fn for_loop_mut_borrow() {
        let mut arena = SlotArena::new();
        let a = arena.insert(1);
        let b = arena.insert(2);

        for (_, v) in &mut arena {
            *v += 10;
        }
        assert_eq!(arena.get(a), Some(&11));
        assert_eq!(arena.get(b), Some(&12));
    }

    #[test]
    fn for_loop_owned() {
        let mut arena = SlotArena::new();
        arena.insert(10);
        arena.insert(20);

        let mut sum = 0;
        for (_, v) in arena {
            sum += v;
        }
        assert_eq!(sum, 30);
    }

    #[test]
    fn iter_count_matches_len() {
        let mut arena = SlotArena::new();
        let ids: Vec<_> = (0..10).map(|i| arena.insert(i)).collect();
        arena.remove(ids[3]);
        arena.remove(ids[7]);

        assert_eq!(arena.iter().count(), arena.len());
        assert_eq!(arena.iter_mut().count(), arena.len());
        assert_eq!(arena.iter_ids().count(), arena.len());
    }

    #[test]
    fn iter_after_clear() {
        let mut arena = SlotArena::new();
        arena.insert("a");
        arena.insert("b");
        arena.clear();

        assert_eq!(arena.iter().count(), 0);
        assert_eq!(arena.iter_mut().count(), 0);
        assert_eq!(arena.iter_ids().count(), 0);
    }

    // -----------------------------------------------------------------------
    // Clone tests
    // -----------------------------------------------------------------------

    #[test]
    fn clone_produces_independent_copy() {
        let mut arena = SlotArena::new();
        let a = arena.insert(1);
        let b = arena.insert(2);

        let mut cloned = arena.clone();

        assert_eq!(cloned.get(a), Some(&1));
        assert_eq!(cloned.get(b), Some(&2));
        assert_eq!(cloned.len(), 2);

        // Mutating clone doesn't affect original
        cloned.remove(a);
        assert_eq!(arena.get(a), Some(&1));
        assert!(!cloned.contains(a));
    }

    #[test]
    fn clone_empty_arena() {
        let arena = SlotArena::<i32>::new();
        let cloned = arena.clone();
        assert!(cloned.is_empty());
    }

    // -----------------------------------------------------------------------
    // Ord tests on SlotId / ShardedSlotId
    // -----------------------------------------------------------------------

    #[test]
    fn slot_id_ordering() {
        let mut arena = SlotArena::new();
        let a = arena.insert("a");
        let b = arena.insert("b");
        let c = arena.insert("c");

        assert!(a < b);
        assert!(b < c);

        let mut ids = [c, a, b];
        ids.sort();
        assert_eq!(ids, [a, b, c]);
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn sharded_slot_id_ordering() {
        let arena = ShardedSlotArena::new(4);
        let a = arena.insert(1);
        let b = arena.insert(2);
        let c = arena.insert(3);

        // Just verify Ord is usable — exact order depends on shard assignment
        let mut ids = [c, a, b];
        ids.sort();
        assert_eq!(ids.len(), 3);
    }

    // -----------------------------------------------------------------------
    // into_inner tests
    // -----------------------------------------------------------------------

    #[cfg(feature = "concurrency")]
    #[test]
    fn concurrent_into_inner_allows_iteration() {
        let arena = ConcurrentSlotArena::new();
        let a = arena.insert(10);
        let b = arena.insert(20);

        let inner = arena.into_inner();
        assert_eq!(inner.get(a), Some(&10));
        assert_eq!(inner.get(b), Some(&20));

        let pairs: Vec<_> = inner.iter().collect();
        assert_eq!(pairs.len(), 2);
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn concurrent_into_inner_into_iter() {
        let arena = ConcurrentSlotArena::new();
        arena.insert("x");
        arena.insert("y");

        let pairs: Vec<_> = arena.into_inner().into_iter().collect();
        assert_eq!(pairs.len(), 2);
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn sharded_into_inner_returns_all_shards() {
        let arena = ShardedSlotArena::new(4);
        for i in 0..8 {
            arena.insert(i);
        }

        let shards = arena.into_inner();
        assert_eq!(shards.len(), 4);
        let total: usize = shards.iter().map(|s| s.len()).sum();
        assert_eq!(total, 8);
    }

    #[cfg(feature = "concurrency")]
    #[test]
    fn sharded_into_inner_allows_iteration() {
        let arena = ShardedSlotArena::new(2);
        arena.insert(1);
        arena.insert(2);
        arena.insert(3);

        let shards = arena.into_inner();
        let all_values: Vec<_> = shards
            .into_iter()
            .flat_map(|s| s.into_iter().map(|(_, v)| v))
            .collect();
        assert_eq!(all_values.len(), 3);
    }
}

#[cfg(test)]
mod property_tests {
    use super::*;
    use proptest::prelude::*;

    // =============================================================================
    // Property Tests - Insert Operations
    // =============================================================================

    proptest! {
        /// Property: insert returns valid SlotId
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_insert_returns_valid_id(
            values in prop::collection::vec(any::<u32>(), 0..50)
        ) {
            let mut arena = SlotArena::new();

            for value in values {
                let id = arena.insert(value);

                prop_assert_eq!(arena.get(id), Some(&value));
                prop_assert!(arena.contains(id));
            }
        }

        /// Property: inserted values can be retrieved
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_insert_and_get(
            value in any::<u32>()
        ) {
            let mut arena = SlotArena::new();
            let id = arena.insert(value);

            prop_assert_eq!(arena.get(id), Some(&value));
        }
    }

    // =============================================================================
    // Property Tests - Remove Operations
    // =============================================================================

    proptest! {
        /// Property: remove decreases length by 1
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_remove_decreases_length(
            values in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in &values {
                let id = arena.insert(*value);
                ids.push(id);
            }

            for id in ids {
                let old_len = arena.len();
                let removed = arena.remove(id);

                prop_assert!(removed.is_some());
                prop_assert_eq!(arena.len(), old_len - 1);
                prop_assert!(!arena.contains(id));
            }

            prop_assert!(arena.is_empty());
        }

        /// Property: remove returns the correct value
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_remove_returns_value(
            values in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in &values {
                let id = arena.insert(*value);
                ids.push((id, *value));
            }

            for (id, expected_value) in ids {
                let removed = arena.remove(id);
                prop_assert_eq!(removed, Some(expected_value));
            }
        }

        /// Property: removing twice returns None
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_remove_twice_returns_none(
            value in any::<u32>()
        ) {
            let mut arena = SlotArena::new();
            let id = arena.insert(value);

            let first = arena.remove(id);
            let second = arena.remove(id);

            prop_assert_eq!(first, Some(value));
            prop_assert_eq!(second, None);
        }
    }

    // =============================================================================
    // Property Tests - SlotId Stability
    // =============================================================================

    proptest! {
        /// Property: SlotId remains valid until removed
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_slot_id_stable_until_removed(
            values in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in &values {
                let id = arena.insert(*value);
                ids.push((id, *value));
            }

            // All SlotIds should be valid
            for (id, value) in &ids {
                prop_assert_eq!(arena.get(*id), Some(value));
                prop_assert!(arena.contains(*id));
            }

            // Remove every other slot
            for (idx, (id, _value)) in ids.iter().enumerate() {
                if idx % 2 == 0 {
                    arena.remove(*id);
                }
            }

            // Remaining slots should still be valid
            for (idx, (id, value)) in ids.iter().enumerate() {
                if idx % 2 != 0 {
                    prop_assert_eq!(arena.get(*id), Some(value));
                } else {
                    prop_assert_eq!(arena.get(*id), None);
                }
            }
        }
    }

    // =============================================================================
    // Property Tests - Free Slot Reuse
    // =============================================================================

    proptest! {
        /// Property: Freed slots are reused
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_free_slot_reuse(
            values1 in prop::collection::vec(any::<u32>(), 5..20),
            values2 in prop::collection::vec(any::<u32>(), 5..20)
        ) {
            let mut arena = SlotArena::new();

            // Insert and collect indices
            let mut ids = Vec::new();
            for value in &values1 {
                let id = arena.insert(*value);
                ids.push(id);
            }

            let removed_indices: Vec<_> = ids.iter().map(|id| id.index()).collect();

            // Remove all slots
            for id in ids {
                arena.remove(id);
            }

            prop_assert!(arena.is_empty());

            // Insert new values - should reuse freed slots
            let mut reused_count = 0;
            for value in &values2 {
                let id = arena.insert(*value);
                if removed_indices.contains(&id.index()) {
                    reused_count += 1;
                }
            }

            // At least some slots should have been reused
            prop_assert!(reused_count > 0);
        }
    }

    // =============================================================================
    // Property Tests - Length Tracking
    // =============================================================================

    proptest! {
        /// Property: len() tracks number of live entries
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_len_tracks_entries(
            values in prop::collection::vec(any::<u32>(), 0..50)
        ) {
            let mut arena = SlotArena::new();

            for (idx, value) in values.iter().enumerate() {
                arena.insert(*value);
                prop_assert_eq!(arena.len(), idx + 1);
            }

            let total = values.len();
            let mut ids: Vec<_> = arena.iter_ids().collect();

            for (idx, id) in ids.drain(..).enumerate() {
                arena.remove(id);
                prop_assert_eq!(arena.len(), total - idx - 1);
            }

            prop_assert_eq!(arena.len(), 0);
        }

        /// Property: is_empty is consistent with len
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_is_empty_consistent(
            values in prop::collection::vec(any::<u32>(), 0..30)
        ) {
            let mut arena = SlotArena::new();

            for value in values {
                arena.insert(value);

                if arena.is_empty() {
                    prop_assert_eq!(arena.len(), 0);
                } else {
                    prop_assert!(!arena.is_empty());
                }
            }
        }
    }

    // =============================================================================
    // Property Tests - Get and Contains
    // =============================================================================

    proptest! {
        /// Property: get returns Some for all inserted values
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_get_returns_inserted_values(
            values in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in &values {
                let id = arena.insert(*value);
                ids.push((id, *value));
            }

            for (id, value) in ids {
                prop_assert_eq!(arena.get(id), Some(&value));
            }
        }

        /// Property: contains is consistent with get
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_contains_consistent_with_get(
            values in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in &values {
                let id = arena.insert(*value);
                ids.push(id);
            }

            for id in ids {
                let contains = arena.contains(id);
                let get_result = arena.get(id);

                if contains {
                    prop_assert!(get_result.is_some());
                } else {
                    prop_assert!(get_result.is_none());
                }
            }
        }
    }

    // =============================================================================
    // Property Tests - Get Mut
    // =============================================================================

    proptest! {
        /// Property: get_mut allows modification
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_get_mut_modifies(
            value1 in any::<u32>(),
            value2 in any::<u32>()
        ) {
            let mut arena = SlotArena::new();
            let id = arena.insert(value1);

            if let Some(val) = arena.get_mut(id) {
                *val = value2;
            }

            prop_assert_eq!(arena.get(id), Some(&value2));
        }
    }

    // =============================================================================
    // Property Tests - Iterator
    // =============================================================================

    proptest! {
        /// Property: iter returns exactly len() items
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_iter_returns_len_items(
            values in prop::collection::vec(any::<u32>(), 0..50)
        ) {
            let mut arena = SlotArena::new();

            for value in values {
                arena.insert(value);
            }

            let iter_count = arena.iter().count();
            prop_assert_eq!(iter_count, arena.len());
        }

        /// Property: iter_ids returns exactly len() items
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_iter_ids_returns_len_items(
            values in prop::collection::vec(any::<u32>(), 0..50)
        ) {
            let mut arena = SlotArena::new();

            for value in values {
                arena.insert(value);
            }

            let ids_count = arena.iter_ids().count();
            prop_assert_eq!(ids_count, arena.len());
        }

        /// Property: iter skips removed slots
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_iter_skips_removed(
            values in prop::collection::vec(any::<u32>(), 5..30)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in &values {
                let id = arena.insert(*value);
                ids.push(id);
            }

            // Remove every other slot
            for (idx, id) in ids.iter().enumerate() {
                if idx % 2 == 0 {
                    arena.remove(*id);
                }
            }

            let iter_count = arena.iter().count();
            let expected_count = values.len() / 2;
            prop_assert_eq!(iter_count, expected_count);
        }
    }

    // =============================================================================
    // Property Tests - Clear Operations
    // =============================================================================

    proptest! {
        /// Property: clear_shrink resets to empty state
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_clear_resets_state(
            values in prop::collection::vec(any::<u32>(), 1..30)
        ) {
            let mut arena = SlotArena::new();

            for value in values {
                arena.insert(value);
            }

            arena.clear_shrink();

            prop_assert!(arena.is_empty());
            prop_assert_eq!(arena.len(), 0);
            prop_assert_eq!(arena.iter().count(), 0);
        }

        /// Property: clear invalidates all SlotIds
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_clear_invalidates_ids(
            values in prop::collection::vec(any::<u32>(), 1..20)
        ) {
            let mut arena = SlotArena::new();
            let mut ids = Vec::new();

            for value in values {
                let id = arena.insert(value);
                ids.push(id);
            }

            arena.clear_shrink();

            // All previous ids should be invalid
            for id in ids {
                prop_assert!(!arena.contains(id));
                prop_assert_eq!(arena.get(id), None);
            }
        }

        /// Property: usable after clear
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_usable_after_clear(
            values1 in prop::collection::vec(any::<u32>(), 1..20),
            values2 in prop::collection::vec(any::<u32>(), 1..20)
        ) {
            let mut arena = SlotArena::new();

            for value in values1 {
                arena.insert(value);
            }

            arena.clear_shrink();

            // Should be usable after clear
            for value in &values2 {
                arena.insert(*value);
            }

            prop_assert_eq!(arena.len(), values2.len());
        }
    }

    // =============================================================================
    // Property Tests - Capacity
    // =============================================================================

    proptest! {
        /// Property: with_capacity pre-allocates
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_with_capacity_preallocates(
            capacity in 1usize..100
        ) {
            let arena: SlotArena<u32> = SlotArena::with_capacity(capacity);

            prop_assert!(arena.capacity() >= capacity);
            prop_assert_eq!(arena.len(), 0);
            prop_assert!(arena.is_empty());
        }
    }

    // =============================================================================
    // Property Tests - Reference Implementation Equivalence
    // =============================================================================

    proptest! {
        /// Property: Behavior matches reference HashMap
        #[cfg_attr(miri, ignore)]
        #[test]
        fn prop_matches_hashmap(
            operations in prop::collection::vec((0u8..3, any::<u32>()), 0..50)
        ) {
            let mut arena = SlotArena::new();
            let mut reference: std::collections::HashMap<SlotId, u32> = std::collections::HashMap::new();

            for (op, value) in operations {
                match op % 3 {
                    0 => {
                        let id = arena.insert(value);
                        reference.insert(id, value);
                    }
                    1 => {
                        if !reference.is_empty() {
                            let keys: Vec<_> = reference.keys().copied().collect();
                            let id = keys[0];

                            let arena_val = arena.remove(id);
                            let ref_val = reference.remove(&id);

                            prop_assert_eq!(arena_val, ref_val);
                        }
                    }
                    2 => {
                        for (&id, &expected_value) in &reference {
                            prop_assert_eq!(arena.get(id), Some(&expected_value));
                        }
                    }
                    _ => unreachable!(),
                }

                prop_assert_eq!(arena.len(), reference.len());
                prop_assert_eq!(arena.is_empty(), reference.is_empty());
            }
        }
    }
}
