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

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

#include "list_interface.h"

struct node  
{
   int item; 
   link next;  
};


struct struct_list
{
   link first;
};

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

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

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


/* Creates and returns an empty list. */
list newList()
{
   list result = malloc(sizeof(*result));
   result->first = 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);
      i = next;
   }
   free(the_list);
}

/* Creates a new link, that contains the value specified in the argument, 
 * and that points to NULL. */
link newLink(int value)
{  
   link result = malloc(sizeof(struct node));
   result->item = value;
   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;
   }
}

/* Inserts new_link to the beginning of the list. */
void insertAtBeginning(list my_list, link new_link)
{
   setNext(new_link, listFirst(my_list));
   setFirst(my_list, 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;
   }
   x->next = temp->next;
   return temp;
}

// Deletes the link at the beginning of the list.
link deleteFirst(list my_list)
{
   link first = my_list->first;
   if (first != NULL)
   {
      my_list->first = first->next;
   }
   
   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->first = previous;
}

void printList(list my_list)
{
   int counter = 0;
   link i;
   printf("\n");
   for (i = my_list->first; i != NULL; i = i->next)
   {
      printf("item %d: %d\n", counter, i->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;
}


list listDeepCopy(list input)
{
   list result = newList();
   link in = listFirst(input);
   link previous = NULL;
   while (in != NULL)
   {
      link out = newLink(linkItem(in));
      insertLink(result, previous, out);
      previous = out;
      in = linkNext(in);      
   }
   
   return result;
}

/* returns a new list that contains all values of input1 and all values 
 * of input2
 */
list mergeLists(list input1, list input2)
{
   list result = listDeepCopy(input1);
   list temp2 = listDeepCopy(input2);
   mergeListsDestructive(result, temp2);
   free(temp2);
   return result;
}


/* modifies target, by inserting to it all links from source. */
void mergeListsDestructive(list target, list source)
{
   link previous = NULL;
   link c;
   
   /* find the last link of target*/
   for (c = listFirst(target); c != NULL; c = linkNext(c))
   {
      previous = c;
   }
   
   /* at this point, previous is the last link of target */
   setNext(previous, listFirst(source));
}