package aima.util;
/**
 * The DottedPair class provides an implementation of LISP-like cons cells.
 *
 * <p>
 * Potential BUG:  Concurrency issues have not yet been addressed.  While
 * we could synchronize on individual DottedPairs, one advantage of having
 * a DottedPair type is that multiple lists can easily and cheaply share
 * substructures:  synchronizing on an individual DottedPair will not 
 * address concurrency issues between two lists that share substructure.
 *
 * @author Michael S. Braverman
 * @see    aima.utilities.Expression
 */

public class DottedPair {
  /**
   * Creates a new DottedPair.
   * <p>
   * Comment:  Maybe one day we'll make this whole class protected or 
   * private to force people to use the <code>Expression(car,cdr)</code>
   * constructor to create DottedPairs.
   *
   * @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 aima.utilities.Expression
   */
  public DottedPair (Object car, Object cdr) {
    theCar = car;
    theCdr = cdr;
  }

  /**
   * Possibly create a new DottedPair which contains the passed parameters,
   * or return this object if it actually contains the passed parameters.
   *
   * @return This object if it already has the given contents, or a new
   *         DottedPair containing the given contents.
   * @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 aima.utilities.Expression#reuse
   */
  public DottedPair reuse(Object car, Object cdr) {
    if ((theCar == car) && (theCdr == cdr)) {
	return this;
    } else {
	return new DottedPair(car,cdr);
    }
  }  

  /**
   * Returns the unique object used to represent the empty list (and
   * which is used to terminate <code>DottedPair</code>s that are true
   * lists).  Analogous to <code>NIL</code> in LISP.
   *
   * @return the unique Null object.
   */
  final public static DottedPair getNull() { 
    return NULL; 
  }

  /**
   * Returns the <code>Object</code> to the left of the "dot".
   *
   * @return the <code>Object</code> to the left of the "dot".
   * @see aima.utilities.Expression#car
   */
  final public Object car() { 
    return theCar;
  }

  /**
   * Returns the <code>Object</code> to the left of the "dot".
   * An alias for <code>car</code>, used when manipulating
   * true lists, to find the value of the first element of the
   * list.
   *
   * @return the <code>Object</code> to the left of the "dot".
   * @see #car
   * @see aima.utilities.Expression#first
   */
  final public Object first() { 
    return theCar;
  }

  /**
   * Returns the <code>Object</code> to the right of the "dot".
   *
   * @return the <code>Object</code> to the right of the "dot".
   * @see aima.utilities.Expression#cdr
   */
  final public Object cdr() { 
    return theCdr;
  }

  /**
   * Returns the <code>Object</code> to the right of the "dot".
   * An alias for <code>cdr</code>, used when manipulating
   * true lists, to return the sub-list representing the rest
   * of the list appearing after the first element.
   *
   * @return the <code>Object</code> to the right of the "dot".
   * @see #cdr
   * @see aima.utilities.Expression#rest
   */
  final public Object rest() { 
    return theCdr;
  }

  /**
   * Returns the result of applying the <code>cdr</code> method the specified
   * number of times.
   *
   * @return The result of applying the <code>cdr</code> method 
   * <code>cdr</code> times.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @exception RuntimeException Possibly thrown at runtime if given number
   * of times is negative.
   * @param n the number of times to take the <code>cdr</cdr>.
   * @see #cdr
   * @see #getNull
   */
  public DottedPair nthcdr(int n) 
    throws ClassCastException, RuntimeException {
    if (n < 0) {
      throw new RuntimeException("nthcdr: given negative index ("+n+")!");
    } else {
      DottedPair scan = this;
      for (scan = this; (n > 0) && (scan != NULL); n--) {
	scan = (DottedPair) scan.cdr();
      }
      return scan;
    }
  }

  /**
   * Returns the <code>Object</code> found at the given (0-based) index
   * of this list.
   *
   * @return the <code>Object</code> found at the given index.
   * @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 attempting to access beyond
   * the end of the list, or if given index is negative.
   * @param index the (0-based) position at which to select.
   * @see #nthcdr
   * @see Expression#elt
   */
  public Object elt(int index) 
    throws ClassCastException, RuntimeException {
    DottedPair position;
    try {
      position = nthcdr(index);
    } catch (Exception e) {
      throw new RuntimeException("elt: error calling nthcdr..."+e);
    }
    if (position.isNull()) {
      throw new RuntimeException("elt: Attempted to get non-existent #"+index+
				 " element of "+this);
    } else {
      return position.car();
    }
  }

  /**
   * Returns a top level copy of the first n elements of this list.
   *
   * @return a prefix copy of the given length from this 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 attempting to access beyond
   * the end of the list.
   * @param n the number of elements of the list to copy.
   * @see #subseq
   */
  private DottedPair subseqRest(int n)
    throws RuntimeException, ClassCastException {
    if (n == 0) {
      return NULL;
    }
    else if (this == NULL) {
      throw new RuntimeException("subseq: Attempted to go beyond end of list");
    } else {
      return new DottedPair(theCar,((DottedPair) theCdr).subseqRest(n-1));
    }
  }

  /**
   * Returns a top level copy of this list.
   *
   * @return a top level copy of this list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @see #subseq
   */
  private DottedPair subseqRest()
    throws ClassCastException {
    if (this == NULL) {
      return NULL;
    } else {
      return new DottedPair(theCar,((DottedPair) theCdr).subseqRest());
    }
  }

  /**
   * Returns a top level copy of the subset of this list indicated
   * by the two (0-based) indices.
   *
   * @return a top level copy of the indicated subset of the 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 start the (0-based) start index
   * @param end the (0-based) end index
   * @see Expression#subseq
   */
  public DottedPair subseq(int start, int end) 
    throws ClassCastException, RuntimeException {
    int subseqLen = end-start+1;
    if (subseqLen <= 0) {
      throw new RuntimeException("subseq: end("+end+") < start("+start+")");
    } else {
      DottedPair beginning = nthcdr(start);
      if (beginning == NULL) {
	throw new RuntimeException("subseq: start="+start+" is beyond end of "+
				   this);
      } else {
	return beginning.subseqRest(subseqLen);
      } 
    }
  }

  /**
   * Returns a top level copy of the suffix of this list starting
   * at the indicated (0-based) index.
   *
   * @return a top level copy of the indicated suffix of the 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 index is beyond
   * the bounds of the list.
   * @param start the (0-based) start index
   * @see Expression#subseq
   */
  public DottedPair subseq(int start) {
    DottedPair beginning = nthcdr(start);
    if (beginning == NULL) {
      throw new RuntimeException("subseq: start="+start+" is beyond end of "+
				 this);
    } else {
      return beginning.subseqRest();
    } 
  }

  /**
   * Returns a top level copy of this list.
   *
   * @return a top level copy of this list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @see Expression#copySeq
   */
  public DottedPair copySeq() {
    return subseqRest();
  }

  /**
   * Indicates if this is the special Null object.  Analogous
   * to the <code>null</code> predicate in LISP.
   *
   * @return true iff this is the special Null object.
   */
  final public boolean isNull() {
    return (this == NULL);
  }

  /**
   * Indicates if this is an atomic object.  Analogous
   * to the <code>atom</code> predicate in LISP.  Since we
   * are dealing with DottedPairs, the only way that this
   * method could return true would be if this object is
   * the special Null object (which, like in LISP, has been
   * given the dual properties of a compound and an atomic object).
   *
   * @return true iff this object is Atomic.
   * @see aima.utilities.Expression#isAtomic
   */
  final public boolean isAtomic() {
    return (this == NULL);
  }

  /**
   * Indicates if this is a true compound object.  Analogous
   * to the <code>consp</code> predicate in LISP.  Since we
   * are dealing with DottedPairs, the only way that this
   * method could return false would be if this object is
   * the special Null object (which, like in LISP, has been
   * given the dual properties of a compound and an atomic object).
   *
   * @return true iff this object is a non-NULL DottedPair.
   * @see aima.utilities.Expression#isTrueCompound
   */
  final public boolean isTrueCompound() {
    return (this != NULL);
  }

  /**
   * Indicates if this is a compound object.  Analogous
   * to the <code>listp</code> predicate in LISP.  Since we
   * are dealing with DottedPairs, the method must always
   * return true.
   *
   * @return true iff this object is a DottedPair
   * (which it is!)
   * @see aima.utilities.Expression#isCompound
   */
  final public boolean isCompound() {
    return true;
  }

  /**
   * Indicates if this is equal to the passed object in 
   * the LISP <code>eql</code> sense.  Since we
   * are dealing with DottedPairs, this method only
   * return true if this is equal to the passed object in the
   * JAVA <code>==</code> sense.
   *
   * @return true iff this is identical to <code>obj</code>
   * @param obj the <code>Object</code> with which to compare.
   * @see aima.utilities.Expression#eql
   */
  public boolean eql(Object obj) {
    return (this == obj);
  }

  /**
   * Indicates if this is equal to the passed object in 
   * the LISP <code>equal</code> sense.  This means that, recursively,
   * all sub-components of this object must equal the corresponding
   * subcomponents of the passed object, but, unlike with <code>eql</code>,
   * the objects and their subcomponents need not be identical in the
   * JAVA <code>==</code> sense.
   *
   * @return true iff this "looks" equal to <code>obj</code>, without
   * necessarily being the identical object.
   * @param obj the <code>Object</code> with which to compare.
   * @see aima.utilities.Expression#equals
   * @see #eql
   */
  public boolean equals(Object obj) {
    if ((this==NULL) || (obj == NULL)) {
      return (this==obj);
    } else if (obj instanceof DottedPair) {
      DottedPair objDP = (DottedPair) obj;
      return (car().equals(objDP.car()) && cdr().equals(objDP.cdr()));
    } else {
      return false;
    }
  }

  /**
   * Returns a new list that is the result of appending the given
   * list to a copy (top level only) of this list.
   *
   * <p>
   * Note:  As in LISP, the result contains a reference to the
   * argument passed (the passed argument is not itself copied). 
   *
   * @return The appended result.
   * @param appendee the list to be appended.
   */
  public DottedPair append(DottedPair appendee) {
    if (isNull()) return appendee;
    else return new DottedPair(first(),((DottedPair) rest()).append(appendee));
  }

  /**
   * Finds and returns the association pair whose first element is
   * <code>eql</code> to the given target, or the special Null object
   * if the target is not found.
   *
   * <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.
   * @see #eql
   */
  public DottedPair assoc(Object target) {
    DottedPair scan;
    for (scan = this; 
	 !(scan.isNull() || 
	   Expression.eql(Expression.car(scan.first()),target));
	 scan=(DottedPair)scan.cdr());
    return (DottedPair) scan.first();
  }

  /**
   * Finds and returns the sublist of this list whose first element is
   * <code>eql</code> to the given target, or the special Null object
   * if the target is not found.
   *
   * <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 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.
   * @see #eql
   */
  public DottedPair member(Object target) 
    throws ClassCastException {
    DottedPair scan;
    for (scan = this; 
	 !(scan.isNull() || 
	   Expression.eql(scan.first(),target));
	 scan=(DottedPair)scan.cdr());
    return scan;
  }

  /**
   * Returns the number of top-level elements of this list.
   *
   * @return The number of top-level elements of this list.
   * @exception ClassCastException Thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   */
  public int length() throws ClassCastException {
    int n = 0;
    for (DottedPair scan=this; scan != NULL; scan = (DottedPair)scan.cdr()) {
      n++;
    }
    return n;
  }

  /**
   * Reverses this list (non-destructively).
   *
   * @return the reversed list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @see Expression#reverse
   */
  public DottedPair reverse() 
    throws ClassCastException {
    return copySeq().nreverse();
  }

  /**
   * Continues the destructive reversal of this list.
   *
   * @return the first <code>DottedPair</code> element of the reversed
   * list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @param prev the list element (<code>DottedPair</code>) that appears
   * immediately before the current list element in the list being
   * reversed.
   * @see #nreverse
   */
  private DottedPair nreverse(DottedPair prev) 
    throws ClassCastException {
    if (this == NULL) return prev;
    else {
      DottedPair next = (DottedPair) theCdr;
      theCdr = prev;
      return next.nreverse(this);
    }
  }

  /**
   * Destructively reverses this list.
   *
   * @return the first <code>DottedPair</code> element of the reversed
   * list.
   * @exception ClassCastException Possibly thrown at runtime if this
   * is not a true list (ends in a non-Null atomic <code>Object</code>).
   * @see Expression#nreverse
   */
  public DottedPair nreverse() 
    throws ClassCastException {
    if (theCdr == NULL) return this;
    else {
      DottedPair next = (DottedPair) theCdr;
      theCdr = NULL;
      return next.nreverse(this);
    }
  }


  /**
   * Created a LISP-like pretty String representation of this object.
   * The return value is pretty in the sense that the DottedPair:
   * <pre>
   *    DottedPair dp = new DottedPair("x",
   *                                   new DottedPair("y",
   *                                                   getNull()));
   * </pre>
   * which equals "(x . (y . ()))" will be formatted by <code>toString</code>
   * as "(x y)"
   *
   * @return A pretty string representation of this <code>DottedPair</code>.
   */
  public  String toString() {
    if (this == NULL) return "()";
    else {
      Object scan = this;
      String result = "(" + possiblyQuote(((DottedPair) scan).car());
      for (scan = ((DottedPair) scan).cdr(); 
	   (scan != NULL) && (scan instanceof DottedPair);
	   scan = ((DottedPair) scan).cdr()) {
	result = result + " " + possiblyQuote(((DottedPair) scan).car());
      }
      if (scan != NULL) { 
	result = result + " . " + possiblyQuote(scan);
      }
      result = result + ")";
      return result;
    }
  }

  /**
   * Puts appropriate quotation characters around an atom so that,
   * for instance, an atom containing a blank will not appear to 
   * be two separate Objects in its String representation.
   *
   * <p>
   * BUGS: This routine should be made more sophisticated.  Currently,
   * it only checks for a space character, and puts vertical bars
   * around such atoms.  However, if the atom contains vertical bars,
   * this is the wrong thing to do (really need to add some backslashes
   * inside the atom as well).
   *
   * @return The quoted string representation.
   */
  private String possiblyQuote(Object obj) {
    String objStr = obj.toString();
    if (obj instanceof DottedPair) {
      return objStr;
    } else if (objStr.indexOf(' ')!=-1) {
      return "|" + objStr + "|";
    } else {
      return objStr;
    }
  }

  /**
   * Used to build the unique Null object representing an empty 
   * <code>DottedPair</code> and used to terminate <code>DottedPair</code>s
   * that are true lists.
   */
  private DottedPair() { 
    theCar = theCdr = this;
  }  

  /**
   * The unique Null object representing an empty 
   * <code>DottedPair</code> and used to terminate <code>DottedPair</code>s
   * that are true lists.  The construction of this object guarantees that
   * the car/first cdr/rest of this object is also the Null object
   */
  private static DottedPair NULL = new DottedPair();

  /**
   * Contents on "left" of the "dot" of this object.
   */
  private Object theCar;
  /**
   * Contents on "right" of the "dot" of this object.
   */
  private Object theCdr;


  /**
   * Tests out the functionality of this class.
   * @param args Ignored.
   */

  public static void main(String args[]) {
    DottedPair SimpleList = 
      new DottedPair("a",
		     new DottedPair("b",
				    new DottedPair("c",DottedPair.getNull())));
    DottedPair NestedList = 
      new DottedPair("1",
		     new DottedPair(SimpleList,
				    new DottedPair("3",DottedPair.getNull())));
    DottedPair DottedList =
      new DottedPair("this","that");
    DottedPair AbsorbedDotList =
      new DottedPair("the",DottedList);
    DottedPair WithWhiteSpaceList =
      new DottedPair("this has space",SimpleList);
    
    System.out.println(SimpleList);
    System.out.println(NestedList);
    System.out.println(DottedList);
    System.out.println(AbsorbedDotList);
    System.out.println(WithWhiteSpaceList);
    System.out.println(WithWhiteSpaceList.append(NestedList));
    try {
      System.out.println(DottedList.append(NestedList));
      System.out.println("This shouldn't be printing");
    } catch (Exception e) {
      System.out.println("An error should be generated: "+e);
    }
    System.out.println("Length of "+NestedList+" is = "+NestedList.length());
    System.out.println("#1 (0-indexed) element of "+NestedList+
		       " is = "+NestedList.elt(1));
    try {
      System.out.print("#5 element of "+NestedList+" is = ");
      System.out.println(NestedList.elt(5));
      System.out.println("This shouldn't be printing");
    } catch (Exception e) {
      System.out.println(e);
    }
    System.out.println("Reverse of "+NestedList+" is "+NestedList.reverse());
  }


}