package treeNAlgo;

import treeN.*;

/**
 * InsertNAlgo  -  inserts the supplied parameter (key) into a TreeN
 *  preserving balance with a maximum number of elements per node.
 * @dependency treeNAlgo.ILambda instantiates
 */
public class InsertNAlgo implements ITreeNAlgo {

    /**
	 * Splits host upwards if its state > order and splices it into
	 * its parent.    The supplied param is an ISpliceCmd used to do the
	 * splicing.
	 */
	private SplitUpAndApply splitUpAndSplice;

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


    public Object caseAt(int i, final TreeN host, final Object param) {
	switch(i) {
	case 0: {
		return host.spliceAt(0, new TreeN((Integer) param));
	    }

	default: {
		host.execute(new ITreeNAlgo() {
			public Object caseAt(int idx,
					     final TreeN h, final Object cmd) {
			    switch(idx) {
			    case 0: {//empty case: instantiate new tree and splice into parent
				    /**
				     * At this point the host is an empty subtree of some parent
				     * tree. Because the parent tree is balanced, it must be a
				     * leaf!
				     */
				    return ((ILambda)cmd).apply(new TreeN((Integer)param));
				}


			    default: {
				    final int[] x={
					0
				    };  // trick to get past restrictions on final
				    // x[0] is the index of insertion location.
				    for(; x[0] < idx; x[0]++) {// find insertion location
					int d = h.getDat(x[0]).intValue();
					if (d >= ((Integer)param).intValue()) {
					    if (d == ((Integer)param).intValue())
						return h; // no duplicate keys allowed
					    else break;
					}
				    }
				    h.getChild(x[0]).execute(this,
							     new ILambda() {
					    /**
					     * @param child a TreeN subtree of h.
					     */
					    public Object apply(Object child){
						// splice child tree into parent
						return h.spliceAt(x[0],
								  (TreeN) child);
					    }
					}
				    );
				    // split up host if necessary
				    return h.execute(splitUpAndSplice, cmd);
				}
			    }
			}
		    }
		    , new ILambda() {// say something meaningful here
			/**
			 * @param child not used.
			 */
			public Object apply(Object child){
			    return host;  //no-op for this one
			}
		    }
		);
		return host;
	    }
	}
    }
}