// file:    IntList.java
// author:  Robert Keller
// purpose: expansion of the IntList class, open list of ints

// In the open list concept, a list is identified with a reference to the 
// first cell of the list.  
//
// The empty list is called nil, which happens to be identified with
// the null reference null.  However, use of nil is preferred because
// other list models to come later will not use this implementation of nil.
//
// cons(F, R)  creates an IntList from an int F and an IntList 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 IntList L in PrintStream S

import java.io.PrintStream;

// The IntList class actually defines a cell containing the first and rest.
// It thus contains the entire list only in a figurative sense.

class IntList
{
static final IntList nil = null;          // the empty IntList

int First;                                // every non-empty list has
IntList Rest;                             // these two things


static IntList cons(int First, IntList Rest) // create a new IntList
  {
  return new IntList(First, Rest);        // see constructor below
  }


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


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


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


// IntList constructor

IntList(int First, IntList Rest) 
  {
  this.First = First;
  this.Rest = Rest;
  }


// println prints IntList as (0 1 2 3 ....) followed by new line

static void println(PrintStream S, IntList L)
  {
  print(S, L);
  S.println();
  }


// print prints IntList as (0 1 2 3 ....)

static void print(PrintStream S, IntList L)  
  {
  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 ")"
  }


// test program

public static void main(String arg[])
  {
//  IntList L = cons(0, cons(1, cons(2, cons(3, nil))));

  IntList L = range(1, 10);

  System.out.print("L = "); 
  println(System.out, L); 

  System.out.println("first(L) = " + first(L)); 

  System.out.print("rest(L) = "); 
  println(System.out, rest(L)); 

  System.out.println("first(rest(L)) = " + first(rest(L))); 

  System.out.print("rest(rest(L)) = "); 
  println(System.out, rest(rest(L))); 

  System.out.print("nil = "); 
  println(System.out, nil); 

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

  System.out.print("nth(7, reverse(L)) = "); 
  System.out.println(nth(7, reverse(L)));

  System.out.print("prefix(7, reverse(L)) = ");
  println(System.out, prefix(7, reverse(L)));
  }


// return new list of elements of L followed by those of M

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

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


// return new list of elements of L in reverse

static IntList reverse(IntList L)
  {
//  return reverse(L, nil);	alternate version
  IntList R = nil;
  while( !isEmpty(L) )
    {
    R = cons(first(L), R);
    L = rest(L);
    }
  return R;
  }


// return new list of elements of L in reverse followed by those of M

static IntList reverse(IntList L, IntList M)
  {
  if( isEmpty(L) )
    return M;

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


// return list (M M+1 M+2 .... N)
// Try doing this iteratively

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

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


// return nth element of L (n = 0, 1, 2, ...)
// Try doing this iteratively

static int nth(int n, IntList L)
  {
  if( n == 0 )
    return first(L);

  return nth(n-1, rest(L));
  }


// return length-n prefix of L

static IntList prefix(int n, IntList L)
  {
  if( n == 0 )
    return nil;

  return cons(first(L), prefix(n-1, rest(L)));  
  }
}

/* Worksheet exercises: Please add to this file and test 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)
*/