DM_LP

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

#define MAX 100 // Broj bucket-a u hash tablici
#define MAX_LINE_LENGTH 100
#define MAX_WORDS 100 // 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 brojanjem kolizija i provjerom load factora
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 original_index = index;
    int tmp = index;

    while (arr[tmp] != NULL && arr[tmp][0] != '\0') {
        if (strcmp(arr[tmp], value) == 0) {
            printf("Element '%s' već postoji!\n", value);
            return;
        }
        tmp = (tmp + 1) % MAX; // Linear probing
        num_collisions++; // Povećaj broj kolizija
        if (tmp == original_index) { // Tablica je puna
            printf("Nema slobodnog mjesta za '%s'!\n", value);
            return;
        }
    }

    arr[tmp] = strdup(value); // Dodaj vrijednost u tablicu
    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;
}