package cse1030;

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());
  }

}