algs4 0.7.0

Algorithms, 4ed. MOOC in Coursera. in Rust.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

use std::hash::{Hash, Hasher, SipHasher};
use std::borrow::Borrow;

const M: usize = 97;

struct Node<K, V> {
    key: K,
    val: V,
    next: Option<Box<Node<K, V>>>
}

impl<K, V> Node<K, V> {
    pub fn size(&self) -> usize {
        match self.next {
            None => 1,
            Some(ref next) => 1 + next.size()
        }
    }
}

fn delete<K: PartialEq, V>(x: Option<Box<Node<K, V>>> , key: &K) -> Option<Box<Node<K, V>>> {
    if let Some(mut x) = x {
        let next = x.next.take();
        if x.key == *key {
            next            // this will drop x
        } else {
            x.next = delete(next, key);
            Some(x)
        }
    } else {
        None
    }
}

pub struct SeparateChainingHashST<K, V> {
    st: Vec<Option<Box<Node<K, V>>>>
}


impl<K: Hash + PartialEq, V> SeparateChainingHashST<K, V> {
    pub fn new() -> SeparateChainingHashST<K, V> {
        let mut st = Vec::with_capacity(M);
        (0..M).map(|_| st.push(None)).count();
        SeparateChainingHashST {
            st: st
        }
    }

    // FIXME: hash state bug
    fn hash(key: &K) -> usize {
        let mut hasher = SipHasher::new();
        key.hash(&mut hasher);
        hasher.finish() as usize % M
    }

    pub fn get<T: Borrow<K>>(&self, key: T) -> Option<&V> {
        let key = key.borrow();
        let i = Self::hash(key);
        let mut x = self.st[i].as_ref();
        while x.is_some() {
            if *key == x.unwrap().key {
                return Some(&x.unwrap().val)
            }
            x = x.unwrap().next.as_ref();
        }
        None
    }

    pub fn put(&mut self, key: K, val: V) {
        let i = Self::hash(&key);
        {
            let mut x = self.st[i].as_mut();
            while x.is_some() {
                if x.as_ref().map(|x| x.key == key).unwrap_or(false) {
                    x.unwrap().val = val;
                    return;
                } else {
                    x = x.unwrap().next.as_mut();
                }
            }
        }
        let old = self.st[i].take();
        self.st[i] = Some(Box::new(Node { key: key, val: val, next: old }))
    }

    pub fn delete(&mut self, key: &K) {
        let i = Self::hash(&key);
        self.st[i] = delete(self.st[i].take(), key);
    }

    pub fn size(&self) -> usize {
        self.st.iter().filter(|n| n.is_some()).map(|h| h.as_ref().unwrap().size()).sum()
    }
}


#[test]
fn test_separate_chaining_st() {
    let mut m = SeparateChainingHashST::new();
    assert_eq!(m.size(), 0);
    m.put("Name", "Feather");
    m.put("Age", "25");
    m.put("Address", "Beijing");

    assert_eq!(m.size(), 3);
    assert_eq!(m.get("Age"), Some(&"25"));
    assert_eq!(m.get("Gender"), None);

    m.delete(&"Age");
    assert_eq!(m.size(), 2);
    assert_eq!(m.get("Age"), None);
}