#include "ReadWriter.h"
#include <algorithm>
//в ReadWriter.h все подключено (Node.h, string, vector, iostream..)
using namespace std;

class buffer
{
public:

    buffer(int size) : cur(0), len(size)
    {
        buf = new char[size];
    }

    void append(char* str, int size)
    {
        int dif = cur + size - len;
        if (dif > 0)
        {
            int l = cur - dif;
            char* old = new char[l];
            memcpy(old, buf + dif, l);
            memcpy(buf, old, l);
            cur = l;
        }
        memcpy(buf + cur, str, size);
        cur += size;
    }

    int length()
    {
        return len;
    }

    int size()
    {
        return cur;
    }

    int freeSize()
    {
        return len - cur;
    }

    char operator[](int i)
    {
        return buf[i];
    }

private:

    int cur;
    int len;
    char* buf;
};

class strbuffer
{
public:

    strbuffer(string& s, int size)
    {
        len = s.size();
        if (size > s.size())
            bufSize = len;
        else
            bufSize = size;

        buf = new char[len];
        memcpy(buf, s.c_str(), len);
    }

    char* getBuf(int count)
    {
        char* nbuf = new char[count];
        memcpy(nbuf, buf, count);
        len -= count;
        if (len < bufSize)
            bufSize = len;
        memcpy(buf, buf + count, len);

        return nbuf;
    }

    int length()
    {
        return len;
    }

    int size()
    {
        return bufSize;
    }

    char operator[](int i)
    {
        return buf[i];
    }

private:

    int bufSize;
    char* buf;
    int len;
};

// s — исходная строка
// res - вектор троек (offs, len, ch)
// histBufMax, prevBufMax - Макс длины буферов истории и предпросмотра
// функция возвращает список блоков
void encodeLZ77(string& s, vector<Node>& res, int histBufMax, int prevBufMax)
{
    buffer dict(histBufMax);
    strbuffer buf(s, prevBufMax);

    while (buf.length() > 0)
    {
        int bufMax = 0;
        int dictLen = 0;
        int firstMax = 0;

        while (dictLen < dict.size())
        {
            int first = 0;
            int bufLen = 0;
            while (dictLen < dict.size() && buf[bufLen] != dict[dictLen])
                ++dictLen;

            if(bufLen < buf.size() && dictLen < dict.size() && buf[bufLen] == dict[dictLen])
            {
                ++bufLen;
                first = dictLen++;
            }

            while (bufLen < buf.size() && dictLen < dict.size() && buf[bufLen] == dict[dictLen])
            {
                ++bufLen;
                ++dictLen;
            }

            if (bufLen > bufMax)
            {
                bufMax = bufLen;
                firstMax = first;
            }
        }

        while (bufMax < buf.size() && buf[bufMax] == dict[firstMax])
            ++bufMax;

        char c = buf[bufMax];
        dict.append(buf.getBuf(bufMax + 1), bufMax + 1);
        if (bufMax == 0)
            res.push_back(Node(0, 0, c));
        else //                Сука параша ебаная это смещение...
            res.push_back(Node(dict.length() - dict.freeSize() - bufMax + firstMax - 1, bufMax, c));
    }
}

int main(int argc, const char* argv[])
{
    // Здесь предлагается задать размер окна в байтах (отдельно буфера предыстории и предпросмотра).
    // В сумме должны образовывать столько, сколько надо в задании.
    // history buffer 3 kb.
    int histBufMax = 1024 * 3;
    // preview buffer 1 kb.
    int prevBufMax = 1024;

    ReadWriter rw;
    string s = "";
    //rw.readString(s);

    for (int i = 0; i < 5000; ++i)
        s += "a";
    s += "#";

    // Основной структурой выбран вектор, так как заранее неизвестно какое количество элементов будет записано.
    vector<Node> v;

    encodeLZ77(s, v, histBufMax, prevBufMax);

    rw.writeCode(v);
    return 0;
}