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

#include <algorithm>
#include <utility>
#include <vector>

// Buffer interface.
#include "buffer.h"
// Basic typedefs.
#include "config.h"
// Self header.
#include "extractor.h"
// NGrams.
#include "ngram.h"
// Progress display.
#include "notifier.h"
#ifdef _DEPENDENCY_MODE
// N-trees extraction.
#include "ntree.h"
#endif
// Parsing.
#include "parser.h"
// Global stores.
#include "persistent.h"
// ith_bit() needed.
#include "utils.h"
// Word store and range types.
#include "word.h"

namespace ace {

#ifdef _DEPENDENCY_MODE
/** Builds a ntree based on grammar dependency tree of given sentence. Each
 *	word in sentence must have unique order no!
 *	@param sentence Reference to pair of iterators pointing to the first and
 *		behind the last word of sentence.
 *	@param nodes Reference to container of nodes which plays the tree role.
 */
void _build_tree(const words_range_t& sentence, ntree_t& nodes) {	

	words_range_t::first_type word = sentence.first;

	// Init with nodes.
	while ( word != sentence.second ) {
		nodes.push_back(NTreeNode(word->order(), word->parent()));
		++word;
	}

	// Add childs to nodes.	
	for ( word_order_t i = 1; i < nodes.size(); ++i ) {
		nodes[nodes[i].parent()].add_child(i);
	}
}


/** Extracts raw N-gram related to passed subtree.
 *	@param sentence_start Iterator pointing to the beginning of the sentence.
 *	@param subtree Subtree of size N extracted from sentence dependency tree.
 *	@param raw_ngram Reference to container for extracted (raw N-gram).
 *	@return Iterator pointing to the word, which is head of extracted N-gram.
 */
words_store_t::const_iterator _extract_ngram(words_store_t::const_iterator sentence_start, const subtree_t& subtree, raw_ngram_t& raw_ngram) {
	//
	words_store_t::const_iterator word, head;

	// 1. Loop through subtree members, store raw N-gram data
	for ( subtree_t::const_iterator i_subtree = subtree.begin(); i_subtree != subtree.end(); ++i_subtree ) {
		// Word coresponding to current member.
		word = sentence_start + *i_subtree - 1; // -1 => indices within subtree_t goes from 1, not 0.
		// Find position of word parent node in `subtree` - we need to know its (new) index in n-gram tree.
		std::pair<subtree_t::const_iterator, subtree_t::const_iterator> i_parent = std::equal_range(subtree.begin(), subtree.end(), word->parent());
		if ( i_parent.first == i_parent.second ) {
			// The only node whom parent isn't in subtree, is root (head) node of n-gram.
			// Store ngram member - use 0 to indicate root member.
			raw_ngram.push_back(raw_ngram_t::value_type(0, word));
			// Store the iterator to N-gram head for output.
			head = word;
		} else {
			// Store ngram member - count its new parent index on the base of subtree form.
			raw_ngram.push_back(raw_ngram_t::value_type(static_cast<ngram_size_t>(i_parent.second - subtree.begin()), word));
		}
	}

	return head;
}
#endif // _DEPENDENCY_MODE

/** Stores instance of given N-gram. If morphologic filter is on, the N-gram
 *	must pass the filter.
 *	@param raw_ngram Raw N-gram intance to be stored.
 *	@param type N-gram type to be stored.
 *	@return Pointer to related N-gram instance within the global N-gram store
 *		or NULL, if N-gram hasn't been stored (didn't make it through filter).
 */
NGram * _store_ngram(const raw_ngram_t& raw_ngram, ngram_type_t type) {		

	// Apply morphologic filter, if on.	
	// Note: 0 typed N-gram will always pass, so don't waste your time with types like him.
	if ( persistent::morphologic_filter.is_on() && (type != 0) ) {
		// Once initialized, stays of the same size (only contents changes)
		static multirule_t tags(NGram::n());
		static std::string empty;				
		
		ngram_type_t i = NGram::n() - 1;
		
		// Raw N-gram contains all N members, but the N-gram type specifies which members are realy significant.
		for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem, --i) {
#ifdef _DEPENDENCY_MODE
			tags[i] = ith_bit(type, i) ? persistent::tags.get(i_mem->second->tag()) : empty;
#else
			tags[i] = ith_bit(type, i) ? persistent::tags.get((*i_mem)->tag()) : empty;
#endif
		}
		// Count filter stats for full N-grams only.
		if ( !persistent::morphologic_filter.match(tags, type == NGram::full_ngram_type()) ) {
			return NULL;
		}
	}

	// Construct NGram by specially crafted static method, insert and...
	NGramStore::insert_status_t pb = persistent::ngrams.insert(NGramToken::get(raw_ngram, type));
	// ...check insertion status.
	if ( !pb.second ) {
		// N-gram already present in the store, so increment its counter.
		pb.first->inc();
	}
	// Return pointer to stored instance.
	return pb.first;
}

/** Stores wide context for given N-gram.
 *	@param ngram Pointer to ngram instance.
 *	@param raw_ngram Related raw N-gram object.
 *	@param context_range Valid context range to be processed.
 */
void _store_wide_context(NGram *ngram, const raw_ngram_t& raw_ngram, words_range_t context_range) {
	// 
	size_t found_so_far = 0;
	// Loop through the given range and store the words within, but don't store the N-gram members itself.
	for ( words_store_t::const_iterator w = context_range.first; w != context_range.second; ++w ) {
next_loop:
		if ( found_so_far < raw_ngram.size() ) {
			// Not all members founded yet.
			ngram_type_t i = NGram::n(); // Should start on n-1, but gets "predecremented" every loop.
			for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem ) {
				// Check, if current N-gram type contains this word.
				if ( ith_bit(ngram->type(), --i) ) {
					// Don't store the members themself.
#ifdef _DEPENDENCY_MODE
					// raw_ngram_member_t is a pair and we are interested in second value.
					if ( w == i_mem->second ) {
#else
					// raw_ngram_member_t is another name for words_store_t::const_iterator.
					if ( w == *i_mem ) {
#endif
						++found_so_far; // One more member founded.
						++w; // Go to next word - required, because of:
						if ( w != context_range.second ) {
							goto next_loop;
						} else {
							goto end;
						}
					}
				}
				// Else not a member (discarded by *).
			}
		}
		
		if ( persistent::context_filter.is_on()
				&& !persistent::context_filter.match(persistent::tags.get(w->tag()), false) ) {
			// Don't store the words that doesn't pass the context filter.
			continue;
		}

		ngram->add_to_context(PartOfContext(w->lemma(), w->tag()));
	}
end:
	;
}

/** Stores all *-types for given raw N-gram and updates related file stats
 *	counter. Also stores N-gram context, if needed.
 *	@param raw_ngram Reference to const raw N-gram to be stored.
 *	@param buffer Reference to underlying buffer.
 *	@param stats Reference to related file stats (to be updated).
 */
#ifdef _DEPENDENCY_MODE
void _store_raw_ngram(const raw_ngram_t& raw_ngram, const Buffer& buffer, NamedDataFileStats& stats, words_store_t::const_iterator head)
#else
void _store_raw_ngram(const raw_ngram_t& raw_ngram, const Buffer& buffer, NamedDataFileStats& stats)
#endif
{
	NGram * ngram = NULL;
	// Store the raw N-gram as NGram instances of all kinds.
	for ( ngram_type_t type = 0; type <= NGram::full_ngram_type(); ++type ) {

		// Store the N-gram (function performs morphologic check, if required).
		ngram = _store_ngram(raw_ngram, type);

		if ( type == NGram::full_ngram_type() ) {
			// Update datafile stats (count only full N-grams).
			++stats.ngrams.extracted;
			if ( ngram == NULL ) {
				++stats.ngrams.filtered;
			} else {
				++stats.ngrams.passed;
			}
		}
		
		if ( (ngram != NULL) && settings::context_tracing_on() ) {
			// Store context.
			if ( (type != 0) ) {
				// Zero-typed N-grams are contextless and so are the "I didn't make it through filter" N-grams :)
				if ( settings::context_window.mode == ContextWindow::SENTENCE_MODE ) {
					_store_wide_context(ngram, raw_ngram, buffer.context_range());
				} else {
#ifdef _DEPENDENCY_MODE
					_store_wide_context(ngram, raw_ngram, buffer.context_range(head));
#else
					_store_wide_context(ngram, raw_ngram, buffer.context_range(raw_ngram.front(), raw_ngram.back()));
#endif
				}
			}
			
			if ( type == NGram::full_ngram_type() ) {
				// Full N-grams need their narrow context to be traced.
				// Front and back members of current N-gram.
#ifdef _DEPENDENCY_MODE
				words_store_t::const_iterator front = raw_ngram.front().second, back = raw_ngram.back().second;
#else
				words_store_t::const_iterator front = raw_ngram.front(), back = raw_ngram.back();
#endif
				if ( front != buffer.current().first ) {
					ngram->add_to_context(PartOfContext((front - 1)->lemma(), (front - 1)->tag(), true));
				}
				if ( (back + 1) != buffer.current().second ) { // current().second is already pointing behind!
					ngram->add_to_context(PartOfContext((back + 1)->lemma(), (back + 1)->tag(), true));
				}
			}
		}
	}
}

/*	Interface item implementation - for info see description in header file.
 */
size_t extract(std::ifstream& input_file, NamedDataFileStats& stats) {
		
	// Count file length.
	input_file.seekg(0, std::ios::end);
	std::streampos pos = input_file.tellg();
	input_file.seekg(0, std::ios::beg);

	size_t file_size = (pos < 0) ? static_cast<std::streampos>(0) : pos;

#ifdef _BOOST_ON
	//// Progress display ////

	bool progress_bar_on = true;
	
	// Progress display. If tellg failed, show 0 sized progress bar.
	progress_display_t display(static_cast<unsigned long>(file_size), notifier::progress.output_stream(), "");
	
	if ( pos < 0 ) {
		notifier::error.warning("Progress bar initialization failed! Going on without progress bar display...");
		progress_bar_on = false;
	}
	// 
	size_t processed_so_far = 0;
#endif

	//// Processing variables initialization ////

	// Extracted N-gram (raw).
	raw_ngram_t raw_ngram;

#ifdef _DEPENDENCY_MODE
	// Vector for NTreeNodes.
	ntree_t nodes;
	NTreeNode abstract_root_node = NTreeNode();
	nodes.push_back(abstract_root_node);

	// Extracted subtrees.
	mapped_subtrees_t subtrees;
#else
	static bools_table_t decomps = bools_table(settings::n - 1, settings::collocation_window_size);
	//
	words_range_t sentence;
	words_store_t::const_iterator word, current_word;
	// Resize raw N-gram (stores items with default constructor).
	raw_ngram.resize(settings::n);
#endif

	//// Modules initialization ////	

	// Parser for current file.
	Parser parser(input_file);
	Buffer buffer(parser, settings::context_window);

	//// Processing ////
	
	if ( buffer.empty() ) {
		// Buffer initialization failed, probably file is corrupted.
		return 0;
	}
	
	do {
#ifdef _DEPENDENCY_MODE
		// 1. Build grammar dependency tree from sentence.
		_build_tree(buffer.current(), nodes);

		// 2. Pass the tree to ntree subtree extractor coupled with size of subtrees (which is N)
		extract_subtrees(nodes, NGram::n(), subtrees);

		// 3. Loop through extracted subtrees.
		for ( mapped_subtrees_t::const_iterator i_subtree = subtrees.begin(); i_subtree != subtrees.end(); ++i_subtree ) {		
			// Get related N-gram (as raw).
			words_store_t::const_iterator head = _extract_ngram(buffer.current().first, i_subtree->second, raw_ngram);
			// Store N-gram (also stores context, if needed).
			_store_raw_ngram(raw_ngram, buffer, stats, head);
			// Clear N-gram container for next loop.
			raw_ngram.clear();
		}			
#else
		// Get whole sentence.
		sentence = buffer.current();
		if ( (sentence.second - sentence.first) < settings::n ) {
			// Sentence is too short, go to next one.
			continue;
		}
		current_word = sentence.first;
		do {			
			size_t rn = 0;
			raw_ngram[rn] = current_word;

			// Extract raw N-grams.
			for ( size_t i = 0; i < decomps.size(); ++i ) {
				// !
				rn = 0;
				// Loop through tables.
				size_t stop_at = std::min(decomps[i].size(), static_cast<size_t>((sentence.second - current_word) - 1));
				// We want to stop before range end!
				for ( size_t j = 0; j < stop_at; ++j ) {
					// For every i: decomps[i].size() == collocation_window_size !
					// Loop through each table.
					if ( decomps[i][j] ) {
						// Add (j+1)-th item after current word.
						raw_ngram[++rn] = current_word + j + 1; // j is zero indexed!
					}
				}
				// If all N members are freshly included (may be not true, if sentence end is near).
				if ( ++rn == settings::n ) {
					// Also stores context, if needed.
					_store_raw_ngram(raw_ngram, buffer, stats);
				}
			}

			++current_word;

		// Stop when there is less than N words between current word (inclusive) and end of sentence.
		} while ( current_word <= (sentence.second - settings::n) );

#endif
#ifdef _BOOST_ON
		// 4. Progress bar update (set, if it's possible to retrieve current pointer position within the ifstream)
		if ( progress_bar_on ) {
			if ( parser.eof() ) {
				// Ok, we're done. Let progress bar reach its end.s
				display += display.expected_count() - display.count();
				// And leave.
				break;
			}
			pos = input_file.tellg();
			if ( (pos < 0) ) {
				// Current pointer position within the stream cannot be retrieved!
				notifier::progress.info("\n"); // Finish progress bar display.
				notifier::error.warning("Progress bar update failed! Stopping progress bar display..."); // Warn.
				progress_bar_on = false;
			} else {
				// Ok, update progress bar (add only as much as have been processed since last update)
				display += static_cast<unsigned long>(static_cast<size_t>(pos) - processed_so_far);
				processed_so_far = static_cast<size_t>(pos);
			}
		}
#endif
#ifdef _DEPENDENCY_MODE
		// 5. Get prepared for the next loop.
		// Keep only root node, drop anything else.
		nodes.resize(1);
		nodes[0] = abstract_root_node; // Re-assignment clears the child nodes of abstract tree node.
		// Clear containers for the next loop.
		subtrees.clear();
#endif
	// Advance buffer to the next sentence.
	} while ( buffer.next() );

	// Add buffer file statistics (words, sentences parsed) to extractor statistics (N-grams extracted).
	stats += buffer.stats();

	return file_size;
	
}

} // namespace ace
