algorithms_fourth 0.1.10

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

use super::{sequential::SequentialSearchST, ST};

pub struct SeparateChainingHashST<K: PartialOrd, V> {
    /// 键值对总数
    len: usize,
    /// 散列表大小
    m: usize,
    st: Vec<SequentialSearchST<K, V>>,
}
impl<K: Ord + Default + Hash, V: Default> SeparateChainingHashST<K, V> {
    pub fn new(cap: usize) -> Self {
        let st = Self::new_st(cap);
        SeparateChainingHashST { len: 0, m: cap, st }
    }
    pub fn hash(&self, k: &K) -> usize {
        Self::hash_for_m(k, self.m)
    }
    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 enumerate = &mut self.st;
        let mut st = Self::new_st(m);
        for item in enumerate {
            for (key, value) in item.iter_mut() {
                let i = Self::hash_for_m(&key, m);
                st[i].put(key, value)
            }
        }
        self.m = m;
        self.st = st;
    }
    fn new_st(cap: usize) -> Vec<SequentialSearchST<K, V>> {
        let mut st = Vec::with_capacity(cap);
        for _ in 0..cap {
            st.push(SequentialSearchST::default());
        }
        st
    }
    fn need_resize(&self) -> bool {
        self.len > 10 * self.m
    }
}

impl<K: Ord + Default + Hash, V: Default> ST<K, V> for SeparateChainingHashST<K, V> {
    fn put(&mut self, key: K, value: V) {
        if self.need_resize() {
            self.resize(2 * self.m)
        }
        assert!(!self.need_resize(), "len:{},m:{}", self.len, self.m);
        if !self.contains(&key) {
            self.len += 1;
        }
        let i = self.hash(&key);
        self.st[i].put(key, value)
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.st[self.hash(key)].get(key)
    }

    fn delete(&mut self, key: &K) {
        if self.contains(key) {
            self.len -= 1;
        }
        let i = self.hash(key);
        self.st[i].delete(key)
    }

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

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

    fn min(&self) -> Option<&K> {
        if self.is_empty() {
            None
        } else {
            self.st
                .iter()
                .filter(|it| !it.is_empty())
                .map(|it| it.min().unwrap())
                .min()
        }
    }

    fn max(&self) -> Option<&K> {
        let ans = if self.is_empty() {
            None
        } else {
            self.st
                .iter()
                .filter(|it| !it.is_empty())
                .map(|it| it.max().unwrap())
                .max()
        };
        ans
    }

    fn floor(&self, key: &K) -> Option<&K> {
        if self.is_empty() {
            None
        } else {
            self.st
                .iter()
                .filter(|it| !it.is_empty())
                .map(|it| it.floor(key))
                .filter(|it| it.is_some())
                .max()
                .unwrap()
        }
    }

    fn ceiling(&self, key: &K) -> Option<&K> {
        if self.is_empty() {
            None
        } else {
            self.st
                .iter()
                .filter(|it| !it.is_empty())
                .map(|it| it.ceiling(key))
                .filter(|it| it.is_some())
                .min()
                .unwrap()
        }
    }

    fn rank(&self, key: &K) -> usize {
        self.st.iter().map(|it| it.rank(key)).sum()
    }

    fn select(&self, k: usize) -> Option<&K> {
        let mut current_i = 0;
        let mut indexes = vec![0usize; self.m];
        let mut changed: bool;
        loop {
            if let Some((i, key)) = self
                .st
                .iter()
                .enumerate()
                .map(|(i, f)| (i, f.select(indexes[i])))
                .filter(|f| f.1.is_some())
                .min_by(|a, b| a.1.cmp(&b.1))
            {
                if current_i == k {
                    return key;
                }
                changed = true;
                indexes[i] += 1;
                current_i += 1;
            } else {
                changed = false;
            }

            if !changed {
                return None;
            }
        }
    }
}
#[cfg(test)]
mod test {
    use rand::seq::SliceRandom;

    use crate::search::ST;

    use super::SeparateChainingHashST;

    #[test]
    fn test() {
        let mut st = SeparateChainingHashST::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() {
            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);
        }
    }
}