package dictionary;

import static org.junit.Assert.assertEquals;

import java.util.Comparator;

import org.junit.Before;
import org.junit.Test;

public class RBTreeWParentDictionaryTest {
  private class IntegerComparator implements Comparator<Integer> {
    public int compare(Integer i1, Integer i2) {
      return i1.compareTo(i2);
    }
  }

  RBTreeWParentDictionary<Integer, String> startRBT;
  IntegerComparator                        comparator;

  @Before
  public void setUp() {
    comparator = new IntegerComparator();
    startRBT = new RBTreeWParentDictionary<Integer, String>(comparator);

    startRBT.root = new RBTreeWParentNode<Integer, String>(10, "10");
    startRBT.root.setBlack();
  }

/*
 * Used for first tests, now removed.
  @Test
  public void rotateLeftTest() {
    startRBT.root.setRed();
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(30, "30"));
    startRBT.root.getRight()
        .setRight(new RBTreeWParentNode<Integer, String>(40, "40"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.root = new RBTreeWParentNode<Integer, String>(30, "30");
    testRbt.root.setRed();
    testRbt.root.setLeft(new RBTreeWParentNode<Integer, String>(10, "10"));
    testRbt.root.setRight(new RBTreeWParentNode<Integer, String>(40, "40"));

    startRBT.testRotateLeft();
    assertEquals(startRBT, testRbt);

  }

  @Test
  public void rotateRightTest() {
    startRBT.root.setRed();
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(9, "9"));
    startRBT.root.getLeft()
        .setLeft(new RBTreeWParentNode<Integer, String>(8, "8"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.root = new RBTreeWParentNode<Integer, String>(9, "9");
    testRbt.root.setRed();
    testRbt.root.setLeft(new RBTreeWParentNode<Integer, String>(8, "8"));
    testRbt.root.setRight(new RBTreeWParentNode<Integer, String>(10, "10"));

    startRBT.testRotateRight();
    assertEquals(startRBT, testRbt);
  }*/

  // Testing case -1
  @Test
  public void testInsertInRoot() {
    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");

    assertEquals(startRBT, testRbt);
  }

  // Testing case 0
  @Test
  public void testInsertLeft() {
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(1, "1"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(1, "1");

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testInsertRight() {
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(30, "30"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(30, "30");

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testInsertTwoSons() {
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(30, "30"));
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(1, "1"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(30, "30");
    testRbt.insert(1, "1");

    assertEquals(startRBT, testRbt);
  }

  // Testing case 1
  public void testInsertLeftNephew() {
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(30, "30"));
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(5, "5"));
    startRBT.root.getLeft().setBlack();
    startRBT.root.getRight().setBlack();
    startRBT.root.getLeft()
        .setLeft(new RBTreeWParentNode<Integer, String>(4, "4"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(30, "30");
    testRbt.insert(5, "5");
    testRbt.insert(4, "4");

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testInsertRightNephew() {
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(30, "30"));
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(5, "5"));
    startRBT.root.getLeft().setBlack();
    startRBT.root.getRight().setBlack();
    startRBT.root.getRight()
        .setRight(new RBTreeWParentNode<Integer, String>(35, "35"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(30, "30");
    testRbt.insert(5, "5");
    testRbt.insert(35, "35");

    assertEquals(startRBT, testRbt);
  }

  // Testing case 2
  @Test
  public void testInsertLeftNephewLeftNoUncle() {
    startRBT.root.setKey(5);
    startRBT.root.setValue("5");
    startRBT.root.setBlack();
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(2, "2"));
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(10,"10"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(5, "5");
    testRbt.insert(2, "2");

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testInsertRightNephewRightNoUncle() {
    startRBT.root.setKey(20);
    startRBT.root.setValue("20");
    startRBT.root.setBlack();
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(10, "10"));
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(30,"30"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(20, "20");
    testRbt.insert(30, "30");

    assertEquals(startRBT, testRbt);
  }

  // Testing case 3
  @Test
  public void testInsertLeftNephewRightNoUncle() {
    startRBT.root.setKey(5);
    startRBT.root.setValue("5");
    startRBT.root.setBlack();
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(3, "3"));
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(10,"10"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(3, "3");
    testRbt.insert(5, "5");

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testInsertRightNephewLeftNoUncle() {
    startRBT.root.setKey(15);
    startRBT.root.setValue("15");
    startRBT.root.setBlack();
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(10, "10"));
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(20,"20"));

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(20, "20");
    testRbt.insert(15, "15");

    assertEquals(startRBT, testRbt);
  }

  /*
   * Testing deletion
   */
  @Test
  public void testDeleteRoot() {
    startRBT.root = null;

    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.delete(10);

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testDeleteLeftChildLeaf() {
    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(1, "1");
    testRbt.delete(1);

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testDeleteRightChildLeaf() {
    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(100, "100");
    testRbt.delete(100);

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testDeleteLeftChild() {
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(3, "3"));
    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(5, "5");
    testRbt.root.getLeft().setLeft(new RBTreeWParentNode<Integer, String>(3, "3"));
    testRbt.delete(5);

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testDeleteRightChild() {
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(20, "20"));
    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(15, "15");
    testRbt.root.getRight().setRight(new RBTreeWParentNode<Integer, String>(20, "20"));
    testRbt.delete(15);

    assertEquals(startRBT, testRbt);
  }

  @Test
  public void testDeleteDoubles() {
    startRBT.root.setRight(new RBTreeWParentNode<Integer, String>(100, "100"));
    startRBT.root.getRight().setBlack();
    startRBT.root.setLeft(new RBTreeWParentNode<Integer, String>(6, "6"));
    startRBT.root.getLeft().setRed();
    startRBT.root.getLeft().setLeft(new RBTreeWParentNode<Integer, String>(5, "5"));
    startRBT.root.getLeft().getLeft().setBlack();
    startRBT.root.getLeft().setRight(new RBTreeWParentNode<Integer, String>(9, "9"));
    startRBT.root.getLeft().getRight().setBlack();
    startRBT.root.getLeft().getLeft().setLeft(new RBTreeWParentNode<Integer, String>(2, "2"));
    RBTreeWParentDictionary<Integer, String> testRbt = new RBTreeWParentDictionary<Integer, String>(
        comparator);
    testRbt.insert(10, "10");
    testRbt.insert(100, "100");
    testRbt.insert(8, "8");
    testRbt.insert(5, "5");
    testRbt.insert(9, "9");
    testRbt.insert(2, "2");
    testRbt.insert(6, "6");
    testRbt.delete(8);
    assertEquals(startRBT, testRbt);
  }
}