//Algorytm ByteRun
//wersja pakujaca sekwencje powtarzajacych sie conajmniej 3 bajtow
//Tomasz Lubinski
//www.algorytm.org

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//Kompresuje dane uzywajac algorytmu ByteRun
void ByteRunCompress(signed char a[], int length)
{
    int i = 0;

    //dopoki wszystkie bajty nie sa skompresowane
    while (i < length)
    {
        //sekwencja powtarzajacych sie conajmniej 3 bajtow
        if ((i < length-2) && 
            (a[i] == a[i+1]) &&
            (a[i] == a[i+2]))
        {
            //zmierz dlugosc sekwencji
            int j = 0;
            while ((i+j < length-2) && 
                   (a[i+j] == a[i+j+1]) &&
                   (a[i+j] == a[i+j+2]) &&
                   (j < 126))
            {
                j++;
            }
            //wypisz spakowana sekwencje
            cout << -(j+1) << ", " << (int)a[i+j] << ", ";
            //przesun wskaznik o dlugosc sekwencji
            i += (j+2);
        }
        //sekwencja roznych bajtow
        else
        {
            //zmierz dlugosc sekwencji
            int j=0;
            while ((i+j < length-2) && 
                   ((a[i+j] != a[j+i+1]) || (a[i+j] != a[j+i+2])) &&
                   (j < 128))
            {
                j++;
            }
            //dodaj jeszcze koncowke
            if ((i+j == length-2) &&
                (j < 128))
            {
                j++;
            }
            if ((i+j == length-1) &&
                (j < 128))
            {
                j++;
            }
            //wypisz spakowana sekwencje
            cout << (j-1) << ", ";
            for (int k=0; k<j; k++)
            {
                cout << (int)a[i+k] << ", ";
            }
            //przesun wskaznik o dlugosc sekwencji
            i += j;
        }
    }
}

//Rozpakowywuje dane uzywajac algorytmu ByteRun
void ByteRunDecompress(signed char a[], int length)
{
    int i = 0;

    //dopoki wszystkie bajty nie sa zdekompresowane
    while (i < length)
    {
        //kod pusty
        if (a[i] == -128)
        {
            i++;
        }
        //sekwencja powtarzajacych sie bajtow
        else if (a[i] < 0)
        {
            for (int j=0; j<-(a[i]-1); j++)
            {
                cout << (int)a[i+1] << ", ";
            }
            i += 2;
        }
        //sekwencja roznych bajtow
        else
        {
            for (int j=0; j<(a[i]+1); j++)
            {
                cout << (int)a[i+1+j] << ", ";
            }
            i += a[i]+2;
        }
    }
}

//Przyklad wywolania
int main()
{
    //przykladowe dane do spakowania
    signed char a[] = {0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 2, 1, 3};
    ByteRunCompress(a, 23);
    cout<<"\n";

    //przykladowe dane do rozpakowania
    signed char b[] = {-4, 0, 5, 1, 2, 3, 4, 5, 6, -2, 7, -5, 8, 2, 2, 1, 3};
    ByteRunDecompress(b, 17);
    cout<<"\n";

    system("PAUSE");
}