package class9_2_TreeRotations;

/**
 * A simple example of a Binary Search Tree
 */
public class BinarySearchTree {

	/*
	 * A node within the tree
	 */
	public static class Node {
		private Node _parent = null;
		private Node _left = null;
		private Node _right = null;
		
		private int _key = 0;
		
		public Node(int key) {
			_key = key;
		}
		
		public int getKey() {
			return _key;
		}
		
		public void setKey(int key) {
			_key = key;
		}
	}
	
	/*
	 * The root of the tree.
	 */
	Node _root = null;
		
	/*
	 * The node is added to the tree.
	 * The node's parent is updated, so it can be used
	 * to find nearby nodes in the tree.
	 * 
	 * From Cormen, Leiserson, et al. 2nd edition, p. 261.
	 */
	public void add(Node newNode) {
		Node current = null;
		Node next = _root;
		while(null != next) {
			current = next;
			if(newNode._key < current._key) {
				next = current._left;
			}
			else {
				next = current._right;
			}
		}
		newNode._parent = current;
		if(null == current) { // Tree was empty.
			_root = newNode;
		}
		else if(newNode._key < current._key) {
			current._left = newNode;
		}
		else {
			current._right = newNode;
		}
	}
	
	/* Perform a left rotation with oldParent
	 * as the old parent and its right child
	 * as the new parent.
	 */
	public void rotateLeft(Node oldParent) {
		if(null == oldParent) {
			return;
		}
		Node newParent = oldParent._right;
		if(null == newParent) {
			return;
		}
		if(_root == oldParent) {
			_root = newParent;
		}
		newParent._parent = oldParent._parent;
		if(null != newParent._parent) {
			if(newParent._parent._right == oldParent) {
				newParent._parent._right = newParent;
			}
			else {
				newParent._parent._left = newParent;
			}
		}
		oldParent._right = newParent._left;
		if(null != oldParent._right) {
			oldParent._right._parent = oldParent;			
		}
		newParent._left = oldParent;
		oldParent._parent = newParent;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		Node n6 = new Node(6);
		Node n7 = new Node(7);
		Node n8 = new Node(8);
		Node n9 = new Node(9);
		Node n10 = new Node(10);
		Node n11 = new Node(11);
		Node n12 = new Node(12);
		Node n13 = new Node(13);
		Node n14 = new Node(14);
		Node n15 = new Node(15);

        tree.add(n2);
        tree.add(n1);
        tree.add(n4);
        tree.add(n3);
        tree.add(n5);
        tree.add(n6);

//		tree.add(n5);
//		tree.add(n2);
//		tree.add(n1);
//		tree.add(n4);
//		tree.add(n9);
//		tree.add(n7);
//		tree.add(n6);
//		tree.add(n12);
//		tree.add(n11);
//		tree.add(n13);
//		tree.add(n15);
		
		System.out.println("Before rotation:");
		tree.print();

		tree.rotateLeft(tree._root);
		
		System.out.println("After rotation:");
		tree.print();
	}
	
	/*
	 * From Cormen, Leiserson, et al. 2nd edition, p. 257.
	 * 
	 * @return the node with the given key, or null if the key is not in the tree.
	 */
	 Node search(int key) {
		Node current = _root;
		while(null != current && current._key != key) {
			if(key < current._key) {
				current = current._left;
			}
			else {
				current = current._right;
			}
		}
		return current; 
	}
	

	
	/*
	 * Return the minimum node of the
	 * current node's sub-tree.
	 * 
	 * (That is the sub-tree including
	 * this node and all its decendents (sp).)
	 */
	Node minimum(Node current) {
		while(null != current._left) {
			current = current._left;
//			System.out.println("Down Left");
		}
		return current;
	}
	
	/*
	 * Return the key one greater than the current node.
	 * 
     * From Cormen, Leiserson, et al. 2nd edition, p. 261
	 */
	Node successor(Node current) {
		if(null != current._right) {
//			System.out.println("Down right");
			return minimum(current._right);
		}
		Node next = current._parent;
		while(null != next && current == next._right) {
//			System.out.println("Up Left");
			current = next;
			next = current._parent;
		}
//		System.out.println("Up Right");
		return next;
	}
	
	/*
	 * Display the tree by printing to standard out.
	 * 
	 * Prints just the nodes, arranged in roughly the
	 * order you would draw a tree on the blackboard.
	 */
	void print() {
		// In-order traverse tree to count nodes
		int numNodes = 0;
		Node current = _root;
		if(current != null) {
			current = minimum(current);
		}
		while(current != null) {
//			System.out.println(current._key);
			numNodes++;
			current = successor(current);
		}
		
		int width = 80;
		
		if(numNodes > 0) {
			// Breadth-first traversal to print.
			int depth[] = new int[numNodes];
			int rowOrder[] = new int[numNodes];
			Node nodes[] = new Node[numNodes];
			
			current = _root;
			depth[0] = 0;
			rowOrder[0] = 0;
			
			int indNextFree = 1;  // Location of next free spot in array
			
			for(int indCurrentNode=0; indCurrentNode<numNodes; indCurrentNode++) {
				nodes[indCurrentNode] = current;
				if(null != current._left) {
					nodes[indNextFree] = current._left;
					depth[indNextFree] = depth[indCurrentNode] + 1;
					rowOrder[indNextFree] = rowOrder[indCurrentNode]*2;
					indNextFree++;
				}
				if(null != current._right) {
					nodes[indNextFree] = current._right;
					depth[indNextFree] = depth[indCurrentNode] + 1;
					rowOrder[indNextFree] = rowOrder[indCurrentNode]*2 + 1;
					indNextFree++;
				}
				if(indCurrentNode + 1 < numNodes) {
					current = nodes[indCurrentNode + 1];
				}
			}
			
			int currentColumn = 0;
			int spacing = 32;
			int currentDepth = 0;
			for(int indCurrentNode=0;indCurrentNode<numNodes; indCurrentNode++) {
				int desiredColumn; 					
				if(depth[indCurrentNode]!=currentDepth) {
					// Begin new line
					currentDepth = depth[indCurrentNode];
					spacing /= 2;
					System.out.println();
					currentColumn = 0;
				}
				desiredColumn = spacing * (1 + 2*rowOrder[indCurrentNode]);
				for(int j = 0; j < (desiredColumn-currentColumn); j++) {
					System.out.print(" ");
				}
				System.out.print(nodes[indCurrentNode].getKey());
				if(nodes[indCurrentNode].getKey()<10) {
					currentColumn = desiredColumn + 1;
				}
				else {
					currentColumn = desiredColumn + 2;
				}
			}
			System.out.println();
		}
	}
	

}