timsrust_utils/
hash_sets.rs

1type FiniteSetIndex = u32;
2
3#[derive(Debug)]
4pub struct FiniteSet {
5    active: Vec<FiniteSetIndex>,
6    pos: Vec<FiniteSetIndex>,
7    capacity: FiniteSetIndex,
8}
9
10impl FiniteSet {
11    pub fn with_capacity(n: FiniteSetIndex) -> Self {
12        Self {
13            active: Vec::with_capacity(n as usize),
14            pos: vec![0; n as usize],
15            capacity: n,
16        }
17    }
18
19    pub fn is_valid(&self, i: FiniteSetIndex) -> bool {
20        i < self.capacity
21    }
22
23    pub fn insert(&mut self, i: FiniteSetIndex) -> bool {
24        if !self.contains(i) && self.is_valid(i) {
25            self.pos[i as usize] = self.active.len() as FiniteSetIndex;
26            self.active.push(i);
27            true
28        } else {
29            false
30        }
31    }
32
33    pub fn remove(&mut self, i: FiniteSetIndex) -> bool {
34        if self.contains(i) {
35            let last = self.active.pop().expect("Active set is empty");
36            if last != i {
37                let p = self.pos[i as usize];
38                self.active[p as usize] = last;
39                self.pos[last as usize] = p;
40            }
41            true
42        } else {
43            false
44        }
45    }
46
47    pub fn contains(&self, i: FiniteSetIndex) -> bool {
48        match self.is_valid(i) {
49            true => {
50                let p = self.pos[i as usize];
51                (p as usize) < self.active.len()
52                    && (self.active[p as usize] == i)
53            },
54            false => false,
55        }
56    }
57
58    pub fn len(&self) -> usize {
59        self.active.len()
60    }
61
62    pub fn is_empty(&self) -> bool {
63        self.active.is_empty()
64    }
65
66    pub fn iter(&self) -> impl Iterator<Item = &FiniteSetIndex> + '_ {
67        self.active.iter()
68    }
69
70    pub fn clear(&mut self) {
71        self.active.clear();
72    }
73}
74
75#[derive(Debug)]
76pub struct FiniteHashMap<V> {
77    keys: FiniteSet,
78    values: Vec<Option<V>>,
79}
80
81impl<V> FiniteHashMap<V> {
82    pub fn capacity(&self) -> FiniteSetIndex {
83        self.keys.capacity
84    }
85
86    pub fn with_capacity(n: FiniteSetIndex) -> Self {
87        let mut values = Vec::with_capacity(n as usize);
88        values.resize_with(n as usize, || None);
89        Self {
90            keys: FiniteSet::with_capacity(n),
91            values,
92        }
93    }
94
95    pub fn insert(&mut self, i: FiniteSetIndex, v: V) -> bool {
96        if self.keys.insert(i) {
97            self.values[i as usize] = Some(v);
98            true
99        } else {
100            false
101        }
102    }
103
104    pub fn remove(&mut self, i: FiniteSetIndex) -> bool {
105        if self.keys.remove(i) {
106            self.values[i as usize] = None;
107            true
108        } else {
109            false
110        }
111    }
112
113    pub fn get(&self, i: FiniteSetIndex) -> Option<&V> {
114        self.values[i as usize].as_ref()
115    }
116
117    pub fn contains_key(&self, i: FiniteSetIndex) -> bool {
118        self.keys.contains(i)
119    }
120
121    pub fn len(&self) -> usize {
122        self.keys.len()
123    }
124
125    pub fn is_empty(&self) -> bool {
126        self.keys.is_empty()
127    }
128
129    pub fn iter_unstable(
130        &self,
131    ) -> impl Iterator<Item = (FiniteSetIndex, &V)> + '_ {
132        self.keys
133            .iter()
134            .filter_map(move |&i| self.get(i).map(|v| (i, v)))
135    }
136
137    pub fn iter_sorted(
138        &self,
139    ) -> impl Iterator<Item = (FiniteSetIndex, &V)> + '_ {
140        let mut keys = self.keys.active.clone();
141        keys.sort_unstable();
142        keys.into_iter()
143            .filter_map(move |i| self.get(i).map(|v| (i, v)))
144    }
145
146    pub fn clear(&mut self) {
147        for key in self.keys.iter() {
148            self.values[*key as usize] = None;
149        }
150        self.keys.clear();
151    }
152}
153
154#[derive(Debug, Default)]
155pub struct SemiDenseMap<K, V>
156where
157    K: Copy + Default + Eq + TryInto<usize> + TryFrom<usize>,
158{
159    positions: Vec<K>,
160    active: Vec<K>,
161    values: Vec<V>,
162}
163
164impl<K, V> SemiDenseMap<K, V>
165where
166    K: Copy + Default + Eq + TryInto<usize> + TryFrom<usize>,
167{
168    pub fn new() -> Self {
169        Self {
170            positions: Vec::new(),
171            active: Vec::new(),
172            values: Vec::new(),
173        }
174    }
175
176    pub fn with_capacity(n: usize) -> Self {
177        Self {
178            positions: vec![K::default(); n],
179            active: Vec::new(),
180            values: Vec::new(),
181        }
182    }
183
184    pub fn with_capacity_and_density(n: usize, d: usize) -> Self {
185        Self {
186            positions: vec![K::default(); n],
187            active: Vec::with_capacity(d),
188            values: Vec::with_capacity(d),
189        }
190    }
191
192    fn get_position(&self, k: K) -> Option<usize> {
193        let ku = k.try_into().ok()?;
194        let position = *self.positions.get(ku)?;
195        let p = position.try_into().ok()?;
196        Some(p)
197    }
198
199    fn position_equals(&self, k: K, position: usize) -> bool {
200        match self.active.get(position) {
201            Some(&key) => key == k,
202            None => false,
203        }
204    }
205
206    pub fn contains(&self, k: K) -> bool {
207        match self.get_position(k) {
208            Some(position) => self.position_equals(k, position),
209            None => false,
210        }
211    }
212
213    pub fn remove(&mut self, k: K) -> Option<V> {
214        let position = self.get_position(k)?;
215        if self.position_equals(k, position) {
216            let last_key = self.active.pop().expect("Active set is empty");
217            if last_key != k {
218                let last_value = self.values.pop()?;
219                self.active[position] = last_key;
220                let removed_value =
221                    std::mem::replace(&mut self.values[position], last_value);
222                let lku = last_key.try_into().ok()?;
223                self.positions[lku] = position.try_into().ok()?;
224                Some(removed_value)
225            } else {
226                self.values.pop()
227            }
228        } else {
229            None
230        }
231    }
232
233    pub fn get(&self, k: K) -> Option<&V> {
234        let position = self.get_position(k)?;
235        if self.position_equals(k, position) {
236            Some(&self.values[position])
237        } else {
238            None
239        }
240    }
241
242    pub fn get_mut(&mut self, k: K) -> Option<&mut V> {
243        let position = self.get_position(k)?;
244        if self.position_equals(k, position) {
245            Some(&mut self.values[position])
246        } else {
247            None
248        }
249    }
250
251    fn get_position_or_extend(
252        &mut self,
253        k: K,
254    ) -> Result<usize, SemiDenseMapError> {
255        let ku = k
256            .try_into()
257            .map_err(|_| SemiDenseMapError::CapacityExceeded)?;
258        if self.positions.len() <= ku {
259            let new_k = K::try_from(self.active.len())
260                .map_err(|_| SemiDenseMapError::CapacityExceeded)?;
261            // TODO be smarter about resizing, e.g. double the size instead of just extending to ku
262            self.positions.resize(ku + 1, new_k);
263        }
264        let position = self.positions[ku];
265        let p = position
266            .try_into()
267            .map_err(|_| SemiDenseMapError::CapacityExceeded)?;
268        Ok(p)
269    }
270
271    fn insert_at_position(
272        &mut self,
273        k: K,
274        v: V,
275        position: usize,
276    ) -> Result<(), SemiDenseMapError> {
277        if self.position_equals(k, position) {
278            Err(SemiDenseMapError::AlreadyExists)
279        } else {
280            if self.active.len() != position {
281                let ku = k
282                    .try_into()
283                    .map_err(|_| SemiDenseMapError::CapacityExceeded)?;
284                self.positions[ku] = K::try_from(self.active.len())
285                    .map_err(|_| SemiDenseMapError::CapacityExceeded)?;
286            }
287            self.values.push(v);
288            self.active.push(k);
289            Ok(())
290        }
291    }
292
293    pub fn insert(&mut self, k: K, v: V) -> Result<(), SemiDenseMapError> {
294        let position = self.get_position_or_extend(k)?;
295        self.insert_at_position(k, v, position)
296    }
297
298    pub fn get_mut_or_default(
299        &mut self,
300        k: K,
301    ) -> Result<&mut V, SemiDenseMapError>
302    where
303        V: Default,
304    {
305        let position = self.get_position_or_extend(k)?;
306        match self.insert_at_position(k, V::default(), position) {
307            Err(SemiDenseMapError::CapacityExceeded) => {
308                Err(SemiDenseMapError::CapacityExceeded)
309            },
310            _ => {
311                let final_position = self
312                    .get_position(k)
313                    .ok_or(SemiDenseMapError::CapacityExceeded)?;
314                Ok(&mut self.values[final_position])
315            },
316        }
317    }
318
319    pub fn len(&self) -> usize {
320        self.active.len()
321    }
322
323    pub fn is_empty(&self) -> bool {
324        self.active.is_empty()
325    }
326
327    pub fn clear(&mut self) {
328        self.active.clear();
329        self.values.clear();
330    }
331
332    pub fn iter_keys_unstable(&self) -> impl Iterator<Item = &K> + '_ {
333        self.active.iter()
334    }
335
336    pub fn iter_values_unstable(&self) -> impl Iterator<Item = &V> + '_ {
337        self.values.iter()
338    }
339
340    pub fn iter_unstable(&self) -> impl Iterator<Item = (&K, &V)> + '_ {
341        self.active.iter().zip(self.values.iter())
342    }
343
344    pub fn iter_sorted(&self) -> impl Iterator<Item = (&K, &V)> + '_
345    where
346        K: Ord,
347    {
348        let mut indices = (0..self.active.len()).collect::<Vec<_>>();
349        indices.sort_unstable_by_key(|&k| self.active[k]);
350        indices
351            .into_iter()
352            .map(move |k| (&self.active[k], &self.values[k]))
353    }
354
355    pub fn iter_mut_values_unstable(
356        &mut self,
357    ) -> impl Iterator<Item = &mut V> + '_ {
358        self.values.iter_mut()
359    }
360
361    pub fn iter_mut_unstable(
362        &mut self,
363    ) -> impl Iterator<Item = (&mut K, &mut V)> + '_ {
364        self.active.iter_mut().zip(self.values.iter_mut())
365    }
366}
367
368#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
369pub enum SemiDenseMapError {
370    CapacityExceeded,
371    AlreadyExists,
372}
373
374impl std::fmt::Display for SemiDenseMapError {
375    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
376        match self {
377            SemiDenseMapError::CapacityExceeded => {
378                write!(f, "Semi-dense map capacity exceeded")
379            },
380            SemiDenseMapError::AlreadyExists => {
381                write!(f, "Key already exists in semi-dense map")
382            },
383        }
384    }
385}
386
387impl std::error::Error for SemiDenseMapError {}
timsrust_utils/hash_sets.rs

timsrust_utils/
hash_sets.rs
