package listFW.visitor;

import listFW.*;

/**
 * Moves the minimum element from a list of Integer to the front.
 * Uses SIDE-EFFECT to accumulate minimum: non-functional programming!!!
 * @author Dung X. Nguyen
 * @since Copyright: Copyright (c) 2005 by DXN - All rights reserved
 */
public class MinFront2 implements IListAlgo {

    private Integer _accMin;  // accumulated min.
    private IListFactory _fact;

    public MinFront2(IListFactory f) {
        _fact = f;
    }

    public Object emptyCase(IEmptyList L, Object... inp) {
        return L;
    }

    public Object nonEmptyCase(INEList L, Object... inp) {

        // We assign _accMin the first of L as a candidate for minimum:
        _accMin = (Integer)L.getFirst();
        /**
        * Let us consider the set S of all elements in L that precede L.
        * S is clearly empty.  At this point we have established the following:
        * _accMin is an element of L and is smaller than all elements of S.
        * We now call on an anonymous helper to operate on L in order to find
        * the minimum and remove it from L.  This helper will recursively
        * traverse L to the end in order to obtain the minimum, save it in
        * _accMin and reconstruct the host list L without the minimum on its way
        * back from the recursive list traversal.
        */
        IList withoutMin = (IList)L.execute(new IListAlgo() {

            /**
            * Note: when L executes this helper, this case is called since L is
            * not empty.  Thus for the first call to this method, h is L.
            * We update _accMin to ensure that it is an element of L and is the
            * minimum of all elements in L that precedes the rest of the host
            * parameter h.  Then we recursively call this helper on h.getRest()
            * to save the minimum in _accMin and create a copy of h.getRest()
            * that does not contain _accMin.
            */
            public Object nonEmptyCase(INEList h, Object... nu) {
                Integer first = (Integer)h.getFirst();
                if (first < _accMin) {
                    _accMin = first;
                }
                /**
                * At this point, we have established the following invariant:
                * _accMin is an element of L and is the minimum of all elements
                * in L that precedes h.getRest().
                */
                IList accList = (IList)h.getRest().execute(this);
                /**
                * By induction, _accMin is now the minimum of the whole outer
                * host list L, and accList is a copy of h.getRest() that does
                * not contain _accMin.
                */
                if (!first.equals(_accMin)) {
                    accList = _fact.makeNEList(first, accList);
                }
                // accList is now a copy of the host h without _accMin.
                return accList;
                /**
                * As noted earlier, L.execute(...) calls nonEmptyCase() since
                * L is not empty.  Thus the first call to nonEmptyCase() is the
                * call with L as the value for the host parameter h.  So, when
                * we return from this first call, accList is a copy of L without
                * the minimum stored in _accMin.
                */
            }

            /**
            * This method is only called from inside of the nonEmptyCase()
            * method.  The empty host parameter h marks the end of the outer
            * host list L.
            * _accmin is thus the minimum. The empty list is thus a copy of
            * the outer host list L from the current list (empty) to the end
            * that does not contain _accMin.
            */
            public Object emptyCase(IEmptyList h, Object... nu) {
                return h;
            }
        });  
        /**
        * "Cons" the minimum to the front of the copy of the host that does not
        *  contain this minimum.
        */
        return _fact.makeNEList(_accMin, withoutMin);
    }

}