#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>

#define HASH_TABLE_SIZE 100


//  Prostoe reheshirovanie
int hash_function(std::string identificator) {
    int h = 0;
    for (int i = 0; i < identificator.size(); i++) {
        h = h + 2 * (int)((char)identificator[i]) - 3;
    }
    return h;
}


// Yporyadochenniy spisok
struct OrdList {
    std::string val;
    OrdList * next;
};

int list_ord_add(OrdList *h, std::string i) {
    OrdList *newNode = new OrdList;
    newNode->val = i;
    newNode->next = NULL;

    OrdList * c = h;
    int cnt = 0;
    while(c != NULL) {
        cnt++;
        if(c->next == NULL) {
            c->next = newNode;
            return cnt;
        }
        c = c->next;
    }
}


int main() {

    int i = 0;
    std::ifstream f("idents.txt");
    std::vector<std::string> idents;
    std::string l;
    while (std::getline(f, l)) {
        idents.push_back(l);
        l.clear();
    }

    //hash test
    std::string hash_massiv[HASH_TABLE_SIZE];
    int max_hash_op_count = 0;

    for(i = 0; i < idents.size(); i++) {
        int h = hash_function(idents[i]) % idents.size();
        int count = 0;
        if (!hash_massiv[h].empty()) {
            int idx = h;
            while (!hash_massiv[idx].empty() && idx < HASH_TABLE_SIZE) {
                count += 1;
                idx += 1;
            }
            if (idx >= HASH_TABLE_SIZE) {
                std::cout << "Ошибка ввода в хэш массив" << std::endl;
                break;
            }else {
                hash_massiv[idx] = idents[i];
                if (max_hash_op_count < count) max_hash_op_count = count;
            }
        } else {
            hash_massiv[h] = idents[i];
            if (max_hash_op_count < count) max_hash_op_count = count;
        }
    }

    std::cout << "Хэш таблица :" << std::endl;
    std::cout << " Максимальное количество операций для вставки = " << max_hash_op_count << std::endl;



    //List test
    OrdList * list = new OrdList();
    std::vector<std::string> sidents = idents;
    std::sort(sidents.begin(),sidents.end());
    list->val = sidents[0];
    int l_op = 0;
    for(i = 1; i < sidents.size(); i++) {
        int c = list_ord_add(list,sidents[i]);
        if(c > l_op) l_op = c;
    }

    std::cout << "Упорядоченный список :" << std::endl;
    std::cout << " Максимальное количество операций для вставки = " << l_op << std::endl;



    // test poiska
    //

    for(i = 0; i < idents.size(); i++) {
        int cnt = 0;
        int h = hash_function(idents[i]) % idents.size();
        if (hash_massiv[h] != idents[i]) {
            int idx = h;
            while (hash_massiv[idx] != idents[i] && idx < HASH_TABLE_SIZE) {
                cnt += 1;
                idx += 1;
            }
            if (idx >= HASH_TABLE_SIZE) {
                std::cout << "Ошибка поиска в хэш массиве" << std::endl;
                break;
            }else {
                if (max_hash_op_count < cnt) max_hash_op_count = cnt;
            }
        }
    }

    std::cout << "Хэш таблица :" << std::endl;
    std::cout << " Максимальное количество операций для поиска = " << max_hash_op_count << std::endl;


    for(i = 0; i < idents.size(); i++) {
        int cnt = 0;
        OrdList * tmp = list;
        while(tmp != NULL) {
            cnt++;
            if(tmp->val == idents[i]) {
                break;
            }
            tmp = tmp->next;
        }
        if(cnt > l_op) l_op = cnt;
    }

    std::cout << "Упорядоченный список :" << std::endl;
    std::cout << " Максимальное количество операций для поиска = " << l_op << std::endl;


    return 0;
}