/* Skrevet av Dag Langmyhr (dag@ifi.uio.no)
   til NM i programmering 2000. */

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


typedef enum {on_shelf, borrowed, returned} status;

typedef struct book {
  struct book *next, *prev;
  char   author[81], title[81];
  status s;
} book;
book *first_book = NULL;


int before(char *a1, char *t1, char *a2, char *t2)
{
  /* Should book 1 (with title `t1' and author `a1') be placed before
     book 2? */

  int cmp1 = strcmp(a1,a2);

  if (cmp1 == 0) return strcmp(t1,t2)<0;
  return cmp1<0;
}


void new_book(char *title, char *author)
{
  /* Insert a new book with the given `title' and `author' into the list. */

  book *p = malloc(sizeof(book)), *px1, *px2;

  printf("Inserting \"%s\" by \"%s\"...\n", title, author);
  strcpy(p->author, author);  strcpy(p->title, title);  p->s = on_shelf;
  p->next = p->prev = NULL;

  if (first_book) {
    if (before(p->author,p->title,first_book->author,first_book->title)) {
      first_book->prev = p;  p->next = first_book;  first_book = p;
    } else {
      px1 = first_book;  px2 = px1->next;
      while (px2 && before(px2->author,px2->title,author,title)) {
	px1 = px2;  px2 = px2->next;
      }
      px1->next = p;  p->prev = px1;
      if (px2) { p->next = px2;  px2->prev = p; }
    }
  } else {
    first_book = p;
  }
}


book *find(char *title)
{
  /* Find book with given `title'. */

  book *p = first_book;

  while (p) {
    if (strcmp(p->title,title) == 0) return p;
    p = p->next;
  }
  fprintf(stderr, "Cannot find book `%s'.\n", title);
  exit(2);
}


void read_word(FILE *f, char *s)
{
  /* Read the next word form `f' into `s'.
     The word may be quoted. */

  int  c;

  while (isspace(c = fgetc(f))) {}
  if (c == '"') {
    c = fgetc(f);
    while (c != '"') { *s++ = c;  c = fgetc(f); }
  } else {
    do { *s++ = c;  c = fgetc(f); } while (! isspace(c));
  }
  *s = '\0';
}


void shelve_books(FILE *f)
{
  book *p = first_book, *px;

  while (p) {
    if (p->s == returned) {
      px = p->prev;
      while (px && px->s!=on_shelf) px = px->prev;
      if (px) fprintf(f, "Put \"%s\" after \"%s\"\n", p->title, px->title);
      else    fprintf(f, "Put \"%s\" first\n", p->title);
      p->s = on_shelf;
    }
    p = p->next;
  }
  fprintf(f, "END\n");
}


int main(void)
{
  FILE *in_f  = fopen("infil.G","r"),
       *out_f = fopen("utfil.G","w");
  book *bp;
  char author[81], title[81];

  read_word(in_f, title);
  while (strcmp(title,"END") != 0) {
    read_word(in_f, author);
    if (strcmp(author,"by") != 0) {
      fprintf(stderr, "ERROR: found '%s', not 'by'.\n", author);
      exit(1);
    }

    read_word(in_f, author);  new_book(title, author);
    read_word(in_f, title);
  }

  read_word(in_f, title);
  while (strcmp(title,"END") != 0) {
    if (strcmp(title,"BORROW") == 0) {
      read_word(in_f, title);  bp = find(title);  bp->s = borrowed;
    } else if (strcmp(title,"RETURN") == 0) {
      read_word(in_f, title);  bp = find(title);  bp->s = returned;
    } else if (strcmp(title,"SHELVE") == 0) {
      shelve_books(out_f);
    } else {
      fprintf(stderr, "Illegal command: '%s'.\n", title);
      exit(3);
    }

    read_word(in_f, title);
  }

  fclose(in_f);  fclose(out_f);  return 0;
}