#[derive(Copy, Clone)]
pub enum TraverseOrder {
  PreOrder,
  InOrder,
  PostOrder,
}

// Visit a node
pub trait Visitor<T> {
  fn visit(&mut self, t: &T);
}

pub trait Traversable<T> {
  fn traverse<V: Visitor<T>>(&self, order: TraverseOrder, visitor: &mut V);
}

pub struct TreeNode<T> {
  pub value: T,
  pub left: Option<Box<TreeNode<T>>>,
  pub right: Option<Box<TreeNode<T>>>,
}

#[cfg(test)]
mod test {
  use super::*;

  fn make_tree() -> TreeNode<u32> {
    //           5
    //     3            8
    //   2   4       6     9
    //  1              7
    return TreeNode {
      value: 5,
      left: Some(Box::new(TreeNode {
        value: 3,
        left: Some(Box::new(TreeNode {
          value: 2,
          left: Some(Box::new(TreeNode {
            value: 1,
            left: None,
            right: None,
          })),
          right: None,
        })),
        right: Some(Box::new(TreeNode {
          value: 4,
          left: None,
          right: None,
        })),
      })),
      right: Some(Box::new(TreeNode {
        value: 8,
        left: Some(Box::new(TreeNode {
          value: 6,
          left: None,
          right: Some(Box::new(TreeNode {
            value: 7,
            left: None,
            right: None,
          })),
        })),
        right: Some(Box::new(TreeNode {
          value: 9,
          left: None,
          right: None,
        })),
      })),
    }
  }

  fn make_tree_2() -> TreeNode<u32> {
    //        1
    //     2     4
    //   3         5
    return TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode {
                value: 3,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            value: 4,
            left: None,
            right: Some(Box::new(TreeNode {
                value: 5,
                left: None,
                right: None,
            })),
        })),
    }
  }

  struct CollectorVisitor<T> {
    pub values: Vec<T>,
  }

  impl<T: Clone> Visitor<T> for CollectorVisitor<T> {
    fn visit(&mut self, t: &T) {
      self.values.push(t.clone());
    }
  }

  impl<T> TreeNode<T> {
    fn traverse<V: Visitor<T>>(&self, order: TraverseOrder, visitor: &mut V) {
        match order {
            TraverseOrder::PreOrder => {
                visitor.visit(&self.value);
                match self.left.as_ref() {
                    Some(x) => x.traverse(TraverseOrder::PreOrder, visitor),
                    None => (),
                }
                match self.right.as_ref() {
                    Some(x) => x.traverse(TraverseOrder::PreOrder, visitor),
                    None => (),
                }
            }
            TraverseOrder::InOrder => {
                match self.left.as_ref() {
                    Some(x) => {
                        x.traverse(TraverseOrder::InOrder, visitor);
                    }
                    None => (),
                }
                visitor.visit(&self.value);
                match self.right.as_ref() {
                    Some(x) => {
                        x.traverse(TraverseOrder::InOrder, visitor);
                    }
                    None => (),
                }
            }
            TraverseOrder::PostOrder => {
                match self.left.as_ref() {
                    Some(x) => x.traverse(TraverseOrder::PostOrder, visitor),
                    None => (),
                }
                match self.right.as_ref() {
                    Some(x) => x.traverse(TraverseOrder::PostOrder, visitor),
                    None => (),
                }
                visitor.visit(&self.value);
            }
        }
    }
}

  #[test]
  fn test_pre_order() {
    let mut collector = CollectorVisitor { values: Vec::<u32>::new() };
    let tree = make_tree();
    tree.traverse(TraverseOrder::PreOrder, &mut collector);
    assert_eq!(collector.values, vec![5, 3, 2, 1, 4, 8, 6, 7, 9]);
  }

  #[test]
  fn test_in_order() {
    let mut collector = CollectorVisitor { values: Vec::<u32>::new() };
    let tree = make_tree();
    tree.traverse(TraverseOrder::InOrder, &mut collector);
    assert_eq!(collector.values, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
  }

  #[test]
  fn test_post_order() {
    let mut collector = CollectorVisitor { values: Vec::<u32>::new() };
    let tree = make_tree();
    tree.traverse(TraverseOrder::PostOrder, &mut collector);
    assert_eq!(collector.values, vec![1, 2, 4, 3, 7, 6, 9, 8, 5]);
  }

  #[test]
  fn test_pre_order_2() {
    let mut collector = CollectorVisitor { values: Vec::<u32>::new() };
    let tree = make_tree_2();
    tree.traverse(TraverseOrder::PreOrder, &mut collector);
    assert_eq!(collector.values, vec![1, 2, 3, 4, 5]);
  }

  #[test]
  fn test_in_order_2() {
    let mut collector = CollectorVisitor { values: Vec::<u32>::new() };
    let tree = make_tree_2();
    tree.traverse(TraverseOrder::InOrder, &mut collector);
    assert_eq!(collector.values, vec![3, 2, 1, 4, 5]);
  }

  #[test]
  fn test_post_order_2() {
    let mut collector = CollectorVisitor { values: Vec::<u32>::new() };
    let tree = make_tree_2();
    tree.traverse(TraverseOrder::PostOrder, &mut collector);
    assert_eq!(collector.values, vec![3, 2, 5, 4, 1]);
  }
}