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

using namespace std;

// Алгоритм обчислення хешу взято звідси http://www.cse.yorku.ca/~oz/hash.html
unsigned long djb2_hash(const char* str)
{
    unsigned long hash = 5381;
    while (int c = *str++) hash = hash * 33 + c;
    return hash;
}

const float kMaxLoadFactor = 0.7;
const int kGrowFactor = 2;
const int kStartSize = 4;

// Цей клас дозволяє вставляти рядки в хеш-таблицю і перевіряти чи таблиця вже має такий елемент
struct MySet {
public:
    // Ця функція ініціалізує об'єкт класу
    MySet() : data_(kStartSize) // Початково data_ матиме розмір kStartSize
    {}

    // Повертає істину, якщо елемент вставлено, хибу, якщо такий елемент вже є
    bool Insert(const string& value) {
        // Вставляємо новий елемент
        const int indexToInsert = djb2_hash(value.c_str()) % data_.size();
        
        // Перевіряємо чи такий елемент є, якщо нема, то вставляємо
        if (find(cbegin(data_[indexToInsert]), cend(data_[indexToInsert]), value) == cend(data_[indexToInsert])) {
            data_[indexToInsert].push_front(value);
            ++entriesCount_;
        }
        else {
            // Якщо елемент вже є, то ми закінчили, просто повертаємо хибу
            return false;
        }

        // Якщо завантаження більше допустимого, необхідно розширити таблицю
        if (LoadFactor() > kMaxLoadFactor) {
            // Тимчасове сховище для даних
            vector<list<string>> newData(data_.size() * kGrowFactor);
            // Ітеруємо по всьому вектору data_
            for (int i = 0; i < data_.size(); ++i) {
                // Ітеруємо по зв'язаному списку, що є в data_[i]
                for (auto iterator = cbegin(data_[i]); iterator != cend(data_[i]); ++iterator) {
                    const string valueToTransfer = *iterator;
                    const int newIndexToInsert = djb2_hash(valueToTransfer.c_str()) % newData.size();
                    // Ми точно знаємо, що дублікатів бути не може, тому тут перевірка непотрібна
                    newData[newIndexToInsert].push_back(valueToTransfer);
                }
            }
            // Переносимо дані у член класу, а про тимчасове сховище забуваємо
            swap(data_, newData);
        }

        return true;
    }

    // Перевірка чи рядок вже в таблиці
    bool Member(const string& value) {
        const int indexToCheck = djb2_hash(value.c_str()) % data_.size();
        return find(cbegin(data_[indexToCheck]), cend(data_[indexToCheck]), value) != cend(data_[indexToCheck]);
    }

    // Обчислимо поточне завантаження
    float LoadFactor() {
        return (float)(entriesCount_) / data_.size();
    }

private:
    int entriesCount_ = 0;
    vector<list<string>> data_;
};

int main()
{
    MySet ms;

    setlocale(LC_CTYPE, "ukr");
    cout << boolalpha; // щоб true/false виводились словами, а не 1/0

    const int kToInsert = 25;
    const int kToCheck = 30;

    // Вставляємо 100 рядків
    for (int i = 0; i < kToInsert; ++i) {
        const string value = to_string(i);
        const bool success = ms.Insert(value);
        cout << "Вставили " << value << " - " << success;
        if (success) {
            cout << ", коеф. завантаження " << ms.LoadFactor();
        }
        cout << endl;
    }

    // Пробуємо вставити ті самі рядки ще раз
    for (int i = 0; i < kToInsert; ++i) {
        const string value = to_string(i);
        cout << "Вставили " << value << " - " << ms.Insert(value) << endl;
    }

    for (int i = 0; i < kToCheck; ++i) {
        const string value = to_string(i);
        if (ms.Member(value)) {
            cout << value << " є в таблиці" << endl;
        }
        else {
            cout << value << " нема в таблиці" << endl;
        }
    }

    cin.get();
    return 0;
}

// Аналіз операцій Insert і Member
//
// Обидві операції використовують зв'язаний список, який для пошуку повинен обійти всі елементи,
// натомість можна використовувати дерево, наприклад реалізоване в std::set, тоді складність пошуку була б логарифмічна.

#include <limits.h>
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
#include <iostream>
 
using namespace std;
 
const int kImpossibleWeight = -1; // неможлива вага, щоб показати, що ребро відсутнє
const int kImpossibleDistance = INT_MAX; // нескінченна відстань, більше будь-якої можливої
const int kImpossibleIndex = -1; // не існує вершини з цим індексом
 
vector<vector<int>> adj_;
 
// Ініціалізуємо двовимірний масив (матрицю) verticesCount-на-verticesCount значеннями kImpossibleWeight
void InitGraph(int verticesCount) {
    adj_ = vector<vector<int>>(verticesCount, vector<int>(verticesCount, kImpossibleWeight));
}
 
void InsertEdge(int a, int b, int w) {
    adj_[a][b] = adj_[b][a] = w;
}
 
int VerticesCount() { return adj_.size(); }
const vector<int>& AdjacentVertices(int a) { return adj_[a]; }
 
 
pair<vector<int>, int> Dijkstra(int from, int to) {
    const int verticesCount = VerticesCount();
 
    // На початку всі відстані вважають нескінченними, лише стартова - 0
    vector<int> distances(verticesCount, kImpossibleDistance);
    distances[from] = 0;
 
    vector<int> prev(verticesCount, kImpossibleIndex);
 
    // Коли ми будемо порівнювати два об'єкти типу VertexWeight, то порівняння відбуватиметься по першому елементу.
    // Оскільки ми використовуємо чергу з пріоритетом в якій вершини впорядковані згідно з їхньою відстанню, то відстань іде першою
    using VertexWeight = pair<int /*відстань*/, int/*номер вершини*/>;
 
    // Set містить вершини, які ми ще невідвідали, вершини впорядковані згідно з поточною відстанню до них
    // Але ми можемо оновлювати цю відстань, якщо знайдемо коротший шлях
    // Під час оновлення вершини автоматично перевпорядковуються
    // !! оригінальний алгоритм використовує чергу з пріоритетом, але stl::priority_queue не підтримує оновлення елементів
    set<VertexWeight> notVisited;
 
    for (int i = 0; i < verticesCount; ++i) { // (0)
        notVisited.insert(make_pair(distances[i], i));
    }
 
    while (notVisited.size()) { // (1)
        // Видобуваємо вершину з найменшою вагою, на першій ітерації це вершина з індексом from
        VertexWeight vw = *notVisited.begin();
        notVisited.erase(notVisited.begin());
        const int currentIndex = vw.second;
        const int currentDistance = vw.first;
        if (currentDistance == kImpossibleDistance) throw "Impossible distance";
 
        // Якщо вершина з найменшою вагою це наша to, то закінчуємо
        if (currentIndex == to) break;
 
        // Для кожного сусіда видобутої вершини
        const vector<int>& adjacent = AdjacentVertices(currentIndex);
        for (int i = 0; i < adjacent.size(); ++i) { // (2)
            if (adjacent[i] != kImpossibleWeight) {
                int alt = currentDistance + adjacent[i]; // альтернативна відстань до вершини з індексом i
                if (alt < distances[i]) { // (3)
                    // Нам треба оновити вершину в set. Для цього ми її повинні знайти, видалити і вставити заново
                    notVisited.erase(make_pair(distances[i], i));
                    distances[i] = alt;
                    prev[i] = currentIndex;
                    notVisited.insert(make_pair(alt, i));
                }
            }
        }
    }
 
    // Формуємо шлях, проходимо від кожної вершини до її попередньої
    vector<int> path;
    int currentPathIndex = to;
    while (prev[currentPathIndex] != kImpossibleIndex) {
        currentPathIndex = prev[currentPathIndex];
        path.push_back(currentPathIndex);
    }
    // Але нам потрібен шлях від from до to, а не навпаки
    reverse(path.begin(), path.end());
    return make_pair(path, distances[to]);
}
 
void showcase(int from, int to) {
    vector<int> path;
    int distance;
    tie(path, distance) = Dijkstra(from, to);
 
    setlocale(LC_CTYPE, "ukr");
 
    cout << "Шлях: ";
    for (int i = 0; i < path.size(); ++i) {
        cout << path[i] << "-";
    }
    cout << to << endl;
    cout << "Відстань: " << distance << endl;
}
 
int main()
{
    // На вході маємо граф зображений на рисунку
    // https://u...content-available-to-author-only...a.org/wikipedia/commons/5/57/Dijkstra_Animation.gif
    InitGraph(6);
    InsertEdge(1, 0, 7);
    InsertEdge(2, 0, 9);
    InsertEdge(2, 1, 10);
    InsertEdge(3, 1, 15);
    InsertEdge(3, 2, 11);
    InsertEdge(4, 3, 6);
    InsertEdge(5, 0, 14);
    InsertEdge(5, 2, 2);
    InsertEdge(5, 4, 9);
    // У результаті цих вставлянь маємо таку трикутну матрицю в g із вагами ребер
    //    0  1  2  3  4  5
    // 0: x, 7, 9, 0, 0,14
    // 1: 7, x,10,15, 0, 0
    // 2: 9,10, x,11, 0, 2
    // 3: 0,15,11, x, 6, 0
    // 4: 0, 0, 0, 6, x, 9
    // 5:14, 0, 2, 0, 9, x
 
    showcase(0, 1); cout << endl;
    showcase(0, 2); cout << endl;
    showcase(0, 3); cout << endl;
    showcase(0, 4); cout << endl;
    showcase(0, 5); cout << endl;
 
    return 0;
}
 
// Розбір асимптотичної складності для графа з V вершинами і E ребрами. 
// На початку notVisited містить V вершин - усі.
// Під час кожної ітерації циклу (1) ми зменшуємо розмір notVisited на 1, отже не більше ніж V ітерації,
// може бути менше, але це неважливо для складності, бо ми не можемо на це сподіватись.
//
// Тепер порахуємо скільки разів відбувається цикл (2). Здавалось би, що це V*V, - V в notVisited і кожна вершина може мати до V-1 сусідів,
// Але фактично, ми проходимо усі ребра не більше ніж по два рази кожне
// (з однієї вершини в бік іншої і навпаки, бо (1) на кожній ітерації працює з іншою вершиною).
// Тобто тіло цикла (2) виконується не більше E разів.
//
// Умовний оператор (3) обов'язоково виконається для кожного ребра хоч раз (зменшуємо з kImpossibleDistance).
// Видалення і вставлення в set має логарифмічну складність.
// Отже асимптотична складність становить O(E*log(V))
//
// Упс, забули про цикл (0). Він виконується V разів. І кожна вставка log(V).
// Отже, сумарна складність O((E+V)*log(V)). Якщо граф зв'язаний (тоді E >= V-1), то можна записати як O(E*log(V)).