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

#define HASHSIZE   101 /* ハッシュ表の大きさ (素数) */
#define MAXWORDLEN 128 /* 最大単語長 */
#define FNAME "file2.txt"

//-----------------------------------------------------------------
int wordlen;                   /* 単語長 */
unsigned long words, newwords; /* 単語, 新単語カウンタ */
char word[MAXWORDLEN + 1];     /* 現在の単語 */

typedef struct node { /* 2分木のノード */
    struct node *left, *right; /* 左右の子 */
    char *key;                 /* キー (文字列) */
    int freq;
} *nodeptr;

struct node nil = {NULL, NULL, word, 0}; /* 番人 */
nodeptr hashtable[HASHSIZE];             /* ハッシュ表 */
//-----------------------------------------------------------------
int swap(int* v1,int* v2);
int hash(char *s);  /* 簡単なハッシュ関数 */
void insert(void);  /* 挿入 (登録) */
void getword(void); /* 文字列の取得 */
void sort_of_freq(int* stbl,int* map); /* 頻度のソート */
//-----------------------------------------------------------------

int main()
{
    int i,stbl[HASHSIZE],map[HASHSIZE];

    words = newwords = 0;
    for (i = 0; i < HASHSIZE; i++) hashtable[i] = &nil;
    if (freopen(FNAME, "r", stdin) == NULL)
        return fprintf(stderr, "can't open %s\n", FNAME), 1;
    while (getword(), wordlen != 0) insert();
    printf("%lu words, %lu different words\n", words, newwords);

    /* 頻度表示配列の初期化 */
    for (i = 0; i < HASHSIZE; i++) map[i]=i;
    /* ソート用頻度記憶 */
    for (i = 0; i < HASHSIZE; i++){
        stbl[i]=hashtable[i]->freq;
        if(hashtable[i]->freq == 0)
            map[i] = 0;
    }
    /* 頻度の並び変え */
    sort_of_freq(stbl,map);
    
    for (i = 0; i < HASHSIZE; i++){
        if(map[i] != 0){
            printf("%s: %d\n",hashtable[map[i]]->key,hashtable[map[i]]->freq);
        }
    }
  
    return EXIT_SUCCESS;
}


// 値の入れ替え
int swap(int* v1,int* v2)
{
    int temp=*v1;
    *v1 = *v2; *v2=temp;
}

// 簡単なハッシュ関数
int hash(char *s)
{
    unsigned v;
    for (v = 0; *s != '\0'; s++)
        v = ((v << CHAR_BIT) + *s) % HASHSIZE;
    return (int)v;
}

// 挿入 (登録)
void insert(void)
{
    int cmp;
    nodeptr *p, q;

    words++;
    p = &hashtable[hash(word)];
    while ((cmp = strcmp(word, (*p)->key)) != 0)
        if (cmp < 0) p = &((*p)->left );
        else p = &((*p)->right);
    if (*p != &nil) {
        printf("");
        (*p)->freq ++;
        return; /* すでに登録されている */
    }
    newwords++;
    if ((q = malloc(sizeof *q)) == NULL ||
        (q->key = malloc(wordlen + 1)) == NULL) {
        printf("cannot alloc memory.\n");
        exit(EXIT_FAILURE);
    }
    strcpy(q->key, word);
    q->freq = 1;
    q->left = &nil; q->right = *p; *p = q;
}

// 文字列の取得
void getword(void)
{
    int c;
    wordlen = 0;
    do {
        if ((c = getchar()) == EOF) return;
    } while (! isalpha(c));
    do {
        if (wordlen < MAXWORDLEN) word[wordlen++] = tolower(c);
        c = getchar();
    } while (isalpha(c));
    word[wordlen] = '\0';
}

// 頻度のソート
void sort_of_freq(int* stbl,int* map)
{
    int i,j;
    for(i=0;i<HASHSIZE;i++) for(j=i;j<HASHSIZE;j++){
        if(stbl[i] != 0 && stbl[j] > stbl[i]){
            swap(&stbl[i],&stbl[j]);
            swap(&map[i],&map[j]);
        }
    }
}