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: