#include "solution.h"

#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_set>

struct HistoryRecord {
    int value;
    int position;
};

std::vector<int> CreateStartPermutation(size_t alphabet_size) {
    std::vector<int> start_permutation(alphabet_size + 1);
    for (size_t i = 1; i < start_permutation.size(); ++i) {
        start_permutation[i] = i;
    }
    return start_permutation;
}

std::vector<int> ReversedPermutation(const std::vector<int>& permutation) {
    std::vector<int> reversed_permutation(permutation.size());
    for (size_t i = 1; i < permutation.size(); ++i) {
        reversed_permutation[permutation[i]] = i;
    }
    return reversed_permutation;
}

std::vector<int> ApplyHistory(
        const std::vector<int>& permutation,
        const std::vector<HistoryRecord>& history
) {
    std::vector<int> updated_permutation(permutation.size());
    std::unordered_set<int> unique;
    auto updated_it = updated_permutation.begin();
    for (int i = history.size() - 1; i >= 0; --i) {
        if (unique.find(history[i].value) == unique.end()) {
            *updated_it = history[i].value;
            ++updated_it;
            unique.insert(history[i].value);
        }
    }
    for (int value : permutation) {
        if (unique.find(value) == unique.end()) {
            *updated_it = value;
            ++updated_it;
        }
    }

    return updated_permutation;
}

int FindPosByValue(
        int value,
        const std::vector<int>& permutation,
        const std::vector<int>& reversed_permutation,
        const std::vector<HistoryRecord>& history
) {
    for (int i = history.size() - 1; i >= 0; ++i) {
        if (value == history[i].value) {
            return i;
        }
    }


}

void ProcessBlock(
        const std::vector<int>& source_text,
        std::vector<int>& result_text,
        const std::vector<int>& permutation,
        std::vector<HistoryRecord>& history,
        int type,
        int block_begin,
        int block_end
) {
    const std::vector<int> reversed_permutation = ReversedPermutation(permutation);
    for (int i = block_begin; i < block_end; ++i) {

    }
    if (type == 1) {

    } else {

    }

}

std::vector<int> Solution(
        const std::vector<int>& source_text,
        size_t alphabet_size,
        int type
) {
    const int BLOCK_SIZE = static_cast<int>(std::sqrt(static_cast<double>(source_text.size()))) + 1;
    const int BLOCKS_COUNT = (static_cast<int>(source_text.size()) + BLOCK_SIZE - 1) / BLOCK_SIZE;
    std::vector<int> result_text(source_text.size());

    std::vector<int> permutation = CreateStartPermutation(alphabet_size);
    std::vector<HistoryRecord> history;
    history.reserve(BLOCK_SIZE);
    for (int block_id = 0; block_id < BLOCKS_COUNT; ++block_id) {
        const int BLOCK_BEGIN_ID = block_id * BLOCK_SIZE;
        const int BLOCK_END_ID = std::min<int>(BLOCK_BEGIN_ID + BLOCK_SIZE, source_text.size());
        permutation = ApplyHistory(permutation, history);
        ProcessBlock(
                source_text,
                result_text,
                permutation,
                history,
                type,
                BLOCK_BEGIN_ID,
                BLOCK_END_ID
        );
    }

    return result_text;
}