algorithms_fourth 0.1.10

//!线性碰撞的HashMap
//!
//!## 使用
//!```
//! use algorithms_fourth::search::linear_probing_hash::LinearProbingHashST;
//!         use algorithms_fourth::search::ST;
//!         use rand::seq::SliceRandom;
//!         let mut st = LinearProbingHashST::new(1);
//!         let mut rng = rand::thread_rng();
//!         let n = 530;
//!         let mut arr: Vec<usize> = (1..=n).collect();
//!         arr.shuffle(&mut rng);
//!         for (i, key) in arr.iter().enumerate() {
//!             // println!("{},{}",i,key);
//!             assert_eq!(st.get(key), None);
//!             st.put(key.clone(), key + 10);
//!             assert_eq!(st.get(key), Some(&(key + 10)));
//!             assert_eq!(st.size(), i + 1);
//!         }
//!         let mut arr: Vec<usize> = (1..=n).collect();
//!         arr.shuffle(&mut rng);
//!         for (i, key) in arr.iter().enumerate() {
//!             assert_eq!(st.get(key), Some(&(key + 10)));
//!             st.delete(&key);
//!             assert_eq!(st.get(key), None);
//!             assert_eq!(st.size(), arr.len() - i - 1);
//!         }
//!```
use std::{
    collections::hash_map::DefaultHasher,
    hash::{Hash, Hasher},
};

use super::ST;

pub struct LinearProbingHashST<K, V> {
    /// 空间总数
    capacity: usize,
    /// 键值对总数
    len: usize,
    keys: Vec<Option<K>>,
    vals: Vec<Option<V>>,
}

impl<K: Default + Ord + Hash, V: Default> Default for LinearProbingHashST<K, V> {
    fn default() -> Self {
        Self::new(4)
    }
}
impl<K: Ord + Hash, V> LinearProbingHashST<K, V> {
    pub fn new(capacity: usize) -> Self {
        // assert!(capacity>1);
        let mut keys = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            keys.push(None);
        }
        let mut vals = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            vals.push(None);
        }
        LinearProbingHashST {
            capacity,
            len: 0,
            keys,
            vals,
        }
    }
    pub fn hash(&self, k: &K) -> usize {
        Self::hash_for_m(k, self.capacity)
    }
    pub fn hash_for_m(k: &K, m: usize) -> usize {
        let mut hasher = DefaultHasher::new();
        k.hash(&mut hasher);
        hasher.finish() as usize % m
    }
    fn resize(&mut self, m: usize) {
        let mut st = Self::new(m);
        for i in 0..self.capacity {
            if let Some(key) = self.keys[i].take() {
                st.put(key, self.vals[i].take().unwrap());
            }
        }
        self.capacity = st.capacity;
        self.keys = st.keys;
        self.vals = st.vals;
    }
    fn need_resize(&self) -> bool {
        self.len >= self.capacity / 2
    }
}
impl<K: Ord + Hash, V> ST<K, V> for LinearProbingHashST<K, V> {
    fn put(&mut self, key: K, value: V) {
        if self.need_resize() {
            self.resize(self.capacity * 2);
        }
        assert!(!self.need_resize());
        let mut i = self.hash(&key);
        while let Some(current_key) = &self.keys[i] {
            if &key == current_key {
                self.vals[i] = Some(value);
                return;
            }
            i = (i + 1) % self.capacity;
        }
        self.keys[i] = Some(key);
        self.vals[i] = Some(value);
        self.len += 1;
    }

    fn get(&self, key: &K) -> Option<&V> {
        if self.is_empty() {
            return None;
        }
        let mut i = self.hash(key);
        while let Some(current_key) = &self.keys[i] {
            if key == current_key {
                return self.vals[i].as_ref();
            }
            let next_i = (i + 1) % self.capacity;
            if next_i == i {
                break;
            }
            i = next_i;
        }
        None
    }

    fn delete(&mut self, key: &K) {
        let mut i = self.hash(key);
        while let Some(current_key) = &self.keys[i] {
            if key == current_key {
                self.keys[i] = None;
                self.vals[i] = None;
                self.len -= 1;
                i = (i + 1) % self.capacity;
                while self.keys[i].is_some() {
                    self.len -= 1;
                    let key = self.keys[i].take().unwrap();
                    let value = self.vals[i].take().unwrap();
                    self.put(key, value);
                    i = (i + 1) % self.capacity;
                }
                return;
            }
            i = (i + 1) % self.capacity;
        }
        if self.len <= self.capacity / 8 {
            self.resize(self.capacity / 2);
        }
    }

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

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

    fn min(&self) -> Option<&K> {
        self.keys.iter().filter_map(|f| f.as_ref()).min()
    }

    fn max(&self) -> Option<&K> {
        self.keys.iter().filter_map(|f| f.as_ref()).max()
    }

    fn floor(&self, key: &K) -> Option<&K> {
        self.keys
            .iter()
            .filter_map(|f| f.as_ref())
            .filter(|f| f <= &key)
            .max()
    }

    fn ceiling(&self, key: &K) -> Option<&K> {
        self.keys
            .iter()
            .filter_map(|f| f.as_ref())
            .filter(|f| f >= &key)
            .min()
    }

    fn rank(&self, key: &K) -> usize {
        self.keys
            .iter()
            .filter_map(|f| f.as_ref())
            .filter(|f| f < &key)
            .count()
    }

    fn select(&self, k: usize) -> Option<&K> {
        let mut keys: Vec<&K> = self.keys.iter().filter_map(|f| f.as_ref()).collect();
        keys.sort();
        keys.get(k).copied()
    }

    fn contains(&self, key: &K) -> bool {
        self.get(key).is_some()
    }

    fn delete_min(&mut self) {
        if let Some(min) = self.min() {
            let min = unsafe { (min as *const K).as_ref().unwrap() };
            self.delete(min);
        }
    }

    fn delete_max(&mut self) {
        if let Some(max) = self.max() {
            let max = unsafe { (max as *const K).as_ref().unwrap() };
            self.delete(max);
        }
    }

    fn size_in(&self, lo: &K, hi: &K) -> usize {
        if hi < lo {
            0
        } else if self.contains(hi) {
            self.rank(hi) - self.rank(lo) + 1
        } else {
            self.rank(hi) - self.rank(lo)
        }
    }
}

#[cfg(test)]
mod test {

    #[test]
    fn test() {
        use super::LinearProbingHashST;
        use crate::search::ST;
        use rand::seq::SliceRandom;
        let mut st = LinearProbingHashST::new(1);
        let mut rng = rand::thread_rng();
        let n = 530;
        let mut arr: Vec<usize> = (1..=n).collect();
        arr.shuffle(&mut rng);
        for (i, key) in arr.iter().enumerate() {
            // println!("{},{}",i,key);
            assert_eq!(st.get(key), None);
            st.put(key.clone(), key + 10);
            assert_eq!(st.get(key), Some(&(key + 10)));
            assert_eq!(st.size(), i + 1);
        }
        let mut arr: Vec<usize> = (1..=n).collect();
        arr.shuffle(&mut rng);
        for (i, key) in arr.iter().enumerate() {
            assert_eq!(st.get(key), Some(&(key + 10)));
            st.delete(&key);
            assert_eq!(st.get(key), None);
            assert_eq!(st.size(), arr.len() - i - 1);
        }
    }
}