rust_fp_pfds/
tree.rs

1use std::rc::Rc;
2
3use crate::Set;
4use rust_fp_categories::Empty;
5
6#[derive(Debug, Clone, PartialEq, PartialOrd)]
7pub enum Tree<A> {
8    Empty,
9    Cons(Rc<Self>, A, Rc<Self>),
10}
11
12impl<A> Tree<A> {
13    pub fn single(value: A) -> Self {
14        Self::cons(Tree::Empty, value, Tree::Empty)
15    }
16
17    pub fn cons(left: Self, value: A, right: Self) -> Self {
18        Tree::Cons(Rc::new(left), value, Rc::new(right))
19    }
20}
21
22impl<A> Empty for Tree<A> {
23    fn empty() -> Self {
24        Tree::Empty
25    }
26
27    fn is_empty(&self) -> bool {
28        match self {
29            &Tree::Empty => true,
30            &Tree::Cons(..) => false,
31        }
32    }
33}
34
35impl<A: Clone + PartialEq + PartialOrd> Set<A> for Tree<A> {
36    fn insert(self, value: A) -> Self {
37        fn insert_to<A: Clone + PartialEq + PartialOrd>(x: A, s: &Tree<A>) -> Option<Tree<A>> {
38            match s {
39                &Tree::Empty => Some(Tree::cons(Tree::Empty, x, Tree::Empty)),
40                &Tree::Cons(ref a, ref y, ref b) => {
41                    if x < *y {
42                        insert_to(x, a)
43                            .map(|a: Tree<A>| Tree::Cons(Rc::new(a), y.clone(), b.clone()))
44                    } else if *y < x {
45                        insert_to(x, b)
46                            .map(|b: Tree<A>| Tree::Cons(a.clone(), y.clone(), Rc::new(b)))
47                    } else {
48                        None
49                    }
50                }
51            }
52        }
53        insert_to(value, &self).unwrap_or(self)
54    }
55
56    fn member(&self, value: A) -> bool {
57        fn member1<A: Clone + PartialEq + PartialOrd>(x: A, last: Option<A>, ss: &Tree<A>) -> bool {
58            match ss {
59                &Tree::Empty => last.iter().any(|y| x == *y),
60                &Tree::Cons(ref a, ref y, ref b) => {
61                    if x < *y {
62                        member1(x, last, a.as_ref())
63                    } else {
64                        member1(x, Some(y.clone()), b.as_ref())
65                    }
66                }
67            }
68        }
69        member1(value, None, self)
70    }
71
72    fn size(&self) -> usize {
73        match self {
74            &Tree::Empty => 0,
75            &Tree::Cons(ref a, _, ref b) => 1 + a.size() + b.size(),
76        }
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use crate::{Set, StackError, Tree};
83
84    #[test]
85    fn test_size() -> Result<(), StackError> {
86        assert_eq!(Tree::single(1).size(), 1);
87        Ok(())
88    }
89}
rust_fp_pfds/tree.rs

rust_fp_pfds/
tree.rs
