/** @file ngram.h
 *
 *	Interface declaration of structure for N-gram representation.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _NGRAM_H
#define _NGRAM_H

// We use pair here.
#include <utility>
#include <vector>

#include "config.h"
// N-gram context.
#include "context.h"
#ifdef _DEPENDENCY_MODE
// dependency::head needed.
#include "dependencies.h"
#endif
// Frequence counter overflow treatment.
#include "overflow.h"
// ith_bit(), bits_in()
#include "utils.h"
// Word(s) are processed here.
#include "word.h"

namespace ace {

#ifdef _SURFACE_MODE
/** This typedef is defined for compability with _DEPENDENCY_MODE version
 *	of program.
 */
typedef words_store_t::const_iterator raw_ngram_member_t;
#else
/** Typedef for pair of values for each raw N-gram member:
 *	1. index of parent node in extracted N-gram (0 if root)
 *	2. iterator to the corresponding word instance
 */
typedef std::pair<ngram_size_t, words_store_t::const_iterator> raw_ngram_member_t;
#endif
/** Raw N-gram is just collection of owned members.
 */
typedef std::vector<raw_ngram_member_t> raw_ngram_t;

// Forward declaration (class is declared as friend).
class NGramToken;

/** Frequency counter datatype definition. We should keep in mind, that value
 *	of ngram_type_t type is stored within most significant bits of frequency
 *	counter, so its datatype should be big enough.
 */
typedef unsigned int freq_counter_t;

/** Frequency datatype definition. It differs from freq_counter_t - frequency_t
 *	is frequency output (result) datatype (it's a type stored in overflow
 *	counters map and used for statistics evaluations). Despite this it may be
 *	the same type as freq_counter_t.
 */
typedef size_t frequency_t;

#if defined(_MSC_VER) || defined(__GNUC__)
// Save default pack value.
#pragma pack(push)
// Pack following structure data on 2 bytes boundary.
#pragma pack(1)
#endif

/** Class designed to keep single NGram data.
 *	Each NGram has its type and frequency counter (stored in same place by
 *	using union). It has also from 0 to N members, but their are not stored
 *	within NGram (more precisely they are stored just behind him). Access
 *	to NGram members is provided by incrementing `this` pointer and casting
 *	him to pointer to NGram::Member.
 *	The precise number of members of certain NGram is determined by NGram type.
 */
class NGram {
public:
	/** Single N-gram member representation.
	 *	Just stores some data, does nothing special.
	 */
	class Member {
		/** Lemma (index) and morphologic tag (index) altogether.
		 */
		TaggedLemma _tagged_lemma;
#ifdef _DEPENDENCY_MODE
		/** Parent member index.
		 */
		ngram_size_t _parent;
		/** Dependency type (index).
		 */
		dependency_index_t _dependency;
	public:
		/** Member constructor does the most common construction,
		 *	just assigns params to their counterparts.
		 *	@param lemma Lemma (index).
		 *	@param tag Morphologic tag (index).
		 *	@param parent Parent word index.
		 *	@param dependency Dependency type (index).
		 */
		Member(string_index_t lemma, tag_index_t tag, ngram_size_t parent, dependency_index_t dependency): _tagged_lemma(lemma, tag), _parent(parent), _dependency(dependency) {}
		/** @return Parent word index.
		 */
		inline ngram_size_t parent(void) const { return _parent; }
		/** @return Dependency type (index).
		 */
		inline dependency_index_t dependency(void) const { return _dependency; }
#else
	public:
		/** Member constructor does the most common construction,
		 *	just assigns params to their counterparts.
		 *	@param lemma Lemma (index).
		 *	@param tag Morphologic tag (index).
		 */
		Member(string_index_t lemma, tag_index_t tag): _tagged_lemma(lemma, tag) {}
#endif
		/** @return Lemma (index).
		 */
		inline string_index_t lemma(void) const { return _tagged_lemma.lemma(); }
		/** @return Morphologic tag (index).
		 */
		inline tag_index_t tag(void) const { return _tagged_lemma.tag(); }
	};
private:
	/** Type definition of Overflow container used with NGram instances.
	 */
	typedef Overflow<const NGram *, frequency_t> _overflows_map_t;

	/// Constant statics first.

	/** Max allowed frequency. Acts also as a mask for frequency retrieving.
	 */
	static const freq_counter_t _max_frequency;
	/** Mask of overflow flag bit.
	 */
	static const ngram_type_t _overflow_flag_mask;
	/** Index of last bit(s) within the frequency-type union (its the index of
	 *	last item in the array).
	 */
	static const size_t _last_bit_index;
	/** Mask of type bit(s).
	 */	
	static const ngram_type_t _type_mask;

	/// N-dependent and other non-const statics then.

	/** Do we run in contextless or contextfull mode?
	 */
	static bool _context_tracing_on;		
	/** Full N-gram type value.
	 */
	static ngram_type_t _full_ngram_type;
	/** Conversion table: N-gram type -> members count.
	 */
	static std::vector<ngram_size_t>  _members_count;
	/** Conversion table: N-gram degree -> required memory size.
	 */
	static std::vector<size_t> _ngrams_memory_sizes;
	/** Mapping of overflows.
	 */
	static _overflows_map_t _overflows;
	/** Number of N-grams types (is equal to 2 to power of N).
	 */
	static ngram_type_t _types_count;

	/// Private data.

	/** Item holds data for frequency, type and overflow flag altogether.
	 *	The data are distributed as follows:
	 *	(MSB) |O|TTTTTTT|F..................F| (LSB)
	 *	O - oveflow flag bit (MSB).
	 *	TTTTTTT - type (7) bits.
	 *	F...F - frequency bits (all remaining part).
	 *	To retrieve appropriate data bitmasks are used.
	 */
	union {
		/** NGram frequency.
		 */
		freq_counter_t _frequency;
		/** The least item in array is used for storage of NGram type and
		 *	its MSB is used for overflow mask bit.
		 *	Note: We expect little-endian ordering!
		 */
		ngram_type_t _frequency_bits[sizeof(freq_counter_t)/sizeof(ngram_type_t)];
	};
	/// Private (forbidden) operators. 

	/* No assignments are allowed - method body must stay undefined.
	 */
	NGram& operator=(const NGram& source);

	/// Private methods.

	/** @return True, if NGram frequency counter overflowen.
	 */
	inline bool _overflow(void) const { return (_frequency_bits[_last_bit_index] & _overflow_flag_mask) != 0; }
	/** Sets given type as NGram type.
	 *	Note: we expect only 0 bytes in place of type bits (so OR can be used for new type assignment).
	 *	@param ngram_type New NGram type.
	 */
	void _type(ngram_type_t ngram_type);
public:
	/** Initialize all static members which depends on precise value of N.
	 */
	static void init(void);

	/** Default constructor constructs zero typed N-gram and sets frequency counter to 0
	 *	and no context store. Due its simplicity is declared as public, there's no difference
	 *	between context-free and contexted zero typed N-grams.
	 */
	NGram(void): _frequency(0) {}
	/** Raw N-gram constructor. Contructs N-gram of given type. Sets frequency counter to 1.
	 *	@param raw_ngram Source raw N-gram.
	 *	@param ngram_type Type of N-gram to be created (determines which members of `raw_ngram` are copied).
	 */
	NGram(const raw_ngram_t& raw_ngram, ngram_type_t ngram_type);
	/** Copy construction of NGrams is allowed.
	 *	@param source NGram to be copied.
	 */
	NGram(const NGram& source);
	/** "Down-cast" copy-constructor. Frequency is copied from source.
	 *	@param source N-gram (fully typed) which should be downcasted.
	 *	@param ngram_type Type of N-gram to be created (determines which members of `source` are copied).
	 */
	NGram(const NGram& source, ngram_type_t ngram_type);

	/** @return Number of members (degree) of N-gram.
	 */
	inline ngram_size_t degree() const { return _members_count[type()]; }
	/** @return Full N-gram type.
	 */
	static ngram_type_t full_ngram_type(void) { return _full_ngram_type; }
	/** @return True, if N-gram is zero-typed.
	 */
	inline bool is_zero(void) const { return type() == 0; }
	/** @return The N number.
	 */
	static ngram_size_t n(void) { return settings::n; }
	/** @return Size of occupied memory by given N-gram type.
	 */
	static size_t size_of(ngram_size_t degree) { return _ngrams_memory_sizes[degree]; }
	/** @return Size of occupied memory by N-gram.
	 */
	inline size_t size_of(void) const { return _ngrams_memory_sizes[degree()]; }
	/** @return N-gram type.
	 */
	inline ngram_type_t type(void) const { return _frequency_bits[_last_bit_index] & _type_mask; }
	/** @return Number of all N-gram types (which is N to power of 2).
	 */
	static ngram_type_t types_count(void) { return _types_count; }

	/** @return Pointer to the instance of first N-gram Member.
	 */
	inline Member * begin(void) { return static_cast<Member *>(static_cast<void *>(this + 1)); }
	/** @return Pointer to the const instance of first N-gram Member.
	 */
	inline const Member * begin(void) const { return static_cast<const Member *>(static_cast<const void *>(this + 1)); }
	/** @return Pointer to the memory behind the last N-gram Member.
	 */
	inline Member * end(void) { return this->begin() + degree(); }
	/** @return Pointer to the const memory behind the last N-gram Member.
	 */
	inline const Member * end(void) const { return this->begin() + degree(); }
	/** @return Pointer to the index-th instance of N-gram Member(s).
	 */
	inline Member * get(ngram_size_t index) { return this->begin() + index; }
	/** @return Pointer to the index-th const instance of N-gram Member(s).
	 */
	inline const Member * get(ngram_size_t index) const { return this->begin() + index; }
	/** @return N-gram frequency.
	 */
	frequency_t frequency(void) const {
		// A + B may oveflow, so special treatment is needed.
		// A - stored (already) partly-overflowen counter value.
		// B - actual counter value.
		return _overflows_map_t::add_to_maximum((_overflow() ? _overflows.get(this) : 0), (_frequency & _max_frequency));
	}
	/** Increments frequency counter by 1.
	 */
	void inc(void);
	/** @param i Member index (which goes from 0 to N-1).
	 *	@return Lemma (index) of i-th N-gram Member.
	 */
	inline string_index_t lemma(ngram_size_t i) const { return this->get(i)->lemma(); }
	/** @param i Member index (which goes from 0 to N-1).
	 *	@return Morphologic tag (index) of i-th N-gram Member.
	 */
	inline tag_index_t tag(ngram_size_t i) const { return this->get(i)->tag(); }
#ifdef _DEPENDENCY_MODE
	/** @param i Member index (which goes from 0 to N-1).
	 *	@return Parent member index of i-th N-gram Member.
	 */
	inline ngram_size_t parent(ngram_size_t i) const { return this->get(i)->parent(); }
	/** @param i Member index (which goes from 0 to N-1).
	 *	@return Dependency (index) of i-th N-gram Member.
	 */
	inline dependency_index_t dependency(ngram_size_t i) const { return this->get(i)->dependency(); }
#endif
	// Context related stuff.

	/** Adds given part_of_context to N-gram context.
	 *	@param part_of_context To be added to the N-gram context.
	 */
	void add_to_context(const PartOfContext& part_of_context);
	/**	@return Pointer to the context container.
	 */
	inline context_t * context(void) {
		return static_cast<context_t *>(static_cast<void *>(this->end()));
	}
	/** @return Pointer to the constant context container.
	 */
	inline const context_t * context(void) const {
		return static_cast<const context_t *>(static_cast<const void *>(this->end()));
	}

	/** NGramToken can access our private stuff.
	 */
	friend class NGramToken;
};

/** Equal to operator for NGrams.
 *	@param lhs Left hand argument.
 *	@param rhs Right hand argument.
 *	@return True, if both NGrams are equal.
 */
bool operator==(const NGram& lhs, const NGram& rhs);
/** Less than operator for NGrams.
 *	@param lhs Left hand argument.
 *	@param rhs Right hand argument.
 *	@return True, if first NGram is lesser than second one.
 */
bool operator<(const NGram& lhs, const NGram& rhs);


#if defined(_MSC_VER) || defined(__GNUC__)
// Restore default pack value.
#pragma pack(pop)
#endif

/** Class purpose is to offer creation of temporary NGram instance to be used
 *	as a key value (token) when searching in NGramStore hashtables.
 *	Note: This class is not thread-safe!
 */
class NGramToken {
	/** Space to keep NGrams instances.
	 *	For efficiency purposes declared as static.
	 */
	static void *_ngram_space;
public:
	/** Performs class start-up initialization.
	 *	Must be called earlier than any of get() methods.
	 */
	static void init(void);
	/**	@param raw_ngram Source raw N-gram.
	 *	@param ngram_type Type of N-gram to be created (determines which members of `raw_ngram` are copied).
	 *	@return Pointer to temporary NGram instance constructed on the basis of given params.
	 */
	static NGram * get(const raw_ngram_t& raw_ngram, ngram_type_t ngram_type);
	/**	@param source Pointer to source N-gram (full type) which should be downcasted.
	 *	@param ngram_type Type of N-gram to be created (determines which members of `source` are copied).
	 *	@return Pointer to temporary NGram instance downcast constructed on the basis of given params.
	 */
	static NGram * get(const NGram *source, ngram_type_t ngram_type);
};

} // namespace ace

#endif
