package editortrees;

import static org.junit.Assert.*;

import java.util.ArrayList;

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

public class EditTreeTest {

	static int points = 0;

	// Feel free to use these strings in your test cases, or not.

	static String s1 = "short string",
			s2 = "a moderately short string",
			s3 = "This string is not as short as the others",
			s4 = "This is a great, big, juicy, longer-than-the-others, string",
			s5 = "You can't always get the strings you want, "
					+ "but if you try sometimes, you just might find you get the strings you need.";

	/**
	 * The variables whose first two digits are your team number are available
	 * for your team's test cases to use. If you want to intiialize them once
	 * and for all instead of in individual test cases, put that code in
	 * setUpXY, where XY is your team number. You may use other variables, of
	 * course, but they should be local to your methods.
	 */
	EditTree t110, t111, t112, t113, t114, t115, t116, t117, t118, t119;
	EditTree t120, t121, t122, t123, t124, t125, t126, t127, t128, t129;
	EditTree t130, t131, t132, t133, t134, t135, t136, t137, t138, t139;
	EditTree t140, t141, t142, t143, t144, t145, t146, t147, t148, t149;
	EditTree t150, t151, t152, t153, t154, t155, t156, t157, t158, t159;
	EditTree t160, t161, t162, t163, t164, t165, t166, t167, t168, t169;
	EditTree t210, t211, t212, t213, t214, t215, t216, t217, t218, t219;
	EditTree t220, t221, t222, t223, t224, t225, t226, t227, t228, t229;
	EditTree t230, t231, t232, t233, t234, t235, t236, t237, t238, t239;
	EditTree t240, t241, t242, t243, t244, t245, t246, t247, t248, t249;
	EditTree t250, t251, t252, t253, t254, t255, t256, t257, t258, t259;
	EditTree t260, t261, t262, t263, t264, t265, t266, t267, t268, t269;
	EditTree ti0, ti1, ti2, ti3, ti4, ti5, ti6, ti7, ti8, ti9;

	// Do not modify this method

	@Before
	public void setUp() throws Exception {
		try {
			setUpInstructors();
		} catch (Exception e) {
			System.out.println("Error in setUpInstructors:");
			e.printStackTrace();
		}
		try {
			setUp11();
		} catch (Exception e) {
			System.out.println("Error in setUp11:");
			e.printStackTrace();
		}
		try {
			setUp12();
		} catch (Exception e) {
			System.out.println("Error in setUp12:");
			e.printStackTrace();
		}
		try {
			setUp13();
		} catch (Exception e) {
			System.out.println("Error in setUp13:");
			e.printStackTrace();
		}
		try {
			setUp14();
		} catch (Exception e) {
			System.out.println("Error in setUp14:");
			e.printStackTrace();
		}
		try {
			setUp15();
		} catch (Exception e) {
			System.out.println("Error in setUp15:");
			e.printStackTrace();
		}
		try {
			setUp16();
		} catch (Exception e) {
			System.out.println("Error in setUp16:");
			e.printStackTrace();
		}
		try {
			setUp21();
		} catch (Exception e) {
			System.out.println("Error in setUp21:");
			e.printStackTrace();
		}
		try {
			setUp22();
		} catch (Exception e) {
			System.out.println("Error in setUp22:");
			e.printStackTrace();
		}
		try {
			setUp23();
		} catch (Exception e) {
			System.out.println("Error in setUp23:");
			e.printStackTrace();
		}
		try {
			setUp24();
		} catch (Exception e) {
			System.out.println("Error in setUp24:");
			e.printStackTrace();
		}
		try {
			setUp25();
		} catch (Exception e) {
			System.out.println("Error in setUp25:");
			e.printStackTrace();
		}
		try {
			setUp26();
		} catch (Exception e) {
			System.out.println("Error in setUp26:");
			e.printStackTrace();
		}
	}

	public void setUpInstructors() throws Exception {

	}

	public void setUp11() throws Exception {

	}

	public void setUp12() throws Exception {

	}

	public void setUp13() throws Exception {

	}

	public void setUp14() throws Exception {

	}

	public void setUp15() throws Exception {
		// Setup a few test trees. Used by get(), toString(), and other
		// non-destructive tests.
		this.t150 = new EditTree();
		this.t151 = new EditTree(s1);
		this.t152 = new EditTree(s2);
		this.t153 = new EditTree(s3);
		this.t154 = new EditTree(s4);
		this.t155 = new EditTree(s5);
		// Used by add() test
		this.t156 = new EditTree(s5);
		// t157 and t158 are used by split and concatenate.
		// t159 is used by the split test and the delete test
		this.t159 = new EditTree(s1);

	}

	public void setUp16() throws Exception {

	}

	public void setUp21() throws Exception {

	}

	public void setUp22() throws Exception {

	}

	public void setUp23() throws Exception {

	}

	public void setUp24() throws Exception {

	}

	public void setUp25() throws Exception {

	}

	public void setUp26() throws Exception {

	}

	// The name of each of your team's tests should end with an underscore
	// followed by your team number,
	// for example, testSize3_13 if you are on team 13.

	// Make sure that each of your tests has a timeout.
	// The timeout should be 1 or 2 seconds unless your
	// test involves VERY complicated operations.

	// Each of your tests should be worth one point.

	// A sample test to remind you of the format:

	@Test(timeout = 1000)
	public void testSize3_i() { // i is for instructor
		ti3 = new EditTree(s1);
		assertEquals(12, ti3.size());
		points += 1; // only incremented if test passes.
	}

	@Test
	// (timeout = 1000)
	public void testInOrderString_15() {
		// Test the toString() method for each of the test strings
		String[] strings = { s1, s2, s3, s4, s5 };
		EditTree[] trees = { t151, t152, t153, t154, t155 };

		for (int t = 0; t < strings.length; t++) {
			assertEquals(trees[t].toString(), strings[t]);
		}

		points += 1;
	}

	@Test(timeout = 1000)
	public void testGet_15() {
		// Tries to get a non-existent element from the null-tree.
		try {
			t150.get(1);
			fail("You should've thrown an IndexOutOfBoundsException on a zero-sized tree!");
		} catch (IndexOutOfBoundsException e) {
			// pass
		}
		// Tries to get an obviously bogus position from a tree
		try {
			t151.get(-1);
			fail("You should've thrown an IndexOutOfBoundsException on a bogus position!");
		} catch (IndexOutOfBoundsException e) {
			// pass
		}
		// Tries to get an object outside of the tree
		try {
			t151.get(42);
			fail("You should've thrown an IndexOutOfBoundsException when the index exceeds the size of the tree!");
		} catch (IndexOutOfBoundsException e) {
			// pass
		}

		// Test the get() method for each of the test strings
		String[] strings = { s1, s2, s3, s4, s5 };
		EditTree[] trees = { t151, t152, t153, t154, t155 };

		for (int t = 0; t < strings.length; t++) {
			String theString = strings[t];
			EditTree theTree = trees[t];

			for (int i = 0; i < theString.length(); i++) {
				assertEquals(theString.charAt(i), theTree.get(i));
			}
		}

		// You've made it this far without blowing up. You may have a point.
		points += 1;
	}

	@Test(timeout = 1000)
	public void testAdd_15() {
		// Add a character to the tree and check if it exists in the toString
		// output.
		String toAdd = "this is a test";
		String currentState = s5;
		for (int i = 0; i < toAdd.length(); i++) {
			// Add it to the tree and the state
			t156.add(toAdd.charAt(i));
			currentState += toAdd.charAt(i);
			assertEquals(currentState, t156.toString());
		}
		// Test adding a specific point
		t151.add('f', 3);
		assertEquals('f', t151.get(3));
		// Try some invalid insert indices
		try {
			t151.add('c', -1);
			fail("You should've thrown an IllegalArgumentException for a negative insertion index!");
		} catch (IllegalArgumentException e) {
			// pass
		}
		// Another test, another point.
		points += 1;
	}

	@Test(timeout = 1000)
	public void testEditTree_15() {
		// Tests the constructor with a tree as an argument
		EditTree testTree = new EditTree(t151);
		// Ensure that they're actually making a copy of the root,
		// not just reassigning it.
		assertFalse(testTree.getRoot() == t151.getRoot());
		// Check if the root and its children are equal
		assertTrue(testTree.getRoot().equals(t151.getRoot()));

		// Here, have a cooki^H^H^H^H^Hpoint
		points += 1;
	}

	@Test(timeout = 2000)
	public void testGetString_15() {
		// Tests the get(pos, length) going from a pos to an arbitrary position
		// in the string
		for (int i = 0; i < s5.length() - 1; i++) {
			for (int j = i + 1; j < s5.length(); j++) {
				assertEquals(s5.substring(i, j), t155.get(i, j - i));
			}
		}

		// ZOMG, UR POINTS ARE GUNNA BE OVER 9000 BY THE END OF THIS!
		points += 1;
	}

	@Test(timeout = 2000)
	public void testHeight_15() {
		String[] strings = { s1, s2, s3, s4, s5 };
		EditTree[] trees = { t151, t152, t153, t154, t155 };
		// Check the height of each node
		for (int t = 0; t < strings.length; t++) {
			assertTrue(maxTreeHeight_15(strings[t].length()) >= trees[t]
					.height());
		}
		//
		points += 1;
	}

	/**
	 * Returns the maximum height of a balanced AVL tree given the number of
	 * nodes.
	 * 
	 * @param nodes
	 * @return
	 */
	private int maxTreeHeight_15(int nodes) {
		double log = Math.log(nodes) / Math.log(2);
		return (int) Math.floor((1.44 * log) - 1.328);
	}

	/**
	 * Perform the concatenate and split tests in this order
	 */
	@Test(timeout = 2000)
	public void testConcatenate_15() {
		// takes a position and splits the string s1 into to substrings
		int pos = 6;
		// constructs two new trees
		this.t157 = new EditTree(s1.substring(0, pos));
		this.t158 = new EditTree(s1.substring(pos, s1.length()));
		// concatenates the two trees
		this.t157.concatenate(this.t158);
		// assert that this new tree has the same in-order traversal as the
		// original string.
		assertEquals(s1, this.t157.toString());
		// You've earned it!
		points += 1;
	}

	@Test(timeout = 2000)
	public void testSplit_15() {
		this.t159 = new EditTree(s1);
		// splits the tree t157 into its original components
		int pos = 6;
		this.t158 = this.t157.split(pos);
		// asserts that the second half of the split t151 is the same as t158
		assertEquals(this.t158, this.t159.split(pos));
		// asserts that the first half of the split is the same as t158
		assertEquals(this.t157, this.t159);

		points += 1;
	}

	@Test(timeout = 3000)
	public void testFind_15() {
		// Choose a fixed position within the s5 string
		int pos = 10;
		int length = 10;
		String substring = s5.substring(pos, pos + length);
		assertEquals(pos, t155.find(substring));
		// Check a non-existent string
		assertEquals(-1, t155.find("asdf"));
		assertEquals(-1, t155.find("asdf", 12));
		// Check for a string that exists before the position given.
		assertEquals(-1, t155.find("can't", 11));

		// Alas! You've found another point!
		points += 1;
	}

	@Test(timeout = 3000)
	public void testDelete_15() {
		this.t159 = new EditTree(s3);
		String modified_s3 = removeCharacter_15(s3, 10);
		this.t159.delete(10);
		assertEquals(modified_s3, this.t159.toString());

	}

	private String removeCharacter_15(String toModified, int position) {
		return toModified.substring(0, position)
				+ toModified.substring(position + 1);
	}

	/**
	 * This test tests the links between a node and it's parent. If the Node
	 * doesn't have a parent field, this test fails gracefully.
	 */
	@Test(timeout = 5000)
	public void testTreeConsistency_parentLinks_15() {
		EditTree[] trees = { t151, t152, t153, t154, t155 };
		for (int i = 0; i < trees.length; i++) {
			// The parentLinksHelper_15() does the actual heavy lifting.
			parentLinksHelper_15(trees[i].getRoot());
		}

		// You did your parent links right, have a point. If you didn't do
		// parent links, have a free point.
		points += 1;
	}

	private void parentLinksHelper_15(Node root) {
		if (root.left != null) {
			// checkParentChildLink_15 does the actual check
			if (checkParentChildLink_15(root, root.left))
				parentLinksHelper_15(root.left);

		}
		if (root.right != null) {
			// checkParentChildLink_15 does the actual check
			if (checkParentChildLink_15(root, root.right))
				parentLinksHelper_15(root.right);
		}
	}

	/**
	 * Checks that the child has a link to the parent, accessing the parent
	 * field using reflection. We're using reflection so that we don't throw
	 * compile-time errors if the parent field doesn't exist.
	 * 
	 * @param parent
	 * @param child
	 * @returns whether the field exists and we should continue checking.
	 */
	private boolean checkParentChildLink_15(Node parent, Node child) {
		Class<?> c_l = child.getClass();
		try {
			// Check if the parent field is equal to the parent.
			// Essentially, this is the same as child.parent == parent
			assertTrue(c_l.getDeclaredField("parent").get(child) == parent);
			return true;
		} catch (IllegalAccessException e) {
			// The field is private..ignored.
			return false;
		} catch (IllegalArgumentException e) {
			// The field isn't a part of the class..fair enough.
			return false;
		} catch (SecurityException e) {
			// The field is private..ignored.
			return false;
		} catch (NoSuchFieldException e) {
			// The field isn't a part of the class..fair enough.
			return false;
		}
	}

	@Test(timeout = 5000)
	public void testTreeConsistency_duplicateNodes_15() {
		Node t155_root = t155.getRoot();
		ArrayList<Node> nodes = new ArrayList<Node>(t155.size() + 1);
		// Do the actual test
		duplicateNodesHelper_15(t155_root, nodes);
		points += 1;
	}

	private void duplicateNodesHelper_15(Node rootNode, ArrayList<Node> nodeList) {
		// Check the children..note this is comparing objects, not .equals()
		// checks.
		for (Node n : nodeList) {
			if (rootNode.left != null) {
				assertFalse(n == rootNode.left);
			}
			if (rootNode.right != null) {
				assertFalse(n == rootNode.right);
			}
		}
		if (rootNode.left != null) {
			nodeList.add(rootNode.left);
			duplicateNodesHelper_15(rootNode.left, nodeList);
		}
		if (rootNode.right != null) {
			nodeList.add(rootNode.right);
			duplicateNodesHelper_15(rootNode.right, nodeList);
		}
	}

}