/* 6. Vjezba
Ancvfngv cebtenz mn fvzhyvenawr chawrawn qngbgrxr hm hcbenoh enmyvpvgvu
ievwrqabfgv iryvpvar cergvapn v iryvpvar cevzneabt cbqehpwn, xbevfgrpv
enmyvpvgr cbfghcxr cergibeor xywhpn h nqerfh. Cebtenz xnb vfubq fvzhynpvwr
qnwr thfgbph cnxvenawn v cbfgbgnx cerywrin.
Ermhygngr geron cevxnmngv h boyvxh qvwntenzn bivfabfgv cbfgbgxn cerywrin b
iryvpvav cergvapn, thfgbpv cnxvenawn v cbfghcxh cergibeor xywhpn h nqerfh.
Mn hmbenx cbqngnxn xbevfgvgv cbqngxr vm qngbgrxr nqerfr.gkg. */

#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define IDSize 8
#define FirstNameSize 20
#define LastNameSize 20
#define PostalIDSize 5
#define CitySize 20

// kreator '97
// nije da se hvalim ali:
// citadel:/mnt/hard_dos/borlandc/source ROOT # id                         # 20:32
// uid=0(root) gid=0(root) groups=0(root),25(floppy),29(audio),24(cdrom)
// 17:55  1997.12.13

struct record
{
	char ID[IDSize+1], FirstName[FirstNameSize+1];
	char LastName[LastNameSize+1], PostalID[PostalIDSize+1];
	char City[CitySize+1];
};

#define ClusterSize 512L //assume we work with fat12
// ClusterSize/(3*20+5+8)=512/73=7 records + 1 byte empty...
#define StudentsNo 100 //assume we have 100 students
// No of records in one matrix (folder)
#define RecordsNo ((int) (ClusterSize/sizeof(struct record)))
// No of matrices/folders
#define MatrixNo ((int) (StudentsNo/RecordsNo*1.3)) //130% of calculated value
//changeable..... !

struct record entry, matrix[RecordsNo];

void fatal (const char *msg)
{
	fputs(msg, stderr);
	exit(EXIT_FAILURE);
}

void empty_all(FILE *output)
{
	int i;
	for(i=0; i<RecordsNo; ++i) matrix[i].ID[0]=0;
	for(i=0; i<MatrixNo; ++i)
	{
		fseek(output, i*ClusterSize, SEEK_SET);
		fwrite(matrix, sizeof(matrix), 1, output);
	}
	printf("table emptied..\nstudents # %d\nrecords # %d\nmatrix # %d\n",
		StudentsNo, RecordsNo, MatrixNo);
}

int calculate_primary(const int m)
{
	int i, prim=m+1, end;
	do
	{
		--prim;
		end=(int)pow((double)prim, (double)0.5);
		for(i=end; i>0; --i) if (!(prim%i)) break;
	} while (i!=1);
	printf("primary # %d\n", prim);
	return prim;
}

//transformations of key in address..
//need only 3 digits coz' we've got 100 students..
//skip first 2 coz' they are allways same (fax)
int folding(const char ID[])
{
	int i, a, b, adr;
	char tmp[3+1]; //tmp storing for 3 digits.. for adding
	tmp[4]=0;
	for(i=0; i<3; ++i) tmp[i]=ID[7-i];
	a=atoi(tmp);
	for(i=0; i<3; ++i) tmp[i]=ID[2+i];
	b=atoi(tmp);
	adr=(a+b)%StudentsNo; //little change..
	return adr;
}

int dividing(const char ID[], const int prim)
{
	int a, adr;
	a=atoi(ID);
	adr=a%prim;
	return adr;
}

int shifting(const char ID[])
{
	int a, b, i;
	int adr;
	char tmp[3+1]; //tmp storing for 3 digits.. for adding
	tmp[4]=0;
	for(i=0; i<3; ++i) tmp[i]=ID[5+i];
	a=atoi(tmp);
	for(i=0; i<3; ++i) tmp[i]=ID[2+i];
	b=atoi(tmp);
	adr=(a+b)%StudentsNo;
	return adr;
}

int folding_dividing(const char ID[], const int prim)
{
	int i, a, b, adr;
	char tmp[3+1]; //tmp storing for 3 digits.. for adding
	tmp[4]=0;
	for(i=0; i<3; ++i) tmp[i]=ID[7-i];
	a=atoi(tmp);
	for(i=0; i<3; ++i) tmp[i]=ID[2+i];
	b=atoi(tmp);
	adr=(a+b)%prim;
	return adr;
}

int enter_data(struct record input, FILE *output, const int prim, int method)
{
	int entered=0, i, j, start_i, full=0, skip=0;
	//get address of matrixx/folder
	switch(method)
	{
		case 1: i=dividing(entry.ID, prim); break;
		case 2: i=shifting(entry.ID); break;
		case 3: i=folding(entry.ID); break;
		case 4: i=folding_dividing(entry.ID, prim); break;
		default: fatal("Wrong hashing method\n");
	}
	start_i=i;
	do
	 {
		//read from folder all records
		fseek(output, i*ClusterSize, SEEK_SET);
		fread(matrix, sizeof(matrix), 1, output);
		for(j=0; j<RecordsNo; ++j)
		{
			if (matrix[j].ID[0]) //it is not empty?
			{
				if (!(strncmp(matrix[j].ID, input.ID, IDSize)))
				{
					entered=1;
					break;
				}
			}
			else //it is empty
			{
				matrix[j]=input;
				fseek(output, i*ClusterSize, SEEK_SET);
				fwrite(matrix, sizeof(matrix), 1, output);
				entered=1;
				break;
			}
		}
		//damn!? still it is not entered!
		if (!entered)
		{
			++skip;
			i=(i+1)%MatrixNo;
			if (i==start_i) full=1;
		}
	} while ((!entered) && (!full));
	return skip;
}

void display(FILE *output)
{
	int i,j;
	for(i=0; i<MatrixNo; ++i)
	{
		fseek(output, i*ClusterSize, SEEK_SET);
		fread(matrix, sizeof(matrix), 1, output);
		for(j=0; j<RecordsNo; ++j)	if (matrix[j].ID[0])
			printf("%s %s %s %s %s\n", matrix[j].ID, matrix[j].LastName,
				matrix[j].FirstName,	matrix[j].PostalID, matrix[j].City);
	}
}

int main(void)
{
	FILE *input, *output;
	int prim, skips=0, method;
	char tmp[2];
	if (!(input=fopen("ADRESE.TXT", "rt")))
		fatal("Cannot read ADRESE.TXT\n");
	if (!(output=fopen("TABLICA.DAT", "w+b")))
		fatal("Cannot read/write TABLICA.DAT");
	empty_all(output);
	printf("Enter desired hashing method\n1) dividing\n2) shifting\n3) folding\n4) folding + dividing\n");
	method=getch()-'0';
	prim=calculate_primary(MatrixNo);
	while (fscanf(input, "%8[^\n] %20[^\n] %20[^\n] %5[^\n] %20[^\n]%[\n]", entry.ID,
		entry.LastName, entry.FirstName, entry.PostalID, entry.City, &tmp)!=EOF)
			skips+=enter_data(entry, output, prim, method);
	fclose(input);
	printf("total skips # %d\n", skips);
	printf("hashing density is %f\n", (float)StudentsNo/(MatrixNo*RecordsNo));
	printf("entry size is %d", sizeof(entry));
	#ifdef DEBUG
		display(output);
	#endif
	fclose(output);
	return (EXIT_SUCCESS);
}