vole 0.1.1

A library for solving search problems in permutation groups
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
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

//! A set of integers with O(1) lookup and O(1) iteration through members.

/// A set of integers with O(1) lookup and iteration
#[derive(Debug, Clone)]
pub struct SmallIntSet {
    bit_set: Vec<bool>,
    values: Vec<usize>,
}

impl SmallIntSet {
    /// Create empty set with size `usize`
    pub fn new(size: usize) -> Self {
        Self {
            bit_set: vec![false; size],
            values: vec![],
        }
    }

    /// Check if set contains `i`
    pub fn contains(&self, i: usize) -> bool {
        self.bit_set[i]
    }

    /// Insert `i` into set (does nothing if `i` is already in the set)
    pub fn insert(&mut self, i: usize) {
        if !self.bit_set[i] {
            self.bit_set[i] = true;
            self.values.push(i)
        }
    }

    /// Return an iterator to iterate through the set (in sorted order)
    pub fn sorted_iter(&mut self) -> ::std::slice::Iter<usize> {
        // Sort lazily
        self.values.sort();
        self.values.iter()
    }

    pub fn clear(&mut self) {
        for i in self.values.iter() {
            self.bit_set[*i] = false;
        }
        self.values.clear();
        assert!(self.values.is_empty());
    }

    pub fn is_empty(&self) -> bool {
        self.values.is_empty()
    }
}

#[cfg(test)]
mod tests {
    use super::SmallIntSet;

    #[test]
    fn basic_test() {
        let mut set = SmallIntSet::new(5);
        assert!(!set.contains(3));
        assert!(!set.contains(0));
        set.insert(2);
        assert!(set.contains(2));
        assert!(!set.contains(3));
        assert_eq!(set.sorted_iter().cloned().collect::<Vec<_>>(), vec![2]);
        set.insert(2);
        assert_eq!(set.sorted_iter().cloned().collect::<Vec<_>>(), vec![2]);
        set.insert(0);
        set.insert(3);
        assert_eq!(set.sorted_iter().cloned().collect::<Vec<_>>(), vec![0, 2, 3]);
        set.insert(4);
        assert_eq!(set.sorted_iter().cloned().collect::<Vec<_>>(), vec![0, 2, 3, 4]);
        set.clear();
        assert_eq!(set.sorted_iter().cloned().collect::<Vec<usize>>(), Vec::<usize>::new());
        assert!(!set.contains(3));
        assert!(!set.contains(0));
        assert!(!set.contains(2));
        set.insert(2);
        assert!(set.contains(2));
        assert!(!set.contains(3));
        assert_eq!(set.sorted_iter().cloned().collect::<Vec<_>>(), vec![2]);
    }
}