Custom hash map implementation

lib.rs

use std::{
    borrow::Borrow,
    fmt::Debug,
    hash::{BuildHasher, Hash, Hasher, RandomState},
};
use smallvec::{smallvec, SmallVec};

#[derive(Debug, PartialEq, thiserror::Error)]
pub enum MapError {
    /// Error indicating that a key was not found in the [`Map`].
    #[error("Key not found in Map")]
    NotFound,
}

pub enum Entry<'a, K, V, S> {
    Occupied(OccupiedEntry<'a, K, V, S>),
    Vacant(VacantEntry<'a, K, V, S>),
}

impl<'a, K, V, S> Entry<'a, K, V, S>
where
    K: Hash + Eq,
    S: BuildHasher,
{
    pub fn or_insert(self, default: V) -> &'a mut V {
        match self {
            Entry::Occupied(entry) => entry.into_mut(),
            Entry::Vacant(entry) => entry.insert(default),
        }
    }

    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
        match self {
            Entry::Occupied(entry) => entry.into_mut(),
            Entry::Vacant(entry) => entry.insert(default()),
        }
    }

    pub fn and_modify<F: FnOnce(&mut V)>(self, f: F) -> Self {
        match self {
            Entry::Occupied(mut entry) => {
                f(entry.get_mut());
                Entry::Occupied(entry)
            }
            Entry::Vacant(entry) => Entry::Vacant(entry), // No modification for vacant entries
        }
    }
}

pub struct OccupiedEntry<'a, K, V, S> {
    map: &'a mut Map<K, V, S>,
    key: K,
    bucket_index: usize,
    item_index: usize,
}

impl<'a, K, V, S> OccupiedEntry<'a, K, V, S> {
    pub fn key(&self) -> &K {
        &self.key
    }

    pub fn get(&self) -> &V {
        &self.map.buckets[self.bucket_index][self.item_index].1
    }

    pub fn get_mut(&mut self) -> &mut V {
        &mut self.map.buckets[self.bucket_index][self.item_index].1
    }

    pub fn into_mut(self) -> &'a mut V {
        &mut self.map.buckets[self.bucket_index][self.item_index].1
    }

    pub fn insert(&mut self, value: V) -> V {
        std::mem::replace(&mut self.map.buckets[self.bucket_index][self.item_index].1, value)
    }

    pub fn remove(self) -> V {
        let (_, value) = self.map.buckets[self.bucket_index].swap_remove(self.item_index);
        self.map.len -= 1;
        value
    }
}

pub struct VacantEntry<'a, K, V, S> {
    map: &'a mut Map<K, V, S>,
    key: K,
    bucket_index: usize,
}

impl<'a, K, V, S> VacantEntry<'a, K, V, S>
where
    K: Hash + Eq,
    S: BuildHasher,
{
    pub fn key(&self) -> &K {
        &self.key
    }

    pub fn into_key(self) -> K {
        self.key
    }

    pub fn insert(self, value: V) -> &'a mut V {
        self.map.buckets[self.bucket_index].push((self.key, value));
        self.map.len += 1;

        // Check if we need to grow
        if self.map.len > Map::<K, V, S>::BUCKET_SIZE * self.map.buckets.len() {
            self.map.grow();
            // After growing, we need to find the new location
            let new_bucket = self.map.bucket_for(&self.map.buckets[self.bucket_index].last().unwrap().0);
            let new_index = self.map.buckets[new_bucket].len() - 1;
            &mut self.map.buckets[new_bucket][new_index].1
        } else {
            let index = self.map.buckets[self.bucket_index].len() - 1;
            &mut self.map.buckets[self.bucket_index][index].1
        }
    }
}

pub struct Map<K, V, S = RandomState> {
    build_hasher: S,
    buckets: Vec<SmallVec<[(K, V); 2]>>, // Inline first 2 items
    len: usize,
}

impl<K, V, S> Map<K, V, S> {
    const BUCKET_SIZE: usize = 8; // Number of items per bucket before growing

    /// Creates a new [`Map`] with the given [`Hasher`] builder.
    pub fn with_hasher(build_hasher: S) -> Self {
        Self {
            build_hasher,
            buckets: Vec::new(),
            len: 0,
        }
    }

    pub fn iter(&self) -> impl Iterator<Item=(&K, &V)> {
        self.buckets.iter().flat_map(|bucket| bucket.iter().map(|(k, v)| (k, v)))
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item=(&mut K, &mut V)> {
        self.buckets.iter_mut().flat_map(|bucket| bucket.iter_mut().map(|(k, v)| (k, v)))
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn with_capacity(capacity: usize) -> Self
    where
        S: Default,
    { Self::with_capacity_and_hasher(capacity, S::default()) }
    
    pub fn with_capacity_and_hasher(capacity: usize, build_hasher: S) -> Self {
        let bucket_count = (capacity / Self::BUCKET_SIZE).max(4);
        Self {
            build_hasher,
            buckets: (0..bucket_count).map(|_| SmallVec::new()).collect(),
            len: 0,
        }
    }

    pub fn capacity(&self) -> usize {
        self.buckets.len() * Self::BUCKET_SIZE
    }
}

impl<K, V, S> IntoIterator for Map<K, V, S> {
    type Item = (K, V);
    type IntoIter = std::iter::FlatMap<
        std::vec::IntoIter<SmallVec<[(K, V); 2]>>,
        smallvec::IntoIter<[(K, V); 2]>,
        fn(SmallVec<[(K, V); 2]>) -> smallvec::IntoIter<[(K, V); 2]>,
    >;
    
    fn into_iter(self) -> Self::IntoIter {
        self.buckets.into_iter().flat_map(|bucket| bucket.into_iter())
    }
}

// Note: this is only implemented for Map<K, V, RandomState>!
impl<K, V> Map<K, V> {
    /// Creates a new [`Map`] with the default [`BuildHasher`].
    pub fn new() -> Self {
        Self::with_hasher(Default::default())
    }
}

impl<K, V, S> Map<K, V, S>
where
    K: Hash + Eq,
    S: BuildHasher,
{
    /// Implements the [`Entry`] API for the [`Map`].
    /// Allows for more ergonomic insertion and retrieval of values.
    /// This method returns an [`Entry`] enum which can be either
    /// [`Occupied`] or [`Vacant`].
    pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S> {
        // Ensure we have buckets
        if self.buckets.is_empty() {
            self.grow();
        }
        
        let bucket_index = self.bucket_for(&key);
        
        // Look for the key in the bucket
        if let Some(item_index) = self.buckets[bucket_index]
            .iter()
            .position(|(k, _)| *k == key)
        {
            Entry::Occupied(OccupiedEntry {
                map: self,
                key,
                bucket_index,
                item_index,
            })
        } else {
            Entry::Vacant(VacantEntry {
                map: self,
                key,
                bucket_index,
            })
        }
    }
    
    /// Given a key, returns the index of the bucket it belongs to.
    fn bucket_for<Q>(&self, key: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: Hash + ?Sized,
    {
        if self.buckets.is_empty() {
            return 0; // No buckets, return the first one
        }
        
        let mut hasher = self.build_hasher.build_hasher();
        key.hash(&mut hasher);

        (hasher.finish() as usize) % self.buckets.len().max(1)
    }

    /// Grows the [`Map`] by doubling its capacity.
    fn grow(&mut self) {
        let old_bucket_count = self.buckets.len();
        let new_bucket_count = (self.buckets.len() * 2).max(4);
        self.buckets.resize_with(new_bucket_count, || smallvec![]);

        // Rehash and move pairs around
        for check_bucket in 0..old_bucket_count {
            let mut index = 0;
            while index < self.buckets[check_bucket].len() {
                let correct_bucket = self.bucket_for(&self.buckets[check_bucket][index].0);
                if correct_bucket != check_bucket {
                    let pair = self.buckets[check_bucket].swap_remove(index);
                    self.buckets[correct_bucket].push(pair);
                } else {
                    index += 1;
                }
            }
        }
    }

    /// Inserts a key-value pair into the [`Map`], returning the old value if
    /// the key was already present.
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        // Special case for when the map is empty (no buckets)
        if self.buckets.is_empty() {
            self.grow();

            let bucket = self.bucket_for(&key);
            self.buckets[bucket].push((key, value));
            self.len += 1;

            return None;
        }

        let bucket = self.bucket_for(&key);
        let pair = self.buckets[bucket].iter_mut().find(|(k, _)| *k == key);
        match pair {
            Some((_, v)) => Some(std::mem::replace(v, value)),
            None => {
                self.buckets[bucket].push((key, value));
                self.len += 1;

                // Check if we have more than BUCKET_SIZE elements per bucket
                // (on average) and then grow if that's the case
                if self.len > Self::BUCKET_SIZE * self.buckets.len() {
                    self.grow();
                }

                None
            }
        }
    }

    /// Returns the value associated with the given key.
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if self.buckets.is_empty() {
            return None; // No buckets, no values
        }
        let bucket = self.bucket_for(key);
        self.buckets[bucket]
            .iter()
            .find_map(|pair| (key == pair.0.borrow()).then_some(&pair.1))
    }
    
    /// Returns a mutable reference to the value associated with the given key.
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if self.buckets.is_empty() {
            return None; // No buckets, no values
        }
        let bucket = self.bucket_for(key);
        self.buckets[bucket]
            .iter_mut()
            .find_map(|(k, v)| (key == (*k).borrow()).then_some(v))
    }
    
    /// Indicates whether the map contains a given key.
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if self.buckets.is_empty() {
            return false; // No buckets, no keys
        }
        let bucket = self.bucket_for(key);
        self.buckets[bucket]
            .iter()
            .any(|(k, _)| k.borrow() == key)
    }
    
    /// Removes the value associated with the given key.
    /// Returns an error if the key is not present.
    pub fn remove<Q>(&mut self, key: &Q) -> Result<(), MapError>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if let None = self.pop(key) {
            Err(MapError::NotFound)
        } else {
            Ok(())
        }
    }

    /// Removes and returns the value associated with a given key.
    /// Returns `None` if the key is not present.
    pub fn pop<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if self.buckets.is_empty() {
            return None; // No buckets, no values
        }
        let bucket = self.bucket_for(key);
        if let Some(pos) = self.buckets[bucket]
            .iter()
            .position(|(k, _)| k.borrow() == key)
        {
            let (_, value) = self.buckets[bucket].swap_remove(pos);
            self.len -= 1;
            Some(value)
        } else {
            None
        }
    }
    
    /// Clears the [`Map`], removing all key-value pairs.
    pub fn clear(&mut self) {
        for bucket in &mut self.buckets {
            bucket.clear();
        }
        self.len = 0;
    }
    
    /// Removes all key-value pairs from the [`Map`] that don't match a predicate.
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&K, &mut V) -> bool,
    {
        for bucket in &mut self.buckets {
            let mut i = 0;
            while i < bucket.len() {
                let (key, value) = &mut bucket[i];
                if !f(key, value) {
                    bucket.swap_remove(i);
                    self.len -= 1;
                } else {
                    i += 1; // Only increment if we didn't remove
                }
            }
        }
    }

    /// Returns an iterator over the keys in the [`Map`].
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        self.iter().map(|(key, _)| key)
    }

    /// Returns an iterator over the values in the [`Map`].
    pub fn values(&self) -> impl Iterator<Item = &V> {
        self.iter().map(|(_, value)| value)
    }

    /// Returns an iterator over the key-value pairs in the [`Map`].
    pub fn items(&self) -> impl Iterator<Item = (&K, &V)> {
        self.iter().map(|(key, value)| (key, value))
    }

    /// Returns the key associated with a given value, if it exists.
    pub fn get_by_value<Q>(&self, value: &Q) -> Option<K>
    where
        K: Clone + Eq + Hash,
        V: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        for bucket in &self.buckets {
            for (key, v2) in bucket {
                if v2.borrow() == value {
                    return Some(key.clone());
                }
            }
        }
        None
    }

    /// Shrinks the [`Map`] to fit its current size, reducing memory usage.
    pub fn shrink_to_fit(&mut self) {
        if self.len == 0 {
            self.buckets.clear();
            return;
        }
        
        // Calculate optimal bucket count
        let optimal_buckets = ((self.len / Self::BUCKET_SIZE).max(1)).next_power_of_two();
        
        if optimal_buckets < self.buckets.len() {
            // Create a new smaller bucket array and rehash
            let old_buckets = std::mem::take(&mut self.buckets);
            self.buckets = (0..optimal_buckets).map(|_| SmallVec::new()).collect();
            
            for bucket in old_buckets {
                for (key, value) in bucket {
                    let new_bucket = self.bucket_for(&key);
                    self.buckets[new_bucket].push((key, value));
                }
            }
        }
    }
}

impl<K, V, S> Debug for Map<K, V, S>
where
    K: Debug,
    V: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut d = f.debug_map();
        for pair in self.buckets.iter().flat_map(|b| b.iter()) {
            d.entry(&pair.0, &pair.1);
        }

        d.finish()
    }
}

impl <K, V> Default for Map<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

impl<K, V, S> Clone for Map<K, V, S>
where
    K: Clone,
    V: Clone,
    S: Clone,
{
    fn clone(&self) -> Self {
        Self {
            build_hasher: self.build_hasher.clone(),
            buckets: self.buckets.clone(),
            len: self.len,
        }
    }
}

impl<K, V, S> PartialEq for Map<K, V, S>
where
    K: Eq + Hash,
    V: PartialEq,
    S: BuildHasher,
{
    fn eq(&self, other: &Self) -> bool {
        if self.len != other.len {
            return false;
        }
        self.iter().all(|(k, v)| other.get(k).map_or(false, |v2| v == v2))
    }
}

impl<K, V, S> Eq for Map<K, V, S>
where
    K: Eq + Hash,
    V: Eq,
    S: BuildHasher,
{} // No implementation needed, just a marker trait

impl<K, V, S> FromIterator<(K, V)> for Map<K, V, S>
where
    K: Hash + Eq,
    S: BuildHasher + Default,
{
    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let (lower_bound, _) = iter.size_hint();
        let mut map = Self::with_capacity(lower_bound);
        
        for (k, v) in iter {
            map.insert(k, v);
        }
        
        map
    }
}

impl<K, V, S> Extend<(K, V)> for Map<K, V, S>
where
    K: Hash + Eq,
    S: BuildHasher + Default,
{
    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
        for (k, v) in iter {
            self.insert(k, v);
        }
    }
}

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

    #[test]
    fn test_default_map() {
        let map: Map<String, i32> = Map::new();
        assert_eq!(map.len, 0);
        assert!(map.buckets.is_empty());
        assert!(map.keys().collect::<Vec<_>>().is_empty());
        assert!(map.values().collect::<Vec<_>>().is_empty());
        assert!(map.items().collect::<Vec<_>>().is_empty());
    }

    #[test]
    fn test_insert_and_get() {
        let mut map = Map::new();
        assert!(map.get("foo").is_none());

        map.insert("foo".to_string(), 42);
        assert_eq!(map.len, 1);
        assert!(matches!(map.get("foo"), Some(42)));

        // Inserting the same key again should replace the value
        map.insert("foo".to_string(), 100);
        assert_eq!(map.len, 1);
        assert!(matches!(map.get("foo"), Some(100)));
    }

    #[test]
    fn test_remove_and_pop() {
        let mut map = Map::new();
        map.insert("foo".to_string(), 42);
        assert_eq!(map.len, 1);

        // Remove an existing key
        assert!(matches!(map.remove("foo"), Ok(())));
        assert_eq!(map.len, 0);
        assert!(map.get("foo").is_none());

        // Try to remove a non-existing key
        assert!(matches!(map.remove("bar"), Err(MapError::NotFound)));

        // Insert again and pop
        map.insert("baz".to_string(), 100);
        assert_eq!(map.len, 1);
        assert!(matches!(map.pop("baz"), Some(100)));
        assert_eq!(map.len, 0);
    }

    #[test]
    fn test_grow() {
        let mut map = Map::new();
        assert_eq!(map.buckets.len(), 0);

        // Insert the first item to trigger the initial growth
        map.insert("key-1".to_string(), -1);
        assert_eq!(map.buckets.len(), 4);

        // Insert more items to trigger further growth
        for i in 0..32 {
            map.insert(format!("key{}", i), i);
        }
        assert_eq!(map.len, 33);
        assert!(map.buckets.len() > 4); // Ensure that the bucket count has grown
    }

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

        let mut keys = map.keys().map(|k| k.to_string()).collect::<Vec<String>>();
        keys.sort();
        assert_eq!(keys, vec!["a".to_string(), "b".to_string(), "c".to_string()]);

        let mut values = map.values().map(|v| *v).collect::<Vec<i32>>();
        values.sort();
        assert_eq!(values, vec![1, 2, 3]);

        let mut items = map.items().map(|(k, v)| (k.to_string(), *v)).collect::<Vec<(String, i32)>>();
        items.sort();
        assert_eq!(items, vec![("a".to_string(), 1), ("b".to_string(), 2), ("c".to_string(), 3)]);
    }

    #[test]
    fn test_get_by_value() {
        let mut map = Map::new();
        map.insert("key1".to_string(), 10);

        // Test getting by value
        assert_eq!(map.get_by_value(&10), Some("key1".to_string()));
    }

    #[test]
    fn test_entry_vacant() {
        let mut map = Map::new();
        
        // Test vacant entry
        match map.entry("key1".to_string()) {
            Entry::Vacant(entry) => {
                assert_eq!(entry.key(), "key1");
                let value_ref = entry.insert(42);
                assert_eq!(*value_ref, 42);
            }
            Entry::Occupied(_) => panic!("Expected vacant entry"),
        }
        
        assert_eq!(map.len(), 1);
        assert_eq!(map.get("key1"), Some(&42));
    }

    #[test]
    fn test_entry_occupied() {
        let mut map = Map::new();
        map.insert("key1".to_string(), 42);
        
        // Test occupied entry
        match map.entry("key1".to_string()) {
            Entry::Occupied(mut entry) => {
                assert_eq!(entry.key(), "key1");
                assert_eq!(entry.get(), &42);
                
                // Test get_mut
                *entry.get_mut() = 100;
                assert_eq!(entry.get(), &100);
                
                // Test insert (replace)
                let old_value = entry.insert(200);
                assert_eq!(old_value, 100);
                assert_eq!(entry.get(), &200);
            }
            Entry::Vacant(_) => panic!("Expected occupied entry"),
        }
        
        assert_eq!(map.len(), 1);
        assert_eq!(map.get("key1"), Some(&200));
    }

    #[test]
    fn test_entry_occupied_remove() {
        let mut map = Map::new();
        map.insert("key1".to_string(), 42);
        map.insert("key2".to_string(), 84);
        
        // Test occupied entry removal
        match map.entry("key1".to_string()) {
            Entry::Occupied(entry) => {
                let removed_value = entry.remove();
                assert_eq!(removed_value, 42);
            }
            Entry::Vacant(_) => panic!("Expected occupied entry"),
        }
        
        assert_eq!(map.len(), 1);
        assert_eq!(map.get("key1"), None);
        assert_eq!(map.get("key2"), Some(&84));
    }

    #[test]
    fn test_entry_vacant_into_key() {
        let mut map: Map<String, i32> = Map::new();
        
        // Test vacant entry into_key
        match map.entry("key1".to_string()) {
            Entry::Vacant(entry) => {
                let key = entry.into_key();
                assert_eq!(key, "key1");
            }
            Entry::Occupied(_) => panic!("Expected vacant entry"),
        }
        
        // Map should still be empty since we didn't insert
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn test_entry_occupied_into_mut() {
        let mut map = Map::new();
        map.insert("key1".to_string(), 42);
        
        // Test occupied entry into_mut
        match map.entry("key1".to_string()) {
            Entry::Occupied(entry) => {
                let value_ref = entry.into_mut();
                *value_ref = 100;
            }
            Entry::Vacant(_) => panic!("Expected occupied entry"),
        }
        
        assert_eq!(map.get("key1"), Some(&100));
    }

    #[test]
    fn test_entry_or_insert() {
        let mut map = Map::new();
        
        // Test or_insert pattern with vacant entry
        let value1 = match map.entry("key1".to_string()) {
            Entry::Vacant(entry) => entry.insert(42),
            Entry::Occupied(entry) => entry.into_mut(),
        };
        assert_eq!(*value1, 42);
        
        // Test or_insert pattern with occupied entry
        let value2 = match map.entry("key1".to_string()) {
            Entry::Vacant(entry) => entry.insert(100),
            Entry::Occupied(entry) => entry.into_mut(),
        };
        assert_eq!(*value2, 42); // Should still be the original value
        
        assert_eq!(map.len(), 1);
    }

    #[test]
    fn test_entry_with_growth() {
        let mut map = Map::new();
        
        // Insert many items using entry API to test growth
        for i in 0..50 {
            match map.entry(format!("key{}", i)) {
                Entry::Vacant(entry) => {
                    entry.insert(i);
                }
                Entry::Occupied(_) => panic!("Should be vacant"),
            }
        }
        
        assert_eq!(map.len(), 50);
        
        // Verify all items are accessible
        for i in 0..50 {
            assert_eq!(map.get(&format!("key{}", i)), Some(&i));
        }
    }

    #[test]
    fn test_clone() {
        let mut map = Map::new();
        map.insert("key1", 42);
        map.insert("key2", 84);
        
        let cloned = map.clone();
        assert_eq!(map.len(), cloned.len());
        assert_eq!(map.get("key1"), cloned.get("key1"));
        assert_eq!(map.get("key2"), cloned.get("key2"));
    }

    #[test]
    fn test_partial_eq() {
        let mut map1 = Map::new();
        let mut map2 = Map::new();
        
        // Empty maps should be equal
        assert_eq!(map1, map2);
        
        // Add same elements
        map1.insert("key1", 42);
        map1.insert("key2", 84);
        map2.insert("key1", 42);
        map2.insert("key2", 84);
        assert_eq!(map1, map2);
        
        // Different values should not be equal
        map2.insert("key1", 100);
        assert_ne!(map1, map2);
        
        // Different lengths should not be equal
        map2.insert("key3", 126);
        assert_ne!(map1, map2);
    }

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

    #[test]
    fn test_default() {
        let map: Map<String, i32> = Map::default();
        assert_eq!(map.len(), 0);
        assert!(map.is_empty());
    }

    #[test]
    fn test_capacity_methods() {
        let map = Map::<String, i32>::with_capacity(10);
        assert!(map.capacity() >= 10);
        
        let map2 = Map::<String, i32>::with_capacity_and_hasher(20, RandomState::new());
        assert!(map2.capacity() >= 20);
    }

    #[test]
    fn test_clear() {
        let mut map = Map::new();
        map.insert("key1", 42);
        map.insert("key2", 84);
        assert_eq!(map.len(), 2);
        
        map.clear();
        assert_eq!(map.len(), 0);
        assert!(map.is_empty());
        assert!(map.get("key1").is_none());
    }

    #[test]
    fn test_retain() {
        let mut map = Map::new();
        map.insert("key1", 10);
        map.insert("key2", 20);
        map.insert("key3", 30);
        
        // Retain only values > 15
        map.retain(|_, v| *v > 15);
        
        assert_eq!(map.len(), 2);
        assert!(map.get("key1").is_none());
        assert_eq!(map.get("key2"), Some(&20));
        assert_eq!(map.get("key3"), Some(&30));
    }

    #[test]
    fn test_contains_key() {
        let mut map = Map::new();
        assert!(!map.contains_key("key1"));
        
        map.insert("key1", 42);
        assert!(map.contains_key("key1"));
        assert!(!map.contains_key("key2"));
    }

    #[test]
    fn test_get_mut() {
        let mut map = Map::new();
        map.insert("key1", 42);
        
        if let Some(value) = map.get_mut("key1") {
            *value = 100;
        }
        
        assert_eq!(map.get("key1"), Some(&100));
        assert!(map.get_mut("nonexistent").is_none());
    }

    #[test]
    fn test_iterators() {
        let mut map = Map::new();
        map.insert("a", 1);
        map.insert("b", 2);
        map.insert("c", 3);
        
        // Test iter
        let mut items: Vec<_> = map.iter().collect();
        items.sort_by_key(|(k, _)| *k);
        assert_eq!(items, vec![(&"a", &1), (&"b", &2), (&"c", &3)]);
        
        // Test iter_mut
        for (_, v) in map.iter_mut() {
            *v *= 2;
        }
        assert_eq!(map.get("a"), Some(&2));
        assert_eq!(map.get("b"), Some(&4));
        assert_eq!(map.get("c"), Some(&6));
        
        // Test into_iter
        let items: Vec<_> = map.into_iter().collect();
        assert_eq!(items.len(), 3);
    }

    #[test]
    fn test_from_iterator() {
        let data = vec![("key1", 42), ("key2", 84), ("key3", 126)];
        let map: Map<&str, i32> = data.into_iter().collect();
        
        assert_eq!(map.len(), 3);
        assert_eq!(map.get("key1"), Some(&42));
        assert_eq!(map.get("key2"), Some(&84));
        assert_eq!(map.get("key3"), Some(&126));
    }

    #[test]
    fn test_extend() {
        let mut map = Map::new();
        map.insert("key1", 42);
        
        let additional = vec![("key2", 84), ("key3", 126)];
        map.extend(additional);
        
        assert_eq!(map.len(), 3);
        assert_eq!(map.get("key2"), Some(&84));
        assert_eq!(map.get("key3"), Some(&126));
    }

    #[test]
    fn test_entry_or_insert_methods() {
        let mut map = Map::new();
        
        // Test or_insert
        let value1 = map.entry("key1".to_string()).or_insert(42);
        assert_eq!(*value1, 42);
        
        let value2 = map.entry("key1".to_string()).or_insert(100);
        assert_eq!(*value2, 42); // Should not change
        
        // Test or_insert_with
        let value3 = map.entry("key2".to_string()).or_insert_with(|| 84);
        assert_eq!(*value3, 84);
        
        // Test and_modify
        map.entry("key1".to_string())
            .and_modify(|v| *v *= 2)
            .or_insert(0);
        assert_eq!(map.get("key1"), Some(&84));
        
        map.entry("key3".to_string())
            .and_modify(|v| *v *= 2)
            .or_insert(200);
        assert_eq!(map.get("key3"), Some(&200));
    }

    #[test]
    fn test_shrink_to_fit() {
        let mut map = Map::new();
        
        // Fill map to trigger growth
        for i in 0..100 {
            map.insert(format!("key{}", i), i);
        }
        let initial_capacity = map.capacity();
        
        // Remove most items
        for i in 10..100 {
            map.pop(&format!("key{}", i));
        }
        
        // Shrink should reduce capacity
        map.shrink_to_fit();
        assert!(map.capacity() <= initial_capacity);
        
        // Verify remaining items are still accessible
        for i in 0..10 {
            assert_eq!(map.get(&format!("key{}", i)), Some(&i));
        }
    }

    #[test]
    fn test_edge_cases() {
        let mut map = Map::new();
        
        // Test empty map operations
        assert!(map.get("key").is_none());
        assert!(map.get_mut("key").is_none());
        assert!(!map.contains_key("key"));
        assert_eq!(map.remove("key"), Err(MapError::NotFound));
        assert!(map.pop("key").is_none());
        
        // Test single element
        map.insert("single", 1);
        assert_eq!(map.len(), 1);
        assert_eq!(map.get("single"), Some(&1));
        
        // Test overwriting
        let old = map.insert("single", 2);
        assert_eq!(old, Some(1));
        assert_eq!(map.len(), 1);
        assert_eq!(map.get("single"), Some(&2));
    }
}