SE250:lab-4:jham005

/*
  File: lab-4-soln.c
  Date: 1 April 2008
  Author: John Hamer
  Purpose: Sample solution to SOFTENG lab #4, 2008
*/

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

typedef int element_t;

typedef
struct Cons {
  element_t head;
  struct Cons* tail;
} Cons;

static Cons NIL = { 0, &NIL };
Cons* nil = &NIL;


Cons* cons( element_t elt, Cons* tail ) {
  Cons* cell = malloc( sizeof(Cons) );
  assert( cell != 0 );
  cell->head = elt;
  cell->tail = tail;
  return cell;
}


void print_list( Cons* list ) {
  char* sep = "";
  printf( "List[" );
  for( ; list != nil; list = list->tail ) {
    printf( "%s%d", sep, list->head );
    sep = ",";
  }
  printf( "]\n" );
}


int length( Cons* list ) {
  int len = 0;
  for( ; list != nil; list = list->tail )
    len++;
  return len;
}


element_t first(  Cons* list ) { return list->head; }
element_t second( Cons* list ) { return list->tail->head; }
element_t third(  Cons* list ) { return list->tail->tail->head; }
element_t fourth( Cons* list ) { return list->tail->tail->tail->head; }

element_t nth( int i, Cons* list ) {
  while( i-- > 0 )
    list = list->tail;
  return list->head;
}


int equal( Cons* xs, Cons* ys ) {
  while( xs != nil && ys != nil ) {
    if( xs->head != ys->head )
      return 0;
    xs = xs->tail;
    ys = ys->tail;
  }
  return xs == ys;
}


Cons* find( element_t elt, Cons* list ) {
  for( ; list != nil; list = list->tail )
    if( list->head == elt )
      break;
  return list;
}


Cons* append( Cons* xs, Cons* ys ) {
  Cons* result;			/* deliberately left uninitialised */
  Cons** cpp = &result;		/* pointer to the last uninitialised list pointer */
  for( ; xs != nil; xs = xs->tail ) {
    *cpp = cons(xs->head, (Cons*)0); /* nil would be misleading; this list is incomplete */
    cpp = &(*cpp)->tail;
  }
  *cpp = ys;
  return result;
}

Cons* copy_list( Cons* list ) { return append( list, nil ); }


Cons* nappend( Cons* xs, Cons* ys ) {
  if( xs == nil )
    return ys;
  else {
    Cons* cp = xs;
    while( cp->tail != nil )
      cp = cp->tail;
    cp->tail = ys;
  }
  return xs;
}


Cons* reverse( Cons* list ) {
  Cons* rev = nil;
  for( ; list != nil; list = list->tail )
    rev = cons( list->head, rev );
  return rev;
}


Cons* nreverse( Cons* list ) {
  Cons* prev = nil;
  Cons* next;
  for( ; list != nil; list = next ) {
    next = list->tail;
    list->tail = prev;
    prev = list;
  }
  return prev;
}


int main( ) {
  print_list( nil );				/* List[] */
  print_list( cons(10,cons(20,cons(30,nil))) ); /* List[10,20,30] */

  assert( length( nil ) == 0 );
  assert( length( cons(10,cons(20,cons(30,nil))) ) == 3 );

  assert( first( nil ) == 0 );
  assert( first( cons(10,cons(20,nil)) ) == 10 );

  assert( second( nil ) == 0 );
  assert( second( cons(10,cons(20,nil)) ) == 20 );

  assert( third( nil ) == 0 );
  assert( third( cons(10,cons(20,nil)) ) == 0 );
  assert( third( cons(10,cons(20,cons(30,nil))) ) == 30 );

  assert( fourth( nil ) == 0 );
  assert( fourth( cons(10,cons(20,nil)) ) == 0 );
  assert( fourth( cons(10,cons(20,cons(30,nil))) ) == 0 );
  assert( fourth( cons(10,cons(20,cons(30,cons(40,nil)))) ) == 40 );

  assert( nth(0,nil) == 0 );
  assert( nth(1,nil) == 0 );
  assert( nth(0,cons(10,nil)) == 10 );
  assert( nth(1,cons(10,nil)) == 0 );

  assert( equal(nil,nil) );
  assert( ! equal(nil,cons(10,nil)) );
  assert( ! equal(cons(10,nil),nil) );
  assert( equal(cons(10,nil),cons(10,nil)) );
  assert( ! equal(cons(10,nil),cons(20,nil)) );

  print_list( find(10,nil) );		/* List[] */
  print_list( find(20,cons(10,nil)) );	/* List[] */
  print_list( find(10,cons(10,nil)) );	/* List[10] */

  print_list( append(nil,nil) );	  /* List[] */
  print_list( append(nil,cons(10,nil)) ); /* List[10] */
  print_list( append(cons(10,nil),nil) ); /* List[10] */
  print_list( append(cons(10,nil),cons(20,nil)) ); /* List[10,20] */

  print_list( copy_list(nil) );		 /* List[] */
  print_list( copy_list(cons(10,nil)) ); /* List[10] */
  print_list( copy_list(cons(10,cons(20,nil))) ); /* List[10,20] */

  print_list( nappend(nil,nil) );	   /* List[] */
  print_list( nappend(nil,cons(10,nil)) ); /* List[10] */
  print_list( nappend(cons(10,nil),nil) ); /* List[10] */
  print_list( nappend(cons(10,nil),cons(20,nil)) ); /* List[10,20] */

  print_list( reverse(nil) );			/* List[] */
  print_list( reverse(cons(10,nil)) );		/* List[10] */
  print_list( reverse(cons(10,cons(20,nil))) );	/* List[20,10] */

  print_list( nreverse(nil) );			/* List[] */
  print_list( nreverse(cons(10,nil)) );		/* List[10] */
  print_list( nreverse(cons(10,cons(20,nil))) ); /* List[20,10] */

  return 0;
}

/*
Local Variables:
compile-command: "gcc -Wall lab-4-soln.c -o lab-4-soln && ./lab-4-soln"
End:
*/