/* This program uses code from "Algorithms in C, Third Edition,"
 *               by Robert Sedgewick, Addison-Wesley, 1998.
 */

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

#include "lists.h"

struct node  
{
   void * item; 
   link next;  
};


struct struct_list
{
   link first;
   link last;
};

link listFirst(list the_list)
{
   return the_list->first;
}

link listLast(list the_list)
{
   return the_list->last;
}

link linkNext(link the_link)
{
   return the_link->next;
}

void * linkItem(link the_link)
{
   return the_link->item;
}


/* Creates and returns an empty list. */
list newList()
{
   list result = malloc(sizeof(*result));
   result->first = NULL;
   result->last = NULL;
   return result;
}

/* Deallocates memory for all nodes in the list. */
void destroyList(list the_list)
{
   link i = the_list->first;
   while(1)
   {
      if (i == NULL)
      {
         break;
      }
      
      link next = i->next;
      free(i->item);
      free(i);
      i = next;
   }
   free(the_list);
}


// returns 1 if the list is empty, 0 otherwise.
int listEmpty(list the_list)
{
   if (the_list->first == NULL)
   {
      return 1;
   }
   else
   {
      return 0;
   }
}

/* Creates a new link, that contains the specified value, 
 * and that points to NULL. */
link newLink(void * content)
{  
   link result = malloc(sizeof(struct node));
   result->item = content;
   result->next = NULL;
   return result;
}

/* Creates a new link, that contains the value specified in the argument, 
 * and that points to NULL. */
link newIntLink(int value)
{  
   link result = malloc(sizeof(struct node));
   int * content = malloc(sizeof(int));
   *content = value;
   result->item = content;
   result->next = NULL;
   return result;
}

/* Inserts new_link to the specified list, at the position right after
 * the link called "previous". */
void insertLink(list my_list, link previous, link new_link)
{
   /* We need a special case when we want to insert to the beginning.
    * In that case, the previous link is NULL. */
   if (previous == NULL)
   {
      new_link->next = my_list->first;
      my_list->first = new_link;
   }
   else
   {
      new_link->next = previous->next;
      previous->next = new_link;
   }
   if (my_list->last == previous)
   {
      my_list->last = new_link;
   }
}

/* Inserts new_link to the beginning of the list. */
void insertAtBeginning(list my_list, link new_link)
{
   new_link->next = my_list->first;
   if (my_list->last == NULL)
   {
      my_list->last = new_link;
   }
   my_list->first = new_link;
}

/* Inserts new_link to the end of the list. */
void insertAtEnd(list my_list, link new_link)
{
   if (my_list->last == NULL)
   {
      my_list->first = new_link;
   }
   else
   {
      setNext(my_list->last, new_link);
   }
   
   my_list->last = new_link;
 }


/* Deletes the link coming AFTER link x. This function DOES NOT  DELETE
 * link x itself. */
link deleteNext(list my_list, link x)
{
   link temp = x->next;
   if (temp == my_list->first)
   {
      my_list->first = temp->next;
   }
   if (temp == my_list->last)
   {
      my_list->last = NULL;
   }
   x->next = temp->next;
   return temp;
}

// Deletes the link at the beginning of the list.
link deleteAtBeginning(list my_list)
{
   link first = my_list->first;
   if (first != NULL)
   {
      my_list->first = first->next;
   }
   if (first == my_list->last)
   {
      my_list->last = NULL;
   }   
   return first;
}

void reverse(list the_list)
{ 
   link current = the_list->first;
   link previous = NULL;
   while (current != NULL)
   { 
      link temp = current->next; 
      current->next = previous; 
      previous = current; 
      current = temp; 
   }    
   the_list->last = the_list->first;
   the_list->first = previous;
}

void printIntList(list my_list)
{
   int counter = 0;
   link i;
   printf("\n");
   for (i = my_list->first; i != NULL; i = i->next)
   {
      int * item = (int *) i->item;
      printf("item %d: %d\n", counter, *item);
      counter++;
   }
   printf("\n");
}

int listLength(list my_list)
{
   int counter = 0;
   link i;
   for (i = my_list->first; i != NULL; i = i->next)
   {
      counter++;
   }
   return counter;
}

void setFirst(list the_list, link first)
{
   the_list->first = first;
}

void setNext(link the_link, link next)
{
   the_link->next = next;
}