dogs 1.3.0

Discrete Optimization Global Search framework. Implements various search algorithms that can be found in combinatorial optimization or heuristic search.
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
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

/**
 implements a sparse set data-structure.
 this structure is efficient to remove all but one values, but is costly in memory.
 if *n* is the number elements and *m* the number of subsets in the set this data-structure has the following complexities:
 - memory: O(n+m)
 - insertion: O(1)
 - remove: O(1)
 - contains: O(1)
 - remove all but one: O(1)
*/
#[derive(Debug)]
pub struct SparseSet {
    /// list of (unsorted) values
    dense: Vec<usize>,
    /// sparse[i] = v <=> dense[v] = i
    sparse: Vec<usize>,
    /// maximum number of elements
    nb_max: usize,
    /// number of elements in the SparseSet
    n: usize,
}


impl SparseSet {
    /**
    creates a new sparse set from its maximum size (nb_max)
    */
    pub fn new(nb_max: usize) -> Self {
        Self {
            dense: vec![usize::MAX;nb_max],
            sparse: vec![usize::MAX;nb_max],
            nb_max,
            n: 0,
        }
    }

    /**
    returns true iff the set is empty
    */
    pub fn is_empty(&self) -> bool { self.n == 0 }

    /**
    returns the number of elements in the set
    */
    pub fn len(&self) -> usize {
        self.n
    }

    /**
    returns the nth element of the set
    */
    pub fn nth(&self, i:usize) -> usize {
        debug_assert!(i<self.n);
        self.dense[i]
    }

    /** true iff e ∈ Set */
    pub fn contains(&self, e:usize) -> bool {
        self.sparse[e] < self.n
    }

    /** inserts e into the set */
    pub fn insert(&mut self, e:usize) {
        debug_assert!(!self.contains(e));
        debug_assert!(e < self.nb_max);
        self.sparse[e] = self.n;
        self.dense[self.n] = e;
        self.n += 1;
    }

    /** removes e from the set */
    pub fn remove(&mut self, e:usize) {
        debug_assert!(self.contains(e));
        // put the last element at the position of e
        self.n -= 1;
        self.dense[self.sparse[e]] = self.dense[self.n];
        self.sparse[self.dense[self.n]] = self.sparse[e];
        self.sparse[e] = usize::MAX;
    }

    /** removes everything except e from the set */
    pub fn remove_all_but_one(&mut self, e:usize) {
        debug_assert!(self.contains(e));
        // put e at the first position
        self.sparse[self.dense[0]] = usize::MAX;
        self.dense[0] = e;
        self.sparse[e] = 0;
        self.n = 1;
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn constructor() {
        let set = SparseSet::new(10);
        assert_eq!(set.len(), 0);
    }

    #[test]
    fn insert() {
        let mut set = SparseSet::new(10);
        set.insert(5);
        set.insert(7);
        set.insert(9);
        assert!(set.contains(5));
        assert!(set.contains(7));
        assert!(set.contains(9));
        assert!(!set.contains(0));
        assert!(!set.contains(1));
        assert!(!set.contains(2));
        assert!(!set.contains(3));
    }

    #[test]
    fn remove() {
        let mut set = SparseSet::new(10);
        set.insert(5);
        set.insert(7);
        assert!(set.contains(5));
        assert!(set.contains(7));
        assert!(!set.contains(3));
        set.remove(5);
        assert!(set.contains(7));
        assert!(!set.contains(5));
        assert!(!set.contains(3));
    }

    #[test]
    fn removeallbutone() {
        let mut set = SparseSet::new(10);
        set.insert(5);
        set.insert(7);
        set.insert(3);
        assert!(set.contains(5));
        assert!(set.contains(7));
        assert!(set.contains(3));
        set.remove_all_but_one(3);
        assert!(!set.contains(5));
        assert!(!set.contains(7));
        assert!(set.contains(3));
    }

}