// file:    OpenList.java
// author:  Robert M. Keller
// purpose: Implement Open Lists is java

import OpenListException;

/**
 * OpenList is a type of uni-directional linked list that permits sharing
 * of list tails.  It is similar to the list representation used in many 
 * functional languages, such as rex, Lisp, etc.
 */

class OpenList
{
/** 
 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 = ", ";


/** 
 * 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.
 */

final public static OpenList nil = cons(null, null);


/** exception message for first of empty list */

public static String firstOfOpenListException = "first() of empty list";


/** exception message for rest of empty list */

public static String restOfOpenListException = "rest() of empty list";


/** 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 "factor") 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 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(firstOfOpenListException);
    }
  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
 * will be thrown.
 */

public OpenList rest() throws OpenListException
  {
  if( isEmpty() ) 
    {
    throw new OpenListException(restOfOpenListException);
    }
  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));
    }
  }


/** 
 * 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 the number of elements of this list.
 * @return the number of elements of this list
 */

public int length()
  {
  OpenList L  = this;
  int result = 0;
  for( ; L.nonEmpty(); L = L.rest() )
    {
    result++;
    }

  return result;
  }



/** 
 * 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
  {
  int remaining = n;
  OpenList L  = this;

  try
    {
    while( remaining > 0 )
      {
      L = L.rest();
      remaining--;
      }
    return L.first();
    }
  catch( OpenListException e )
    {
    throw new OpenListException("nth of an OpenList of length " + length()
                              + ", where n == " + n);
    }
  }




/** 
 * 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.
 * 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));
  }


/** 
 * Convert this OpenList to a String, using default punctuation.
 *
 * @return String representing 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();
  }


/** 
 * 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("L5.nth(4) = " + L5.nth(4));
    }
  catch( Exception e )
    {
    System.err.println("*** caught: " + e);
    }
  }

}