general_sam/
table.rs

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

general_sam/
table.rs
