// AVL balanced binary search trees
#![allow(dead_code, non_snake_case, unused_variables)]

/*
Alternative representation:
struct Node<T> {
  item : T,
  left : Option<Box<Node<T>>>,
  right : Option<Box<Node<T>>>, 
}
*/

pub enum Tree<T> {
  Empty,
  Node(Box<Cell<T>>),
}
use Tree::*; 

pub struct Cell<T> {
  item : T,
  left : Tree<T>,
  right: Tree<T>,
  height: u8, // 2**255 cells is a very large tree!
}

impl<T:Ord> Tree<T> {
  pub fn new_node(x:T) -> Self {
    Node( Box::new(Cell{ item: x, left:Empty, right:Empty, height:1}) )
  }//new singleton node

  fn insert(&mut self, x:T) -> bool { // false if duplicate
    let mut current = self;
    while let Node(bxcell) = current {
      if &x == &bxcell.item { return false; }
      else if &x < &bxcell.item { current = &mut bxcell.left; }
      else { current = &mut bxcell.right; }
    }
    *current = Self::new_node(x);
    true
  }//insert - non recursive  --- DOES NOT SELF-BALANCE!

  fn add(&mut self, x:T) -> bool {  //recursive insert
    match self {
      Empty => {
        *self = Self::new_node(x);
	true
      },
      Node(bxcell) => {
        if &x == &bxcell.item { false }
	else if &x < &bxcell.item {
	  let result = bxcell.left.add(x);
	  if result { self.adjust(); }
	  result
	}
	else {
	  let result = bxcell.right.add(x);
	  if result { self.adjust(); }
	  result
        }
      },
    }//match
  }//add - recursive

  fn search(&self, x:&T) -> bool {
    let mut current = self;
    while let Node(bxcell) = current {
      if x == &bxcell.item { return true; }
      else if x < &bxcell.item { current = &bxcell.left; }
      else { current = &bxcell.right; }
    }
    false
  }// search - non-recursive

  fn contains(&self, x:&T) -> bool { // recursive
    match self {
      Empty => false,
      Node(bxcell) => {
        x==&bxcell.item || (x<&bxcell.item && bxcell.left.contains(x))
	                || (x>&bxcell.item && bxcell.right.contains(x))
      },
    }//match
  }//contains

  pub fn size(&self) -> usize {
    if let Node(bc) = self { 1 + bc.left.size() + bc.right.size() }
    else { 0 }
  }//size

  pub fn inorder_map<F:FnMut(&T)>(&self, mapfun:&mut F) {
    match self {
      Empty => {},
      Node(bxcell) => {
	bxcell.left.inorder_map(mapfun);
        mapfun(&bxcell.item);
	bxcell.right.inorder_map(mapfun);
      }
    }//match
  }//inorder_map


// recursive remove
pub fn remove(&mut self, x:&T) -> bool {  // false if x not found
  match self {
    Empty => { false },
    Node(cell) => {
      if x < &cell.item {
        let result = cell.left.remove(x);
        self.adjust();
	result
      }
      else if x > &cell.item {
        let result = cell.right.remove(x);
	self.adjust();
	result
      }
      else { // found x
        // check if left subtree is empyt
	if let Empty = &cell.left { // move right subtree to self
	  //*self = cell.right;  // won't compile
	  let mut temp = Empty;
	  std::mem::swap(&mut temp, &mut cell.right);
	  *self = temp;
	}
	else {  // call auxiliary procedure to delete max on left subtree
	  cell.item = cell.left.delmax();
	}
	self.adjust();
        true
      } // found x
    },
  }//match
}//remove

fn delmax(&mut self) -> T { // auxiliary to remove
  if let Node(cell) = self {
    if let &Empty = &cell.right {
      let mut left0 = Empty;
      std::mem::swap(&mut left0, &mut cell.left);
      let mut self0 = Empty;
      std::mem::swap(&mut self0, self);
      *self = left0;
      if let Node(bc) = self0 { return bc.item; }
      else {panic!("this should not happen");}
    }
    else {
      let result = cell.right.delmax();
      self.adjust();
      result
    }
  }
  else { panic!("this should never happen"); }
}//delmax

// O(n) depth
fn depth(&self) -> usize {
  match self {
    Empty => 0,
    Node(cell) => std::cmp::max(cell.left.depth(),cell.right.depth())+1,
  }
}//depth (recursive)

// O(1) depth
fn get_height(&self) -> u8 {
  if let Node(cell) = self { cell.height }
  else { 0 }
}//get_height

fn height_balance(&self) -> i8 {
  match self {
    Empty => 0,
    Node(cell) => cell.left.get_height() as i8 - cell.right.get_height() as i8,
  }//match
}//height_balance

// setheight, also returns height balance. O(1) operation.
fn set_height(&mut self) -> i8 {
  match self {
    Empty => 0,
    Node(cell) => {
      let hl = cell.left.get_height();
      let hr = cell.right.get_height();
      cell.height = std::cmp::max(hl,hr)+1;
      hl as i8 - hr as i8 // returns height difference
    },
  }//match
}//set_height

// basic rotations
fn LL(&mut self) {
  let Node(scell) = self else {return};
  let Node(lcell) = &mut scell.left else {return};
  std::mem::swap(&mut scell.item, &mut lcell.item);
  std::mem::swap(&mut lcell.left, &mut lcell.right); // lr now in place
  std::mem::swap(&mut lcell.right, &mut scell.right); // r now in place
  std::mem::swap(&mut scell.left, &mut scell.right);  
  scell.right.set_height();
  self.set_height();
}// LL

fn RR(&mut self) {
  let Node(scell) = self else {return};
  let Node(rcell) = &mut scell.right else {return};
  std::mem::swap(&mut scell.item, &mut rcell.item);
  std::mem::swap(&mut rcell.right, &mut rcell.left);
  std::mem::swap(&mut rcell.left, &mut scell.left);
  std::mem::swap(&mut scell.left, &mut scell.right);
  scell.left.set_height();
  self.set_height();
}// RR

fn adjust(&mut self) {
  let hb = self.set_height(); // get hight balance
  if hb > 1 { // left side too high
    // check height balance on left node
    let Node(scell) = self else {return};
    if scell.left.height_balance() < 0 { scell.left.RR(); } //double rotation
    self.LL();
  }
  else if hb < -1 { // right side too high
    let Node(scell) = self else {return};
    if scell.right.height_balance() > 0 { scell.right.LL(); }
    self.RR();
  }
}//adjust

}// main impl for Tree

fn main() {
  let mut tree:Tree<i32> = Tree::new_node(9);
  for x in [2,4,8,10,2,3,6,90,1,34,5] { tree.insert(x); }
  println!("size {}", tree.size());
  tree.inorder_map(&mut |x|{print!("{} ",x);} );  println!();
  tree.remove(&10);
  tree.remove(&3);
  tree.insert(7);
  tree.insert(11);
  tree.insert(3);
  tree.remove(&7);
  println!("size after removes {}", tree.size());
  tree.inorder_map(&mut |x|{print!("{} ",x);} );  println!();

  tree = Tree::new_node(0);
  for i in 0..10000000 { tree.add(i); }
  println!("new tree size {}",tree.size());
  println!("depth {}",tree.depth());
  println!("height {}",tree.get_height());  
} //main