/**
 * list.c
 *   A simple implementation of lists.
 */

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>		// For strcmp

#include "node.h"
#include "list.h"

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

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


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

struct list
  {
    struct node *head;
    struct node *tail;
    int length;
  };


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

#ifdef UNIT_TESTS
int errors;
#endif


// +--------------------+---------------------------------------------
// | Exported Variables |
// +--------------------+

char *list_error = "unknown error";


// +----------------------------+-------------------------------------
// | Constructors & Destructors |
// +----------------------------+

struct list *
list_new ()
{
  struct list *lst = malloc (sizeof (struct list));
  if (lst == NULL)
    return NULL;
  lst->head = NULL;
  lst->tail = NULL;
  lst->length = 0;
  return lst;
} // list_new

void
list_free (struct list* lst)
{
  // Free all of the cons cells.
  list_clear (lst);
  // Reset values (not necessary, but safer).
  lst->length = 0;
  lst->head = NULL;
  lst->tail = NULL;
  // Free the surrounding struct
  free (lst);
} // list_free

void
list_clear (struct list *lst)
{
  struct node *garbage;
  while (lst->head != NULL)
    {
      garbage = lst->head;
      lst->head = cdr (lst->head);
      free (garbage);
    }
  lst->tail = NULL;
  lst->length = 0;
} // list_clear


// +-----------+------------------------------------------------------
// | Observers |
// +-----------+

char *
list_get (struct list *lst, int n)
{
  // Note: If the preconditions are not met, this behaves badly.
  int i;
  struct node *current = lst->head;
  for (i = 0; i < n; i++)
    current = cdr (current);
  return car (current);
} // list_get

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

int 
list_index_of (struct list *lst, char *str)
{
  int i;	// Andrew likes counter variables
  // Repeatedly advance the head until you reach the end or ...
  struct node *current = lst->head;
  i = 0;
  while (current != NULL)
    {
      // You find what you're looking for
      if (strcmp (str, car (current)) == 0)
        return i;
      // Move on to the next thing
      current = cdr (current);
      ++i;
    } // while
  // Ran out of things.  Must not be there.
  return -1;
} // list_index_of

void
list_print (struct list *lst, FILE *fp)
{
  np_print (lst->head, fp);
} // list_print


// +----------+-------------------------------------------------------
// | Mutators |
// +----------+

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

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

int 
list_append (struct list *lst, char *str)
{
  // Build a node to hold the string.
  struct node *newtail = cons (str, NULL);
  if (newtail == NULL)
    return 0;

  // Special case: List is currently empty
  if (lst->length == 0)
    {
      lst->length = 1;
      lst->head = newtail;
      lst->tail = newtail;
      return 1;
    }

  // Normal case: List is nonempty
  ++(lst->length);
  set_cdr (lst->tail, newtail);
  lst->tail = newtail;
  return 1;
} // list_append

int 
list_prepend (struct list *lst, char *str)
{
  struct node *newhead = cons (str, lst->head);
  if (newhead == NULL)
    return 0;
  lst->head = newhead;
  if (lst->tail == NULL)
    lst->tail = newhead;
  ++(lst->length);
  return 1;
} // list_prepend

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

int 
list_cut (struct list *lst, int n)
{
  // Special case: Stupid client
  if ((n < 0) || (n >= list_length (lst)))
    return 0;

  // Special case: Cutting the first element
  if (n == 0)
    {
      struct node *newhead = lst->head->next;
      free (lst->head);
      lst->head = newhead;
      --(lst->length);
      if (lst->head == NULL)
        lst->tail = NULL;
      return 1;
    }

  // Advance to the element *before* the nth element
  struct node *current = lst->head;
  int i;
  for (i = 0; i < n-1; i++)
    current = cdr (current);
  // Figure out where its next pointer should go
  struct node *newnext = current->next->next;
  // Free the element we want to delete
  free (current->next);
  // Update the before element's next pointer
  current->next = newnext;
  // Update the length
  --(lst->length);
  // Special case: Deleted the tail
  if (n == lst->length)
    lst->tail = current;
  // And we're done
  return 1;
} // list_cut


// +-----------+------------------------------------------------------
// | Iterators |
// +-----------+

void
list_foreach (struct list *lst, int (*fun)(char *))
{
  struct node *current = lst->head;
  while (current != NULL)
    {
      fun (car (current));
      current = cdr (current);
    } // while
} // list_foreach


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

#ifdef UNIT_TESTS
int
main ()
{
  struct list *lst1 = list_new ();
  struct list *lst2 = list_new ();

  CHECK_INT (list_length (lst1), 0);
  CHECK_INT (list_length (lst2), 0);

  // Create a list and make sure that we can delete the first element.
  // Create a list and make sure that we can delete the last element.
  // Make sure that it works for a length-one list.
  // More generally, try lots of lengths and lots of positions.

  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);        \
    if (LIST == NULL)                                   \
      fprintf (stderr, "<NULL>");                       \
    else                                                \
      list_print (LIST, stderr);                        \
    fprintf (stderr, "\n"); )

#define PRINT_STUFF()					\
  BLOCK(						\
    PRINT_LIST (lst1);					\
    PRINT_LIST (lst2);					\
    PRINT_INT (mem_allocated ());			\
  )

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

  PRINT_INT (mem_allocated ());

  EXPERIMENT (lst1 = list_new ());
  EXPERIMENT (lst2 = list_new ());
  PRINT_STUFF ();

  EXPERIMENT (list_prepend (lst1, stuff));
  PRINT_STUFF ();

  EXPERIMENT (list_prepend (lst1, stuff));
  PRINT_STUFF ();

  EXPERIMENT (list_prepend (lst1, "Hi"));
  PRINT_STUFF ();

  EXPERIMENT (list_prepend (lst2, "Goodbye"));
  PRINT_STUFF ();

  EXPERIMENT (list_clear (lst1));
  PRINT_STUFF ();
 
  EXPERIMENT (list_prepend (lst1, stuff));
  PRINT_STUFF ();
 
  // Testing list_index_of
  EXPERIMENT (list_clear (lst1));
  EXPERIMENT (list_append (lst1, "Alpha"));
  EXPERIMENT (list_append (lst1, "Bravo"));
  EXPERIMENT (list_append (lst1, "Charlie"));
  EXPERIMENT (list_append (lst1, "Delta"));
  EXPERIMENT (list_append (lst1, "Echo"));
  EXPERIMENT (list_append (lst1, "Foxtrot"));
  PRINT_STUFF ();
  PRINT_INT (list_index_of (lst1, "Alpha"));
  PRINT_INT (list_index_of (lst1, "Beta"));
  PRINT_INT (list_index_of (lst1, "Bravo"));
  PRINT_INT (list_index_of (lst1, "Charlie"));
  PRINT_INT (list_index_of (lst1, "Delta"));
  PRINT_INT (list_index_of (lst1, "Foxtrot"));

  // Testing list_cut
  EXPERIMENT (list_cut (lst1, 0));
  PRINT_STUFF ();
  EXPERIMENT (list_cut (lst1, list_length (lst1) - 1));
  PRINT_STUFF ();
  EXPERIMENT (list_cut (lst1, 2));
  PRINT_STUFF ();
  EXPERIMENT (list_clear (lst2));
  EXPERIMENT (list_prepend (lst2, "One Element"));
  PRINT_STUFF ();
  EXPERIMENT (list_cut (lst2, 0));
  PRINT_STUFF ();
  

  // Create a list and make sure that we can delete the first element.
  // Create a list and make sure that we can delete the last element.
  // Make sure that it works for a length-one list.
  EXPERIMENT (list_free (lst1));
  EXPERIMENT (list_free (lst2));
  PRINT_INT (mem_allocated ());

  return 0;
} // main

#endif // EXPERIMENTS