/**
 * list2.c
 *   Doubly-linked lists.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

#ifdef UNIT_TESTS
#include "utest.h"
#endif


// +-------+----------------------------------------------------------
// | Types |
// +-------+

struct dnode {
  char *data;
  struct dnode *next;
  struct dnode *prev;
};

struct list {
  struct dnode *head;   // The first element
  struct dnode *tail;   // The last element
  int size;             // The number of elements
};


// +---------+--------------------------------------------------------
// | Globals |
// +---------+

#ifdef UNIT_TESTS
static int errors;
#endif

// +-----------------+------------------------------------------------
// | Basic Functions |
// +-----------------+

struct list *new_list ()
{
  struct list *result;
  result = malloc (sizeof (struct list));
  if (result != NULL)
    {
      result->head = NULL;
      result->tail = NULL;
    }
  return result;
} // new_list

char *
list_first (struct list *lst)
{
  if (lst->head == NULL)
    return NULL;
  else
    return lst->head->data;
} // list_first

char *
list_last (struct list *lst)
{
  if (lst->tail == NULL)
    return NULL;
  else
    return lst->tail->data;
} // list_last

int 
list_length (struct list *lst)
{
  return lst->size;
} // list_length

void
list_print (struct list *lst, FILE *fp)
{
  struct dnode *current = list->head;

  if (current== NULL)
    {
      fprintf (fp, "()");
      return;
    }

  fprintf (fp, "(%s", current->data);
  while ((current = current->next) != NULL)
    fprintf (fp, " %s", current->data);
  fprintf (fp, ")");
} // list_print

int 
list_append (struct list *lst, char *str)
{
  struct dnode *newnode = malloc (sizeof (struct dnode));
  if (newnode == NULL)
    return 0;

  // Fill in fields
  newnode->data = str;
  // newnode->next = ???
  // newnode->prev = ???

  if (lst->size == 0)
    {
      lst->head = newnode;
      lst->tail = newnode;
    }
  else
    {
      set_cdr (lst->tail, newnode);
      lst->tail = newnode;
    }
  ++(lst->size);
  return 1;
} // list_append

int 
list_prepend (struct list *lst, char *str)
{
  struct dnode *newnode = malloc (sizeof (struct dnode));
  if (newnode == NULL)
    return 0;

  // Fill in fields
  newnode->data = str;
  // newnode->next = ???
  // newnode->prev = ???

  lst->head = newnode;
  if (lst->size == 0)
    lst->tail = newnode;
  ++(lst->size);
  return 1;
} // list_prepend

int
list_delete (struct list *lst, char *str)
{
  return 0;
} // list_delete


// +------------+-----------------------------------------------------
// | Unit Tests |
// +------------+

#ifdef UNIT_TESTS
int
main ()
{
  fprintf (stderr, "%d errors encountered.\n", errors);
  return errors;
} // main
#endif // UNIT_TESTS


/**
 * node.c
 *   Nodes for an implementation of lists.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>
#include <stdlib.h>
#include "node.h"

#ifdef UNIT_TESTS
#include "utest.h"
#endif

#ifdef EXPERIMENTS
#include "expt.h"
#endif


// +---------+--------------------------------------------------------
// | Globals |
// +---------+

#ifdef UNIT_TESTS
static int errors;
#endif


// +-----------------+------------------------------------------------
// | Basic Functions |
// +-----------------+

int 
is_null (struct node *lst)
{
  return lst == NULL;
} // is_null

struct node *
cons (char *str, struct node *lst)
{
  struct node *newlst = malloc (sizeof (struct node));
  if (newlst == NULL)
    return NULL;
  newlst->data = str;
  newlst->next = lst;
  return newlst;
} // cons

char *
car (struct node *lst)
{
  if (is_null (lst))
    {
      fprintf (stderr, "Cannot take car of empty list.\n");
      return NULL;
    }

  return lst->data;
} // car

struct node *
cdr (struct node *lst)
{
  if (is_null (lst))
    {
      fprintf (stderr, "Cannot take car of empty list.\n");
      return NULL;
    }

  return lst->next;
} // cdr

struct node *
set_car (struct node *lst, char *str)
{
  if (is_null (lst))
    {
      fprintf (stderr, "Cannot set the car of empty list.\n");
      return NULL;
    }
  lst->data = str;
  return lst;
} // set_car

struct node *
set_cdr (struct node *lst, struct node *rest)
{
  if (is_null (lst))
    {
      fprintf (stderr, "Cannot set the cdr of empty list.\n");
      return NULL;
    }
  lst->next = rest;
  return lst;
} // set_cdr


// +--------------------+---------------------------------------------
// | Advanced Functions |
// +--------------------+

char *
np_last (struct node *lst)
{
  if (is_null (lst))
    {
      fprintf (stderr, "Cannot take last element of empty list.\n");
      return NULL;
    }
  while (lst->next != NULL)
    lst = lst->next;
  return lst->data;
} // np_last

int 
np_length (struct node *lst)
{
  int length;
  for (length = 0; lst != NULL; length++, lst = lst->next)
    ;
  return length;
} // np_length

void 
np_print (struct node *lst, FILE *fp)
{
  if (lst == NULL)
    {
      fprintf (fp, "()");
      return;
    }

  fprintf (fp, "(%s", lst->data);
  while ((lst = lst->next) != NULL)
    fprintf (fp, " %s", lst->data);
  fprintf (fp, ")");
} // np_print

struct node *
np_append (struct node *lst, char *str)
{
  struct node *np = lst;
  if (lst == NULL)
    return cons (str, NULL);
  while (np->next != NULL) 
    np = np->next;
  np->next = cons (str, NULL);
  return lst;
} // np_append

struct node *
np_delete (struct node *lst, char *str)
{
  // Not yet implemented
  return lst;
} // np_delete


// +------------+-----------------------------------------------------
// | Unit Tests |
// +------------+

#ifdef UNIT_TESTS
int
main ()
{
  struct node *np = NULL;

  CHECK_INT (is_null (np), 1);

  fprintf (stderr, "%d errors encountered.\n", errors);
  return errors;
} // main
#endif // UNIT_TESTS


// +-------------+----------------------------------------------------
// | Experiments |
// +-------------+

#ifdef EXPERIMENTS

#define PRINT_LIST(LIST) \
  BLOCK( \
    fprintf (stderr, VAR_PREFIX "%s = ", #LIST);  \
    np_print (LIST, stderr); \
    fprintf (stderr, "\n"); )

int
main ()
{
  struct node *lst1, *lst2;
  char stuff[] = "Hello";
  struct node *greet;

  EXPERIMENT (lst1 = NULL);
  PRINT_LIST (lst1);
  EXPERIMENT (lst2 = cons ("a", lst1));
  PRINT_LIST (lst1);
  PRINT_LIST (lst2);
  EXPERIMENT (lst1 = cons ("b", lst2));
  PRINT_LIST (lst1);
  PRINT_LIST (lst2);

  EXPERIMENT (lst1 = np_append (lst1, "seek"));
  PRINT_LIST (lst1);
  PRINT_LIST (lst2);

  EXPERIMENT (greet = cons (stuff, NULL));
  EXPERIMENT (greet = cons (stuff, greet));
  PRINT_LIST (greet);
  EXPERIMENT (stuff[0] = '\'');
  PRINT_LIST (greet);

  EXPERIMENT (set_car(greet, "Why,"));
  PRINT_LIST (greet);

  EXPERIMENT (set_cdr(greet, lst2));
  PRINT_LIST (greet);

  PRINT_STR (car(greet));
  PRINT_STR (car (cdr (greet)));

  EXPERIMENT (set_cdr(greet, greet));
  PRINT_STR (car(greet));
  PRINT_STR (car (cdr (greet)));


  return 0;
} // main
#endif // EXPERIMENTS