#include <stdio.h>
#include <stdlib.h>
#define MinSize 10

typedef unsigned int Index;
typedef Index Position;

struct HashTbl;
typedef struct HashTbl* HashTable;

HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(int key, HashTable H);
void Insert(int key, HashTable H);
int Retrieve(HashTable H);
HashTable Rehash(HashTable H);

enum KindOfEntry { Legitimate, Empty, Deleted };

//哈希单元
struct HashEntry
{
	int data;
	enum KindofEntry Info;
};

typedef struct HashEntry Cell;
struct HashTbl {
	int TableSize;
	Cell* TheCells;
};

HashTable InitializiTable(int TableSize)
{
	if (TableSize < MinSize)
	{
		Error("NO SPACE!!");
		return NULL;
	}

	HashTable H = malloc(sizeof(struct HashTbl));
	if (H == NULL)
		Error("no space!!");
	H->TableSize = NextPrime(TableSize);

	H->TheCells = malloc(sizeof(Cell) * H->TableSize);
	if (H->TheCells == NULL)
		FatalError("No Space!!");

	int i;
	for (i = 0; i < H->TableSize; i++)
		H->TheCells[i].Info = Empty;

	return H;
}

int Hash(int key, int size);

Position Find(int key, HashTable H)
{
	Position CurrentPos = Hash(key, H->TableSize);
	int CollisionNum = 0;
	while (H->TheCells[CurrentPos].Info != Empty &&
		H->TheCells[CurrentPos].data != key)
	{
		int dif = 2 * ++CollisionNum - 1;
		CurrentPos += dif;

		if (CurrentPos > H->TableSize)
			CurrentPos -= H->TableSize;
	}

	return CurrentPos;
}

void Insert(int key, HashTable H)
{
	int CurPos = Hash(key, H->TableSize);
	int ColNum = 0;
	while (H->TheCells[CurPos].Info != Empty&& H->TheCells[CurPos].data!=key)
	{
		CurPos += 2 * ++ColNum - 1;
		if (CurPos > H->TableSize)
			CurPos -= H->TableSize;
	}
	if (H->TheCells[CurPos].Info != Legitimate)
	{
		H->TheCells[CurPos].data = key;
		H->TheCells[CurPos].Info = Legitimate;
	}
}

int Hash2(int key, HashTable H);
HashTable Rehashing(HashTable H)
{
	int NewSize = NextPrime(2 * H->TableSize);
	HashTable New = InitializeTable(NewSize);

	for (int i = 0; i < H->TableSize; i++)
	{
		if (H->TheCells[i].Info == Legitimate)
			Insert(H->TheCells[i].data, New);
	}
	free(H->TheCells);
	
	return New;
}