// file: OpenList.java
// author: Robert M. Keller
// purpose: Implement Open Lists is java
// note: The comments in this file are javadoc style, used to generate
// API documentation automatically.
import java.io.*;
/**
* OpenList is a type of uni-directional linked list that permits sharing
* of list tails. It implements the list abstraction used in many
* languages, such as rex, Lisp, etc.
*/
class OpenList
{
/**
* the one and only empty OpenList. Do not create any others.
* This list is represented by a unique cell allocated for the purpose.
* The first and rest are not intended to be used. We do not use null
* for this list, so that we can call methods on it. We do not create other
* empty lists so that our implementation of isEmpty() works by comparing
* references.
*/
final public static OpenList nil = cons(null, null);
/**
the default left paren used when a list is printed.
Defaults are used when the toString() method is called, i.e. whenever
an OpenList is automatically cast to a String, as in printing.
To use different punctuation, or no punctuation, use the three-argument
toString, and supply the punctuation you want.
*/
public static String defaultLeftParen = "[";
/** the default right paren used when a list is printed */
public static String defaultRightParen = "]";
/** the default space used when a list is printed */
public static String defaultSpacer = ", ";
/** exception message for first of empty list */
public static String firstException = "first() of empty list";
/** exception message for rest of empty list */
public static String restException = "rest() of empty list";
/** exception message for nth of a list */
public static String nthException = "nth of an OpenList of length ";
/** part of exception message for nth of a list */
public static String wherePart = ", where n == ";
/** exception message for second of a list */
public static String secondException = "second of an OpenList, where length() = ";
/** exception message for third of a list */
public static String thirdException = "third of an OpenList, where length() = ";
/** the Object in the first cell of a non-empty list */
private Object First;
/** the rest of a list, defined to be an OpenList of all but the first cell */
private OpenList Rest;
/**
* Construct an OpenList from its first and rest.
* This constructor is private because it is intended that the
* pseudo-constructor (or "factory") cons be used outside.
*
* @param _First the first Object in the list
* @param _Rest list of the rest of the objects in the list
*/
private OpenList(Object _First, OpenList _Rest)
{
First = _First;
Rest = _Rest;
}
/**
* Return a new OpenList constructed from its first and rest.
*
* @param _First the first Object in the list
* @param _Rest list of the rest of the objects in the list
* @return new OpenList from first and rest
*/
public static OpenList cons(Object _First, OpenList _Rest)
{
return new OpenList(_First, _Rest);
}
/**
* Return a new OpenList constructed from this list and a first.
*
* @param _First the first Object in the list
* @return new OpenList from first and rest
*/
public OpenList cons(Object _First)
{
return new OpenList(_First, this);
}
/**
* Return the first of this non-empty OpenList.
*
* @return first of this list
* @exception OpenListException if this list happens to be empty
*/
public Object first() throws OpenListException
{
if( isEmpty() )
{
throw new OpenListException(firstException);
}
return First;
}
/**
* Return the first of the argument, a non-empty OpenList.
*
* @param List the list the rest of which is to be returned
* @return first of the argument list
* @exception OpenListException if the argument happens to be empty
*/
public static Object first(OpenList List) throws OpenListException
{
return List.first();
}
/**
* Return the rest, i.e. all a list of all but the first of this non-empty
* OpenList.
*
* @return rest of this list
* @exception OpenListException if this list happens to be empty
*/
public OpenList rest() throws OpenListException
{
if( isEmpty() )
{
throw new OpenListException(restException);
}
return Rest;
}
/**
* Return the rest, i.e. all a list of all but the first of the argument
* non-empty OpenList.
*
* @parameter List the list the rest of which is to be returned
* @return rest of the argument list
* @exception OpenListException if the argument happens to be empty
*/
public static OpenList rest(OpenList List) throws OpenListException
{
return List.rest();
}
/**
* Return true if this list is empty, false otherwise.
* Note: Done by comparing this list to nil, which should be the only
* way to determine whether the list is empty.
* @return true if this list is empty, false otherwise
*/
public boolean isEmpty()
{
return this == nil;
}
/**
* Return true if this list is non-empty, false otherwise.
* @return true if this list is non-empty, false otherwise
*/
public boolean nonEmpty()
{
return this != nil;
}
/**
* Return true if the argument list is empty, false otherwise.
* Note: Done by comparing this list to nil, which should be the only
* way to determine whether the list is empty.
*
* @param List the OpenList for which emptiness is to be determined
* @return true if the argument list is empty, false otherwise
*/
public static boolean isEmpty(OpenList List)
{
return List.isEmpty();
}
/**
* Return true if the argument list is non-empty, false otherwise.
*
* @param List the OpenList for which non-emptiness is to be determined
* @return true if the argument list is non-empty, false otherwise
*/
public static boolean nonEmpty(OpenList List)
{
return List.nonEmpty();
}
/**
* Create a new list formed by elements of the first argument followed by
* those of the second.
*
* @param L1 the list providing the initial elements of the result
* @param L2 the list providing the final elements of the result
* @return the list containing the elements of the first list followed
* by those of the second
*/
public static OpenList append(OpenList L1, OpenList L2)
{
if( L1.isEmpty() )
{
return L2;
}
else
{
return cons(L1.first(), append(L1.rest(), L2));
}
}
/**
* Create a new list formed by elements of this list followed by those
* of the argument list.
*
* @param L the list providing the final elements of the result
* @return the list containing the elements of this list followed
* by those of the second
*/
public OpenList append(OpenList L2)
{
return append(this, L2);
}
/**
* Return true if the first argument is a member (in the sense of being
* equals) of the second argument list
*
* @param Ob the object being tested for membership
* @param L the list in which membership is to be tested
* @return true if the first argument is a member of the second, false
* otherwise
*/
public static boolean member(Object Ob, OpenList L)
{
for( ; L.nonEmpty(); L = L.rest() )
{
if( Ob.equals(L.first()) ) return true;
}
return false;
}
/**
* Return true if the first argument is a member (in the sense of being
* equals) of this OpenList
*
* @param Ob the object being tested for membership
* @return true if the first argument is a member of this list, false
* otherwise
*/
public boolean member(Object Ob)
{
return member(Ob, this);
}
/**
* Return a new list containing the elements of the argument list in
* reverse order.
*
* @param L1 the list providing the elements
* @return the reverse of the argument list
*/
public static OpenList reverse(OpenList L1)
{
OpenList result = nil;
for( ; L1.nonEmpty(); L1 = L1.rest() )
{
result = cons(L1.first(), result);
}
return result;
}
/**
* Return a new list containing the elements of the argument this list in
* reverse order.
*
* @return the reverse of this list
*/
public OpenList reverse()
{
return reverse(this);
}
/**
* Return the number of elements of the argument list.
* @param L the list, the length of which is to be determined
* @return the number of elements of the argument list
*/
public static int length(OpenList L)
{
int result = 0;
for( ; L.nonEmpty(); L = L.rest() )
{
result++;
}
return result;
}
/**
* Return the number of elements of this list.
* @return the number of elements of this list
*/
public int length()
{
return length(this);
}
/**
* Return the nth element of the second argument list,
* starting with n = 0, 1, 2, ...
* If there is no nth element, throws an OpenListException so indicating.
*
* @param n the index (0, 1, 2, ...) of the desired element.
* @param L the list from which the indexed item is selected
* @return the nth element of this list
* @exception OpenListException if there is no nth element
*/
public static Object nth(int n, OpenList L) throws OpenListException
{
int remaining = n;
OpenList original = L;
try
{
while( remaining > 0 )
{
L = L.rest();
remaining--;
}
return L.first();
}
catch( OpenListException e )
{
throw new OpenListException(nthException + original.length() + wherePart + n);
}
}
/**
* Return the nth element of this list, starting with n = 0, 1, 2, ...
* If there is no nth element, throws an EmptyList exception so indicating.
*
* @param n the index (0, 1, 2, ...) of the desired element.
* @return the nth element of this list
* @exception OpenListException if there is no nth element
*/
public Object nth(int n) throws OpenListException
{
return nth(n, this);
}
/**
* Returns the first n elements of this OpenList. If there aren't n
* elements in the list, returns the entire list. If n <= 0, returns nil.
*
* @param n the length of the desired prefix of this list.
* @return the prefix of this list of the desired length, or the entire
* list itself if the list is not as long as desired.
*/
public OpenList prefix(int n)
{
if( isEmpty() || n <= 0 )
{
return nil;
}
return cons(first(), rest().prefix(n-1));
}
/**
* Returns the first n elements of an OpenList. If there aren't n
* elements in the list, returns the entire list. If n <= 0, returns nil.
*
* @param n the length of the desired prefix of this list.
* @param L the list, the prefix of which is to be extracted
* @return the prefix of this list of the desired length, or the entire
* list itself if the list is not as long as desired.
*/
static public OpenList prefix(int n, OpenList L)
{
return L.prefix(n);
}
/**
* Return the second element of this OpenList, assuming it has one.
*
* @return the second element of this OpenList
* @exception OpenListException if there is no second element
*/
public Object second() throws OpenListException
{
try
{
return nth(1);
}
catch( OpenListException e )
{
throw new OpenListException(thirdException + length());
}
}
/**
* Return the third element of this OpenList, assuming it has one.
*
* @return the third element of this OpenList
* @exception OpenListException if there is no third element
*/
public Object third() throws OpenListException
{
try
{
return nth(2);
}
catch( OpenListException e )
{
throw new OpenListException(thirdException + length());
}
}
/**
* Return the second element of the argument OpenList, assuming it has one.
*
* @param L an OpenList, the second element of which is to be extracted
* @return the second element L
* @exception OpenListException if there is no second element
*/
public static Object second(OpenList L) throws OpenListException
{
return L.second();
}
/**
* Return the third element of the argument OpenList, assuming it has one.
*
* @param L an OpenList, the third element of which is to be extracted
* @return the second element L
* @exception OpenListException if there is no third element
*/
public static Object third(OpenList L) throws OpenListException
{
return L.third();
}
/**
* Return the list consisting of the argument objects, in this case the
* empty list.
*
* @return the list consisting of the argument objects
*/
public static OpenList list()
{
return nil;
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First)
{
return cons(First, nil);
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @param Second the second element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First, Object Second)
{
return cons(First, list(Second));
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @param Second the second element in the resulting list
* @param Third the third element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First, Object Second, Object Third)
{
return cons(First, list(Second, Third));
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @param Second the second element in the resulting list
* @param Third the third element in the resulting list
* @param Fourth the fourth element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First,
Object Second,
Object Third,
Object Fourth)
{
return cons(First, list(Second, Third, Fourth));
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @param Second the second element in the resulting list
* @param Third the third element in the resulting list
* @param Fourth the fourth element in the resulting list
* @param Fifth the fifth element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First,
Object Second,
Object Third,
Object Fourth,
Object Fifth)
{
return cons(First, list(Second, Third, Fourth, Fifth));
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @param Second the second element in the resulting list
* @param Third the third element in the resulting list
* @param Fourth the fourth element in the resulting list
* @param Fifth the fifth element in the resulting list
* @param Sixth the sixth element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First,
Object Second,
Object Third,
Object Fourth,
Object Fifth,
Object Sixth)
{
return cons(First, list(Second, Third, Fourth, Fifth, Sixth));
}
/**
* Return the list consisting of the argument objects.
*
* @param First the first element in the resulting list
* @param Second the second element in the resulting list
* @param Third the third element in the resulting list
* @param Fourth the fourth element in the resulting list
* @param Fifth the fifth element in the resulting list
* @param Sixth the sixth element in the resulting list
* @param Seventh the seventh element in the resulting list
* @return the list consisting of the argument objects
*/
public static OpenList list(Object First,
Object Second,
Object Third,
Object Fourth,
Object Fifth,
Object Sixth,
Object Seventh)
{
return cons(First, list(Second, Third, Fourth, Fifth, Sixth, Seventh));
}
/**
* Return true if the two OpenLists are equal, in the sense of having
* the equal elements in both listss.
*
* @param L1 one of two OpenLists to be compared for equality
* @param L2 the other of two OpenLists to be compared for equality
* @return true if the arguments are equal, false otherwise
*/
public static boolean equals(OpenList L1, OpenList L2)
{
// As long as both lists have elements, check for the equality of
// those elements.
while( L1.nonEmpty() && L2.nonEmpty() )
{
if( !(L1.first().equals(L2.first())) )
{
return false;
}
L1 = L1.rest();
L2 = L2.rest();
}
// Now at least one of the lists is empty.
// The two are equal if, and only if, both are empty.
return L1.isEmpty() && L2.isEmpty();
}
/**
* Return true if this list is equal to the argument list.
*
* @param Ob the Object to be compared with this for equality
* @return true if the argument is an OpenList equal to this one.
*/
public boolean equals(Object Ob)
{
if( Ob instanceof OpenList )
{
return equals(this, (OpenList)Ob);
}
return false; // An OpenList can only be equals to another OpenList
}
/**
* Convert this OpenList to a String, using default punctuation.
*
* @return String representing this OpenList
*/
public String toString()
{
return toString(defaultLeftParen, defaultSpacer, defaultRightParen);
}
/**
* Convert this OpenList to a String, using the arguments as punctuation.
*
* @param leftParen String that is output before the list elements
* @param spacer String that is output between list elements
* @param rightParen String that is output after the list elements
* @return String representing OpenList
*/
public String toString(String leftParen,
String spacer,
String rightParen)
{
StringBuffer buffer = new StringBuffer();
buffer.append(leftParen);
if( nonEmpty() )
{
buffer.append(first().toString());
OpenList remainder = rest();
while( remainder.nonEmpty() )
{
buffer.append(spacer);
buffer.append(remainder.first());
remainder = remainder.rest();
}
}
buffer.append(rightParen);
return buffer.toString();
}
/**
* Explode the argument String into a list of Characters wrapping
* the characters of the String.
*
* @param String to be exploded
* @return OpenList containing the characters of the String
*/
public static OpenList explode(String s)
{
OpenList result = nil;
for( int i = s.length()-1; i >= 0; i-- )
{
result = cons(new Character(s.charAt(i)), result);
}
return result;
}
/**
* Implode the contents of an OpenList into a single String.
* The list can contain any Objects, not just Characters.
* The toString method is used to get the character representation of
* the object. No parentheses or spacing is added around or between
* the elements of the outer list. If these are wanted, use the
* toString method rather than implode.
*
* @param L the list to be imploded
* @return String representing the imploded list.
*/
public static String implode(OpenList L)
{
StringBuffer buffer = new StringBuffer();
for( ; L.nonEmpty(); L = L.rest() )
{
buffer.append(L.first().toString());
}
return buffer.toString();
}
/**
* Implode this OpenList into a single String.
* The list can contain any Objects, not just Characters.
* The toString method is used to get the character representation of
* the object. No parentheses or spacing is added around or between
* the elements of the outer list.
*
* @return String representing the imploded list.
*/
public String implode()
{
return implode(this);
}
/**
* Return an array of the Objects in the argument OpenList.
*
* @param L the list of objects to be used as elements of the array
* @return an array of the Objects in the argument OpenList
*/
public static Object[] toArray(OpenList L)
{
Object a[] = new Object[L.length()];
int i = 0;
for( ; L.nonEmpty(); L = L.rest() )
{
a[i] = L.first();
i++;
}
return a;
}
/**
* Return an array of the Objects in this OpenList.
*
* @return an array of the Objects in this OpenList
*/
public Object[] toArray()
{
return toArray(this);
}
/**
* Create an OpenList from an array of Objects.
*
* @return an OpenList containing the Objects in the argument array
*/
public static OpenList fromArray(Object a[])
{
OpenList result = nil;
for( int i = a.length-1; i >= 0; i-- )
{
result = cons(a[i], result);
}
return result;
}
/**
* Return a sorted version of this list, as determined by the Comparator,
* using the Quicksort algorithm
*
* @param comparator used to determine whether one element is less than
* another
* @return the list consisting of the Objects in the original list
* in order as determined by the comparator
*/
public OpenList sort(java.util.Comparator comparator)
{
Object a[] = this.toArray();
Quicksort q = new Quicksort(a);
q.sort(comparator);
return fromArray(a);
}
/**
* Read lines from a BufferedReader, each as a separate String.
* The lines read are returned as an OpenList of Strings.
*
*@param reader reads the lines that are compiled into a list
*@return list of Strings read, one String per line
*/
static OpenList readLines(BufferedReader reader) throws IOException
{
String stringRead = reader.readLine();
if( stringRead == null )
return nil;
return cons(stringRead, readLines(reader));
}
/**
* test program:
* exercises a variety of the defined methods, printing out results
*/
public static void main(String arg[])
{
try
{
OpenList L0 = nil;
System.out.println("L0 = " + L0);
OpenList L1 = cons("a", cons("b", cons("c", nil)));
System.out.println("L1 = " + L1);
OpenList L2 = cons(cons("b", cons("c", nil)), cons("d", nil));
System.out.println("L2 = " + L2);
OpenList L3 = cons(L1, cons(L2, nil));
System.out.println("L3 = " + L3);
OpenList L4 = cons(L1, L2);
System.out.println("L4 = " + L4);
OpenList L5 = cons(L2, L1);
System.out.println("L5 = " + L5);
OpenList L6 = cons(new Integer(1), nil);
System.out.println("L6 = " + L6);
OpenList L7 = cons(new Integer(1),
cons(new Integer(2),
cons(new Integer(3),
cons(new Integer(4),
nil))));
System.out.println("L7 = " + L7);
System.out.println("append(L1, L2) = " + append(L1, L2));
System.out.println("reverse(L5) = " + reverse(L5));
System.out.println("append(reverse(L7), reverse(L1)) = "
+ append(reverse(L7), reverse(L1)));
System.out.println("reverse(append(L1, L7)) = "
+ reverse(append(L1, L7)));
System.out.println("L5.length() = " + L5.length());
System.out.println("L5.nth(2) = " + L5.nth(2));
System.out.println("L5.prefix(3) = " + L5.prefix(3));
System.out.println("explode(\"Hello, World\") = "
+ explode("Hello, World"));
System.out.println("implode(explode(\"Hello, World\")) = "
+ implode(explode("Hello, World")));
System.out.println("equals(append(reverse(L1), reverse(L2)), "
+ " reverse(append(L2, L1))) = "
+ equals(append(reverse(L1), reverse(L2)),
reverse(append(L2, L1))));
System.out.println("L7.equals(reverse(reverse(L7))) = "
+ L7.equals(reverse(reverse(L7))));
// This will intentionally throw an exception.
System.out.println("L5.nth(4) = " + L5.nth(4));
}
catch( Exception e )
{
System.err.println("*** caught: " + e);
}
}
}
/* Output from main:
L0 = []
L1 = [a, b, c]
L2 = [[b, c], d]
L3 = [[a, b, c], [[b, c], d]]
L4 = [[a, b, c], [b, c], d]
L5 = [[[b, c], d], a, b, c]
L6 = [1]
L7 = [1, 2, 3, 4]
append(L1, L2) = [a, b, c, [b, c], d]
reverse(L5) = [c, b, a, [[b, c], d]]
append(reverse(L7), reverse(L1)) = [4, 3, 2, 1, c, b, a]
reverse(append(L1, L7)) = [4, 3, 2, 1, c, b, a]
L5.length() = 4
L5.nth(2) = b
L5.prefix(3) = [[[b, c], d], a, b]
explode("Hello, World") = [H, e, l, l, o, ,, , W, o, r, l, d]
implode(explode("Hello, World")) = Hello, World
equals(append(reverse(L1), reverse(L2)), reverse(append(L2, L1))) = true
L7.equals(reverse(reverse(L7))) = true
*** caught: OpenListException: nth of an OpenList of length 4, where n == 4
*/