logic_eval_util/
unique.rs

1use crate::Map;
2use smallvec::{smallvec, SmallVec};
3use std::{
4    cell::Cell,
5    collections::hash_map::DefaultHasher,
6    hash::{Hash, Hasher},
7    iter, mem, ops,
8};
9
10/// - Each value is unique in this container. if multiple indices have to refer to the same value,
11///   then only one index points to the real value and the others point to indirect values, which
12///   are just jump indices to the real value.
13/// - You can get a value via its index.
14#[derive(Debug, Clone)]
15pub struct UniqueContainer<T> {
16    values: Values<T>,
17
18    /// Hash of a `T` -> Indices to `values`, but only for [`Value::Data`].
19    map: Map<u64, SmallVec<[usize; 1]>>,
20}
21
22impl<T> UniqueContainer<T> {
23    pub fn new() -> Self {
24        Self {
25            values: Values::new(),
26            map: Map::default(),
27        }
28    }
29
30    pub fn len(&self) -> usize {
31        self.values.len()
32    }
33
34    pub fn is_empty(&self) -> bool {
35        self.len() == 0
36    }
37
38    pub fn get(&self, index: usize) -> Option<&T> {
39        self.values.get(index)
40    }
41
42    pub fn iter(&self) -> PairIter<'_, T> {
43        self.values.iter()
44    }
45
46    pub fn values(&self) -> ValueIter<'_, T> {
47        self.values.values()
48    }
49
50    /// All indices will be invalidated.
51    pub fn clear(&mut self) {
52        self.values.clear();
53        self.map.clear();
54    }
55}
56
57impl<T> UniqueContainer<T>
58where
59    T: Hash + Eq,
60{
61    /// Shortens the container to the given length.
62    ///
63    /// All indices beyond the length will be invalidated.
64    pub fn truncate(&mut self, len: usize) {
65        for index in len..self.values.len() {
66            let hash = Self::hash(&self.values[index]);
67            Self::remove_mapping(&mut self.map, hash, index);
68        }
69        self.values.truncate(len);
70    }
71
72    /// Inserts the given value in the container.
73    ///
74    /// If the same value was found by [`PartialEq`], then the old value is replaced with the given
75    /// new value.
76    pub fn insert(&mut self, value: T) -> usize {
77        let hash = Self::hash(&value);
78        if let Some(index) = self._find(hash, &value) {
79            self.values.replace(index, Value::Data(value));
80            return index;
81        }
82
83        let index = self.values.len();
84
85        Self::append_mapping(&mut self.map, hash, index);
86        self.values.push(Value::Data(value));
87
88        index
89    }
90
91    pub fn next_index<Q>(&mut self, value: &Q) -> usize
92    where
93        Q: Hash + PartialEq<T> + ?Sized,
94    {
95        self.find(value).unwrap_or(self.values.len())
96    }
97
98    pub fn replace<Q>(&mut self, old: &Q, new: T) -> bool
99    where
100        Q: Hash + PartialEq<T> + ?Sized,
101    {
102        if let Some(index) = self.find(old) {
103            self.replace_at(index, new);
104            true
105        } else {
106            false
107        }
108    }
109
110    /// Replaces a value at the given index with the given value.
111    ///
112    /// Note that some other indices that point to the old value will point to the given new value
113    /// after replacement.
114    ///
115    /// You may keep in mind that you should get an index using [`Self::find`]. Because what you
116    /// want would be to replace [`Value::Data`] which can be obtained by the find function.
117    /// Otherwise, you may pick up an index to a [`Value::Indirect`] which ends up a wrong result.
118    fn replace_at(&mut self, index: usize, value: T) {
119        let hash = Self::hash(&value);
120
121        if let Some(exist_idx) = self._find(hash, &value) {
122            replace(self, index, Value::Indirect(Cell::new(exist_idx)));
123            replace(self, exist_idx, Value::Data(value));
124        } else {
125            replace(self, index, Value::Data(value));
126        }
127
128        // === Internal helper functions ===
129
130        fn replace<T: Hash + Eq>(this: &mut UniqueContainer<T>, index: usize, value: Value<T>) {
131            if let Value::Data(new) = &value {
132                let hash = UniqueContainer::<T>::hash(new);
133                UniqueContainer::<T>::append_mapping(&mut this.map, hash, index);
134            }
135
136            let old = this.values.replace(index, value);
137
138            if let Value::Data(old) = old {
139                let hash = UniqueContainer::<T>::hash(&old);
140                UniqueContainer::<T>::remove_mapping(&mut this.map, hash, index);
141            }
142        }
143    }
144
145    pub fn find<Q>(&self, value: &Q) -> Option<usize>
146    where
147        Q: Hash + PartialEq<T> + ?Sized,
148    {
149        let hash = Self::hash(value);
150        self._find(hash, value)
151    }
152
153    /// Returns an index to the given value in the container.
154    ///
155    /// The returned index points to a real data, which is [`Value::Data`] in other words.
156    fn _find<Q>(&self, hash: u64, value: &Q) -> Option<usize>
157    where
158        Q: PartialEq<T> + ?Sized,
159    {
160        self.map.get(&hash).and_then(|indices| {
161            indices
162                .iter()
163                .find(|index| value == &self.values[**index])
164                .cloned()
165        })
166    }
167
168    fn hash<Q>(value: &Q) -> u64
169    where
170        Q: Hash + PartialEq<T> + ?Sized,
171    {
172        let mut hasher = DefaultHasher::new();
173        value.hash(&mut hasher);
174        hasher.finish()
175    }
176
177    fn append_mapping(map: &mut Map<u64, SmallVec<[usize; 1]>>, hash: u64, index: usize) {
178        map.entry(hash)
179            .and_modify(|indices| indices.push(index))
180            .or_insert(smallvec![index]);
181    }
182
183    fn remove_mapping(map: &mut Map<u64, SmallVec<[usize; 1]>>, hash: u64, index: usize) {
184        let Some(indices) = map.get_mut(&hash) else {
185            return;
186        };
187
188        let Some((i, _)) = indices.iter().enumerate().find(|(_, ii)| **ii == index) else {
189            return;
190        };
191
192        indices.swap_remove(i);
193
194        if indices.is_empty() {
195            map.remove(&hash);
196        }
197    }
198}
199
200impl<T> ops::Index<usize> for UniqueContainer<T> {
201    type Output = T;
202
203    fn index(&self, index: usize) -> &Self::Output {
204        &self.values[index]
205    }
206}
207
208impl<T> Default for UniqueContainer<T> {
209    fn default() -> Self {
210        Self::new()
211    }
212}
213
214#[derive(Debug, Clone)]
215struct Values<T>(Vec<Value<T>>);
216
217impl<T> Values<T> {
218    const fn new() -> Self {
219        Self(Vec::new())
220    }
221
222    fn len(&self) -> usize {
223        self.0.len()
224    }
225
226    fn iter(&self) -> PairIter<'_, T> {
227        PairIter::new(self)
228    }
229
230    fn values(&self) -> ValueIter<'_, T> {
231        ValueIter::new(self)
232    }
233
234    fn get(&self, index: usize) -> Option<&T> {
235        self.get_with_opt(index).map(|(_idx, ty)| ty)
236    }
237
238    fn get_with_opt(&self, index: usize) -> Option<(usize, &T)> {
239        match self.0.get(index)? {
240            Value::Indirect(v) => {
241                let (w, ty) = self.get_with_opt(v.get())?;
242                v.set(w);
243                Some((w, ty))
244            }
245            Value::Data(ty) => Some((index, ty)),
246        }
247    }
248
249    fn replace(&mut self, index: usize, value: Value<T>) -> Value<T> {
250        mem::replace(&mut self.0[index], value)
251    }
252
253    fn push(&mut self, value: Value<T>) {
254        self.0.push(value);
255    }
256
257    fn clear(&mut self) {
258        self.0.clear();
259    }
260
261    fn truncate(&mut self, len: usize) {
262        self.0.truncate(len);
263    }
264}
265
266impl<T> ops::Index<usize> for Values<T> {
267    type Output = T;
268
269    fn index(&self, index: usize) -> &Self::Output {
270        self.get(index).expect("index is out of bounds")
271    }
272}
273
274#[derive(Debug, Clone)]
275enum Value<T> {
276    Indirect(Cell<usize>),
277    Data(T),
278}
279
280/// The iterator skips indirect values.
281#[derive(Clone)]
282pub struct PairIter<'a, T> {
283    values: &'a [Value<T>],
284    cur: usize,
285    remain: usize,
286}
287
288impl<'a, T> PairIter<'a, T> {
289    fn new(values: &'a Values<T>) -> Self {
290        Self {
291            values: values.0.as_slice(),
292            cur: 0,
293            remain: values
294                .0
295                .iter()
296                .filter(|value| matches!(value, Value::Data(_)))
297                .count(),
298        }
299    }
300
301    const fn len(&self) -> usize {
302        self.remain
303    }
304}
305
306impl<'a, T> Iterator for PairIter<'a, T> {
307    type Item = (usize, &'a T);
308
309    fn next(&mut self) -> Option<Self::Item> {
310        if self.remain == 0 {
311            return None;
312        }
313
314        let value = loop {
315            let value = &self.values[self.cur];
316            self.cur += 1;
317            match value {
318                Value::Indirect(_) => continue,
319                Value::Data(value) => break value,
320            }
321        };
322        self.remain -= 1;
323        Some((self.cur - 1, value))
324    }
325
326    fn size_hint(&self) -> (usize, Option<usize>) {
327        let len = <Self>::len(self);
328        (len, Some(len))
329    }
330}
331
332impl<T> ExactSizeIterator for PairIter<'_, T> {
333    fn len(&self) -> usize {
334        <Self>::len(self)
335    }
336}
337
338impl<T> iter::FusedIterator for PairIter<'_, T> {}
339
340/// The iterator skips indirect values.
341#[derive(Clone)]
342pub struct ValueIter<'a, T> {
343    rest: &'a [Value<T>],
344    remain: usize,
345}
346
347impl<'a, T> ValueIter<'a, T> {
348    fn new(values: &'a Values<T>) -> Self {
349        Self {
350            rest: values.0.as_slice(),
351            remain: values
352                .0
353                .iter()
354                .filter(|value| matches!(value, Value::Data(_)))
355                .count(),
356        }
357    }
358
359    const fn len(&self) -> usize {
360        self.remain
361    }
362}
363
364impl<'a, T> Iterator for ValueIter<'a, T> {
365    type Item = &'a T;
366
367    fn next(&mut self) -> Option<Self::Item> {
368        let value = loop {
369            let (head, rest) = self.rest.split_first()?;
370            self.rest = rest;
371            match head {
372                Value::Indirect(_) => continue,
373                Value::Data(value) => break value,
374            }
375        };
376        self.remain -= 1;
377        Some(value)
378    }
379
380    fn size_hint(&self) -> (usize, Option<usize>) {
381        let len = <Self>::len(self);
382        (len, Some(len))
383    }
384}
385
386impl<T> ExactSizeIterator for ValueIter<'_, T> {
387    fn len(&self) -> usize {
388        <Self>::len(self)
389    }
390}
391
392impl<T> iter::FusedIterator for ValueIter<'_, T> {}
logic_eval_util/unique.rs

logic_eval_util/
unique.rs
