#include <iostream>
#include <fstream>
#include <windows.h>
#include <process.h>

using namespace std;

int n;
int k;
int amount;

const int threads = 4;

unsigned int WINAPI ThreadFunction(LPVOID pvParam)
{
    int* values = new int[pow(k, n)];
    int* incr = new int[n];
    int* vars = new int[n];
    int* maxValue = new int[k];
    int* minValue = new int[k];
    int* maxPoint = new int[k];
    int* minPoint = new int[k];
    int thread_id = (int)pvParam;
    int index;
    int incrDifference;
    int iterations;
    int real_k;
    int linear;
    bool algorithm;
    bool found = false;
    bool* exist = new bool[k];
    string filename = "functions";
    filename += (thread_id + '0');
    filename += ".txt";
    ifstream in(filename);
    string outfile = "results";
    outfile += (thread_id + '0');
    outfile += ".txt";
    ofstream out(outfile);
    string shortname = "i";
    shortname += (thread_id + '0');
    shortname += ".txt";
    ofstream iters(shortname);
    while (!in.eof())
    {
        for (int i = 0; i < pow(k, n); i++)
            in >> values[i];
        for (int i = 0; i < n; i++)
        {
            incr[i] = 0;
            for (int j = 0; j < pow(k, n - 1); j++)
            {
                index = j;
                for (int l = n - 2; l >= 0; l--)
                {
                    vars[l] = index % k;
                    index -= vars[l];
                    index /= k;
                    if (l >= i)
                        vars[l + 1] = vars[l];
                }
                for (int l = 0; l < k - 1; l++)
                {
                    vars[i] = l;
                    index = 0;
                    for (int m = 0; m < n; m++)
                        index += (vars[m] * pow(k, n - m - 1));
                    incrDifference = values[index];
                    index -= (vars[i] * pow(k, n - i - 1));
                    for (int m = l + 1; m < k; m++)
                    {
                        vars[i] = m;
                        index += (vars[i] * pow(k, n - i - 1));
                        incr[i] += (values[index] - incrDifference);
                        index -= (vars[i] * pow(k, n - i - 1));
                    }
                }
            }
        }
        algorithm = false;
        iterations = 0;
        while (!algorithm)
        {
            iterations++;
            found = false;
            for (int i = 0; i < k; i++)
                exist[i] = false;
            for (int i = 0; i < pow(k, n); i++)
            {
                index = i;
                linear = 0;
                for (int j = n - 1; j >= 0 ; j--)
                {
                    vars[j] = index % k;
                    linear += (vars[j] * incr[j]);
                    index -= vars[j];
                    index /= k;
                }
                if (!exist[values[i]])
                {
                    exist[values[i]] = true;
                    maxPoint[values[i]] = i;
                    maxValue[values[i]] = linear;
                    minPoint[values[i]] = i;
                    minValue[values[i]] = linear;
                }
                else
                {
                    if (maxValue[values[i]] < linear)
                    {
                        maxPoint[values[i]] = i;
                        maxValue[values[i]] = linear;
                    }
                    if (minValue[values[i]] > linear)
                    {
                        minPoint[values[i]] = i;
                        minValue[values[i]] = linear;
                    }
                }
            }
            real_k = k;
            for (int i = k - 1; i >= 0; i--)
                if (!exist[i])
                {
                    for (int j = i + 1; j < real_k; j++)
                    {
                        maxPoint[j - 1] = maxPoint[j];
                        maxValue[j - 1] = maxValue[j];
                        minPoint[j - 1] = minPoint[j];
                        minValue[j - 1] = minValue[j];
                    }
                    real_k--;
                }
            for(int i = 0; i < real_k - 1; i++)
                if (maxValue[i] > minValue[i + 1])
                {
                    found = true;
                    index = maxPoint[i];
                    for (int j = n - 1; j >= 0; j--)
                    {
                        vars[j] = index % k;
                        incr[j] -= vars[j];
                        index -= vars[j];
                        index /= k;
                    }
                    index = minPoint[i + 1];
                    for (int j = n - 1; j >= 0; j--)
                    {
                        vars[j] = index % k;
                        incr[j] += vars[j];
                        index -= vars[j];
                        index /= k;
                    }
                    break;
                }
            if (!found)
            {
                for(int i = real_k - 1; i >= 0; i--)
                    if (!exist[i])
                    {
                        real_k++;
                        for (int j = real_k - 1; j > i; j--)
                        {
                            maxPoint[values[j + 1]] = maxPoint[values[j]];
                            maxValue[values[j + 1]] = maxValue[values[j]];
                            minPoint[values[j + 1]] = minPoint[values[j]];
                            minValue[values[j + 1]] = minValue[values[j]];
                        }
                        minValue[i] = maxValue[i - 1] + 1;
                        maxValue[i] = minValue[i + 1] - 1;
                    }
                out << "coeffs = {";
                for (int i = 0; i < n - 1; i++)
                    out << incr[i] << ", ";
                out << incr[n - 1] << "}\tborders = {";
                for (int i = 1; i < k; i++)
                    out << minValue[i] << ", ";
                out << "infinity}\titerations = " << iterations << ".\n";
                algorithm = true;
                iters << iterations << "\n";
            }
        }
    }
    delete[] values;
    delete[] incr;
    delete[] vars;
    delete[] maxValue;
    delete[] minValue;
    delete[] maxPoint;
    delete[] minPoint;
    delete[] exist;
    out.close();
    iters.close();
    in.close();
}

int readInfo()
{
    int tmpThreads = 0;
    ifstream info("info.txt");
    info >> n >> k >> amount >> tmpThreads;
    info.close();
    if (tmpThreads != threads)
    {
        printf("[x] threads amount doesn't match. change the value at line 12.\n");
        return 0;
    }
    return 1;
}

int main()
{
    int starttime = GetTickCount();
    if (!readInfo())
        return 0;
    HANDLE hThreads[threads];
    for (int i = 0; i < threads; i++)
    {
        hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunction, (LPVOID)i, 0, NULL);
        if (hThreads[i] == NULL)
        {
            printf("[x] thread #%d cannot be created, error %d", i, GetLastError());
            return 1;
        }
    }
    WaitForMultipleObjects(threads, hThreads, TRUE, INFINITE);
    //ThreadFunction((LPVOID)3);
    printf("program is finished in %d ms\n", (GetTickCount() - starttime));
    system("pause");
    return 0;
}