kermit_algos/
singleton.rs

1//! Singleton unary trie iterator representing a nonmaterialized view
2//! of `Const_a = {a}`, used by the Const-view rewrite (see
3//! [`crate::const_rewrite`]).
4
5use kermit_iters::{JoinIterable, LinearIterator, TrieIterable, TrieIterator, TrieIteratorWrapper};
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8enum State {
9    Root,
10    AtValue,
11    Exhausted,
12}
13
14/// Unary trie iterator holding a single `usize` value.
15///
16/// Equivalent to the paper's "nonmaterialized view" of `Const_a = {a}`
17/// (Veldhuizen 2014 §3.4 point 4). Exposes exactly one tuple `[value]`
18/// through the [`TrieIterator`] / [`LinearIterator`] interface.
19#[derive(Debug, Clone)]
20pub struct SingletonTrieIter {
21    value: usize,
22    state: State,
23}
24
25impl SingletonTrieIter {
26    /// Constructs a new singleton positioned at its root (pre-`open`).
27    pub fn new(value: usize) -> Self {
28        Self {
29            value,
30            state: State::Root,
31        }
32    }
33}
34
35impl LinearIterator for SingletonTrieIter {
36    fn key(&self) -> Option<usize> {
37        match self.state {
38            | State::AtValue => Some(self.value),
39            | State::Root | State::Exhausted => None,
40        }
41    }
42
43    fn next(&mut self) -> Option<usize> {
44        if self.state == State::AtValue {
45            self.state = State::Exhausted;
46        }
47        None
48    }
49
50    fn seek(&mut self, seek_key: usize) -> bool {
51        if self.state != State::AtValue {
52            return false;
53        }
54        if seek_key > self.value {
55            self.state = State::Exhausted;
56            false
57        } else {
58            true
59        }
60    }
61
62    fn at_end(&self) -> bool { self.state == State::Exhausted }
63}
64
65impl TrieIterator for SingletonTrieIter {
66    fn open(&mut self) -> bool {
67        match self.state {
68            | State::Root => {
69                self.state = State::AtValue;
70                true
71            },
72            | State::AtValue | State::Exhausted => false,
73        }
74    }
75
76    fn up(&mut self) -> bool {
77        match self.state {
78            | State::AtValue | State::Exhausted => {
79                self.state = State::Root;
80                true
81            },
82            | State::Root => false,
83        }
84    }
85}
86
87impl IntoIterator for SingletonTrieIter {
88    type IntoIter = TrieIteratorWrapper<Self>;
89    type Item = Vec<usize>;
90
91    fn into_iter(self) -> Self::IntoIter { TrieIteratorWrapper::new(self) }
92}
93
94impl JoinIterable for SingletonTrieIter {}
95
96impl TrieIterable for SingletonTrieIter {
97    fn trie_iter(&self) -> impl TrieIterator + IntoIterator<Item = Vec<usize>> { self.clone() }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn new_at_root_not_at_end() {
106        let it = SingletonTrieIter::new(42);
107        assert_eq!(it.state, State::Root);
108        assert!(!it.at_end());
109        assert_eq!(it.key(), None);
110    }
111
112    #[test]
113    fn open_descends_to_value() {
114        let mut it = SingletonTrieIter::new(42);
115        assert!(it.open());
116        assert_eq!(it.state, State::AtValue);
117        assert_eq!(it.key(), Some(42));
118        assert!(!it.at_end());
119    }
120
121    #[test]
122    fn next_exhausts_the_level() {
123        let mut it = SingletonTrieIter::new(42);
124        it.open();
125        assert_eq!(it.next(), None);
126        assert_eq!(it.state, State::Exhausted);
127        assert!(it.at_end());
128        assert_eq!(it.key(), None);
129    }
130
131    #[test]
132    fn seek_below_value_stays_at_value() {
133        let mut it = SingletonTrieIter::new(42);
134        it.open();
135        assert!(it.seek(10));
136        assert_eq!(it.key(), Some(42));
137    }
138
139    #[test]
140    fn seek_at_value_stays_at_value() {
141        let mut it = SingletonTrieIter::new(42);
142        it.open();
143        assert!(it.seek(42));
144        assert_eq!(it.key(), Some(42));
145    }
146
147    #[test]
148    fn seek_above_value_exhausts() {
149        let mut it = SingletonTrieIter::new(42);
150        it.open();
151        assert!(!it.seek(43));
152        assert!(it.at_end());
153    }
154
155    #[test]
156    fn up_from_value_returns_to_root() {
157        let mut it = SingletonTrieIter::new(42);
158        it.open();
159        assert!(it.up());
160        assert_eq!(it.state, State::Root);
161    }
162
163    #[test]
164    fn open_then_up_then_reopen_is_idempotent() {
165        let mut it = SingletonTrieIter::new(42);
166        assert!(it.open());
167        assert_eq!(it.key(), Some(42));
168        assert!(it.up());
169        assert!(it.open());
170        assert_eq!(it.key(), Some(42));
171    }
172
173    #[test]
174    fn wrapper_yields_single_tuple() {
175        let tuples: Vec<Vec<usize>> = SingletonTrieIter::new(7).into_iter().collect();
176        assert_eq!(tuples, vec![vec![7]]);
177    }
178}
kermit_algos/singleton.rs

kermit_algos/
singleton.rs
