// file:    List.java
// author:  Robert Keller
// purpose: Class List of Poly package
// To test main use: java -cs Poly.List

package Poly;

import java.io.*;
import java.lang.*;
import java.util.*;

/**   
  <pre>
    List is the basic unit for constructing an open linked list of Objects.
    A List can be either :
      an EmptyList, or 
      a  NonEmptyList, in which case it consists of:
           a Object as the first thing in the list
           a rest which is a List.
  </pre>
  <p>
    This class is abstract, even though javadoc might not indicate that.
 **/

public abstract class List
  {

  /**
    *  nil is the empty-list constant
   **/

  public static final List nil = new EmptyList();


  /**
    *  isEmpty() tells whether the List is empty.
   **/

  public abstract boolean isEmpty();


  /**
    *  nonEmpty() tells whether the List is non-empty.
   **/

  public abstract boolean nonEmpty();


  /**
    *  first() returns the first element of a non-empty List.
    * @exception EmptyListException Can't take first of an empty List.
    *
   **/ 

  public abstract Object first() throws EmptyListException;


  /**
    *  rest() returns the rest of a non-empty List.
    * @exception EmptyListException Can't take rest of an empty List.
   **/ 

  public abstract List rest() throws EmptyListException;


  /**
    *  getNonEmpty() gets a NonEmptyList from a List 
    * @exception EmptyListException is thrown if the list is empty after all
   **/ 

  public abstract NonEmptyList getNonEmpty() throws EmptyListException;


  /**
    *  toString converts the list to a string using S expression formatting
   **/ 

  public abstract String toString();


  /**
    *  cons returns a new List given a First and a Rest.
   **/ 

  public static List cons(Object First, List Rest)
    {
    return new NonEmptyList(First, Rest);
    }


  /**
    *  This variant of cons takes a Seed instead of a List as rest, so
    *  the list can be grown incrementally.
   **/ 

  public static List cons(Object First, Seed Rest)
    {
    return new NonEmptyList(First, Rest);
    }


  /**
    *  ListFromEnum makes a List out of any Enumeration.
   **/ 

  public static List ListFromEnum(java.util.Enumeration e)
    {
    if( e.hasMoreElements() )
      return cons(e.nextElement(), ListFromEnum(e));
    else
      return nil;
    }


/**
  *  list(A, B, C, ...) returns a list made of specific elements.
  *  There is one function of each number of elements, up to 16 elements.
 **/

  public static List list()
    {
    return nil;
    }

  public static List list(Object A)
    {
    return cons(A, nil);
    }

  public static List list(Object A, Object B)
    {
    return cons(A, cons(B, nil));
    }

  public static List list(Object A, Object B, Object C)
    {
    return cons(A, cons(B, cons(C, nil)));
    }

  public static List list(Object A, Object B, Object C, Object D)
    {
    return cons(A, cons(B, cons(C, cons(D, nil))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, nil)))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                     Object F)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, nil))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, cons(G, nil)))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H)
    {
    return cons(A, cons(B, 
           cons(C, cons(D, cons(E, cons(F, cons(G, cons(H, nil))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H, Object I)
    {
    return cons(A, cons(B, cons(C, 
           cons(D, cons(E, cons(F, cons(G, cons(H, cons(I, nil)))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H, Object I, Object J)
    {
    return cons(A, cons(B, cons(C, cons(D, 
           cons(E, cons(F, cons(G, cons(H, cons(I, cons(J, nil))))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                Object F, Object G, Object H, Object I, Object J, Object K)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, 
           cons(F, cons(G, cons(H, cons(I, cons(J, cons(K, nil)))))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
          Object F, Object G, Object H, Object I, Object J, Object K, Object L)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, 
           cons(G, cons(H, cons(I, cons(J, cons(K, cons(L, nil))))))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H, Object I, Object J, 
                          Object K, Object L, Object M)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, cons(G, cons(H, 
           cons(I, cons(J, cons(K, cons(L, cons(M, nil)))))))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H, Object I, Object J, 
                          Object K, Object L, Object M, Object N)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, cons(G, cons(H, 
           cons(I, cons(J, cons(K, cons(L, cons(M, cons(N, nil))))))))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H, Object I, Object J, 
                          Object K, Object L, Object M, Object N, Object O)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, cons(G, cons(H, 
           cons(I, cons(J, cons(K, cons(L, cons(M, cons(N, 
           cons(O, nil)))))))))))))));
    }

  public static List list(Object A, Object B, Object C, Object D, Object E, 
                          Object F, Object G, Object H, Object I, Object J, 
                          Object K, Object L, Object M, Object N, Object O, 
                          Object P)
    {
    return cons(A, cons(B, cons(C, cons(D, cons(E, cons(F, cons(G, cons(H, 
           cons(I, cons(J, cons(K, cons(L, cons(M, cons(N, cons(O, 
           cons(P, nil))))))))))))))));
    }


  public int length()
    {
    int len = 0;
    for( Enumeration e = elements(); e.hasMoreElements(); e.nextElement() )
      {
      len++;
      }
    return len;
    }


  /**
    *  elements() returns a ListEnum object, which implements the
    *  interface java.util.Enumeration.
   **/

  public ListEnum elements()
    {
    return new ListEnum(this);
    }


  /**
    *  first(L) returns the first element of its argument.
    * @exception EmptyListException Can't take first of empty List.
   **/

  static public Object first(List L) throws EmptyListException
    {
    return L.first();
    }


  /**
    *  rest(L) returns the rest of its argument.
    * @exception EmptyListException Can't take rest of empty List.
   **/

  static public List rest(List L) throws EmptyListException
    {
    return L.rest();
    }


  /**
    *  reverse(L) returns the reverse of List L.
   **/

  static public List reverse(List L)
    {
    List rev = nil;
    for( Enumeration e = L.elements(); e.hasMoreElements(); )
      {
      rev = cons(e.nextElement(), rev);
      }
    return rev;
    }


  /**
    *  append(L, M) returns a List consisting of the elements of L 
    *  followed by those of M.
   **/

  static public List append(List L, List M)
    {
    if( L.isEmpty() )
      return M;
    try
      {
      return cons(L.first(), append(L.rest(), M));
      }
    catch( EmptyListException e )
      {
      System.err.println("*** should never occur");
      return nil;
      }
    }


  /**
    *  member(A, L) tells whether A is a member of L
   **/

  static public boolean member(Object A, List L) 
    {
    for( Enumeration e = L.elements(); e.hasMoreElements(); )
      if( Arith.equal(e.nextElement(), A) )
        return true;
    return false;
    }


  /**
    *  range(M, N) returns a List of the form (M M+1 .... N)
   **/

  static public List range(long M, long N)
    {
    if( M > N )
      return nil;
    else
      return cons(new Long(M), range(M+1, N));
    }


  /**
    *  range(M, N, S) returns a List of the form (M M+S .... N)
   **/

  static public List range(long M, long N, long S)
    {
    if( S >= 0 )
      return rangeUp(M, N, S);
    else
      return rangeDown(M, N, S);
    }


  /**
    *  rangeUp(M, N, S) is an auxiliary function for range
   **/

  static List rangeUp(long M, long N, long S)
    {
    if( M > N )
      return nil;
    else
      return cons(new Long(M), rangeUp(M+S, N, S));
    }


  /**
    *  rangeDown(M, N, S) is auxiliary function for range
   **/

  static List rangeDown(long M, long N, long S)
    {
    if( M < N )
      return nil;
    else
      return cons(new Long(M), range(M+S, N, S));
    }

/**
  *  second selects the second element of a List.
  * @exception EmptyListException Can't take second of List.
 **/

  public Object second() throws EmptyListException
    {
    return rest().first();
    }


/**
  *  third selects the third element of a List.
  * @exception EmptyListException Can't take third of List.
 **/

  public Object third() throws EmptyListException
    {
    return rest().rest().first();
    }


/**
  *  fourth selects the fourth element of a List.
  * @exception EmptyListException Can't take fourth of List.
 **/

  public Object fourth() throws EmptyListException
    {
    return rest().rest().rest().first();
    }


/**
  *  fifth selects the fifth element of a List.
  * @exception EmptyListException Can't take fifth of List
 **/

  public Object fifth() throws EmptyListException
    {
    return rest().rest().rest().rest().first();
    }


/**
  *  sixth selects the sixth element of a List.
  * @exception EmptyListException Can't take sixth of List
 **/

  public Object sixth() throws EmptyListException
    {
    return rest().rest().rest().rest().rest().first();
    }


/**
  *  nth selects List item by index (0, 1, 2, ...).
  * @exception EmptyListException Can't select from an empty List.
 **/

  public Object nth(long n) throws EmptyListException
    {
    List L = this;
    while( n-- > 0 )
      L = L.rest();
    return L.first();
    }


/**
 *   prefix creates the length-n prefix of a List.
 **/

  public static List prefix(long n, List L)
    {
    if( n <= 0 || L.isEmpty() )
      return nil;
    try
      {
      return cons(L.first(), prefix(n-1, L.rest()));
      }
    catch( EmptyListException e )
      {
      System.err.println("*** should never occur");
      return nil;
      }
    }


/**
 *   coprefix creates the list with all but the length-n prefix of a list
 **/

  public static List coprefix(long n, List L)
    {
    if( n <= 0 || L.isEmpty() )
      return L;
    try
      {
      return coprefix(n-1, L.rest());
      }
    catch( EmptyListException e )
      {
      System.err.println("*** should never occur");
      return nil;
      }
    }


  /**
    *  equals(L, M) tells whether Lists L and M are equal
   **/

  static public boolean equals(List L, List M)
    {
    Enumeration e = L.elements();
    Enumeration f = M.elements();

    while( e.hasMoreElements() && f.hasMoreElements() )
      {
      if( !Arith.equal(e.nextElement(), f.nextElement() ) )
        return false;
      }        
    return e.hasMoreElements() || f.hasMoreElements();
    }


  /**
    *  equals(M) tells whether this List is equal to some other
   **/

  public boolean equals(List M)
    {
    return equals(this, M);
    }



  /**
    *  test program for lists etc.
   **/

  static public void main(String args[])
    {
    try
      {
      System.out.println(nats);

      System.out.println(prefix(10, nats));

      System.out.println(nats);

      System.out.println(prefix(20, nats));

      System.out.println(nats);

      System.out.println(coprefix(10, prefix(20, nats)));

      List sqs = new Incremental(new squares(0));

      System.out.println(prefix(10, sqs));

      System.out.println(sqs);

      System.out.println(prefix(10, primes));


      System.out.println(prefix(10, map(new cube(), range(1, 10))));


      List x = list(new Long(3), new Long(4));

      // x = (3 4)


      x = list(new Long(2), x);

      // x = (2 (3 4))


      x = list(list(new Long(1)), x);

      // x = ((1) (2 (3 4)))


      x = cons(new Long(0), x);

      // x = (0 (1) (2 (3 4)))


      x = append(x, range(5, 9));

      // x = (0 (1) (2 (3 4)) 5 6 7 8 9)


      // print using the default style (S expression)

      System.out.println(x);

      // prints (0 (1) (2 (3 4)) 5 6 7 8 9)


      // print only the third element

      System.out.println(x.third());

      // prints (2 (3 4))


      // print only the fourth element

      System.out.println(x.nth(3));

      // prints 5


      List q = reverse(x);

      System.out.println(q);

      // prints (9 8 7 6 5 (2 (3 4)) (1) 0)


      System.out.println(x.nth(2).equals(q.nth(5)));

      // prints true


      // print first 2 elements

      System.out.println(prefix(2, q));

      // prints (9 8)


      // check out getting enumeration from a list

      System.out.println("Printed using an enumeration:");

      for( Enumeration e = q.elements(); e.hasMoreElements(); )
	{
	System.out.print(e.nextElement() + "  ");
	}
      System.out.println();

      // check out ListFromEnum

      Stack s = new Stack();
      for( int i = 0; i < 20; i++ )
	s.push(new Integer(i));

      List z = ListFromEnum(s.elements());

      System.out.println(z);

      System.out.println(member(new Long(9), z));

      System.out.println("From array: ");

      Object[] a = z.array();

      for( int i = 0; i < a.length; i++ )
        System.out.print(a[i] + " ");

      System.out.println();

      System.out.println(ListFromArray(a));

      List nitt = explode("Now is the time");

      System.out.println(nitt);

      System.out.println(nitt.implode());

      System.out.println(list("foo", "bar", new Long(123)).implode());

      System.out.println("Type in S expressions for echo-ing");

      Tokenizer in = new Tokenizer(System.in);

      Object ob;
      while( (ob = in.nextSexp()) != Tokenizer.eof )
	{
	System.out.println(analysis(ob));
	}
      }
    catch( EmptyListException e)
      {
      System.out.println("EmptyListException caught: " + e.cause);
      }
    catch( argumentTypeException e)
      {
      System.out.println("argumentTypeException caught: " + e.arg 
                       + " expected " + e.classString);
      }
    }

  // Examples:
  // we start the list of nats, so that it will print as (0 ...) rather than
  // just ...

  static public List nats = cons(new Long(0), 
                                 new Incremental(new integers(1)));

  static public List primes = cons(new Long(2), 
                                   new Incremental(new oddprimes()));

  
  /**
    *  analysis produces a string analyzing objects, especially Lists
   **/

  public static String analysis(Object Ob)
    {
    return analysis(Ob, 0);
    }

  String analysis()
    {
    return analysis(0);
    }

  String analysis(int N)
    {
    if( isEmpty() )
      return spaces(N) + "The empty list";
    StringBuffer buff = new StringBuffer();
    buff.append(spaces(N));
    int len = length();
    buff.append("A List consisting of " + len + " element"
              + (len > 1 ? "s" : "") + ": \n");
    List L = this;
    for( Enumeration e = elements(); e.hasMoreElements(); )
      {          
      buff.append(analysis(e.nextElement(), N+1));
      }    
    return buff.toString();
    }

  static String analysis(Object Ob, int N)
    {
    if( Ob instanceof List )
      return ((List)Ob).analysis(N);
    else
      return spaces(N) + Ob.toString() + " (class " 
           + Ob.getClass().getName() + ")\n";
    }

  // spaces is for indentation

  static String spaces(int N)
    {
    StringBuffer buff = new StringBuffer();
    while( N > 0 )
      {
      buff.append("  ");
      N--;
      }
    return buff.toString();
    }


  /**
    * array() returns an array of elements in list
   **/

  public Object[] array()
    {
    Object[] result = new Object[length()];
    int i = 0;
    for( Enumeration e = elements(); e.hasMoreElements(); )
      {
      result[i++] = e.nextElement();
      }
    return result;
    }


  /**
    * ListFromArray makes a list out of an array of objects
   **/

  static List ListFromArray(Object[] array)
    {
    List result = nil;
    for( int i = array.length-1; i >= 0; i-- )
      result = cons(array[i], result);
    return result;
    }


  /**
    * explode(String S) converts a string into a list of Character
   **/

  static List explode(String S)
    {
    List result = nil;
    for( int i = S.length()-1; i >= 0; i-- )
      result = cons(new Character(S.charAt(i)), result);
    return result;
    }


  /**
    * implode() creates a String from a list of items
   **/

  String implode()
    {
    StringBuffer buff = new StringBuffer();
    for( Enumeration e = elements(); e.hasMoreElements(); )
      {
      buff.append(e.nextElement().toString());
      }
    return buff.toString();
    }


  /**
    * map maps an object of class Function over a list returning a List
    * @exception argumentTypeException
   **/

  static List map(Function F, List L) throws argumentTypeException
    {
    if( L.isEmpty() )
      return nil;
    else
      try
        {
        return List.cons(F.apply(L.first()), map(F, L.rest()));
        }
      catch( EmptyListException e )
        {
        System.err.println("should never occur");
        return nil;
        }
    }
  }  // class List


  /**
    * Function is an interface defining the function argument to map
    * @exception argumentTypeException
   **/

interface Function 
  {
  Object apply(Object x) throws argumentTypeException;
  }



// Examples of creating incremental lists

// squares does not reuse the Growable, although it could in principal

class squares extends Growable
  {
  long n;
  squares(long n)
    {
    this.n = n;
    }

  public Object grow()
    {
    return List.cons(new Long(n*n), new Incremental(new squares(n+1)));
    }
  }


// integers reuses the Growable

class integers extends Growable
  {
  long n;
  integers(long n)
    {
    this.n = n;
    }

  public Object grow()
    {
    Long value = new Long(n); 
    n++;
    return List.cons(value, new Incremental(this));
    }
  }


// oddprimes is the list of primes (3 5 7 11 ... )

class oddprimes extends Growable
  {
  long n;

  oddprimes()
    {
    this.n = 3;
    }

  public Object grow()
    {
loop:
    for( ; ; n+=2 )
      {
      for( Enumeration e = List.primes.elements(); ; )
        {
        long trial = (((Long)(e.nextElement())).longValue());
        if( n % trial == 0 )
          {
          continue loop;
          }
        if( trial*trial > n )
          break loop;
        }
      }
    Long first = new Long(n);
    n+=2;
    return List.cons(first, new Incremental(this));
    }
  }



class cube implements Function 
  {
  public Object apply(Object N) throws argumentTypeException
    {
    return Arith.multiply(N, Arith.multiply(N, N));
    }
  }