// Binary Search Tree

// option1:

struct Cell0<T:Ord> {
   item : T,
   left : Option<Box<Cell0<T>>>,
   right : Option<Box<Cell0<T>>>,   
}

// option2 (adopted)

#[derive(Debug,Clone)]
enum Tree<T> {
  Empty,
  Node(Box<Cell<T>>),
}
#[derive(Debug,Clone)]
struct Cell<T> {
  item : T,
  left : Tree<T>,
  right: Tree<T>,
}
use Tree::*;

impl<T> Cell<T> {
  fn singleton(x:T) -> Self /* Cell<T> */ {
     Cell { item : x, left : Empty, right : Empty, }
  }
  fn new(x:T, a:Tree<T>, b:Tree<T>) -> Self {
     Cell { item : x, left : a, right : b, }
  }
}// impl Cell

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

  fn size(&self) -> usize {
    let mut counter = 0;
    self.inorder_map(&mut |_|{ counter+=1; });
    counter
  }//size

  fn depth(&self) -> usize {
    match self {
      Empty => 0,
      Node(cell) => {
        let dl = cell.left.depth();
	let dr = cell.right.depth();
	if dl>dr {dl+1} else {dr+1}
      }
    }//match
  }//depth

  fn insert(&mut self, x:T) -> bool {
    match self {
      Empty => { *self = Node(Box::new(Cell::singleton(x))); },
      Node(bxcell) => {
        if &x == &bxcell.item { return false; }
	if &x < &bxcell.item { bxcell.left.insert(x); }
	else { bxcell.right.insert(x); }
      },
    }//match
    true
  }//insert

  fn search(&self, x:&T) -> bool {
    match self {
      Empty => false,
      Node(cell) => {
        if x==&cell.item { true }
	else if x <&cell.item { cell.left.search(x) }
	else { cell.right.search(x) }
      },
    }//match
  }//search
  
} // impl Tree


///// implementing an in-order iterator

struct BstIter<'lt, T> {
  stack : Vec<&'lt Cell<T>>,
}
impl<'lt,T> BstIter<'lt,T> {
  fn new(root : &'lt Tree<T>) -> Self {
    let mut stack = Vec::new();
    let mut current = root;
    while let Node(cell) = current {
      stack.push(&**cell);
      current = &cell.left;
    }
    BstIter { stack }
  }//new
}

impl<'lt,T> Iterator for BstIter<'lt,T> {
   type Item = &'lt T;
   fn next(&mut self) -> Option<Self::Item> {
     let next = self.stack.pop()?;
     // must stack right nodes's left descendants
     let mut current = &next.right;
     while let Node(cell) = current {
       self.stack.push(&**cell);
       current = &cell.left;
     }
     Some(&next.item)
   }//next
}

impl<T> Tree<T> {
  fn iter<'lt>(&'lt self) -> BstIter<'lt,T> {
    BstIter::new(self)
  }
}

impl<'lt,T> IntoIterator for &'lt Tree<T> {
  type Item = &'lt T;
  type IntoIter = BstIter<'lt,T>;
  fn into_iter(self) -> Self::IntoIter {
    self.iter()
  }
}

fn main() {
 let mut tree = Empty;
 for x in [7,2,9,10,11,8,15,4,6,1] { tree.insert(x); }
 for x in &tree { println!("{}",x); }
 println!("size: {}", tree.size());
} // main