/*-------------------------------------------------------
 * Name : hash table
 * Programmed by : Man Geun Jeong
 * Included fuction:
	void init_hash(element ht[]);
	int transform(char *key);
	int hash_function(char *key);
	int char_analysis(char* key);
	int bit_extraction(char *key);
	void hash_add(element ht[],data item);
	void hash_search(element ht[],data item);
	void delete_hash(element ht[],data item);
	void display_hash(element ht[]);
 * Date: 12 10 2013
 *(c) Copyright by Department of Digital Informatics and
 *    Convergence a Chungbuk National University,
 *    ChungBuk, Republic of Korea  
 --------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define KEY_SIZE 10   //단어의 최대 크기
#define TABLE_SIZE 30 //버켓 사이즈
#define SLOT_SIZE 3  //슬롯 사이즈
#define INSERT 1
#define SEARCH 2
#define DELETE 3
#define DISPLAY 4
#define EXIT 5

typedef struct data{    //단어 구조체
	char word[KEY_SIZE];
}data;

typedef struct overdata{ //슬롯 초과시 단어 추가 구조체
	data item;
	overdata *link;
}overdata;

typedef struct element{    //버켓 구조체 선언
	data key[SLOT_SIZE];
	overdata *link;
}element;

void init_hash(element ht[]);
int transform(char *key);
int hash_function(char *key);
int char_analysis(char* key);
int bit_extraction(char *key);
void hash_add(element ht[],data item);
void hash_search(element ht[],data item);
void delete_hash(element ht[],data item);
void display_hash(element ht[]);

int fuction_choise = 1;

int main(){
	int choise = 0;
	char *temp = ".";
	data buffer;
	element hashtable[TABLE_SIZE];

	FILE* stream = fopen("input.txt","rt");
	init_hash(hashtable);
	puts("1.제산함수 2.문자분석함수 3.비트추출함수");
	scanf("%d",&fuction_choise);
	do{
		puts("1.삽입 2.검색 3.삭제 4.출력 5.종료");
		scanf("%d",&choise);
		switch(choise){
		case INSERT:
			while(1){
			if(fgets(buffer.word,KEY_SIZE,stream) == NULL) break;
			buffer.word[strlen(buffer.word)-1] = NULL; //입력된 엔터 빼기
			hash_add(hashtable,buffer);
			}
			break;
		case SEARCH:
			printf("찾고 싶은 단어를 입력하세요 \n");
			scanf("%s",buffer.word);
			hash_search(hashtable,buffer);
			break;

		case DELETE:
			printf("삭제하고 싶은 단어를 입력하세요 \n");
			scanf("%s",buffer.word);
			delete_hash(hashtable,buffer);
			break;

		case DISPLAY:display_hash(hashtable);
			break;

		case EXIT:
			break;
		}
	}while(choise != 5);
	fclose(stream);
	return 0;
}
void init_hash(element ht[]){  //해시 테이블 초기화
	int i,j;
	for(i = 0;i < TABLE_SIZE;i++){
		for(j = 0;j < SLOT_SIZE;j++){
			ht[i].key[j].word[0] = NULL;
		}
		ht[i].link = NULL;
	}
}

int transform(char *key){  //키를 숫자로 바꿔서 반환
	int number = 0;
	
	while(*key)
	number += *key++;
	
	return number;
}
int hash_function(char *key){ //제산 함수 사용
	
	switch(fuction_choise){
	case 1:return transform(key) % TABLE_SIZE;break;
	case 2:return char_analysis(key);break;
	case 3:return bit_extraction(key);break;
	}
	return transform(key) % TABLE_SIZE;
}
int char_analysis(char *key){ //문자 분석 함수 사용
	int n = 0;
	n += *key++;
	n += *key;
	n = n % 30;
	return n;
}
int bit_extraction(char *key){ //비트 추출 함수 
	int i, share = transform(key);
	int rest[5];
	
	for(i = 0; i < 5;i++){
		rest[i] = share % 2;
		share = share / 2; 
	}
	return ((rest[0]*16 + rest[1]*8 + rest[2]*4 + rest[3]*2 + rest[4]) % TABLE_SIZE);
	
}
void hash_add(element ht[],data item){
	
	int hash_index;  //해싱 테이블의 인덱스 값 선언
	int i = 0;

	hash_index = hash_function(item.word);//인덱스 값을 제산함수를 이용해서 삽입
	while(ht[hash_index].key[i].word[0] != NULL){ //해싱 테이블의 첫번째 버켓에 무언가 들어가 있을 때
		if(strcmp(ht[hash_index].key[i].word, item.word) == 0){ // 삽입하는 단어와 같은지 확인
			fprintf(stderr,"테이블에 이미 존재하는 단어입니다.\n");
			return;
		}
		i++; //다음 슬롯으로 넘어간다.
		if(i >= SLOT_SIZE){ //슬롯이 꽉차면 리턴한다.
			return;
		}
	}

	if(i >= SLOT_SIZE ){ //버켓이 꽉차서 온 경우 체이닝 기법으로 추가한다.
		overdata *new_hash; //새로운 해싱 테이블
		overdata *before_hash = NULL; //이전 해싱 주소 포인터
		overdata *present_hash = ht[hash_index].link; // 현재 해싱 주소 포인터
		//체이닝으로 추가된 테이블 중에 item과 중복인지 확인과정
		for(;present_hash;before_hash = present_hash,present_hash->link){ //현재 주소가 NULL 이 아닐경우 반복
			if(strcmp(present_hash->item.word, item.word) == 0){
				fprintf(stderr,"테이블에 이미 존재하는 단어입니다.\n");
				return;
			}
		}
		//중복이 없을경우
		new_hash = (overdata*)malloc(sizeof(overdata));  //메모리 공간 확보
		new_hash->item = item;  //단어 삽입
		new_hash->link = NULL;  //다음 해싱 주소 NULL 지정
		
		if(before_hash){ //이전에 체이닝이 있으면 연결
			before_hash->link = new_hash;
		}else{ //이전에 체이닝이 없으면 해싱테이블에 바로 연결
			ht[hash_index].link = new_hash;
		}

	}else{ //버켓이 비어있을 경우 그 버켓에 넣는다.
		ht[hash_index].key[i] = item;
	}
}
void hash_search(element ht[],data item){
	int hash_index;  //해싱 테이블의 인덱스 값 선언
	int i = 0;

	hash_index = hash_function(item.word);//인덱스 값을 제산함수를 이용해서 삽입
	while(ht[hash_index].key[i].word[0] != NULL){ //해싱 테이블의 첫번째 버켓에 무언가 들어가 있을 때
		if(strcmp(ht[hash_index].key[i].word, item.word) == 0){ // 삽입하는 단어와 같은지 확인
			fprintf(stdout,"테이블에 존재하는 단어입니다.\n");
			return;
		}
		i++; //다음 슬롯으로 넘어간다.
		if(i >= SLOT_SIZE){ //슬롯이 꽉차면 리턴한다.
			return;
		}
	}

	if(i >= SLOT_SIZE ){ //버켓이 꽉차서 온 경우 체이닝 기법으로 추가한다.
		overdata *before_hash = NULL; //이전 해싱 주소 포인터
		overdata *present_hash = ht[hash_index].link; // 현재 해싱 주소 포인터
		//체이닝으로 추가된 테이블 중에 item과 중복인지 확인과정
		for(;present_hash;before_hash = present_hash,present_hash->link){ //현재 주소가 NULL 이 아닐경우 반복
			if(strcmp(present_hash->item.word, item.word) == 0){
				fprintf(stdout,"테이블에 존재하는 단어입니다.\n");
				return;
			}
		}
	}else{ //버켓이 비어있을 경우 그 버켓에 넣는다.
		puts("테이블에 존재 하지 않는 단어입니다.");
	}
}
void delete_hash(element ht[],data item){
	int hash_index;  //해싱 테이블의 인덱스 값 선언
	int i = 0;

	hash_index = hash_function(item.word);//인덱스 값을 제산함수를 이용해서 삽입
	while(ht[hash_index].key[i].word[0] != NULL){ //해싱 테이블의 첫번째 버켓에 무언가 들어가 있을 때
		if(strcmp(ht[hash_index].key[i].word, item.word) == 0){ // 삽입하는 단어와 같은지 확인
			fprintf(stdout,"%s를 삭제합니다.\n",ht[hash_index].key[i].word);
			ht[hash_index].key[i].word[0]= NULL;
			return;
		}
		i++; //다음 슬롯으로 넘어간다.
		if(i >= SLOT_SIZE){ //슬롯이 꽉차면 리턴한다.
			return;
		}
	}

	if(i >= SLOT_SIZE ){ //버켓이 꽉차서 온 경우 체이닝 기법으로 추가한다.
		overdata *before_hash = NULL; //이전 해싱 주소 포인터
		overdata *present_hash = ht[hash_index].link; // 현재 해싱 주소 포인터
		//체이닝으로 추가된 테이블 중에 item과 중복인지 확인과정
		for(;present_hash;before_hash = present_hash,present_hash->link){ //현재 주소가 NULL 이 아닐경우 반복
			if(strcmp(present_hash->item.word, item.word) == 0){
				fprintf(stdout,"%s를 삭제합니다.\n",ht[hash_index].link->item.word);
				if(present_hash->link){
					before_hash->link = present_hash->link;
					free(present_hash);
				}else{
					before_hash->link = NULL;
					free(present_hash);
				}
				return;
			}
		}
	}else{ //버켓이 비어있을 경우 그 버켓에 넣는다.
		puts("테이블에 존재 하지 않는 단어입니다.");
	}
}
void display_hash(element ht[]){
	int i,j;
	overdata *temp;

	for(i = 0; i < TABLE_SIZE;i++){
		temp = ht[i].link;
		printf("[%d]:",i);
		for(j = 0; j < SLOT_SIZE; j++){
			printf("SLOT[%d]: %s ->", j, ht[i].key[j].word);
		}
		for(;temp;temp = temp->link){
			printf("Over data: %s ->",temp->item.word);
		}
		printf("\n");
	}
}