import java.util.*;
class HW10A extends Cow {

	static void runAutograder() {
		// indices  0  1  2  3  4  5  6  7
		int[] U = { 9, 4, 0, 1, 7, 6, 8, 3 }; // Unsorted
		int[] S = { 0, 1, 3, 4, 6, 7, 8, 9 }; // Sorted
		int[] L = { 0, 1, 3, 4, 6, 7, 8    }; // different Length
		int[] V = { 0, 1, 3, 4, 5, 7, 8, 9 }; // different Values
		int[] O = { 0 };                      // One element
		int[] E = {};                         // Empty
		System.out.println("NOTE: Later tests use your areEqual(...) implementation.");

		System.out.println("\nRUNNING AUTOGRADER");
		System.out.print  ("------------------");

		System.out.print("\nareEqual");
		_grade(areEqual(S, S.clone()) == true);
		_grade(areEqual(S, U) == false);
		_grade(areEqual(S, V) == false);
		_grade(areEqual(S, L) == false);
		_grade(areEqual(S, E) == false);
		_grade(areEqual(E, E) == true);

		System.out.print("\nisSorted");
		_grade(isSorted(S) == true);
		_grade(isSorted(U) == false);
		_grade(isSorted(O) == true);
		_grade(isSorted(E) == true);

		System.out.print("\nlinearSearch");
		_grade(linearSearch(S, 0) == 0);
		_grade(linearSearch(S, 6) == 4);
		_grade(linearSearch(S, 9) == 7);
		_grade(linearSearch(S, 5) == -1);
		_grade(linearSearch(S, -10) == -1);
		_grade(linearSearch(O, 0) == 0);
		_grade(linearSearch(O, 5) == -1);
		_grade(linearSearch(E, 5) == -1);
		_grade(linearSearch(U, 9) == 0);

		System.out.print("\nbinarySearch");
		_grade(binarySearch(S, 0) == 0);
		_grade(binarySearch(S, 6) == 4);
		_grade(binarySearch(S, 9) == 7);
		_grade(binarySearch(S, 5) == -1);
		_grade(binarySearch(S, -10) == -1);
		_grade(binarySearch(O, 0) == 0);
		_grade(binarySearch(O, 5) == -1);
		_grade(binarySearch(E, 5) == -1);


		System.out.print("\nbubbleSort");
		{
			int[] U_clone = U.clone();
			bubbleSort(U_clone);
			_grade(areEqual(S, U_clone) == true);
		}


		System.out.print("\ntreeSort");
		{
			int[] U_clone = U.clone();
			treeSort(U_clone);
			// System.out.println(Arrays.toString(U_clone)); 
			_grade(areEqual(S, U_clone) == true);
		}

		System.out.print("\nheapSort");
		{
			int[] U_clone = U.clone();
			heapSort(U_clone);
			_grade(areEqual(S, U_clone) == true);
		}
	}

	static void _grade(boolean shouldBeTrue) {
		char c;
		if (shouldBeTrue) {
			c = '+';
		} else {
			c = '-';
		}
		System.out.print(c);
	}

	////////////////////////////////////////////////////////////////////////////////
	// YOUR CODE STARTS HERE ///////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////


	public static void main(String[] arguments) {
		// int[] array = { 9, 4, 0, 1, 7, 6, 8, 3 }; 
		// System.out.println(Arrays.toString(array));

		runAutograder();
	}

	// Get whether the arrays A and B have all the exact same elements
	// in the exact same order.
	// 
	// Worst-case Time: O(n)
	// Worst-case Space: O(1)
	static boolean areEqual(int[] A, int[] B) {
		if (A.length != B.length) return false;
		for (int i = 0; i < A.length; ++i) {
			if (A[i] != B[i]) return false;
		}
		return true;
	}

	// Get whether the array is sorted.
	// The empty array is considered to be sorted.
	// NOTE: For us, sorted means "in ascending order."
	// 
	// Worst-case Time: O(n)
	// Worst-case Space: O(1)
	static boolean isSorted(int[] array) {
		for (int i = 0; i < array.length - 1; ++i) {
			int j = i + 1;
			if (array[i] > array[j]) return false;
		}
		return true;
	}

	// Get the index of the first element in array with this value.
	// Returns -1 if no such element exists.
	// 
	// Worst-case Time: O(n)
	// Worst-case Space: O(1)
	static int linearSearch(int[] array, int value) {
		for (int i = 0; i < array.length; ++i) {
			if (array[i] == value) {
				return i;
			}
		}
		return -1;
	}

	// Get the index of the first element in array with this value.
	// Returns -1 if no such element exists.
	// NOTE!: array must be sorted; otherwise returns nonsense.
	// 
	// Worst-case Time: O(log n)
	// Worst-case Space: O(1)
	static int binarySearch(int[] array, int value) {
		if (array.length == 0) return -1;
		int i = 0;
		int j = array.length - 1;
		int k = -1;
		do {
			k = (i + j) / 2;
			if (value == array[k]) {
				return k;
			} else if (value < array[k]) {
				j = k - 1;
			} else {
				i = k + 1;
			}
		} while (i <= j);
		return -1;
	}


	// Sorts the array in-place using bubble sort.
	// NOTE: Best-case runtime is better than worst-case runtime.
	// 
	// Worst-case Time: O(n^2)
	// Best-case Time: O(n)
	// Worst-case Space: O(1)
	static void bubbleSort(int[] array) {
		// HINT: Look up bubble sort on Wikipedia.
		for (int rep = 0; rep < array.length; ++rep) {
			boolean madeAnySwaps = false;
			for (int i = 0; i < (array.length - 1) - rep; ++i) {
				if (array[i] > array[i + 1]) {
					madeAnySwaps = true;
					int tmp = array[i];
					array[i] = array[i + 1];
					array[i + 1] = tmp;
				}
			}
			if (!madeAnySwaps) break;
		}
	}


	static class Node {
		int value;
		Node leftChild;
		Node rightChild;
	}

	static class BinarySearchTree {
		Node root;
		void add(int value) {
			Node newNode = new Node();
			newNode.value = value;
			if (root == null) {
				root = newNode;
				return;
			}
			Node curr = root;
			while (true) {
				if (value < curr.value) {
					if (curr.leftChild == null) {
						curr.leftChild = newNode;
						return;
					} else {
						curr = curr.leftChild;
					}
				} else {
					if (curr.rightChild == null) {
						curr.rightChild = newNode;
						return;
					} else {
						curr = curr.rightChild;
					}
				}
			}
		}
		ArrayList<Integer> gatherNodesIntoSortedArrayList() {
			ArrayList<Integer> result = new ArrayList<>();
			_gatherHelper(root, result);
			return result;
		}
		void _gatherHelper(Node curr, ArrayList<Integer> result) {
			if (curr.leftChild != null) _gatherHelper(curr.leftChild, result);
			result.add(curr.value);
			if (curr.rightChild != null) _gatherHelper(curr.rightChild, result);
		}
	}

	// Sort the array using (out-of-place) tree sort.
	//
	// 1) Build a BinarySearchTree object out of the array.
	//
	//    No work-arounds allowed.
	//    You MUST implement an add function, and use it like this:
	//
	//    for (int element : array) {
	//        binarySearchTree.add(element);
	//    }
	//
	// 2) Traverse the binary search tree
	//    (using the appropriate traversal order)
	//    to gather the elements in sorted order.
	//
	// NOTE: You can (and should) write more functions.
	// NOTE: You must document all functions.
	// 
	// Worst-case Time: O(n^2) NOTE: our tree is NOT self-balancing
	// Worst-case Space: O(n)
	static void treeSort(int[] array) {
		BinarySearchTree binarySearchTree = new BinarySearchTree();
		for (int element : array) {
			binarySearchTree.add(element);
			// HW10_printBinaryTree(binarySearchTree.root);
		}

		// HINT: Here is a function I wrote that can print your tree (or heap)
		//       Definitely print the tree to check your work!
		//       Try lots of different test cases!
		// HW10_printBinaryTree(binarySearchTree.root);

		// v This is meh, but fine :)
		ArrayList<Integer> tmp = binarySearchTree.gatherNodesIntoSortedArrayList();
		assert(array.length == tmp.size());
		for (int i = 0; i < array.length; ++i) array[i] = tmp.get(i);
	}

	static void heapSort(int[] array) {
	}

}