DM_DH

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

#define MAX 100000 // Broj bucket-a u hash tablici
#define R 7919 // Prost broj za drugu hash funkciju
#define MAX_LINE_LENGTH 100
#define MAX_WORDS 10000 // Maksimalan broj riječi

char *arr[MAX];
int num_elements = 0; // Ukupan broj elemenata u hash tablici
int num_collisions = 0; // Broj kolizija

// Inicijalizacija hash tablice
void inicijalizacija() {
    for (int i = 0; i < MAX; i++) {
        arr[i] = NULL;
    }
}

// Prva hash funkcija koristeći Division Method
int hash1(char *value) {
    int sum = 0;
    for (int i = 0; value[i] != '\0'; i++) {
        sum += value[i];
    }
    return sum % MAX;
}

// Druga hash funkcija
int hash2(char *key) {
    int sum = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        sum += key[i];
    }
    return (R - (sum % R));
}

// Insert funkcija s Double Hashingom i brojanjem kolizija
void insert(char *value) {
    if ((float)num_elements / MAX > 0.75) {
        printf("Hash tablica load factor premašuje 0.75. Nove riječi se ne dodaju.\n");
        return;
    }

    int index = hash1(value);
    if (arr[index] == NULL || strcmp(arr[index], "") == 0) {
        arr[index] = strdup(value);
    } else {
        int i = 1;
        int index2 = hash2(value);
        int tmpIndex;

        while (i < MAX) {
            tmpIndex = (index + i * index2) % MAX;
            if (arr[tmpIndex] == NULL || strcmp(arr[tmpIndex], "") == 0) {
                arr[tmpIndex] = strdup(value);
                break;
            } else {
                num_collisions++; // Kolizija detektirana
                i++;
            }
        }

        if (i == MAX) {
            printf("Nema slobodnog mjesta za '%s'!\n", value);
        }
    }

    num_elements++;
}

// Funkcija za mjerenje vremena unosa i brojanje kolizija
void measure_insertion_time(FILE *file) {
    char line[MAX_LINE_LENGTH];
    int word_count = 0;
    clock_t start, end;
    double total_time;

    start = clock();
    while (fgets(line, MAX_LINE_LENGTH, file) && word_count < MAX_WORDS) {
        line[strcspn(line, "\n")] = '\0'; // Ukloni novi red
        insert(line);
        word_count++;
    }
    end = clock();
    total_time = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Vrijeme unosa: %f sekundi\n", total_time);
    printf("Broj riječi: %d\n", word_count);
    printf("Broj kolizija: %d\n", num_collisions);
}

int main() {
    FILE *in_file = fopen("words.txt", "r");
    if (!in_file) {
        printf("Nije moguće otvoriti datoteku!\n");
        exit(-1);
    }

    inicijalizacija();
    measure_insertion_time(in_file);

    fclose(in_file);
    return 0;
}