/** @file ngrams.cpp
 *
 *	Definition (implementation) of NGrams hashing store interface.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

// Self header.
#include "ngrams.h"

namespace ace {

/** Maximum N for which hashing function bitmask tables are prepared.
 */
const ngram_size_t _max_n = 8;

#ifdef _64_BIT
const size_t _lemma_bitmasks[_max_n+1] = {
	0x00, // 0: 0......0
	0xFFFFFFFF, // 1: last (whole) 32 bits
	0x00FFFFFF, // 2: last 24 bits
	0x0000FFFF, // 3: last 16 bits
	0x000003FF, // 4: last 10 bits
	0x000000FF, // 5: last 8 bits
	0x000000FF, // 6: dtto
	0x000000FF, // 7: dtto
	0x000000FF, // 8: dtto
};
#ifdef _DEPENDENCY_MODE
const size_t _dependency_bitmasks[_max_n+1] = { 
	0x00, // 0: 0......0
	0x7C, // 1: 01111100 (whole significant part)
	0x7C, // 2: 01111100 (dtto)
	0x3C, // 3: 00111100
	0x3C, // 4: 00111100
	0x1C, // 5: 00011100
	0x1C, // 6: 00011100
	0x0C, // 7: 00001100
	0x04 //  8: 00000000
};
const size_t _parent_bitmasks[_max_n+1] = {
	0x00, // 0: 0......0
	0x03, // 1: 00000011 (whole significant part)
	0x03, // 2: 00000011 (dtto)
	0x03, // 3: 00000011 (dtto)
	0x03, // 4: 00000011 (dtto)
	0x03, // 5: 00000011 (dtto)
	0x00, 0x00, 0x00 // 6-8: 0......0
};
const size_t _dp_shift[_max_n+1] = {
	0, // 0: see lemma bitmask
	32, // 1: dtto
	24, // 2: dtto
	16, // 3: dtto
	10, // 4: dtto
	8, // 5: dtto
	6, // 6: |lemma bitmask| - |no of trailing zero digits in dependency bitmask|
	6, // dtto
	0 // 8: dependency and parent bitmask are 0-length
};
#endif
// Rounded up.
const size_t _bits_per_member[_max_n+1] = { 0, 64, 32, 22, 16, 13, 11, 10, 8 };

#else // 32-bit
const size_t _lemma_bitmasks[_max_n+1] = {
	0x00, // 0: 0......0
	0x00FFFFFF, // 1: last 24 bits
	0x00000FFF, // 2: last 12 bits
	0x000000FF, // 3: last 8 bits
	0x0000003F, // 4: last 6 bits
	0x0000003F, // 5: last 6 bits
	0x0000003F, // 6: last 6 bits
	0x0000001F, // 7: last 5 bits
	0x0000000F, // 8: last 4 bits
};

#ifdef _DEPENDENCY_MODE
const size_t _dependency_bitmasks[_max_n+1] = { 
	0x00, // 0: 0......0
	0x7C, // 1: 01111100
	0x0C, // 2: 00001100
	0x1C, // 3: 00011100
	0x0C, // 4: 00001100
	0x04, // 5: 00000100
	0x00, 0x00, 0x00 // 6-8: 0......0
};
const size_t _parent_bitmasks[_max_n+1] = {
	0x00, // 0: 0......0
	0x03, // 1: 00000011
	0x03, // 2: 00000011
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00 // 3-8: 0......0
};
const size_t _dp_shift[_max_n+1] = {
	0, // 0: see lemma bitmask
	24, // 1: dtto
	12, // 2: dtto
	6, // 3: |lemma bitmask| - |no of trailing zero digits in dependency bitmask|
	4, // 4: dtto
	4, // 5: dtto
	0, 0, 0 // 6-8: dependency and parent bitmask are 0-length
};
#endif
// Rounded up.
const size_t _bits_per_member[_max_n+1] = { 0, 32, 16, 11, 8, 7, 6, 5, 4 };

#endif // 64-bit vs. 32-bit

/*	Interface item implementation - for info see description in header file.
 */
size_t NGramHashCounter::count_hash(const NGram *gram) {

	// Hash, loop counter.
	size_t hash = _seed, loop = 0;
	// How many loops to perform?
	ngram_size_t mc = gram->degree();
#ifndef _SURFACE_MODE
	size_t db = _dependency_bitmasks[mc], pb = _parent_bitmasks[mc], lb = _lemma_bitmasks[mc], dp_s = _dp_shift[mc], bpm = _bits_per_member[mc];
#else
	size_t lb = _lemma_bitmasks[mc], bpm = _bits_per_member[mc];
#endif

	for ( const NGram::Member * i_mem = gram->begin(); i_mem != gram->end(); ++i_mem, ++loop ) {
		hash ^=
			(
#ifndef _SURFACE_MODE
				(
					(
						// Dependency and parent bitmasks didn't overlap, so we can use them all in one expression.
						(i_mem->dependency() & db) | (i_mem->parent() & pb)
					)
					// The result is shifted to gain room for lemma bitmask.
					<< dp_s
				)
				|
#endif
				// Apply and add lemma bitmask.
				(i_mem->lemma() & lb)
			)
		    // Shift the l-th loop (member) related bits to their position in final hash.
			<< loop * bpm;
	}
	return hash;

}

/*	Interface item implementation - for info see description in header file.
 */
bool NGramHashCounter::check(ngram_size_t n) {
	return _max_n >= n;
}

#ifdef _USE_HASHSET

#if defined(__GNUC__)

/*	Interface item implementation - for info see description in header file.
 */
bool NGramEqualComparator::operator()(const NGram *lhs, const NGram *rhs) const {
	return *lhs == *rhs;
}

#elif defined(_MSC_VER)

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

/* Static members initialization.
 */
NGramHasher NGramHashCompare::_hasher;
NGramLessComparator NGramHashCompare::_comparator;

#endif

#endif // _USE_HASHSET


//// NGramStore ////

/*	Interface item implementation - for info see description in header file.
 */
NGramStore::NGramStore(size_t memory_pool_block_size): _memory_pools(), _hash_tables() {
	if ( memory_pool_block_size ) {
		init(memory_pool_block_size);
	}
	// Otherwise postpone initialization process (explicit call to init() will be needed).
}

/*	Interface item implementation - for info see description in header file.
 */
const NGram * NGramStore::get(const NGram *ngram) const {	
	if ( ngram->is_zero() ) {
		return &zero_ngram;
	}
	// Search for N-gram in hash tables using _find().
	_hash_table_pair_cib_t pair_cib = _find(ngram);

	if ( pair_cib.second ) {
		// Founded!
		return *(pair_cib.first);
	}
	// Otherwise => not found.
	return NULL;
}

/*	Interface item implementation - for info see description in header file.
 */
void NGramStore::init(size_t memory_pool_block_size) {
	if ( memory_pool_block_size && _hash_tables.empty() && _memory_pools.empty() ) {
		// Hash tables - separate table for each type.
#ifdef _USE_HASHSET
		// Create hash tables by use of default constructor.
		_hash_tables.resize(NGram::types_count());
#else
		// Create hash tables - pass appropriate settings values.
		_hash_tables.push_back(hash_table_t(0, 0, 0)); // Zero-index padding.
		for ( ngram_type_t type = 1; type < NGram::types_count(); ++type ) {
			// TODO: Literal!
			_hash_tables.push_back(hash_table_t(8, settings::bucket_size, settings::crop_ratio));
		}
#endif
		// Pools - separate pool for each degree.
		_memory_pools.push_back(VoidPool(0)); // Zero-index padding.
		for ( ngram_size_t degree = 1; degree <= NGram::n(); ++degree ) {
			// Make each pool contain exactly `memory_pool_block_size` units.
			_memory_pools.push_back(VoidPool(memory_pool_block_size*NGram::size_of(degree)));
		}
	}
}

/*	Interface item implementation - for info see description in header file.
 */
NGramStore::insert_status_t NGramStore::insert(const NGram *ngram) {
	if ( ngram->is_zero() ) {			
		return insert_status_t(&zero_ngram, false);
	}
	// Search for N-gram in hash tables using _find().
	_hash_table_pair_cib_t pair_cib = _find(ngram);

	if ( pair_cib.second ) {
		// Founded!
		return insert_status_t(*pair_cib.first, false);
	}

	// Note: we cannot insert ngram directly, because we DO want its copy
	// to be inserted eventually.

	// New object - new memory needed...
	void *mem = _memory_pools[ngram->degree()].get_raw_memory(ngram->size_of()); // This may throw.
	
	// Copy passed word to new memory using copy constructor and placement new,
	// insert pointer to hash table and return dereferenced iterator.
	return insert_status_t(*_hash_tables[ngram->type()].insert(new (mem) NGram(*ngram)).first, true);
}

/*	Interface item implementation - for info see description in header file.
 */
NGramStore::_hash_table_pair_cib_t NGramStore::_find(const NGram *ngram) const {
	//
	std::pair<hash_table_t::const_iterator, hash_table_t::const_iterator> ip = _hash_tables[ngram->type()].equal_range(const_cast<NGram *>(ngram));
	// If iterators are different, we found what we looked for.
	return _hash_table_pair_cib_t(ip.first, ip.first != ip.second);
}

#ifndef _USE_HASHSET
void NGramStore::sort(ngram_type_t type) {
	if ( type == 0 ) {
		// 0 means sort all (except 0 itself:)
		for ( type = 1; type <= NGram::full_ngram_type(); ++type ) {
			_hash_tables[type].sort();
		}
	} else {
		_hash_tables[type].sort();
	}
}
#endif


//// NGramsProcessor ////

/*	Interface item implementation - for info see description in header file.
 */
bool NGramsProcessor::next(void) {
	if ( _next == _end ) {
		return false;
	}
	// Otherwise...
	_ngram_frequencies.ngram = *_next;

	// Full N-gram frequency needs to be stored too.
	_ngram_frequencies.frequencies[NGram::full_ngram_type()] = _ngram_frequencies.ngram->frequency();
	
	for ( ngram_type_t type = 0; type < NGram::full_ngram_type(); ++type ) {
		// Create instance of N-gram downcasted to `type` and get frequency of his hash-stored alter ego.
		_ngram_frequencies.frequencies[type] = _ngram_store.get(NGramToken::get(*_next, type))->frequency();;
	}
	// Advance to next...
	++_next;

	return true;
}

} // namespace ace
