---

OpenList.java

Go to the documentation of this file.

// 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 <i>only</i>
 * 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 <i>only</i>
 * 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

*/

---