#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <bitset>

using namespace std;

const int encLength = 1;
const int dictSize = 8;
const int bufferSize = 8;

//string sampleString = "abracadabra";
string dictionary = "aaaaaaaa";

struct compressingInfo{
    int length;
    int offset;
    bool found;
    string off;
};

static vector <compressingInfo> output;

string readFile(){
    string input;
    ifstream myFile ("example.txt");

    if (myFile.is_open()) {
        while ( getline (myFile,input) ) {
            cout << input << '\n';
         }
     myFile.close();
    } else {
      cout << "Unable to open file";
      input = "abracadabra";
    }

    return input;
}

void showOutput(){
    if(encLength <= 1){
        for(int i = 0; i < output.size(); i++){
            if(output[i].found == true){
                cout << "Found: " << output[i].found << " Offset: " << output[i].off << endl;
            } else {
            cout << "Found: " << output[i].found << " Offset: " << output[i].offset << " Length: " << output[i].length << endl;
            }
        }
    } else {
        for(int i = 0; i < output.size(); i++){
            if(output[i].found == true){
                cout << "Found: " << output[i].found << " Offset: " << output[i].off << " Length: " << output[i].length << endl;
            } else {
            cout << "Found: " << output[i].found << " Offset: " << output[i].offset << " Length: " << output[i].length << endl;
            }
        }
    }
}

void bitForm(){
    for (int i = 0; i < output.size(); i++) {
        if (output[i].found == true) {
            string match = std::bitset<1>(output[i].found).to_string();
            string character = std::bitset<8>(output[i].off.c_str()[0]).to_string();
            cout << match << " " << character << " ";
        } else {
            string match = std::bitset<1>(output[i].found).to_string();
            string offset = std::bitset<8>(output[i].offset).to_string();
            string length = std::bitset<3>(output[i].length).to_string();
            cout << match << " " << offset << " " << length << " ";
        }
    }
    cout << endl;
}

void decompress(){
    cout << " ==== DECOMPRESSING ====" << endl;
    string outputString = "";
    string chain = dictionary;

    for(int i = 0 ; i < output.size(); i++) {
        if(output[i].found == true) {
            outputString += output[i].off;
            chain += output[i].off;
        } else {
            outputString += chain.substr(output[i].offset, output[i].length);
            chain += chain.substr(output[i].offset, output[i].length);
        }
        chain = chain.substr(chain.length() - dictSize);
    }

    cout << outputString << endl;
}

void compress(){
    cout << "==== COMPRESSING ====" << endl;
    string sampleString = readFile();
    string chain = dictionary + sampleString;

    for(int i = 0; i < sampleString.length();) {
        string toSearch = chain.substr(i, dictSize);
        string buffer = sampleString.substr(i, bufferSize);

        while(toSearch.find(buffer) == string::npos && buffer.length() > encLength) {
            buffer = buffer.substr(0, buffer.length()-1);
        }

        if(toSearch.find(buffer) == string::npos) {
            compressingInfo obj;
            obj.found = true;
            obj.off = buffer;
            obj.offset = toSearch.find(buffer);
            obj.length = buffer.length();
            output.push_back(obj);
        } else {
            compressingInfo obj;
            obj.found = false;
            obj.off = buffer;
            obj.offset = toSearch.find(buffer);
            obj.length = buffer.length();
            output.push_back(obj);
        }
        i += buffer.length();
    }
    showOutput();
    bitForm();
    decompress();
}

int main(){
    compress();
    system("PAUSE");
    return 0;
}