#![allow(unused)]

use std::iter::empty as empty_iter;
use std::iter::once;
use std::mem::{self};
use BST::*;

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

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

    // Associated Methods
    fn is_empty(&self) -> bool {
        if let Empty = self {
            true
        } else {
            false
        }
    }

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

    // Tree Traverslas
    fn pre_order_iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
        match self {
            Empty => Box::new(empty_iter()),
            Node { value, left, right } => Box::new(
                once(value)
                    .chain(left.pre_order_iter())
                    .chain(right.pre_order_iter()),
            ),
        }
    }

    fn in_order_iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
        match self {
            Empty => Box::new(empty_iter()),
            Node { value, left, right } => Box::new(
                left.in_order_iter()
                    .chain(once(value))
                    .chain(right.in_order_iter()),
            ),
        }
    }

    fn post_order_iter(&self) -> Box<dyn Iterator<Item = &T> + '_> {
        match self {
            Empty => Box::new(empty_iter()),
            Node { value, left, right } => Box::new(
                left.post_order_iter()
                    .chain(right.post_order_iter())
                    .chain(once(value)),
            ),
        }
    }

    // Tree Removal
    fn min_mut(&mut self) -> Option<&mut T> {
        match self {
            Empty => None,
            Node { value, left, .. } => {
                if left.is_empty() {
                    Some(value)
                } else {
                    left.min_mut()
                }
            }
        }
    }

    fn remove(&mut self, to_remove: &T) {
        match self {
            Empty => (),
            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) {
                        (Empty, Empty) => *self = Empty,
                        (_, Empty) => *self = mem::replace(&mut **left, Empty),
                        (Empty, _) => *self = mem::replace(&mut **right, Empty),
                        _ => {
                            mem::swap(value, right.min_mut().unwrap());
                            right.remove(to_remove);
                        }
                    }
                }
            }
        }
    }
}

fn main() {
    eprintln!();

    let mut bst = BST::leaf(5);
    bst.insert(8);
    bst.insert(2);
    bst.insert(3);
    bst.insert(1);
    bst.insert(6);
    bst.insert(9);
    bst.insert(7);

    bst.remove(&5);

    dbg!(&bst);

    for x in bst.in_order_iter() {
        println!("{}", x);
    }
}