package cse1030.recursion;

import static org.junit.Assert.*;

import org.junit.Test;

public class BinarySearchTreeTest {

  /**
   * Tests the following tree one level at a time.
   *
   *                    M
   *                   / \
   *                  G   Q
   *                     / \
   *                    M   Q
   *                         \
   *                          R
   */
  @Test
  public void testAdd() {
    BinarySearchTree<String> t = new BinarySearchTree<String>();
    t.add("M");
    assertEquals("M", t.getRoot().data());
    assertEquals(null, t.getRoot().left());
    assertEquals(null, t.getRoot().right());
    
    t.add("G");
    assertEquals("M", t.getRoot().data());
    assertEquals("G", t.getRoot().left().data());
    assertEquals(null, t.getRoot().left().left());
    assertEquals(null, t.getRoot().left().right());
    assertEquals(null, t.getRoot().right());
    
    t.add("Q");
    assertEquals("M", t.getRoot().data());
    assertEquals("G", t.getRoot().left().data());
    assertEquals(null, t.getRoot().left().left());
    assertEquals(null, t.getRoot().left().right());
    assertEquals("Q", t.getRoot().right().data());
    assertEquals(null, t.getRoot().right().left());
    assertEquals(null, t.getRoot().right().right());
    
    t.add("M");
    assertEquals("M", t.getRoot().data());
    assertEquals("G", t.getRoot().left().data());
    assertEquals(null, t.getRoot().left().left());
    assertEquals(null, t.getRoot().left().right());
    assertEquals("Q", t.getRoot().right().data());
    assertEquals("M", t.getRoot().right().left().data());
    assertEquals(null, t.getRoot().right().right());
    
    t.add("Q");
    assertEquals("M", t.getRoot().data());
    assertEquals("G", t.getRoot().left().data());
    assertEquals(null, t.getRoot().left().left());
    assertEquals(null, t.getRoot().left().right());
    assertEquals("Q", t.getRoot().right().data());
    assertEquals("M", t.getRoot().right().left().data());
    assertEquals("Q", t.getRoot().right().right().data());
    
    t.add("R");
    assertEquals("M", t.getRoot().data());
    assertEquals("G", t.getRoot().left().data());
    assertEquals(null, t.getRoot().left().left());
    assertEquals(null, t.getRoot().left().right());
    assertEquals("Q", t.getRoot().right().data());
    assertEquals("M", t.getRoot().right().left().data());
    assertEquals("Q", t.getRoot().right().right().data());
    assertEquals("R", t.getRoot().right().right().right().data());
  }
  
  @Test
  public void testAddAscending() {
    BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
    Integer[] values = {1, 2, 3, 4, 5};
    for (Integer i : values) {
      t.add(i);
    }
    assertEquals(Integer.valueOf(1), t.getRoot().data());
    assertEquals(Integer.valueOf(2), t.getRoot().right().data());
    assertEquals(Integer.valueOf(3), t.getRoot().right().right().data());
    assertEquals(Integer.valueOf(4), t.getRoot().right().right().right().data());
    assertEquals(Integer.valueOf(5), t.getRoot().right().right().right().right().data());
  }
  
  @Test
  public void testAddDescending() {
    BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
    Integer[] values = {5, 4, 3, 2, 1};
    for (Integer i : values) {
      t.add(i);
    }
    assertEquals(Integer.valueOf(5), t.getRoot().data());
    assertEquals(Integer.valueOf(4), t.getRoot().left().data());
    assertEquals(Integer.valueOf(3), t.getRoot().left().left().data());
    assertEquals(Integer.valueOf(2), t.getRoot().left().left().left().data());
    assertEquals(Integer.valueOf(1), t.getRoot().left().left().left().left().data());
  }

  @Test
  public void testContains() {
    BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
    assertFalse(t.contains(1));
    
    Integer[] values = {50, 25, 75, 12, 37, 60, 55, 65};
    for (Integer i : values) {
      t.add(i);
    }
    for (Integer i : values) {
      assertTrue(t.contains(i));
      assertFalse(t.contains(i + 1));
    }
  }

  @Test
  public void testToString() {
    BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
    assertEquals("{}", t.toString());
    
    Integer[] values = {50, 25, 75, 12, 37, 60, 55, 65};
    for (Integer i : values) {
      t.add(i);
    }
    assertEquals("{12, 25, 37, 50, 55, 60, 65, 75}", t.toString());
  }
  
  /**
   * Uses the following tree.
   *
   *                    M
   *                   / \
   *                  G   Q
   *                     / \
   *                    N   R
   *                         \
   *                          S
   */
  @Test
  public void testMaximumInSubtree() {
	  BinarySearchTree<String> t = new BinarySearchTree<String>();
	    t.add("M");
	    t.add("G");
	    t.add("Q");
	    t.add("N");
	    t.add("R");
	    t.add("S");
	    
	  BinarySearchTree.Node<String> n = t.getRoot();
	  n = n.left();
	  assertEquals("G", BinarySearchTree.maximumInSubtree(n).data());
	  
	  n = t.getRoot();
	  n = n.right();
	  assertEquals("S", BinarySearchTree.maximumInSubtree(n).data());
  }
  
  @Test
  public void testMinimumInSubtree() {
	  BinarySearchTree<String> t = new BinarySearchTree<String>();
	    t.add("M");
	    t.add("G");
	    t.add("Q");
	    t.add("N");
	    t.add("R");
	    t.add("S");
	    
	  BinarySearchTree.Node<String> n = t.getRoot();
	  n = n.left();
	  assertEquals("G", BinarySearchTree.minimumInSubtree(n).data());
	  
	  n = t.getRoot();
	  n = n.right();
	  assertEquals("N", BinarySearchTree.minimumInSubtree(n).data());
  }

  @Test
  public void testPredecessorInSubtree() {
	  BinarySearchTree<String> t = new BinarySearchTree<String>();
	    t.add("M");
	    t.add("G");
	    t.add("Q");
	    t.add("N");
	    t.add("R");
	    t.add("S");
	    
	  BinarySearchTree.Node<String> n = t.getRoot();
	  n = n.left();
	  assertEquals(BinarySearchTree.predecessorInSubtree(n), null);
	  
	  n = t.getRoot();
	  n = n.right();
	  assertEquals(n.left(), BinarySearchTree.predecessorInSubtree(n));
  }
  
  
  @Test
  public void testSuccessorInSubtree() {
	  BinarySearchTree<String> t = new BinarySearchTree<String>();
	    t.add("M");
	    t.add("G");
	    t.add("Q");
	    t.add("N");
	    t.add("R");
	    t.add("S");
	    
	  BinarySearchTree.Node<String> n = t.getRoot();
	  n = n.left();
	  assertEquals(BinarySearchTree.successorInSubtree(n), null);
	  
	  n = t.getRoot();
	  n = n.right();
	  assertEquals(n.right(), BinarySearchTree.successorInSubtree(n));
  }
}