worlde_automaton/
types.rs

1//! Types and data structures to help with the automaton implementation
2
3/// A possible letter, can only be lowercase ASCII characters, i.e. [a-z]
4#[derive(Clone, Copy, Debug, PartialEq, Eq)]
5#[repr(transparent)]
6pub struct Letter(u8);
7
8impl Letter {
9    /// Create a new letter
10    ///
11    /// Returns None if the letter is not in [a-zA-Z]
12    #[must_use]
13    pub const fn try_new(b: u8) -> Option<Self> {
14        match b {
15            b'a'..=b'z' => Some(Self(b - b'a')),
16            b'A'..=b'Z' => Some(Self(b - b'A')),
17            _ => None,
18        }
19    }
20
21    /// Create a new letter
22    ///
23    /// # Panics
24    /// Panics if the letter is not in [a-zA-Z]
25    #[must_use]
26    pub const fn new(b: u8) -> Self {
27        match b {
28            b'a'..=b'z' => Self(b - b'a'),
29            b'A'..=b'Z' => Self(b - b'A'),
30            _ => panic!("Invalid letter, only accept [a-zA-Z]"),
31        }
32    }
33}
34
35impl From<Letter> for u8 {
36    fn from(letter: Letter) -> Self {
37        b'a' + letter.0
38    }
39}
40
41/// A set of letters
42#[derive(Clone, Copy, Debug, PartialEq, Eq)]
43#[repr(transparent)]
44pub struct LetterSet(u32);
45
46impl LetterSet {
47    /// Create an empty set
48    #[must_use]
49    pub const fn new() -> Self {
50        Self(0)
51    }
52
53    /// Test if a letter is contained in this set
54    #[must_use]
55    pub const fn contains(self, letter: Letter) -> bool {
56        (self.0 >> letter.0) & 1 == 1
57    }
58
59    /// Add a letter to this set
60    #[must_use]
61    pub const fn add(self, letter: Letter) -> Self {
62        Self(self.0 | (1 << letter.0))
63    }
64}
65
66/// A list of letters with support for up to 5 entries
67#[derive(Clone, Copy, Debug, PartialEq, Eq)]
68#[repr(transparent)]
69pub struct LetterList(u32);
70
71impl LetterList {
72    /// Create an empty list
73    #[must_use]
74    pub const fn new() -> Self {
75        Self(0)
76    }
77
78    /// Return the number of entries in this list
79    #[must_use]
80    pub const fn len(self) -> u32 {
81        self.0 & 0x1F
82    }
83
84    /// Returns true iff the list is empty
85    #[must_use]
86    pub const fn is_empty(self) -> bool {
87        self.0 == 0
88    }
89
90    /// Adds a letter in O(1)
91    ///
92    /// # Panics
93    /// Panic if the list is full
94    #[must_use]
95    pub const fn add(self, letter: Letter) -> Self {
96        let len = self.len() + 1;
97        debug_assert!(len <= 5, "maximum capacity of 5 is reached");
98        Self((letter.0 as u32 + 1) << (5 * len) | (self.0 & !0x1F) | len)
99    }
100
101    /// Removes a letter by comparing the value in O(n)
102    ///
103    /// Returns (true, newList) if item was in this list, otherwise returns (false, self)
104    #[must_use]
105    pub const fn remove(self, letter: Letter) -> (bool, Self) {
106        let t = letter.0 as u32 + 1;
107        let mut r = 0;
108        let mut rs = 5;
109        let mut n = self.0 >> 5;
110        while n != 0 {
111            let x = n & 0x1F;
112            n >>= 5;
113
114            if x == t {
115                return (true, Self(r | n << rs | (self.len() - 1)));
116            }
117
118            r |= x << rs;
119            rs += 5;
120        }
121
122        (false, self)
123    }
124
125    /// Create an iterator over all entries in this list.
126    #[must_use]
127    pub const fn iter(self) -> LetterListIter {
128        LetterListIter(self.0 >> 5)
129    }
130}
131
132/// List entry iterator. See [`LetterList::iter()`].
133#[allow(missing_copy_implementations)] // Iterators should not be copy
134#[derive(Clone, Debug)]
135pub struct LetterListIter(u32);
136
137impl Iterator for LetterListIter {
138    type Item = Letter;
139
140    fn next(&mut self) -> Option<Self::Item> {
141        if self.0 == 0 {
142            return None;
143        }
144        let x = (self.0 & 0x1F) - 1;
145        // this should never fail
146        let x = u8::try_from(x).ok()?;
147        self.0 >>= 5;
148        Some(Letter(x))
149    }
150}
151
152impl IntoIterator for LetterList {
153    type Item = Letter;
154
155    type IntoIter = LetterListIter;
156
157    fn into_iter(self) -> Self::IntoIter {
158        self.iter()
159    }
160}
161
162/// Constraint for a single position
163///
164/// Combines a [`LetterSet`] with an additional quasi-Option of a single entry
165/// The set flags all letters that may never appear on this position (eff. 26 bits for 26 letters)
166/// The entry is set if a known letter is at that position (5 bits to write 1 value in 0..26)
167/// The last bit encodes whether the set or the entry are in use (1-set, 0-entry)
168#[derive(Clone, Copy, Debug, PartialEq, Eq)]
169#[repr(transparent)]
170pub struct Constraint(u32);
171
172impl Constraint {
173    /// Create an empty constraint
174    #[must_use]
175    pub const fn new() -> Self {
176        Self(1 << 31)
177    }
178
179    /// Test if the letter is accepted by the this constraint
180    ///
181    /// If the known-entry is set, the letter must match that entry
182    /// Otherwise the letter must not be in the set
183    #[must_use]
184    pub const fn accept(self, letter: Letter) -> bool {
185        // cast is safe since we shift by 26, which leaves 6 bits
186        #[allow(clippy::cast_possible_truncation)]
187        let must = (self.0 >> 26) as u8;
188        if must < 32 {
189            must == letter.0
190        } else {
191            !LetterSet(self.0).contains(letter)
192        }
193    }
194
195    /// Test is the constraint is still unknown, i.e. does not have a known entry
196    #[must_use]
197    pub const fn is_free(self) -> bool {
198        self.0 >> 31 == 1
199    }
200
201    /// Set the letter as the known entry
202    #[must_use]
203    pub const fn must(self, letter: Letter) -> Self {
204        Self((letter.0 as u32) << 26 | (self.0 & 0x03FF_FFFF))
205    }
206
207    /// Flag a letter as invalid for this constraint
208    #[must_use]
209    pub const fn must_not(self, letter: Letter) -> Self {
210        Self(LetterSet(self.0).add(letter).0)
211    }
212
213    /// Return the letter that is known to be required
214    ///
215    /// The result is unreliable if [`Constraint::is_free()`] returns `false`.
216    /// _Some_ arbitrary letter is returned.
217    #[must_use]
218    pub const fn must_letter(self) -> Letter {
219        // cast is safe since we shift by 26 and mask by 0x1F, which leaves 5 bits
220        #[allow(clippy::cast_possible_truncation)]
221        Letter(((self.0 >> 26) & 0x1F) as _)
222    }
223}
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228
229    #[test]
230    fn test_letter_try_new() {
231        assert_eq!(Letter::try_new(b'a'), Some(Letter(0)));
232        assert_eq!(Letter::try_new(b'z'), Some(Letter(25)));
233        assert_eq!(Letter::try_new(b'A'), Some(Letter(0)));
234        assert_eq!(Letter::try_new(b'Z'), Some(Letter(25)));
235        assert_eq!(Letter::try_new(b' '), None);
236        assert_eq!(Letter::try_new(b'0'), None);
237        assert_eq!(Letter::try_new(b'9'), None);
238        assert_eq!(Letter::try_new(b'.'), None);
239        assert_eq!(Letter::try_new(b'!'), None);
240    }
241
242    #[test]
243    fn test_letter_new() {
244        assert_eq!(Letter::new(b'a'), Letter(0));
245        assert_eq!(Letter::new(b'z'), Letter(25));
246        assert_eq!(Letter::new(b'A'), Letter(0));
247        assert_eq!(Letter::new(b'Z'), Letter(25));
248    }
249
250    #[test]
251    fn test_letter_into() {
252        assert_eq!(u8::from(Letter::new(b'a')), b'a');
253        assert_eq!(u8::from(Letter::new(b'z')), b'z');
254        assert_eq!(u8::from(Letter::new(b'A')), b'a');
255        assert_eq!(u8::from(Letter::new(b'Z')), b'z');
256    }
257
258    #[test]
259    #[should_panic(expected = "Invalid letter, only accept [a-zA-Z]")]
260    const fn test_letter_new_invalid() {
261        let _ = Letter::new(b' ');
262    }
263
264    #[test]
265    fn test_set() {
266        let set = LetterSet::new();
267        assert!(!set.contains(Letter(0)));
268        assert!(!set.contains(Letter(1)));
269        let set = set.add(Letter(0));
270        assert!(set.contains(Letter(0)));
271        assert!(!set.contains(Letter(1)));
272        let set = set.add(Letter(1));
273        assert!(set.contains(Letter(0)));
274        assert!(set.contains(Letter(1)));
275        // set semantics
276        let set = set.add(Letter(0));
277        assert!(set.contains(Letter(0)));
278        assert!(set.contains(Letter(1)));
279    }
280
281    #[test]
282    fn test_list() {
283        let list = LetterList::new();
284        assert_eq!(list.len(), 0);
285
286        let list = list.add(Letter(0));
287        assert_eq!(list.len(), 1);
288
289        let list = list.add(Letter(1));
290        assert_eq!(list.len(), 2);
291
292        // list semantics, not set
293        let list = list.add(Letter(0));
294        assert_eq!(list.len(), 3);
295    }
296
297    fn contains(ev: LetterList, letter: Letter) -> bool {
298        ev.iter().any(|l| l == letter)
299    }
300
301    #[test]
302    fn test_list_contains() {
303        let list = LetterList::new();
304        assert!(!contains(list, Letter(0)));
305        assert!(!contains(list, Letter(1)));
306
307        let list = list.add(Letter(0));
308        assert!(contains(list, Letter(0)));
309        assert!(!contains(list, Letter(1)));
310
311        let list = list.add(Letter(1));
312        assert!(contains(list, Letter(0)));
313        assert!(contains(list, Letter(1)));
314
315        let list = list.add(Letter(0));
316        assert!(contains(list, Letter(0)));
317        assert!(contains(list, Letter(1)));
318    }
319
320    #[test]
321    fn test_list_remove() {
322        let list = LetterList::new();
323        let (removed, _) = list.remove(Letter(0));
324        assert!(!removed);
325
326        let list = list.add(Letter(0));
327        let (removed, list2) = list.remove(Letter(0));
328        assert!(removed);
329        assert!(contains(list, Letter(0)));
330        assert!(!contains(list2, Letter(0)));
331
332        let list = list.add(Letter(1));
333        let (removed, list2) = list.remove(Letter(1));
334        assert!(removed);
335        assert!(contains(list, Letter(0)));
336        assert!(contains(list, Letter(1)));
337        assert!(contains(list2, Letter(0)));
338        assert!(!contains(list2, Letter(1)));
339
340        let list = list.add(Letter(0));
341        let (removed, list2) = list.remove(Letter(0));
342        assert!(removed);
343        assert!(contains(list, Letter(0)));
344        assert!(contains(list, Letter(1)));
345        assert!(contains(list2, Letter(0)));
346        assert!(contains(list2, Letter(1)));
347    }
348
349    #[test]
350    fn test_list_iter() {
351        let list = LetterList::new()
352            .add(Letter(0))
353            .add(Letter(1))
354            .add(Letter(2));
355
356        let letters = list.into_iter().collect::<Vec<_>>();
357        assert_eq!(letters, &[Letter(0), Letter(1), Letter(2)]);
358    }
359
360    #[test]
361    #[should_panic(expected = "maximum capacity of 5 is reached")]
362    const fn test_list_full() {
363        let list = LetterList(5);
364        let _ = list.add(Letter(0));
365    }
366
367    #[test]
368    fn test_constraint() {
369        let cons = Constraint::new();
370        assert!(cons.accept(Letter(0)));
371        assert!(cons.accept(Letter(1)));
372
373        let cons = cons.must_not(Letter(0));
374        assert!(!cons.accept(Letter(0)));
375        assert!(cons.accept(Letter(1)));
376
377        let cons = cons.must(Letter(0));
378        assert!(cons.accept(Letter(0)));
379        assert!(!cons.accept(Letter(1)));
380    }
381
382    #[test]
383    fn test_constraint_is_free() {
384        let cons = Constraint::new();
385        assert!(cons.is_free());
386
387        let cons = cons.must_not(Letter(0));
388        assert!(cons.is_free());
389
390        let cons = cons.must(Letter(0));
391        assert!(!cons.is_free());
392    }
393
394    #[test]
395    fn test_constraint_must_letter() {
396        let cons = Constraint::new();
397
398        let cons = cons.must(Letter(1));
399        assert_eq!(cons.must_letter(), Letter(1));
400
401        let cons = cons.must(Letter(2));
402        assert_eq!(cons.must_letter(), Letter(2));
403    }
404}
worlde_automaton/types.rs

worlde_automaton/
types.rs
