general_sam/
table.rs

1//! Transition table backends.
2
3use std::collections::{BTreeMap, HashMap};
4use std::iter::repeat_n;
5use std::marker::PhantomData;
6
7use crate::GeneralSamNodeID;
8
9#[derive(Clone, Debug)]
10pub struct WithKeyDerefedIter<
11    'a,
12    KeyType: 'a + Clone,
13    IterType: Iterator<Item = (&'a KeyType, &'a GeneralSamNodeID)>,
14> {
15    inner: IterType,
16}
17
18impl<'a, KeyType: 'a + Clone, IterType: Iterator<Item = (&'a KeyType, &'a GeneralSamNodeID)>>
19    Iterator for WithKeyDerefedIter<'a, KeyType, IterType>
20{
21    type Item = (KeyType, &'a GeneralSamNodeID);
22
23    fn next(&mut self) -> Option<Self::Item> {
24        self.inner.next().map(|x| (x.0.clone(), x.1))
25    }
26}
27
28#[derive(Clone, Debug)]
29pub struct TransitionIter<
30    'a,
31    KeyType: 'a,
32    IterType: Iterator<Item = (KeyType, &'a GeneralSamNodeID)>,
33> {
34    inner: IterType,
35}
36
37impl<'a, KeyType: 'a, IterType: Iterator<Item = (KeyType, &'a GeneralSamNodeID)>> Iterator
38    for TransitionIter<'a, KeyType, IterType>
39{
40    type Item = &'a GeneralSamNodeID;
41
42    fn next(&mut self) -> Option<Self::Item> {
43        self.inner.next().map(|x| x.1)
44    }
45}
46
47pub trait TransitionTable {
48    type KeyType: Clone;
49    type IterType<'a>: Iterator<Item = (Self::KeyType, &'a GeneralSamNodeID)>
50    where
51        Self: 'a,
52        Self::KeyType: 'a;
53
54    fn from_kv_iter<'b, Iter: IntoIterator<Item = (Self::KeyType, &'b GeneralSamNodeID)>>(
55        iter: Iter,
56    ) -> Self
57    where
58        Self::KeyType: 'b;
59    fn get(&self, key: &Self::KeyType) -> Option<&GeneralSamNodeID>;
60    fn get_mut(&mut self, key: &Self::KeyType) -> Option<&mut GeneralSamNodeID>;
61    fn iter(&self) -> Self::IterType<'_>;
62
63    fn contains_key(&self, key: &Self::KeyType) -> bool {
64        self.get(key).is_some()
65    }
66
67    fn transitions(&self) -> TransitionIter<'_, Self::KeyType, Self::IterType<'_>> {
68        TransitionIter { inner: self.iter() }
69    }
70}
71
72pub trait ConstructiveTransitionTable: TransitionTable + Clone + Default {
73    fn insert(&mut self, key: Self::KeyType, trans: GeneralSamNodeID);
74
75    fn from_kv_iter<'b, Iter: IntoIterator<Item = (Self::KeyType, &'b GeneralSamNodeID)>>(
76        iter: Iter,
77    ) -> Self
78    where
79        Self::KeyType: 'b,
80    {
81        let mut res = Self::default();
82        for (k, v) in iter {
83            res.insert(k, *v);
84        }
85        res
86    }
87}
88
89pub type BTreeTransTable<KeyType> = BTreeMap<KeyType, GeneralSamNodeID>;
90
91impl<KeyType: Ord + Clone> ConstructiveTransitionTable for BTreeTransTable<KeyType> {
92    fn insert(&mut self, key: KeyType, trans: GeneralSamNodeID) {
93        BTreeMap::insert(self, key, trans);
94    }
95}
96
97impl<KeyType: Clone + Ord> TransitionTable for BTreeTransTable<KeyType> {
98    type KeyType = KeyType;
99    type IterType<'a>
100        = WithKeyDerefedIter<
101        'a,
102        KeyType,
103        std::collections::btree_map::Iter<'a, KeyType, GeneralSamNodeID>,
104    >
105    where
106        Self: 'a,
107        Self::KeyType: 'a;
108
109    fn get(&self, key: &KeyType) -> Option<&GeneralSamNodeID> {
110        BTreeMap::get(self, key)
111    }
112
113    fn get_mut(&mut self, key: &KeyType) -> Option<&mut GeneralSamNodeID> {
114        BTreeMap::get_mut(self, key)
115    }
116
117    fn iter(&self) -> Self::IterType<'_> {
118        WithKeyDerefedIter {
119            inner: BTreeMap::iter(self),
120        }
121    }
122
123    fn from_kv_iter<'b, Iter: IntoIterator<Item = (KeyType, &'b GeneralSamNodeID)>>(
124        iter: Iter,
125    ) -> Self
126    where
127        Self::KeyType: 'b,
128    {
129        <Self as ConstructiveTransitionTable>::from_kv_iter(iter)
130    }
131}
132
133pub type HashTransTable<KeyType> = HashMap<KeyType, GeneralSamNodeID>;
134
135impl<KeyType: std::hash::Hash + Eq + Clone> ConstructiveTransitionTable
136    for HashTransTable<KeyType>
137{
138    fn insert(&mut self, key: KeyType, trans: GeneralSamNodeID) {
139        HashMap::insert(self, key, trans);
140    }
141}
142
143impl<KeyType: std::hash::Hash + Eq + Clone> TransitionTable for HashTransTable<KeyType> {
144    type KeyType = KeyType;
145    type IterType<'a>
146        = WithKeyDerefedIter<
147        'a,
148        KeyType,
149        std::collections::hash_map::Iter<'a, KeyType, GeneralSamNodeID>,
150    >
151    where
152        Self: 'a,
153        Self::KeyType: 'a;
154
155    fn get(&self, key: &KeyType) -> Option<&GeneralSamNodeID> {
156        HashMap::get(self, key)
157    }
158
159    fn get_mut(&mut self, key: &KeyType) -> Option<&mut GeneralSamNodeID> {
160        HashMap::get_mut(self, key)
161    }
162
163    fn iter(&self) -> Self::IterType<'_> {
164        WithKeyDerefedIter {
165            inner: HashMap::iter(self),
166        }
167    }
168
169    fn from_kv_iter<'b, Iter: IntoIterator<Item = (KeyType, &'b GeneralSamNodeID)>>(
170        iter: Iter,
171    ) -> Self
172    where
173        Self::KeyType: 'b,
174    {
175        <Self as ConstructiveTransitionTable>::from_kv_iter(iter)
176    }
177}
178
179fn bisect_unstable<K: Ord, V, C: AsRef<[(K, V)]>>(container: C, key: &K) -> Option<usize> {
180    let (mut lo, mut hi) = (0, container.as_ref().len());
181    while hi - lo > 0 {
182        let mid = (lo + hi) / 2;
183        match container.as_ref()[mid].0.cmp(key) {
184            std::cmp::Ordering::Equal => {
185                return Some(mid);
186            }
187            std::cmp::Ordering::Less => {
188                lo = mid + 1;
189            }
190            std::cmp::Ordering::Greater => {
191                hi = mid;
192            }
193        }
194    }
195
196    if lo < hi && container.as_ref()[lo].0 == *key {
197        Some(lo)
198    } else {
199        None
200    }
201}
202
203#[derive(Clone, Debug)]
204pub struct BisectTable<
205    K: Clone + Ord,
206    C: AsRef<[(K, GeneralSamNodeID)]>
207        + AsMut<[(K, GeneralSamNodeID)]>
208        + FromIterator<(K, GeneralSamNodeID)>,
209> {
210    inner: C,
211    phantom: PhantomData<K>,
212}
213
214#[derive(Clone, Debug)]
215pub struct BisectTableIter<'s, K: Clone + Ord> {
216    inner: core::slice::Iter<'s, (K, GeneralSamNodeID)>,
217}
218
219impl<'s, K: Clone + Ord> Iterator for BisectTableIter<'s, K> {
220    type Item = (K, &'s GeneralSamNodeID);
221
222    fn next(&mut self) -> Option<Self::Item> {
223        self.inner.next().map(|x| (x.0.clone(), &x.1))
224    }
225}
226
227impl<
228    K: Clone + Ord,
229    C: AsRef<[(K, GeneralSamNodeID)]>
230        + AsMut<[(K, GeneralSamNodeID)]>
231        + FromIterator<(K, GeneralSamNodeID)>,
232> TransitionTable for BisectTable<K, C>
233{
234    type KeyType = K;
235    type IterType<'a>
236        = BisectTableIter<'a, K>
237    where
238        Self: 'a,
239        Self::KeyType: 'a;
240
241    fn get(&self, key: &Self::KeyType) -> Option<&GeneralSamNodeID> {
242        bisect_unstable(&self.inner, key).map(|i| &self.inner.as_ref()[i].1)
243    }
244
245    fn get_mut(&mut self, key: &K) -> Option<&mut GeneralSamNodeID> {
246        bisect_unstable(&self.inner, key).map(|i| &mut self.inner.as_mut()[i].1)
247    }
248
249    fn iter(&self) -> Self::IterType<'_> {
250        BisectTableIter {
251            inner: self.inner.as_ref().iter(),
252        }
253    }
254
255    fn from_kv_iter<'b, Iter: IntoIterator<Item = (K, &'b GeneralSamNodeID)>>(iter: Iter) -> Self
256    where
257        Self::KeyType: 'b,
258    {
259        let mut inner: Box<[(K, GeneralSamNodeID)]> =
260            iter.into_iter().map(|(u, v)| (u.clone(), *v)).collect();
261        inner.sort_unstable_by(|a, b| a.0.cmp(&b.0));
262        Self {
263            inner: inner.iter().map(|x| (x.0.clone(), x.1)).collect(),
264            phantom: Default::default(),
265        }
266    }
267}
268
269pub type VecBisectTable<K> = BisectTable<K, Vec<(K, GeneralSamNodeID)>>;
270pub type BoxBisectTable<K> = BisectTable<K, Box<[(K, GeneralSamNodeID)]>>;
271
272pub trait SmallAlphabet: Copy + Ord + Into<usize> {
273    const SIZE_LOG_2: usize;
274    const SIZE: usize = 1 << Self::SIZE_LOG_2;
275
276    fn from_usize(val: usize) -> Self;
277}
278
279impl SmallAlphabet for bool {
280    const SIZE_LOG_2: usize = 1;
281
282    fn from_usize(val: usize) -> Self {
283        (val & 1) > 0
284    }
285}
286
287impl SmallAlphabet for u8 {
288    const SIZE_LOG_2: usize = 8;
289
290    fn from_usize(val: usize) -> Self {
291        (val & (Self::SIZE - 1)) as Self
292    }
293}
294
295#[derive(Clone, Debug)]
296pub struct WholeAlphabetTable<
297    K: SmallAlphabet,
298    C: AsRef<[Option<GeneralSamNodeID>]>
299        + AsMut<[Option<GeneralSamNodeID>]>
300        + FromIterator<Option<GeneralSamNodeID>>
301        + Clone,
302> {
303    inner: C,
304    phantom: PhantomData<K>,
305}
306
307#[derive(Clone, Debug)]
308pub struct WholeAlphabetTableIter<'s, K: SmallAlphabet> {
309    inner: std::iter::Enumerate<core::slice::Iter<'s, Option<GeneralSamNodeID>>>,
310    phantom: PhantomData<K>,
311}
312
313impl<'s, K: SmallAlphabet> Iterator for WholeAlphabetTableIter<'s, K> {
314    type Item = (K, &'s GeneralSamNodeID);
315
316    fn next(&mut self) -> Option<Self::Item> {
317        for (k, v) in self.inner.by_ref() {
318            if let Some(v) = v {
319                return Some((K::from_usize(k), v));
320            }
321        }
322        None
323    }
324}
325
326impl<
327    K: SmallAlphabet,
328    C: AsRef<[Option<GeneralSamNodeID>]>
329        + AsMut<[Option<GeneralSamNodeID>]>
330        + FromIterator<Option<GeneralSamNodeID>>
331        + Clone,
332> Default for WholeAlphabetTable<K, C>
333{
334    fn default() -> Self {
335        Self {
336            inner: C::from_iter(repeat_n(None, K::SIZE)),
337            phantom: Default::default(),
338        }
339    }
340}
341
342impl<
343    K: SmallAlphabet,
344    C: AsRef<[Option<GeneralSamNodeID>]>
345        + AsMut<[Option<GeneralSamNodeID>]>
346        + FromIterator<Option<GeneralSamNodeID>>
347        + Clone,
348> ConstructiveTransitionTable for WholeAlphabetTable<K, C>
349{
350    fn insert(&mut self, key: Self::KeyType, trans: GeneralSamNodeID) {
351        let k: usize = key.into();
352        self.inner.as_mut()[k] = Some(trans)
353    }
354}
355
356impl<
357    K: SmallAlphabet,
358    C: AsRef<[Option<GeneralSamNodeID>]>
359        + AsMut<[Option<GeneralSamNodeID>]>
360        + FromIterator<Option<GeneralSamNodeID>>
361        + Clone,
362> TransitionTable for WholeAlphabetTable<K, C>
363{
364    type KeyType = K;
365    type IterType<'a>
366        = WholeAlphabetTableIter<'a, K>
367    where
368        Self: 'a,
369        Self::KeyType: 'a;
370
371    fn get(&self, key: &Self::KeyType) -> Option<&GeneralSamNodeID> {
372        let k: usize = (*key).into();
373        self.inner.as_ref().get(k).and_then(|x| x.as_ref())
374    }
375
376    fn get_mut(&mut self, key: &Self::KeyType) -> Option<&mut GeneralSamNodeID> {
377        let k: usize = (*key).into();
378        self.inner.as_mut().get_mut(k).and_then(|x| x.as_mut())
379    }
380
381    fn iter(&self) -> Self::IterType<'_> {
382        WholeAlphabetTableIter {
383            inner: self.inner.as_ref().iter().enumerate(),
384            phantom: Default::default(),
385        }
386    }
387
388    fn from_kv_iter<'b, Iter: IntoIterator<Item = (Self::KeyType, &'b GeneralSamNodeID)>>(
389        iter: Iter,
390    ) -> Self
391    where
392        Self::KeyType: 'b,
393    {
394        <Self as ConstructiveTransitionTable>::from_kv_iter(iter)
395    }
396}
general_sam/table.rs

general_sam/
table.rs
