#[derive(Debug)]
struct Interval {
    lower: i32,
    upper: i32,
}

impl Interval {
    fn single(lower: i32) -> Interval {
        Interval { lower: lower, upper: lower }
    }

    fn new(lower: i32, upper: i32) -> Interval {
        assert!(lower <= upper);
        Interval { lower: lower, upper: upper }
    }

    fn in_range(&self, item: i32) -> bool {
        self.lower <= item && item <= self.upper
    }
}

type SplitResult = (i32, Option<Box<Node>>);

#[derive(Debug)]
struct Node {
    left: Option<Box<Node>>,
    value: Interval,
    right: Option<Box<Node>>,
}

impl Node {
    fn single(v : i32) -> Node {
        Node { left: None, value: Interval::single(v), right: None }
    }

    fn contains(&self, item: i32) -> bool {
        if self.value.in_range(item) {
            true
        } else if item < self.value.lower {
            self.left.as_ref().map_or(false, |v| v.contains(item))
        } else {
            self.right.as_ref().map_or(false, |v| v.contains(item))
        }
    }

    fn split_max(self) -> SplitResult {
        if let Some(node) = self.right {
            let (u, r_) = node.split_max();
            (u, Some(Box::new(Node { right: r_, ..self })))
        } else {
            (self.value.lower, self.left)
        }
    }

    fn possible_split_max(&self) -> i32 {
        if let Some(ref node) = self.right {
            node.possible_split_max()
        } else {
            self.value.upper
        }
    }

    fn join_left(&mut self) {
        if self.left.is_none() {
            return;
        }

        let y_ = self.left.as_ref().unwrap().possible_split_max();
        if y_ + 1 == self.value.lower {
            let (x_, l_) = self.left.take().unwrap().split_max();
            self.value.lower = x_;
            self.left = l_;
        }
    }

    fn split_min(self) -> SplitResult {
        if let Some(node) = self.left {
            let (v, l_) = node.split_min();
            (v, Some(Box::new(Node { left: l_, ..self })))
        } else {
            (self.value.upper, self.right)
        }
    }

    fn possible_split_min(&self) -> i32 {
        if let Some(ref node) = self.left {
            node.possible_split_min()
        } else {
            self.value.lower
        }
    }

    fn join_right(&mut self) {
        if self.right.is_none() {
            return;
        }

        let x_ = self.right.as_ref().unwrap().possible_split_min();
        if x_ - 1 == self.value.upper {
            let (y_, r_) = self.right.take().unwrap().split_min();
            self.value.upper = y_;
            self.right = r_;
        }
    }

    fn insert(&mut self, new_item: i32) {
        match new_item {
            k if k == self.value.lower - 1 => {
                self.value.lower = k;
                self.join_left();
            },
            k if k == self.value.upper + 1 => {
                self.value.upper = k;
                self.join_right();
            },
            k if k < self.value.lower => {
                Node::insert_or_create(&mut self.left, k);
            },
            k if k > self.value.upper => {
                Node::insert_or_create(&mut self.right, k);
            },
            _ => {
                assert!(self.value.in_range(new_item));
            }
        }
    }

    fn insert_or_create(node: &mut Option<Box<Node>>, new_item: i32) {
        if let Some(ref mut node) = *node {
            node.insert(new_item);
        } else {
            *node = Some(Box::new(Node::single(new_item)));
        }
    }

    fn maybe_delete(opt_node: &mut Option<Box<Self>>, item: i32) {
        let mut delete_node = false;
        if let Some(ref mut node) = *opt_node {
            if item < node.value.lower {
                Node::maybe_delete(&mut node.left, item);
            } else if item > node.value.upper {
                Node::maybe_delete(&mut node.right, item);
            } else if item == node.value.lower {
                if item == node.value.upper {
                    match (node.left.take(), node.right.take()) {
                        (None, None) => {
                            delete_node = true;
                        },
                        (Some(left), None) => {
                            *node = left;
                        },
                        (None, Some(right)) => {
                            *node = right;
                        }
                        (Some(left), Some(right)) => {
                            let y = left.possible_split_max();
                            let (x, l_) = left.split_max();
                            node.value.lower = x;
                            node.value.upper = y;
                            node.left = l_;
                            node.right = Some(right);
                        }
                    }
                } else {
                    node.value.lower += 1;
                }
            } else if item == node.value.upper {
                node.value.upper -= 1;
            } else {
                let right_value = Interval::new(item + 1, node.value.upper);
                node.value.upper = item - 1;
                let right = node.right.take();
                node.right = Some(Box::new(Node { left: None, right: right, value: right_value }));
            }
        }

        if delete_node {
            opt_node.take();
        }
    }
}

#[derive(Debug)]
pub struct Diet {
    root: Option<Box<Node>>,
}

impl Diet {
    pub fn new() -> Diet {
        Diet { root: None }
    }

    pub fn contains(&self, item: i32) -> bool {
        self.root.as_ref().map_or(false, |v| v.contains(item))
    }

    pub fn insert(&mut self, new_item: i32) -> () {
        Node::insert_or_create(&mut self.root, new_item);
    }

    pub fn delete(&mut self, item: i32) -> () {
        Node::maybe_delete(&mut self.root, item);
    }
}

#[cfg(test)]
mod test {
    use super::{Interval,Node,Diet};

    #[test]
    fn test_interval() {
        Interval::new(3, 4);
    }

    #[test]
    #[should_panic]
    fn test_bad_interval() {
        Interval::new(4, 4);
        Interval::new(4, 3);
    }

    #[test]
    fn test_node() {
        let i = Interval::new(4, 5);
        let r = Box::new(Node::single(7));

        let node = Node { left: None, value: i, right: Some(r) };
        assert!(node.contains(4));
        assert!(node.contains(5));
        assert!(node.contains(7));
        assert!(!node.contains(6));
        assert!(!node.contains(3));

        let i2 = Interval::new(4, 5);
        let l = Box::new(Node::single(0));

        let node2 = Node { left: Some(l), value: i2, right: None };
        assert!(node2.contains(4));
        assert!(node2.contains(5));
        assert!(!node2.contains(7));
        assert!(!node2.contains(6));
        assert!(!node2.contains(3));
        assert!(node2.contains(0));
    }

    #[test]
    fn test_diet_basic() {
        let mut d = Diet::new();
        assert!(!d.contains(5));

        d.insert(5);
        assert!(d.contains(5));

        d.insert(3);
        assert!(d.contains(3));

        d.insert(4);
        assert!(d.contains(4));

        {
            let b = d.root.as_ref().unwrap();
            assert!(b.left.is_none());
            assert!(b.right.is_none());
            assert!(b.value.lower == 3);
            assert!(b.value.upper == 5);
        }

        d.insert(7);
        assert!(d.contains(7));
        assert!(!d.contains(6));
        d.insert(6);

        assert!(d.contains(6));
        {
            let b = &d.root.unwrap();
            assert!(b.left.is_none());
            assert!(b.right.is_none());
            assert!(b.value.lower == 3);
            assert!(b.value.upper == 7);
        }
    }

    #[test]
    fn test_delete_simple() {
        let mut d = Diet::new();
        d.delete(5);
        d.insert(5);
        assert!(d.contains(5));
        d.delete(5);
        assert!(!d.contains(5));
    }

    #[test]
    fn test_delete_branch() {
        let mut d = Diet::new();
        d.insert(5);
        d.insert(3);
        d.insert(7);

        d.delete(3);
        assert!(!d.contains(3));
        assert!(d.contains(5));
        assert!(d.contains(7));

        d.delete(7);
        assert!(d.contains(5));
    }

    #[test]
    fn test_delete_replace_merge() {
        let mut d = Diet::new();
        d.insert(5);
        d.insert(3);

        d.delete(5);
        assert!(!d.contains(5));
        assert!(d.contains(3));

        d.insert(7);
        d.delete(3);
        assert!(!d.contains(3));
        assert!(d.contains(7));
    }

    #[test]
    fn test_delete_lower_upper() {
        let mut d = Diet::new();
        d.insert(5);
        d.insert(6);
        d.insert(7);

        d.delete(5);
        assert!(d.contains(6));
        assert!(d.contains(7));

        d.delete(7);
        assert!(d.contains(6));
    }

    #[test]
    fn test_delete_merge() {
        unimplemented!();
    }

    #[test]
    fn test_delete_split_left() {
        let mut d = Diet::new();
        d.insert(8);
        d.insert(9);
        d.insert(10);

        d.insert(2);
        d.insert(4);
        d.insert(6);
        d.insert(14);
        d.insert(12);
        d.insert(16);

        d.delete(8);
        d.delete(9);
        d.delete(10);

        assert!(d.contains(2));
        assert!(d.contains(4));
        assert!(d.contains(6));
        assert!(d.contains(14));
        assert!(d.contains(12));
        assert!(d.contains(16));
    }
}
