package semisplay;

import java.util.ArrayList;

/**
 * Project Algoritmen en Datastructuren II - Semi-splay
 * UGent - Academiejaar 2007-2008
 *
 * Bottom-up implementatie van semi-splay
 *
 * Naam student:
 * Studentennummer:
 */

public class BottomUpSemiSplay<E extends Comparable<E>> extends AbstractBinaryTree<E> {
    private StackArray<BinaryTreeNode<E>> path;
    private BinaryTreeNode<E>[] splays;
    private ArrayList<BinaryTreeNode<E>> splayChildren;
    
    public BottomUpSemiSplay(){
        super();
        path=new StackArray<BinaryTreeNode<E>>();
        splays=new BinaryTreeNode[3];
        splayChildren=new ArrayList<BinaryTreeNode<E>>();
    }
    public boolean add(E obj) {
        if(obj==null)return false;
        BinaryTreeNode<E> node=new BinaryTreeNode(obj);
        if(rootNode==null){
            rootNode=node;
            size++;
            return true;
        }else{
            boolean ret;
            path.push(rootNode);
            ret=addTo(node,rootNode,true);
            if(ret)size++;
            splay();
            return ret;
        }
    }
    public boolean remove(Object obj) {
        return false;
    }
    public boolean remove(E obj) {
        if(obj==null || rootNode==null)return false;
        boolean isRoot=obj.equals(rootNode.obj);
        BinaryTreeNode<E> rem;
        if(isRoot) rem=rootNode;
        else rem=getFrom(obj,rootNode);
        if(rem==null){while(path.size()!=0)path.pop();  return false;}
        if(rem.leftNode==null){
            if(isRoot)rootNode=rem.rightNode;
            else{
                if(obj.compareTo((E)path.peek().obj)<0) path.peek().leftNode=rem.rightNode;
                else path.peek().rightNode=rem.rightNode;
                if(rem.rightNode!=null)path.push(rem.rightNode);
            }
        }
        if(rem.rightNode==null){
            if(isRoot)rootNode=rem.leftNode;
            else{
                if(obj.compareTo((E)path.peek().obj)<0) path.peek().leftNode=rem.leftNode;
                else path.peek().rightNode=rem.leftNode;
                if(rem.leftNode!=null)path.push(rem.leftNode);
            }
        }
        if(!(rem.leftNode==null || rem.rightNode==null)){
            BottomUpSemiSplay<BinaryTreeNode> hulp=new BottomUpSemiSplay<BinaryTreeNode>();
            hulp.rootNode=rem.leftNode;
            getFrom(obj,rootNode).obj=(E)hulp.last().obj;
            remove((E)hulp.last.obj);
        }
        splay();
        size--;
        return true;
    }
    private BinaryTreeNode getFrom(E obj,BinaryTreeNode<E> par){
        path.push(par);
        if(par.obj.compareTo(obj)<0){
            if(par.leftNode==null)return null;
            if(obj.equals(par.leftNode.obj))return par.leftNode;
            else return getFrom(obj,par.leftNode);
        }else{
            if(par.rightNode==null)return null;
            if(obj.equals(par.rightNode.obj))return par.rightNode;
            else return getFrom(obj,par.rightNode);
        }
    }
    private void splay(){
        if(path.size()<3){
            while(path.size()!=0)path.pop();
            return;
        }
        for(int i=0;i<3;i++){
            splays[i]=path.pop();
            splayChildren.add(splays[i].leftNode);
            splayChildren.add(splays[i].rightNode);
            splays[i].leftNode=null;
            splays[i].rightNode=null;
        }
        int min=0,max=0,mid;
        for(int i=1;i<3;i++){
            if(splays[i].obj.compareTo((E)splays[min].obj)<0)min=i;
            if(splays[i].obj.compareTo((E)splays[max].obj)>0)max=i;
        }
        mid=3-(min+max);
        splays[mid].leftNode=splays[min];
        splays[mid].rightNode=splays[max];
        if(path.peek().obj.compareTo((E)splays[mid].obj)>0) path.peek().leftNode=splays[mid];
        else path.peek().rightNode=splays[mid];
        path.push(splays[mid]);
        for(BinaryTreeNode child : splayChildren) addTo(child,splays[mid],false);
        splay();
    }
    private boolean addTo(BinaryTreeNode<E> node, BinaryTreeNode<E> parent, boolean registerPath){
        if(node==null || node.obj.equals(parent.obj))return false;
        if(node.obj.compareTo((E)parent.obj)<0){ //in dit geval is het toe te voegen element groter als de ouder
            if(parent.leftNode!=null){
                if(registerPath)path.push(parent.leftNode);
                return addTo(node,parent.leftNode,registerPath);
            }else{
                if(registerPath){
                    path.push(parent.leftNode);
                    path.push(node);
                }
                parent.leftNode=node;
            }
        }else{ //in dit geval is het toe te voegen element groter als de ouder
            if(parent.rightNode!=null){
                if(registerPath)path.push(parent.rightNode);
                return addTo(node,parent.rightNode,registerPath);
            }
            if(registerPath){
                path.push(parent.rightNode);
                path.push(node);
            }
            parent.rightNode=node;
        }
        return true;
    }
}