// file:    list2a.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
//          and give ansers to the following exercises: 

// 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)

/* The output of this program is:

    L = (1 2 3 4 5 6 7 8 9 10)
    M = (11 12 13 14 15)
    append(L, M) = (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
    reverse(L) = (10 9 8 7 6 5 4 3 2 1)
    nth(3, M) = 14
    last(M) = 15
    prefix(3, M) = (11 12 13)
    member(15, M) = true
    member(16, M) = false
    insertAt(2, M, 99) = (11 12 99 13 14 15)
    insertAt(2, M, L) = (11 12 1 2 3 4 5 6 7 8 9 10 13 14 15)
    dropAt(3, M) = (11 12 13 15)
    change(2, M, 99) = (11 12 99 14 15)
    L = (1 2 3 4 5 6 7 8 9 10)
    M = (11 12 13 14 15)
*/

// Note that in printing, we use
//
//    System.out.println(int n)   to print an int n, but
//    println(List L, System.out) to print a list L
//
// This is because the system method println doesn't know how to print lists
// as we want to see them.  So we have defined a static function println
// to handle lists.  Later on, with a slightly different definition of List,
// we will see how to define System.out.println(List L).

// 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;
  } 


// nth(int n, List L) returns the nth element of L (n = 0, 1, 2, ...)

static int nth(int n, List L)
  {
  while( n > 0 )
    {
    L = rest(L);
    n--;
    }
  return first(L);
  }


// last(List L) returns the last element of L

static int last(List L)
  {
  while( !isEmpty(rest(L)) )
    {
    L = rest(L);
    }  
  return first(L);
  }


// prefix(int n, List L) returns the length-n prefix of L

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

  return cons(first(L), prefix(n-1, rest(L)));
  }


// member(int n, List L) tells whether n is in L

static boolean member(int n, List L)
  {
  while( !isEmpty(L) )
    { 
    if( n == first(L) )
      return true;
    L = rest(L);
    }
  return false;
  }


// insertAt(int n, List L, int k) makes a new list like L except
//   that k is inserted at position n

static List insertAt(int n, List L, int k)
  {
  if( n == 0 )
    return cons(k, L);

  return cons(first(L), insertAt(n-1, rest(L), k));
  }


// insertAt(int n, List L, List K) makes a new list like L except
//   that list K is inserted starting at position n

static List insertAt(int n, List L, List K)
  {
  if( n == 0 )
    return append(K, L);

  return cons(first(L), insertAt(n-1, rest(L), K));
  }


// dropAt(int n, List L) makes a new list like L except
//   that the nth element is dropped out

static List dropAt(int n, List L)
  {
  if( n == 0 )
    return rest(L);

  return cons(first(L), dropAt(n-1, rest(L)));
  }


// change(int n, List L, int k) makes a new list like L except
//   that the nth element is replaced by k (non-destructively)

static List change(int n, List L, int k) 
  {
  if( n == 0 )
    return cons(k, rest(L));

  return cons(first(L), change(n-1, rest(L), k));
  }


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);
  System.out.print("nth(3, M) = ");     System.out.println(nth(3, M));
  System.out.print("last(M) = ");       System.out.println(last(M));
  System.out.print("prefix(3, M) = ");  println(prefix(3, M), System.out);
  System.out.print("member(15, M) = "); System.out.println(member(15, M));
  System.out.print("member(16, M) = "); System.out.println(member(16, M));
  System.out.print("insertAt(2, M, 99) = "); 
                                       println(insertAt(2, M, 99), System.out);

  System.out.print("insertAt(2, M, L) = "); 
                                        println(insertAt(2, M, L), System.out);
  System.out.print("dropAt(3, M) = ");  println(dropAt(3, M), System.out);
  System.out.print("change(2, M, 99) = "); 
                                        println(change(2, M, 99), System.out);
  System.out.print("L = ");             println(L, System.out);
  System.out.print("M = ");             println(M, System.out);
  }


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