fst 0.1.9

Use finite state transducers to compactly represents sets or maps of many strings (> 1 billion is possible).
Documentation 
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

pub struct SparseSet {
    dense: Vec<usize>,
    sparse: Vec<usize>,
    size: usize,
}

impl SparseSet {
    pub fn new(size: usize) -> SparseSet {
        SparseSet {
            dense: vec![0; size],
            sparse: vec![0; size],
            size: 0,
        }
    }

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

    pub fn add(&mut self, ip: usize) -> usize {
        let i = self.size;
        self.dense[i] = ip;
        self.sparse[ip] = i;
        self.size += 1;
        i
    }

    pub fn get(&self, i: usize) -> usize {
        self.dense[i]
    }

    pub fn contains(&self, ip: usize) -> bool {
        let i = self.sparse[ip];
        i < self.size && self.dense[i] == ip
    }

    pub fn clear(&mut self) {
        self.size = 0;
    }
}