graph_arena/
lib.rs

1use std::{
2    cmp::Eq,
3    collections::{hash_map::DefaultHasher, HashMap},
4    hash::{Hash, Hasher},
5};
6
7pub struct GraphArena<T>
8where
9    T: Sized + Hash + Eq,
10{
11    data: Vec<T>,
12    mapping: HashMap<u64, usize>,
13}
14
15impl<T> GraphArena<T>
16where
17    T: Sized + Hash + Eq,
18{
19    pub fn new() -> Self {
20        GraphArena {
21            data: Vec::new(),
22            mapping: HashMap::new(),
23        }
24    }
25
26    pub fn get(&self, key: usize) -> &T {
27        &self.data[key]
28    }
29
30    pub fn insert(&mut self, item: T) -> usize {
31        let hashsum = hash(&item);
32
33        if let Some(key) = self.mapping.get(&hashsum) {
34            // perfrom EQ test im data[key] and use new hasher, if it fails
35            // if self.data[*key] != item {
36            //     self.rehash();
37            //     return self.insert(item);
38            // }
39
40            return *key;
41        }
42
43        let index = self.data.len();
44        self.data.push(item);
45        self.mapping.insert(hashsum, index);
46        index
47    }
48}
49
50impl<T> IntoIterator for GraphArena<T>
51where
52    T: Sized + Hash + Eq,
53{
54    type Item = T;
55
56    type IntoIter = std::vec::IntoIter<T>;
57
58    fn into_iter(self) -> Self::IntoIter {
59        self.data.into_iter()
60    }
61}
62
63fn hash<T>(item: &T) -> u64
64where
65    T: Hash,
66{
67    let mut hasher = DefaultHasher::new();
68    item.hash(&mut hasher);
69    hasher.finish()
70}
71
72#[cfg(test)]
73mod test {
74    use super::*;
75
76    #[test]
77    fn test_hash() {
78        let obj = (123, 456);
79        let h1 = hash(&obj);
80        let h2 = hash(&obj);
81        assert_eq!(h1, h2);
82    }
83}
graph_arena/lib.rs

graph_arena/
lib.rs
