/* words4.c
 *
 * Input and print a list of words, 
 * implemented with a doubly linked list of words
 * (see e.g. http://en.wikipedia.org/wiki/Doubly_linked_list)
 * defined using struct and malloc.
 *
 * Here only the input buffer is on the stack.
 * The space for the word_list object, each word object,
 * and the word object's data (the string) are all on the heap,
 * with explicit functions to create and destroy all the pieces.
 *
 * A linked list like this has the advantages that it has an
 * arbitrary size, and that inserting an element is O(1).
 * However, accessing the n'th element requires following
 * the links and is O(n) ... albeit with fast steps.
 *
 * The interface and implementation of the word list
 * could be moved to separate files word_list.h and word_list.c
 *
 *   $ gcc words3.c -o words3
 *   $ ./words3
 *   Input one word per line, terminated by a blank line.
 *    1: one
 *    2: two
 *    3: three
 *    4: 
 *    The list has 3 words : [one, two, three].
 *
 * *Now* we're having fun.
 *
 * Jim Mahoney | Feb 2013 | MIT License
 */

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

// --- word_list.h  --------------------------------------------------

#define WORD_LENGTH_LIMIT 100

typedef struct _word *word;
struct _word {
  word next;
  word prev;
  char* data;
};

typedef struct _word_list *word_list;
struct _word_list {
  int length;
  word first;
  word last;
};

word new_word(char* string);          // copy string into new word & return it
void free_word(word w);               // free memory for word & its data

word_list new_word_list();            // initially empty
void free_word_list(word_list list);  // free memory for list, words, & data

void push(word_list list, word w);    // append a word to the end of the list
word pop(word_list list);             // remove & return last word from list
void read_next_word(word_list list);  // read from stdin, push word on list
void print_word_list(word_list list); // "['word1', 'word2', ...]" to stdout

// --- word_list.c  --------------------------------------------------

word new_word(char* string){
  word w = malloc(sizeof(struct _word));
  w->data = malloc(sizeof(strlen(string)+1)); // +1 for trailing 0
  strcpy(w->data, string);
  w->next = NULL;
  w->prev = NULL;
  return w;
}

void free_word(word w){
  free(w->data);
  free(w);
}

word_list new_word_list(){
  word_list list = malloc(sizeof(struct _word_list));
  list->length = 0;
  list->first = NULL;
  list->last = NULL;
  return list;
}

void free_word_list(word_list list){
  word w = list->first;
  word next;
  while (w != NULL){
    next = w->next;
    free_word(w);
    w = next;
  }
  free(list);
}

void push(word_list list, word w){
  if (list->length == 0){
    list->first = w;
    list->last = w;
    list->length = 1;
  }
  else {
    w->prev = list->last;
    list->last->next = w;
    list->last = w;
    list->length++;
  }
}

word pop(word_list list){
  word w = list->last;
  if (w != NULL){
    list->last = w->prev;
    w->prev = NULL;
    list->length--;
  }
  if (list->length == 0){ 
    list->first = NULL;
  }
  else {
    list->last->next = NULL;
  }
  return w;
}

void read_next_word(word_list list){
  char input_buffer[WORD_LENGTH_LIMIT];
  char* status = fgets(input_buffer, WORD_LENGTH_LIMIT, stdin);
  int length = strlen(input_buffer);
  if (status == NULL || length == 0) return;  // if error do nothing
  if (input_buffer[length - 1] == '\n'){      // remove trailing newline
    input_buffer[length - 1] = (char) 0; 
    length--; 
  }
  push(list, new_word(input_buffer));
}

void print_word_list(word_list list){
  word w = list->first;
  printf("[");
  while (w != NULL){
    printf("%s", w->data);
    if (w->next != NULL) printf(", ");
    w = w->next;
  }
  printf("]");
}

// --- main ----------------------------------------------------------

int main(){
  word_list list = new_word_list();
  printf("Input one word per line, terminated by a blank line.\n");
  while (1){
    printf(" %i: ", list->length + 1);
    read_next_word(list);
    if (strlen(list->last->data) == 0){
      pop(list);
      break;
    }
  }
  printf("The list has %d words : ", list->length);
  print_word_list(list);
  printf(".\n");
  free_word_list(list);
  return 0;
}