package edu.princeton.cs.algs4.growingtree.framework;

import edu.princeton.cs.algs4.growingtree.experiments.ExperimentTree;
import edu.princeton.cs.algs4.growingtree.experiments.IExperimentLogger;
import edu.princeton.cs.algs4.growingtree.interfaces.IDeletingNode;
import edu.princeton.cs.algs4.growingtree.interfaces.IInsertingNode;
import edu.princeton.cs.algs4.growingtree.interfaces.INode;
import edu.princeton.cs.algs4.growingtree.interfaces.ISearchingNode;

/**
 * This class defines the nodes that interact directly with the
 * operators defined by the client. Primitives such as rotation
 * happen synchronously within the tree composed of these nodes,
 * whereas they occur asynchronously within the 
 * <code>GrowingTreeNode</code> tree. 
 * 
 * Operators receive instances of these objects, though they are
 * cast to the appropriate interface. When an operator calls a
 * primitive, such as rotateLeft, it passed along to the 
 * <code>GrowingTreeNode</code> associated with this ShadowNode, so
 * that the animation can be queued up.
 * @author Josh Israel
 *
 * @param <P> NodeProperties subclass that parameterizes the tree
 */

public class ShadowNode<P extends NodeProperties> implements IInsertingNode<P>, 
													         ISearchingNode<P>,
													         IDeletingNode<P> {
	/**
	 * Are we animating these operations? (is it a TreeVisualization or a TreeExperiment?)
	 */
	private boolean animating;
	/**
	 * Are we logging these operations?
	 */
	private boolean logging;
	/**
	 * Visual node associated with this node 
	 */
	private GrowingTreeNode<P> node; // ONLY USED FOR ANIMATING
	private P nodeProperties;
	private ShadowNode<P> parent;
	private ShadowNode<P> left;
	private ShadowNode<P> right;
	/**
	 * Key to be used when running experiments. Admittedly, a bit kludgey
	 */
	private Double key; // ONLY USED FOR RUNNING EXPERIMENTS
	
	public IExperimentLogger<P> logger;
	
	public ShadowNode(GrowingTreeNode<P> node, P np) {
		this.node = node;
		this.nodeProperties = np;
		animating = true;
		logging = false;
	}
	
	public ShadowNode(GrowingTreeNode<P> node, P np, IExperimentLogger<P> logger) {
		this(node, np);
		logging = true;
		this.logger = logger;
	}
	
	public ShadowNode(double key, P np, ExperimentTree<P> et) {
		this.key = key;
		this.nodeProperties = np;
		this.logger = et;
		logging = true;
	}
	
	public Double getKey() {
		return key;
	}
	
	public GrowingTreeNode<P> getGrowingNode() {
		return node;
	}
	
	public IExperimentLogger<P> getLogger() {
		return logger;
	}
	
	private static int height(ShadowNode<?> n) {
		if (n == null) return -1;
		return n.getNodeProperties().getHeight();
	}
	
	private static int size(ShadowNode<?> n) {
		if (n == null) return 0;
		return n.getNodeProperties().getSize();
	}
	
	private void updateHeight() {
		int newHeight = 1 + Math.max(height(getLeft()), height(getRight()));
		if (newHeight != getNodeProperties().getHeight()) {
			if (getLogger() != null)
				getLogger().logOther(this, IExperimentLogger.HEIGHT_UPDATE);
			getNodeProperties().setHeight(newHeight);
			if (getParent() != null) {
				getParent().updateHeight();
			}
		}
	}
	private void updateSize() {
		int newSize =  1 + size(getLeft()) + size(getRight());
		if (newSize != getNodeProperties().getSize()) {
			if (getLogger() != null)
				getLogger().logOther(this, IExperimentLogger.SIZE_UPDATE);
			getNodeProperties().setSize(newSize); 
			if (getParent() != null) {
				getParent().updateSize();
			}
		}
	}
	
	public ShadowNode<P> getRight() {
		assert (right != this);
		if (right != null) {
			if (right.parent != this)
				System.out.println("The key is: " + getKey() + " " + right.getKey() + " " + right.parent.getKey());
			assert (right.parent==this);
		}
		return right;
	}
	
	public ShadowNode<P> getLeft() {
		assert (left != this);
		if (left != null) assert (left.parent==this);
		return left;
	}
	
	public ShadowNode<P> getParent() {
		assert (parent != this);
		if (parent != null)
			assert (parent.left == this || parent.right == this);
		return parent;
	}
	
	public ShadowNode<P> getRoot() {
		ShadowNode<P> root = this;
		while (root.getParent() != null) {
			root = root.getParent();
		}
		return root;
	}
	
	public int compareTo(INode<P> other) {
		ShadowNode<P> that = (ShadowNode<P>) other;
		if (animating) return getGrowingNode().compareTo(that.getGrowingNode());
		return getKey().compareTo(that.getKey()); 
	}
	
	public int compareTo(Double other) {
		return getKey().compareTo(other);
	}
	
	public P getNodeProperties() {
		return nodeProperties;
	}
	
	public ShadowNode<P> rotateLeft() {
		assert (right != null);
		assert(getRoot().isBST());
		if (animating) right.getGrowingNode().rotateUp();
		if (logging)   logger.logRotation(this);
		ShadowNode<P> x = right;
		right = x.left;
		if (right != null) {
			right.parent = this;
		}
		x.left = this;
		if (parent != null) {
			if (parent.right == this) parent.right = x;
			else if (parent.left == this) parent.left = x;
			else {
				assert(false); 
			}
		}
		x.parent = parent;
		parent = x;
		assert(getRoot().isBST());
		updateHeight();
		x.updateHeight();
		updateSize();
		x.updateSize();
		if (x.getParent() != null) {
			x.getParent().updateHeight();
		}
		return right;
	}
	
	public ShadowNode<P> rotateRight() {
		assert (left != null);
		assert(getRoot().isBST());
		if (animating) left.getGrowingNode().rotateUp();
		if (logging)   logger.logRotation(this);
		ShadowNode<P> x = left;
		left = x.right;
		if (left != null) {
			left.parent = this;
		}
		x.right = this;
		if (parent != null) {
			if (parent.right == this) parent.right = x;
			else if (parent.left == this) parent.left = x;
			else {
				assert(false);
			}
		}
		x.parent = parent;
		parent = x;
		assert(getRoot().isBST());
		updateHeight();
		x.updateHeight();
		updateSize();
		x.updateSize();
		if (x.getParent() != null) {
			x.getParent().updateHeight();
		}
		return x;
	}
	
	public ShadowNode<P> insertLeft(INode<P> n) {
		assert(n != null);
		ShadowNode<P> ns = (ShadowNode<P>) n;
		assert(ns.parent == null && ns.left == null && ns.right == null);
		ns.parent = this;
		this.left = ns;
		if (animating) getGrowingNode().insertNode(((ShadowNode<P>) n).node);
		if (logging)   logger.logInsertion(this);
		left = (ShadowNode<P>) n;
		assert (getRoot().isBST());
		updateHeight();
		updateSize();
		return left;
	}

	public ShadowNode<P> insertRight(INode<P> n) {
		assert (n != null);
		ShadowNode<P> ns = (ShadowNode<P>) n;
		if (ns.parent != null) assert(false);
		ns.parent = this;
		this.right = ns;
		if (animating) getGrowingNode().insertNode(ns.getGrowingNode());
		if (logging)   logger.logInsertion(this);
		right = ns;
		assert (getRoot().isBST());
		updateHeight();
		updateSize();
		return right;
	}
	
	public ShadowNode<P> getSuccessor() {
		ShadowNode<P> succ = right;
		while (succ.left != null) {
			succ = succ.left;
		}
		return succ;
	}
	
	public ShadowNode<P> getPredecessor() {
		ShadowNode<P> pred = left;
		while (pred.right != null) {
			pred = pred.right;
		}
		return pred;
	}
	
	private static <P extends NodeProperties> int rank(ShadowNode<P> key, ShadowNode<P> n) {
		if (n == null) return 0; 
        int cmp = key.compareTo(n); 
        if      (cmp < 0) return rank(key, n.getLeft()); 
        else if (cmp > 0) return 1 + size(n.getLeft()) 
        						   + rank(key, n.getRight()); 
        else              return size(n.getLeft());
		
		
	}
	
	private void swapNodes(ShadowNode<P> other) {
		if (animating) {
			int rank = rank(other, this);
			getGrowingNode().getHead().swapNodes(getGrowingNode(), rank);
			GrowingTreeNode<P> temp = getGrowingNode();
			node = other.node;
			other.node = temp;
			node.shadowNode = this;
			other.node.shadowNode = other;
		}

		ShadowNode<P> tempParent = getParent();
		ShadowNode<P> tempLeft = getLeft();
		ShadowNode<P> tempRight = getRight();
		if (tempParent != null && this == tempParent.left) {
			tempParent.left = other;
		}
		else {
			if (tempParent != null) tempParent.right = other;
		}
		if (other.parent != null && other.parent.left == other) {
			other.parent.left = this;
		}
		else {
			other.parent.right = this;
		}
		right = other.right;
		left = other.left;
		if (other.parent == this) parent = other;
		else					  parent = other.parent;
		other.parent = tempParent;
		if (tempLeft == other)  other.left = this;
		else 					other.left = tempLeft;
		if (tempRight == other) other.right = this;
		else                    other.right = tempRight;
		if (right != null) right.parent = this;
		if (left != null) left.parent = this;
		if (other.left != null) other.left.parent = other;
		if (other.right != null) other.right.parent = other;
		other.updateHeight();
		other.updateSize();
		updateHeight();
		updateSize();
		assert(getRoot().isBST());
	}
	
	private ShadowNode<P> leafDelete() {
		if (animating) getGrowingNode().getHead().delete(getGrowingNode(), true);
		if (parent == null) {
			return null;
		}
		if (parent.left == this) {
			parent.left = null;
		}
		if (parent.right == this) {
			parent.right = null;
		}
		parent.updateHeight();
		parent.updateSize();
		return null;
	}
	
	// replace a node with 1 child with that child
	private ShadowNode<P> replaceWithChild() {
		assert (left == null || right == null);
		if (animating) getGrowingNode().getHead().delete(getGrowingNode(), true);
		ShadowNode<P> child;
		if (left == null) { child = right; }
		else { child = left; }
		assert (child != null);
		
		child.parent = parent;
		
		if (parent == null) return child;
		
		if (parent.right == this) {
			parent.right = child;
		}
		else {
			parent.left = child;
		}
		parent.updateHeight();
		parent.updateSize();
		return child;
	}
	
	public ShadowNode<P> successorHibbardDelete() {
		ShadowNode<P> ret;
		if (logging)   logger.logDeletion(this);
		if (left == null && right == null) {
			ret = leafDelete();
		}
		else if (right == null || left == null) {
			ret = replaceWithChild();
		}
		else {
			assert (right != null);
			ShadowNode<P> succ = getSuccessor();
			swapNodes(succ);
			if (right == null && left == null) {
				ret = leafDelete();
			}
			else {
				ret = replaceWithChild();
			}
			assert(succ.getRoot().isBST());
		}
		return ret;
	}
	
	public ShadowNode<P> predecessorHibbardDelete() {
		ShadowNode<P> ret;
		if (logging)   logger.logDeletion(this);
		if (left == null && right == null) {
			ret = leafDelete();
		}
		else if (right == null || left == null) {
			ret = replaceWithChild();
		}
		else {
			assert (right != null);
			ShadowNode<P> succ = getPredecessor();
			swapNodes(succ);
			if (succ.right == null && succ.left == null) {
				ret = succ.leafDelete();
			}
			else {
				ret = succ.replaceWithChild();
			}
		}
		return ret;
	}
	
	public void markFound() {
		if (animating) getGrowingNode().getHead().searchAnimatingType(getGrowingNode().getKey());
		if (logging)   logger.logSearchHit(this);
	}
	
	public boolean isBST() {
		assert(parent != this);
		if (right != null) {
			assert (this == right.parent);
			assert (right.isBST());
		}
		if (left != null) {
			assert (this == left.parent);
			assert (left.isBST());
		}
		
		return true;
	}
	
	public void freeze() { freeze(1); }
	
	public void freeze(double lengthMult) {
		if (animating) getGrowingNode().getHead().freeze(lengthMult);
	}
	
}