package treeNAlgo;

import treeN.*;

/**
 * DeleteNAlgo  -  deletes the supplied parameter from a TreeN
 *  preserving balance with a maximum number of elements per node.
 * @dependency treeNAlgo.ILambda instantiates
 */
public class DeleteNAlgo implements ITreeNAlgo {

    /**
	 * Splits child upwards if its state > order and splices it into
	 * its parent.  The supplied param is an ISpliceCmd used to do the
	 * splicing.
	 * @SBGen Variable (helper,,,128)
	 */
    private SplitUpAndApply splitUpAndSplice;

    /**
     * Constructor for the class
     * @param order -- the max possible number of elements in a node
     */
    public DeleteNAlgo(int order) {
	splitUpAndSplice = new SplitUpAndApply(order);
    }

    public Object caseAt(int s, final TreeN host, final Object key) {

	switch(s) {
	case 0: {
		return key;  // no-op for empty case
	    }

	case 1: {
		collapse2Node(host);
	    }// fall through to default case

	default: {
		return host.execute(new ITreeNAlgo() {
			public Object caseAt(int s_help,
					     final TreeN h, Object cmd) {
			    switch(s_help) {
			    case 0: {
				    return key;
				}
			    case 1: {
				    if (h.getDat(0).equals(key)) {
					System.out.println("Found data element!");
					Object d = h.getDat(0); // get key
					h.splitDownAt(0); //transition to empty
					return d;
				    }
				    else {
					System.err.println("Element "+ key +" not in tree!");
					((ILambda)cmd).apply(h);
					return h.getDat(0);
				    }
				}
			    default : {
				    final int x = findX(h,
							s_help,
							((Integer)key).intValue());
//				    h.splitDownAt(x);
//				    TreeN newChild = collapse2Node(h.getChild(x)); // push data down
				    TreeN newChild = collapse2Node(h.splitDownAt(x).getChild(x)); // push data down
				    Object result = newChild.execute(this,
								     new ILambda() {
					    /**
					     * @param child a TreeN subtree of h.
					     */
					    public Object apply(Object child) {
						return h.spliceAt(x,
								  (TreeN)child);
					    }
					}
				    );
				    h.execute(splitUpAndSplice, cmd);
				    return result;
				}
			    }
			}
		    }
		    , new ILambda() {
			/**
			 * @param child not used.
			 */
			public Object apply(Object child) {
			    return host;
			}
		    }
		);
	    }
	}
    }

    //------ Utility methods ------------------------------------------------------

    /**
     * Utility method to collapses a 2-node tree by splicing it with
     * its two children.
     * @param t -- must be a 2-node tree!
     */
    private final TreeN collapse2Node(TreeN t) {
	t.spliceAt(1,t.getChild(1));
	t.spliceAt(0,t.getChild(0));
	return t;
    }

    /**
     * Utility method that finds the index of the data element that
     * either matches the supplied key or is the first element bigger
     * than the key.
     * @param t - an TreeN
     * @param state - the state of the tree
     * @param k - the key to locate
     * @return - the index of the data element such that if k exists in the
     * tree, it is guaranteed to be in the 2-node tree
     * defined by the data at the index and its left and right children.
     */
    private final int findX(TreeN t, int state, int k) {
	for(int i = 0;i< state; i++) if(t.getDat(i).intValue()>=k) return i;
	return state-1;
    }
}