* 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. *
* Comment: Maybe one day we'll make this whole class protected or
* private to force people to use the
* 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
*
* Note: Should one day implement a version of this code that takes
* an arbitrary predicate, rather than assuming
* Note: Should one day implement a version of this code that takes
* an arbitrary predicate, rather than assuming
* 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
* Expression(car,cdr)
* 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 DottedPairs that are true
* lists). Analogous to NIL in LISP.
*
* @return the unique Null object.
*/
final public static DottedPair getNull() {
return NULL;
}
/**
* Returns the Object to the left of the "dot".
*
* @return the Object to the left of the "dot".
* @see aima.utilities.Expression#car
*/
final public Object car() {
return theCar;
}
/**
* Returns the Object to the left of the "dot".
* An alias for car, used when manipulating
* true lists, to find the value of the first element of the
* list.
*
* @return the Object to the left of the "dot".
* @see #car
* @see aima.utilities.Expression#first
*/
final public Object first() {
return theCar;
}
/**
* Returns the Object to the right of the "dot".
*
* @return the Object to the right of the "dot".
* @see aima.utilities.Expression#cdr
*/
final public Object cdr() {
return theCdr;
}
/**
* Returns the Object to the right of the "dot".
* An alias for cdr, used when manipulating
* true lists, to return the sub-list representing the rest
* of the list appearing after the first element.
*
* @return the Object 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 cdr method the specified
* number of times.
*
* @return The result of applying the cdr method
* cdr times.
* @exception ClassCastException Possibly thrown at runtime if this
* is not a true list (ends in a non-Null atomic Object).
* @exception RuntimeException Possibly thrown at runtime if given number
* of times is negative.
* @param n the number of times to take the 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 Object found at the given (0-based) index
* of this list.
*
* @return the Object found at the given index.
* @exception ClassCastException Possibly thrown at runtime if this
* is not a true list (ends in a non-Null atomic Object).
* @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 Object).
* @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 Object).
* @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 Object).
* @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 Object).
* @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 Object).
* @see Expression#copySeq
*/
public DottedPair copySeq() {
return subseqRest();
}
/**
* Indicates if this is the special Null object. Analogous
* to the null 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 atom 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 consp 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 listp 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 eql sense. Since we
* are dealing with DottedPairs, this method only
* return true if this is equal to the passed object in the
* JAVA == sense.
*
* @return true iff this is identical to obj
* @param obj the Object 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 equal sense. This means that, recursively,
* all sub-components of this object must equal the corresponding
* subcomponents of the passed object, but, unlike with eql,
* the objects and their subcomponents need not be identical in the
* JAVA == sense.
*
* @return true iff this "looks" equal to obj, without
* necessarily being the identical object.
* @param obj the Object 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.
*
* eql to the given target, or the special Null object
* if the target is not found.
*
* eql.
* 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 eql to the
* given target, or the special Null object if no matching element
* is found.
* @param target the Object 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
* eql to the given target, or the special Null object
* if the target is not found.
*
* eql.
*
* @return The sublist whose first element is eql to the
* given target, or the special Null object if no matching element
* is found.
* @param target the Object 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 Object).
*/
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 Object).
* @see Expression#reverse
*/
public DottedPair reverse()
throws ClassCastException {
return copySeq().nreverse();
}
/**
* Continues the destructive reversal of this list.
*
* @return the first DottedPair element of the reversed
* list.
* @exception ClassCastException Possibly thrown at runtime if this
* is not a true list (ends in a non-Null atomic Object).
* @param prev the list element (DottedPair) 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 DottedPair element of the reversed
* list.
* @exception ClassCastException Possibly thrown at runtime if this
* is not a true list (ends in a non-Null atomic Object).
* @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:
*
* DottedPair dp = new DottedPair("x",
* new DottedPair("y",
* getNull()));
*
* which equals "(x . (y . ()))" will be formatted by toString
* as "(x y)"
*
* @return A pretty string representation of this DottedPair.
*/
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.
*
* DottedPair and used to terminate DottedPairs
* that are true lists.
*/
private DottedPair() {
theCar = theCdr = this;
}
/**
* The unique Null object representing an empty
* DottedPair and used to terminate DottedPairs
* 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());
}
}