logic_eval_util/
unique.rs

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

logic_eval_util/
unique.rs
