/** @file ntree.cpp
 *
 *	Definition (implementation) of indexed-trees processing module interface.
 *
 *	See ntree.h for more info about the interface.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>

// Self header.
#include "ntree.h"
// Sum decompositions.
#include "utils.h"

#ifdef _DEPENDENCY_MODE

namespace ace {

/** Vector is used as subtrees container.
 */
typedef std::vector<subtree_t> subtrees_container_t;
/** Sometimes we need container for container of subtrees :)
 */
typedef std::vector<subtrees_container_t> subtrees_to_merge_t;

/**
 */
subtrees_to_merge_t::size_type _product(subtrees_to_merge_t::size_type product_so_far, const subtrees_container_t& subtrees) {
	return product_so_far * subtrees.size();
}
	
/**
 *	@param subtrees_by_root_node Vectors of subtrees to join (passed in outer vector).
 *		Subtrees within one vector cannot be merged together (they are subtrees of the same root node).
 *	@param results Store place for created subtrees.
 */
void _join_subtrees(const subtrees_to_merge_t& subtrees_by_root_node, subtrees_container_t& results) {
	if ( subtrees_by_root_node.empty() ) {
		return;
	}
	
	// The number of results is product of multiplication of counts of various nodes subtrees.
	size_t results_count = std::accumulate(subtrees_by_root_node.begin(), subtrees_by_root_node.end(), 1, _product);
	results.reserve(results_count);

	// Iterate through vectors of subtrees and create desired subtrees.
	for ( size_t i = 0; i < subtrees_by_root_node.size(); ++i ) { // Loop through different nodes.
		for ( size_t j = 0; j < subtrees_by_root_node[i].size(); ++j ) { // Loop through subtrees of given node.
			// Loop as many times as needed. The more subtrees of given node,
			// the less loops performed (every subtree will be combined with the same number
			// of subtrees of different nodes.
			size_t loop = results_count/subtrees_by_root_node[i].size();
			for ( size_t k = 0; k < loop; ++k ) {
				if ( i == 0 ) {
					// First outer loop, init resulting subtree with copy of j-th subtree of first node.
					results.push_back(subtrees_by_root_node[i][j]);
				} else {
					// Not first outer loop (subtree of later than first node), insert into existing subtree.
					results[j*loop + k].insert(results[j*loop + k].end(), subtrees_by_root_node[i][j].begin(), subtrees_by_root_node[i][j].end());
				}
			}
		}
	}
}


/*	Interface item implementation - for info see description in header file.
 */
void extract_subtrees(ntree_t& nodes, tree_size_t subtree_size, mapped_subtrees_t& results) {

	if ( nodes.size() <= subtree_size ) {
		// Number of nodes is lesser than required subtree size.
		// Note: `nodes` container have one item more than is the nodes count.
		return;
	}
	
	// Utility object which precounts decomposition of all `sums` from 1 up to N
	// with use of M addends.
	// We used this decompositions to iterate through all posibilities how to construct
	// subtree of size N as composition of M smaller subtrees.
	// We are interested only in subtrees of maximum size `subtree_size`, so we only
	// want to get `subtree_size`-1 subtree nodes from childs of certain node.
	static SumDecompositions sum_decompositions(subtree_size-1, subtree_size*2);
	
	// Process queue - every node has to be processed once. The queue is initialized
	// with leaf nodes and order of processing of the rest of nodes is determined by
	// tree structure.
	std::queue<tree_size_t> process_queue;

	/** Store of subtrees of processed nodes. It's continously filled during the processing of nodes queue.
	 *	I-th item contains subtrees of i-th node (if the node has been already processed).
	 */
	std::vector<mapped_subtrees_t> subtrees(nodes.size());
	/** Counters of processed childs for every node. The node cannot be add to the process queue
	 *	until all its childs are processed.
	 */
	std::vector<tree_size_t> childs_processed(nodes.size());
	
	// Step 0: Init the process queue with leaf nodes.
	// The 0-th node (abstract root) can be safely ignored.
	for ( tree_size_t i = 1; i < nodes.size(); ++i ) {
		if ( nodes[i].is_leaf() ) {
			// Add node to the process queue.
			process_queue.push(nodes[i].index());
		}
	}

	// Step 1: Cycle processing the queue.
	while ( !process_queue.empty() ) {
		// Current node.
		NTreeNode& current = nodes[process_queue.front()];
		// Parent node.
		NTreeNode& parent = nodes[current.parent()];
		
		// Every node is at least root of subtree of size one (containing only
		// the node itself), so...
		subtree_t new_one; // Create.
		new_one.push_back(current.index()); // Fill with current.
		// Subtrees are indexed by root nodes indices and the size of subtree is the map key.
		subtrees[current.index()].insert(mapped_subtrees_t::value_type(new_one.size(), new_one)); // Store.
		
		// Leaf or not leaf?:)
		if ( !current.is_leaf() ) {
			// Current node has some childs, process them (find all subtrees).

			// Few temporary containers...
			// There will be at most `subtree_size` subtrees_to_merge.
			subtrees_to_merge_t subtrees_to_merge;
			subtrees_to_merge.reserve(subtree_size);
			// Prepare container for results.
			subtrees_container_t merge_results;
			// 
			subtrees_container_t node_subtrees;
			
			for ( tree_size_t n = 2; n <= subtree_size; ++n ) {
				// Sum to get from childs.
				tree_size_t sum = n - 1;

				// Get decompositions of `sum` into `count_childs` addends
				const sum_decompositions_t *sd = sum_decompositions.get_decompositions_table(sum, current.count_childs());
				
				// Process them.
				for ( size_t i = 0; i < sd->size(); ++i ) { // Loop through every decomposition.
					size_t j = 0;
					for ( childs_t::const_iterator i_child = current.get_childs().begin(); i_child != current.get_childs().end(); ++i_child, ++j) { // Loop through every child node.
						if ( (*sd)[i][j] == 0 ) {
							// There is no such thing like subtree with zero nodes, so go to next.
							continue;
						}
						// Get all of subtrees of required size.
						std::pair<mapped_subtrees_t::const_iterator, mapped_subtrees_t::const_iterator> range = subtrees[*i_child].equal_range((*sd)[i][j]);
						// Copy them into `node_subtrees`.
						std::transform(range.first, range.second, std::back_inserter(node_subtrees), select2nd<mapped_subtrees_t::value_type>());
						//
						subtrees_to_merge.push_back(node_subtrees);
						// Clear for use in next loop.
						node_subtrees.clear();
					}
					// Join subtrees.
					_join_subtrees(subtrees_to_merge, merge_results);
					// Clear for use in next loop.
					subtrees_to_merge.clear();
					// Store the results as subtrees of current node,
					// don't forget to insert current node as well!
					// Also check, if there are any subtrees of size N!
					// If so, store them in results.
					for ( size_t n = 0; n < merge_results.size(); ++n ) {
						// Insert current node as well!
						merge_results[n].push_back(current.index());
						subtrees[current.index()].insert(mapped_subtrees_t::value_type(merge_results[n].size(), merge_results[n]));
						// Any subtree of desired size?
						if ( merge_results[n].size() == subtree_size ) {
							// Sort the subtree before copying it to results container!
							std::sort(merge_results[n].begin(), merge_results[n].end());
							results.insert(mapped_subtrees_t::value_type(current.index(), merge_results[n]));
						}
					}
					// Clear results for use in next loop.
					merge_results.clear();
				}
			}
		}

		// Node has been processed, so:
		// 1. Pop him from the queue.
		process_queue.pop();
		// 2. Increment processed childs counter of parent node.
		++(childs_processed[parent.index()]);

		if ( !parent.is_abstract() && (parent.count_childs() == childs_processed[parent.index()]) ) {
			// Parent node is not the abstract root node and all its childs have been already processed.
			process_queue.push(parent.index());
		}
		
	}

}

} // namespace ace

#endif // _DEPENDENCY_MODE
