/** Persistent binary search tree.
 * Uses path-copying (as opposed to fat nodes or node copying, so Omega(log n)
 * instead of Omega(1)). */
public class PathCopyingBST
	<K extends Comparable<? super K>, V> implements BST<K,V> {
	private java.util.ArrayList<Node<K,V>> versions;
	private Node<K,V> root;

	/** constructor */
	public PathCopyingBST() {
		root = null;
		versions = new java.util.ArrayList<Node<K,V>>();
	}

	/** associate key with value
	 * @return the version spawned by this operation. */
	public int insert (K key, V value) {
		versions.add(root);	
		if (key == null)
			throw new NullPointerException(
				"tried to insert with null key");
		
		root = insert(root, key, value);
		return versions.size() - 1;
	}
	
	/** insert key in a specific subtree */
	private Node<K,V> insert(Node<K,V> node, K key, V value) {
		/* add new node here, end recursion */
		if (node == null)
			return new Node<K,V>(key, value);

		/* recurse until we reach the desired node */	
		int comp = key.compareTo(node.key);
		if (comp < 0)
			return new Node<K,V>(insert(node.left, key, value), 
				node.key, node.value, node.right);
		else if (comp > 0)
			return new Node<K,V>(node.left, node.key, node.value,  
				insert(node.right, key, value));
		else  /* old key found, add new value */ 
			return new Node<K,V>(node.left, key, value, node.right);
	}

	/** find key and return corresponding value
	 * @return value associated with key, or null if not found. */
	public V search (K key) {
		if (key == null)
			throw new NullPointerException(
				"tried to search with null key");
		else
			return search(root, key);
	}
	
	/** find key and return corresponding value from a specific version
	 * @param key the key to find
	 * @param version the version number of the tree.
	 * @return value associated with key, or null if not found / non-existing
	 *  version. */
	public V search (K key, int version) {
		if (key == null)
			throw new NullPointerException(
				"tried to search with null key");
		if (version >= versions.size())
			return null;
		
		/* temporarily set current version to requested version,
		 * and restore it after performing search. */
		return search(versions.get(version), key);
	}
	
	/** find key in a specific subtree, return value
	 * pass a root node from an earlier insert or delete operation to 
	 * search in that version of the tree.
	 * @return the value associated with key, in the specified tree */
	public V search (Node<K,V> n, K key) {
		/* key not found */
		if (n == null)
			return null;

		int comp = key.compareTo(n.key);
		if (comp < 0)
			return search(n.left, key);
		else if (comp > 0)
			return search(n.right, key);
		else
			/* key found */
			return n.value;
	}

	/** find key and remove corresponding element
	 * @return the version spawned by this operation.. */
	public int delete (K key) {
		versions.add(root);
		if (key == null)
			throw new NullPointerException(
				"tried to delete with null key");
		root = delete(root, key);
		return versions.size() - 1;
	}

	private Node<K,V> delete (Node<K,V> n, K key) {
		/* key not found, end recursion */
		if (n == null)
			return null;

		/* recurse until we reach the desired node */
		int comp = key.compareTo(n.key);
		if (comp < 0)
			return new Node<K,V>(delete(n.left, key), n.key, 
				n.value, n.right);
		else if (comp > 0)
			return new Node<K,V>(n.left, n.key, n.value, 
				delete(n.right, key));
		
		/* recursion reached the node to be deleted */
		/* simple cases, 0 or 1 child: */
		if (n.left == null && n.right == null)
			return null;
		else if (n.left == null)
			return n.right;
		else if (n.right == null)
			return n.left;
		/* 2 children, swap node with in-order predecessor 
		 * and delete it. to simplify matters the path to the
		 * predecessor is walked twice, first looking it up and
		 * then copying its path minus the node to be deleted. */
		else {
			/* find in-order predecessor */
			Node<K,V> pred = predNode(n.left);
			/* delete it from this subtree */
			Node<K,V> temp = delete(n, pred.key);
			/* return predecessor with children of old node */
			return new Node<K,V>(temp.left, pred.key, pred.value, temp.right);
		}
	}
	
	/** return in-order predecessor of specified node */
	private Node<K,V> predNode(Node <K,V> node) {
		if (node.right == null)
			return node;
		else
			return predNode(node.right);
	}

	/** undo last mutation. 
	 * undoing itself can not be undone, this operation is destructive,
	 * since the versions are stored in a list which can not keep track 
	 * of multiple branches. */
	public void rollback() {
		/* get last version from stack and make it current */
		root = versions.get(versions.size() - 1);
	}

	/** return an in-order traversal of the tree */
	public String toString() {
		if (root == null)
			return "empty tree";
		else
			return inOrder(root);
	}
	
	/** recursive in-order helper function */
	private String inOrder (Node node) {
		if (node == null)
			return "";
		
		return inOrder(node.left) + " " + node.key + "=" + node.value
			+ inOrder(node.right);
	}
}