/***********************************************
 * # Copyright 2009-2010. Liu Yongchao
 * # Contact: Liu Yongchao, School of Computer Engineering,
 * #			 Nanyang Technological University.
 * # Emails:	 liuy0039@ntu.edu.sg; nkcslyc@hotmail.com
 * #
 * # GPL version 3.0 applies.
 * #
 * ************************************************/

#ifndef _MSA_GUIDE_TREE_H
#define _MSA_GUIDE_TREE_H
#include "MSADef.h"
#include "MSA.h"

#include "SafeVector.h"
#include "MultiSequence.h"
#include "ScoreType.h"
#include "ProbabilisticModel.h"
#include "SparseMatrix.h"

class MSA;
struct ValidNode {
	ValidNode* prev;
	ValidNode* next;
	int n;				//the index in the distance matrix			
	int node;			//the index in the tree node entries
};

struct TreeNode {
	struct TreeNode *left;			//the pointer to its left child
	struct TreeNode *right;			//the pointer to its right child
	struct TreeNode *parent;		//the pointer to its parent
	int leftIdx;					//the index of the left child
	int rightIdx;					//the index of the right child
	int parentIdx;					//the index of its parent
	int idx;						//the index of itself
	float dist;						//the distance to its parent
	int leaf;						//whether it is a leaf node or not
	int order;			//the number of generations dating back to its ancestor
	int depth;						//the depth of the node
};
struct AlignmentOrder {
	int nodeDepth;			//the depth of the internal node
	int leftOrder;			//the order number of the right child
	int rightOrder;			//the order number of the left child
	int* leftLeafs;			//the indices of leafs in the left subtree
	int leftNum;			//the number of leafs in the left subtree
	int* rightLeafs;			//the indices of leafs in the right subtree
	int rightNum;			//the number of leafs in the right substree
};

class MSAGuideTree {
public:
	MSAGuideTree(MSA* msa, VVF& distMatrix, int numSeqs);
	virtual ~MSAGuideTree() = 0;	//abstract class

	//get the tree nodes
	TreeNode* getNodes();
	//get the leaf nodes
	TreeNode* getLeafs();
	//get the number of nodes;
	int getNodesNum();
	//get the number of leaf nodes
	int getLeafsNum();
	//get the root of the tree
	TreeNode* getRoot() {
		return this->root;
	}
	//get the alignment orders
	AlignmentOrder* getAlignOrders();
	int getAlignOrdersNum();
	//construct the alignment orders
	void createAlignmentOrders();

	//construct the guide tree
	virtual void create();
	//calculate the sequence weights
	virtual void getSeqsWeights();

	/**********DEBUGING****************/
	//display the tree
	void displayTree();
	//display the alignment orders
	void displayAlignmentOrders();

protected:
	//join two nodes
	void connectNodes(TreeNode* parent, int parentIdx, TreeNode* leftChild,
			float leftDist, TreeNode* rightChild, float rightDist);
	//release the alignment orders vector
	void releaseAlignmentOrders();
	//recursive implemenation of constructing the alignment orders
	int recursiveCreateAlignmentOrders(TreeNode* subRoot, int* subLeafs,
			int& subLeafsNum, int nodeDepth);

	//system configurations
	MSA* msa;
	VVF* distMatrix;
	int numSeqs;
	int* seqsWeights;

	//all the tree nodes
	TreeNode* nodes;
	int nodesNum;
	int nodesSize;
	//the root tree node
	TreeNode* root;
	//leaf node
	TreeNode* leafs;
	int leafsNum;

	//alignment order
	AlignmentOrder* alignOrders;
	int alignOrdersNum;
	int alignOrdersSize;
};
#endif