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
97
98
99
100

use crate::flow::comparator::*;

#[derive(Clone)]
pub struct Bounds<A> {
    l: Option<A>,
    r: Option<A>,
}

#[derive(Debug)]
pub enum BoundsError<A> {
    BoundsViolated { l: A, r: A },
    OverflowL(A),
    OverflowR(A),
}

impl<A: Clone> Bounds<A> {
    pub fn unbound() -> Self {
        Bounds { l: None, r: None }
    }

    fn ordered(l: &A, r: &A, comparator: &impl Comparator<A>) -> Result<(), BoundsError<A>> {
        if let Comparison::R = comparator.compare(l, r) {
            Err(BoundsError::BoundsViolated {
                l: l.clone(),
                r: r.clone(),
            })
        } else {
            Ok(())
        }
    }

    fn orderedl(
        l: &Option<A>,
        r: &A,
        comparator: &impl Comparator<A>,
    ) -> Result<(), BoundsError<A>> {
        if let Some(l) = &l {
            Self::ordered(l, r, comparator)
        } else {
            Err(BoundsError::OverflowL(r.clone()))
        }
    }

    fn orderedr(
        l: &A,
        r: &Option<A>,
        comparator: &impl Comparator<A>,
    ) -> Result<(), BoundsError<A>> {
        if let Some(r) = &r {
            Self::ordered(l, r, comparator)
        } else {
            Err(BoundsError::OverflowR(l.clone()))
        }
    }

    fn new(
        l: Option<A>,
        r: Option<A>,
        comparator: &impl Comparator<A>,
    ) -> Result<Self, BoundsError<A>> {
        if let (Some(kl), Some(kr)) = (&l, &r) {
            Self::ordered(kl, kr, comparator)?
        }
        Ok(Bounds { l, r })
    }

    pub fn split(
        self,
        key: &A,
        comparator: &impl Comparator<A>,
    ) -> Result<(Self, Self), BoundsError<A>> {
        Ok((
            Self::new(self.l, Some(key.clone()), comparator)?,
            Self::new(Some(key.clone()), self.r, comparator)?,
        ))
    }

    pub fn join(
        l: Self,
        r: Self,
        key: &A,
        comparator: &impl Comparator<A>,
    ) -> Result<Self, BoundsError<A>> {
        Self::orderedl(&l.r, key, comparator)?;
        Self::orderedr(key, &r.l, comparator)?;
        Self::new(l.l, r.r, comparator)
    }

    fn equal_bound(l: &Option<A>, r: &Option<A>, comparator: &impl Comparator<A>) -> bool {
        match (l, r) {
            (None, None) => true,
            (Some(kl), Some(kr)) => comparator.equal(kl, kr),
            _ => false,
        }
    }

    pub fn equal(bl: &Self, br: &Self, comparator: &impl Comparator<A>) -> bool {
        Self::equal_bound(&bl.l, &br.l, comparator) && Self::equal_bound(&bl.r, &br.r, comparator)
    }
}