/* Definition of data structure and operations
   for working with Scheme-like lists
*/

/* libraries for standard I/O, strings, and memory allocation */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* maximum size of an array within a list node */
#define STRMAX 50   

typedef struct Node listNode;

struct Node {
  char data [STRMAX];
  listNode* next;
};


/* ---------------------------------------------------------------- */
/* function prototypes, listed in alphabetical order */

char*
car (listNode* list);
/* pre-condition:  list is an initialized list (actually list node)
   post-condition: head of the list is returned
*/

listNode*
cdr (listNode* list);
/* pre-condition:  list is an initialized list (actually list node)
   post-condition: tail of the list is returned
*/

listNode*
cons (char* newData, listNode* rest);
/* pre-condition:  newData is an initialized string
                   rest is an intialized list
   post-condition: returns new node with newData copied to data field
                   and next field pointing to rest
*/

/* function prototypes, listed in alphabetical order */

void
listDelete (listNode** listPtr);
/* pre-condition:  *listPtr is an initialized list
   post-condition: *listPtr is changed to a NULL list
                   with any previously-defined nodes deallocated
*/

void
listInit (listNode** listPtr);
/* pre-condition:  none
   post-condition: *listPtr is initialized to a null list
*/

void
listPrint (listNode* list);
/* pre-condition:  list is an initialized list
   post-condition: data in each node is printed, Scheme-style, within ()
*/

/* ---------------------------------------------------------------- */
/* function definitions */

char*
car (listNode* list) {
/* pre-condition:  list is an initialized list (actually list node)
   post-condition: head of the list is returned
*/
  return list->data;
} // car

listNode*
cdr (listNode* list) {
/* pre-condition:  list is an initialized list (actually list node)
   post-condition: tail of the list is returned
*/
  return list->next;
} // cdr

listNode*
cons (char* newData, listNode* rest) {
/* pre-condition:  newData is an initialized string
                   rest is an initialized list
   post-condition: returns new node with newData copied to data field
                   and next field pointing to rest
*/
  listNode* newNode = (listNode*)malloc(sizeof(listNode)); 
  strncpy(newNode->data, newData, STRMAX); /* limit copying to avoid overflow */
  newNode->next = rest;  /* define next field of node as the rest of the list */
  return newNode;        /* return newly initialized node */
} // cons

void
listDelete (listNode** listPtr) {
/* pre-condition:  *listPtr is an initialized list
   post-condition: *listPtr is changed to a NULL list
                   with any previously-defined nodes deallocated
*/
  if (*listPtr != NULL)
    {
      listDelete(&((*listPtr)->next));/* recursively remove remainder of list */
      free(*listPtr);             /* deallocate the space for the node itself */
      *listPtr = NULL;    /* nullify list pointer, avoiding wayward refereces */
    }
} // listDelete

void
listInit (listNode** listPtr) {
  /* pre-condition:  none
     post-condition: *listPtr is initialized to a null list
  */
  *listPtr = NULL;
} // listInit

void
listPrint (listNode* list) {
/* pre-condition:  list is an initialized list
   post-condition: data in each node is printed, Scheme-style, within ()
*/
  listNode* listPtr = list;
  char* separator = "";

  printf("(");
  while (listPtr != NULL)
    {
      printf("%s\"%s\"", separator, listPtr->data);
      separator = " ";
      listPtr = listPtr->next;
    }
  printf(")\n");
} // listPrint
  
/* ---------------------------------------------------------------- */
/* main program: testing for lists-like-Scheme operations */

int
main (void)
{
  printf("testing of lists-like-scheme operations\n");
  
  /* declarations */
  listNode* a;
  listNode* b;
  listNode* c;
  listNode* d;
  listNode* e;
  char* str;

  /* create lists */
  listInit(&a);
  b = cons("node B", a);
  c = cons("node C", b);
  d = cons("node D", c);
  e = cdr(d);
  
  /* check list creation */
  printf("list a:  ");
  listPrint(a);
  
  printf("list b:  ");
  listPrint(b);
  
  printf("list c:  ");
  listPrint(c);
  
  printf("list d:  ");
  listPrint(d);
  
  printf("list e:  ");
  listPrint(e);
  
  /* test car operation (cdr tested earlier) */
  str = car(d);
  printf("car of list d:  %s\n", str);

  /* clean up */
  listDelete(&d);
  a = NULL;
  b = NULL;
  c = NULL;  
  e = NULL;
  printf("list d:  ");
  listPrint(d);

  printf("end of testing\n");
} // main