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

/**
 * All of the Splay Tree Operators.
 * @author Josh Israel
 */

import edu.princeton.cs.algs4.growingtree.framework.NodeProperties;
import edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode;
import edu.princeton.cs.algs4.growingtree.interfaces.IDeleteOperator;
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;

public class SplayOperators {
	public <P extends NodeProperties> void splay(IAlgorithmNode<P> x, IAlgorithmNode<P> root) {
		IAlgorithmNode<P> p, g;
		  /*check if node x is the root node*/
		if(x.getParent() == null) return;
		  /*Performs Zig step*/
		else if(x.getParent()==root) {
			if(x==x.getParent().getLeft()) {
				root.rotateRight();
				root = root.getParent();
			}
			else
				root.rotateLeft();
				root = root.getParent();
			}
		else {
			p = x.getParent(); /*now points to parent of x*/
			g = p.getParent(); /*now points to parent of x's parent*/
			/*Performs the Zig-zig step when x is left and x's parent is left*/
			if(x==p.getLeft() && p==g.getLeft()) {
				g.rotateRight();
				p.rotateRight();
			}
			/*Performs the Zig-zig step when x is right and x's parent is right*/
			else if(x==p.getRight() && p==g.getRight()) {
				g.rotateLeft();
				p.rotateLeft();
			}
			/*Performs the Zig-zag step when x's is right and x's parent is left*/
			else if(x==p.getRight() && p==g.getLeft()) {
				p.rotateLeft();
				g.rotateRight();
			}
			/*Performs the Zig-zag step when x's is left and x's parent is right*/
			else if(x==p.getLeft() && p==g.getRight()) {
				p.rotateRight();
				g.rotateLeft();
			}
			splay(x, x.getRoot());
		}
	}
	
	
	public class SplayInsertion<P extends NodeProperties> extends BSTInsertion<P> {
		public void doInsert(IInsertingNode<P> root, INode<P> newNode) {
			if (newNode == null) return;
			IAlgorithmNode<P> inserted = insert(root, newNode);
			if (inserted != null)
				splay(inserted, root);
		}
	}
	
	public class SplaySearch<P extends NodeProperties> extends BSTSearch<P> {
		public INode<P> doSearch(ISearchingNode<P> root, Comparable<INode<P>> keyCompare) {
			
			IAlgorithmNode<P> found = search(root, keyCompare);
			if (found == null) {
				return null;
			}
			splay(found, root);
			return found;
		}
	}
	
	public class SplayDeletion<P extends NodeProperties> implements IDeleteOperator<P> {
		public void doDelete(IAlgorithmNode<P> root, IDeletingNode<P> node) {
			IAlgorithmNode<P> parent = node.getParent();
			node.successorHibbardDelete();
			if (parent != null) {
				splay(parent, root);
			}
		}
	}
	
}