#include <stdio.h>
#define HSZ 127 //해쉬 크기
#define HASHING(x)  ((x)%HSZ)
struct node_t {
	int val;
	struct node_t * next;
}node_t;

struct node_t hash_table[HSZ];

void init(void) {
	for (int i = 0; i < HSZ; i++) {
		hash_table[i].next= NULL;   /*hash_table[i]->val = NULL 이라고했다가 에러 떴음*/
	}
}

/*해쉬테이블을 node_t의 포인터형식이 아니라 (헤드포인터 못쓰게함!) hash_table[].next를 첫 요소로 썼다. */

void insert_hash(int value) {
	int hash_adress = HASHING(value);
	struct node_t* node = hash_table[hash_adress].next; //첫요소.
	//포인터형식으로 받아야지 링크타고 계속 옆으로 가기 때문에..next를 첫요소로 받아야한다.
	struct node_t* node_before = NULL;
	for (; node; node_before = node, node = node->next) {
		if (node->val > value) break; //node->val이 value보다 크면 멈춘다 -> 이 이전에 삽입해줘야함 (node_before)
	}
	struct node_t* new_node = (struct node_t*)malloc(sizeof(struct node_t));
	new_node->val = value;
	if (node_before) //이전 노드가 있다면
		node_before->next = new_node; //이전노드의 링크가 new_node가 된다.
	else //이전노드가 없다면 맨 앞에 추가해야줘야 한다.
		hash_table[hash_adress].next = new_node;

	if (node) //만약 node (뒤에 나올 노드가) 존재한다면
		new_node->next = node;
	else //뒤에 나올 노드가 존재하지 않는다면..null로
		new_node->next = NULL;


}



int delete_hash(int value)
{
	int hash_adress = HASHING(value);
	struct node_t* node = hash_table[hash_adress].next; //첫 노드를 next로.
	struct node_t* node_before = NULL;
	for (; node ; node_before = node, node = node->next) {
		if (node->val==value) { //만약 node->val과 지우려는 value가 같은 값을 갖는다면
			if (node_before != NULL) { //만약 이전 노드가 존재한다면 (맨 첫노드가 아니라면)
				node_before->next = node->next; //이전 노드가 지우려는 노드의 다음 노드를 가리키도록..(null일수도)
			}
			else if (node_before == NULL && node->next) { //만약 이전노드는 존재 안하는데 (첫요소) node->next는 존재한다면
				//즉 지우려는 요소가 첫요소라면
				hash_table[hash_adress].next = node->next; //첫요소를 그 다음 노드로 바꿔줌
			}
			else { //지우려는 요소가 첫요소고 그 다음 요소도 없다면 그냥 아예 첫요소를 null로 해줘야함
				//이거 안하니까 free된 heap영역 접근했다고 에러뜸
				hash_table[hash_adress].next= NULL;
			}
			//그 후 해제한다.
			free(node);
			return 1;
		}
	}
	return 0;
}

void print_hash(int value)
{
	int hash_adress = HASHING(value);
	struct node_t* node = hash_table[hash_adress].next;
	if (!node) printf(" there is no node");
	while (node) {
		printf("%d ", node->val);
		node = node->next;
	}
}

int main()
{
	init();
	insert_hash(6);
	insert_hash(127);
	insert_hash(0);
	insert_hash(8);
	insert_hash(25);
	insert_hash(35);
	insert_hash(45);
	insert_hash(36);
	//printf("%d %d", HASHING(0), HASHING(127));
	print_hash(0);
	puts("");
	printf("%d", delete_hash(25));
	puts("");
	print_hash(25);
}