#include <iostream>


using namespace std;
/*
    Задача 2: Запълване на масива.
    Запълване на двумерен динамичен масив със стойности също въведени от потребителя.
*/
/*
    Check if any row of the array has duplicated elements. This functions is used... TODO
*/
bool setHasDupes (int *arr, unsigned sz){
    for (int i = 0; i < sz; i++) {
        for (int j = i+1; j < sz; j++) {
            if (arr[i] == arr[j]) {
                return true;
            }
        }
    }
    return false;
}

void fillArray (int **arr, int rows, int cols){
    for (unsigned i=0; i<rows; ++i) {
        for (unsigned j=0; j<cols; ++j) {
            cin >> arr[i][j];
        }
        if(setHasDupes(arr[0], cols)){
            i--;
        }
    }
}

/*
    Тестова функция.
    отпечатване на масива в следния вид по редове
    row 1 : {1, 2, 3, 4},
    row 2 : {5, 6, 7, 8}.
*/
void printArray (int **arr, int rows, int cols){
    for (unsigned i=0; i<rows; ++i) {
        cout << "row " << i+1 << ": || ";
        for (unsigned j=0; j<cols; ++j) {
            cout << arr[i][j] << ((j==cols-1)?" || ":" | ");
        }
        cout << ((i==rows-1)?" || ":" | ") << endl;
    }

}

/*
    Задача 3:
    Проверка дали функцията е инекция.
    Взема стойност от първи ред и сравнява със всияки стойности от втори ред,
    като търси дали въпросната стойнос се среща брой различен от 1 път,
    в такъв случай стойност false, в противен случай връща true;
*/
bool isInjection(int **arr, int rows, int cols){
    unsigned cnt = 0;
    for (int i = 0; i < cols; i++){
            cnt = 0;
        for (int j = 0; j < cols; j++){
            if(arr[0][i] == arr[1][j]){
                cnt++;
            }
        }
        if(cnt != 1){
            return false;
        }
    }
    return true;
    if(setHasDupes(arr[1], cols)){
        return false;
    } else {
        return true;
    }
}
/*
    Задача 4:
    Проверка дали функцията е сюрекция.
    Взема стойност от втори ред и сравнява със всияки стойности от първи ред,
    като търси дали въпросната стойнос се среща поне 1 път път,
    в такъв случай връща стойност false, в противен случай връща true;
*/
bool isSurjection(int **arr, int rows, int cols){
    unsigned cnt = 0;
    for (int i = 0; i < cols; i++){
            cnt = 0;
        for (int j = 0; j < cols; j++){
            if(arr[1][i] == arr[0][j]){
                cnt++;
            }
        }
        if(cnt == 0){
            return false;
        }
    }
    return true;
    if(!setHasDupes(arr[1], cols) && setHasDupes(arr[0], cols)){
        return false;
    } else {
        return true;
    }
}

/*
    Задача 5:
    Проверка дали функцията е бинекция.
    Взема за стойности резултатите от булевите функции за сюрекция и инекция и ако и двете дават за резултат true,
    следва, че функцията е бинекция. Ако поне един от резултатите е false, следва, че не е бинекция.
*/

bool isBijection(int **arr, int rows, int cols, bool(*isSur)(int**, int, int), bool(*isInj)(int**, int, int)){
    if((isSur(arr, rows, cols)) && (isInj(arr, rows, cols))){
        return true;
    } else {
    return false;
    }
}

/*6 задача*/
unsigned permutationNum( unsigned n ){
    if( n <= 1 ) return 1;
    return n * permutationNum( n-1 );
}
/*7*/
bool nepodvijNATochka(int **arr, int rows, int cols){
    for (int i = 0; i < cols; i++){
        if(arr[0][i] == arr[1][i]){
            return true;
        }
    }
    return false;
}
/*8*/
unsigned numberOfNT(int **arr, int rows, int cols){
    unsigned cnt = 0;
    for (int i = 0; i < cols; i++){
        if(arr[0][i] == arr[1][i]){
            cnt++;
        }
    }
    return cnt;
}

/*9*/
bool hasIdentities(int **arr, int rows, int cols){
    if(numberOfNT(arr, 2, cols) == cols){
        return true;
    } else {
        return false;
    }

}

int getIndex(int *set, int size, int element) {
    for (int i = 0; i < size; i++) {
        if (set[i] == element) {
            return i;
        }
    }
    return -1;
}

int getFirstFreeIndex(int *passedIndexes, int size) {
    for (int i = 0; i < size; i++) {
        if (passedIndexes[i] == 0) {
            return i;
        }
    }
    return -1;
}

void printElementsCntPerCycle(int *permutation, int *universal, int size) {
    int elementsPerIndependentCycle[size]{0};
    int currentIndependentCycle = 0;

    int cyclesCnt = 0;

    int passedIndexes[size]{0};

    int wantedIndex = 0;
    int wanted = universal[wantedIndex];

    int operatingIndex = 0;
    int upElement = universal[operatingIndex];
    int downElement = permutation[operatingIndex];

    while (cyclesCnt < size) {
        elementsPerIndependentCycle[currentIndependentCycle]++;
        while (downElement != wanted) {
            elementsPerIndependentCycle[currentIndependentCycle]++;
            passedIndexes[operatingIndex] = -1;
            operatingIndex = getIndex(universal, size, downElement);
            upElement = universal[operatingIndex];
            downElement = permutation[operatingIndex];
            cyclesCnt++;
        }
        currentIndependentCycle++;
        passedIndexes[operatingIndex] = -1;
        operatingIndex = getFirstFreeIndex(passedIndexes, size);
        if (operatingIndex == -1) {
            break;
        }
        wanted = universal[operatingIndex];
        upElement = universal[operatingIndex];
        downElement = permutation[operatingIndex];
    }

    for(int i = 0; i < currentIndependentCycle; i++){
        cout << "Cycle " << i + 1 << " has " << elementsPerIndependentCycle[i] << " elements." << endl;
    }

}

void printCycles(int *permutation, int *universal, int size) {
    int cyclesCnt = 0;

    int passedIndexes[size]{0};

    int wantedIndex = 0;
    int wanted = universal[wantedIndex];

    int operatingIndex = 0;
    int upElement = universal[operatingIndex];
    int downElement = permutation[operatingIndex];

    while (cyclesCnt < size) {
        cout << "(";
        while (downElement != wanted) {
            passedIndexes[operatingIndex] = -1;
            cout << upElement << " ";
            operatingIndex = getIndex(universal, size, downElement);
            upElement = universal[operatingIndex];
            downElement = permutation[operatingIndex];
            cyclesCnt++;
        }
        cout << upElement << ")";
        passedIndexes[operatingIndex] = -1;
        operatingIndex = getFirstFreeIndex(passedIndexes, size);
        if (operatingIndex == -1) {
            break;
        }
        wanted = universal[operatingIndex];
        upElement = universal[operatingIndex];
        downElement = permutation[operatingIndex];
    }
    cout << endl;

}



int main(){



    /*
    Задача 1:
    Дефиниране на двумерен масив с 2 реда и брой колони въведени от потребителя.
    */
    unsigned rows = 2, cols;
    cout << "Please enter number of columns: ";
    cin >> cols;
    int ** arr = NULL;
    arr = new int* [rows];
    for (unsigned i=0; i<rows; ++i) {
        arr[i] = new int[cols];
    }



    fillArray(arr, 2, cols);
    printArray(arr, 2, cols);
    printCycles(arr[1], arr[0], cols);
    printElementsCntPerCycle(arr[1], arr[0], cols);



/*
    cout << "PERMUTATIONS" << endl;
    cout << ((isInjection(arr, 2, cols))?"Yes, the function is injective!":"No, the function isn't injective!") << endl;
    cout << ((isSurjection(arr, 2, cols))?"Yes, the function is surjective!":"No, the function isn't surjective!") << endl;
    /*
    Задача 5:
    Ако една функция е едновременно инекция и сюрекция, от тя е Бинекция.
    *//*
    cout << ((isBijection(arr, 2, cols, isSurjection, isInjection))?"Yes, the function is bijective!":"No, the function isn't bijective!") << endl;
    cout << "The amount of permutations of set with 5 elements is: " << permutationNum(cols) << endl;





    cout << "NEPODVIJNI TOCHKI" << endl;
    if (nepodvijNATochka(arr, 2, cols) == true && numberOfNT(arr, 2, cols) != cols){
        cout << "Yes it has " << numberOfNT(arr, 2, cols) << " nepodvijni tochki." << endl;
    } else {
        cout << "It doesn't have nepodvijni tochki" << endl;
    }

    cout << ((hasIdentities(arr, 2, cols))?"Yes, the function has identities!":"No, the function hasn't identities!") << endl;



    cout << "INDEPENDET LOOPS" << endl;


    // Освобождава се заделената памет
    for (unsigned i=0; i<rows; ++i) {
        delete[] arr[i];
    }
    delete[] arr;
    arr = NULL;*/
    return 0;
}