// #include "new_delete.hpp"
#include <algorithm>
#include <chrono>
#include <cstring>
#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 nh1(std::string str)
{
    // empty input
    if (str.empty()) { return str; }

    // create vector to hold string rotations
    auto perms = std::vector<std::string>();
    perms.reserve(str.size());
    perms.push_back(str);

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

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

std::string nh2(const std::string_view sv)
{
    // empty input
    if (sv.empty()) { return {}; }

    // create strings
    auto best_str = std::string(sv);
    auto dup_str = std::string(sv);
    dup_str.append(sv);

    // compare strings
    for (std::size_t i = 1; i < sv.size(); ++i)
    {
        auto slide_view = std::string_view(dup_str.c_str() + i, sv.size());
        if (slide_view < best_str) { best_str = slide_view; }
    }

    // return best (least) string
    return best_str;
}

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>>();
    // map.reserve(180000);
    for (auto& word : input_words)
    {
        auto nh = nh2(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;
    }
}