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


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

typedef struct node node_t;

struct node {
  char data [STRMAX+1]; /* Additional slot for sentinel */
  node_t * next;
};


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

char *
car (const node_t * list);
/* pre-condition:  list is an initialized, non-empty list (actually list node)
   post-condition: head of the list is returned
*/

node_t *
cdr (const node_t * list);
/* pre-condition:  list is an initialized, non-empty list (actually list node)
   post-condition: tail of the list is returned
*/

node_t *
cons (const char * newData, node_t * 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 (node_t ** 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 (node_t ** listPtr);
/* pre-condition:  none
   post-condition: *listPtr is initialized to a null list
*/

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

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

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

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

node_t *
cons (const char * newData, node_t * 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
                   if new node cannot be allocated, returns NULL and prints error
*/
  node_t * newNode = malloc (sizeof(node_t));

  if (newNode == NULL) {
    perror ("Unable to allocate node");
    return NULL;
  }
  strncpy (newNode->data, newData, STRMAX+1); /* limit copy to avoid overflow */
  newNode->data[STRMAX] = '\0'; /* ensure null termination of the string */
  newNode->next = rest;  /* define next field of node as the rest of the list */
  return newNode;        /* return newly initialized node */
} // cons

void
listDelete (node_t ** 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 rest of list */
    free (*listPtr);            /* deallocate the space for the node itself */
    *listPtr = NULL;    /* nullify list pointer, avoiding wayward refereces */
  }
} // listDelete

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

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

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

int
main (void)
{
  printf ("testing of lists-like-scheme operations\n");
  
  /* declarations */
  node_t * a;
  node_t * b;
  node_t * c;
  node_t * d;
  node_t * 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