mutcrab 0.1.1

#![allow(unused)]

use mutcrab::base::numbers::next_power_of_two;
use mutcrab::collection::map::{Map, RawTable, Entry};
use std::hash::{DefaultHasher, Hash, Hasher};

struct Node<K, V> {
    hash: u32,
    key: K,
    value: V,
    next: Option<Box<Node<K, V>>>,
}

pub struct HashMap<K, V> {
    size: u32,
    tab: Vec<Option<Box<Node<K, V>>>>,
    mask: u32,
    threshold: u32,
}

const DEFAULT_LOAD_FACTOR:f32 = 0.75;

impl <K,V> Node<K, V> {
    fn set_value(&mut self, new_value:V) ->V {
        std::mem::replace(&mut self.value, new_value)
    }
}


impl<K, V> HashMap<K, V>
where
    K: Eq + Hash,
{
    pub fn new() -> HashMap<K, V> {
        Self::with_capacity(16)
    }

    pub fn with_capacity(init_cap: u32) -> HashMap<K, V> {
        let capacity = next_power_of_two(init_cap);
        HashMap {
            size: 0,
            tab: Vec::new(),
            mask: 0,
            threshold: capacity,
        }
    }

    pub fn of(key: K, value: V) -> HashMap<K, V> {
        let mut map = Self::with_capacity(1);
        map.put(key, value);
        map
    }

    fn resize(&mut self) {
        let old_capacity = match self.tab.is_empty() {
            true => 0,
            false => self.mask + 1,
        };
        let capacity: u32 = match old_capacity > 0 {
            true => old_capacity << 1,
            false => self.threshold,
        };

        let mut new_tab: Vec<Option<Box<Node<K, V>>>> = Vec::with_capacity(capacity as usize);
        for _ in 0..capacity {
            new_tab.push(None);
        }

        let tab = &mut self.tab;
        for i in 0..old_capacity {
            let mut node = tab[i as usize].take(); // move first node to node_var
            while let Some(mut x) = node {
                let index = x.hash & (capacity - 1); // 计算新桶的索引
                node = x.next; // 更新当前桶中的链表指针

                // 将当前节点插入到新的桶中
                x.next = new_tab[index as usize].take(); // 将原来的节点指向新桶中的节点
                new_tab[index as usize] = Some(x); // 更新新桶
            }
        }

        self.tab = new_tab;
        self.mask = capacity - 1;
        self.threshold = (capacity as f32 * DEFAULT_LOAD_FACTOR) as u32;
    }

    fn hash<T: Hash>(&self, key: &T) -> u64 {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish()
    }
}

impl<K, V> RawTable<K, V> for HashMap<K, V> {
    fn insert(&mut self, key: K, value: V, hash_code: u32) -> (&K, &mut V) {
        todo!()
    }
}

impl<K, V> Map<K, V> for HashMap<K, V>
where
    K: Eq + Hash,
{
    fn size(&self) -> u32 {
        self.size
    }

    fn get(&self, key: &K) -> Option<&V> {
        if self.tab.is_empty() {
            return None
        }
        let hash_code: u32 = self.hash(key) as u32;
        let index: u32 = hash_code & self.mask;

        let tab = &self.tab;
        let mut node = &tab[index as usize]; // 获取桶中的链表头节点
        while let Some(x) = node {
            // if &node.key == key {
            if *key == x.key {
                return Some(&x.value);
            }
            node = &x.next;
        }

        return None;
    }

    fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        if self.tab.is_empty() {
            return None
        }
        let hash_code: u32 = self.hash(key) as u32;
        let index: u32 = hash_code & self.mask;

        let tab = &mut self.tab;
        let mut node = &mut tab[index as usize]; // 获取桶中的链表头节点
        while let Some(x) = node {
            // if &node.key == key {
            if *key == x.key {
                return Some(&mut x.value);
            }
            node = &mut x.next;
        }

        return None;
    }

    fn entry(&mut self, key: K) -> Entry<'_, K, V, HashMap<K, V>> {
        todo!()
    }

    fn put(&mut self, key: K, value: V) -> Option<V> {
        let hash_code: u32 = self.hash(&key) as u32;
        if self.tab.is_empty() {
            self.resize();
        }

        let index: u32 = hash_code & self.mask;
        let tab = &mut self.tab;
        let mut node = &mut tab[index as usize]; // 获取桶中的链表头节点
        while let Some(x) = node {
            if key == x.key {
                //let old:V = x.set_value(value);
                let old: V = std::mem::replace(&mut x.value, value);
                return Some(old);
            }
            node = &mut x.next;
        }

        let mut new_node: Box<Node<K, V>> = Box::new(Node {
            hash: hash_code,
            key: key,
            value: value,
            next: None,
        });

        let node_ref = &mut tab[index as usize];
        new_node.next = node_ref.take(); // 将当前桶的节点链接到新节点
        *node_ref = Some(new_node); // 将新节点赋值给桶
        self.size += 1;

        if self.size > self.threshold {
            self.resize();
        }

        return None;
    }

    fn remove(&mut self, key: &K) -> Option<V> {
        // rust box linked list
        todo!()
    }

    fn foreach<F: FnMut(&K, &mut V)>(&mut self, mut f: F) {
        if self.tab.is_empty() {
            return;
        }
        let tab =  &mut self.tab;
        for i in 0..tab.len() {
            let mut node = &mut tab[i];
            while let Some(x) = node {
                f(&x.key, &mut x.value);
                node = &mut x.next;
            }
        }
    }
}