import listFW.*;

/**
 * Inserts an Integer into an ordered host list, assuming the host list contains
 * only Integer objects.
 */
public class InsertInOrder implements IListAlgo {

    public static final InsertInOrder Singleton = new InsertInOrder();
    private InsertInOrder() {
    }

    /**
     * This is easy, don't you think?
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object emptyCase(MTList host, Object... inp) {
        return new NEList(inp[0], host);
    }

    /**
     * Delegate (to recur)!
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object nonEmptyCase(NEList host, Object... inp) {
        int n = (Integer)inp[0];
        int f = (Integer)host.getFirst();
        return n < f ?
                new NEList(inp[0], host):
                new NEList(host.getFirst(), (IList)host.getRest().execute(this, inp[0]));
    }
}

package listFW;

/**
 * Represents the abstract behavior of the immutable list structure.
 * A list intrinsically "knows" how to execute an algorithm on itself.
 */
interface IList {
    Object execute(IListAlgo algo, Object... inp);
}

package listFW;

/**
 * Represents the immutable empty list.
 * The empty list has no well-defined structural behavior:
 * it has no first and no rest.
 */
interface IMTList extends IList {
}

package listFW;

/**
 * Represents the immutable non-empty list.
 * An immutable non-empty list has a data object called first, and an
 * isomorphic subcomponent called rest.  Its structural behavior
 * provides access to its internal data (first) and substructure (rest).
 */
interface INEList extends IList {
    /**
     * "Gettor" method for the list's first.
     * @return this INElist's first element.
     */
    Object getFirst();

    /**
     * "Gettor" method for the list's rest.
     * @return this INElist's rest.
     */
    IList getRest();
}

package listFW;

/**
 * Abstract factory to manufacture IMTList and INEList.
 */
interface IListFactory {
    /**
     * Creates an empty list.
     * @return an IMTList object.
     */
    IMTList makeEmptyList();

    /**
     * Creates a non-empty list containing a given first and a given rest.
     * @param first a data object.
     * @param rest != null, the rest of the non-empty list to be manufactured.
     * @return an INEList object containing first and rest
     * @exception IllegalArgumentException if rest is null.
     */
    INEList makeNEList(Object first, IList rest);
}

import listFW.*;

/**
 * Inserts an Integer into an ordered host list, assuming the host list contains
 * only Integer objects.  Has no knowledge of how IList is implemented.  Must
 * make use of a list factory (IListFactory) to create IList objects instead of
 * calling the constructors of concrete subclasses directly.
 */
public class InsertInOrderWithFactory implements IListAlgo {

    private IListFactory _listFact;

    public InsertInOrderWithFactory(IListFactory lf) {
        _listFact = lf;
    }

    /**
     * Simply makes a new non-empty list with the given inp parameter as first.
     * @param host an empty IList.
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object emptyCase(IMTList host, Object... inp) {
        return _listFact.makeNEList(inp[0], host);
    }

    /**
     * Recur!
     * @param host a non-empty IList.
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object nonEmptyCase(INEList host, Object... inp) {
        int n = (Integer)inp[0];
        int f = (Integer)host.getFirst();
        return n < f ?
                _listFact.makeNEList(inp[0], host):
                _listFact.makeNEList(host.getFirst(),
                                    (IList)host.getRest().execute(this, inp[0]));
    }
}

package listFW.factory;

import listFW.*;

/**
 * Manufactures concrete IMTList and INEList objects.  Has only one
 * instance referenced by CompositeListFactory.Singleton.
 * MTList and NEList are static nested classes and hidden from all external
 * client code.  The implementations for MTList and NEList are the same as
 * before but completely invisible to the outside of this factory.
 */
public class CompositeListFactory implements IListFactory {

    /**
     * Note the use of private static.
     */
    private static class MTList implements IMTList {
        public final static MTList Singleton = new MTList ();
        private MTList() {
        }

        final public Object execute(IListAlgo algo, Object... inp) {
            return algo.emptyCase(this, inp);
        }

        public String toString() {
            return "()";
        }
    }

    /**
     * Note the use of private static.
     */
    private static class NEList implements INEList {
        private Object _first;
        private IList _rest;

        public NEList(Object dat, IList rest) {
            _first = dat;
            _rest = rest;
        }

        final public Object getFirst() {
            return _first;
        }

        final public IList getRest() {
            return _rest;
        }

        final public Object execute(IListAlgo algo, Object... inp) {
            return algo.nonEmptyCase(this, inp);
        }


        public String toString() {
            return (String)ToStringAlgo.Singleton.nonEmptyCase(this);
        }
    }

    /**
     * Singleton Pattern
     */
    public static final CompositeListFactory Singleton = new CompositeListFactory();
    private CompositeListFactory() {
    }

    /**
     * Creates an empty list.
     * @return an IMTList object.
     */
    public IMTList makeEmptyList() {
        return MTList.Singleton;
    }

    /**
     * Creates a non-empty list containing a given first and a given rest.
     * @param first a data object.
     * @param rest != null, the rest of the non-empty list to be manufactured.
     * @return an INEList object containing first and rest
     */
    public INEList makeNEList(Object first, IList rest) {
        return new NEList(first, rest);
    }
}

package listFW.visitor.test;
import listFW.*;
import listFW.factory.*;
import listFW.visitor.*;

import junit.framework.TestCase;

/**
 * A JUnit test case class.
 * Every method starting with the word "test" will be called when running
 * the test with JUnit.
 */
public class Test_InsertInOrderWithFactory extends TestCase {
  

  public void test_ordered_insert() {
    IListFactory fac = CompositeListFactory.Singleton;
    IListAlgo algo = new InsertInOrderWithFactory(fac);
    
    IList list0 = fac.makeEmptyList();   
    assertEquals("Empty list", "()", list0.toString());
    
    IList list1 = (IList) list0.execute(algo, 55);
    assertEquals("55->()", "(55)", list1.toString());

    IList list2 = (IList) list1.execute(algo, 30);
    assertEquals("30->(55)", "(30, 55)", list2.toString());
    
    IList list3 = (IList) list2.execute(algo, 100);
    assertEquals("100 -> (30, 55)", "(30, 55, 100)", list3.toString());
    
    IList list4 = (IList) list3.execute(algo, 45);
    assertEquals("45->(30, 55, 100)", "(30, 45, 55, 100)", list4.toString());
    
    IList list5 = (IList) list4.execute(algo, 60);
    assertEquals("60 -> (30, 45, 55, 100)", "(30, 45, 55, 60, 100)", list5.toString()); 
  }  
}