import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Iterator;

import org.junit.AfterClass;
import org.junit.Test;

public class Testing {
    private static int points = 0;


    ////////// Testing insertion
    @Test
    public void testSplits(){
	AATree<Integer> a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);
	a.insert(5);
	a.insert(6);
	a.insert(7);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(4);
	values.add(2);
	values.add(1);
	values.add(3);
	values.add(6);
	values.add(5);
	values.add(7);
	levels.add(3);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}
	points += 8;
    }

    @Test
    public void testSkewsandSplits(){
	AATree<Integer> a = new AATree<Integer>();
	a.insert(7);
	a.insert(6);
	a.insert(5);
	a.insert(4);
	a.insert(3);
	a.insert(2);
	a.insert(1);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(4);
	values.add(2);
	values.add(1);
	values.add(3);
	values.add(6);
	values.add(5);
	values.add(7);
	levels.add(3);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}
	points += 7;
    }

    public void nums(int lower, int upper, Iterator<AATree<Integer>.BinaryNode> i){
	if (lower > upper) return;
	int mid = (lower + upper)/2;
	assertEquals(new Integer(mid), i.next().getElement());
	nums(lower, mid - 1, i);
	nums(mid + 1, upper, i);
    }

    @Test
    public void testingStressWithOnlySingleLeftRotations(){
	AATree<Integer> b = new AATree<Integer>();
	//int rc;
	//int rcc;
	for (int i = 1; i < 1048576; i++) {
	    //rc = b.getRotationCount();
	    b.insert(i);
	    //rcc = b.getRotationCount();
	    //if ((rcc-rc)>1) {
	    //     System.out.println(rcc-rc);
	    //}
	}
	nums(1, 1048575, b.preOrderIterator());
	assertEquals(1048555, b.getRotationCount());
	assertEquals(19, b.height());
	assertEquals(1048575, b.size());
	//System.out.println("Tree height is: " + b.height());
	points += 8;
    }

    @Test
    public void testingStressWithOnlySingleRightRotations(){
	AATree<Integer> b = new AATree<Integer>();
	//int rc;
	//int rcc;
	for (int i = 1048575; i >= 1; i--) {
	    //rc = b.getRotationCount();
	    b.insert(i);
	    //rcc = b.getRotationCount();
	    //if ((rcc-rc)>1) {
	    //     System.out.println(rcc-rc);
	    //}
	}
	nums(1, 1048575, b.preOrderIterator());
	assertEquals(3145665, b.getRotationCount());
	assertEquals(19, b.height());
	assertEquals(1048575, b.size());
	points += 7;
    }



    ////////// Testing removal
    @Test
    public void testRemovalofLeafs() {
	AATree<Integer> a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);

	// testing removal of leaf, requiring no adjustments
	a.remove(4);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(2);
	values.add(1);
	values.add(3);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}
	points += 2;


	//// testing removal of leaf, requiring level adjustment on right and skew

	a.remove(3);

	result = a.toArrayList();
	values = new ArrayList<Object>();
	levels = new ArrayList<Object>();
	values.add(1);
	values.add(2);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}

	points += 2;

	// testing removal of leaf, requiring level adjustment on left, but no skew
	a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);

	a.remove(1);

	result = a.toArrayList();
	values = new ArrayList<Object>();
	levels = new ArrayList<Object>();
	values.add(2);
	values.add(3);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}

	points += 2;
    }

    @Test
    public void testRemovalofNodesWithOneChild() {
	AATree<Integer> a = new AATree<Integer>();
	// testing removal of node with one child, requiring no level adjustment
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);
	a.remove(3);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(2);
	values.add(1);
	values.add(4);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}

	points += 2;

	// testing removal of root which has no children
	a.remove(4);
	a.remove(2);
	a.remove(1);
	//System.out.println(a);
	result = a.toArrayList();
	assertTrue(result.size() == 0);

	points += 2;
    }


    // testing removal of nodes with two children
    @Test
    public void testRemovalofNodesWithTwoChildren() {
	AATree<Integer> a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);
	a.insert(5);
	a.remove(4);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(2);
	values.add(1);
	values.add(3);
	values.add(5);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}

	points += 2;

	//// testing removal of root with two children
	a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);
	a.remove(2);

	result = a.toArrayList();
	values = new ArrayList<Object>();
	levels = new ArrayList<Object>();
	values.add(3);
	values.add(1);
	values.add(4);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}

	points += 2;
    }

    @Test
    public void testFigure19point63() {
	AATree<Integer> a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(5);
	a.insert(6);
	a.insert(7);
	a.insert(4);

	a.remove(1);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(3);
	values.add(2);
	values.add(5);
	values.add(4);
	values.add(6);
	values.add(7);

	levels.add(2);
	levels.add(1);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(1);

	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}

	points += 2;

	//testing same fig but removal of 2
	a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(5);
	a.insert(6);
	a.insert(7);
	a.insert(4);

	a.remove(2);

	result = a.toArrayList();
	values = new ArrayList<Object>();
	levels = new ArrayList<Object>();
	values.add(3);
	values.add(1);
	values.add(5);
	values.add(4);
	values.add(6);
	values.add(7);

	levels.add(2);
	levels.add(1);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(1);

	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}
	points += 2;
    }

    @Test
    public void testFigure2FromAAPaper() {
	AATree<Integer> a = new AATree<Integer>();
	a.insert(1);
	a.insert(2);
	a.insert(3);
	a.insert(4);
	a.insert(5);
	a.insert(6);
	a.insert(7);
	a.insert(8);
	a.insert(9);
	a.insert(10);
	a.insert(11);
	a.insert(12);
	a.insert(13);
	a.remove(7);
	a.insert(7);

	a.remove(1);

	ArrayList<Object> result = a.toArrayList();
	ArrayList<Object> values = new ArrayList<Object>();
	ArrayList<Object> levels = new ArrayList<Object>();
	values.add(6);
	values.add(4);
	values.add(2);
	values.add(3);
	values.add(5);
	values.add(10);
	values.add(8);
	values.add(7);
	values.add(9);
	values.add(12);
	values.add(11);
	values.add(13);

	levels.add(3);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(1);
	levels.add(3);
	levels.add(2);
	levels.add(1);
	levels.add(1);
	levels.add(2);
	levels.add(1);
	levels.add(1);

	for (int i = 0; i < values.size(); i++){
	    assertEquals(values.get(i), ((AATree.BinaryNode) result.get(i)).getElement());
	    assertEquals(levels.get(i), ((AATree.BinaryNode) result.get(i)).getLevel());
	}
	points += 2;
    }


    @Test
    public void testingStressRemovalDecreasing(){
	AATree<Integer> b = new AATree<Integer>();
	// Creating a tree using no rotations.
	int size = 1048576; //128
	int v = size / 2;
	int temp;
	while (v > 0) {
	    temp = v;
	    while (temp < size){
		b.insert(temp);
		temp += v;
	    }
	    v = v / 2;
	}
	nums(1,1048575,b.preOrderIterator());
	//System.out.println(b);
	assertEquals(2097110, b.getRotationCount());
	// now, let's see whether we will ever have
	// more than one rotation on removal
	//int rc;
	//int rcc;
	//System.out.println("Testing num rotation: ");
	for (int i = 1048575; i > 1; i--){
	    //rc = b.getRotationCount();
	    assertTrue(b.remove(i));
	    assertEquals(i-1, b.size());
	    //rcc = b.getRotationCount();
	    //if ((rcc-rc)>1) {
	    //System.out.println(rcc-rc);
	    //}
	}
	assertEquals(3145665, b.getRotationCount()); // 57
	assertEquals(0, b.height());
	assertTrue(b.remove(1));
	assertEquals(0, b.size());
	assertEquals(-1, b.height());
	points += 7;
    }

    @Test
    public void testingStressRemovalIncreasing(){
	AATree<Integer> b = new AATree<Integer>();
	// Creating a tree using no rotations.
	int size = 1048576; //128
	int v = size / 2;
	int temp;
	while (v > 0) {
	    temp = v;
	    while (temp < size){
		b.insert(temp);
		temp += v;
	    }
	    v = v / 2;
	}
	nums(1,1048575,b.preOrderIterator());
	//System.out.println(b);
	assertEquals(2097110, b.getRotationCount());
	// now, let's see whether we will ever have
	// more than one rotation on removal
	//int rc;
	//int rcc;
	//System.out.println("Testing num rotation: ");
	for (int i = 2; i <= 1048575; i++) {
	    //rc = b.getRotationCount();
	    assertTrue(b.remove(i));
	    //assertEquals(i-1, b.size());
	    //rcc = b.getRotationCount();
	    //if ((rcc-rc)>1) {
	    //System.out.println(rcc-rc);
	    //}
	}
	assertEquals(3145655, b.getRotationCount()); // 57
	assertEquals(0, b.height());
	assertTrue(b.remove(1));
	assertEquals(0, b.size());
	assertEquals(-1, b.height());
	points += 8;
    }



    @Test
    public void testingLogBehaviorOfRemoval(){
	AATree<Integer> t = new AATree<Integer>();
	int nums = 2000000;
	int[] a = new int[nums];
	// populating array
	for (int i = 0; i < nums; i++){
	    a[i] = i;
	}
	int i1;
	int i2;
	int temp;
	// shuffling array
	for (int i = 0; i < nums; i++) {
	    i1 = (int) (Math.random() * nums);
	    i2 = (int) (Math.random() * nums);
	    temp = a[i1];
	    a[i1] = a[i2];
	    a[i2] = temp;
	}
	for (int i = 0; i < nums; i++) t.insert(a[i]);
	assertEquals(nums, t.size());

	ArrayList<Object> al = t.toArrayList();
	for (int i = 1; i < nums; i++) {
	    Integer val = (Integer) ((AATree.BinaryNode) al.get(i)).getElement();
	    if (((AATree.BinaryNode) al.get(i)).getLeftChild() != null) {
		if ((Integer)((AATree.BinaryNode) al.get(i)).getLeftChild().getElement() > val) fail("Not an AA tree");
	    }
	    if (((AATree.BinaryNode) al.get(i)).getRightChild() != null) {
		if ((Integer)((AATree.BinaryNode) al.get(i)).getRightChild().getElement() < val) fail("Not an AA tree");
	    }
	}

	for (int i = 0; i < nums; i++) t.remove(i);
	assertEquals(0, t.size());
	points += 10;
    }

    @AfterClass
    public static void testNothing(){
	System.out.println(points);
    }

}