libunseemly/util/
asterism.rs

1use std::{fmt, iter::Iterator};
2
3// An `Asterism` is a tree with an arbirary arity at each node,
4//  but all leaves are at the same depth.
5// This structure arises from parsing under Kleene stars; each star correspons to a level of nodes.
6
7// [                                              ] <- 2 children
8// [                                        ][    ] <- 3, 1 children
9// [                          ][][          ][    ] <- 5, 0, 1, 2 children
10// [    ][ ][    ][    ][     ]  [          ][ ][ ] <- 2, 1, 2, 2, 2, 4, 1, 1 children
11//  a  b  c  d  e  f  g  h  i     j  k  l  m  n  o
12
13// * * # a b # c # d e # f g # h i * * # j k l m * * # n # o
14//     ----| --| ----| ----| ----| |   --------|     --| --| <- these are `PackedNodes`es
15//   ----------------------------| | ----------|   --------| <- everything below is a `Node`
16// --------------------------------------------| ----------| <-             ⋮
17
18#[derive(Debug, PartialEq, Eq, Clone)]
19/// This is only `pub` for technical reasons; it doesn't need to be exposed to other modules.
20///
21/// `Node`s and `PackedNodes`es appear at the beginning of a slice to guide marching.
22/// If you see `[PackedNodes, …]`, you know you're at depth 1 and [1..] is your leaves.
23/// Otherwise, `[Node(n), <n entries>, Node(m), <m entries>, …]` is the shape of the current level.
24pub enum LeafOrNode<T> {
25    Leaf(T),
26    /// A depth-1 node: *each* subtree is a single `Leaf`
27    PackedNodes,
28    /// A depth >1 node: *this* subtree is `usize` entires long
29    Node(usize),
30}
31
32#[derive(PartialEq, Eq, Clone)]
33pub struct Asterism<T>(Vec<LeafOrNode<T>>);
34#[derive(PartialEq, Eq)]
35pub struct AsterismSlice<'a, T>(&'a [LeafOrNode<T>]);
36
37// `AsterismSlice` is a reference-like type, so it's always `Clone` and `Copy`, even if `T` isn't:
38impl<'a, T> Copy for AsterismSlice<'a, T> {}
39impl<'a, T> Clone for AsterismSlice<'a, T> {
40    fn clone(&self) -> AsterismSlice<'a, T> { *self }
41}
42
43/// This trait is for reference-like views of `Asterism`.
44pub trait AsterMarchable<'a, T: 'a>: Sized + Clone + Copy {
45    fn as_slice(self) -> AsterismSlice<'a, T>;
46
47    /// Only used for implementation of other methods;
48    ///  adding another layer of trait seems like too much trouble to hide this.
49    fn inner(self) -> &'a [LeafOrNode<T>];
50
51    /// Returns an iterator of `AsterMarchable<T>`s
52    fn march(self) -> std::vec::IntoIter<AsterismSlice<'a, T>> {
53        let mut subs = vec![];
54        if self.inner().len() == 0 {
55            return subs.into_iter();
56        }
57
58        // A `PackedNodes` means the rest of the slice is our children (all leaves):
59        let depth_1: bool = match self.inner()[0] {
60            LeafOrNode::PackedNodes => true,
61            _ => false,
62        };
63        let mut i = if depth_1 { 1 } else { 0 }; // Skip the `PackedNodes`
64
65        while i < self.inner().len() {
66            let span = match self.inner()[i] {
67                LeafOrNode::Leaf(_) => {
68                    if !depth_1 {
69                        icp!("Unexpected Leaf")
70                    }
71                    1
72                }
73                LeafOrNode::PackedNodes => icp!("Unexpected PackedNodes"),
74                LeafOrNode::Node(span) => {
75                    if depth_1 {
76                        icp!("Unexpected Node")
77                    }
78                    i += 1;
79                    span
80                }
81            };
82            subs.push(AsterismSlice(&self.inner()[i..i + span]));
83
84            i += span;
85        }
86
87        subs.into_iter()
88    }
89
90    fn collect(self) -> Vec<AsterismSlice<'a, T>> {
91        let mut res = vec![];
92        for sub in self.march() {
93            res.push(sub);
94        }
95        res
96    }
97
98    fn is_leaf(self) -> bool {
99        let inner = self.as_slice().0;
100        if inner.len() == 0 {
101            return false;
102        }
103        match inner[0] {
104            LeafOrNode::Leaf(_) => true,
105            _ => false,
106        }
107    }
108
109    fn as_leaf(self) -> &'a T {
110        let inner = self.as_slice().0;
111        if inner.len() != 1 {
112            icp!("not a leaf, length is {}", inner.len())
113        }
114        match inner[0] {
115            LeafOrNode::Leaf(ref l) => l,
116            _ => icp!("malformed Asterism"),
117        }
118    }
119
120    fn as_depth_1(self) -> Box<dyn Iterator<Item = &'a T> + 'a> {
121        if self.as_slice().0.len() == 0 {
122            // The "official" representation of an empty depth-1 node is a sequence with 1 `PN`.
123            // ...but `Asterism::join(vec![])` doesn't know whether it's depth-1 or not!
124            // So we also support an empty vector.
125            // TODO: is there a better way?
126            return Box::new(std::iter::empty());
127        }
128        match self.as_slice().0[0] {
129            LeafOrNode::PackedNodes => {}
130            _ => icp!("Not depth-1"),
131        }
132        Box::new(self.as_slice().0[1..].iter().map(|lon| match lon {
133            LeafOrNode::Leaf(ref l) => l,
134            _ => icp!("Not depth-1"),
135        }))
136    }
137}
138
139impl<'a, T> AsterMarchable<'a, T> for AsterismSlice<'a, T> {
140    fn as_slice(self) -> AsterismSlice<'a, T> { self }
141    fn inner(self) -> &'a [LeafOrNode<T>] { self.0 }
142}
143
144impl<'a, T> AsterMarchable<'a, T> for &'a Asterism<T> {
145    fn as_slice(self) -> AsterismSlice<'a, T> { AsterismSlice(&self.0[..]) }
146    fn inner(self) -> &'a [LeafOrNode<T>] { &self.0[..] }
147}
148
149impl<T> Asterism<T> {
150    pub fn join(subs: Vec<Asterism<T>>) -> Asterism<T> {
151        let mut res = vec![];
152        if subs.len() == 0 {
153            return Asterism(vec![LeafOrNode::Node(0)]);
154        }
155        if subs[0].0.len() != 0 {
156            match subs[0].0[0] {
157                LeafOrNode::Leaf(_) => {
158                    let mut res = vec![LeafOrNode::PackedNodes];
159                    for mut leaf_asterism in subs {
160                        if !leaf_asterism.is_leaf() {
161                            icp!("Not a valid leaf");
162                        }
163                        res.push(leaf_asterism.0.remove(0));
164                    }
165                    return Asterism(res);
166                }
167                _ => {}
168            }
169        }
170
171        for mut aster in subs {
172            res.push(LeafOrNode::Node(aster.0.len()));
173            res.append(&mut aster.0);
174        }
175        Asterism(res)
176    }
177
178    pub fn from_leaf(leaf: T) -> Asterism<T> { Asterism(vec![LeafOrNode::Leaf(leaf)]) }
179
180    pub fn from_depth_1(leaves: Vec<T>) -> Asterism<T> {
181        let mut res = vec![LeafOrNode::PackedNodes];
182        for leaf in leaves {
183            res.push(LeafOrNode::Leaf(leaf))
184        }
185
186        Asterism(res)
187    }
188}
189
190impl<'a, T: Clone> AsterismSlice<'a, T> {
191    pub fn to_asterism(self) -> Asterism<T> { Asterism(self.0.to_vec()) }
192}
193
194impl<T: fmt::Debug> fmt::Debug for AsterismSlice<'_, T> {
195    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
196        if self.is_leaf() {
197            write!(f, "{:?}", self.as_leaf())
198        } else {
199            write!(f, "[")?;
200            let mut first = true;
201            for ref sub in self.march() {
202                if !first {
203                    write!(f, " ")?;
204                }
205                write!(f, "{:?}", sub)?;
206                first = false;
207            }
208            write!(f, "]")
209        }
210    }
211}
212
213impl<T: fmt::Debug> fmt::Debug for Asterism<T> {
214    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.as_slice().fmt(f) }
215}
216
217impl<T: fmt::Display> fmt::Display for AsterismSlice<'_, T> {
218    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
219        if self.is_leaf() {
220            write!(f, "{}", self.as_leaf())
221        } else {
222            write!(f, "[")?;
223            let mut first = true;
224            for ref sub in self.march() {
225                if !first {
226                    write!(f, " ")?;
227                }
228                write!(f, "{}", sub)?;
229                first = false;
230            }
231            write!(f, "]")
232        }
233    }
234}
235
236impl<T: fmt::Display> fmt::Display for Asterism<T> {
237    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.as_slice().fmt(f) }
238}
239
240impl<T: fmt::Debug> Asterism<T> {
241    /// For internal debugging only
242    fn show(&self) {
243        for elt in &self.0 {
244            match elt {
245                LeafOrNode::Node(n) => print!("N{} ", n),
246                LeafOrNode::PackedNodes => print!("PN "),
247                LeafOrNode::Leaf(l) => print!("L{:?} ", l),
248            }
249        }
250    }
251}
252
253#[test]
254fn asterism_basics() {
255    let abc = Asterism::from_depth_1(vec!["a", "b", "c"]);
256
257    assert_eq!(abc.as_slice().as_depth_1().collect::<Vec<_>>(), vec![&"a", &"b", &"c"]);
258
259    let (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) =
260        (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14);
261
262    let a_through_i = Asterism::join(vec![
263        Asterism::from_depth_1(vec![a, b]),
264        Asterism::from_depth_1(vec![c]),
265        Asterism::from_depth_1(vec![d, e]),
266        Asterism::from_depth_1(vec![f, g]),
267        Asterism::from_depth_1(vec![h, i]),
268    ]);
269
270    let a_through_m = Asterism::join(vec![
271        a_through_i,
272        Asterism::join(vec![]), // Empty `Asterism`s can be deeper than they look
273        Asterism::join(vec![Asterism::from_depth_1(vec![j, k, l, m])]),
274    ]);
275
276    let a_through_o = Asterism::join(vec![
277        a_through_m,
278        Asterism::join(vec![Asterism::join(vec![
279            Asterism::from_depth_1(vec![n]),
280            Asterism::from_depth_1(vec![o]),
281        ])]),
282    ]);
283
284    assert_eq!(
285        format!("{}", a_through_o),
286        "[[[[0 1] [2] [3 4] [5 6] [7 8]] [[]] [[9 10 11 12]]] [[[13] [14]]]]"
287    );
288
289    let mut expected_d1 = 0;
290    let mut expected_m = 0;
291    for m in a_through_o.march() {
292        for mm in m.march() {
293            for mmm in mm.march() {
294                for mmmm in mmm.as_depth_1() {
295                    assert_eq!(*mmmm, expected_d1);
296                    expected_d1 += 1;
297                }
298                for mmmm in mmm.march() {
299                    assert_eq!(*mmmm.as_leaf(), expected_m);
300                    expected_m += 1;
301                }
302            }
303        }
304    }
305    assert_eq!(15, expected_d1);
306    assert_eq!(15, expected_m);
307
308    let d1 = Asterism::from_depth_1(vec![vec![1, 3], vec![2, 3]]);
309
310    for v in d1.as_depth_1() {
311        assert_eq!(v.len(), 2)
312    }
313}
libunseemly/util/asterism.rs

libunseemly/util/
asterism.rs
