use std::fmt::Display;



fn main() -> Result<(), Box<dyn std::error::Error>> {
    // println!("{}", 1_f32/q_rsqrt(16f32));

    let mut h = Node::new(5);
    let mut l0 = Node::new(3);
    let mut lr = Node::new(4);
    let mut r0 = Node::new(7);
    let mut rr = Node::new(8);
    h.left = Some(&mut l0);
    l0.right = Some(&mut lr);
    h.right = Some(&mut r0);
    r0.right = Some(&mut rr);


    let t = Tree::new(&mut h);
    t.trav_inord();
    Ok(())
}

#[allow(dead_code)]
fn q_rsqrt(num: f32) -> f32 {
    let x2  = num * 0.5_f32;
    let mut i = u32::from_le_bytes(num.to_le_bytes());
    i = 0x5f3759df - (i >> 1);
    let y = f32::from_le_bytes(i.to_le_bytes());
    y * (1.5_f32 - (x2 * y * y))
}


#[derive(Debug, Default)]
pub struct Node<T> {
    val: T,
    left: Option<*mut Node<T>>,
    right: Option<*mut Node<T>>,
}

impl<T> Node<T> {
    pub fn new(val: T) -> Self {
        Node {
            val,
            left: None,
            right: None,
        }
    }
}

impl <T> Drop for Node<T> {
    fn drop(&mut self) {
        let mut que = vec![self as *mut Node<T>];
        unsafe {
            while !que.is_empty() {
                let t = que.remove(0);
                if let Some(l) = (*t).left.take() {
                    que.push(l);
                }
                if let Some(r) = (*t).right.take() {
                    que.push(r);
                }
            }
        }
    }
}

#[derive(Debug, Default)]
pub struct Tree<T: Display> {
    inner: Option<*mut Node<T>>,
}

impl <T: Display> Tree<T> {
    pub fn new(head: &mut Node<T>) -> Self {
        Tree {
            inner: Some(head),
        }
    }
}

impl <T: Display> Tree<T> {
    pub fn trav_inord(&self) {
        let mut ptr = self.inner;
        let mut pre;
        unsafe {
            while let Some(r_ptr) = ptr {
                pre = (*r_ptr).left;
                if let Some(mut r_pre) = pre {
                    while (*r_pre).right.is_some() && !std::ptr::eq((*r_pre).right.unwrap(), r_ptr) {
                        r_pre = (*r_pre).right.unwrap();
                    }
                    match (*r_pre).right {
                        Some(_) => (*r_pre).right = None,
                        None => {
                            (*r_pre).right = Some(r_ptr);
                            ptr = (*r_ptr).left;
                            continue;
                        }
                    }
                }
                print!("{} -> ", (*r_ptr).val);
                ptr = (*r_ptr).right;
            }
        }
    }
}