public class TrinaryTree<T extends Comparable<T>> {

	private class Node {
		private T value;
		private Node left;
		private Node mid;
		private Node right;

		public Node(T value) {
			this.value = value;
			left = null;
			right = null;
		}
	}

	private Node root;

	public TrinaryTree() {
		root = null;
	}

	public void insert(T value) {
		root = insert(root, value);
	}

	private Node insert(Node node, T value) {
		if (node == null) {
			Node n = new Node(value);
			return n;
		}
		int comp = value.compareTo(node.value);
		if (comp < 0)
			node.left = insert(node.left, value);
		else if (comp > 0)
			node.right = insert(node.right, value);
		else 
			node.mid = insert(node.mid, value);
		return node;

	}

	public void delete(T value) {
		root = delete(root, value);
	}

	private Node delete(Node node, T value) {
		if (node == null)
			return null;
		int comp = value.compareTo(node.value);
		if (comp < 0)
			node.left = delete(node.left, value);
		else if (comp > 0)
			node.right = delete(node.right, value);
		else {
			if (node.mid != null)
				node.mid = delete(node.mid, value);
			else {
				if (node.left == null)
					return node.right;
				if (node.right == null)
					return node.left;
				//if has both left and right children
				Node x = node;
				//find successor
				node = findMin(node.right);
				node.right = deleteMin(x.right);
				node.left = x.left;
			}
		}
		return node;
	}

	private Node findMin(Node node) {
		while (node.left != null)
			node = node.left;
		while (node.mid != null)
			node = node.mid;
		return node;
	}

	//when delete min, first find if there is duplicate key
	//if found, delete duplicate, otherwise, delete that node
	private Node deleteMin(Node node) {
		if (node.left == null)
			return deleteMid(node);
		node.left = deleteMin(node.left);
		return node;
	}

	//delete duplicates
	private Node deleteMid(Node node) {
		if (node.mid == null)
			return node.right;
		node.mid = deleteMid(node.mid);
		return node;

	}

	//for test use

	/*
	 * specification of serialize:
	 * 
	 * The function serialize the trinary tree by using level order traversal, # indicate null,
	 * all nodes with less then 3 children will be followed by # for each null children, except
	 * for nodes in deepest level
	 */
	public String serialize() {
		return serialize(root);
	}

	private String serialize(Node root) {
		String str = "";
		LinkedList<Node> parent = new LinkedList<Node>();
		parent.add(root);
		boolean end = false;
		while (!end) {
			end = true;
			int size = parent.size();
			for (int i = 0; i < size; i++) {
				Node temp = parent.removeFirst();
				str += temp == null? "#": temp.value;
				str += ",";
				if (temp == null)
					continue;
				if (!isLeaf(temp))
					end = false;
				parent.add(temp.left);
				parent.add(temp.mid);
				parent.add(temp.right);
			}
		}
		return str.substring(0, str.length() - 1);
	}

	private boolean isLeaf(Node node) {
		return node.left == null && node.right == null && node.mid == null;
	}

	public static void main(String[] args) {
		test1();
		test2();
		test3();
		test4();
	}

	
	/*
	 * 
	 * Test Cases
	 *
	 */

	//test insert without duplicate
	private static void test1() {
		TrinaryTree<Integer> t = new TrinaryTree<Integer>();
		t.insert(10);
		t.insert(5);
		t.insert(15);
		t.insert(3);
		t.insert(7);
		t.insert(8);
		t.insert(9);
		t.insert(13);
		t.insert(14);
		t.insert(18);
		t.insert(16);
		//expected result after insertion
		String res = "10,5,#,15,3,#,7,13,#,18,#,#,#,#,#,8,#,#,14,16,#,#,#,#,9,#,#,#,#,#,#";
		if (res.equals(t.serialize()))
			System.out.println("Test Case 1 passed!");
		else 
			System.out.println("Test Case 1 failed...");
	}

	//test delete without duplicate
	private static void test2() {
		TrinaryTree<Integer> t = new TrinaryTree<Integer>();
		t.insert(17);
		t.insert(10);
		t.insert(22);
		t.insert(5);
		t.insert(13);
		t.insert(19);
		t.insert(27);
		t.insert(4);
		t.insert(11);
		t.insert(14);
		t.insert(18);
		t.insert(20);
		t.insert(29);
		t.insert(3);
		t.insert(28);
		//expected result after insertion
		String res = "17,10,#,22,5,#,13,19,#,27,4,#,#,11,#,14,18,#,20,#,#,29,"
				+ "3,#,#,#,#,#,#,#,#,#,#,#,#,#,#,28,#,#";
		if (!res.equals(t.serialize())) {
			System.out.println("Test Case 2 failed...");
			return;
		}

		t.delete(10);
		//expected result after delete 10
		res = "17,11,#,22,5,#,13,19,#,27,4,#,#,#,#,14,18,#,20,#,#,29,3,#,#,#,#,#,#,#,#,#,#,#,28,#,#";
		if (!res.equals(t.serialize())) {
			System.out.println("Test Case 2 failed...");
			return;
		}

		t.delete(28);
		//expected result after delete 28
		res = "17,11,#,22,5,#,13,19,#,27,4,#,#,#,#,14,18,#,20,#,#,29,3,#,#,#,#,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize())) {
			System.out.println("Test Case 2 failed...");
			return;
		}

		t.delete(27);
		//expected result after delete 27
		res = "17,11,#,22,5,#,13,19,#,29,4,#,#,#,#,14,18,#,20,#,#,#,3,#,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize())) {
			System.out.println("Test Case 2 failed...");
			return;
		}

		t.delete(5);
		t.delete(19);
		t.delete(17);
		//expected result after multiple deletions
		res = "18,11,#,22,4,#,13,20,#,29,3,#,#,#,#,14,#,#,#,#,#,#";
		if (!res.equals(t.serialize()))
			System.out.println("Test Case 2 failed...");
		else
			System.out.println("Test Case 2 passed!");

	}

	//test insert with duplicates
	public static void test3() {
		TrinaryTree<Integer> t = new TrinaryTree<Integer>();
		t.insert(27);
		t.insert(15);
		t.insert(33);
		t.insert(7);
		t.insert(22);
		t.insert(30);
		t.insert(39);
		t.insert(27);
		t.insert(27);
		t.insert(15);
		t.insert(7);
		t.insert(9);
		t.insert(22);
		t.insert(31);
		t.insert(35);
		t.insert(39);
		t.insert(8);
		t.insert(9);
		t.insert(22);
		t.insert(30);
		t.insert(30);
		//expected result after insertion
		String res = "27,15,27,33,7,15,22,#,27,#,30,#,39,#,7,9,#,#,#,#,22,#,#,#,#,#,30,31,35,39,"
				+ "#,#,#,#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize()))
			System.out.println("Test Case 3 failed...");
		else
			System.out.println("Test Case 3 passed!");
	}

	//test delete with duplicates
	public static void test4() {
		TrinaryTree<Integer> t = new TrinaryTree<Integer>();
		t.insert(27);
		t.insert(15);
		t.insert(33);
		t.insert(7);
		t.insert(22);
		t.insert(30);
		t.insert(39);
		t.insert(27);
		t.insert(27);
		t.insert(15);
		t.insert(7);
		t.insert(9);
		t.insert(22);
		t.insert(31);
		t.insert(35);
		t.insert(39);
		t.insert(8);
		t.insert(9);
		t.insert(22);
		t.insert(30);
		t.insert(30);
		//expected result after deletion
		String res = "27,15,27,33,7,15,22,#,27,#,30,#,39,#,7,9,#,#,#,#,22,#,#,#,#,#,30,31,35,39,"
				+ "#,#,#,#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize())){
			System.out.println("Test Case 4 failed...");
			return;
		}

		//delete 27
		t.delete(27);
		//expected result after delete 27
		res = "27,15,27,33,7,15,22,#,#,#,30,#,39,#,7,9,#,#,#,#,22,#,#,30,31,35,39,"
				+ "#,#,#,#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize())){
			System.out.println("Test Case 4 failed...");
			return;
		}

		//delete 7
		t.delete(7);
		//expected result after delete 7
		res = "27,15,27,33,7,15,22,#,#,#,30,#,39,#,#,9,#,#,#,#,22,#,#,30,31,35,39,"
				+ "#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize())){
			System.out.println("Test Case 4 failed...");
			return;
		}

		//multiple deletions
		t.delete(22);
		t.delete(27);
		t.delete(27);
		//expected result after delete 7
		res = "30,15,#,33,7,15,22,30,#,39,#,#,9,#,#,#,#,22,#,#,30,31,35,39,"
				+ "#,8,9,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#";
		if (!res.equals(t.serialize()))
			System.out.println("Test Case 4 failed...");
		else 
			System.out.println("Test Case 4 passed");
	}
}