33

#include <iostream>
#include <fstream>
#include <iomanip>
#include "libBook.h"

using namespace std;

int countCharInFile(string fileName){
    int count = 0;
    ifstream fin;
    fin.open(fileName);
    if(!fin.is_open()){
        cout<<"Error read from file"<<endl;
    }else{
        while(!fin.eof()){
            fin.get();
            count++;
        }
    }
    fin.close();
    return count;
}

int** initMatrix(int size){
    int** matrix = new int*[size];
    for (int i = 0; i < size; i++)
        matrix[i] = new int[size];
    for (int i = 0; i < size; i++){
        for (int j = 0; j < size; j++){
            matrix[i][j] = 0;
        }
    }
    return matrix;
}

void fillMatrixFromFile(int** matrix, int size, string fileName){
    ifstream fin;
    fin.open(fileName);
    if(!fin.is_open()){
        cout<<"Error open file"<<endl;
    }else{
        for (int i = 0, byte; !fin.eof(); i++){
            byte = fin.get();
            if(byte == -1)
                byte = 1;
            matrix[0][i] = byte;
        }
        for (int i = 1; i < size; i++){
            for (int j = 0; j < size; j++){
                matrix[i][j] = matrix[0][(j+i)%size];
            }
            cout<<endl;
        }
    }
}

void outputMatrix(int** matrix, int N){
    cout<<endl;
    cout.setf(ios::fixed);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if(matrix[i][j] == -1 || matrix[i][j] == 10){
                if(matrix[i][j] == 38)
                    cout<<setw(4)<<"eof"<<" ";
                if(matrix[i][j] == 10)
                    cout<<setw(4)<<"\\n"<<" ";
            }else{
                cout<<setw(4)<<(char)matrix[i][j]<<" ";
            }
        }
        cout<<endl;
    }
    cout<<endl;
}

void outputMatrix(int** matrix, int N, int M){
    cout<<endl;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            if(j == 0){
                if(matrix[i][j] == -1 || matrix[i][j] == 10){
                    if(matrix[i][j] == 38)
                        cout<<i<<"eof"<<" ";
                    if(matrix[i][j] == 10)
                        cout<<i<<"\\n"<<"  ";
                }else{
                    cout<<i<<" "<<(char)matrix[i][j]<<"  ";
                }
            }else{
                cout<<" "<<matrix[i][j]<<"  ";
            }

        }
        cout<<endl;
    }
    cout<<endl;
}

void outputArray(int* array, int size){
    for (int j = 0; j < size; j++){
        if(array[j] == -1 || array[j] == 10){
            if(array[j] == 38)
                cout<<"eof"<<" ";
            if(array[j] == 10)
                cout<<"\\n"<<"  ";
        }else{
            cout<<" "<<(char)array[j]<<"  ";
        }
    }
    cout<<endl;
}

void quickSort(int *Array, int size, int L, int R){
    while(L < R){
        int x = Array[L], i = L, j = R;
        while (i <= j){
            while (Array[i] < x) i++;
            while (x < Array[j]) j--;
            if (i <= j){
                int temp;
                temp = Array[i];
                Array[i] = Array[j];
                Array[j] = temp;
                i++; j--;
            }
            if((j - L) > (R - i)){
                quickSort(Array, size, i, R);
                R = j;
            }else{
                quickSort(Array, size, L, j);
                L = i;
            }
        }
    }
}

void quickSort(int **Array, int size, int L, int R, int pointer){
    cout<<"pppp";
    while(L < R){
        int x = Array[L][pointer], i = L, j = R;
        while (i <= j){
            while (Array[i][pointer] < x) i++;
            while (x < Array[j][pointer]) j--;
            if (i <= j){
                int temp;
                for(int k = 0; k < size; k++){
                    temp = Array[i][k];
                    Array[i][k] = Array[j][k];
                    Array[j][k] = temp;
                }
                i++; j--;
            }
            if((j - L) > (R - i)){
                quickSort(Array, size, i, R, pointer);
                R = j;
            }else{
                quickSort(Array, size, L, j, pointer);
                L = i;
            }
        }
    }
}

void sortMatrix(int** array, int size, int begin, int end, int pointer){
    cout<<"ха ха";
    int currentItem = 0;
    int series = 0;
    if(pointer == size-2)
        quickSort(array, size, 0, size-1, pointer);
    for(int i = begin; i < end; i++){
        if (currentItem == array[i][pointer]){
            series++;
        }else{
            if(series > 0){
                quickSort(array, size, i-series-1, i-1, pointer-1);
                sortMatrix(array, size, i-series-1, i , pointer-1);
                series = 0;
            }
            currentItem = array[i][pointer];
        }
    }
    if(series > 0){
        quickSort(array, size, end-series-1, end-1, pointer-1);
        sortMatrix(array, size, end-series-1, end , pointer-1);
    }
}

int* getBWT(int** array, int size){
    int* BWT = new int[size];
    for(int i = 0; i < size; i++){
        BWT[i] = array[i][size-1];
    }
    return BWT;
}

int getIndexOfFirstItemInBWT(int* BWT, int size, int firstItem){
    int result = 0;
    for(int i = 0; i < size; i++){
        if(BWT[i] == firstItem){
            result = i;
            break;
        }
    }
    return result;
}

void copyArray(int* array1, int* array2, int size){
    for(int i = 0; i < size; i++)
        array2[i] = array1[i];
}

int** initSecondArray(int size){
    int** array = new int*[size];
    for(int i = 0; i < size; i++){
        array[i] = new int[2];
    }
    return array;
}

void fillSecondArray(int* BWT, int* firstArray, int** secondArray, int size){
    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            if(BWT[i] == firstArray[j]){
                secondArray[i][0] = BWT[i];
                secondArray[i][1] = j;
                firstArray[j] = 0;
                break;
            }
        }
    }
}

string restoreMessage(int** secondArray, int index, int size){
    if (size == 0) return "";
    string str = string(1,secondArray[index][0]);
    //string str = to_string(secondArray[index][0]) + " ";
    return  str + restoreMessage(secondArray, secondArray[index][1], size-1);
}

string BWTtoByteString(int* BWT, int size){
    string str = "";
    for(int i = 0; i < size; i++){
        str += to_string(BWT[i]) + " ";
    }
    return str;
}

int* StringToBTW(string str){
    int* BTW = new int[str.size()];
    char item;
    for(int i = 0; i < str.size(); i++){
        item = str[i];
        BTW[i] = (int)item;
    }
    return BTW;
}

int main() {
    int* arrayAlphabet;
    set<char> Alphabet = readAlphabet("../lol.txt");
    string bookCode = "";

    int countChar = countCharInFile("../lol.txt");
    int** charMatrix = nullptr;
    int* BWT = nullptr;
    int* firstDecodeArray = new int [countChar];
    int** secondDecodeArray = initSecondArray(countChar);

    charMatrix = initMatrix(countChar);
    fillMatrixFromFile(charMatrix, countChar, "../lol.txt");
    outputMatrix(charMatrix, countChar);
    int firstChar = charMatrix[0][0];

    sortMatrix(charMatrix, countChar, 0, countChar, countChar-2);
    BWT = getBWT(charMatrix, countChar);
    copyArray(BWT, firstDecodeArray, countChar);
    quickSort(firstDecodeArray, countChar, 0 , countChar-1);
    outputMatrix(charMatrix, countChar);

    //outputArray(BWT, countChar);

    cout<<endl;
    //cout<<BWTtoByteString(BWT, countChar);

    //cout<< "|| " << getIndexOfFirstItemInBWT(BWT, countChar, firstChar)<<endl;

    //outputArray(firstDecodeArray, countChar);


    fillSecondArray(BWT, firstDecodeArray, secondDecodeArray, countChar);

    //outputMatrix(secondDecodeArray, countChar, 2);

    int sizeArray = Alphabet.size();

    arrayAlphabet = new int[sizeArray];

    set<char>::iterator setIt = Alphabet.begin();
    for(int i = 0; i < sizeArray; i++, setIt++){
        arrayAlphabet[i] = *setIt;
    }

    bookCode = stackBook(BWTtoByteString(BWT, countChar), arrayAlphabet, sizeArray);
    cout<<endl;
    cout<<"Text into F1Code : \n"<<bookCode<<endl<<endl;

    setIt = Alphabet.begin();
    for(int i = 0; i < sizeArray; i++, setIt++){
        arrayAlphabet[i] = *setIt;
    }

    int bitCountCode = bookCode.size();
    int bitCountFile = weightBitOfFile("../lol.txt");

    string BookToBTW = stackBookDecode(f1_decode(bookCode), arrayAlphabet, sizeArray);
    cout<<"Restored text : \n"<<  BookToBTW <<endl;
    cout<<endl;
    cout<<"Bits in Code = "<< bitCountCode << ", Bits in File = " << bitCountFile <<endl;
    cout<<"Compression ratio "<<(float)bitCountFile/bitCountCode<<endl;


    int* restoredBWT = StringToBTW(BookToBTW);

    outputArray(BWT, countChar);
    cout<<endl;
    outputArray(restoredBWT, countChar);
    cout<<endl;
    //outputMatrix(secondDecodeArray, countChar, 2);

    cout<<restoreMessage(secondDecodeArray, getIndexOfFirstItemInBWT(restoredBWT, countChar, firstChar), countChar);

    return 0;
}