#include "l_subset_finder.h"

void findAndSaveIntSubset(int numberOfSetElements) {
    int *arr = new int[numberOfSetElements]; // we will work on this array to generate next possible subsets
    int rows = pow(2, numberOfSetElements);
    int **twoDimArray = new int*[rows]; // all possible subsets are being saved in this 2darray
    for (int i = 0; i < rows; i++) {
        twoDimArray[i] = new int[numberOfSetElements];
    }
    int currentRowCount = 0;
    for (int i = 0; i < numberOfSetElements; i++) {
        arr[i] = 0;
        twoDimArray[currentRowCount][i] = arr[i];
    }
    int currentNumberOfPermutations = 0;
    int currentIndexInPermutation = 0;
    do {
        currentRowCount++;
        currentNumberOfPermutations++;
        currentIndexInPermutation = 0;
        int numberOfPermutationsToModify = currentNumberOfPermutations;
        while (numberOfPermutationsToModify % 2 == 0) {
            numberOfPermutationsToModify /= 2;
            currentIndexInPermutation++;
        }
        if (currentIndexInPermutation < numberOfSetElements) {
            arr[currentIndexInPermutation] = 1 - arr[currentIndexInPermutation];
            for (int i = 0; i < numberOfSetElements; i++) {
                twoDimArray[currentRowCount][i] = arr[i];
            }
        }
    } while (currentIndexInPermutation < numberOfSetElements);
    sort(twoDimArray, rows, numberOfSetElements);
    saveSubsetsToFile(twoDimArray, rows, numberOfSetElements);
}


void findAndSaveCharSubset(int numberOfSetElements) {

    int *arr = new int[numberOfSetElements];
    int rows = pow(2, numberOfSetElements); //all posible combinations = 2^numberOfElements
    int **twoDimArray = new int*[rows];
    for (int i = 0; i < rows; i++) {
        twoDimArray[i] = new int[numberOfSetElements];
    }
    int currentRowCount = 0;
    for (int i = 0; i < numberOfSetElements; i++) {
        arr[i] = 0;
        twoDimArray[currentRowCount][i] = arr[i];
    }
    int currentNumberOfPermutations = 0;
    int currentIndexInPermutation = 0;
    do {
        currentRowCount++;
        currentNumberOfPermutations++;
        currentIndexInPermutation = 0;
        int numberOfPermutationsToModify = currentNumberOfPermutations;
        while (numberOfPermutationsToModify % 2 == 0) {
            numberOfPermutationsToModify /= 2;
            currentIndexInPermutation++;
        }
        if (currentIndexInPermutation < numberOfSetElements) {
            arr[currentIndexInPermutation] = 1 - arr[currentIndexInPermutation];
            for (int i = 0; i < numberOfSetElements; i++) {
                twoDimArray[currentRowCount][i] = arr[i];
            }
        }
    } while (currentIndexInPermutation < numberOfSetElements);
    sort(twoDimArray, rows, numberOfSetElements);
    saveCharSubsetsToFile(twoDimArray, rows, numberOfSetElements);
}

void findAllSubsetsOfGivenSizeOfASet(int numberOfElementsInSet, int numberOfElementsInSubSet) {

    if (numberOfElementsInSet < numberOfElementsInSubSet) {
        return;
    }
    std::ofstream writingStreamInt("intSubsetOut2.txt");
    std::ofstream writingStreamChar("charSubsetOut2.txt");

    char ch = 'a';
    int *arr = new int[numberOfElementsInSubSet];
    int i;
    for (i = 0; i < numberOfElementsInSubSet; i++) {
        arr[i] = i;
    }
    int p = numberOfElementsInSubSet - 1;
    while (p >= 0) {
        for (int j = 0; j < numberOfElementsInSubSet; j++) {
            writingStreamInt << arr[j] << " ";
            writingStreamChar << static_cast<char>(ch + arr[j]);
            ch = 'a';
        }
        writingStreamInt << std::endl;
        writingStreamChar << std::endl;
        if (arr[numberOfElementsInSubSet - 1] == numberOfElementsInSet)
            p--;
        else
            p = numberOfElementsInSubSet - 1;
        if (p >= 0) {
            for (i = numberOfElementsInSubSet - 1; i >= p; i--)
                arr[i] = arr[p] + i - p + 1;
        }
    };
    writingStreamInt.close();
    writingStreamChar.close();
}

void sort(int **&arr, int rows, int numberOfSetElements) {
    int *eachRowBinaryRepresentation = new int[rows] {0};
    for (int i = 0; i < rows; i++) {
        int k = numberOfSetElements - 1;
        for (int j = 0; j < numberOfSetElements; j++) {
            eachRowBinaryRepresentation[i] += arr[i][j] * pow(2, k);
            k--;
        }
    }
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < rows - 1; j++) {
            if (eachRowBinaryRepresentation[j] > eachRowBinaryRepresentation[j + 1]) {
                int temp1D = eachRowBinaryRepresentation[j];
                int *temp2D = new int[numberOfSetElements];
                eachRowBinaryRepresentation[j] = eachRowBinaryRepresentation[j + 1];
                eachRowBinaryRepresentation[j + 1] = temp1D;
                for (int k = 0; k < numberOfSetElements; k++) {
                    temp2D[k] = arr[j][k];
                }
                for (int k = 0; k < numberOfSetElements; k++) {
                    arr[j][k] = arr[j + 1][k];
                }
                for (int k = 0; k < numberOfSetElements; k++) {
                    arr[j + 1][k] = temp2D[k];
                }
            }
        }
    }
}

void saveSubsetsToFile(int **subsetsArray, int rows, int columns) {
    std::ofstream writingStream("intSubsetOut.txt");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++)
            writingStream << subsetsArray[i][j];
        writingStream << std::endl;
    }
    writingStream.close();
}

void saveCharSubsetsToFile(int **subsetsArray, int rows, int columns) {
    char *letters = new char[columns];
    char k = 'a';
    for (int i = 0; i < columns; i++) {
        letters[i] = k++;
    }
    std::ofstream writingStream("charSubsetOut.txt");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (subsetsArray[i][j] == 1) // could be true as well but type conflict warning
                writingStream << letters[j];
            else
                writingStream << "-";
        }
        writingStream << std::endl;
    }
    writingStream.close();
}

void findAllPossibleSumsToCreateNumber(int number) {
    std::ofstream writingStream("Out3.txt");
    int *partsOfNumber = new int[number];
    int *howManyTimesIsPartAppearing = new int[number];
    for (int i = 0; i < number; i++) {
        partsOfNumber[i] = -1;
        howManyTimesIsPartAppearing[i] = -1;
    }
    partsOfNumber[0] = number;
    howManyTimesIsPartAppearing[0] = 1;
    int d = 0;
    writingStream << partsOfNumber[0];
    writingStream << std::endl;
    while (partsOfNumber[0] > 1) {
        int sum = 0;
        if (partsOfNumber[d] == 1) {
            sum += howManyTimesIsPartAppearing[d];
            partsOfNumber[d] = -1; // set values to -1 so it won't be printed to file
            howManyTimesIsPartAppearing[d] = -1;
            d--;
        }
        sum += partsOfNumber[d];
        howManyTimesIsPartAppearing[d]--;
        int l = partsOfNumber[d] - 1;
        if (howManyTimesIsPartAppearing[d] > 0) {
            d++;
        }
        partsOfNumber[d] = l;
        howManyTimesIsPartAppearing[d] = sum / l;
        l = sum % l;
        if (l != 0) {
            d++;
            partsOfNumber[d] = l;
            howManyTimesIsPartAppearing[d] = 1;
        }
        for (int i = 0; i < number; i++) {
            if (howManyTimesIsPartAppearing[i] != -1) {
                for (int j = 0; j < howManyTimesIsPartAppearing[i]; j++) {
                    writingStream << partsOfNumber[i];
                    if (j < howManyTimesIsPartAppearing[i] -1)
                        writingStream << "+";
                }
                if (howManyTimesIsPartAppearing[i + 1] != -1)
                    writingStream << "+";
            }
        }
        writingStream << std::endl;
    }
    writingStream.close();
}