/*
* Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
* This component and the accompanying materials are made available
* under the terms of the License "Eclipse Public License v1.0"
* which accompanies this distribution, and is available
* at the URL "http://www.eclipse.org/legal/epl-v10.html".
*
* Initial Contributors:
* Nokia Corporation - initial contribution.
*
* Contributors:
*
* Description: 
*
*/

#ifndef BYTE_PAIR_H
#define BYTE_PAIR_H

 
#ifdef __VC32__
 #ifdef __MSVCDOTNET__
  #include <strstream>
  #include <iomanip>
 #else //!__MSVCDOTNET__
  #include <strstrea.h>
  #include <iomanip.h>
 #endif //__MSVCDOTNET__
#else // !__VC32__
#ifdef __TOOLS2__ 
#include <sstream>
#include <iomanip>
#include <iostream>
using namespace std;
#else
 #include <strstream.h>
 #include <iomanip.h>
 #endif
#endif // __VC32__

//#include <myassert.h>
//#define DEBUG_ASSERT
#ifdef DEBUG_ASSERT
void myassert(int c);
#else
#define myassert(c) 
#endif

#include <e32cmn.h> 
typedef struct {
    TUint16 Count;
    TUint16 Index; 
} TPairCountIndex;

typedef struct {
    TUint16 Pair;
    TUint16 Next;
    TUint16 Prev;
    TUint16 Pos;
} TPair;
typedef struct {
    TUint16 Pos;
    TUint16 Next;
} TPos;

const TInt MaxBlockSize = 0x1000;

const TUint16 PosEnd = 0xffff;
const TUint16 PosHead = 0xfffe;
const TUint8 ByteRemoved = 'R';
const TUint8 ByteMarked = 'M';
const TUint8 ByteHead = 'H';
const TUint8 ByteTail = 'T';
const TUint8 ByteNew = 'N';
class CBytePair {
    private:
        TInt    marker;
        TInt    markerCount;
        TUint8  Mask[MaxBlockSize];
        TUint16 ByteCount[0x100];
        TUint16 ByteIndex[0x100];
        TUint16 BytePos[MaxBlockSize];
        TPairCountIndex PairCount[0x10000];
        TPair   PairBuffer[MaxBlockSize*2];
        TInt    PairBufferNext;
        TPos    PairPos[MaxBlockSize*3];
        TUint16 PairPosNext;
        TUint16 PairLists[MaxBlockSize/2+2];
        TInt    PairListHigh;

        void CountBytes(TUint8* data, TInt size) {
	    memset(reinterpret_cast<char*>(ByteCount),0,sizeof(ByteCount));
            memset(reinterpret_cast<char*>(ByteIndex),0xff,sizeof(ByteIndex));
            memset(reinterpret_cast<char*>(BytePos),0xff, sizeof(BytePos));
            TUint8* dataEnd = data + size;
            int pos = 0;
            while(data < dataEnd) {
                BytePos[pos] = ByteIndex[*data];
                ByteIndex[*data] = (TUint16)pos;
                pos ++;
                ++ByteCount[*data++];
            }
        }
        inline void ByteUsed(TInt b) {
            ByteCount[b] = 0xffff;
        }
        int TieBreak(int b1,int b2) {
            return -ByteCount[b1]-ByteCount[b2];
        }
        void SortN(TUint16 *a, TInt n);
        void InsertN(TUint16 *a, TInt n, TUint16 v);
        TInt PosN(TUint16 index, TInt minFrequency);

        void Initialize(TUint8* data, TInt size);
        TInt MostCommonPair(TInt& pair, TInt minFrequency);
        TInt LeastCommonByte(TInt& byte);
        inline void InsertPair(const TUint16 pair, const TUint16 pos) {
            //ClockInsert1 = clock();
            //cout << "Pair:" << hex << setw(4) << setfill ('0') << pair << endl;
            TUint16 count = PairCount[pair].Count;
            if (0==count) {
                PairCount[pair].Index = (TUint16)PairBufferNext;
                if (PairLists[1] != PosEnd) {
                    PairBuffer[PairLists[1]].Prev = (TUint16)PairBufferNext;
                }
                PairBuffer[PairBufferNext].Next = PairLists[1];
                PairBuffer[PairBufferNext].Prev = PosHead;
                PairLists[1] = (TUint16)PairBufferNext;
                PairBuffer[PairBufferNext].Pair = pair;
                PairBuffer[PairBufferNext].Pos = PairPosNext;
                PairBufferNext ++;
                myassert(PairBufferNext < MaxBlockSize*2);
                PairPos[PairPosNext].Pos = pos; 
                PairPos[PairPosNext].Next = PosEnd;
            } else {
                TUint16 index = PairCount[pair].Index;
               
                if (PairBuffer[index].Next == PosEnd){
                    if (PairBuffer[index].Prev == PosHead){
                        PairLists[count] = PosEnd;
                    } else {
                        PairBuffer[PairBuffer[index].Prev].Next = PosEnd;
                    }
                } else {
                    if (PairBuffer[index].Prev == PosHead){
                        PairLists[count] = PairBuffer[index].Next;
                        PairBuffer[PairBuffer[index].Next].Prev = PosHead;
                    } else {
                        PairBuffer[PairBuffer[index].Prev].Next = PairBuffer[index].Next;
                        PairBuffer[PairBuffer[index].Next].Prev = PairBuffer[index].Prev;
                    }
                }
                
                if (PairLists[count+1] != PosEnd){
                    PairBuffer[PairLists[count+1]].Prev = index;
                    PairBuffer[index].Next = PairLists[count+1];
                    PairBuffer[index].Prev = PosHead;
                    PairLists[count+1] = index;
                }else{
                    PairLists[count+1] = index;
                    PairBuffer[index].Next = PosEnd;
                    PairBuffer[index].Prev = PosHead;
                }

                PairPos[PairPosNext].Pos = pos;
                PairPos[PairPosNext].Next = PairBuffer[index].Pos;
                PairBuffer[index].Pos = PairPosNext;
            }
            PairPosNext ++;
            
            myassert(PairPosNext < MaxBlockSize*3);
            PairCount[pair].Count ++;
            if (PairCount[pair].Count > PairListHigh) 
                PairListHigh = PairCount[pair].Count; 
        }
        inline void RemovePair(const TUint16 pair, const TUint16 pos){
            //ClockRemove1 = clock();
            TUint16 count = PairCount[pair].Count;
            TUint16 index = PairCount[pair].Index;
            if (count == 1 ) {
                PairCount[pair].Count = 0;
                PairCount[pair].Index = PosEnd;
                return;
            }
            
            myassert(index != PosEnd);
            TUint16 *posnextp = &PairBuffer[index].Pos;
            while (*posnextp != PosEnd){
                if (PairPos[*posnextp].Pos == pos)
                    break;
                posnextp = &PairPos[*posnextp].Next;
            }
            myassert(*posnextp != PosEnd);
            *posnextp = PairPos[*posnextp].Next;
            
            if (PairBuffer[index].Next == PosEnd){
                if (PairBuffer[index].Prev == PosHead){
                    PairLists[count] = PosEnd;
                } else {
                    PairBuffer[PairBuffer[index].Prev].Next = PosEnd;
                }
            } else {
                if (PairBuffer[index].Prev == PosHead){
                    PairLists[count] = PairBuffer[index].Next;
                    PairBuffer[PairBuffer[index].Next].Prev = PosHead;
                } else {
                    PairBuffer[PairBuffer[index].Prev].Next = PairBuffer[index].Next;
                    PairBuffer[PairBuffer[index].Next].Prev = PairBuffer[index].Prev;
                }
            }
            myassert(PairCount[pair].Count > 0);
            PairCount[pair].Count --;
            if (PairCount[pair].Count == 0)
                PairCount[pair].Index = PosEnd;
            
            count = PairCount[pair].Count;
            if (count > 0) {
                if (PairLists[count] != PosEnd){
                    PairBuffer[PairLists[count]].Prev = index;
                    PairBuffer[index].Next = PairLists[count];
                    PairBuffer[index].Prev = PosHead;
                    PairLists[count] = index;
                }else{
                    PairLists[count] = index;
                    PairBuffer[index].Next = PosEnd;
                    PairBuffer[index].Prev = PosHead;
                }
            }            
            while (PairLists[PairListHigh] == PosEnd) {
                PairListHigh --;
            }             
        }
        inline void GetPairBackward (TUint8 *data, TUint16 pos, TUint16 &pairpos, TUint16 &pair) {
            myassert(pos <MaxBlockSize);
            myassert(Mask[pos] != ByteMarked);
            myassert(Mask[pos] != ByteRemoved);
            TUint8 b = data[pos];
            if (pos == 0) {
                pair = 0;
                pairpos = PosEnd;
                return;
            }
            pos --;
            while ((pos>0) && (Mask[pos] == ByteRemoved)){
                pos --;
            }
            if ((Mask[pos] == ByteRemoved) || (Mask[pos] == ByteMarked)) {
                pair = 0;
                pairpos = PosEnd;
            } else {
                pair = (TUint16)((b << 8) | data[pos]);
                pairpos = pos;
            }
        }
        
        inline void GetPairForward (TUint8 *data, TUint16 pos, TInt size, TUint16 &pairpos, TUint16 &pair) {
            myassert(Mask[pos] != ByteMarked);
            myassert(Mask[pos] != ByteRemoved);
            myassert(pos < size);
            TUint8 b = data[pos];
            pairpos = pos;
            pos ++;
            while ((pos < size) && (Mask[pos] == ByteRemoved))
                pos++;
            if ((pos == size) || (Mask[pos] == ByteMarked)) {
                pair = 0;
                pairpos = PosEnd;
            } else {
                pair = (TUint16)(b | (data[pos] << 8));
            }
        }
#ifdef  __TOOLS2__        
        void DumpList(TUint8 *data, TInt size) {
            int i, j;
            cout << "src: " << dec << size << " bytes"<< endl;
            for (i=0;i<size;i+=16){
                cout << endl;
                cout << hex;
                cout << setfill('0') << setw(4) << right << i << " ";
                for (j=0;j<16;j++) {
                    cout << setfill ('0') << setw(2) << right << (unsigned int)data[i+j] << " ";
                }
                cout << "    ";
                for (j=0;j<16;j++) {
                    char c = isgraph(data[i+j]) ? data[i+j]:'.';
                    cout << c;
                }
            }
            cout << endl;
            
            for (i=0;i<256;i+=16){
                cout << endl << hex << setfill('0') << setw(2) <<right <<i << " ";
                for (j=0;j<16;j++) {
                    cout << setfill ('0') << setw(4) << right << (unsigned int)ByteIndex[i+j] << " ";
                }
            }
            cout << endl;
            for (i=0;i<256;i++){
                cout << "Byte: <" << i << "> Count: " << ByteCount[i];
                TUint16 pos = ByteIndex[i];
                int j = 0;
                while (pos != PosEnd){
                    if (j++ % 16 == 0)
                        cout << endl << "    ";
                    cout << hex << setw(4) << setfill('0') << pos << " ";
                    pos = BytePos[pos];
                }
                cout << endl;
            }
            cout << "buffer lists" << endl;
            for (i=PairListHigh; i>=0; i--){
                TUint16 index = PairLists[i];
                if (index == PosEnd)
                    continue;
                cout << dec;
                cout << "List " << i << endl;
                while (index != PosEnd){ 
                    char b0 = (char)PairBuffer[index].Pair;
                    char b1 = (char)(PairBuffer[index].Pair >> 8);
                    cout << "    " << setw(4) << setfill('0') << hex << PairBuffer[index].Pair << " " << "<" << (isgraph(b1)? b1:'.') << (isgraph(b0) ? b0 : '.') << ">";  
                    TUint16 pos;
                    pos = PairBuffer[index].Pos;
                    int k = 0;
                    while (pos != PosEnd){
                        if (k%16 ==0) {
                            cout << endl << "        ";
                        };
                        cout << setw(4) << setfill('0') << PairPos[pos].Pos << " ";
                        k ++;
                        pos = PairPos[pos].Next;
                    }
                    cout << endl;
                    index = PairBuffer[index].Next;
                }
                
            }
        }
#endif
	public:
        TInt Compress(TUint8* dst, TUint8* src, TInt size);
        TInt Decompress(TUint8* dst, TInt dstSize, TUint8* src, TInt srcSize, TUint8*& srcNext);
};
TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size, CBytePair *aBPE);

#endif