package brs.visitor;

import brs.*;

/**
 *      Implements Sleator and Tarjan's top-down splay algorithm.  Returns
 *      the BiTree containing the given key Object.  If, however, that
 *      key Object is not found in the BST, returns a BiTree that is
 *      adjacent to the key Object, coming before or after it.
 *
 * @author Alan L. Cox
 */
public class BSTSplay implements IVisitor {
    public static final BSTSplay Singleton = new BSTSplay();
    private BSTSplay() {
    }

    /**
     * @param host an empty binary search tree
     * @param input not used
     * @return the host
     */
    public Object emptyCase(BiTree host, Object input) {
	return (host);
    }

    /**
     * @param host a non-empty binary search tree
     * @param input the key Object
     * @return null or a BiTree whose key is equal or close to input
     */
    public Object nonEmptyCase(BiTree host, final Object input) {
	class Helper {
	    BiTree _dummy;
	    BiTree _leftSubTreeMax;
	    BiTree _rightSubTreeMin;

	    Helper() {
		_dummy = new BiTree();
		_dummy.insertRoot(null);
		_leftSubTreeMax = _dummy;
		_rightSubTreeMin = _dummy;
	    }

	    void setLeftSubTreeMax(BiTree bt) {
		_leftSubTreeMax.setRightSubTree(bt);
		_leftSubTreeMax = bt;
	    }

	    void setRightSubTreeMin(BiTree bt) {
		_rightSubTreeMin.setLeftSubTree(bt);
		_rightSubTreeMin = bt;
	    }

	    BiTree getLeftSubTree() {
		return (_dummy.getRightSubTree());
	    }

	    BiTree getRightSubTree() {
		return (_dummy.getLeftSubTree());
	    }
	}
	final Helper helper = new Helper();

	class Outer implements IVisitor {
	    public Object emptyCase(BiTree child, Object root) {
		return (root);
	    }
	    
	    public Object nonEmptyCase(BiTree root, Object notUsed) {
		if (((Comparable)input).compareTo(root.getRootDat()) < 0) {
		    BiTree child = root.getLeftSubTree();
		    return (child.execute(new IVisitor() {
			public Object emptyCase(BiTree child, Object root) {
			    return (root);
			}

			public Object nonEmptyCase(BiTree child, Object root) {
			    if (((Comparable)input).compareTo(child.getRootDat()) < 0) {
				/* Rotate right. */
				((BiTree)root).setLeftSubTree(child.getRightSubTree());
                                child.setRightSubTree((BiTree)root);
				root = child;
				child = ((BiTree)root).getLeftSubTree();
			    }
			    return (child.execute(new IVisitor() {
				public Object emptyCase(BiTree child, Object root) {
				    return (root);
				}

				public Object nonEmptyCase(BiTree child, Object root) {
				    helper.setRightSubTreeMin((BiTree)root);
				    return (child.execute(Outer.this, root));
				}
			    }, root));
			}
		    }, root));
		} else if (((Comparable)input).compareTo(root.getRootDat()) > 0) {
		    BiTree child = root.getRightSubTree();
		    return (child.execute(new IVisitor() {
			public Object emptyCase(BiTree child, Object root) {
			    return (root);
			}

			public Object nonEmptyCase(BiTree child, Object root) {
			    if (((Comparable)input).compareTo(child.getRootDat()) > 0) {
				/* Rotate left. */
                                ((BiTree)root).setRightSubTree(child.getLeftSubTree());
                                child.setLeftSubTree((BiTree)root);
				root = child;
				child = ((BiTree)root).getRightSubTree();
			    }
			    return (child.execute(new IVisitor() {
				public Object emptyCase(BiTree child, Object root) {
				    return (root);
				}

				public Object nonEmptyCase(BiTree child, Object root) {
				    helper.setLeftSubTreeMax((BiTree)root);
				    return (child.execute(Outer.this, root));
				}
			    }, root));
			}
		    }, root));
		} else
		    return (root);
	    }
	}
	BiTree root = (BiTree)host.execute(new Outer(), null);

	helper.setLeftSubTreeMax(root.getLeftSubTree());
	helper.setRightSubTreeMin(root.getRightSubTree());

	root.setLeftSubTree(helper.getLeftSubTree());
	root.setRightSubTree(helper.getRightSubTree());

	return (root);
    }
}