// file:    list2.java
// author:  Robert Keller
// purpose: expansion of the List class, open list of integers
//          Here we add various functions such as append, range, and reverse

// exercises: You add the following:
//           nth(int n, List L) returns the nth element of L (n = 0, 1, 2, ...)
//           last(List L) returns the last element of L
//           prefix(int n, List L) returns the length-n prefix of L
//           member(int n, List L) tells whether n is in L
//           insertAt(int n, List L, int k) makes a new list like L except
//             that k is inserted at position n
//           insertAt(int n, List L, List K) makes a new list like L except
//             that list K is inserted starting at position n
//           dropAt(int n, List L) makes a new list like L except
//             that the nth element is dropped out
//           change(int n, List L, int k) makes a new list like L except
//             that the nth element is replaced by k (non-destructively)

// In the open list concept, a List is a REFERENCE to the first cell 
// of the list.  
// Thus the empty List is identified with null, the null reference,
// which is part of the Java language.  However, we call this list
// nil rather than null, to indicate its use as a list.
//
// cons(F, R)  creates a List from an element F and a list R.
// first(L)    returns the first of a non-empty list
// rest(L)     returns all but the first of a non-empty list
// isEmpty(L)  tells whether L is empty
// print(L, S) prints L in PrintStream S

import java.io.PrintStream;

class List
{
int First;                              // every non-empty list has
List Rest;                              // these two things

static List cons(int First, List Rest)  // creat a new list
  {
  return new List(First, Rest);         // defined in constructor below
  }


static int first(List L)                // get First
  {
  return L.First;
  }


static List rest(List L)                // get Rest
  {
  return L.Rest;
  }


static boolean isEmpty(List L)          // tell whether empty
  {
  return L == nil;
  }


static final List nil = null;           // empty list


static void print(List L, PrintStream S)  // print list as (1 2 3 ....)
  {
  S.print("(");                 // print opening "("
  
  if( !isEmpty(L) )
    {
    S.print(first(L));          // print first element if any

    L = rest(L);
  
    while( !isEmpty(L) )          // print rest of elements
      {
      S.print(" ");
      S.print(first(L));
      L = rest(L);
      }
    }

  S.print(")");                 // print closing ")"
  }


static void println(List L, PrintStream S)      // print list with eol
  {
  print(L, S);
  S.println();
  }


// append(L, M) creates a new List with List M appended to L

static List append(List L, List M)
  {
  if( isEmpty(L) )
    return M;

  return cons(first(L), append(rest(L), M));
  }


// range(M, N) creates the list (M M+1 .... N)

static List range(int M, int N)
  {
  if( M > N )
    return nil;

  return cons(M, range(M+1, N));
  }


// reverse(L) creates the reverse of List L

static List reverse(List L)
  {
  List R = nil;
  while( !isEmpty(L) )
    {
    R = cons(first(L), R);
    L = rest(L);
    }
  return R;
  } 


public static void main(String arg[])   // main program or test
  {
  List L = range(1, 10);
  List M = range(11, 15);

  System.out.print("L = ");            println(L, System.out);
  System.out.print("M = ");            println(M, System.out);
  System.out.print("append(L, M) = "); println(append(L, M), System.out);
  System.out.print("reverse(L) = ");   println(reverse(L), System.out);
  }


List(int First, List Rest)      // List constructor
  {
  this.First = First;
  this.Rest = Rest;
  }
}