general_sam/
table.rs

1//! Transition table backends.
2
3use std::{
4    collections::{BTreeMap, HashMap},
5    iter::repeat,
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> = WithKeyDerefedIter<'a, KeyType, std::collections::btree_map::Iter<'a, KeyType, GeneralSamNodeID>> where Self: 'a, Self::KeyType: 'a;
102
103    fn get(&self, key: &KeyType) -> Option<&GeneralSamNodeID> {
104        BTreeMap::get(self, key)
105    }
106
107    fn get_mut(&mut self, key: &KeyType) -> Option<&mut GeneralSamNodeID> {
108        BTreeMap::get_mut(self, key)
109    }
110
111    fn iter(&self) -> Self::IterType<'_> {
112        WithKeyDerefedIter {
113            inner: BTreeMap::iter(self),
114        }
115    }
116
117    fn from_kv_iter<'b, Iter: IntoIterator<Item = (KeyType, &'b GeneralSamNodeID)>>(
118        iter: Iter,
119    ) -> Self
120    where
121        Self::KeyType: 'b,
122    {
123        <Self as ConstructiveTransitionTable>::from_kv_iter(iter)
124    }
125}
126
127pub type HashTransTable<KeyType> = HashMap<KeyType, GeneralSamNodeID>;
128
129impl<KeyType: std::hash::Hash + Eq + Clone> ConstructiveTransitionTable
130    for HashTransTable<KeyType>
131{
132    fn insert(&mut self, key: KeyType, trans: GeneralSamNodeID) {
133        HashMap::insert(self, key, trans);
134    }
135}
136
137impl<KeyType: std::hash::Hash + Eq + Clone> TransitionTable for HashTransTable<KeyType> {
138    type KeyType = KeyType;
139    type IterType<'a> = WithKeyDerefedIter<'a, KeyType, std::collections::hash_map::Iter<'a, KeyType, GeneralSamNodeID>> where Self: 'a, Self::KeyType: 'a;
140
141    fn get(&self, key: &KeyType) -> Option<&GeneralSamNodeID> {
142        HashMap::get(self, key)
143    }
144
145    fn get_mut(&mut self, key: &KeyType) -> Option<&mut GeneralSamNodeID> {
146        HashMap::get_mut(self, key)
147    }
148
149    fn iter(&self) -> Self::IterType<'_> {
150        WithKeyDerefedIter {
151            inner: HashMap::iter(self),
152        }
153    }
154
155    fn from_kv_iter<'b, Iter: IntoIterator<Item = (KeyType, &'b GeneralSamNodeID)>>(
156        iter: Iter,
157    ) -> Self
158    where
159        Self::KeyType: 'b,
160    {
161        <Self as ConstructiveTransitionTable>::from_kv_iter(iter)
162    }
163}
164
165fn bisect_unstable<K: Ord, V, C: AsRef<[(K, V)]>>(container: C, key: &K) -> Option<usize> {
166    let (mut lo, mut hi) = (0, container.as_ref().len());
167    while hi - lo > 0 {
168        let mid = (lo + hi) / 2;
169        match container.as_ref()[mid].0.cmp(key) {
170            std::cmp::Ordering::Equal => {
171                return Some(mid);
172            }
173            std::cmp::Ordering::Less => {
174                lo = mid + 1;
175            }
176            std::cmp::Ordering::Greater => {
177                hi = mid;
178            }
179        }
180    }
181
182    if lo < hi && container.as_ref()[lo].0 == *key {
183        Some(lo)
184    } else {
185        None
186    }
187}
188
189#[derive(Clone, Debug)]
190pub struct BisectTable<
191    K: Clone + Ord,
192    C: AsRef<[(K, GeneralSamNodeID)]>
193        + AsMut<[(K, GeneralSamNodeID)]>
194        + FromIterator<(K, GeneralSamNodeID)>,
195> {
196    inner: C,
197    phantom: PhantomData<K>,
198}
199
200#[derive(Clone, Debug)]
201pub struct BisectTableIter<'s, K: Clone + Ord> {
202    inner: core::slice::Iter<'s, (K, GeneralSamNodeID)>,
203}
204
205impl<'s, K: Clone + Ord> Iterator for BisectTableIter<'s, K> {
206    type Item = (K, &'s GeneralSamNodeID);
207
208    fn next(&mut self) -> Option<Self::Item> {
209        self.inner.next().map(|x| (x.0.clone(), &x.1))
210    }
211}
212
213impl<
214        K: Clone + Ord,
215        C: AsRef<[(K, GeneralSamNodeID)]>
216            + AsMut<[(K, GeneralSamNodeID)]>
217            + FromIterator<(K, GeneralSamNodeID)>,
218    > TransitionTable for BisectTable<K, C>
219{
220    type KeyType = K;
221    type IterType<'a> = BisectTableIter<'a, K> where Self: 'a, Self::KeyType: 'a;
222
223    fn get(&self, key: &Self::KeyType) -> Option<&GeneralSamNodeID> {
224        bisect_unstable(&self.inner, key).map(|i| &self.inner.as_ref()[i].1)
225    }
226
227    fn get_mut(&mut self, key: &K) -> Option<&mut GeneralSamNodeID> {
228        bisect_unstable(&self.inner, key).map(|i| &mut self.inner.as_mut()[i].1)
229    }
230
231    fn iter(&self) -> Self::IterType<'_> {
232        BisectTableIter {
233            inner: self.inner.as_ref().iter(),
234        }
235    }
236
237    fn from_kv_iter<'b, Iter: IntoIterator<Item = (K, &'b GeneralSamNodeID)>>(iter: Iter) -> Self
238    where
239        Self::KeyType: 'b,
240    {
241        let mut inner: Box<[(K, GeneralSamNodeID)]> =
242            iter.into_iter().map(|(u, v)| (u.clone(), *v)).collect();
243        inner.sort_unstable_by(|a, b| a.0.cmp(&b.0));
244        Self {
245            inner: inner.iter().map(|x| (x.0.clone(), x.1)).collect(),
246            phantom: Default::default(),
247        }
248    }
249}
250
251pub type VecBisectTable<K> = BisectTable<K, Vec<(K, GeneralSamNodeID)>>;
252pub type BoxBisectTable<K> = BisectTable<K, Box<[(K, GeneralSamNodeID)]>>;
253
254pub trait SmallAlphabet: Copy + Ord + Into<usize> {
255    const SIZE_LOG_2: usize;
256    const SIZE: usize = 1 << Self::SIZE_LOG_2;
257
258    fn from_usize(val: usize) -> Self;
259}
260
261impl SmallAlphabet for bool {
262    const SIZE_LOG_2: usize = 1;
263
264    fn from_usize(val: usize) -> Self {
265        (val & 1) > 0
266    }
267}
268
269impl SmallAlphabet for u8 {
270    const SIZE_LOG_2: usize = 8;
271
272    fn from_usize(val: usize) -> Self {
273        (val & (Self::SIZE - 1)) as Self
274    }
275}
276
277#[derive(Clone, Debug)]
278pub struct WholeAlphabetTable<
279    K: SmallAlphabet,
280    C: AsRef<[Option<GeneralSamNodeID>]>
281        + AsMut<[Option<GeneralSamNodeID>]>
282        + FromIterator<Option<GeneralSamNodeID>>
283        + Clone,
284> {
285    inner: C,
286    phantom: PhantomData<K>,
287}
288
289#[derive(Clone, Debug)]
290pub struct WholeAlphabetTableIter<'s, K: SmallAlphabet> {
291    inner: std::iter::Enumerate<core::slice::Iter<'s, Option<GeneralSamNodeID>>>,
292    phantom: PhantomData<K>,
293}
294
295impl<'s, K: SmallAlphabet> Iterator for WholeAlphabetTableIter<'s, K> {
296    type Item = (K, &'s GeneralSamNodeID);
297
298    fn next(&mut self) -> Option<Self::Item> {
299        for (k, ref v) in self.inner.by_ref() {
300            if let Some(ref v) = v {
301                return Some((K::from_usize(k), v));
302            }
303        }
304        None
305    }
306}
307
308impl<
309        K: SmallAlphabet,
310        C: AsRef<[Option<GeneralSamNodeID>]>
311            + AsMut<[Option<GeneralSamNodeID>]>
312            + FromIterator<Option<GeneralSamNodeID>>
313            + Clone,
314    > Default for WholeAlphabetTable<K, C>
315{
316    fn default() -> Self {
317        Self {
318            inner: C::from_iter(repeat(None).take(K::SIZE)),
319            phantom: Default::default(),
320        }
321    }
322}
323
324impl<
325        K: SmallAlphabet,
326        C: AsRef<[Option<GeneralSamNodeID>]>
327            + AsMut<[Option<GeneralSamNodeID>]>
328            + FromIterator<Option<GeneralSamNodeID>>
329            + Clone,
330    > ConstructiveTransitionTable for WholeAlphabetTable<K, C>
331{
332    fn insert(&mut self, key: Self::KeyType, trans: GeneralSamNodeID) {
333        let k: usize = key.into();
334        self.inner.as_mut()[k] = Some(trans)
335    }
336}
337
338impl<
339        K: SmallAlphabet,
340        C: AsRef<[Option<GeneralSamNodeID>]>
341            + AsMut<[Option<GeneralSamNodeID>]>
342            + FromIterator<Option<GeneralSamNodeID>>
343            + Clone,
344    > TransitionTable for WholeAlphabetTable<K, C>
345{
346    type KeyType = K;
347    type IterType<'a> = WholeAlphabetTableIter<'a, K> where Self: 'a, Self::KeyType: 'a;
348
349    fn get(&self, key: &Self::KeyType) -> Option<&GeneralSamNodeID> {
350        let k: usize = (*key).into();
351        self.inner.as_ref().get(k).and_then(|x| x.as_ref())
352    }
353
354    fn get_mut(&mut self, key: &Self::KeyType) -> Option<&mut GeneralSamNodeID> {
355        let k: usize = (*key).into();
356        self.inner.as_mut().get_mut(k).and_then(|x| x.as_mut())
357    }
358
359    fn iter(&self) -> Self::IterType<'_> {
360        WholeAlphabetTableIter {
361            inner: self.inner.as_ref().iter().enumerate(),
362            phantom: Default::default(),
363        }
364    }
365
366    fn from_kv_iter<'b, Iter: IntoIterator<Item = (Self::KeyType, &'b GeneralSamNodeID)>>(
367        iter: Iter,
368    ) -> Self
369    where
370        Self::KeyType: 'b,
371    {
372        <Self as ConstructiveTransitionTable>::from_kv_iter(iter)
373    }
374}
general_sam/table.rs

general_sam/
table.rs
