Untitled

#include <iostream>
#include <string>

using namespace std;

template <typename T>
struct Node {
    struct Node<T>* prev = nullptr;
    T data;
    struct Node<T>* next = nullptr;
};

template <typename T, typename Y>
struct LinkedList {
    struct Node<T>* head = nullptr;
    struct Node<T>* tail = nullptr;
    int size = 0;

    void pushBack(T data) {

        // tworzenie węzła
        Node<T>* n = new Node<T>();
        n->data = data;

        n->prev = tail;

        // jeśli nie został wcześniej dodany żaden element
        if (tail != nullptr) {
            tail->next = n;
        }
        else {
            head = n;
        }

        tail = n;

        // zwiększenie informacji o ilości elementów znajdujących się w liście
        size++;
    }

    bool isEmpty() {
        if (head == nullptr)
            return true;

        return false;
    }

    Node<T>* search(string key) {
        Node<T>* n = head;

        while (n != nullptr) {

            if (n->data.key == key) return n;

            n = n->next;
        }

        return nullptr;
    }

    bool searchAndDelete(string key) {
        Node<T>* n = search(key);

        if (n == nullptr) return false;
        else {
            if (n == head) {
                if (n->next != nullptr) {
                    head = n->next;
                    head->prev = nullptr;
                }
                else {
                    head = tail = nullptr;
                }

            }
            else if (n == tail) {
                tail = n->prev;
                tail->next = nullptr;
            }
            else {
                n->next->prev = n->prev;
                n->prev->next = n->next;
            }

            delete n;
            size--;

            return true;
        }
    }


    void clear() {
        Node<T>* n = head;
        Node<T>* lastFound = nullptr;

        if (head == nullptr) {
            return;
        }

        while (true) {
            lastFound = n;

            n = n->next;

            if (n == nullptr)
                break;

            delete n->prev;

            size--;
        }

        delete lastFound;

        // ustawienie tail i head na nullptr
        head = tail = nullptr;
    }

    string str(string(*func)(Y)) {
        string s = "";

        Node<T>* n = head;

        while (n != nullptr) {
            s += n->data.key + " -> " + func(n->data.data) + "; \n";

            if (n->next != nullptr)
                s += "\t\t   ";

            n = n->next;
        }

        return s;

    }

    int getSize() {
        return size;
    }

    Node<T>* get(int i) {
        Node<T>* n = head;

        for (int j = 0; j < i; j++) {
            n = n->next;
        }

        return n;
    }
};  // dotąd dosłownie mamy po prostu liste z dowiązaniami (1 zadanie)

template <typename T>
struct Item {
    string key;
    T data;
}; // para klucz data, czyli to co bedzie dodawane pozniej do node'a, który jest w liście która jest w tablicy 

// jakby nie mialy byc same inty w mainie 
// struct simple_object {
//     string surname;
//     int age;
// };

// string so_str(simple_object so) {
//     return so.surname + ' ' + to_string(so.age);
// }

template <typename T>
struct HashTable {

    int size = 0;
    int capacity = 10;
    // tworzenie tablicy list
    LinkedList<Item<T>, T>* array = new LinkedList<Item<T>, T>[capacity]; //item<T> to para klucz, a samo t to data ta ktora jest juz w itemie przy okazji wczesniej (jest to po to zeby moc zwrocic latwiej po prostu samo data a nie caly item ) 
    //T* array = new T[capacity];
    // po prostu troche zmieniona tablica dynamiczna
    // F)
    int hash_func(string key) {
        int q = key.length();
        long long hash = 0;

        for (int i = 0; i < q; i++) {
            hash += key[i] * pow(31, (q - 1 - i));
        }

        hash = abs(hash % capacity);    // hash zmienia sie w zaleznosci od rozmiaru tablicy
        return hash;
    } // po prostu dosłownie podpunkt 8 z instrukcji przepisany
    // G)
    void rehash() {
        int old_capacity = capacity;
        capacity *= 2;  // powiekszam capacity 2x

        LinkedList<Item<T>, T>* tmp_array = new LinkedList<Item<T>, T>[capacity]; // znowu tworze tablice list tylko 2x wieksza

        for (int i = 0; i < old_capacity; i++) {    // jade po wszystkich elementach (indeksach) - vertcial tablicy a pod kazdym elementem jest lista
            if (!array[i].isEmpty()) {
                for (int j = 0; j < array[i].getSize(); j++) { // tutaj jade po wszystkich elementach (horyzontalnie) listy ktora jest pod danym indeksem w tablicy
                    Node<Item<T>>* n = array[i].get(j); // wyciągam element
                    string key = n->data.key; // wyciągam kllucz elementu i dalej jak w insercie
                    int hash = hash_func(key);  // to samo co w insercie, czyli znajduje miejsce w funkcji hash dla powiekszonej tablicy
                    tmp_array[hash].pushBack(n->data);  // i wrzucam tam ta date po prostu (bardzo podobnie jak w insert)
                }
            } // znajdzie miejsce dla nowych data no bo capacity jest 2x większe
        }
        delete array; // zwalniam stara tablice
        array = tmp_array;  // przypisuje nowa
    }
    // A)
    void insert(string key, T data) {

        Item<T>* is = search(key); // szukam czy istnieje juz w tablicy hashujacej taki sam klucz
        if (is != nullptr) {
            is->data = data; // jesli istnieje to podmieniam data na nową data
        }
        else {
            Item<T> it = Item<T>{ key, data }; // w przeciwnym tworze nowy item
            int hash = hash_func(key);  // wrzucam "hash z klucza" zeby wiedziec w ktorym miejscu wrzucic
            array[hash].pushBack(it);   // w miejscu w ktore zwrocila funkcja hash istnieje lista i dodaje po prostu do tej listy
            size++;
        }

        if (capacity * 0.75 < size) {
            rehash();   // jesli size przekroczy 75% capacity (jest zapelniona w 75%) to wywolujemy rehash 
        }

    }
    // B)
    Item<T>* search(string key) {
        int hash = hash_func(key);      // uzywamy funkcji hash zeby sprawdzic pod jakim indeksem moglby byc dany element o danym kluczu (jezeli by istniał)
        Node<Item<T>>* n = array[hash].search(key); // szukamy w liscie czy istnieje pod danym indeksem tablicy

        if (n != nullptr) // jesli rozne od nullptr
            return &n->data; // zwracamy date
        else
            return nullptr; // a jesli wyszedl nullptr no to nullptr XD
    }
    // C)
    bool remove(string key) {
        int hash = hash_func(key); // uzywamy funkcji hash zeby sprawdzic pod jakim indeksem moglby byc dany element o danym kluczu (jezeli by istniał)
        bool flag = array[hash].searchAndDelete(key); //funckja znowu z tablicy searchanddelete (albo zwroci prawde albo nieprawde w zaleznosci czy istnieje element czy nie)

        if (flag == 1) // jesli istnial to zmniejszamy rozmiar wszystkich elementów
            size--;

        return flag;
    }
    // D)
    void clear() {
        for (int i = 0; i < capacity; i++) {
            array[i].clear(); // czyscze kazda liste pod kazdym indeksem (array[i] to jest cala nasza lista jakas)
        }

        delete[] array; // zwolnienie pamieci tablicy, czyli pustych list bo te zostaly juz wczesniej wyczyszczone
        size = 0;
        capacity = 10;
        array = new LinkedList<Item<T>, T>[capacity]; // tworzymy nowa tablice list
    }
    // PODPUNKT 9
    // string stats() { // statystyki
    //     int min_list_size = array[0].getSize();
    //     int max_list_size = array[0].getSize();
    //     int nonempty_lists = 0; // default values
    //     int item_counter = 0;

    //     for (int i = 0; i < capacity; i++) { // jade po calej tej XD tablicy 
    //         if (!array[i].isEmpty())    // sprawdzam jesli lista nie jest pusta
    //         {
    //             nonempty_lists++;       
    //             int current_list_size = array[i].getSize(); // sprawdzamy size listy
    //             item_counter += current_list_size;

    //             if (current_list_size > max_list_size) // sprawdzamy czy wiekszy niz maksymalny
    //                 max_list_size = current_list_size; // jesli byl to przypisujemy do maksymalnego
    //             else if (current_list_size < max_list_size) //sprawdzamy czy wiekszy niz minimalnu
    //                 min_list_size = current_list_size; // jesli byl to przypisujemy do minimalnego

    //         }

    //     }

        // printowanie wszystkiego
    /*float average_list_size = item_counter / static_cast<float>(capacity);
    return "Stats:\n\tlist min size: " + to_string(min_list_size) + "\n\tlist max size: " + to_string(max_list_size) + "\n\tnonempty lists: " + to_string(nonempty_lists) + "\n\taverage list size: " + to_string(average_list_size) + '\n';
}*/
// E)
// i tutaj do postaci stringa zeby sobie wyprintowac ten tego tablice
    string str(string(*func)(T), int x = 0) { // domyslnie argument x = 0 wiec jesli by nic nie wpisal to bedzie cala lista jesli by wpisal 5 to 5 elementow
    string s = "Hash table: \n\tCurrent size: " + to_string(size) + "\n\tMax size: " + to_string(capacity) + "\n\tTable:\n\t{\n";

    if (x < 1)
        x = capacity;

    for (int i = 0; i < x; i++) {
        if (!array[i].isEmpty()) {
            s += "\t\t" + to_string(i) + ": " + array[i].str(func); // to samo co wczesniej przy statystykach wiec do str dodaje
        }
    }

    s += "\t}\n";

    return s;
}

};


// tworzenie randomowych kluczy o dlugosci 6 (dokladnie z zadania wziete on chcial zeby taka funkcja byla)
string randKey(int j) {
    string s = "";
    for (int i = 0; i < j; i++)
        s += static_cast<char>(rand() % (127 + 1 - 32) + 32); // od 32 do 127 symbole ASCII wybiera do kluczy

    return s;
}


int main()
{
    srand(time(NULL));



    const int MAX_ORDER = 7;
    HashTable<int>* ht = new HashTable<int>();

    for (int o = 1; o <= MAX_ORDER; o++) {
        const int n = pow(10, o);

        clock_t t1 = clock();
        for (int i = 0; i < n; i++)
            ht->insert(randKey(6), i); // tutaj tam i sram 6 znakowe klucze, jesli chcialby nie same inty tylko na szablonach to odkomentowuje simple object i so str
        clock_t t2 = clock();          // i daje zamiast i np {"kddfvd", "deffdedf", 21}

        cout << ht->str(to_string, 5);
        cout << "\nCzas dodawania: " << (double)(t2 - t1) / CLOCKS_PER_SEC;

        const int m = pow(10, 4);
        int hits = 0;
        t1 = clock();
        for (int i = 0; i < m; i++) {
            Item<int>* it = ht->search(randKey(6));
            if (it != nullptr)
                hits++;
        }
        t2 = clock();
        cout << "\nCzas wyszukiwania: " << (double)(t2 - t1) / CLOCKS_PER_SEC << "\n";
        //cout << ht->stats(); DO PODPUNKTU 9 -> PRZY SPRAWDZANIU WYWALIĆ, W RAZIE CZEGO DODAĆ
        ht->clear();
    }
    delete ht;
}

// hash table with chaining jak bym szukał filmików