llvm-native-core 0.1.15

//! Open-addressing hash map with tombstone deletion.
//!
//! Clean-room implementation of LLVM's `DenseMap<K, V>` and `DenseSet<T>`.
//! Uses linear probing with tombstone markers and automatic rehashing
//! when the load factor exceeds 0.75.
//!
//! @llvm_behavior: LLVM's DenseMap is an open-addressing hash table
//!   with linear probing and tombstone markers. It provides O(1)
//!   average-case lookup, insertion, and deletion.

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

// ============================================================================
// Internal Bucket Type
// ============================================================================

/// Internal bucket for the open-addressing hash table.
///
/// Each slot is either `Empty`, `Tombstone` (previously occupied but now
/// deleted), or `Full` (holding a key-value pair).
#[derive(Debug, Clone)]
enum DenseMapBucket<K, V> {
    Empty,
    Tombstone,
    Full { key: K, value: V },
}

impl<K, V> DenseMapBucket<K, V> {
    /// Returns a reference to the value if the bucket is full.
    fn value(&self) -> Option<&V> {
        match self {
            DenseMapBucket::Full { value, .. } => Some(value),
            _ => None,
        }
    }

    /// Returns a mutable reference to the value if the bucket is full.
    fn value_mut(&mut self) -> Option<&mut V> {
        match self {
            DenseMapBucket::Full { value, .. } => Some(value),
            _ => None,
        }
    }

    /// Take ownership of the key-value pair, leaving Tombstone behind.
    fn take(&mut self) -> Option<(K, V)> {
        match self {
            DenseMapBucket::Full { .. } => {
                // Replace self with Tombstone, take the old value
                let old = std::mem::replace(self, DenseMapBucket::Tombstone);
                match old {
                    DenseMapBucket::Full { key, value } => Some((key, value)),
                    _ => unreachable!(),
                }
            }
            _ => None,
        }
    }
}

// ============================================================================
// DenseMap
// ============================================================================

/// An open-addressing hash map with tombstone deletion.
///
/// Uses linear probing for collision resolution. The load factor
/// (including tombstones) is kept below 0.75 by automatic rehashing.
///
/// # Type Parameters
/// - `K`: Key type, must implement `Eq + Hash + Clone`
/// - `V`: Value type, must implement `Clone`
///
/// @llvm_behavior: LLVM's `DenseMap<K, V>` is an open-addressed hash table
///   supporting insertion, lookup, and erasure. Tombstones mark deleted
///   entries to avoid breaking probe chains.
pub struct DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    /// Bucket array. Each slot is Empty, Tombstone, or Full.
    buckets: Vec<DenseMapBucket<K, V>>,
    /// Number of Full entries.
    num_entries: usize,
    /// Number of Tombstone entries.
    num_tombstones: usize,
}

// ============================================================================
// Internal Helpers
// ============================================================================

impl<K, V> DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    /// Compute the hash of a key.
    fn hash_key(key: &K) -> u64 {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish()
    }

    /// The minimum capacity for a non-empty map.
    const MIN_CAPACITY: usize = 8;

    /// Returns true if the map should grow (load factor > 0.75).
    fn needs_grow(&self) -> bool {
        let cap = self.buckets.len();
        if cap == 0 {
            return true;
        }
        // Grow when (entries + tombstones) > 0.75 * capacity
        (self.num_entries + self.num_tombstones) * 4 > cap * 3
    }

    /// Find the next power-of-2 capacity >= `desired`.
    fn next_capacity(desired: usize) -> usize {
        let min = Self::MIN_CAPACITY;
        let target = std::cmp::max(desired, min);
        if target.is_power_of_two() {
            target
        } else {
            target.next_power_of_two()
        }
    }

    /// Resize the bucket array to `new_capacity` and rehash all entries.
    /// `new_capacity` must be a power of 2.
    fn rehash(&mut self, new_capacity: usize) {
        debug_assert!(new_capacity.is_power_of_two());
        debug_assert!(new_capacity >= self.num_entries);

        let mut new_buckets: Vec<DenseMapBucket<K, V>> =
            (0..new_capacity).map(|_| DenseMapBucket::Empty).collect();

        for bucket in self.buckets.iter_mut() {
            if let DenseMapBucket::Full { .. } = bucket {
                // Take the entry out, leaving Tombstone (which we'll discard)
                if let Some((key, value)) = bucket.take() {
                    let hash = Self::hash_key(&key);
                    let mask = new_capacity - 1;
                    let mut idx = (hash as usize) & mask;
                    loop {
                        match &new_buckets[idx] {
                            DenseMapBucket::Empty => {
                                new_buckets[idx] = DenseMapBucket::Full { key, value };
                                break;
                            }
                            _ => {
                                idx = (idx + 1) & mask;
                            }
                        }
                    }
                }
            }
        }

        self.buckets = new_buckets;
        self.num_tombstones = 0;
    }

    /// Find the index of the bucket for `key`, or the first available slot
    /// (Empty or Tombstone) where it could be inserted.
    ///
    /// Returns `(index, is_present)`:
    /// - If `is_present` is true, the index points to a Full bucket with the key.
    /// - If `is_present` is false, the index points to the first Empty or
    ///   Tombstone slot encountered during probing.
    fn find_bucket(&self, key: &K) -> (usize, bool) {
        let cap = self.buckets.len();
        if cap == 0 {
            return (0, false);
        }

        let hash = Self::hash_key(key);
        let mask = cap - 1;
        let mut idx = (hash as usize) & mask;
        let mut first_tombstone: Option<usize> = None;

        loop {
            match &self.buckets[idx] {
                DenseMapBucket::Empty => {
                    // Use the first tombstone we saw, or this Empty slot
                    let slot = first_tombstone.unwrap_or(idx);
                    return (slot, false);
                }
                DenseMapBucket::Tombstone => {
                    // Remember this tombstone for potential insertion
                    if first_tombstone.is_none() {
                        first_tombstone = Some(idx);
                    }
                }
                DenseMapBucket::Full { key: k, .. } => {
                    if *k == *key {
                        return (idx, true);
                    }
                }
            }
            idx = (idx + 1) & mask;
        }
    }

    /// Ensure capacity for `additional` more entries.
    fn ensure_capacity(&mut self, additional: usize) {
        let needed = self.num_entries + additional;
        if self.buckets.len() == 0 || needed * 4 > self.buckets.len() * 3 {
            let new_cap = Self::next_capacity(needed * 4 / 3 + 1);
            self.rehash(new_cap);
        } else if self.needs_grow() {
            // Rehash to clean up tombstones without growing
            self.rehash(self.buckets.len());
        }
    }
}

// ============================================================================
// Public API
// ============================================================================

impl<K, V> DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    /// Creates an empty `DenseMap`.
    ///
    /// The map will not allocate until the first insertion.
    #[inline]
    pub fn new() -> Self {
        DenseMap {
            buckets: Vec::new(),
            num_entries: 0,
            num_tombstones: 0,
        }
    }

    /// Creates an empty `DenseMap` with at least the specified capacity.
    ///
    /// The actual capacity will be the next power of 2 >= `capacity`
    /// (or `MIN_CAPACITY`, whichever is larger).
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        let cap = Self::next_capacity(capacity);
        DenseMap {
            buckets: (0..cap).map(|_| DenseMapBucket::Empty).collect(),
            num_entries: 0,
            num_tombstones: 0,
        }
    }

    /// Inserts a key-value pair into the map.
    ///
    /// If the map already had this key present, the old value is replaced
    /// and returned. Otherwise, `None` is returned.
    ///
    /// # Examples
    /// ```
    /// # use llvm_native_core::support::dense_map::DenseMap;
    /// let mut map = DenseMap::new();
    /// assert_eq!(map.insert("key", 42), None);
    /// assert_eq!(map.insert("key", 99), Some(42));
    /// ```
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        // Ensure there's room
        if self.buckets.is_empty() {
            self.buckets = (0..Self::MIN_CAPACITY)
                .map(|_| DenseMapBucket::Empty)
                .collect();
        }

        // Check if we need to grow before insertion
        if self.needs_grow() {
            let new_cap = if self.buckets.is_empty() {
                Self::MIN_CAPACITY
            } else {
                self.buckets.len() * 2
            };
            self.rehash(new_cap);
        }

        let (idx, present) = self.find_bucket(&key);
        if present {
            // Replace existing value
            match &mut self.buckets[idx] {
                DenseMapBucket::Full {
                    value: existing, ..
                } => {
                    let old = existing.clone();
                    *existing = value;
                    Some(old)
                }
                _ => unreachable!(),
            }
        } else {
            // Insert new entry
            match &self.buckets[idx] {
                DenseMapBucket::Tombstone => {
                    self.num_tombstones -= 1;
                }
                _ => {}
            }
            self.buckets[idx] = DenseMapBucket::Full { key, value };
            self.num_entries += 1;
            None
        }
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// # Examples
    /// ```
    /// # use llvm_native_core::support::dense_map::DenseMap;
    /// let mut map = DenseMap::new();
    /// map.insert("key", 42);
    /// assert_eq!(map.get(&"key"), Some(&42));
    /// assert_eq!(map.get(&"missing"), None);
    /// ```
    pub fn get(&self, key: &K) -> Option<&V> {
        let (idx, present) = self.find_bucket(key);
        if present {
            self.buckets[idx].value()
        } else {
            None
        }
    }

    /// Returns a mutable reference to the value corresponding to the key.
    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        let (idx, present) = self.find_bucket(key);
        if present {
            self.buckets[idx].value_mut()
        } else {
            None
        }
    }

    /// Removes a key from the map, returning the value if the key was present.
    ///
    /// The bucket is marked as a Tombstone rather than Empty to preserve
    /// probe chains.
    pub fn remove(&mut self, key: &K) -> Option<V> {
        let (idx, present) = self.find_bucket(key);
        if present {
            match self.buckets[idx].take() { Some((_key, value)) => {
                self.num_entries -= 1;
                self.num_tombstones += 1;
                Some(value)
            } _ => {
                None
            }}
        } else {
            None
        }
    }

    /// Returns true if the map contains the specified key.
    #[inline]
    pub fn contains_key(&self, key: &K) -> bool {
        self.get(key).is_some()
    }

    /// Returns the number of entries in the map.
    #[inline]
    pub fn len(&self) -> usize {
        self.num_entries
    }

    /// Returns true if the map contains no entries.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.num_entries == 0
    }

    /// Returns the capacity of the map (total number of buckets).
    #[inline]
    pub fn capacity(&self) -> usize {
        self.buckets.len()
    }

    /// Clears the map, removing all entries.
    ///
    /// Note: this does not release memory; use `shrink_to_fit` after `clear`
    /// to free the allocation.
    pub fn clear(&mut self) {
        self.buckets.clear();
        self.num_entries = 0;
        self.num_tombstones = 0;
    }

    /// Reserves capacity for at least `additional` more entries.
    ///
    /// The map may reserve more space to avoid frequent reallocations.
    pub fn reserve(&mut self, additional: usize) {
        self.ensure_capacity(additional);
    }

    /// Shrinks the capacity to fit the current number of entries.
    ///
    /// Rehashes all entries into a new allocation sized to the minimum
    /// power-of-2 capacity that fits the entries.
    pub fn shrink_to_fit(&mut self) {
        if self.num_entries == 0 {
            self.buckets.clear();
            self.num_tombstones = 0;
            return;
        }
        let new_cap = Self::next_capacity(self.num_entries);
        if new_cap < self.buckets.len() {
            self.rehash(new_cap);
        }
    }

    /// Returns an iterator over the key-value pairs in unspecified order.
    #[inline]
    pub fn iter(&self) -> DenseMapIter<'_, K, V> {
        DenseMapIter {
            buckets: &self.buckets,
            index: 0,
        }
    }

    /// Returns an iterator over the keys in unspecified order.
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        self.iter().map(|(k, _)| k)
    }

    /// Returns an iterator over the values in unspecified order.
    pub fn values(&self) -> impl Iterator<Item = &V> {
        self.iter().map(|(_, v)| v)
    }

    /// Returns a mutable iterator over the values in unspecified order.
    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
        DenseMapIterMut {
            buckets: &mut self.buckets,
            index: 0,
        }
    }
}

// ============================================================================
// Default
// ============================================================================

impl<K, V> Default for DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    fn default() -> Self {
        Self::new()
    }
}

// ============================================================================
// Debug
// ============================================================================

impl<K, V> std::fmt::Debug for DenseMap<K, V>
where
    K: Eq + Hash + Clone + std::fmt::Debug,
    V: Clone + std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_map().entries(self.iter()).finish()
    }
}

// ============================================================================
// PartialEq
// ============================================================================

impl<K, V> PartialEq for DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone + PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }
        for (k, v) in self.iter() {
            match other.get(k) {
                Some(other_v) if *v == *other_v => {}
                _ => return false,
            }
        }
        true
    }
}

// ============================================================================
// IntoIterator for owned DenseMap (consuming iterator)
// ============================================================================

impl<K, V> IntoIterator for DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    type Item = (K, V);
    type IntoIter = DenseMapIntoIter<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        DenseMapIntoIter {
            buckets: self.buckets,
            index: 0,
        }
    }
}

/// Consuming iterator over a `DenseMap`.
pub struct DenseMapIntoIter<K, V> {
    buckets: Vec<DenseMapBucket<K, V>>,
    index: usize,
}

impl<K, V> Iterator for DenseMapIntoIter<K, V> {
    type Item = (K, V);

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.buckets.len() {
            match self.buckets[self.index].take() {
                Some((key, value)) => {
                    self.index += 1;
                    return Some((key, value));
                }
                None => {
                    self.index += 1;
                }
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.buckets.len() - self.index;
        (0, Some(remaining))
    }
}

// ============================================================================
// Iterator (shared reference)
// ============================================================================

/// Iterator over entries in a `DenseMap` (by shared reference).
///
/// Skips `Empty` and `Tombstone` buckets. Iteration order is unspecified.
pub struct DenseMapIter<'a, K, V> {
    buckets: &'a [DenseMapBucket<K, V>],
    index: usize,
}

impl<'a, K, V> Iterator for DenseMapIter<'a, K, V> {
    type Item = (&'a K, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.buckets.len() {
            match &self.buckets[self.index] {
                DenseMapBucket::Full { key, value } => {
                    self.index += 1;
                    return Some((key, value));
                }
                _ => {
                    self.index += 1;
                }
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.buckets.len() - self.index;
        (0, Some(remaining))
    }
}

// ============================================================================
// Iterator (mutable reference)
// ============================================================================

/// Iterator over values in a `DenseMap` (by mutable reference).
pub struct DenseMapIterMut<'a, K, V> {
    buckets: &'a mut [DenseMapBucket<K, V>],
    index: usize,
}

impl<'a, K, V> Iterator for DenseMapIterMut<'a, K, V> {
    type Item = &'a mut V;

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.buckets.len() {
            // SAFETY: We're borrowing different elements on each call.
            // Using raw pointer manipulation to work around borrow checker
            // limitations with mutable iteration over a slice.
            let ptr = self.buckets.as_mut_ptr();
            unsafe {
                let bucket = &mut *ptr.add(self.index);
                match bucket {
                    DenseMapBucket::Full { value, .. } => {
                        self.index += 1;
                        return Some(value);
                    }
                    _ => {
                        self.index += 1;
                    }
                }
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.buckets.len() - self.index;
        (0, Some(remaining))
    }
}

// ============================================================================
// IntoIterator for &DenseMap and &mut DenseMap
// ============================================================================

impl<'a, K, V> IntoIterator for &'a DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    type Item = (&'a K, &'a V);
    type IntoIter = DenseMapIter<'a, K, V>;

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

impl<'a, K, V> IntoIterator for &'a mut DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    type Item = (&'a K, &'a mut V);
    type IntoIter = DenseMapIterMutRef<'a, K, V>;

    fn into_iter(self) -> Self::IntoIter {
        DenseMapIterMutRef {
            buckets: &mut self.buckets,
            index: 0,
        }
    }
}

/// Iterator over key-value pairs in a `DenseMap` with mutable value references.
pub struct DenseMapIterMutRef<'a, K, V> {
    buckets: &'a mut [DenseMapBucket<K, V>],
    index: usize,
}

impl<'a, K, V> Iterator for DenseMapIterMutRef<'a, K, V> {
    type Item = (&'a K, &'a mut V);

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.buckets.len() {
            let ptr = self.buckets.as_mut_ptr();
            unsafe {
                let bucket = &mut *ptr.add(self.index);
                match bucket {
                    DenseMapBucket::Full { key, value } => {
                        self.index += 1;
                        return Some((&*key, value));
                    }
                    _ => {
                        self.index += 1;
                    }
                }
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.buckets.len() - self.index;
        (0, Some(remaining))
    }
}

// ============================================================================
// Clone
// ============================================================================

impl<K, V> Clone for DenseMap<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    fn clone(&self) -> Self {
        DenseMap {
            buckets: self.buckets.clone(),
            num_entries: self.num_entries,
            num_tombstones: self.num_tombstones,
        }
    }
}

// ============================================================================
// DenseSet
// ============================================================================

/// A set backed by a `DenseMap<T, ()>`.
///
/// Provides the same open-addressing behavior as `DenseMap` but stores
/// only keys (the value type is the unit type `()`).
///
/// @llvm_behavior: LLVM's `DenseSet<T>` is a convenience wrapper around
///   `DenseMap<T, detail::DenseSetEmpty>`.
pub struct DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    map: DenseMap<T, ()>,
}

impl<T> DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    /// Creates an empty `DenseSet`.
    #[inline]
    pub fn new() -> Self {
        DenseSet {
            map: DenseMap::new(),
        }
    }

    /// Creates an empty `DenseSet` with at least the specified capacity.
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        DenseSet {
            map: DenseMap::with_capacity(capacity),
        }
    }

    /// Inserts a value into the set.
    ///
    /// Returns `true` if the value was not already present.
    #[inline]
    pub fn insert(&mut self, value: T) -> bool {
        self.map.insert(value, ()).is_none()
    }

    /// Removes a value from the set.
    ///
    /// Returns `true` if the value was present.
    #[inline]
    pub fn remove(&mut self, value: &T) -> bool {
        self.map.remove(value).is_some()
    }

    /// Returns `true` if the set contains the value.
    #[inline]
    pub fn contains(&self, value: &T) -> bool {
        self.map.contains_key(value)
    }

    /// Returns the number of elements in the set.
    #[inline]
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns `true` if the set contains no elements.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Clears the set, removing all elements.
    #[inline]
    pub fn clear(&mut self) {
        self.map.clear();
    }

    /// Returns an iterator over the elements in unspecified order.
    #[inline]
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.map.keys()
    }

    /// Reserves capacity for at least `additional` more elements.
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        self.map.reserve(additional);
    }

    /// Returns the capacity of the underlying map.
    #[inline]
    pub fn capacity(&self) -> usize {
        self.map.capacity()
    }
}

impl<T> Default for DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    fn default() -> Self {
        Self::new()
    }
}

impl<T> IntoIterator for DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    type Item = T;
    type IntoIter = DenseSetIntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        DenseSetIntoIter {
            inner: self.map.into_iter(),
        }
    }
}

/// Consuming iterator over a `DenseSet`.
pub struct DenseSetIntoIter<T> {
    inner: DenseMapIntoIter<T, ()>,
}

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

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

impl<'a, T> IntoIterator for &'a DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    type Item = &'a T;
    type IntoIter = DenseSetIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        DenseSetIter {
            inner: self.map.iter(),
        }
    }
}

/// Iterator over elements in a `DenseSet` (by shared reference).
pub struct DenseSetIter<'a, T> {
    inner: DenseMapIter<'a, T, ()>,
}

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

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

impl<T> std::fmt::Debug for DenseSet<T>
where
    T: Eq + Hash + Clone + std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_set().entries(self.iter()).finish()
    }
}

impl<T> PartialEq for DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }
        for item in self.iter() {
            if !other.contains(item) {
                return false;
            }
        }
        true
    }
}

impl<T> Clone for DenseSet<T>
where
    T: Eq + Hash + Clone,
{
    fn clone(&self) -> Self {
        DenseSet {
            map: self.map.clone(),
        }
    }
}

// ============================================================================
// SmallDenseMap
// ============================================================================

/// A `DenseMap` variant that pre-allocates capacity for up to `N` entries.
///
/// This is a minimal implementation that wraps a `DenseMap` with an initial
/// capacity. A full inline-storage implementation (using stack allocation
/// for the first N entries) is a future optimization.
///
/// @llvm_behavior: LLVM's `SmallDenseMap<K, V, N>` uses inline storage for
///   the first N entries to avoid heap allocation for small maps.
pub struct SmallDenseMap<K, V, const N: usize>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    inner: DenseMap<K, V>,
}

impl<K, V, const N: usize> SmallDenseMap<K, V, N>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    /// Creates an empty `SmallDenseMap` with inline capacity for N entries.
    ///
    /// The first N insertions will use pre-allocated capacity; additional
    /// insertions will allocate on the heap.
    pub fn new() -> Self {
        SmallDenseMap {
            inner: DenseMap::with_capacity(N),
        }
    }

    /// Inserts a key-value pair into the map.
    ///
    /// Returns the old value if the key was already present.
    #[inline]
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        self.inner.insert(key, value)
    }

    /// Returns a reference to the value corresponding to the key.
    #[inline]
    pub fn get(&self, key: &K) -> Option<&V> {
        self.inner.get(key)
    }

    /// Returns true if the map contains the specified key.
    #[inline]
    pub fn contains_key(&self, key: &K) -> bool {
        self.inner.contains_key(key)
    }

    /// Returns the number of entries in the map.
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Returns true if the map contains no entries.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
}

impl<K, V, const N: usize> Default for SmallDenseMap<K, V, N>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    fn default() -> Self {
        Self::new()
    }
}

// ============================================================================
// Tests
// ============================================================================

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

    // --- DenseMap construction ---

    #[test]
    fn test_new_map_is_empty() {
        let map: DenseMap<i32, i32> = DenseMap::new();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn test_with_capacity() {
        let map: DenseMap<i32, i32> = DenseMap::with_capacity(16);
        assert!(map.is_empty());
        assert!(map.capacity() >= 16);
    }

    // --- DenseMap insert and get ---

    #[test]
    fn test_insert_and_get() {
        let mut map = DenseMap::new();
        assert_eq!(map.insert("hello", 42), None);
        assert_eq!(map.get(&"hello"), Some(&42));
        assert_eq!(map.get(&"world"), None);
    }

    #[test]
    fn test_insert_replace() {
        let mut map = DenseMap::new();
        map.insert("key", 1);
        assert_eq!(map.insert("key", 2), Some(1));
        assert_eq!(map.get(&"key"), Some(&2));
        assert_eq!(map.len(), 1);
    }

    #[test]
    fn test_insert_many() {
        let mut map = DenseMap::new();
        for i in 0..1000 {
            map.insert(i, i * 2);
        }
        assert_eq!(map.len(), 1000);
        for i in 0..1000 {
            assert_eq!(map.get(&i), Some(&(i * 2)));
        }
    }

    // --- DenseMap contains_key ---

    #[test]
    fn test_contains_key() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        assert!(map.contains_key(&"a"));
        assert!(!map.contains_key(&"b"));
    }

    // --- DenseMap remove ---

    #[test]
    fn test_remove() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);
        assert_eq!(map.remove(&"a"), Some(1));
        assert_eq!(map.get(&"a"), None);
        assert_eq!(map.len(), 1);
        assert_eq!(map.get(&"b"), Some(&2));
    }

    #[test]
    fn test_remove_nonexistent() {
        let mut map: DenseMap<i32, i32> = DenseMap::new();
        assert_eq!(map.remove(&42), None);
    }

    #[test]
    fn test_remove_then_reinsert() {
        let mut map = DenseMap::new();
        map.insert("key", 1);
        map.remove(&"key");
        // Reinsert should work (tombstone slot reused)
        assert_eq!(map.insert("key", 2), None);
        assert_eq!(map.get(&"key"), Some(&2));
        assert_eq!(map.len(), 1);
    }

    #[test]
    fn test_remove_tombstone_probe_chain() {
        let mut map = DenseMap::new();
        // Insert keys that may collide
        map.insert(1, "one");
        map.insert(17, "seventeen"); // Could collide depending on hash
        map.remove(&1);
        // Should still find 17 through the tombstone
        assert_eq!(map.get(&17), Some(&"seventeen"));
    }

    // --- DenseMap clear ---

    #[test]
    fn test_clear() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);
        map.clear();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
        assert_eq!(map.get(&"a"), None);
    }

    // --- DenseMap len / is_empty / capacity ---

    #[test]
    fn test_len_and_capacity() {
        let mut map = DenseMap::with_capacity(8);
        assert_eq!(map.len(), 0);
        assert_eq!(map.capacity(), 8);

        map.insert(1, "a");
        assert_eq!(map.len(), 1);
        assert!(!map.is_empty());
    }

    // --- DenseMap iteration ---

    #[test]
    fn test_iter() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);
        map.insert("c", 3);

        let mut collected: Vec<(&str, i32)> = map.iter().map(|(k, v)| (*k, *v)).collect();
        collected.sort_by_key(|(k, _)| *k);
        assert_eq!(collected, vec![("a", 1), ("b", 2), ("c", 3)]);
    }

    #[test]
    fn test_keys_and_values() {
        let mut map = DenseMap::new();
        map.insert("x", 10);
        map.insert("y", 20);

        let mut keys: Vec<&&str> = map.keys().collect();
        keys.sort();
        assert_eq!(keys, vec![&"x", &"y"]);

        let mut values: Vec<&i32> = map.values().collect();
        values.sort();
        assert_eq!(values, vec![&10, &20]);
    }

    #[test]
    fn test_values_mut() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);

        for v in map.values_mut() {
            *v *= 10;
        }

        let mut values: Vec<i32> = map.values().copied().collect();
        values.sort();
        assert_eq!(values, vec![10, 20]);
    }

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

    // --- DenseMap into_iter ---

    #[test]
    fn test_into_iter_owned() {
        let mut map = DenseMap::new();
        map.insert(1, "one");
        map.insert(2, "two");

        let mut collected: Vec<(i32, &str)> = map.into_iter().collect();
        collected.sort_by_key(|(k, _)| *k);
        assert_eq!(collected, vec![(1, "one"), (2, "two")]);
    }

    #[test]
    fn test_into_iter_ref() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);

        let mut collected: Vec<(&str, &i32)> = (&map).into_iter().map(|(k, v)| (*k, v)).collect();
        collected.sort_by_key(|(k, _)| *k);
        assert_eq!(collected, vec![("a", &1), ("b", &2)]);
    }

    #[test]
    fn test_into_iter_mut() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);

        for (k, v) in &mut map {
            *v *= 10;
        }

        assert_eq!(map.get(&"a"), Some(&10));
        assert_eq!(map.get(&"b"), Some(&20));
    }

    // --- DenseMap reserve and shrink ---

    #[test]
    fn test_reserve() {
        let mut map: DenseMap<i32, i32> = DenseMap::new();
        let cap_before = map.capacity();
        map.reserve(100);
        assert!(map.capacity() >= 100);
    }

    #[test]
    fn test_shrink_to_fit() {
        let mut map = DenseMap::with_capacity(64);
        map.insert(1, "a");
        map.insert(2, "b");
        map.shrink_to_fit();
        assert!(map.capacity() <= 16); // Should be reduced significantly
        assert_eq!(map.len(), 2);
    }

    #[test]
    fn test_shrink_to_fit_empty() {
        let mut map: DenseMap<i32, i32> = DenseMap::with_capacity(64);
        map.shrink_to_fit();
        assert_eq!(map.capacity(), 0);
    }

    // --- DenseMap clone ---

    #[test]
    fn test_clone() {
        let mut map = DenseMap::new();
        map.insert("a", 1);
        map.insert("b", 2);

        let cloned = map.clone();
        assert_eq!(cloned.len(), map.len());
        assert_eq!(cloned.get(&"a"), Some(&1));
        assert_eq!(cloned.get(&"b"), Some(&2));

        // Modifying clone doesn't affect original
        drop(cloned);
        assert_eq!(map.get(&"a"), Some(&1));
    }

    // --- DenseMap eq ---

    #[test]
    fn test_eq() {
        let mut a = DenseMap::new();
        a.insert("x", 1);
        a.insert("y", 2);

        let mut b = DenseMap::new();
        b.insert("y", 2);
        b.insert("x", 1);

        assert_eq!(a, b);

        let mut c = DenseMap::new();
        c.insert("x", 1);
        c.insert("y", 3);
        assert_ne!(a, c);
    }

    // --- DenseMap debug ---

    #[test]
    fn test_debug() {
        let mut map = DenseMap::new();
        map.insert("key", 42);
        let debug_str = format!("{:?}", map);
        assert!(debug_str.contains("key"));
        assert!(debug_str.contains("42"));
    }

    // --- DenseMap stress ---

    #[test]
    fn test_stress_insert_remove() {
        let mut map = DenseMap::new();
        let n = 500;

        // Insert
        for i in 0..n {
            map.insert(i, format!("val-{}", i));
        }
        assert_eq!(map.len(), n);

        // Verify
        for i in 0..n {
            assert_eq!(
                map.get(&i).map(|s| s.as_str()),
                Some(format!("val-{}", i).as_str())
            );
        }

        // Remove half
        for i in 0..n / 2 {
            map.remove(&i);
        }
        assert_eq!(map.len(), n - n / 2);

        // Verify remaining
        for i in n / 2..n {
            assert!(map.contains_key(&i));
        }

        // Re-insert removed keys
        for i in 0..n / 2 {
            map.insert(i, format!("new-{}", i));
        }
        assert_eq!(map.len(), n);
    }

    #[test]
    fn test_many_tombstones() {
        let mut map = DenseMap::new();
        // Insert many keys, then remove them all, then insert again
        for i in 0..100 {
            map.insert(i, i);
        }
        for i in 0..100 {
            map.remove(&i);
        }
        assert_eq!(map.len(), 0);
        assert!(map.is_empty());

        // Re-insert — should reuse tombstone slots
        for i in 0..100 {
            map.insert(i, i + 100);
        }
        assert_eq!(map.len(), 100);
        for i in 0..100 {
            assert_eq!(map.get(&i), Some(&(i + 100)));
        }
    }

    // --- DenseSet ---

    #[test]
    fn test_dense_set_basic() {
        let mut set = DenseSet::new();
        assert!(set.is_empty());

        assert!(set.insert(1));
        assert!(!set.insert(1)); // Duplicate
        assert!(set.insert(2));

        assert_eq!(set.len(), 2);
        assert!(set.contains(&1));
        assert!(set.contains(&2));
        assert!(!set.contains(&3));
    }

    #[test]
    fn test_dense_set_remove() {
        let mut set = DenseSet::new();
        set.insert("a");
        set.insert("b");

        assert!(set.remove(&"a"));
        assert!(!set.contains(&"a"));
        assert!(set.contains(&"b"));
        assert!(!set.remove(&"a")); // Already removed
    }

    #[test]
    fn test_dense_set_iter() {
        let mut set = DenseSet::new();
        set.insert(3);
        set.insert(1);
        set.insert(2);

        let mut collected: Vec<i32> = set.iter().copied().collect();
        collected.sort();
        assert_eq!(collected, vec![1, 2, 3]);
    }

    #[test]
    fn test_dense_set_clear() {
        let mut set = DenseSet::new();
        set.insert(1);
        set.insert(2);
        set.clear();
        assert!(set.is_empty());
        assert!(!set.contains(&1));
    }

    #[test]
    fn test_dense_set_eq() {
        let mut a = DenseSet::new();
        a.insert("x");
        a.insert("y");

        let mut b = DenseSet::new();
        b.insert("y");
        b.insert("x");

        assert_eq!(a, b);

        let mut c = DenseSet::new();
        c.insert("x");
        assert_ne!(a, c);
    }

    #[test]
    fn test_dense_set_into_iter() {
        let mut set = DenseSet::new();
        set.insert("a");
        set.insert("b");

        let mut collected: Vec<&str> = set.into_iter().collect();
        collected.sort();
        assert_eq!(collected, vec!["a", "b"]);
    }

    #[test]
    fn test_dense_set_capacity() {
        let set: DenseSet<i32> = DenseSet::with_capacity(32);
        assert!(set.capacity() >= 32);
        assert!(set.is_empty());
    }

    #[test]
    fn test_dense_set_debug() {
        let mut set = DenseSet::new();
        set.insert(1);
        set.insert(2);
        let debug_str = format!("{:?}", set);
        assert!(debug_str.contains('1'));
        assert!(debug_str.contains('2'));
    }

    // --- SmallDenseMap ---

    #[test]
    fn test_small_dense_map_basic() {
        let mut map: SmallDenseMap<&str, i32, 4> = SmallDenseMap::new();
        assert!(map.is_empty());

        map.insert("a", 1);
        map.insert("b", 2);

        assert_eq!(map.len(), 2);
        assert!(map.contains_key(&"a"));
        assert_eq!(map.get(&"a"), Some(&1));
        assert_eq!(map.get(&"b"), Some(&2));
        assert_eq!(map.get(&"c"), None);
    }

    #[test]
    fn test_small_dense_map_insert_replace() {
        let mut map: SmallDenseMap<i32, i32, 8> = SmallDenseMap::new();
        assert_eq!(map.insert(1, 100), None);
        assert_eq!(map.insert(1, 200), Some(100));
        assert_eq!(map.get(&1), Some(&200));
    }

    #[test]
    fn test_small_dense_map_over_inline() {
        // Exceeds the inline capacity of 2
        let mut map: SmallDenseMap<i32, i32, 2> = SmallDenseMap::new();
        for i in 0..10 {
            map.insert(i, i * 10);
        }
        assert_eq!(map.len(), 10);
        for i in 0..10 {
            assert_eq!(map.get(&i), Some(&(i * 10)));
        }
    }

    #[test]
    fn test_small_dense_map_default() {
        let map: SmallDenseMap<i32, i32, 8> = SmallDenseMap::default();
        assert!(map.is_empty());
    }

    // --- DenseMap with string keys (testing Hash + Eq properly) ---

    #[test]
    fn test_string_keys() {
        let mut map = DenseMap::new();
        map.insert("hello".to_string(), 1);
        map.insert("world".to_string(), 2);

        assert_eq!(map.get(&"hello".to_string()), Some(&1));
        assert_eq!(map.remove(&"world".to_string()), Some(2));
        assert!(!map.contains_key(&"world".to_string()));
    }

    // --- DenseMap get_mut ---

    #[test]
    fn test_get_mut() {
        let mut map = DenseMap::new();
        map.insert("key", vec![1, 2, 3]);

        if let Some(v) = map.get_mut(&"key") {
            v.push(4);
        }

        assert_eq!(map.get(&"key"), Some(&vec![1, 2, 3, 4]));
    }

    // --- Load factor and rehashing ---

    #[test]
    fn test_growth_on_insert() {
        let mut map: DenseMap<i32, i32> = DenseMap::with_capacity(4);
        let initial_cap = map.capacity();

        // Insert enough to trigger growth (load factor > 0.75)
        for i in 0..100 {
            map.insert(i, i);
        }

        assert!(map.capacity() > initial_cap);
        assert_eq!(map.len(), 100);
    }
}