transition_table/
lib.rs

1#![doc = include_str!("../README.md")]
2#![no_std]
3extern crate alloc;
4
5use alloc::vec::Vec;
6
7/// Type alias for the transition table entry.
8pub type Transition<K, J, OpV> = (K, J, J, OpV);
9
10/// To represent empty trie entry.
11/// Provided implementations for integer primitive types as `-1` represents None.
12pub trait Optional: Copy {
13    type Inner: Copy;
14
15    fn none() -> Self;
16    fn some(v: Self::Inner) -> Self;
17    fn is_none(&self) -> bool;
18    fn is_some(&self) -> bool { !self.is_none() }
19    fn inner(&self) -> Option<Self::Inner>;
20}
21
22macro_rules! optional_uint {
23    ($($ty:ty),+) => {
24        $(
25            impl Optional for $ty {
26                type Inner = $ty;
27
28                fn none() -> Self { !0 }
29
30                fn some(v: Self::Inner) -> Self {
31                    assert_ne!(v, Self::none());
32                    v
33                }
34
35                fn is_none(&self) -> bool {
36                    *self == Self::none()
37                }
38
39                fn inner(&self) -> Option<Self::Inner> {
40                    if self.is_none() {
41                        None
42                    } else {
43                        Some(*self)
44                    }
45                }
46            }
47        )+
48    };
49}
50
51optional_uint! { u8, u16, u32, u64, u128, usize }
52
53impl<T: Copy> Optional for Option<T> {
54    type Inner = T;
55
56    fn none() -> Self { None }
57    fn some(v: Self::Inner) -> Self { Some(v) }
58    fn is_none(&self) -> bool {
59        self.is_none()
60    }
61
62    fn inner(&self) -> Option<Self::Inner> {
63        *self
64    }
65}
66
67/// Trie generator.
68///
69/// ```
70/// # use transition_table::*;
71/// const KEYWORDS: [(&'static str, i8); 3] = [
72///     ("A", 1),
73///     ("BB", 2),
74///     ("BBC", 3),
75/// ];
76///
77/// let tree = Entry::<char, _>::new(KEYWORDS.iter());
78/// let tbl: Vec<Transition<_, _, _>> = tree.into();
79/// let mut it = tbl.iter();
80///
81/// assert_eq!(it.next().unwrap(), &('C', 0usize, 0usize, 2usize));
82/// assert_eq!(it.next().unwrap(), &('B', 0usize, 1usize, 1usize));
83/// assert_eq!(it.next().unwrap(), &('A', 0usize, 0usize, 0usize));
84/// assert_eq!(it.next().unwrap(), &('B', 1usize, 2usize, !0usize));
85/// assert_eq!(it.next().unwrap(), &('\u{0}', 2usize, 4usize, !0usize));
86/// assert!(it.next().is_none());
87/// ```
88pub struct Entry<K, V> {
89    key: K,
90    nexts: Vec<Self>,
91    value: V,
92}
93
94macro_rules! impl_entry_new {
95    ($key:ty, $iter:ident) => {
96        impl Entry<$key, usize> {
97            /// Reading const array, then creating tree structure to generate trie.
98            pub fn new<'a, I, S, V>(src: I) -> Self
99            where
100                I: Iterator<Item = &'a (S, V)>,
101                S: 'a + AsRef<str>,
102                V: 'a,
103            {
104                src.enumerate().fold(
105                    Self::default(),
106                    |mut root, (i, (ref s, _))| {
107                        root.push(s.as_ref().$iter(), i);
108                        root
109                    }
110                )
111            }
112        }
113    };
114}
115
116impl_entry_new! { char, chars }
117impl_entry_new! { u8, bytes }
118
119impl<K, V> Entry<K, V>
120where
121    K: Copy + Ord,
122    V: Optional,
123{
124    /// Pushing a single entry.
125    pub fn push<I>(&mut self, key: I, v: V::Inner)
126    where
127        I: IntoIterator<Item = K>
128    {
129        let mut it = key.into_iter();
130
131        match it.next() {
132            Some(c) => {
133                let i = match self.nexts.binary_search_by_key(&c, |e| e.key) {
134                    Ok(i) => i,
135                    Err(i) => {
136                        self.nexts.insert(i, Self {
137                            key: c,
138                            nexts: Vec::new(),
139                            value: V::none(),
140                        });
141                        i
142                    },
143                };
144
145                self.nexts[i].push(it, v)
146            },
147            None => self.value = V::some(v),
148        }
149    }
150
151    /// Generating trie.
152    pub fn push_to(&self, tbl: &mut Vec<Transition<K, usize, V>>) -> Transition<K, usize, V> {
153        let mut v = self.nexts.iter().fold(
154            Vec::new(),
155            |mut v, child| {
156                v.push(child.push_to(tbl));
157                v
158            }
159        );
160        let retval = (self.key, tbl.len(), tbl.len() + self.nexts.len(), self.value.clone());
161
162        tbl.append(&mut v);
163        retval
164    }
165}
166
167impl<K, V> Default for Entry<K, V>
168where
169    K: Default,
170    V: Optional,
171{
172    fn default() -> Self {
173        Self {
174            key: Default::default(),
175            nexts: Vec::new(),
176            value: V::none(),
177        }
178    }
179}
180
181impl<K, V> Into<Vec<Transition<K, usize, V>>> for Entry<K, V>
182where
183    K: Copy + Ord,
184    V: Optional,
185{
186    fn into(self) -> Vec<Transition<K, usize, V>> {
187        let mut tbl = Vec::new();
188        let root = self.push_to(&mut tbl);
189
190        tbl.push(root);
191        tbl
192    }
193}
transition_table/lib.rs

transition_table/
lib.rs
