/** @file ngrams.h
 *	
 *	Interface declaration of structure designed to keep all instances
 *	of NGram(s).
 *
 *	NGram(s) data are saved inside memory pool(s). The use of hashing
 *	container(s) gains us the quick access to stored instances.
 *	The stored NGram instances are kept unique within the program scope.
 *
 *	Note: Because hash_set container, which is used below is not standardized,
 *	there are some differences between implementations founded in Visual Studio
 *	(based on Dinkumware library) and GCC (based on SGI library).
 *	The main difference is in comparison function. Dinkumware lib compares
 *	stored items by < operator, while SGI lib uses == operator.
 *	Therefore there are some differences in code handed to VS and to GCC
 *	(precompiler directives are used to handle this).
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _NGRAMS_H
#define _NGRAMS_H

//
#include "config.h"

#ifdef _USE_HASHSET
// Use almost std hash_set.
#if defined(_MSC_VER)
#include <hash_set>
#elif defined(__GNUC__)
// GCC stores hash_set in ext subdirectory.
#include <ext/hash_set>
#endif
#else
//
#include "hash_vector.h"
#endif

// Some vectors are engaged.
#include <vector>
// We use std::pair here.
#include <utility>

// N-gram, of course!
#include "ngram.h"
// VoidPool class.
#include "pool.h"

namespace ace {

/** Class provides hashing function for N-grams instances.
 */
class NGramHashCounter {	

#ifdef _64_BIT
	// 64-bit CPU
	/** "Random" seed.
	 */
	static const size_t _seed = 0xdeadbeeffeeddeaf;
#else
	/** "Random" seed.
	 */
	static const size_t _seed = 0xdeadbeef;
#endif

public:
	/** Function counts hash for given N-gram.
	 *	@param gram Pointer to N-gram to be hashed.
	 *	@return Hash for given N-gram.
	 */
	static size_t count_hash(const NGram *gram);
	/**
	 */
	static bool check(ngram_size_t n);
};

/** Functor, which wraps hashing function (NGramHashCounter::count_hash()).
 */
struct NGramHasher: public std::unary_function<size_t, const NGram *> {
	/** Hashing function.
	 *	@param key Pointer to NGram (instance) to be hashed.
	 *	@return Counted hash.
	 */
	inline size_t operator()(const NGram *key) const {
		return NGramHashCounter::count_hash(key);
	}
};

#ifdef _USE_HASHSET

#if defined(_MSC_VER)

/** Functor wrapping "less than" comparison function (for NGram instances).
 */
struct NGramLessComparator: public std::binary_function<bool, const NGram *, const NGram *> {
	/** Comparison function.
	 *	@return True, if 1st argument is lesser than 2nd argument.
	 */
	bool operator()(const NGram *lhs, const NGram *rhs) const;
};

/** We redeclare some parts of traits class for Dinkumware hash containers,
 *	so our own hashing function and comparator will be used.
 */
class NGramHashCompare: public stdext::hash_compare<const NGram *> {
	/** Hashing object (functor).
	 */
	static NGramHasher _hasher;
	/** Comparator object (functor).
	 */
	static NGramLessComparator _comparator;
public:
	/* Double sized than default.
	 */
	enum {
		bucket_size = 8,
		min_buckets = 16
	};
	/** Hashing function.
	 *	@param key Pointer to NGram (instance) to be hashed.
	 *	@return Counted hash.
	 */
	inline size_t operator()(const NGram *key) const {
		//
		return _hasher(key);
	}
	/** Comparison function.
	 *	@param lhs Pointer to 1st NGram.
	 *	@param rhs Pointer to 2nd NGram.
	 *	@return True, if 1st argument is lesser than 2nd argument.
	 */
	inline bool operator()(const NGram *lhs, const NGram *rhs) const {
		//
		return _comparator(lhs, rhs);
	}
};

#elif defined(__GNUC__)
/** Functor wrapping "equal to" comparison function (for NGram instances).
 */
struct NGramEqualComparator: public std::binary_function<bool, const NGram *, const NGram *> {
	/** "Equal to" comparison of two NGram instances.
	 *	@param lhs Pointer to 1st NGram.
	 *	@param rhs Pointer to 2nd NGram.
	 *	@return True, if 1st argument is equal to 2nd argument.
	 */
	bool operator()(const NGram *lhs, const NGram *rhs) const;
};

#endif

#endif // _USE_HASHSET

/** Class serves as NGram(s) store.
 *	There is separate memory pool and hash table for each NGram type.
 *	NGram data are stored within the pool, while pointer to NGram is stored
 *	within the hash table.
 */
class NGramStore {
public:
#ifdef _USE_HASHSET
	/** We use hash tables with our own hashing functions and comparators.
	 */
#if defined(_MSC_VER)
	typedef stdext::hash_set<NGram *, NGramHashCompare> hash_table_t;
#elif defined(__GNUC__)
	typedef __gnu_cxx::hash_set<NGram *, NGramHasher, NGramEqualComparator> hash_table_t;
#endif
#else
	typedef HashVector<NGram *, NGramHasher> hash_table_t;
#endif
	/** Only one zero-typed N-gram exists in whole universe (which is restrained by program scope of course).
	 */
	NGram zero_ngram;

private:
	/** Pair is returned as find() methods result.
	 *	The 1st value is const_iterator pointing to founded item (if founded -
	 *	otherwise its value cannot be consider as valid).
	 *	2nd value answers the question: was searched key founded?
	 */
	typedef std::pair<hash_table_t::const_iterator, bool> _hash_table_pair_cib_t;
	/** VoidPool serves as a data container for NGram instances.
	 *	For each N-gram type there is a separate pool, because of various memory sizes needed.
	 */
	std::vector<VoidPool> _memory_pools;
	/** Hash table is used to quickly gain pointer to stored NGram instance.
	 *	There is a separate hash table for each N-gram type, what
	 *	makes iteration through all instances of certain N-gram type very easy.
	 */
	std::vector<hash_table_t> _hash_tables;

	/** @param ngram Pointer to NGram instance which shall be looked after.
	 *	@return Lookup result (see return type description for more info).
	 */
	_hash_table_pair_cib_t _find(const NGram *ngram) const;

	/** No copy constructs.
	 */
	NGramStore(const NGramStore&);
	/** No assignments.
	 */
	NGramStore& operator=(const NGramStore&);
public:
	/** Pair returned as insert method result. The 1st value is pointer to the stored NGram
	 *	instance, 2nd value determines whether inserted item was added to store (true) or was not,
	 *	which means it has been already present.
	 */
	typedef std::pair<NGram *, bool> insert_status_t;

	/** Constructor initializes all underlying containers in case,
	 *	the passed types_count is non zero.
	 *	@param memory_pool_block_size Number of NGram(s) to be stored in every pool.
	 */
	NGramStore(size_t memory_pool_block_size = 0);
	
	// No need for special destructor - pools destructor properly clears memory they occupy.	 
	
	/** @param type N-gram type.
	 *	@return Iterator pointing to the beginning of store of given N-grams type.
	 */
	inline hash_table_t::const_iterator begin(ngram_size_t type) const { return _hash_tables[type].begin(); }
	/*	@return Iterator pointing to the beginning of store of full N-gram type.
	 */
	inline hash_table_t::const_iterator begin(void) const { return _hash_tables[NGram::full_ngram_type()].begin(); }
	/** @param type N-gram type.
	 *	@return Iterator pointing to the end of store of given N-grams type.
	 */
	inline hash_table_t::const_iterator end(ngram_size_t type) const { return _hash_tables[type].end(); }
	/*	@return Iterator pointing to the end of store of full N-gram type.
	 */
	inline hash_table_t::const_iterator end(void) const { return _hash_tables[NGram::full_ngram_type()].end(); }
	/** @return Pointer to the stored counterpart of passed NGram or NULL,
	 *		if no counterpart instance has been found within the store.
	 */
	const NGram * get(const NGram *ngram) const;
	/** Performs object initialization. Can be used in "post-init" manner also,
	 *	but only if object has been created by default constructor.
	 *	@param memory_pool_block_size Number of NGram(s) to be stored in every pool.
	 */
	void init(size_t memory_pool_block_size);
	/** @param ngram Pointer to NGram instance which should be inserted into store.
	 */
	insert_status_t insert(const NGram *ngram);
	/** @param type N-gram type.
	 *	@return Number of given type N-grams within the store.
	 */
	inline size_t size(ngram_type_t type) const { return (type == 0) ? 1 : _hash_tables[type].size(); }
	/**	@return Number of all full N-grams within the store.
	 */
	inline size_t size(void) const { return _hash_tables[NGram::full_ngram_type()].size(); }
#ifndef _USE_HASHSET
	/**
	 */
	void sort(ngram_type_t type = 0);
#endif
};

/** Container for frequency statistics.
 */
typedef std::vector<frequency_t> freq_table_t;

/** Struct holds table of all *-frequencies of certain N-gram. 
 */
struct NGramFrequencies {
	/** Pointer to N-gram.
	 */
	const NGram *ngram;
	/** Frequencies.
	 *	111 : ABC
	 *	110 : AB*
	 *	101 : A*C
	 *	100 : A**
	 *	...etc.
	 */
	freq_table_t frequencies;
	/** Constructor inits all data members,
	 *	creates frequency table of appropriate size.
	 */
	NGramFrequencies(void): ngram(NULL), frequencies(NGram::types_count()) {}
};

/** NGramsProcessor simplifies gathering of frequency stats of given N-gram
 *	(and all its downcasted types) from NGramStore container.
 */
class NGramsProcessor {
	/** Reference to NGramStore to be processed.
	 */
	const NGramStore& _ngram_store;
	/** Iterator to the next item to be processed.
	 */
	NGramStore::hash_table_t::const_iterator _next;
	/** Iterator to the end of store.
	 */
	NGramStore::hash_table_t::const_iterator _end;
	/** Recently gathered frequencies of certain N-gram.
	 */
	NGramFrequencies _ngram_frequencies;
public:
	/** Pass n-gram store to n-grams processor to retrieve all *-frequencies.
	 *	@param ngrams N-gram store.
	 */
	NGramsProcessor(NGramStore& ngrams): _ngram_store(ngrams), _next(ngrams.begin()), _end(ngrams.end()), _ngram_frequencies() {}

	/** Counts values of frequency table for next N-gram.
	 *	@return True, if there has been N-gram to process, otherwise return false.
	 */
	bool next(void);

	/** Frequencies object is returned by reference, so it stays valid till
	 *	the following next() call.
	 *	@return Last processed N-gram frequencies.
	 */
	inline const NGramFrequencies& ngram_frequencies(void) const { return _ngram_frequencies; }
};

} // namespace ace

#endif
