/** @file ntree.h
 *
 *	Declaration of indexed-trees processing module interface.
 *
 *	Indexed-tree (sometimes referred to as N-tree) is ordinary rooted trees that
 *	has its every node indexed with unique (in tree scope) unsigned number and
 *	the indices within one tree are compact (there are no "holes") and goes starts
 *	with 1.
 *
 *	Module is designed in purpose to extract indexed subtrees of given size
 *	from passed indexed tree (see extract_subtrees()).
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _NTREE_H
#define _NTREE_H

#include <map>
#include <set>
#include <vector>

namespace ace {

/** Type definition for tree size type used to store NTree indices.
 *	Must be one of the unsigned types!
 */
typedef size_t tree_size_t;
/** To represent subtrees (and resultant n-trees) vector is used.
 *	Subtree nodes are determined by indices stored within container,
 *	so all values shall be unique (but it's not necessary to have them
 *	sorted all the time).
 */
typedef std::vector<tree_size_t> subtree_t;
/** Childs of certain node are stored in set, because we want them sorted
 *	and there's no need for random access. They are determined in the same
 *	way as in subtree_t container (by indices stored within container).
 */
typedef std::set<tree_size_t> childs_t;
/** Mapped subtrees are subtrees with some extra special information - key.
 *	The key can stand for one of the following:
 *		1. Size of related subtree (use during extractor processing).
 *		2. Index of root node of related subtree (used in resultant set).
 *	Multimap is used mainly because of the former. Multimap makes possible
 *	to access subtrees of given size in O(log N) time, where N stands for
 *	number of all subtrees of certain node.
 */
typedef std::multimap<tree_size_t, subtree_t> mapped_subtrees_t;

/** Class holds information of single indexed-tree node. For description
 *	of indexed-tree see file commentary.
 *	Note that the zero index is used for special purposes - it determines
 *	that given node is so called abstract root. Real tree roots (or root)
 *	are then childs of this abstract root node.
 */
class NTreeNode {	
private:
	/** Index of given node (0 for abstract node).
	 */
	tree_size_t _index;
	/** Index of parent node (0 for root node).
	 */
	tree_size_t _parent;
	/** Indexes of childs of given node (order is significant).
	 */
	childs_t _childs;
public:
	/** Default constructor constructs abstract (root) node.
	 */
	NTreeNode(void): _index(0), _parent(0), _childs() {}
	/** It's required to know parent index when constructing node non-abstract node.
	 *	@param index Node index.
	 *	@param parent Index of parent node.
	 */
	NTreeNode(tree_size_t index, tree_size_t parent): _index(index), _parent(parent), _childs() {}
	/**
	 */
	void add_child(tree_size_t child_index) { _childs.insert(child_index); }
	/** @return Number of node childs.
	 */
	inline size_t count_childs(void) const throw() { return _childs.size(); }
	/** @return Reference to childs container.
	 */
	const childs_t& get_childs(void) const throw() { return _childs; }
	/** @return Node index.
	 */
	inline tree_size_t index(void) const throw() { return _index; }
	/** Node is abstract, if its index is 0. Only the root node should be abstract.
	 *	@return True, if node is abstract.
	 */
	inline bool is_abstract(void) const throw() { return _index == 0; }
	/** @return True, if node is leaf (has no childs).
	 */
	inline bool is_leaf(void) const throw() { return _childs.empty(); }
	/** @return True, if node is root (has no parent node = parent node index is 0).
	 */
	inline bool is_root(void) const throw() { return _parent == 0; }
	/** @return Index of parent node.
	 */
	inline tree_size_t parent(void) const throw() { return _parent; }
};

/** Comparison function for NTreeNode(s). Comparison is based on NTreeNode indices.
 *	@param lhs Left hand operand.
 *	@param rhs Right hand operand.
 *	@return True, if left NTreeNode is lesser than right NTreeNode.
 */
inline bool operator<(const NTreeNode& lhs, const NTreeNode& rhs) {
	return lhs.index() < rhs.index();
}

/** To represent indexed-tree the std::vector of NTreeNode instances is used.
 *	It's essential that vector is indexed in the same fashion as NTreeNode
 *	instances it contains, so NTreeNode instance at i-th position has to have
 *	its index equal to i. Therefore, the first NTreeNode in ntree_t (at 0-th
 *	position) shall be abstract root (see definition of NTreeNode class) and is
 *	considered that way by extract_subtrees() procedure).
 */
typedef std::vector<NTreeNode> ntree_t;

/** Extracts indexed subtrees of given size from passed indexed-tree. For
 *	definition of indexed-tree see header file comment. For definition
 *	of ntree_t see its typedef description, and do so for definition of
 *	mapped_subtrees_t too.
 *	@param nodes Reference to container of NTreeNode instances.
 *	@param subtree_size Determines size of extracted subtrees.
 *	@param results Reference to container capable of holding resulted subtrees.
 */
void extract_subtrees(ntree_t& nodes, tree_size_t subtree_size, mapped_subtrees_t& results);

} // namespace ace

#endif
