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

#define p 127
#define q 31
#define c1 2
#define c2 5

const int M = 5003;

int generator_retezce (char *pole);
void uvodni_okno();

int main()
{
	int i, j, k, l, m;
    int linearni_pokusy = 0, kvadraticke_pokusy = 0, dvoji_pokusy = 0;
    int procenta[3];

    procenta[0] = 0.50 * M;
    procenta[1] = 0.75 * M;
    procenta[2] = 0.90 * M;
    procenta[3] = 0.95 * M;

	char retezec[21], q1, q2, qe;
	char *pole_linearni[M], *pole_kvadraticke[M], *pole_dvoji[M];

	double linearni[4], kvadraticke[4], dvoji[4];

	srand(time(0));

	//uvodni_okno();

    for (i = 0; i < 4; i++)
    {
        linearni[i] = 0;
        kvadraticke[i] = 0;
        dvoji[i] = 0;
    }

    for (j = 0; j < M; j++)
    {
        pole_linearni[j] = NULL;
        pole_kvadraticke[j] = NULL;
        pole_dvoji[j] = NULL;
    }

    for (k = 0; k < M; k++)
    {
        l = generator_retezce(retezec);
        q1 = retezec[0];
        q2 = retezec[1];
        qe = retezec[l-1];

        if (k == procenta[0])
        {
            linearni[0] = linearni_pokusy;
            kvadraticke[0] = kvadraticke_pokusy;
            dvoji[0] = dvoji_pokusy;
        }

        else if (k == procenta[1])
        {
            linearni[1] = linearni_pokusy;
            kvadraticke[1] = kvadraticke_pokusy;
            dvoji[1] = dvoji_pokusy;
        }

        else if (k == procenta[2])
        {
            linearni[2] = linearni_pokusy;
            kvadraticke[2] = kvadraticke_pokusy;
            dvoji[2] = dvoji_pokusy;
        }

        else
        {
            linearni[3] = linearni_pokusy;
            kvadraticke[3] = kvadraticke_pokusy;
            dvoji[3] = dvoji_pokusy;
        }

        unsigned cz = (p * q1 + q * q2 + qe + l);


        // Lineární funkce

        int zaplneno = 1;
        int kolize = 0;

        while (zaplneno == 1)
        {
            unsigned h = ((cz % M) + kolize) % M;

            linearni_pokusy++;

            if (pole_linearni[h] != NULL)
            {
                kolize++;
            }

            else
            {
                pole_linearni[h] = strdup(retezec);
                zaplneno = 0;
            }
        }

        // Kvadraticka funkce

        zaplneno = 1;
        kolize = 0;

        while (zaplneno == 1)
        {
            unsigned h = ((cz % M) + (c1 * kolize) + c2 * (kolize * kolize)) % M;

            kvadraticke_pokusy++;

            if (pole_kvadraticke[h] != NULL)
            {
                kolize++;
            }

            else
            {
                pole_kvadraticke[h] = strdup(retezec);
                zaplneno = 0;
            }
        }

        // Dvoji funkce

        zaplneno = 1;
        kolize = 0;

        while (zaplneno == 1)
        {
            unsigned h = ((cz % M) + kolize * (1 + cz % (M-1))) % M;

            dvoji_pokusy++;

            if (pole_dvoji[h] != NULL)
            {
                kolize++;
            }

            else
            {
                pole_dvoji[h] = strdup(retezec);
                zaplneno = 0;
            }
        }
    }

	printf("\t  Prumerny pocet pokusu k nalezeni volne pozice pro ulozeni: \n");
    printf("\t  ----------------------------------------------------------\n\n");
    printf("-------------------------------------------------------------------------------\n");
    printf("|  Obsazeni (v %%)  | Linearni hledani | Kvadraticke hledani |  Dvoji hledani  |\n");
    printf("-------------------------------------------------------------------------------\n");

	for(m = 0; m < 4; m++)
    {
        if (m == 0)
        {
            printf("|        50        |        %2.2f      |         %.2f        |       %.2f      |\n", linearni[m]/ procenta[m], kvadraticke[m]/ procenta[m], dvoji[m]/ procenta[m]);
            printf("-------------------------------------------------------------------------------\n");
        }

        else if (m == 1)
        {
            printf("|        75        |      %2.2f      |         %.2f        |       %.2f      |\n", linearni[m]/ procenta[m], kvadraticke[m]/ procenta[m], dvoji[m]/ procenta[m]);
            printf("-------------------------------------------------------------------------------\n");
        }


        else if (m == 2)
        {
            printf("|        90        |      %2.2f      |         %.2f        |       %.2f      |\n", linearni[m]/ procenta[m], kvadraticke[m]/ procenta[m], dvoji[m]/ procenta[m]);
            printf("-------------------------------------------------------------------------------\n");
        }


        else if (m == 3)
        {
            printf("|        95        |      %2.2f      |        %.2f        |       %.2f      |\n", linearni[m]/ procenta[m], kvadraticke[m]/ procenta[m], dvoji[m]/ procenta[m]);
            printf("-------------------------------------------------------------------------------\n");
        }
    }


	return 0;
}

int generator_retezce (char *pole)
{
    int i, cislo;
	int delka_retezce = 3 + (rand() % 18);

	for (i = 0; i < delka_retezce; i++)
	{
		cislo = 97 + (rand() % 25);
		pole[i] = cislo;
	}

	pole[delka_retezce] = '\0';

	return delka_retezce - 1;
}

void uvodni_okno()
{
    system("cls");
    printf("|------------------------------------------------------------------------------|");
    printf("| *********         *         ********   ********   *******  ******* ********* |");
    printf("|        *         * *        *       * *        * *        *            *     |");
    printf("|       *         *   *       *       * *        * *        *            *     |");
    printf("|      *         *     *      *       * *        * *        *            *     |");
    printf("|     *         *       *     ********  *        * *        *****        *     |");
    printf("|    *         ***********    *         *        * *        *            *     |");
    printf("|   *         *           *   *         *        * *        *            *     |");
    printf("|  *         *             *  *         *        * *        *            *     |");
    printf("| ********* *               * *          ********   *******  *******     *     |");
    printf("|                                                                    ----------|");
    printf("|       *       *         ******** *       *       *     ********* / ********* |");
    printf("|      * *      *        *         **     **      * *        *    |          * |");
    printf("|     *   *     *        *         * *   * *     *   *       *    |          * |");
    printf("|    *     *    *        *   *** * *  * *  *    *     *      *    |    *****   |");
    printf("|   *********   *        *       * *   *   *   *********     *    |  *         |");
    printf("|  *         *  *        *       * *       *  *         *    *    |  *         |");
    printf("| *           * ********  ******** *       * *           *   *    |  ********* |");
    printf("|------------------------------------------------------------------------------|");
    printf("|                                                                              |");
    printf("| Uloha:\tHashovaci tabulky                                              |");
    printf("| Autor:\tTomas Lehar                                                    |");
    printf("| Verze:\t1.0                                                            |");
    printf("|------------------------------------------------------------------------------|");
    system("pause");
    system("cls");
}