fingertrees/
tree.rs

1use self::Tree::{Deep, Empty, Single};
2use crate::digit::Digit;
3use crate::measure::Measured;
4use crate::monoid::Monoid;
5use crate::node::Node;
6use crate::reference::{Ref, Refs};
7
8/// Only visible to define custom [`Refs`](trait.Refs.html)
9pub struct TreeInner<R, V>
10where
11    R: Refs<V>,
12    V: Measured,
13{
14    pub(crate) measure: V::Measure,
15    pub(crate) left: Digit<Node<R, V>>,
16    pub(crate) spine: Tree<R, V>, //TODO: lazy spine
17    pub(crate) right: Digit<Node<R, V>>,
18}
19
20pub enum Tree<R, V>
21where
22    R: Refs<V>,
23    V: Measured,
24{
25    Empty,
26    Single(Node<R, V>),
27    Deep(R::Tree),
28}
29
30impl<R, V> Measured for Tree<R, V>
31where
32    R: Refs<V>,
33    V: Measured,
34{
35    type Measure = V::Measure;
36
37    fn measure(&self) -> Self::Measure {
38        match self {
39            Empty => Self::Measure::unit(),
40            Single(node) => node.measure(),
41            Deep(deep) => deep.measure.clone(),
42        }
43    }
44}
45
46impl<R, V> Clone for Tree<R, V>
47where
48    R: Refs<V>,
49    V: Measured,
50{
51    fn clone(&self) -> Self {
52        match self {
53            Empty => Empty,
54            Single(node) => Single(node.clone()),
55            Deep(deep) => Deep(deep.clone()),
56        }
57    }
58}
59
60impl<R, V> Tree<R, V>
61where
62    R: Refs<V>,
63    V: Measured,
64{
65    pub(crate) fn empty() -> Self {
66        Tree::Empty
67    }
68
69    pub(crate) fn single(node: Node<R, V>) -> Self {
70        Tree::Single(node)
71    }
72
73    pub(crate) fn deep(
74        left: Digit<Node<R, V>>,
75        spine: Tree<R, V>,
76        right: Digit<Node<R, V>>,
77    ) -> Self {
78        let measure = left.measure().join(&spine.measure()).join(&right.measure());
79        Tree::Deep(R::Tree::new(TreeInner {
80            measure,
81            left,
82            spine,
83            right,
84        }))
85    }
86
87    pub(crate) fn push_left(&self, value: Node<R, V>) -> Self {
88        match self {
89            Empty => Self::single(value),
90            Single(other) => Self::deep(
91                Digit::One([value]),
92                Self::empty(),
93                Digit::One([other.clone()]),
94            ),
95            Deep(deep) => {
96                if let [l0, l1, l2, l3] = deep.left.as_ref() {
97                    Self::deep(
98                        Digit::Two([value, l0.clone()]),
99                        deep.spine
100                            .push_left(Node::node3(l1.clone(), l2.clone(), l3.clone())),
101                        deep.right.clone(),
102                    )
103                } else {
104                    Self::deep(
105                        &Digit::One([value]) + &deep.left,
106                        deep.spine.clone(),
107                        deep.right.clone(),
108                    )
109                }
110            }
111        }
112    }
113
114    pub(crate) fn push_right(&self, value: Node<R, V>) -> Self {
115        match self {
116            Empty => Self::single(value),
117            Single(other) => Self::deep(
118                Digit::One([other.clone()]),
119                Self::empty(),
120                Digit::One([value]),
121            ),
122            Deep(deep) => {
123                if let [r0, r1, r2, r3] = deep.right.as_ref() {
124                    Self::deep(
125                        deep.left.clone(),
126                        deep.spine
127                            .push_right(Node::node3(r0.clone(), r1.clone(), r2.clone())),
128                        Digit::Two([r3.clone(), value]),
129                    )
130                } else {
131                    Self::deep(
132                        deep.left.clone(),
133                        deep.spine.clone(),
134                        &deep.right + Digit::One([value]),
135                    )
136                }
137            }
138        }
139    }
140
141    // left element is not `Digit` because `Digit` cannot be empty, but left in current
142    // position can be.
143    fn deep_left(left: &[Node<R, V>], spine: &Tree<R, V>, right: &Digit<Node<R, V>>) -> Self {
144        if left.is_empty() {
145            match spine.view_left() {
146                Some((head, tail)) => Self::deep((&head).into(), tail, right.clone()),
147                None => Tree::from(right),
148            }
149        } else {
150            Self::deep(left.into(), spine.clone(), right.clone())
151        }
152    }
153
154    pub(crate) fn view_left(&self) -> Option<(Node<R, V>, Self)> {
155        match self {
156            Empty => None,
157            Single(value) => Some((value.clone(), Tree::empty())),
158            Deep(deep) => match deep.left.as_ref().split_first() {
159                None => unreachable!("digit cannot be empty"),
160                Some((head, tail)) => Some((
161                    head.clone(),
162                    Self::deep_left(tail, &deep.spine, &deep.right),
163                )),
164            },
165        }
166    }
167
168    fn deep_right(left: &Digit<Node<R, V>>, spine: &Tree<R, V>, right: &[Node<R, V>]) -> Self {
169        if right.is_empty() {
170            match spine.view_right() {
171                Some((head, tail)) => Self::deep(left.clone(), tail, (&head).into()),
172                None => Tree::from(left),
173            }
174        } else {
175            Self::deep(left.clone(), spine.clone(), right.into())
176        }
177    }
178
179    pub(crate) fn view_right(&self) -> Option<(Node<R, V>, Self)> {
180        match self {
181            Empty => None,
182            Single(value) => Some((value.clone(), Tree::empty())),
183            Deep(deep) => match deep.right.as_ref().split_last() {
184                None => unreachable!("digit cannot be empty"),
185                Some((head, tail)) => Some((
186                    head.clone(),
187                    Self::deep_right(&deep.left, &deep.spine, tail),
188                )),
189            },
190        }
191    }
192
193    pub(crate) fn split<F>(
194        &self,
195        measure: V::Measure,
196        pred: &mut F,
197    ) -> (Tree<R, V>, Node<R, V>, Tree<R, V>)
198    where
199        F: FnMut(&V::Measure) -> bool,
200    {
201        match self {
202            Empty => unreachable!("recursive split of finger-tree called on empty tree"),
203            Single(value) => (Tree::empty(), value.clone(), Tree::empty()),
204            Deep(deep) => {
205                // left
206                let left_measure = measure.join(&deep.left.measure());
207                if pred(&left_measure) {
208                    let (l, x, r) = deep.left.split(measure, pred);
209                    return (
210                        Tree::from(l),
211                        x.clone(),
212                        Self::deep_left(r, &deep.spine, &deep.right),
213                    );
214                }
215                // spine
216                let spine_measure = left_measure.join(&deep.spine.measure());
217                if pred(&spine_measure) {
218                    let (sl, sx, sr) = deep.spine.split(left_measure.clone(), pred);
219                    let sx = Digit::from(&sx);
220                    let (l, x, r) = sx.split(left_measure.join(&sl.measure()), pred);
221                    return (
222                        Self::deep_right(&deep.left, &sl, l),
223                        x.clone(),
224                        Self::deep_left(r, &sr, &deep.right),
225                    );
226                }
227                // right
228                let (l, x, r) = deep.right.split(spine_measure, pred);
229                (
230                    Self::deep_right(&deep.left, &deep.spine, l),
231                    x.clone(),
232                    Tree::from(r),
233                )
234            }
235        }
236    }
237
238    pub(crate) fn split_left<F>(
239        &self,
240        measure: V::Measure,
241        pred: &mut F,
242    ) -> (Tree<R, V>, Node<R, V>)
243    where
244        F: FnMut(&V::Measure) -> bool,
245    {
246        match self {
247            Empty => unreachable!("recursive split of finger-tree called on empty tree"),
248            Single(value) => (Tree::empty(), value.clone()),
249            Deep(deep) => {
250                // left
251                let left_measure = measure.join(&deep.left.measure());
252                if pred(&left_measure) {
253                    let (l, x, _r) = deep.left.split(measure, pred);
254                    return (Tree::from(l), x.clone());
255                }
256                // spine
257                let spine_measure = left_measure.join(&deep.spine.measure());
258                if pred(&spine_measure) {
259                    let (sl, sx) = deep.spine.split_left(left_measure.clone(), pred);
260                    let sx = Digit::from(&sx);
261                    let (l, x, _r) = sx.split(left_measure.join(&sl.measure()), pred);
262                    return (Self::deep_right(&deep.left, &sl, l), x.clone());
263                }
264                // right
265                let (l, x, _r) = deep.right.split(spine_measure, pred);
266                (Self::deep_right(&deep.left, &deep.spine, l), x.clone())
267            }
268        }
269    }
270
271    pub(crate) fn split_right<F>(
272        &self,
273        measure: V::Measure,
274        pred: &mut F,
275    ) -> (V::Measure, Node<R, V>, Tree<R, V>)
276    where
277        F: FnMut(&V::Measure) -> bool,
278    {
279        match self {
280            Empty => unreachable!("recursive split of finger-tree called on empty tree"),
281            Single(value) => (measure, value.clone(), Tree::empty()),
282            Deep(deep) => {
283                // left
284                let left_measure = measure.join(&deep.left.measure());
285                if pred(&left_measure) {
286                    let (l, x, r) = deep.left.split(measure.to_owned(), pred);
287                    return (
288                        measure.join(&l.measure()),
289                        x.clone(),
290                        Self::deep_left(r, &deep.spine, &deep.right),
291                    );
292                }
293                // spine
294                let spine_measure = left_measure.join(&deep.spine.measure());
295                if pred(&spine_measure) {
296                    let (slm, sx, sr) = deep.spine.split_right(left_measure.clone(), pred);
297                    let sx = Digit::from(&sx);
298                    let (l, x, r) = sx.split(slm.to_owned(), pred);
299                    return (
300                        slm.join(&l.measure()),
301                        x.clone(),
302                        Self::deep_left(r, &sr, &deep.right),
303                    );
304                }
305                // right
306                let (l, x, r) = deep.right.split(spine_measure.to_owned(), pred);
307                (spine_measure.join(&l.measure()), x.clone(), Tree::from(r))
308            }
309        }
310    }
311
312    fn push_left_many(self, iter: &mut dyn Iterator<Item = Node<R, V>>) -> Self {
313        match iter.next() {
314            None => self,
315            Some(node) => self.push_left_many(iter).push_left(node),
316        }
317    }
318
319    fn push_right_many(self, iter: &mut dyn Iterator<Item = Node<R, V>>) -> Self {
320        match iter.next() {
321            None => self,
322            Some(node) => self.push_right(node).push_right_many(iter),
323        }
324    }
325
326    pub(crate) fn concat(
327        left: &Self,
328        mid: &mut dyn Iterator<Item = Node<R, V>>,
329        right: &Self,
330    ) -> Self {
331        match (left, right) {
332            (Empty, _) => right.clone().push_left_many(mid),
333            (_, Empty) => left.clone().push_right_many(mid),
334            (Single(left), _) => right.clone().push_left_many(mid).push_left(left.clone()),
335            (_, Single(right)) => left.clone().push_right_many(mid).push_right(right.clone()),
336            (Deep(deep0), Deep(deep1)) => {
337                let left = deep0.right.as_ref().iter().cloned();
338                let right = deep1.left.as_ref().iter().cloned();
339                Self::deep(
340                    deep0.left.clone(),
341                    Self::concat(
342                        &deep0.spine,
343                        &mut Node::lift(left.chain(mid).chain(right)),
344                        &deep1.spine,
345                    ),
346                    deep1.right.clone(),
347                )
348            }
349        }
350    }
351
352    pub(crate) fn find<F>(&self, measure: V::Measure, pred: &mut F) -> &V
353    where
354        F: FnMut(&V::Measure) -> bool,
355    {
356        match self {
357            Empty => unreachable!("recursive find of finger-tree called on empty tree"),
358            Single(value) => value.find(measure, pred),
359            Deep(deep) => {
360                // left
361                let left_measure = measure.join(&deep.left.measure());
362                if pred(&left_measure) {
363                    let (measure, node) = deep.left.find(measure, pred);
364                    return node.find(measure, pred);
365                }
366                // spine
367                let spine_measure = left_measure.join(&deep.spine.measure());
368                if pred(&spine_measure) {
369                    return deep.spine.find(left_measure, pred);
370                }
371                // right
372                let (measure, node) = deep.right.find(spine_measure, pred);
373                node.find(measure, pred)
374            }
375        }
376    }
377}
378
379impl<R, T, V> From<T> for Tree<R, V>
380where
381    R: Refs<V>,
382    T: AsRef<[Node<R, V>]>,
383    V: Measured,
384{
385    fn from(slice: T) -> Self {
386        slice
387            .as_ref()
388            .iter()
389            .fold(Tree::empty(), |ft, v| ft.push_right(v.clone()))
390    }
391}
392
393pub(crate) fn build<R, V>(nodes: &mut [Node<R, V>]) -> Tree<R, V>
394where
395    R: Refs<V>,
396    V: Measured,
397{
398    match nodes {
399        [] => Tree::empty(),
400        [n] => Tree::single(n.clone()),
401        [n0, n1] => Tree::deep(
402            Digit::One([n0.clone()]),
403            Tree::empty(),
404            Digit::One([n1.clone()]),
405        ),
406        [n0, n1, n2] => Tree::deep(
407            Digit::Two([n0.clone(), n1.clone()]),
408            Tree::empty(),
409            Digit::One([n2.clone()]),
410        ),
411        [n0, n1, n2, n3] => Tree::deep(
412            Digit::Two([n0.clone(), n1.clone()]),
413            Tree::empty(),
414            Digit::Two([n2.clone(), n3.clone()]),
415        ),
416        [n0, n1, n2, n3, n4] => Tree::deep(
417            Digit::Three([n0.clone(), n1.clone(), n2.clone()]),
418            Tree::empty(),
419            Digit::Two([n3.clone(), n4.clone()]),
420        ),
421        [n0, n1, n2, n3, n4, n5] => Tree::deep(
422            Digit::Three([n0.clone(), n1.clone(), n2.clone()]),
423            Tree::empty(),
424            Digit::Three([n3.clone(), n4.clone(), n5.clone()]),
425        ),
426        [n0, n1, n2, n3, n4, n5, n6] => Tree::deep(
427            Digit::Four([n0.clone(), n1.clone(), n2.clone(), n3.clone()]),
428            Tree::empty(),
429            Digit::Three([n4.clone(), n5.clone(), n6.clone()]),
430        ),
431        [n0, n1, n2, n3, n4, n5, n6, n7] => Tree::deep(
432            Digit::Four([n0.clone(), n1.clone(), n2.clone(), n3.clone()]),
433            Tree::empty(),
434            Digit::Four([n4.clone(), n5.clone(), n6.clone(), n7.clone()]),
435        ),
436        [n0, n1, n2, n3, n4, n5, n6, n7, n8] => Tree::deep(
437            Digit::Four([n0.clone(), n1.clone(), n2.clone(), n3.clone()]),
438            Tree::single(Node::node2(n4.clone(), n5.clone())),
439            Digit::Three([n6.clone(), n7.clone(), n8.clone()]),
440        ),
441        _ => {
442            let mut start = 4;
443            let end = nodes.len() - 4;
444            let left = Digit::from(&nodes[..start]);
445            let right = Digit::from(&nodes[end..]);
446            // lift nodes in-place
447            let mut offset = 0;
448            loop {
449                match end - start {
450                    0 => break,
451                    1 => unreachable!(),
452                    2 => {
453                        let node = Node::node2(nodes[start].clone(), nodes[start + 1].clone());
454                        nodes[offset] = node;
455                        start += 2;
456                        offset += 1;
457                    }
458                    4 => {
459                        let n0 = Node::node2(nodes[start].clone(), nodes[start + 1].clone());
460                        let n1 = Node::node2(nodes[start + 2].clone(), nodes[start + 3].clone());
461                        nodes[offset] = n0;
462                        nodes[offset + 1] = n1;
463                        start += 4;
464                        offset += 2;
465                    }
466                    _ => {
467                        let node = Node::node3(
468                            nodes[start].clone(),
469                            nodes[start + 1].clone(),
470                            nodes[start + 2].clone(),
471                        );
472                        nodes[offset] = node;
473                        start += 3;
474                        offset += 1;
475                    }
476                }
477            }
478            Tree::deep(left, build(&mut nodes[..offset]), right)
479        }
480    }
481}
fingertrees/tree.rs

fingertrees/
tree.rs
