// cs_161_165.c
/*
    C/C++の宿題片付けます 161代目
    http://t...content-available-to-author-only...h.net/test/read.cgi/tech/1354070278/165
 */

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

/* 共通エラーコード */
typedef enum {
    EC_Normal,                  // 正常終了
    EC_FileOpen,                // ファイルオープン失敗
    EC_MemAlloc,                // メモリ確保失敗
    EC_CantAddHash,             // Hashテーブル記録先が見つけられなかった(衝突時のハッシュ関数が甘い)
} ERR_CODE;
char *getStr_ERR_CODE(ERR_CODE ec)
{
    switch (ec) {
    case EC_Normal      :return "正常終了";
    case EC_FileOpen    :return "ファイルオープン失敗";
    case EC_MemAlloc    :return "メモリ確保失敗";
    case EC_CantAddHash :return "Hashテーブル記録先が見つけられなかった(衝突時のハッシュ関数が甘い)";
    }
    return "";
}

/* 重複文字列があったときに、追加するか無視するか */
typedef enum {
    AMD_ADD,                    // 追加する
    AMD_MUSI,                   // 追加しない
} ADD_MODE;
char *getStr_ADD_MODE(ADD_MODE code)
{
    switch (code) {
    case AMD_ADD    :return "追加する";
    case AMD_MUSI   :return "追加しない";
    }
    return "";
}

/* data */
typedef struct {
    ADD_MODE mode;              // (手動設定)重複時の動作
    int flag_res_out;           // (手動設定)結果出力時、空のテーブル要素を出力するかどうなのか(1 or 0)
    int data_n;                 // 文字列数
    int len_max;                // 文字列最大長
    int tbl_size;               // ハッシュテーブルサイズ
    char **table;               // ハッシュテーブル
    int *ref_search_count;      // table[] 探索参照カウンタ
} HASH_DATA;

/* prototype */
extern int hashfunc_h(char *s, HASH_DATA * hash);
extern int hashfunc_p(char *s, HASH_DATA * hash);
extern ERR_CODE hash_creat(HASH_DATA * hash, char *filename);
extern ERR_CODE hash_make(HASH_DATA * hash, char *filename);
extern ERR_CODE hash_add(HASH_DATA * hash, char *str);
extern void hash_show(HASH_DATA * hash, char *src_filename);
extern void hash_delete(HASH_DATA * hash);
extern int strcmp_ignore(char *s1, char *s2);

/*
 *      main
 */
int main(int argc, char *argv[])
{
    int res = (int) EC_Normal;
    HASH_DATA hd;

    // 初期化
    memset(&hd, 0x00, sizeof(HASH_DATA));
    hd.mode = AMD_MUSI;         // (手動設定)重複時の動作
    hd.flag_res_out = 1;        // (手動設定)結果出力時、空のテーブル要素を出力するかどうなのか(1 or 0)
    if (EC_Normal != (res = hash_creat(&hd, argv[1]))) {
        goto END_main;
    }
    // ハッシュ作成
    if (EC_Normal != (res = hash_make(&hd, argv[1]))) {
        goto END_main;
    }
    // 結果表示
    hash_show(&hd, argv[1]);
    // 終了
    res = (int) EC_Normal;
  END_main:
    hash_delete(&hd);
    if (res != EC_Normal) {
        fprintf(stderr, "Err :%s\n", getStr_ERR_CODE(res));
    }
    return res;
}

/* 大小文字区別なし文字列比較 (負:s1<s2, 正:s1>s2, 0:s1==s2)
 *  ※ s1="321", s2="321000"のときは、s1 < s2
 */
int strcmp_ignore(char *s1, char *s2)
{
    int cmp;
    while (1) {
        cmp = tolower((int) *s1) - tolower((int) *s2);
        if (cmp) {
            break;
        }
        if (*s1 == '\0' && *s2 == '\0') {
            break;
        }
        s1++;
        s2++;
    }

    return cmp;
}

/*
 *      HASH_DATA operation
 */
// ファイル filename を解析して、HASH_DATAを初期化

ERR_CODE hash_creat(HASH_DATA * hash, char *filename)
{
    FILE *fp;
    int len, pos_now, pos_prev;
    int c;

    // 単語数カウント
    if (NULL == (fp = fopen(filename, "r"))) {
        return EC_FileOpen;
    }
    pos_now = pos_prev = 0;
    while (c = fgetc(fp)) {
        if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == EOF) {
            ++hash->data_n;
            len = pos_now - pos_prev;
            if (hash->len_max < len) {
                hash->len_max = len;
            }
            pos_prev = pos_now + 1;
            if (c == EOF) {
                break;
            }
        }
        pos_now++;
    }
    fclose(fp);
    // HashTableサイズ決め (単語数の2倍以上 かつ 素数)
    int n;
    hash->tbl_size = hash->data_n * 2;
    while (1) {
        for (n = 2; (n * n < hash->tbl_size) && (hash->tbl_size % n); ++n);
        if (hash->tbl_size % n) {   /* 素数 */
            break;
        }
        ++hash->tbl_size;
    }
    // 確保
    if (NULL == (hash->table = (char **) malloc(sizeof(char *) * hash->tbl_size))) {
        return EC_MemAlloc;
    }
    memset(hash->table, 0x00, sizeof(char *) * hash->tbl_size);
    if (NULL == (hash->ref_search_count = (int *) malloc(sizeof(int) * hash->tbl_size))) {
        return EC_MemAlloc;
    }
    memset(hash->ref_search_count, 0x00, sizeof(int) * hash->tbl_size);

    return EC_Normal;
}

void hash_delete(HASH_DATA * hash)
{
    int i;
    if (hash) {
        if (hash->table) {
            for (i = 0; i < hash->tbl_size; i++) {
                if (hash->table[i]) {
                    free(hash->table[i]);
                    hash->table[i] = NULL;
                }
            }
            free(hash->table);
            hash->table = NULL;
        }
        if (hash->ref_search_count) {
            free(hash->ref_search_count);
            hash->ref_search_count = NULL;
        }
        memset(hash, 0x00, sizeof(HASH_DATA));
    }
}

ERR_CODE hash_make(HASH_DATA * hash, char *filename)
{
    FILE *fp = NULL;
    char *buf = NULL, *p;
    int c;
    ERR_CODE res = EC_Normal;

    // バッファ確保
    if (NULL == (buf = (char *) malloc(sizeof(char) * (hash->len_max + 2)))) {
        res = EC_MemAlloc;
        goto END_hash_make;
    }
    // 読み込み ＆ ハッシュに追加
    fp = fopen(filename, "r");
    p = &buf[0];
    while (c = fgetc(fp)) {
        if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == EOF) {
            *p = '\0';
            p = &buf[0];
            if (strlen(buf)) {
                if (EC_Normal != (res = hash_add(hash, &buf[0]))) {
                    goto END_hash_make;
                }
            }
            if (c == EOF) {
                break;
            }
        } else {
            *p++ = (char) c;
        }
    }
    // 終了
    res = EC_Normal;
  END_hash_make:
    if (buf) {
        free(buf);
        buf = NULL;
    }
    if (fp) {
        fclose(fp);
        fp = NULL;
    }

    return res;
}

ERR_CODE hash_add(HASH_DATA * hash, char *str)
{
    int index;                  // 記録先
    int next_step;              // 衝突時書き込み先探索ステップ
    int limit;                  // 記録先が見つからない場合への備え

    // hash値取得
    index = hashfunc_h(str, hash);
    hash->ref_search_count[index]++;    // 探索参照カウンタ
    // 衝突
    if (hash->table[index]) {
        // 同一文字列
        if (0 == strcmp_ignore(hash->table[index], str)) {
            if (hash->mode == AMD_MUSI) {
                return EC_Normal;
            }
        }
        // 衝突後 入れ先探索
        next_step = hashfunc_p(str, hash);
        for (limit = 0; limit < hash->tbl_size; limit++) {
            index = (index + next_step) % hash->tbl_size;
            hash->ref_search_count[index]++;    // 探索参照カウンタ
            if (NULL == hash->table[index]) {
                break;
            }
        }
        if (limit >= hash->tbl_size) {
            return EC_CantAddHash;
        }
    }
    // 追加
    if (NULL == (hash->table[index] = (char *) malloc(sizeof(char) * strlen(str) + 1))) {
        return EC_MemAlloc;
    }
    strcpy(hash->table[index], str);

    // end
    return EC_Normal;
}

void hash_show(HASH_DATA * hash, char *src_filename)
{
    int i;
    char b[256];
    int keta_cell;              // セル番号桁数
    int keta_ref;               // 参照回数桁数
    int m;

    // 桁数計算
    keta_cell = sprintf(b, "%d", hash->tbl_size);
    for (i = m = 0; i < hash->tbl_size; i++) {
        if (m > hash->ref_search_count[i]) {
            m = hash->ref_search_count[i];
        }
    }
    keta_ref = sprintf(b, "%d", m);

    // 出力
    fprintf(stdout, "・入力ファイル     : %s\n", src_filename);
    fprintf(stdout, "・最大文字列長     : %d\n", hash->len_max);
    fprintf(stdout, "・文字列数         : %d個\n", hash->data_n);
    fprintf(stdout, "・Hashテーブル数   : %d個\n", hash->tbl_size);
    fprintf(stdout, "・Hash追加モード   : 同一文字列を、%s\n", getStr_ADD_MODE(hash->mode));
    fprintf(stdout, "・当結果出力モード : 空のテーブル要素を出力%s\n", hash->flag_res_out ? "する" : "しない");
    for (i = 0; i < hash->tbl_size; i++) {
        if (hash->flag_res_out || hash->table[i]) {
            fprintf(stdout, "[%0*d] 参照回数 = %0*d, 格納文字 = [%s]\n", keta_cell, i, keta_ref, hash->ref_search_count[i]
                    , hash->table[i] ? hash->table[i] : "");
        }
    }
}

/*
 *      hash functions
 */

int hashfunc_h(char *s, HASH_DATA * hash)
{
    int r = 0;
    while (*s) {
        *s = tolower(*s);
        if ('a' <= *s && *s <= 'z') {
            r = r * 26 + (*s - 'a');
            r %= hash->tbl_size;
        }
        ++s;
    }
    return r;
}

int hashfunc_p(char *s, HASH_DATA * hash)
{
    return 1;
}

// End of cs_161_165.c