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

/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif

#define ID_GETLINE  1001
#define ID_NODE     1002
#define ID_STR      1004
#define ID_WORDDATA 1005
#define ID_ANALYZE2 1006
#define ID_ANALYZE3 1007
#define ID_ANALYZE4 1008

#define BUFFSIZE 3 /* >= 2 */
char *mygetline(FILE *fp) {
  static char inbuff[BUFFSIZE];
  char *outbuff_malloc, *tmpbuff;
  char *p, *r;
  int fEOL;

  if ((outbuff_malloc = xmalloc(1, ID_GETLINE)) == NULL) {
    return NULL;
  }
  *outbuff_malloc = '\0';
  fEOL = 0;
  do {
    r = fgets(inbuff, BUFFSIZE, fp);
    if (r == NULL)
      break;
    for (p = inbuff; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n')
      fEOL = 1;
    if ((tmpbuff = xrealloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1, ID_GETLINE)) == NULL) {
      xfree(outbuff_malloc, ID_GETLINE);
      return NULL;
    }
    strcat(tmpbuff, inbuff);
    outbuff_malloc = tmpbuff;
  } while (!fEOL);
  if (strlen(outbuff_malloc) > 0) {
    for (p = outbuff_malloc; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n')
      *(p - 1) = '\0';
    return outbuff_malloc;
  }
  xfree(outbuff_malloc, ID_GETLINE);
  return NULL;
}

struct node {
  void *data;
  int bal;
  struct node *left;
  struct node *right;
};

void treeRotateSingleL(struct node **p) {
  struct node *p1;
  p1 = (*p)->left;
  (*p)->left = p1->right;
  p1->right = *p;
  (*p)->bal = 0;
  *p = p1;
}
 
void treeRotateSingleR(struct node **p) {
  struct node *p1;
  p1 = (*p)->right;
  (*p)->right = p1->left;
  p1->left = *p;
  (*p)->bal = 0;
  *p = p1;
}

void *insertAVLTree(struct node **p, void *data, int (*cmp)(void *, void *), int *ph) {
  void *rc;
  struct node *p1, *p2;
  if (!*p) {
    if ((*p = xmalloc(sizeof(struct node), ID_NODE)) == NULL) {
      fprintf(stderr, "cannot allocate enough memory(struct node), aborted\n");
      exit(-1);
    }
    *ph = 1;
    (*p)->data = data;
    (*p)->bal = 0;
    (*p)->left = (*p)->right = NULL;
    return data;
  } 
  if ((*cmp)(data, (*p)->data) < 0) {
    if ((rc = insertAVLTree(&((*p)->left), data, cmp, ph)) != data)
      return rc;
    if (*ph > 0) {
      if ((*p)->bal == 1) {
        (*p)->bal = 0;
        *ph = 0;
      } else if ((*p)->bal == 0) {
        (*p)->bal = -1;
      } else if ((*p)->bal == -1) {
        if ((*p)->left->bal == -1) {
          treeRotateSingleL(p);
        } else {
          p1 = (*p)->left;
          p2 = (p1)->right;
          treeRotateSingleR(&((*p)->left));
          treeRotateSingleL(p);
          if (p2->bal == -1)
            (*p)->bal = 1;
          else
            (*p)->bal = 0;
          if (p2->bal == +1)
            p1->bal = -1;
          else
            p1->bal = 0;
        }
        (*p)->bal = 0;
        *ph = 0;
      }
    }
    return rc;
  } else if ((*cmp)(data, (*p)->data) > 0) {
    if((rc = insertAVLTree(&((*p)->right), data, cmp, ph)) != data)
      return rc;
    if (*ph > 0) {
      if ((*p)->bal == -1) {
        (*p)->bal = 0;
        *ph = 0;
      } else if ((*p)->bal == 0) {
        (*p)->bal = +1;
      } else if ((*p)->bal == +1) {
        if ((*p)->right->bal == +1) {
          treeRotateSingleR(p);
        } else { /* rotate double RL */
          p1 = (*p)->right;
          p2 = (p1)->left;
          treeRotateSingleL(&((*p)->right));
          treeRotateSingleR(p);
          if (p2->bal == 1)
            (*p)->bal = -1;
          else
            (*p)->bal = 0;
          if (p2->bal == -1)
            p1->bal = 1;
          else
            p1->bal = 0;
        }
        (*p)->bal = 0;
        *ph = 0;
      }
    }
    return rc;
  } else {
    return (*p)->data;
  }
}

void *pop(struct node **root) {
  struct node *p;
  void *data;
  if (*root == NULL) {
    return NULL;
  }
  if ((*root)->left) {
    data = pop(&((*root)->left));
    return data;
  }
  assert((*root)->left == NULL);
  p = *root;
  data = p->data;
  *root = p->right;
  xfree(p, ID_NODE);
  return data;
}

struct worddata {
  char *word;
};

int isDelimiter(char c) {
  return c == ' ';
}

int cmp(struct worddata *s, struct worddata *t) {
  return strcmp(s->word, t->word);
}

void wdregister(char *p, struct node **root) {
  char *word;
  struct worddata *wd, *already;
  int ph;
  word = xmalloc(strlen(p) + 1, ID_STR);
  if (!word) {
    fprintf(stderr, "cannot allocate enough memory, aborted.\n");
    exit(-1);
  }
  strcpy(word, p);
  wd = xmalloc(sizeof(struct worddata), ID_WORDDATA);
  if (!wd) {
    fprintf(stderr, "cannot allocate enough memory, aborted.\n");
    exit(-1);
  }
  wd->word = word;

  if ((already = insertAVLTree(root, wd, (int (*)(void *, void *))cmp, &ph)) != wd) {
    xfree(wd->word, ID_STR);
    xfree(wd, ID_WORDDATA);
  }
}

void analyze_line_main(char *line, struct node **root) {
  char *p, *q;
  for (p = line; *p;) {
    for (;isDelimiter(*p) && *p; p++)
      ;
    if (!*p)
      break;
    for (q = p; !isDelimiter(*q) && *q; q++)
      ;
    if (*q) {
      *q = '\0';
      wdregister(p, root);
      p = q + 1;
    } else {
      wdregister(p, root);
      break;
    }
  }
}

int isApostrophe(char *p, char *line_start) {
  assert(*p == '\'');
  if (p == line_start || !isalpha(*(p - 1) & 0xff))
    return 0;
  if (*(p + 1) == '\0' || !isalpha(*(p + 1) & 0xff))
    return 0;
  return 1;
}

int isItIs(char *p) {
  if (strstr(p, "'tis") == p)
    return 1;
  return 0;
}

/* supress '\'' except for single apostrophe */
void analyze_line4(char *p, struct node **root) {
  char *q, *s, *t;
  if ((q = xmalloc(strlen(p) + 1, ID_ANALYZE4)) != NULL) {
/* convert */
    for (s = p, t = q; *s; s++, t++)
      if (*s == '\'') {
        if (isApostrophe(s, p) || isItIs(s))
          *t = *s;
        else
          *t = ' ';
      } else {
        *t = *s;
      }
    *t = '\0';
    analyze_line_main(q, root);
    xfree(q, ID_ANALYZE4);
  }
}

/* exchange to space except alphabet and apostrophie and space*/
void analyze_line3(char *p, struct node **root) {
  char *q, *s, *t;
  if ((q = xmalloc(strlen(p) + 1, ID_ANALYZE3)) != NULL) {
/* convert */
    for (s = p, t = q; *s; s++, t++)
      if (isalpha(*s & 0xff) || *s == '\'' || *s == ' ')
        *t = *s;
      else
        *t = ' ';
    *t = '\0';
    analyze_line4(q, root);
    xfree(q, ID_ANALYZE3);
  }
}

/* upper to lower */
void analyze_line2(char *p, struct node **root) {
  char *q, *r;
  if ((q = xmalloc(strlen(p) + 1, ID_ANALYZE2)) != NULL) {
    strcpy(q, p);
/* convert */
    for (r = q; *r; r++)
      if (isupper(*r & 0xff))
        *r = (char)tolower(*r & 0xff);

    analyze_line3(q, root);
    xfree(q, ID_ANALYZE2);
  }
}

/* cut text for analyzing */
#define P_FIRST_LINE "CHAPTER I. Down the Rabbit-Hole"
#define P_LAST_LINE "THE END"
void analyze_line1(char *line, struct node **root) {
  static int flag_textin = 0;
  static int flag_endline = 0;
  if (strstr(line, P_FIRST_LINE))
    flag_textin = 1;
  if (strstr(line, P_LAST_LINE)) {
    flag_endline = 1;
  }
  if (flag_textin) {
    analyze_line2(line, root);
  }
  if (flag_endline) {
    flag_textin = 0;
    flag_endline = 0;
  }
}

#define FILENAME "alice.txt"
int main(int argc, char *argv[]) {
  FILE *fp;
  struct node *root;
  struct worddata *p;
  char *line;
  int count, flag_verbose;

  flag_verbose = 0;
  if (argc == 2 && *argv[1] == '-' && *(argv[1] + 1) == 'v')
    flag_verbose = 1;

  if ((fp = fopen(FILENAME, "rt")) != NULL) {
    root = NULL;
    while ((line = mygetline(fp)) != NULL) {
      analyze_line1(line, &root);
      xfree(line, ID_GETLINE);
    }
    count = 0;
    while ((p = pop(&root)) != NULL) {
      count++;
      if (flag_verbose)
        printf("%s\n", p->word);
      xfree(p->word, ID_STR);
      xfree(p, ID_WORDDATA);
    }
    printf("%d\n", count);
    fclose(fp);
  }
  xmallocdump();
  return 0;
}
/* end */