/* 2. Vjezba
Uporabom funkcije int rand(void); i makro naredbe void randomize(void);
naciniti opcenitu funkciju za generiranje polja s n pseudoslucajnih brojeva
cija se vrijednost nalazi izmedju zadane donje i gornje granice. Prototip
funkcije je: gen_arr (long *polje, int n, long donja, long gornja); Naciniti
funkcije za izracunavanje moda sortiranog cjelobrojnog polja: a) izravno b)
rekurzivno c) nerekurzivno Treba generirati i sortirati polje (koristiti
proizvoljni algoritam za sort) te izmjeriti vremena trazenja moda za svaki
od tri navedena postupka.  Generiranje polja i vremena ponoviti za najgori
slucaj (svi elementi isti) i najbolji slucaj (svi elementi razliciti).
Dobivene rezultate prikazati u tablicnom obliku.  Dodatak: Pokusati
poboljsati postupak c).
*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 3000

//kreator '97

void gen_arr(long *polje, int n, long donja, long gornja)
{
	int i;
	randomize();
	if (gornja==donja) for (i=0; i<n; ++i) polje[i]=gornja;
		else for (i=0; i<n; ++i) polje[i]=(rand()%(gornja-donja))+donja;
}

void sort(long *polje, int n)
{
	int i,j;
	long tmp;
	for (i=0; i<n-1; ++i) for (j=i; j<n; ++j) if (polje[i]>polje[j])
	{
		tmp=polje[i];
		polje[i]=polje[j];
		polje[j]=tmp;
	}
}

long mode0(long *polje, int n, int *freq)
{
	long mode=*polje;
	int i, tmp_freq=1;
	*freq=1;
	for (i=1; i<n; ++i) if (polje[i]!=polje[i-1]) tmp_freq=1; else
	{
		++tmp_freq;
		if (tmp_freq>*freq) *freq=tmp_freq;
		mode=polje[i];
	}
	return mode;
}
long rmode0(long *polje, int n, int *freq)
{
	long mode;
	if (!n)
	{
		mode=*polje;
		*freq=1;
	} else
	{
		mode=rmode0(polje, n-1, freq);
		if (polje[n]==polje[n-*freq])
		{
			mode=polje[n];
			++(*freq);
		}
	}
	return mode;
}

long rmode1(long *polje, int n, int *freq)
{
	long mode=*polje;
	int i;
	*freq=1;
	for (i=1; i<n; ++i) if (polje[i]==polje[i-*freq])
	{
		mode=polje[i];
		++(*freq);
	}
	return mode;
}
void main(void)
{
	FILE *out;
	long a[MAX];
	int i, n, freq, broj_pon;
	long min, max;
	double f[3];
	clock_t tajm1, tajm2;

	out=fopen("lab2.txt", "wt");
	while (1)
	{
		printf("\nUnesite broj ponavljanja > ");
		scanf("%d", &broj_pon);
		if (!broj_pon) break;
		printf("Unesite broj clanova, min i max clan > ");
		scanf("%d %ld %ld", &n, &min, &max);

		gen_arr(a, n, min, max);

		tajm1=clock();
		for(i=0; i<broj_pon; ++i) mode0(a, n, &freq);
		tajm2=clock();
		f[0]=(double)(tajm2-tajm1);

		tajm1=clock();
		for(i=0; i<broj_pon; ++i) rmode0(a, n, &freq);
		tajm2=clock();
		f[1]=(double)(tajm2-tajm1);

		tajm1=clock();
		for(i=0; i<broj_pon; ++i) rmode1(a, n, &freq);
		tajm2=clock();
		f[2]=(double)(tajm2-tajm1);

		for(i=0; i<3; ++i) f[i]=f[i]/((double)broj_pon*CLK_TCK);
		printf("\nvremena:\nmode0: %lg\nrmode0: %lg\nrmode1: %lg", f[0], f[1], f[2]);
		fprintf(out, "\nbroj ponavljanja %d\nbroj clanova %d, donja granica %ld, gornja granica %ld", broj_pon, n, min, max);
		fprintf(out, "\nvremena:\nmode0: %lg\nrmode0: %lg\nrmode1: %lg\n", f[0], f[1], f[2]);
	}
	fclose(out);
}