/// (C) 2010, Andrew Polar under GPL ver. 3.
//   LICENSE
//
//   This program is free software; you can redistribute it and/or
//   modify it under the terms of the GNU General Public License as
//   published by the Free Software Foundation; either version 3 of
//   the License, or (at your option) any later version.
//
//   This program is distributed in the hope that it will be useful, but
//   WITHOUT ANY WARRANTY; without even the implied warranty of
//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//   General Public License for more details at
//   Visit <http://www.gnu.org/copyleft/gpl.html>.
//
// This is DEMO of Dictionary class, which is part of iROLZ algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <math.h>
#include <string.h>

class Dictionary {
public:
	Dictionary(int PrefixSize, int OffsetLen);
	~Dictionary();
	void updateDictionary(unsigned char byte);
	int  getNextPosition(int position);
private:
	int* m_last_position_lookup;
	int* m_self_addressed_dictionary;
	int m_prefix_mask, m_buffer_mask, m_context, m_index;
};

Dictionary::Dictionary(int PrefixSize, int OffsetLen) {
	if (PrefixSize == 1) m_prefix_mask = 0xff;
	else if (PrefixSize == 2) m_prefix_mask = 0xffff;
	else m_prefix_mask = 0xffffff;
	m_last_position_lookup = (int*)malloc((m_prefix_mask + 1) * sizeof(int));
	memset(m_last_position_lookup, 0x00, (m_prefix_mask + 1) * sizeof(int));
	m_buffer_mask = (1<<OffsetLen) - 1;
	m_self_addressed_dictionary = (int*)malloc((m_buffer_mask + 1) * sizeof(int));
	memset(m_self_addressed_dictionary, 0x00, (m_buffer_mask + 1) * sizeof(int));
	m_context = m_index = 0;
}

Dictionary::~Dictionary() {
	if (m_self_addressed_dictionary) free(m_self_addressed_dictionary);
	if (m_last_position_lookup)      free(m_last_position_lookup);
}

void Dictionary::updateDictionary(unsigned char byte) {
	m_context <<= 8;
	m_context |= byte;
	m_context &= m_prefix_mask;
	m_self_addressed_dictionary[m_index & m_buffer_mask] = m_last_position_lookup[m_context];
	m_last_position_lookup[m_context] = m_index;
	++m_index;
}

int Dictionary::getNextPosition(int position) {
	return m_self_addressed_dictionary[position & m_buffer_mask];
}

int main() {

	const int size = 50;
	unsigned char data[size] = {1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0};

	int prefix_size = 2; //can be 1, 2 or 3. It means how many elements we compare.

	//5 is a bitlength of circular history buffer. Since it is circular buffer it looks back on
	//64 elements, twice longer than max 5 bit number. If you change it to 4 it start looking back on 32 elements. 
	Dictionary* dictionary = new Dictionary(prefix_size, 5);
	
	int index = 0;
	do {
		dictionary->updateDictionary(data[index]);
		int position = index;
		while (true) {
			int new_position = dictionary->getNextPosition(position);
			if (new_position >= position) break;   //positions should only going back in history
			if (new_position < prefix_size-1) break; //should not go to negative array index
			//next word match verification is optional, it works without it since in encoding
			//and decoding operations are going in the same way
			int current_word = 0;
			int offset_word  = 0;
			for (int k=0; k<prefix_size; ++k) {
				current_word <<= 8;
				current_word |= data[index - k];
				offset_word <<= 8;
				offset_word |= data[new_position - k];
			}
			if (current_word != offset_word) break; 
			//end of optional part
			printf("%8d %8d %8d %8d\n", current_word, offset_word, new_position, index);
			position = new_position;
		}
		printf("--------------------\n");
		++index;
	} while (index < size);
	delete dictionary;
	return 0;
}