00001: package clogs.util;
00002:
00003: import java.util.HashSet;
00004: import java.util.Iterator;
00005: import java.util.NoSuchElementException;
00006:
00007:
00008: public abstract class List<A> implements Iterable<A>
00009: {
00010: public static <A> List<A> nil ()
00011: {
00012: return new ListNil<A> ();
00013: }
00014:
00015:
00016: public static <A> List<A> singleton (A head)
00017: {
00018: return List.<A>nil ().cons (head);
00019: }
00020:
00021:
00022: public List<A> cons (A head)
00023: {
00024: return new ListCons<A> (head, this);
00025: }
00026:
00027:
00028: public List<A> snoc (A last)
00029: {
00030: return this.concat (singleton (last));
00031: }
00032:
00033:
00034: public A get (int index)
00035: {
00036: int i = index;
00037: List<A> l = this;
00038: while ((i > 0) && (!l.isNil ())) {
00039: i--;
00040: l = l.tail ();
00041: }
00042:
00043: if ((i != 0) || l.isNil ()) {
00044: throw new IndexOutOfBoundsException
00045: ("Attempt to access element " + i + " in list of length " + size () + "\n" + this);
00046: }
00047:
00048: return l.head ();
00049: }
00050:
00051:
00052: public abstract boolean isNil ();
00053: public abstract int size ();
00054:
00055: public abstract A head () throws EmptyListException;
00056: public abstract List<A> tail () throws EmptyListException;
00057:
00058: public abstract List<A> concat (List<A> l);
00059: public abstract List<A> reverse ();
00060: abstract List<A> reverseAux (List<A> end);
00061:
00062:
00063: public String toString ()
00064: {
00065: StringBuffer sb = new StringBuffer ();
00066:
00067: if (isNil ()) {
00068: return ("[]");
00069: }
00070:
00071: sb.append ("[ ");
00072: List l = this;
00073: boolean first = true;
00074: while (!l.isNil ()) {
00075: if (first) {
00076: first = false;
00077: } else {
00078: sb.append (", ");
00079: }
00080: sb.append (l.head ());
00081: l = l.tail ();
00082: }
00083: sb.append (" ]");
00084:
00085: return sb.toString ();
00086: }
00087:
00088:
00089: // Returns a duplicate in the list (upto .equals ()) if there is one, otherwise returns null.
00090: public A findDuplicate ()
00091: {
00092: HashSet<A> set = new HashSet<A> ();
00093: List<A> list = this;
00094: while (!list.isNil ()) {
00095: A o = list.head ();
00096: if (!set.contains (o)) {
00097: set.add (o);
00098: } else {
00099: return o;
00100: }
00101: list = list.tail ();
00102: }
00103: return null;
00104: }
00105:
00106:
00107: class ListIteratorImpl<A> implements Iterator<A>
00108: {
00109: private List<A> contents;
00110:
00111: ListIteratorImpl (List<A> contents)
00112: {
00113: this.contents = contents;
00114: }
00115:
00116: public boolean hasNext ()
00117: {
00118: return !contents.isNil ();
00119: }
00120:
00121: public A next ()
00122: {
00123: if (contents.isNil ()) {
00124: throw new NoSuchElementException ();
00125: } else {
00126: A result = contents.head ();
00127: contents = contents.tail ();
00128: return result;
00129: }
00130: }
00131:
00132: public void remove ()
00133: {
00134: throw new UnsupportedOperationException ();
00135: }
00136: }
00137:
00138:
00139: public Iterator<A> iterator ()
00140: {
00141: return new ListIteratorImpl<A> (this);
00142: }
00143:
00144:
00145: // Applies fun.f to every object in the list to create a new list of the results.
00146: // If fun.f returns null, the result is discarded (a combined map/filter).
00147: public <B> List<B> map (Function<A,B> fun)
00148: {
00149: if (isNil ()) {
00150: return nil ();
00151: } else {
00152: B newHead = fun.f (head ());
00153: List<B> newTail = tail ().map (fun);
00154: if (newHead == null) {
00155: return newTail;
00156: } else {
00157: return newTail.cons (newHead);
00158: }
00159: }
00160: }
00161:
00162:
00163: public boolean contains (A o)
00164: {
00165: List<A> list = this;
00166: while (!list.isNil ()) {
00167: if (o.equals (list.head ())) {
00168: return true;
00169: }
00170: list = list.tail ();
00171: }
00172: return false;
00173: }
00174: }
00175:
00176:
00177:
|
