package plp.collection; /** * A fonctional kind of list "a la Scheme". * car denotes the first element of a list, * cdr the list minus the first element. */ public class SList { private Object car; private SList cdr; private static final Object EMPTY = new Object(); /** * The empty list. */ public static final SList EMPTY_SLIST = new SList(); private SList() { car = EMPTY; cdr = null; } private void checkNonEmpty(String message) { if (empty()) throw new Error(message); } /** * A cdr cannot be null (null cannot be a SList, even to represent * the empty list). */ public SList(Object car, SList cdr) { if (cdr == null) throw new Error("Cannot used null as cdr"); this.car = car; this.cdr = cdr; } /** Test if the list is EMPTY_SLIST. */ public boolean empty() { return (car == EMPTY); } /** * Cannot be used on EMPTY_LIST. */ public Object car() { checkNonEmpty("Calling car() on empty list"); return car; } /** * Cannot be used on EMPTY_LIST. */ public SList cdr() { checkNonEmpty("Calling cdr() on empty list"); return cdr; } public int length() { return empty()? 0 : 1 + cdr().length(); } public SList append(SList l2) { return empty()? l2 : new SList(car(), cdr().append(l2)); } /* This procedure appends this.reverse() with l2. Its main interest is that it is tail recursive. */ private SList rappend(SList l2) { return empty()? l2 : cdr().rappend(new SList(car(), l2)); } public SList reverse() { return rappend(EMPTY_SLIST); } public String toString() { String s = "("; if (!empty()) { s += car(); for (SList l = this.cdr(); !l.empty(); l = l.cdr()) s += " " + l.car(); } s += ")"; return s; } }