1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

use std::rc::Rc;

use rust_fp_categories::*;
use rust_fp_categories::empty::Empty;
use rust_fp_categories::hkt::HKT;
use set::Set;

#[derive(Debug, PartialEq, PartialOrd)]
pub enum Tree<A> {
    Empty,
    Cons(Rc<Self>, A, Rc<Self>),
}

derive_hkt!(Tree);

impl<A> Tree<A> {

    fn cons(left: Self, value: A, right: Self) -> Self {
        Tree::Cons(Rc::new(left), value, Rc::new(right))
    }

}

impl<A> Empty for Tree<A> {

    fn empty() -> Self {
        Tree::Empty
    }

    fn is_empty(&self) -> bool {
        match self {
            &Tree::Empty => true,
            &Tree::Cons(..) => false,
        }
    }

}

impl<A: PartialEq + PartialOrd> Set<A> for Tree<A> {

    fn insert(self, value: A) -> Self {
        fn insert_to<A: PartialEq + PartialOrd>(
            x: A,
            s_arc: Rc<Tree<A>>,
        ) -> Option<Rc<Tree<A>>> {
            let s = Rc::try_unwrap(s_arc).unwrap_or(Tree::Empty);
            match s {
                Tree::Empty => Some(Rc::new(Tree::cons(Tree::Empty, x, Tree::Empty))),
                Tree::Cons(a, y, b) => {
                    if x < y {
                        insert_to(x, a).map(|a| Rc::new(Tree::Cons(a, y, b)))
                    } else if y < x {
                        insert_to(x, b).map(|b| Rc::new(Tree::Cons(a, y, b)))
                    } else {
                        None
                    }
                }
            }
        }
        let target = Rc::new(self);
        let default = Rc::clone(&target);
        let result = insert_to(value, target).unwrap_or(default);
        Rc::try_unwrap(result).unwrap_or(Tree::Empty)
    }

    fn member(self, value: A) -> bool {
        fn member1<A: PartialEq + PartialOrd>(
            x: A,
            last: Option<A>,
            ss_arc: Rc<Tree<A>>,
        ) -> bool {
            let ss = Rc::try_unwrap(ss_arc).unwrap_or(Tree::Empty);
            match ss {
                Tree::Empty => last.iter().any(|y| x == *y),
                Tree::Cons(a, y, b) => {
                    if x < y {
                        member1(x, last, a)
                    } else {
                        member1(x, Some(y), b)
                    }
                }
            }
        }
        member1(value, None, Rc::new(self))
    }
}

#[cfg(test)]
mod tests {
    use stack::StackError;

    #[test]
    fn test() -> Result<(), StackError> {
        Ok(())
    }
}