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: