DM_QP

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

#define MAX 1000 // Broj bucket-a u hash tablici
#define MAX_LINE_LENGTH 100
#define MAX_WORDS 1000 // 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;
    }
}

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

// Insert funkcija s Quadratic Probingom 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 = hash(value);
    int tmp;
    int flag = 0;
    int i = 0;

    while (i < MAX) {
        tmp = (index + i * i) % MAX;
        if (arr[tmp] == NULL || strcmp(arr[tmp], "") == 0) {
            arr[tmp] = strdup(value);
            flag = 1;
            break;
        } else {
            num_collisions++; // Kolizija se dogodila
            i++;
        }
    }

    if (!flag) {
        printf("Nema slobodnog mjesta za '%s'!\n", value);
    } else {
        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;
}