package aima.util;
import java.io.StreamTokenizer;
import java.io.Reader;
import java.io.StringReader;
import java.text.NumberFormat;
import java.text.ParsePosition;
/**
 * The Expression class provides static methods to facilitate JAVA 
 * programming in terms of LISP-like atomic and dotted-pair expressions.
 * While the Expression class (currently) extends the <code>
 * DottedPair </code> class, this is done as a mere convenience so that
 * one can do the nicer looking:
 * <pre>
 *    Expression expr    = new Expression("a",new Integer(5));
 *    String     aString = (String) Expression.first(expr);
 * </pre>
 * rather than:
 * <pre>
 *    DottedPair dp      = new DottedPair("a",new Integer(5));
 *    String     aString = (String) Expression.first(dp);
 * </pre>
 * The idea here is that the <code>Expression</code> class, with its
 * associated static methods creates the illusion that it can
 * manipulate atomic as well as dotted pair objects, without accentuating
 * the fact that non-atomic objects are actually implemented in terms
 * of the <code>DottedPair</code> class.   
 *
 * Other than the constructor method, all the other methods are 
 * <code>static</code>, to conceptually keep separate the generic
 * atom/dotted-pair manipulation methods from the actual dotted-pair
 * implementation in the <code>DottedPair</code> class.  An <em>
 * atom </em> in this implementation is any JAVA <code>Object</code>
 * that is neither an instance of the <code>DottedPair</code> class
 * nor is the special, unique (nil-like) object used to terminate
 * <code>DottedPair</code>'s and to represent the empty list.
 *
 * The static methods of this class expect that run-time exceptions
 * will be thrown if they are called inappropriately.  For example:
 * <pre>
 *    Integer    atom1  = new Integer(1);
 *    Integer    atom2  = new Integer(2);
 *    Expression expr12 = new Expression(atom1,atom2);
 *    Object     good   = Expression.first(expr12); // OK
 *    Object     bad    = Expression.first(atom1);  // Runtime error
 * </pre>
 * The last statement will throw an error because you cannot take the
 * first element of an atom.  Currently this error is a JAVA mis-casting
 * runtime error, but perhaps in the future we may define an
 * <code>Expression</code> specific error to throw.
 *
 * @author Michael S. Braverman
 * @see    DottedPair  
 */
public class Expression extends DottedPair {
  /**
   * Creates a new compound (dotted) expresssion.
   *
   * @param car the Object to go to the left of the "dot"
   * @param cdr the Object to go to the right of the "dot"
   *
   * @see DottedPair
   */
  public Expression (Object car, Object cdr) {
    super(car,cdr);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>reuse</code> method,
   * assuming that compObj is a compound <code>DottedPair</code> object.
   *
   * @return the result of DottedPair.reuse
   * @param car see first parameter of DottedPair.reuse
   * @param cdr see second parameter of DottedPair.reuse
   * @param compObj the object on which to invoke DottedPair.reuse(car,cdr)
   * @exception ClassCastException Thrown at runtime if
   * compObj </code> is not a compound <code>DottedPair</code>
   * object.
   * @see DottedPair#reuse
   */
  static public DottedPair reuse (Object car, Object cdr, Object compObj) 
    throws ClassCastException {
    return ((DottedPair) compObj).reuse(car,cdr);
  }

  /**
   * Tells whether or not the given object is the unique "NULL" object
   * that represents the empty compound expression (which is used to
   * terminate compound expressions that are true lists).
   *
   * @return true, iff <code>obj</code> is the NULL object.
   * @param obj Object to test.
   * @see DottedPair#getNull
   */
  static public boolean isNull(Object obj) {
    return (obj == getNull());
  }

  /**
   * Tells whether or not the given object is considered an atomic
   * expression.  Analogous to the <code>atom</code> predicate in
   * LISP.
   *
   * @return true, iff <code>obj</code> is neither a dotted compound
   * expression, nor the special, unique NULL (empty) compound object.
   * @param obj Object to test.
   * @see DottedPair#isAtomic
   * @see DottedPair#getNull
   */
  static public boolean isAtomic(Object obj) {
    // Note: we only cast when it is safe to do so
    return (!(obj instanceof DottedPair) || 
	      ((DottedPair) obj).isAtomic());
  }

  /**
   * Tells whether or not the given object is considered a true compound
   * expression.  Analogous to the <code>consp</code> predicate in
   * LISP.
   *
   * @return true, iff <code>obj</code> is a dotted compound but
   * not the special empty NULL compound expression.
   * @param obj Object to test.
   * @see DottedPair#isTrueCompound
   * @see DottedPair#getNull
   * @see #isCompound
   */
  static public boolean isTrueCompound(Object obj) {
    return ((obj instanceof DottedPair) &&
	    ((DottedPair) obj).isTrueCompound());
  }

  /**
   * Tells whether or not the given object is considered a compound
   * expression.  Analogous to the <code>listp</code> predicate in
   * LISP.
   *
   * @return true, iff <code>obj</code> is a compound expression,
   * including the special empty NULL compound expression.
   * @param obj Object to test.
   * @see DottedPair
   */
  static public boolean isCompound(Object obj) {
    return (obj instanceof DottedPair);
  }

  /**
   * Tells whether or not the given objects are equal, 
   * analogous to the <code>equal</code> predicate in
   * LISP.
   *
   * @return true, iff <code>obj1</code> and <code>obj2</code>
   * are equal in the LISP equal sense.
   * @param obj1 first Object to compare.
   * @param obj2 second Object to compare.
   * @see DottedPair#equals
   */
  static public boolean equals(Object obj1, Object obj2) {
    if (isAtomic(obj1) || isAtomic(obj2)) {
      return obj1.equals(obj2);
    } else {
      DottedPair obj1DP = (DottedPair) obj1;
      DottedPair obj2DP = (DottedPair) obj2;
      return (obj1DP.car().equals(obj2DP.car()) &&
	      obj1DP.cdr().equals(obj2DP.cdr()));
    }
  }

  /**
   * Tells whether or not the given objects are equal, 
   * analogous to the <code>eql</code> predicate in
   * LISP. 
   *
   * @return true, iff <code>obj1</code> and <code>obj2</code>
   * are equal in the LISP eql sense.
   * @param obj1 first Object to compare.
   * @param obj2 second Object to compare.
   * @see DottedPair#eql
   */
  static public boolean eql(Object obj1, Object obj2) {
    if (isAtomic(obj1) && isAtomic(obj2)) {
      return obj1.equals(obj2);
    } else {
      return (obj1 == obj2);
    }
  }

  /**
   * Invokes the <code>DottedPair</code> <code>assoc</code> method,
   * assuming that assocList is a compound <code>DottedPair</code> object,
   * in the form of an association list.
   *
   * <p>
   * Note: Should one day implement a version of this code that takes
   * an arbitrary predicate, rather than assuming <code>eql</code>.
   * Similarly, should possibly take a function that directs the
   * search to more than just the first element of each pair.
   *
   * @return The pair whose first element is <code>eql</code> to the
   * given target, or the special Null object if no matching element
   * is found.
   * @param target the <code>Object</code> for which to search.
   * @param assocList the association list to scan.
   * @exception ClassCastException Thrown at runtime if 
   * <code>assocList</code> is not a compound <code>DottedPair</code>
   * object. 
   * @see DottedPair#assoc
   * @see #eql
   */
  static public DottedPair assoc(Object target, Object assocList)
    throws ClassCastException {
    return ((DottedPair) assocList).assoc(target);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>length</code> method,
   * assuming that argument <code>list</code> is a compound
   * <code>DottedPair</code> object, and returns
   * the number of top-level elements of this list.
   *
   * @return The number of top-level elements of this list.
   * @param listObj a true (Null terminated) list
   * @exception ClassCastException Thrown at runtime if this
   * is not a <code>DottedPair</code> that is also a true list
   * (ends in a non-Null atomic <code>Object</code>).
   * @see DottedPair#getNull
   * @see DottedPair#length
   */
  static public int length(Object listObj)
    throws ClassCastException {
    return ((DottedPair) listObj).length();
  }

  /**
   * Invokes the <code>DottedPair</code> <code>member</code> method,
   * assuming that searchList is a compound <code>DottedPair</code> object,
   * in the form of a true list.
   *
   * <p>
   * Note: Should one day implement a version of this code that takes
   * an arbitrary predicate, rather than assuming <code>eql</code>.
   *
   * @return The sublist of the given <code>searchList</code> whose first
   * element is <code>eql</code> to the given <code>target</code>.
   * @param target the <code>Object</code> for which to search.
   * @param searchList the list to search.
   * @exception ClassCastException Thrown at runtime if 
   * <code>searchList</code> is not a compound <code>DottedPair</code>
   * object. 
   * @see DottedPair#member
   * @see #eql
   */
  static public DottedPair member(Object target, Object searchList)
    throws ClassCastException {
    return ((DottedPair) searchList).member(target);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>nthcdr</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object,
   * in the form of a true list.
   *
   * @return The result of applying <code>cdr</code> the specified number
   * of times.
   * @param n the number of times to apply <code>cdr</code>
   * @param listObj the initial list.
   * @exception ClassCastException Thrown at runtime if 
   * <code>searchList</code> is not a compound <code>DottedPair</code>
   * object. 
   * @see DottedPair#nthcdr
   */
  static public DottedPair nthcdr(int n,  Object listObj)
    throws ClassCastException {
    return ((DottedPair) listObj).nthcdr(n);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>elt</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object,
   * in the form of a true list.
   *
   * @return The element of the list found at the given (0-based) index.
   * @param listObj the list.
   * @param index the (0-based) index.
   * @exception ClassCastException Thrown at runtime if 
   * <code>listObj</code> is not a compound <code>DottedPair</code>
   * object. 
   * @exception RuntimeException Thrown if <code>index</code> is out
   * of bounds (negative or beyond the end of the list).
   * @see DottedPair#elt
   */
  static public Object elt(Object listObj, int index)
    throws ClassCastException, RuntimeException {
    return ((DottedPair) listObj).elt(index);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>subseq</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object.
   *
   * @return a top level copy of the indicated subset of the given list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @exception RuntimeException Thrown if given indices are beyond
   * the bounds of the list.
   * @param listObj the list whose subset is to be copied.
   * @param start the (0-based) start index.
   * @param end the (0-based) end index.
   * @see DottedPair#subseq
   */
  static public DottedPair subseq(Object listObj, int start, int end)
    throws ClassCastException, RuntimeException {
    return ((DottedPair) listObj).subseq(start,end);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>subseq</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object.
   *
   * @return a top level copy of the indicated suffix of the given list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @exception RuntimeException Thrown if given start index is beyond
   * the bounds of the list.
   * @param listObj the list whose suffix is to be copied.
   * @param start the (0-based) start index.
   * @see DottedPair#subseq
   */
  static public DottedPair subseq(Object listObj, int start)
    throws ClassCastException, RuntimeException {
    return ((DottedPair) listObj).subseq(start);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>copySeq</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object.
   *
   * @return a top level copy of the indicated list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @see DottedPair#copySeq
   */
  static public DottedPair copySeq(Object listObj) {
    return ((DottedPair) listObj).copySeq();
  }

  /**
   * Invokes the <code>DottedPair</code> <code>nreverse</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object.
   *
   * @return the first <code>DottedPair</code> element of the (destructively)
   * reversed given list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @param listObj the list to destructively reverse.
   * @see DottedPair#nreverse
   */
  static public DottedPair nreverse(Object listObj) {
    return ((DottedPair) listObj).nreverse();
  }

  /**
   * Invokes the <code>DottedPair</code> <code>reverse</code> method,
   * assuming that listObj is a compound <code>DottedPair</code> object.
   *
   * @return a reversed (non-destructive) copy of the given list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @param listObj the list to reverse.
   * @see DottedPair#reverse
   */
  static public DottedPair reverse(Object listObj) {
    return ((DottedPair) listObj).reverse();
  }

  /**
   * Returns a new list that is the result of appending a (surface level)
   * copy of the first list argument to the second list argument.
   *
   * <p>
   * Note:  As in LISP, the result contains a reference to the
   * second list argument passed (the passed argument is not itself copied). 
   *
   * @return The appended result.
   * @param list1 the list to which to append.
   * @param list2 the list that is appended.
   * @exception ClassCastException Thrown at runtime if 
   * <code>list1</code> and <code>list2</code> are not both
   * compound <code>DottedPair</code> objects. Additionally, <code>list1</code>
   * had better be a true list or the same exception will be thrown when
   * the internal <code>DottedPair.append</code> method reaches the atomic
   * last element of <code>list1</code>.
   */
  static public DottedPair append(Object list1, Object list2)
    throws ClassCastException {
    return ((DottedPair) list1).append((DottedPair) list2);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>car</code> method,
   * assuming that compObj is a compound <code>DottedPair</code> object.
   *
   * @return the result of DottedPair.car (the first element of the pair)
   * @param compObj the object on which to invoke DottedPair.car()
   * @exception ClassCastException Thrown at runtime if <code>
   * compObj </code> is not a compound <code>DottedPair</code>
   * object. 
   * @see DottedPair#car
   */
  static public Object car(Object compObj) throws ClassCastException {
    return ((DottedPair) compObj).car();
  }
  /**
   * An alias for the <code>car</code> method.
   *
   * @return the result of DottedPair.car (the first element of the pair)
   * @param compObj the object on which to invoke DottedPair.car()
   * @exception ClassCastException Thrown at runtime if <code>
   * compObj </code> is not a compound <code>DottedPair</code>
   * object. 
   * @see #car
   */
  static public Object first(Object compObj) throws ClassCastException { 
    return car(compObj);
  }

  /**
   * Invokes the <code>DottedPair</code> <code>cdr</code> method,
   * assuming that compObj is a compound <code>DottedPair</code> object.
   *
   * @return the result of DottedPair.cdr (the right element of the pair)
   * @param compObj the object on which to invoke DottedPair.cdr()
   * @exception ClassCastException Thrown at runtime if <code>
   * compObj </code> is not a compound <code>DottedPair</code>
   * object. 
   * @see DottedPair#cdr
   */
  static public Object cdr(Object compObj) throws ClassCastException { 
    return ((DottedPair) compObj).cdr();
  }

  /**
   * An alias for the <code>cdr</code> method.
   *
   * @return the result of DottedPair.cdr (the right element of the pair)
   * @param compObj the object on which to invoke DottedPair.cdr()
   * @exception ClassCastException Thrown at runtime if <code>
   * compObj </code> is not a compound <code>DottedPair</code>
   * object. 
   * @see #cdr
   */
  static public Object rest(Object compObj)  throws ClassCastException {
    return cdr(compObj);
  }


  /**
   * Reads and parses the next atomic or compound expression from the
   * given Reader stream.
   *
   * @return An object consistent with the description in the stream.
   * @param reader The stream from which to read.
   * @exception Exception An Exception will be thrown if a parsing error occurs.
   * @see java.io.Reader
   */
   static public Object parse(Reader reader) throws Exception {
    StreamTokenizer tokenizer = new StreamTokenizer(reader);
    lexDottedPairSyntax(tokenizer);
    return parse(tokenizer);
  }

  /**
   * Reads and parses the first atomic or compound expression from the
   * given <code>String</code>.
   *
   * @return An object consistent with the description in <code>str</code>.
   * @param str The <code>String</code> to parse.
   * @exception Exception An Exception will be thrown if a parsing error occurs.
   */
  static public Object parse(String str) throws Exception {
    return parse(new StringReader(str));
  }

  /**
   * Reads and parses the next atomic or compound expression from the
   * given <code>StreamTokenizer</code> stream.
   *
   * @return An object consistent with the description in the stream.
   * @param tokenizer The token stream from which to read.
   * @exception Exception An Exception will be thrown if a parsing error
   * occurs.
   * @see java.io.StreamTokenizer
   */
  private static Object parse(StreamTokenizer tokenizer) throws Exception {
    int tokenType = tokenizer.nextToken();
    switch (tokenType) {
    case StreamTokenizer.TT_WORD:
      if (isDot(tokenizer)) {
	throw new Exception(". seen, but unexpected");
      } else {
	String atom = tokenizer.sval;
	if ("-+.0123456789".indexOf(atom.charAt(0)) == -1) {
	  return atom;
	} else {
	  return parseNumber(atom);
	}
      }
    case '(':
      return parseDottedPair(tokenizer);
    case '"':
    case '|':
      return tokenizer.sval;
    default:
      throw new Exception("Unexpected token "+((char) tokenType));
    }
  }

  /**
   * Converts the last-read token of the given <code>StreamTokenizer
   * </code> to a <code>String</code> representation.
   *
   * @return the <code>String</code> representation of the last-read
   * token.
   * @param tokenizer The tokenizer containing a read token.
   * @see java.io.StreamTokenizer
   */
  private static String  tokenToString(StreamTokenizer tokenizer) {
    switch (tokenizer.ttype) {
    case StreamTokenizer.TT_EOF:
      return "*END OF STREAM*";
    case StreamTokenizer.TT_EOL:
      return "\n";
    case StreamTokenizer.TT_NUMBER:
      return String.valueOf(tokenizer.nval);
    case StreamTokenizer.TT_WORD:
      return tokenizer.sval;
    default:
      return String.valueOf((char) tokenizer.ttype);
    }
  }

  /**
   * Initializes the syntax table of a <code>StreamTokenizer</code>
   * to read LISP-like atoms and compound expressions.
   *
   * @param tokenizer The tokenizer to initialize.
   * @see java.io.StreamTokenizer
   */
  private static void lexDottedPairSyntax(StreamTokenizer tokenizer) {
    tokenizer.resetSyntax();
    tokenizer.wordChars('a','z');
    tokenizer.wordChars('A','Z');
    tokenizer.wordChars('0','9');
    tokenizer.whitespaceChars(0,' ');
    tokenizer.quoteChar('"');
    tokenizer.quoteChar('|');
    String constituents = "!$%&*.+-/:<=>?@[]^_{}~";
    for (int i=0;i<constituents.length();i++) {
      char c = constituents.charAt(i);
      tokenizer.wordChars(c,c);
    }
  }

  /**
   * Determines if the tokenizer just read a single dot "."
   *
   * @param tokenizer The tokenizer to inspect.
   * @see java.io.StreamTokenizer
   */
  private static boolean isDot(StreamTokenizer tokenizer) {
    return ((tokenizer.ttype == StreamTokenizer.TT_WORD) &&
	    tokenizer.sval.equals("."));
  }

  /**
   * Parse an expression from the tokenizer, assuming that the previous
   * token was a single dot, and remove the closing ')' that must
   * syntactically follow.
   *
   * @param tokenizer The tokenizer from which to parse.
   * @return The parsed object.
   * @exception Exception Parsing error if a close parenthesis ')' does not 
   * follow.
   * @see java.io.StreamTokenizer
   */
  private static Object parseCdrDottedPair(StreamTokenizer tokenizer) 
    throws Exception {
    Object cdr = parse(tokenizer);
    int tokenType = tokenizer.nextToken();
    if (tokenType != ')') {
      throw new Exception("Should have seen ')', but saw '"+
			  tokenToString(tokenizer)+"'");
    }
    return cdr;
  }

  /**
   * Parses the subsequent element(s) of a compound expression (after the first
   * element has already been parsed).
   *
   * @param tokenizer The tokenizer from which to parse.
   * @return The atomic or compound expression representing the
   * subsequent element(s)
   * @exception Exception A parsing exception may possibly be thrown from 
   * called routines.
   * @see java.io.StreamTokenizer
   */
  private static Object parseRestDottedPair(StreamTokenizer tokenizer) 
    throws Exception {
    int tokenType = tokenizer.nextToken();
    if (tokenType == ')') {
      return getNull();
    } else if (isDot(tokenizer)) {
      return parseCdrDottedPair(tokenizer);      
    }
    tokenizer.pushBack();
    Object car = parse(tokenizer);
    Object cdr = parseRestDottedPair(tokenizer);
    return new DottedPair(car,cdr);
  }

  /**
   * Parses the an entire <code>DottedPair</code>.
   *
   * @param tokenizer The tokenizer from which to parse.
   * @return A <code>DottedPair</code> consistent with the contents
   * of the stream of tokens presented by the tokenizer.
   * @exception Exception A parsing exception may possibly be thrown from
   * called routines.
   * @see java.io.StreamTokenizer
   * @see DottedPair
   */
  private static Object parseDottedPair(StreamTokenizer tokenizer) 
    throws Exception {
    int tokenType = tokenizer.nextToken();
    if (tokenType == ')') {
      return getNull();
    } else {
      tokenizer.pushBack();
      Object car = parse(tokenizer);
      Object cdr = parseRestDottedPair(tokenizer);
      return new Expression(car,cdr);
    }
  }

  /**
   * Parses the a number from the given <code>String</code> token.  
   * Depending on the format of the number in the String, either a 
   * <code>Long</code> or <code>Double</code> Java <code>Number</code>,
   * as appropriate, will be returned as the result of the parse.
   * This method is needed because the built in JAVA methods for
   * parsing numbers don't parse scientific notation.  This method
   * parses numbers of the form:
   * <pre>
   *   [+-]dddd[.dddd][[eE][+-]dddd]
   * </pre>
   * @param token The token to parse.
   * @return A <code>Number</code> consistent in type with the
   * contents of the token.
   * @exception Exception A parsing exception may be thrown if the
   * token does not represent a well-formatted number.
   * @see java.text.NumberFormat
   */
  private static Number parseNumber(String token) throws Exception {
    NumberFormat  nf = NumberFormat.getInstance();
    int tokenLength   = token.length();

    // We allow a leading +, so set parse position after it, if present:
    int parseIndex = (token.charAt(0)=='+'?1:0);
    ParsePosition pp = new ParsePosition(parseIndex);

    Number numObj = nf.parse(token,pp);
    parseIndex    = pp.getIndex();

    if (parseIndex == tokenLength) {
      return numObj;
    } else if ("eE".indexOf(token.charAt(parseIndex)) == -1) {
      throw new Exception("invalid numeric-looking object '"+token+"'");
    } else {
      // Skip over the 'e' or 'E'
      parseIndex++;
      // Further skip over the optional leading '+', if present;
      if ((parseIndex < tokenLength) && 
	  (token.charAt(parseIndex) == '+')) parseIndex++;
      if (parseIndex >= tokenLength) {
	throw new Exception("invalid exponent in numeric-looking object '"
				 + token+"'");
      } else {
	pp.setIndex(parseIndex);
	nf.setParseIntegerOnly(true);
	Number expObj = nf.parse(token,pp);
	parseIndex = pp.getIndex();
	if (parseIndex != tokenLength) {
	  throw 
	    new Exception("invalid exponent in numeric-looking object '"+
			       token+"'");
	} else {
	  // For better numeric accuracy, find 10^abs(exponent) and then
	  // divide by that value if exponent is negative (rather than 
	  // multiplying by the reciprocal 10^-abs(exponent) which can
	  // lead to round off error).
	  double num = numObj.doubleValue();
	  double exponentFactor = 
	    Math.pow(10.0,Math.abs(expObj.doubleValue()));
	  if (expObj.doubleValue() >= 0) {
	    return new Double(num*exponentFactor);
	  } else {
	    return new Double(num/exponentFactor);
	  }
	}
      }
    }
  }


  /**
   * Tests out the functionality of this class.
   * @param args Ignored.
   */
  public static void main(String args[]) {
    String ParseTests[] = {"(a b c)",
			   "(a |b \\nc| d)",
			   "(a \"b c\" d)",
			   "(a (b .  c) d)",
			   "(a .)",
			   "(a . b c)",
			   "(a  b.cdef c)",
			   "(a  10 1.5  c)",
			   "(a  10 1.5a  c)",
			   "(a  10 1.5E3  c)",
			   "(a  10 .5E3  c)",
			   "(a  10 -.5E3  c)",
			   "(a  10 +.5E3  c)",
			   "(a  10 1.5E3.5  c)",
			   "(a  10 1.5E-1  c)",
			   "(a  10 .15  c)",
			   "(a  10 .15e+1  c)",
			   "(a  10 15%  c)",
			   "(a  . (b . (c . ())))",
			   "(a  .(b .(c .())))",
			   "hello",
			   ".",
			   "12"};

    System.out.println("*** Parsing Tests ***");
    for (int i = 0; i < ParseTests.length; i++) {
      try {
	System.out.print(ParseTests[i]+" = ");
	System.out.println(parse(ParseTests[i]));
      } catch (Exception e) {
	System.out.println(e);
      }
    }

    String AssocTests[] = {"((a . 1) (b . 2) (c . 3) (d . 4))",
			   "a",
			   "((a . 1) (b . 2) (c . 3) (d . 4))",
			   "c",
			   "((a . 1) (b . 2) (c . 3) (d . 4))",
			   "e",
			   "((a . 1) (b . 2) ((c  d) . 3) (e . 4))",
			   "(c d)"};
    System.out.println("*** Assoc Tests ***");
    for (int i = 0; i < AssocTests.length/2; i++) {
      try {
	System.out.print("Expression.assoc("+AssocTests[2*i+1]+", "+
			 AssocTests[2*i]+") = ");
	System.out.println(Expression.assoc(parse(AssocTests[2*i+1]),
					    parse(AssocTests[2*i])));
      } catch (Exception e) {
	System.out.println(e);
      }
    }

    String AppendTests[] = {"(j k)",
			    "(g (h . i))",
			    "((d e) () f)",
			    "((a b c))",
			    "(generates . error)"};
    System.out.println("*** Append Tests ***");
    DottedPair accumulate = getNull();
    for (int i = 0; i < AppendTests.length; i++) {
      try {
	System.out.print("Expression.append("+AppendTests[i]+", "+
			 accumulate+") = ");
	accumulate = Expression.append(parse(AppendTests[i]),accumulate);
	System.out.println(accumulate);
      } catch (Exception e) {
	System.out.println(e);
      }
    }


    System.out.println("*** Member Tests ***");
    String MemberTests[] = {"a","b","c","d"};
    try {
      DottedPair searchList = (DottedPair) Expression.parse("(a b no-c no-d)");
      for (int i = 0; i < MemberTests.length; i++) {
	try {
	  System.out.print("Expression.member("+MemberTests[i]+", "+
			   searchList+") = ");
	  System.out.println(Expression.member(parse(MemberTests[i]),
					       searchList));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
    } catch (Exception e) {
      System.out.println(e);
    }


    System.out.println("*** Elt Tests ***");
    try {
      DottedPair eltList = (DottedPair) Expression.parse("(a b c d)");
      for (int i = -1; i <= 4; i++) {
      try {
	  System.out.print("Expression.elt("+eltList+", "+i+") = ");
	  System.out.println(Expression.elt(eltList,i));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
    } catch (Exception e) {
      System.out.println(e);
    }


    System.out.println("*** Length Tests ***");
    try {
      DottedPair list1 = (DottedPair) Expression.parse("(1 (a b) (c d) 4)");
      DottedPair list2 = Expression.getNull();
      System.out.println("Expression.length("+list1+") = " +
			Expression.length(list1));
      System.out.println("Expression.length("+list2+") = " +
			Expression.length(list2));
    } catch (Exception e) {
	  System.out.println(e);
    }

    System.out.println("*** Nthcdr Tests ***");
    try {
      DottedPair nthcdrList = (DottedPair) Expression.parse("(a b c d)");
      for (int i = -1; i <= 4; i++) {
      try {
	  System.out.print("Expression.nthcdr("+i+", "+nthcdrList+") = ");
	  System.out.println(Expression.nthcdr(i,nthcdrList));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
    } catch (Exception e) {
      System.out.println(e);
    }

    System.out.println("*** Subseq(start,end) Tests ***");
    try {
      DottedPair list = (DottedPair) Expression.parse("(a b c d)");
      for (int i = -1; i <= 4; i++) {
        try {
	  System.out.print("Expression.subseq("+list+","+i+",2) = ");
	  System.out.println(Expression.subseq(list,i,2));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
      for (int i = -1; i <= 4; i++) {
        try {
	  System.out.print("Expression.subseq("+list+","+2+","+i+") = ");
	  System.out.println(Expression.subseq(list,2,i));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
    } catch (Exception e) {
      System.out.println(e);
    }

    System.out.println("*** Subseq(start) Tests ***");
    try {
      DottedPair list = (DottedPair) Expression.parse("(a b c d)");
      for (int i = -1; i <= 4; i++) {
        try {
	  System.out.print("Expression.subseq("+list+","+i+") = ");
	  System.out.println(Expression.subseq(list,i));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
    } catch (Exception e) {
      System.out.println(e);
    }


    System.out.println("*** Reverse Tests ***");
    try {
      String tests[]={"(a b c d)",
      		      "(a b c . d)",  // should throw an error
      		      "()", 
	              "(a (b . c) d)"};
      for (int i = 0; i < tests.length; i++) {
        try {
	  DottedPair list = (DottedPair) Expression.parse(tests[i]);
	  System.out.print("Expression.reverse("+list+") = ");
	  System.out.println(Expression.reverse(list));
	} catch (Exception e) {
	  System.out.println(e);
	}
      }
    } catch (Exception e) {
      System.out.println(e);
    }
  }

}