333

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

using namespace std;

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 fillMatrixFromString(int** matrix, string str){
        for (int i = 0, byte; i < str.size(); i++){
            byte = str[i];
            if(byte == -1)
                byte = 1;
            matrix[0][i] = byte;
        }
        for (int i = 1; i < str.size(); i++){
            for (int j = 0; j < str.size(); j++){
                matrix[i][j] = matrix[0][(j+i)%str.size()];
            }
        }
}

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){
    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){
    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;
}

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);
}

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;
}

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

int* getRowWithFirstChar(int**matrix, int size){
    int* result = new int[size];

    for(int i = 0; i < size; i++){
        result[i] = matrix[1][i];
    }
    return result;
}

int searchIndexRowWithFirstChar(int**matrix, int size, int* firstRow){
    bool equals = true;
    for(int i = 0; i <size; i++){
        for(int j = 0; j <size; j++){
            if(firstRow[j] != matrix[i][j])
                equals = false;
        }
        if(equals)
            return i;
        equals = true;
    }
    return 0;
}

string getblockBWT(int**matrix, int*BWT, string message){
    if(message == "") return "";
    matrix = initMatrix(message.size());
    fillMatrixFromString(matrix, message);
    //outputMatrix(matrix, message.size());
    int* firstCharRow = getRowWithFirstChar(matrix, message.size());

    sortMatrix(matrix, message.size(), 0, message.size(), message.size()-2);
    //outputMatrix(matrix, message.size());
    BWT = getBWT(matrix, message.size());

    return BWTToString(BWT, message.size()) + (char)(searchIndexRowWithFirstChar(matrix, message.size(), firstCharRow)+33);
}

int main() {
    string fileName = "../lol.txt";

    int blockSize = 50;
    int countChar = blockSize;
    int** charMatrix = nullptr;
    int* BWT = nullptr;
    int* firstDecodeArray = new int [countChar];
    int** secondDecodeArray = initSecondArray(countChar);
    string BWTstr = "";

    ifstream fin;
    char symbol;
    string blockText = "";
    fin.open(fileName);
    bool eof = true;
    if(!fin.is_open()){
        cout<<"fail read from file";
    }else{
        while(eof){
            for(int i = 0; i < blockSize; i++){
                symbol = fin.get();
                blockText += symbol;
                if(symbol == -1){
                    eof=false;
                    break;
                }
            }
            //cout<<blockText<<endl;
            BWTstr += getblockBWT(charMatrix, BWT,  blockText);
            blockText = "";
        }
    }
    cout<<"BWT\n"<<BWTstr<<endl;

    set<char> Alphabet = readAlphabetFromStr(BWTstr);
    string bookCode = "";

    int* arrayAlphabet;
    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 = stackBookStr(BWTstr, 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(fileName);

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

    blockText = "";
    char firstItem;
    string result = "";
    for(int i = 0, j = 0; i < BookToBTW.size(); i+=j){
        for(j = 0; j < blockSize; j++){
            if (i+j > BookToBTW.size())
                break;
            blockText += BookToBTW[i+j];
        }
        firstItem = BookToBTW[i+j];
        j++;
        if(blockText.size() < blockSize){
            firstItem = (int)blockText[blockText.size()-2];
            blockText = blockText.substr(0, blockText.size()-2);
        }

        int* restoredBWT = StringToBTW(blockText);
        copyArray(restoredBWT, firstDecodeArray, blockText.size());
        quickSort(firstDecodeArray, blockText.size(), 0 , blockText.size()-1);

        fillSecondArray(restoredBWT, firstDecodeArray, secondDecodeArray, blockText.size());
        result += restoreMessage(secondDecodeArray, ((int)firstItem)-33, blockText.size());

        //cout<<blockText <<"|| "<< ((int)firstItem)-33<<endl;
        blockText = "";
    }
    cout<<endl;
    cout<<"Restored Text:\n"<<result;

    return 0;
}