#![allow(unused)]

use std::iter::{empty as empty_iter, once};

#[derive(Debug, PartialEq)]
enum BST<T> {
    Empty,
    Node {
        value: T,
        left: Box<BST<T>>,
        right: Box<BST<T>>,
    }
}

impl<T: PartialOrd> BST<T> {
    /// Return leaf node
    fn leaf(value: T) -> Self {
        BST::Node{
            value,
            left: Box::new(BST::Empty),
            right: Box::new(BST::Empty),
        }
    }

    /// Associate function
    fn is_empty(&self) -> bool {
        match *self {
            BST::Empty => true,
            _ => false,
        }
    }

    /// Insert a node
    fn insert(&mut self, to_insert: T) {
        match self {
            BST::Empty => *self = BST::leaf(to_insert),
            BST::Node {value, left, right} => {
                if to_insert < *value {
                    left.insert(to_insert);
                } else {
                    right.insert(to_insert);
                }
            },
        }
    }

    /// in order
    fn in_order_iter(&'static self) -> Box<dyn Iterator<Item = &T>> {
        match self {
            BST::Empty => Box::new(empty_iter()) as Box<dyn Iterator<Item = &T>>,
            BST::Node { value, left, right } => Box::new(
                left.in_order_iter()
                    .chain(once(value))
                    .chain(right.in_order_iter())
            ) as Box<dyn Iterator<Item = &T>>,
        }
    }

    /// Get mutable min value ref
    fn min_mut(&mut self) -> Option<&mut T> {
        match self {
            BST::Empty => None,
            BST::Node {value, left, ..} => {
                if left.is_empty() {
                    Some(value)
                } else {
                    left.min_mut()
                }
            }
        }
    }

    /// remove
    fn remove(&mut self, to_remove: T) {
        match self {
            BST::Empty => {},
            BST::Node {value, left, right} => {
                if to_remove < *value {
                    left.remove(to_remove);
                } else if to_remove > *value {
                    right.remove(to_remove);
                } else {
                    match (&**left, &**right) {
                        (BST::Empty, BST::Empty) => (),
                        (_, BST::Empty) => *self = std::mem::replace(&mut **left, BST::Empty),
                        (BST::Empty, _) => *self = std::mem::replace(&mut **right, BST::Empty),
                        _ => {
                            std::mem::swap(value, right.min_mut().unwrap());
                            right.remove(to_remove);
                        }
                    }
                }
            }
        }
    }
}

fn main() {
    let root = BST::leaf(5);
    dbg!(root.is_empty());
    dbg!(root);
}