#ifndef PHYCPP_TREE_NODE_HPP
#define PHYCPP_TREE_NODE_HPP

#include "edge.hpp"
#include "definitions.hpp"
#include "iterator.hpp"
#include "../utility/valuedobject.hpp"
#include "../utility/stringalgorithm.hpp"
#include <sstream>
#include <vector>

namespace PhyCpp {

template <typename TaxonT, typename NodeT, typename EdgeT>
class BasicTree;

template <typename TaxonT, typename NodeT, typename EdgeT>
class BasicNode;

template <typename TaxonT, typename NodeT, typename EdgeT>
class BasicNode : public ValuedObject<NodeT> {

	friend class BasicTree<TaxonT, NodeT, EdgeT>;
	friend class BasicEdge<TaxonT, NodeT, EdgeT>;
	template <typename, typename, typename, bool, bool> friend class BasicNodeIterator;

	BasicNode(BasicTree<TaxonT, NodeT, EdgeT> * tree, double length);

	struct IntNode {
		unsigned int i;
		BasicNode * n;
		inline bool operator < (const IntNode & other) const {return i < other.i;}
	};

public:

	typedef BasicEdge<TaxonT, NodeT, EdgeT> Edge;
	typedef BasicTree<TaxonT, NodeT, EdgeT> Tree;
	typedef BasicTaxon<TaxonT>              Taxon;
	typedef NodeT value_type;
	typedef BasicNode<TaxonT, NodeT, EdgeT> Node;

	typedef Detail::BasicTreeIterator<BasicNode, BasicNode, false, false> iterator;
	typedef Detail::BasicTreeIterator<BasicNode, BasicNode, true, false> const_iterator;
	typedef Detail::BasicTreeIterator<BasicNode, BasicNode, false, true> reverse_iterator;
	typedef Detail::BasicTreeIterator<BasicNode, BasicNode, true, true> const_reverse_iterator;

	/** @name Destruction */
	//@{
	~BasicNode();
	//@}

	/** @name Topology access */
	//@{
	inline BasicNode * parent() {return parentnode;}
	inline const BasicNode * parent() const {return parentnode;}

	inline Edge * parentEdge() {return parentedge;}
	inline const Edge * parentEdge() const {return parentedge;}

	inline BasicNode * rightSibling() {return rightsibling;}
	inline const BasicNode * rightSibling() const {return rightsibling;}

	BasicNode * leftSibling();
	const BasicNode * leftSibling() const;

	inline BasicNode * leftChild() {return leftchild;}
	inline const BasicNode * leftChild() const {return leftchild;}

	inline BasicNode * preorderNext() {return preordernext;}
	inline const BasicNode * preorderNext() const {return preordernext;}

	inline BasicNode * postorderNext() {return this->postordernext;}
	inline const BasicNode * postorderNext() const {return this->postordernext;}

	inline Tree * tree() {return tree_ptr;}
	inline const Tree * tree() const {return tree_ptr;}

	inline bool isTip() const {return (leftchild == 0);}
	inline bool isInternal() const {return leftchild != 0;}
	inline bool isRoot() const {return (tree_ptr->root() == this);}

	inline bool isPolytomy() const {return (leftchild != 0 && leftchild->rightsibling != 0 && leftchild->rightsibling->rightsibling != 0);}
	inline bool isDichotomy() const {return (leftchild != 0 && leftchild->rightsibling != 0 && leftchild->rightsibling->rightsibling == 0);}

	bool isDescendedFrom(const BasicNode * other);

	BasicNode * rightSubtreeExtent();
	BasicNode * subtreePreorderNext();

	inline std::string toString() const {return getNewickString() + ";";}
	//@}

	/** @name Topology modification */
	//@{
	BasicNode * appendChild(double edgeLength = -1);
	void collapseSubtree(bool accumulateBranchLengths = true);
	void ladderizeSubtree(HorizontalDirection direction);
	void resolvePolytomy(PolytomyResolutionMethod method);
	bool setParent(BasicNode * other, HorizontalDirection dir = Right, bool retainUnbranchedOldParent = false, bool retainUnbranchedNewParent = false, bool accumulateBranchLengths = true);
	bool swapSubtreeWith(BasicNode * subtreeRoot);
	//@}

	/** @name Taxonomy */
	//@{
	inline Taxon * taxon() {return tax;}
	inline const Taxon * taxon() const {return tax;}
	Taxon * setTaxon(Taxon * t);
	Taxon * setTaxon(const std::string & label);
	//@}

private:

	void reroot(BasicNode * previous);

	std::string getNewickString() const;

	void destroy();

	void recalculateTraversalOrder() {recalculateTraversalOrder(this);}
	void recalculateTraversalOrder(BasicNode * subtreeRoot);

	inline static void setPreorderRelation(BasicNode * from, BasicNode * to) {
		if ((from == 0 && to == 0) || (from != 0 && to != 0 && from->tree_ptr != to->tree_ptr))
			return;
		if (from != 0) {
			if (to != 0) {
				from->preordernext = to;
				to->postordernext = from;
			} else {
				setPreorderRelation(from, from->tree_ptr->endNode);
			}
		} else {
			setPreorderRelation(to->tree_ptr->startNode, to);
		}
	}

	BasicTree<TaxonT, NodeT, EdgeT> * tree_ptr;
	BasicNode * parentnode;
	BasicNode * leftchild;
	BasicNode * rightsibling;
	BasicNode * preordernext;
	BasicNode * postordernext;
	BasicEdge<TaxonT, NodeT, EdgeT> * parentedge;
	BasicTaxon<TaxonT> * tax;
};

} // namespace PhyCpp

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::BasicNode(BasicTree<TaxonT, NodeT, EdgeT> * tree, double length) :
	   ValuedObject<NodeT>(),
	   tree_ptr(tree),
	   parentnode(0),
	   leftchild(0),
	   rightsibling(0),
	   preordernext(0),
	   postordernext(0),
	   parentedge(new BasicEdge<TaxonT, NodeT, EdgeT>(this, length)),
	   tax(0) {
	++tree_ptr->node_count;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::~BasicNode() {
	tree_ptr->setTaxon(this, 0);
	--tree_ptr->node_count;
	delete parentedge;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
void PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::BasicNode::destroy() {
	if (leftchild != 0) {
		leftchild->destroy();
		BasicNode * n = leftchild->rightsibling;
		while (n) {
			n->destroy();
			BasicNode * z = n->rightsibling;
			n->leftchild = n->rightsibling = 0;
			delete n;
			n = 0;
			n = z;
		}
		delete leftchild;
		leftchild = 0;
	}
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicNode<TaxonT, NodeT, EdgeT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::leftSibling() {
	return const_cast<BasicNode*>(((const BasicNode*)this)->leftSibling());
}

template <typename TaxonT, typename NodeT, typename EdgeT>
const PhyCpp::BasicNode<TaxonT, NodeT, EdgeT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::leftSibling() const {
	if (parentnode == 0)
		return 0;
	const BasicNode * n = parentnode->leftchild;
	if (n == this) {
		return 0;
	}
	else {
		while (n->rightsibling != this)
			n = n->rightsibling;
		return n;
	}
}

template <typename TaxonT, typename NodeT, typename EdgeT>
std::string PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::getNewickString() const {

	std::string result;
	if (leftchild == 0) {
		if (tax != 0) {
			result = tax->label();
		}
		if (parentnode != 0 && parentedge->len >= 0) {
			result += ":";
			std::stringstream ss;
			ss << parentedge->len;
			result += ss.str();
		}
	} else {
		result = "(";
		bool started = false;
		const BasicNode * n = leftchild;
		while (n) {
			if (started)
			result += ",";
			else
			started = true;
			result += n->getNewickString();
			n = n->rightsibling;
		}
		result += ")";
		if (tax != 0) {
			result += tax->label();
		}
		if (parentedge != 0 && parentedge->len >= 0) {
			result += ":";
			std::stringstream ss;
			ss << parentedge->len;
			result += ss.str();
		}
	}
	return result;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicTaxon<TaxonT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::setTaxon(BasicTaxon<TaxonT> * t) {
	return tree_ptr->setTaxon(this, t);
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicTaxon<TaxonT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::setTaxon(const std::string & label) {
	return tree_ptr->setTaxon(this, label);
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicNode<TaxonT, NodeT, EdgeT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::appendChild(double edgeLength) {

	if (leftchild == 0) {
		leftchild = new BasicNode(tree_ptr, edgeLength);
		leftchild->parentnode = this;
		setPreorderRelation(this, leftchild);
		setPreorderRelation(leftchild, rightsibling);
		if (leftchild->preordernext == 0) {
			tree_ptr->endNode->postordernext = leftchild;
			leftchild->preordernext = tree_ptr->endNode;
		}
		return leftchild;
	} else {
		BasicNode * n = leftchild;
		while (n->rightsibling != 0)
			n = n->rightsibling;
		BasicNode * k = new BasicNode(tree_ptr, edgeLength);
		k->parentnode = this;
		k->preordernext = rightsibling;
		if (n->leftchild == 0) {
			setPreorderRelation(n, k);
		}
		else {
			BasicNode * z = n;
			while (z->leftchild != 0) {
				z = z->leftchild;
				while (z->rightsibling != 0)
					z = z->rightsibling;
			}
			setPreorderRelation(z, k);
		}
		n->rightsibling = k;
		if (k->preordernext == 0)
			setPreorderRelation(k, tree_ptr->endNode);
		return k;
	}
}

template <typename TaxonT, typename NodeT, typename EdgeT>
bool PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::isDescendedFrom(const BasicNode * other) {
	BasicNode * n = parentnode;
	while (n) {
		if (n == other)
			return true;
		n = n->parentnode;
	}
	return false;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
void PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::resolvePolytomy(PolytomyResolutionMethod method) {

	if (!isPolytomy())
		return;

	if (method == LadderizeLeft) {
		BasicNode * n = leftchild->rightsibling;
		while (n->rightsibling != 0) {
			BasicNode * newnode = leftchild->parentedge->insertNode(0.0);
			newnode->leftchild->rightsibling = n;
			setPreorderRelation(newnode->leftchild->rightSubtreeExtent(), n);
			newnode->rightsibling = n->rightsibling;
			n->rightsibling = 0;
			setPreorderRelation(n->rightSubtreeExtent(), n->subtreePreorderNext());
			n->parentnode = newnode;
			n = newnode->rightsibling;
		}
	}
}

template <typename TaxonT, typename NodeT, typename EdgeT>
void PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::reroot(BasicNode * previous) {

	if (previous != 0 && previous->parentnode == this) {
		double L = parentedge->length();
		parentedge->setLength(previous->parentedge->length());
		previous->parentedge->setLength(L);
		previous->parentedge->swapValuesWith(parentedge);
	}

	std::vector<BasicNode *> newChildren;

	if (previous == 0 || previous == parentnode) {
		BasicNode * n = leftchild;
		if (previous != parentnode && parentnode->leftchild != this)
			newChildren.push_back(parentnode);
		while (n) {
			newChildren.push_back(n);
			n = n->rightsibling;
		}
		if (previous != parentnode && parentnode->leftchild == this)
			newChildren.push_back(parentnode);
	} else {
		BasicNode * n = leftchild;
		while (n != previous)
			n = n->rightsibling;
		n = n->rightsibling;
		while (n) {
			newChildren.push_back(n);
			n = n->rightsibling;
		}
		if  (parentnode != 0)
		newChildren.push_back(parentnode);
		n = leftchild;
		while (n != previous) {
			newChildren.push_back(n);
			n = n->rightsibling;
		}
	}

	for (unsigned int i = 0; i < newChildren.size(); ++i)
		newChildren[i]->reroot(this);

	parentnode = previous;

	for (unsigned int i = 0; i < newChildren.size(); ++i) {
		if (i > 0)
			newChildren[i-1]->rightsibling = newChildren[i];
		if (i == newChildren.size()-1)
			newChildren[i]->rightsibling = 0;
	}

	leftchild = (newChildren.size() > 0) ? newChildren[0] : 0;

	if (parentnode == 0)
		rightsibling = 0;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicNode<TaxonT, NodeT, EdgeT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::rightSubtreeExtent() {
	BasicNode * n = this;
	while (n->leftchild != 0) {
		n = n->leftchild;
		while (n->rightsibling != 0)
			n = n->rightsibling;
	}
	return n;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
PhyCpp::BasicNode<TaxonT, NodeT, EdgeT> * PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::subtreePreorderNext() {
	BasicNode * j = this;
	while (j && j->rightsibling == 0)
		j = j->parentnode;
	if (j)
		j = j->rightsibling;
	return j;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
bool PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::setParent(BasicNode * node, HorizontalDirection dir, bool retainUnbranchedOldParent, bool retainUnbranchedNewParent, bool accumulateBranchLengths) {

	if (node == 0 || node == this || node->tree_ptr != tree_ptr || node->isDescendedFrom(this))
		return false;

	BasicNode * oldParent = parentnode;

	if (parentnode->leftchild == this) {
		parentnode->leftchild = rightsibling;
		setPreorderRelation(parentnode, rightsibling);
	}
	else {
		BasicNode * k = leftSibling();
		k->rightsibling = rightsibling;
		setPreorderRelation(k->rightSubtreeExtent(), rightsibling);
	}

	if (node->leftchild == 0) {
		node->leftchild = this;
		parentnode = node;
		setPreorderRelation(node, this);
		rightsibling = 0;
		setPreorderRelation(rightSubtreeExtent(), subtreePreorderNext());
	} else {
		if (dir == Right) {
			node = node->leftchild;
			while (node->rightsibling != 0)
				node = node->rightsibling;
			node->rightsibling = this;
			setPreorderRelation(node->rightSubtreeExtent(), this);
			parentnode = node->parentnode;
			rightsibling = 0;
			setPreorderRelation(rightSubtreeExtent(), subtreePreorderNext());
		} else if (dir == Left) {
			rightsibling = node->leftchild;
			setPreorderRelation(rightSubtreeExtent(), node->leftchild);
			node->leftchild = this;
			parentnode = node;
			setPreorderRelation(node, this);
		}
	}

	if (oldParent->leftchild == 0 || (oldParent->leftchild != 0 && oldParent->leftchild->rightsibling == 0))
		if (!retainUnbranchedOldParent)
			tree_ptr->removeNode(oldParent);
	if (parentnode->leftchild == 0 || (parentnode->leftchild != 0 && parentnode->leftchild->rightsibling == 0))
		if (!retainUnbranchedNewParent)
			tree_ptr->removeNode(parentnode);

	return true;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
void PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::collapseSubtree(bool accumulateBranchLengths) {

	std::vector<BasicNode*> terminalNodes;
	std::vector<BasicNode*> internalNodes;
	std::map<BasicNode*, double> lengths;
	lengths[this] = parentedge->length() < 0 ? -1 : 0;
	typename BasicNode::iterator it = tree_ptr->begin(this);
	typename BasicNode::iterator ite = tree_ptr->end(this);
	++it;
	while (it != ite) {

		if (accumulateBranchLengths) {
			double thisLen = it.node()->parentedge->length();
			double pLen = lengths[it.node()->parentnode];
			if (thisLen < 0 && pLen < 0)
				lengths[it.node()] = -1;
			else if (thisLen >= 0 && pLen >= 0)
				lengths[it.node()] = thisLen + pLen;
			else if (thisLen >= 0)
				lengths[it.node()] = thisLen;
			else
				lengths[it.node()] = pLen;
		}

		if (it.node()->leftchild == 0) {
			terminalNodes.push_back(it.node());
			it.node()->parentedge->setLength(lengths[it.node()]);
		} else {
			internalNodes.push_back(it.node());
		}
		++it;
	}
	for (unsigned int i = 0; i < internalNodes.size(); ++i) {
		internalNodes[i]->parentnode = internalNodes[i]->rightsibling = 0;
		delete internalNodes[i];
	}
	for (unsigned int i = 0; i < terminalNodes.size(); ++i) {
		terminalNodes[i]->parentnode = this;
		if (i == 0) {
			leftchild = terminalNodes[i];
			setPreorderRelation(this, terminalNodes[i]);
		}
		else {
			terminalNodes[i-1]->rightsibling = terminalNodes[i];
			setPreorderRelation(terminalNodes[i-1], terminalNodes[i]);
		}
	}
}

template <typename TaxonT, typename NodeT, typename EdgeT>
void PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::recalculateTraversalOrder(BasicNode * subtreeRoot) {

	if (parentnode == 0)
		setPreorderRelation(0, this);
	int counter = (this == subtreeRoot);
	if (leftchild != 0) {
		setPreorderRelation(this, leftchild);
		leftchild->recalculateTraversalOrder(subtreeRoot);
	} else if (rightsibling != 0) {
		setPreorderRelation(this, rightsibling);
		rightsibling->recalculateTraversalOrder(subtreeRoot);
	} else {
		BasicNode * n = parentnode;
		counter += (n == subtreeRoot);
		while (n != 0) {
			if (n->rightsibling != 0)
				break;
			n = n->parentnode;
			counter += (n == subtreeRoot);
		}
		if (n != 0 && n->rightsibling != 0) {
			n = n->rightsibling;
			setPreorderRelation(this, n);
			if (counter == 0)
				n->recalculateTraversalOrder(subtreeRoot);
		} else {
			setPreorderRelation(this, 0);
		}
	}
}

template <typename TaxonT, typename NodeT, typename EdgeT>
bool PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::swapSubtreeWith(BasicNode * subtreeRoot2) {

	if (subtreeRoot2->tree_ptr != tree_ptr || this == subtreeRoot2 || this->isDescendedFrom(subtreeRoot2) || subtreeRoot2->isDescendedFrom(this))
		return false;

	BasicNode * n1 = this;
	while (n1->leftchild != 0) {
		n1 = n1->leftchild;
		while (n1->rightsibling != 0)
			n1 = n1->rightsibling;
	}
	BasicNode * n2 =  subtreeRoot2;
	while (n2->leftchild != 0) {
		n2 = n2->leftchild;
		while (n2->rightsibling != 0)
			n2 = n2->rightsibling;
	}

	BasicNode * parent1 = parentnode;
	BasicNode * parent2 = subtreeRoot2->parentnode;
	BasicNode * leftsib1 = leftSibling();
	BasicNode * leftsib2 = subtreeRoot2->leftSibling();
	BasicNode * rightsib1 = rightsibling;
	BasicNode * rightsib2 = subtreeRoot2->rightsibling;

	parentnode = parent2;
	subtreeRoot2->parentnode = parent1;
	bool change1 = (parent2->leftchild == subtreeRoot2);
	bool change2 = (parent1->leftchild == this);
	if (change1) {
		parent2->leftchild = this;
		setPreorderRelation(parent2, this);
	}
	if (change2) {
		parent1->leftchild = subtreeRoot2;
		setPreorderRelation(parent1, subtreeRoot2);
	}

	if (leftsib1 != 0 && leftsib1 != subtreeRoot2) {
		leftsib1->rightsibling = subtreeRoot2;
		BasicNode * b = leftsib1;
		while (b->leftchild != 0) {
			b = b->leftchild;
			while (b->rightsibling != 0)
				b = b->rightsibling;
		}
		setPreorderRelation(b, subtreeRoot2);
	}
	if (leftsib2 != 0 && leftsib2 != this) {
		leftsib2->rightsibling = this;
		BasicNode * b = leftsib2;
		while (b->leftchild != 0) {
			b = b->leftchild;
			while (b->rightsibling != 0)
				b = b->rightsibling;
		}
		setPreorderRelation(b, this);
	}

	if (rightsib2 != this) {
		this->rightsibling = rightsib2;
		if (rightsib2 != 0) {
			setPreorderRelation(n1, rightsib2);
		} else {
			BasicNode * k = this;
			while (k != 0 && k->rightsibling == 0)
				k = k->parentnode;
			if (k != 0)
				k = k->rightsibling;
			setPreorderRelation(n1, k);
		}
	} else  {
		this->rightsibling = subtreeRoot2;
		if (subtreeRoot2 != 0) {
			setPreorderRelation(n1, subtreeRoot2);
		} else {
			BasicNode * k = this;
			while (k != 0 && k->rightsibling == 0)
				k = k->parentnode;
			if (k != 0)
				k = k->rightsibling;
			setPreorderRelation(n1, k);
		}
	}

	if (rightsib1 != subtreeRoot2) {
		subtreeRoot2->rightsibling = rightsib1;
		if (rightsib1 != 0) {
			setPreorderRelation(n2, rightsib1);
		} else  {
			BasicNode * k = subtreeRoot2;
			while (k != 0 && k->rightsibling == 0)
				k = k->parentnode;
			if (k != 0)
				k = k->rightsibling;
			setPreorderRelation(n2, k);
		}
	} else {
		subtreeRoot2->rightsibling = this;
		if (this != 0) {
			setPreorderRelation(n2, this);
		} else {
			BasicNode * k = subtreeRoot2;
			while (k != 0 && k->rightsibling == 0)
				k = k->parentnode;
			if (k != 0)
				k = k->rightsibling;
			setPreorderRelation(n2, k);
		}
	}

	return true;
}

template <typename TaxonT, typename NodeT, typename EdgeT>
void PhyCpp::BasicNode<TaxonT, NodeT, EdgeT>::ladderizeSubtree(HorizontalDirection direction) {

	std::map<BasicNode*, unsigned int> tipCounts;
	typename BasicNode::reverse_iterator rit = tree_ptr->rbegin(this);
	typename BasicNode::reverse_iterator rite = tree_ptr->rend(this);
	while (rit != rite) {
		unsigned int count = 0;
		BasicNode * n = rit.node()->leftchild;
		while (n != 0) {
			count += 1;
			count += tipCounts[n];
			n = n->rightsibling;
		}
		tipCounts[rit.node()] = count;
		++rit;
	}

	typename BasicNode::iterator it = tree_ptr->begin(this);
	typename BasicNode::iterator ite = tree_ptr->end(this);
	while (it != ite) {
		std::vector<IntNode> intNodes;
		BasicNode * n = it.node()->leftchild;
		while (n != 0) {
			IntNode in;
			in.n = n;
			in.i = tipCounts[n];
			intNodes.push_back(in);
			n = n->rightsibling;
		}
		if (intNodes.size() > 0) {
			if (direction == Left)
				std::stable_sort(intNodes.begin(), intNodes.end());
			else
				std::stable_sort(intNodes.rbegin(), intNodes.rend());
			BasicNode * n = it.node()->leftchild;
			for (unsigned int i = 0; i < intNodes.size(); ++i) {
				if (n == intNodes[i].n) {
					n = n->rightsibling;
				} else {
					n->swapSubtreeWith(intNodes[i].n);
					n = intNodes[i].n->rightsibling;
				}
			}
		}
		++it;
	}
}

#endif // PHYCPP_TREE_NODE_HPP
