Rice University Comp 212 - Intermediate Programming

Spring 2008

Lecture #19: The Immutable Generic List Framework

Today's Menu

Finish lecture #18 on Java generics.
Go through the code for the Generic Immutable List Framework:
- Source code
- Zipped file

public interface IList<E> {
    public abstract <R,P> R execute(IListAlgo<? super E, R, P> algo, P ... inp);
}

public interface IMTList<E> extends IList<E> {
}

public interface INEList<E> extends IList<E> {

   public abstract E getFirst();

   public abstract IList<? extends E> getRest();
}

/**
* A visitor to (algorithm on) an IList<T> where T is a subclass of E
* Also parameterized by it return type R and input parameter type P.
*/
public interface IListAlgo<E,R,P> {

    public abstract R emptyCase(IMTList<? extends E> host, P ... inp);

    public abstract R nonEmptyCase(INEList<? extends E> host, P ... inp);
}

public interface IListFactory<E> {
    public abstract IMTList<E> makeEmptyList();

    public abstract INEList<E> makeNEList(E first, IList<? extends E> rest);
}

Visitor Examples:

public class ToStringAlgo implements IListAlgo<Object, String, Object> {

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

    /**
    * Returns "()".
    */
    public String emptyCase(IMTList<? extends Object> host, Object ... inp) {
        return "()";
    }

    /**
    * Passes "(" + first to the rest of IList and asks for help to complete the computation.
    */
    public String nonEmptyCase(INEList<? extends Object> host, Object ... inp) {
        return host.getRest().execute(ToStringHelper.Singleton, "(" + host.getFirst());
    }
}

/**
* Helps ToStringAlgo compute the String representation of the rest of the list.
*/
class ToStringHelper implements IListAlgo<Object, String, String> {
    public static final ToStringHelper Singleton = new ToStringHelper();
    private ToStringHelper() {
    }

    /**
    * Returns the accumulated String + ")".
    * At end of list: done! 
    */
    public String emptyCase(IMTList<? extends Object> host, String ... acc) {
        return acc[0] + ")";
    }

    /**
    * Continues accumulating the String representation by appending ", " + first to acc
    * and recur!
    */
    public String nonEmptyCase(INEList<? extends Object> host, String ... acc) {
        return host.getRest().execute(this, acc[0] + ", " + host.getFirst());
    }
}

/**
* Copies an IList<T> using the supplied IListFactory<T>
*/
public class CopyList2<T> implements IListAlgo<T,IList<T>, Object> {
    private IListFactory<T> fac;

    public CopyList2(IListFactory<T> fac) {
        this.fac = fac;
    }  

    public IMTList<T> emptyCase(IMTList<? extends T> host, Object ... nu) {
        return fac.makeEmptyList();
    }

    public INEList<T> nonEmptyCase(INEList<? extends T> host, Object ... nu) {
        return fac.makeNEList( host.getFirst(), host.getRest().execute(this));
    }
}

/**
* Copies an IList<T> using the an IListFactory<T> supplied as an input parameter.
*/
public class CopyList3<T> implements IListAlgo<T,IList<T>, IListFactory<?>> {

    public IMTList<T> emptyCase(IMTList<? extends T> host, IListFactory<?> ... fac) {
        return ((IListFactory<T>)fac[0]).makeEmptyList(); // Generates "unchecked cast" warning
    }

    public INEList<T> nonEmptyCase(INEList<? extends T> host, IListFactory<?> ... fac) {
        return ((IListFactory<T>)fac[0]).makeNEList( host.getFirst(), host.getRest().execute(this, fac)); 
        // Generates "unchecked cast" warning
    }
}

Last Revised Monday, 18-Feb-2008 12:42:09 CST