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

#define STR 32
#define N 500

int zap(int what,int way);
int lin(char element[STR],int mode);
int quad(char element[STR],int mode);
int fulltest();

char matrix[N][STR];
int h0(char element[STR]);



int main()
{
//        for(int i=0;i<N;i++)rix[i];
//        printf("%d--%d",);
	memset(matrix,0,N*STR);
	fulltest();
	return 0;
}


int h0(char element[32])
{
	int out=0;
	div_t ost;
/*        for (int i=1;i<31;i++){
		ost=div((unsigned char )element[i-1],i);
		out+=ost.rem;
	}
*/      
	for (int i=0;i<strlen(element);i++)out+=element[i];
//        return 1+(int) (255.0*rand()/(RAND_MAX+1.0));
	return(out%N);
};


int lin(char element[STR],int mode)
{
	int h=h0(element);
	int ri=1;
	for(;strcmp(matrix[(h+ri)%N],"")!=0;ri++,ri%=N); //esli mesto ne pusto-dal'she....
	if(mode) 
	    strcpy(matrix[(h+ri)%N],element); //esli nsda vstavit'-do it... ili v sad...
	return(ri);
};

int quad(char element[STR],int mode)
{
	int i=1;
	int h=h0(element);
	int ri=(i*i+i+5);
	for(;strcmp(matrix[(h+ri)%N],"")!=0;i++,ri=(i*i+i+5)%N); //esli mesto ne pusto-dal'she....
	if (mode) 
	    strcpy(matrix[(h+ri)%N],element);
	return(i);
};

int zap(int what,int way)
{
	char tt[32]="\0";
	div_t t;
	int i;
	char p;
	for(i=0; i<30;i++){
		tt[i]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
	};
	tt[i+1]='\0';
//        if(way==1) lin(tt,what);
//        else 
	quad(tt,what);
	return(0);
};

int fulltest()
{
	int i;
	int accum=0;
	int ii;
	char tt[32]="\0";
	div_t t;
	char p;
	printf("Trying Quadrant search....\n");
	printf("Trying to full matrix for about 90%%\n\r");
	for(i=0;i<450;i++){
	    zap(1,1);
	};
	printf("Done!!!\n");
	for (i=0;i<50;i++){
		for(ii=0; ii<30;ii++){
		    tt[ii]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
		};
		tt[ii+1]='\0';
		accum+=quad(tt,0);
	};
	printf("\n\rThere was %f tries to find place by quadrant search for each point.\n",accum/50.0);
	printf("----------------------\nTrying Linear search....\n");
	memset(matrix,0,N*STR);
	printf("Trying to full matrix for about 90%%\n\r");
	accum=0;
	for(i=0;i<450;i++){
	    zap(1,1);
	};
	printf("Done!!!\n");
	for (i=0;i<50;i++){
		for(ii=0; ii<30;ii++){
		    tt[ii]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
		};
		tt[ii+1]='\0';
		accum+=lin(tt,0);
	};
	printf("\n\rThere was %f tries to find place by linear search for each point.\n",accum/50.0);
	memset(matrix,0,N*STR);

	printf("Trying Quadrant search....\n");
	printf("Trying to full matrix for about 50%%\n\r");
	for(i=0;i<200;i++){
	    zap(1,1);
	};
	printf("Done!!!\n");
	for (i=0;i<50;i++){
		for(ii=0; ii<30;ii++){
		    tt[ii]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
		};
		tt[ii+1]='\0';
		accum+=quad(tt,0);
	};
	printf("\n\rThere was %f tries to find place by quadrant search for each point.\n",accum/50.0);
	printf("----------------------\nTrying Linear search....\n");
	memset(matrix,0,N*STR);
	printf("Trying to full matrix for about 50%%\n\r");
	accum=0;
	for(i=0;i<200;i++){
	    zap(1,1);
	};
	printf("Done!!!\n");
	for (i=0;i<50;i++){
		for(ii=0; ii<30;ii++){
		    tt[ii]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
		};
		tt[ii+1]='\0';
		accum+=lin(tt,0);
	};
	printf("\n\rThere was %f tries to find place by linear search for each point.\n",accum/50.0);
	printf("Trying Quadrant search....\n");
	memset(matrix,0,N*STR);

	printf("Trying to full matrix for about 10%%\n\r");
	for(i=0;i<50;i++){
	    zap(1,1);
	};
	printf("Done!!!\n");
	for (i=0;i<50;i++){
		for(ii=0; ii<30;ii++){
		    tt[ii]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
		};
		tt[ii+1]='\0';
		accum+=quad(tt,0);
	};
	printf("\n\rThere was %f tries to find place by quadrant search for each point.\n",accum/50.0);
	printf("----------------------\nTrying Linear search....\n");
	memset(matrix,0,N*STR);
	printf("Trying to full matrix for about 10%%\n\r");
	accum=0;
	for(i=0;i<50;i++){
	    zap(1,1);
	};
	printf("Done!!!\n");
	for (i=0;i<50;i++){
		for(ii=0; ii<30;ii++){
		    tt[ii]=1+(int) (10.0*rand()/(RAND_MAX+1.0))+65;
		};
		tt[ii+1]='\0';
		accum+=lin(tt,0);
	};
	printf("\n\rThere was %f tries to find place by linear search for each point.\n",accum/50.0);

};