SE250:lab-4:rwan064:code

#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;

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

element_t first( Cons* list )
{
	if ( length( list ) >= 1 ) {
		return list->head;
	}
	else {
		// length of list is less than one so a first element cannot exist.
		return 0;
	}
}
element_t second( Cons* list )
{
	if ( length( list ) >= 2 ) {
		Cons *cp = list;
		int i;
		for ( i = 0; i < 1; i++ ) {
			cp = cp->tail;
		}
		return cp->head;
	}
	else {
		return 0;
	}
}
element_t third( Cons* list )
{
	if ( length( list ) >= 3 ) {
		Cons *cp = list;
		int i;
		for ( i = 0; i < 2; i++ ) {
			cp = cp->tail;
		}
		return cp->head;
	}
	else {
		return 0;
	}
}
element_t fourth( Cons* list )
{
	if ( length( list ) >= 4 ) {
		Cons *cp = list;
		int i;
		for ( i = 0; i < 3; i++ ) {
			cp = cp->tail;
		}
		return cp->head;
	}
	else {
		return 0;
	}
}

element_t nth( int i, Cons *list )
{
	if ( length( list ) >= i ) {
		Cons *cp = list;
		int count;
		for ( count = 0; count < (i-1); count++ ) {
			cp = cp->tail;
		}
		return cp->head;
	}
	else {
		return 0;
	}
}

int equal( Cons *xs, Cons *ys )
{
	if ( length( xs ) == length( ys ) ) {
		Cons *cp;
		int i = 1;
		for ( cp = xs; cp != nil; cp = cp->tail ) {
			if ( cp->head != nth( i, ys ) ) {
				return 0;
			}
			i++;
		}
		return 1;
	}
	else {
		return 0;
	}
}

Cons* find( element_t t, Cons* list )
{
	Cons *cp;
	for ( cp = list; cp != nil; cp = cp->tail ) {
		if ( cp->head == t ) {
			return cp;
		}
	}
	return 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" );
}


Cons* copy_list( Cons *list )
{
	Cons *cp = nil;
	Cons *copy = nil;
	
	int len = length(list);
	element_t ts[ len ];
	int i = 0;
	
	for ( cp = list; cp != nil; cp = cp->tail ) {
		ts[ i ] = cp->head;
		i++;
	}
	if ( i != 0 ) {
		i = 0;
		for ( i = (len - 1); i >= 0; i-- ) {
			copy = cons( ts[i], copy );
		}
	}
	return copy;
}

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

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

Cons* reverse( Cons *xs )
{
	Cons *cp = nil;
	Cons *copy = nil;
	
	for ( cp = xs; cp != nil; cp = cp->tail ) {
		copy = cons( cp->head, copy );
	}
	return copy;
}

Cons* nreverse( Cons *xs )
{
	Cons *cp = nil;
	
	int len = length( xs );
	element_t ts[ len ];
	int i = 0;
	
	for ( cp = xs; cp != nil; cp = cp->tail ) {
		ts[ i ] = cp->head;
		i++;
	}
	if ( i != 0 ) {
		i = len - 1;
		for ( cp = xs; cp != nil; cp = cp->tail ) {
			cp->head = ts[i];
			i--;
		}
		cp = xs;
	}
	
	return cp;
}
/* 2nd try for the destructive reverse function */
Cons *nnreverse( Cons *xs )
{
	Cons *prev = xs;
	Cons *cp = xs->tail;
	prev->tail = nil;
	while ( cp != nil ) {
		Cons *t = cp->tail;
		cp->tail = prev;
		prev = cp;
		cp = t;
	}
	return prev;
}

int main( )
{
	printf( "\n" );
	
	print_list( cons(1,cons(2,cons(3,nil))) ); /* expect: List[1,2,3] */
	
	Cons *my_list = cons(2, cons(4, cons(6, cons(8, nil))));
	print_list( my_list );
	printf( "Length of my_list is %d\n", length(my_list) );
	
	printf( "First element is %d\n"
			"Second element is %d\n"
			"Third element is %d\n"
			"Fourth element is %d\n", 
			first( my_list ), second( my_list ), third( my_list ), fourth( my_list ) );
	
	
	int i;
	for ( i = 0; i < 10; i++ ) {
		printf( "The %d'th element is %d\n", i, nth( i, my_list ) );
	}

	Cons *xs = cons(1, cons(2, nil));
	Cons *ys = cons(1, cons(2, xs));
	
	print_list( xs );
	print_list( ys );
	
	printf( "The two lists xs and ys are %s\n", (equal(xs, ys) == 1) ? "equal" : "not equal" );


	Cons *cp = cons(1, cons(2, cons(3, nil)));
	
	Cons *result = find( 4, cp );
	printf( "%d\n", (result == nil) ? 0 : result->head );
	
	
	Cons *cp = cons(67, cons(45, cons(21, cons(89, nil))));
	
	print_list( cp );
	print_list( copy_list( cp ) );
	
	printf( "%s\n", (equal( cp, copy_list(cp) ) == 1) ? "equal" : "not equal" );
	
	
	Cons *xs = cons(1, cons(2, cons(3, nil)));
	Cons *ys = cons(4, cons(5, cons(6, nil)));
	Cons *zs = append( xs, ys );
	
	print_list( xs );
	print_list( ys );
	print_list( zs );
	
	ys->head = 5;
	print_list( ys );
	print_list( zs );


	Cons *xs = cons(1, cons(2, cons(3, nil)));
	Cons *ys = cons(4, cons(5, cons(6, nil)));
	Cons *zs = nappend( xs, ys );
	print_list( xs );
	print_list( ys );
	print_list( zs );
	
	xs->head = 3;
	ys->head = 5;
	
	print_list( xs );
	print_list( ys );
	print_list( zs );

	Cons *xs = cons(1, cons(2, cons(3, cons(4, cons(5, cons(6, nil))))));
	print_list( xs );
	Cons *ys = nnreverse( xs );
	
	print_list( xs );

	print_list( ys );

	return 0;
}