//#include "new_delete.hpp"
#include <algorithm>
#include <chrono>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

struct Timer
{
    using clock_type = std::chrono::high_resolution_clock;
    using time_point_type = std::chrono::time_point<clock_type>;
    using duration_type = std::chrono::duration<double>;

    time_point_type start;
    std::string name;

    Timer(const std::string& name) : name(name) { start = clock_type::now(); }
    ~Timer()
    {
        auto end = clock_type::now();
        auto duration = duration_type(end - start);
        auto ms = duration.count() * 1000.0f;
        std::cout << "Timer '" << name << "' took " << ms << "ms " << std::endl;
    }
};

std::vector<std::string> read_words(const std::string& file_path)
{
    auto words = std::vector<std::string>();
    auto ifs = std::ifstream(file_path);
    auto line = std::string();

    while (ifs)
    {
        std::getline(ifs, line);
        words.push_back(line);
    }

    return words;
}

std::string necklace_hash(std::string str)
{
    if (str.empty()) { return str; }

    auto perms = std::vector<std::string>();
    perms.reserve(str.size());
    perms.push_back(str);

    for (std::size_t i = 1; i < str.size(); ++i)
    {
        std::rotate(str.begin(), str.begin() + 1, str.end());
        perms.push_back(str);
    }

    auto min_it = std::min_element(perms.begin(), perms.end());
    return *min_it;
}

int main()
{
    // get filename
    std::cout << "Enter a filename: ";
    auto filename = std::string();
    std::cin >> filename;

    // read words from file
    auto t1 = Timer("include IO");
    auto input_words = read_words(filename);
    auto t2 = Timer("without IO");

    // sort words into necklaces
    auto map = std::unordered_map<std::string, std::vector<std::string>>();
    for (auto& word : input_words)
    {
        auto nh = necklace_hash(word);
        map[nh].push_back(std::move(word));
    }

    // get key with 4 permutations
    auto key4 = std::string();
    for (auto& [key, value] : map) { if (value.size() == 4) { key4 = key; break; } }

    // output results
    if (key4.empty()) { std::cout << "No set of 4 necklace strings found." << std::endl; }
    else
    {
        std::cout << "Key4: " << key4 << '\n';
        std::cout << "Values:";
        for (auto& val : map[key4]) { std::cout << '\n' << val; }
        std::cout << '\n' << std::endl;
    }
}