/** @file ngram.cpp
 *
 *	Definition (implementation) of N-gram interface.
 *
 *	See ngram.h for more info about the interface.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

// We use std::copy() here.
#include <algorithm>
// We use numeric_limits<> here.
#include <limits>

// Self header
#include "ngram.h"

namespace ace {

//// NGram ////

/* Static members initialization.
 */

bool NGram::_context_tracing_on = false;

// Const - independent on N.

const freq_counter_t NGram::_max_frequency = std::numeric_limits<freq_counter_t>::max() >> (sizeof(ngram_type_t)*constants::bits_per_char);

const ngram_type_t NGram::_overflow_flag_mask = static_cast<ngram_type_t>(1 << (sizeof(ngram_type_t)*constants::bits_per_char - 1));

const size_t NGram::_last_bit_index = sizeof(freq_counter_t) / sizeof(ngram_type_t) - 1;
// Type mask must omit most significant bit used for overflow flag.
const ngram_type_t NGram::_type_mask = ff<ngram_type_t>() >> 1;

// Non const statics - N-dependent.

ngram_type_t NGram::_full_ngram_type = 0;

std::vector<ngram_size_t> NGram::_members_count;

std::vector<size_t> NGram::_ngrams_memory_sizes;

NGram::_overflows_map_t NGram::_overflows;

ngram_type_t NGram::_types_count = 0;

void  NGram::_type(ngram_type_t ngram_type) {
	bool overflow = _overflow();
	_frequency_bits[_last_bit_index] = ngram_type;
	if ( overflow ) {
		_frequency_bits[_last_bit_index] |= _overflow_flag_mask;
	}
}

/*	Interface item implementation - for info see description in header file.
 */
void NGram::init(void) {
	// Context tracing on?
	_context_tracing_on = settings::context_tracing_on();
	// Num = 2 to power of N.
	_types_count = static_cast<ngram_type_t>(1 << n());
	// Initialize members count table.
	for ( ngram_type_t type = 0; type < _types_count; ++type ) {
		_members_count.push_back(static_cast<ngram_size_t>(bits_in(type)));
	}
	// Initialize full N-gram infos.
	_full_ngram_type = static_cast<ngram_type_t>(~(ff<ngram_type_t>() << n()));
	// Initialize members size_of table.
	for ( ngram_size_t degree = 0; degree <= n(); ++degree ) {
		_ngrams_memory_sizes.push_back(sizeof(NGram) + degree*sizeof(Member));
	}
	if ( _context_tracing_on ) {
		// Skip zero typed N-gram!
		for ( ngram_size_t degree = 1; degree <= n(); ++degree ) {
			// 
			_ngrams_memory_sizes[degree] += sizeof(context_t);
		}
	}
}

/*	Interface item implementation - for info see description in header file.
 */
NGram::NGram(const raw_ngram_t& raw_ngram, ngram_type_t ngram_type): _frequency(1) {
	// Store N-gram type within frequency.
	_type(ngram_type);
	// 
	unsigned s = 0, i = n(); // i gets decremented.
	for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem ) {
		// If i-th bit set, then store the member, otherwise do nothing.
		if ( ith_bit(ngram_type, --i) ) { // i must starts at n()-1 and decrements every loop!
#ifdef _DEPENDENCY_MODE
			new (get(s)) Member( i_mem->second->lemma(), i_mem->second->tag(), i_mem->first, (i_mem->first == 0) ? dependency::head : i_mem->second->dependency() );
#else
			new (get(s)) Member((*i_mem)->lemma(), (*i_mem)->tag());
#endif
			++s; // !
		}
	}
	if ( _context_tracing_on ) {
		new (context()) context_t();
	}
}

/*	Interface item implementation - for info see description in header file.
 */
NGram::NGram(const NGram& source): _frequency(source._frequency) {
	// Note, that we can't init _frequency by calling frequency() getter, because we would lost
	// type info.
	// 
	std::copy(source.begin(), source.end(), this->begin());
	// Don't copy context, make new (the only copy of context should be within pooled instance).
	if ( _context_tracing_on ) {
		new (context()) context_t();
	}
}

/*	Interface item implementation - for info see description in header file.
 */
NGram::NGram(const NGram& source, ngram_type_t ngram_type): _frequency(source._frequency) {
	// Store N-gram type within frequency.
	_type(ngram_type);
	for ( ngram_size_t i = 0, j = n(), s = 0; i < n(); ++i ) {
		// If j-th bit set, then copy member, otherwise do nothing.
		if ( ith_bit(ngram_type, --j) ) { // !
			new (get(s)) Member(*source.get(i)); // Use implicitly created default constructor.
			++s; // !
		}
	}
	// Don't copy context, make new (the only copy of context should be within pooled instance).
	if ( _context_tracing_on ) {
		new (context()) context_t();
	}
}

/*	Interface item implementation - for info see description in header file.
 */
void NGram::inc(void) {
	if ( (_frequency & _max_frequency) == _max_frequency ) {
		// Maximum frequency reached!
		// Store type.
		ngram_type_t t = type();
		// Store frequency.
		_overflows.add(this, _max_frequency);
		// Reset counter.
		_frequency = 0;
		// Restore type.
		_type(t);
		// Set overflow flag bit on.
		_frequency_bits[_last_bit_index] |= _overflow_flag_mask;
	}
	// Std way.
	++_frequency;
}

/*	Interface item implementation - for info see description in header file.
 */
void NGram::add_to_context(const PartOfContext& part_of_context) {
	if ( !_context_tracing_on ) {
		return;
	}

	context_t *ctx = context();
	context_t::iterator i_part_of_context = std::find(ctx->begin(), ctx->end(), part_of_context);
	if ( i_part_of_context != ctx->end() ) {
		i_part_of_context->inc(); // This may throw!
		if ( i_part_of_context != ctx->begin() ) {
			// Keep context sorted by their frequency (DESC).
			context_t::iterator prev = i_part_of_context - 1;
			while ( prev->frequency() < i_part_of_context->frequency() ) {
				// Swap values.
				std::swap(*prev, *i_part_of_context);
				i_part_of_context = prev;
				if ( i_part_of_context == ctx->begin() ) {
					break;
				} else {
					prev = i_part_of_context - 1;
				}
			}
		}	
		return;
	}
	// Otherwise needs to be stored...
	ctx->push_back(part_of_context);
}

/*	Interface item implementation - for info see description in header file.
 */
bool operator==(const NGram& lhs, const NGram& rhs) {
	
	// Types needed to be checked first.
	if ( lhs.type() != rhs.type() ) {
		return false;
	}
	
	// N-gram types are equal => both N-grams have to have the same degree.
	ngram_size_t mc = lhs.degree(); 

	for ( ngram_size_t i = 0; i < mc; ++i ) {	
		// Compare lemmas first, then parent indices, dependency and tags in the end.
		if ( lhs.lemma(i) != rhs.lemma(i) ) {
			return false;
		}
#ifdef _DEPENDENCY_MODE
		if ( lhs.parent(i) != rhs.parent(i) ) {
			return false;
		}
		if ( lhs.dependency(i) != rhs.dependency(i) ) {
			return false;
		}
#endif
		if ( lhs.tag(i) != rhs.tag(i) ) {
			return false;
		}
	}
	// R == L
	return true;

}

/*	Interface item implementation - for info see description in header file.
 */
bool operator<(const NGram& lhs, const NGram& rhs) {

	// Types needed to be checked first.
	if ( lhs.type() < rhs.type() ) {
		return true;
	}
	if ( rhs.type() < lhs.type() ) {
		return false;
	}
	// N-gram types are equal => both N-grams have to have the same degree.
	ngram_size_t mc = lhs.degree();
	
	for ( ngram_size_t i = 0; i < mc; ++i ) {
		// Compare lemmas first, then parent indices, dependency and tags in the end.
		if ( lhs.lemma(i) < rhs.lemma(i) ) {
			// L < R
			return true;
		}
		if ( rhs.lemma(i) < lhs.lemma(i) ) {
			// R < L
			return false;
		}
#ifdef _DEPENDENCY_MODE
		if ( lhs.parent(i) < rhs.parent(i) ) {
			// L < R
			return true;
		}
		if ( rhs.parent(i) < lhs.parent(i) ) {
			// R < L
			return false;
		}
		if ( lhs.dependency(i) < rhs.dependency(i) ) {
			// L < R
			return true;
		}
		if ( rhs.dependency(i) < lhs.dependency(i) ) {
			// R < L
			return false;
		}
#endif
		if ( lhs.tag(i) < rhs.tag(i) ) {
			// L < R
			return true;
		}
		if ( rhs.tag(i) < lhs.tag(i) ) {
			// R < L
			return false;
		}
	}
	// R == L
	return false;
}

//// NGramToken ////

void *NGramToken::_ngram_space = 0;

/*	Interface item implementation - for info see description in header file.
 */
void NGramToken::init(void) {	
	// Space big enough to store full N-gram type.
	_ngram_space = operator new(NGram::size_of(NGram::n()));
}

/*	Interface item implementation - for info see description in header file.
 */
NGram * NGramToken::get(const raw_ngram_t& raw_ngram, ngram_type_t ngram_type) {
	return new (_ngram_space) NGram(raw_ngram, ngram_type);
}

/*	Interface item implementation - for info see description in header file.
 */
NGram * NGramToken::get(const NGram *source, ngram_type_t ngram_type) {
	return new (_ngram_space) NGram(*source, ngram_type);
}

} // namespace ace
