/** \file
 * \brief Declaration and implementation of the class PQNode.
 *
 * This file contains the header for the class template PQNode. The
 * class template PQNode is used as an abstract base class for all
 * nodes in a PQ-tree. The derived classes are a class template for
 * Q- and P-nodes internalNodes (PQInternalNode) and a class template
 * PQLeaf for the leaves of the tree.
 *
 * \author Sebastian Leipert
 *
 * \par License:
 * This file is part of the Open Graph Drawing Framework (OGDF).
 *
 * \par
 * Copyright (C)<br>
 * See README.md in the OGDF root directory for details.
 *
 * \par
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * Version 2 or 3 as published by the Free Software Foundation;
 * see the file LICENSE.txt included in the packaging of this file
 * for details.
 *
 * \par
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * \par
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, see
 * http://www.gnu.org/copyleft/gpl.html
 */

#pragma once

#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/pqtree/PQNodeRoot.h>

namespace ogdf {

template<class T, class X, class Y>
class PQInternalKey;
template<class T, class X, class Y>
class PQLeafKey;
template<class T, class X, class Y>
class PQNodeKey;
template<class T, class X, class Y>
class PQTree;

template<class T, class X, class Y>
class PQNode : public PQNodeRoot {
	/**
	 * All members and member function of PQNode are needed
	 * by the class template PQTree. Therefore the class PQTree
	 * was made friendof PQNode, since this prevents the use of a large
	 * amount of extra public functions.
	 */
	friend class PQTree<T, X, Y>;

public:
	/**
	 * The (first) constructor combines the node with its information and
	 * will automatically set the PQBasicKey::m_nodePointer (see basicKey) of
	 * the element of type PQNodeKey.
	 */
	PQNode(int count, PQNodeKey<T, X, Y>* infoPtr);


	/**
	 * The (second) constructor is called,
	 * if no information is available or neccessary.
	 */
	explicit PQNode(int count);

	/**
	 * The destructor does not delete any accompanying information class as PQLeafKey,
	 * PQNodeKey and PQInternalKey.	This has been avoided, since applications may
	 * need the existence of these information classes after the corresponding node
	 * has been	deleted. If the deletion of an accompanying information class should
	 * be performed with the deletion of a node, either derive a new class
	 * with an appropriate destructor, or make use of the function
	 * CleanNode() of the class template PQTree.
	 */
	virtual ~PQNode() {
		delete fullChildren;
		delete partialChildren;
	}

	/**
	 * The function changeEndmost() replaces the old endmost child \p oldEnd
	 * of the node by a new child \p newEnd.
	 * If the node is a Q-node, then it must have two valid
	 * pointers to its endmost children. If one of the endmost children is
	 * \p oldEnd, it is replaced by \p newEnd.
	 * The function changeEndmost() returns 1 if it succeeded in
	 * replacing \p oldEnd by \p newEnd. Otherwise the function returns
	 * 0, leaving with an error message.
	 */
	bool changeEndmost(PQNode<T, X, Y>* oldEnd, PQNode<T, X, Y>* newEnd);

	/**
	 * The function changeSiblings() replaces the old sibling \p oldSib of the
	 * node by a new sibling \p newSib.
	 * If the node has \p oldSib as sibling, then it changes the
	 * sibling pointer that references to \p oldSib and places \p newSib
	 * at its position.
	 * The function changeSiblings() returns 1 if it succeeded in
	 * replacing \p oldSib by \p newSib. Otherwise the function returns
	 * 0, leaving with an error message.
	 */
	bool changeSiblings(PQNode<T, X, Y>* oldSib, PQNode<T, X, Y>* newSib);

	/**
	 * The function endmostChild() checks if a node is endmost child of
	 * a Q-node. This is 1 if one of the sibling pointers #m_sibLeft
	 * or #m_sibRight is 0. If the node is endmost child of a Q-node,
	 * then it has a valid parent pointer.
	 */
	bool endmostChild() const { return m_sibLeft == nullptr || m_sibRight == nullptr; }

	/**
	 * Returns one of the endmost children of node, if node is a Q-node.
	 * The function getEndmost() accepts as input a pointer to a
	 * PQNode stored in \p other. The returned endmost child is unequal
	 * to the one specified in \p other.  In case that an arbitrary endmost child
	 * should be looked up, set \p other = 0. This makes the function
	 * getEndmost() return an arbitrary endmost child (it returns the
	 * left endmost child).
	 */
	PQNode<T, X, Y>* getEndmost(PQNode<T, X, Y>* other) const {
		if (m_leftEndmost != other) {
			return m_leftEndmost;
		} else if (m_rightEndmost != other) {
			return m_rightEndmost;
		}

		return nullptr;
	}

	/**
	 * Returns one of the endmost children of node, if node is a Q-node.
	 * The function accepts an integer denoting a direction causing the
	 * function to return either the left or the endmost child.
	 */
	PQNode<T, X, Y>* getEndmost(SibDirection side) const {
		if (side == SibDirection::Left || side == SibDirection::NoDir) {
			return m_leftEndmost;
		} else if (side == SibDirection::Right) {
			return m_rightEndmost;
		}

		return nullptr;
	}

	//! Returns the identification number of a node.
	PQNodeKey<T, X, Y>* getNodeInfo() const { return m_pointerToInfo; }

	/**
	 * The function getSib() returns one of the siblings of the node.
	 * It accepts an integer denoting a dircetion causing the
	 * function to return either the left or the right sibling.
	 */
	PQNode<T, X, Y>* getSib(SibDirection side) const {
		if (side == SibDirection::Left) {
			return m_sibLeft;
		} else if (side == SibDirection::Right) {
			return m_sibRight;
		}

		return nullptr;
	}

	/**
	 * The function getNextSib() returns one of the siblings of the node.
	 * The function getNextSib() accepts as input a pointer to a
	 * PQNode stored in \p other. The returned sibling is unequal to the
	 * one specified in \p other. In case
	 * that no sibling has been looked up before, set \p other = 0.
	 * This makes the function getNextSib() return an arbitrary sibling
	 * (it returns the left sibling).
	 */
	PQNode<T, X, Y>* getNextSib(PQNode<T, X, Y>* other) const {
		if (m_sibLeft != other) {
			return m_sibLeft;
		} else if (m_sibRight != other) {
			return m_sibRight;
		}

		return nullptr;
	}

	//! Returns the identification number of a node.
	int identificationNumber() const { return m_identificationNumber; }

	//! Returns the number of children of a node.
	int childCount() const { return m_childCount; }

	//! Sets the number of children of a node.
	void childCount(int count) { m_childCount = count; }

	/**
	 * The function parent() returns a pointer to the parent of a node.
	 *
	 * \warning After reducing the PQ-tree, some nodes may not have
	 * valid parent pointers anymore. This is no fault, the datastructur
	 * was designed this way. See also Booth and Lueker.
	 */
	PQNode<T, X, Y>* parent() const { return m_parent; }

	/**
	 * Sets the parent pointer of a node. This function
	 * is needed in more ellaborated algorithms implemented as derivation of
	 * the class template PQTree. Here, the parent pointer probably is
	 * always needed and therefore has to be set within special functions,
	 * used in a pre-run before applying the bubble Phase of the PQTree.
	 */
	PQNode<T, X, Y>* parent(PQNode<T, X, Y>* newParent) { return m_parent = newParent; }

	//! Returns the type of the parent of a node.
	PQNodeType parentType() const { return m_parentType; }

	/**
	 * Sets the type of the parent of a node.
	 * This does not change the type of the parent!
	 */
	void parentType(PQNodeType newParentType) { m_parentType = newParentType; }

	//! Returs the number of pertinent children of a node.
	int pertChildCount() const { return m_pertChildCount; }

	//! Sets the number of pertinent children of a node.
	void pertChildCount(int count) { m_pertChildCount = count; }

	/**
	 * The default function putSibling()
	 * stores a new sibling at a free sibling pointer
	 * of the node. This is only possible, if the node has at most one sibling.
	 * The function then detects a non used sibling pointer and places \p newSib
	 * onto it. putSibling() returns 0 if there have been two siblings
	 * detected, occupying the two possible pointers. In this case the new sibling
	 * \p newSib cannot be stored. If there was at a maximum one sibling stored,
	 * the function will place \p newSib on the free pointer and return either
	 * \a LEFT or \a RIGHT, depending wich pointer has been used.
	 *
	 * This function will always scan the pointer to the left brother first.
	 */
	SibDirection putSibling(PQNode<T, X, Y>* newSib) {
		if (m_sibLeft == nullptr) {
			m_sibLeft = newSib;
			return SibDirection::Left;
		}

		OGDF_ASSERT(m_sibRight == nullptr);
		m_sibRight = newSib;
		return SibDirection::Right;
	}

	/**
	 * The function putSibling()
	 * with preference stores a new sibling at a free sibling pointer
	 * of the node. This is only possible, if the node has at most one sibling.
	 * The function then detects a non used sibling pointer and places \p newSib
	 * onto it. putSibling() returns 0 if there have been two siblings
	 * detected, occupying the two possible pointers. In this case the new sibling
	 * \p newSib could not be stored. If there was at a maximum one sibling
	 * stored, the function will place \p newSib on the free pointer and
	 * return either \a LEFT or \a RIGHT, depending wich pointer has been used.
	 *
	 * This function scans the brother first, which has been specified in the
	 * preference. If the preference has value \a LEFT, it scans the pointer
	 * to the left brother first. If the value is \a RIGHT, it scans the pointer
	 * to the right brother first.
	 */
	SibDirection putSibling(PQNode<T, X, Y>* newSib, SibDirection preference) {
		if (preference == SibDirection::Left) {
			return putSibling(newSib);
		}

		OGDF_ASSERT(preference == SibDirection::Right);

		if (m_sibRight == nullptr) {
			m_sibRight = newSib;
			return SibDirection::Right;
		}

		OGDF_ASSERT(m_sibLeft == nullptr);
		m_sibLeft = newSib;
		return SibDirection::Left;
	}

	//! Returns a pointer to the reference child if node is a P-node.
	PQNode<T, X, Y>* referenceChild() const { return m_referenceChild; }

	//! Returns the pointer to the parent if node is a reference child.
	PQNode<T, X, Y>* referenceParent() const { return m_referenceParent; }

	//! Sets the pointer #m_pointerToInfo to the specified adress of \p pointerToInfo.
	bool setNodeInfo(PQNodeKey<T, X, Y>* pointerToInfo) {
		m_pointerToInfo = pointerToInfo;
		if (pointerToInfo != nullptr) {
			m_pointerToInfo->setNodePointer(this);
			return true;
		}

		return false;
	}

	/**
	 * getKey() returns a pointer to the PQLeafKeyof a node, in case that
	 * the node is supposed to have a key, such as elements of the derived
	 * class template PQLeaf.
	 * The key contains information and is of type PQLeafKey.
	 */
	virtual PQLeafKey<T, X, Y>* getKey() const = 0;

	//! Sets a specified pointer variable in a derived class to the	specified adress of \p pointerToKey that is of type PQLeafKey.
	/**
	 * If a derived class, such as PQInternalNode, is not supposed to store
	 * informations of type PQLeafKey, setKey() ignores the informations as long as
	 * \p pointerToKey = 0. The return value then is 1.
	 * In case that \p pointerToKey != 0, the return value is 0.
	 *
	 * If a derived class, such as PQLeaf is supposed to
	 * store informations of type PQLeafKey, \p pointerToKey
	 * has to be instantiated by the client. The function setKey() does
	 * not instantiate the corresponding variable in the derived class.
	 * The return value is always 1 unless \p pointerKey was equal to 0.
	 */
	virtual bool setKey(PQLeafKey<T, X, Y>* pointerToKey) = 0;

	/**
	 * getInternal() returns a pointer to the PQInternalKey
	 * information of a node, in case that
	 * the node is supposed to have PQInternalKey information,
	 * such as elements of the derived class template PQInternalNode.
	 * The internal information is of type PQInternalKey.
	 */
	virtual PQInternalKey<T, X, Y>* getInternal() const = 0;

	/*
	 * setInternal() sets a specified pointer variable in a derived class
	 * to the specified adress of \p pointerToInternal that is of type
	 * PQInternalKey.
	 *
	 * If a derived class, such as PQLeaf,
	 * is not supposed to store informations of type PQInternalKey,
	 * setInternal() ignores the informations as long as
	 * \p pointerToInternal = 0. The return value then is 1.
	 * In case that \p pointerToInternal != 0, the return value is 0.
	 *
	 * If a derived class, such as PQInternalNode is
	 * supposed to store informations of type PQInternalKey,
	 * \p pointerToInternal has to be instantiated by the client. The
	 * function setInternal() does
	 * not instantiate the corresponding variable in the derived class.
	 * The return value is always 1 unless \p pointerInternal was
	 * equal to 0.
	 */
	virtual bool setInternal(PQInternalKey<T, X, Y>* pointerToInternal) = 0;

	/**
	 * mark() returns the variable PQLeaf::m_mark in the
	 * derived class PQLeaf and PQInternalNode.
	 * In a derived class this function has to return the designation used in
	 * the first pass of Booth and Luekers algorithm called Bubble(). A
	 * node then is either marked \a BLOCKED, \a UNBLOCKED or \a QUEUED (see PQNode).
	 */
	virtual PQNodeMark mark() const = 0;

	//! mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.
	virtual void mark(PQNodeMark) = 0;

	//! Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.
	/**
	 * Its objective is to manage
	 * status of a node in the PQ-tree. A status is
	 * any kind of information of the current situation in the frontier of
	 * a node (the frontier of a node are all descendant leaves of the
	 * node). A status is anything such as \a EMPTY, \a FULL or
	 * \a PARTIAL (see PQNode). Since there might be more than those three possibilities,
	 * (e.g. in computing planar subgraphs this
	 * function probably has to be overloaded by the client.
	 */
	virtual PQNodeStatus status() const = 0;

	//! Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.
	virtual void status(PQNodeStatus) = 0;

	//! Returns the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode.
	/**
	 * Its objective it to manage the type of a node.
	 * node the current node is. The type of a node in the class template
	 * PQTree is either PNode, QNode or \a leaf (see PQNode).
	 * There may be of course more types such as <em>sequence indicators</em>.
	 *
	 * Observe that the derived class template PQLeaf does
	 * not have a variable PQInternalNode::m_type, since it obviously is of type	\p leaf.
	 */
	virtual PQNodeType type() const = 0;

	//! Sets the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode.
	virtual void type(PQNodeType) = 0;


protected:
	// Stores the number of children of the node.
	int m_childCount;

	/**
	 * Needed for debuging
	 * purposes. The PQ-trees can be visualized with the help of the <em>Tree
	 * Interface</em> and the #m_debugTreeNumber is needed to print out the
	 * tree in the correct file format.
	 */
	int m_debugTreeNumber;

	/**
	 * Each node that has been introduced once into
	 * the tree gets a unique number. If the node is removed from the
	 * tree during a reduction or with the help of one of the functions
	 * that is provided by the class template PQtree, its number <b>is not reused</b>.
	 * This always allows exact identification of nodes
	 * during any process that is envoked on the PQ-tree. We strongly
	 * recommend users who construct the tree with the help of the
	 * construction functions and who instantiate the nodes by them selves
	 * to do the same.
	 */
	int m_identificationNumber;

	//! Stores the type of the parent which can be either a P- or Q-node.
	PQNodeType m_parentType;

	//! Stores the number of pertinent children of the node.
	int m_pertChildCount;

	//! Stores the number of pertinent leaves in the frontier of the node.
	int m_pertLeafCount;

	//! Stores a pointer to the first full child of a Q-node.
	PQNode<T, X, Y>* m_firstFull;

	PQNode<T, X, Y>* m_leftEndmost;

	/**
	 * Is a pointer to the parent. Observe that this
	 * pointer may not be up to date after a few applications of the
	 * reduction.
	 */
	PQNode<T, X, Y>* m_parent;

	/**
	 * Stores a pointer to one child, the <b>reference child</b> of the
	 * doubly linked cirkular list of children of a
	 * P-node. With the help of this pointer, it is possible to access
	 * the children of the P-node
	 */
	PQNode<T, X, Y>* m_referenceChild;

	/**
	 * Is a pointer to the parent, in case that the
	 * parent is a P-node and the node itself is its reference child.
	 * The pointer is needed in order to identify the reference child
	 * among all children of a P-node.
	 */
	PQNode<T, X, Y>* m_referenceParent;

	//! Stores the right endmost child of a Q-node.
	PQNode<T, X, Y>* m_rightEndmost;

	/**
	 * Stores a pointer ot the left sibling of PQNode.
	 * If PQNode is child of a Q-node and has no left sibling,
	 * #m_sibLeft is set to 0. If PQNode is child of a P-node,
	 * all children of the P-node are linked in a circular list. In the
	 * latter case, #m_sibLeft is never 0.
	 */
	PQNode<T, X, Y>* m_sibLeft;

	/**
	 * Stores a pointer ot the right sibling of PQNode.
	 * If PQNode is child of a Q-node and has no right sibling,
	 * #m_sibRight is set to 0. If PQNode is child of a P-node,
	 * all children of the P-node are linked in a circular list. In the
	 * latter case, #m_sibRight is never 0.
	 */
	PQNode<T, X, Y>* m_sibRight;

	//! Stores a pointer to the corresponding information of the node.
	PQNodeKey<T, X, Y>* m_pointerToInfo;


	//! Stores all full children of a node during a reduction.
	List<PQNode<T, X, Y>*>* fullChildren;

	//! Stores all partial children of a node during a reduction.
	List<PQNode<T, X, Y>*>* partialChildren;
};

/*
The function [[changeEndmost]] replaces the old endmost child [[oldEnd]] of
the node by a new child [[newEnd]].
If the node is a $Q$-node, then it must have two valid
pointers to its endmost children. If one of the endmost children is [[oldEnd]],
it is replaced by [[newEnd]].
The function [[changeEndmost]] returns [[1]] if it succeeded in
replacing [[oldEnd]] by [[newEnd]]. Otherwise the function returns
[[0]], leaving with an error message.
*/
template<class T, class X, class Y>
bool PQNode<T, X, Y>::changeEndmost(PQNode<T, X, Y>* oldEnd, PQNode<T, X, Y>* newEnd) {
	if (m_leftEndmost == oldEnd) {
		m_leftEndmost = newEnd;
		return true;
	} else if (m_rightEndmost == oldEnd) {
		m_rightEndmost = newEnd;
		return true;
	}
	return false;
}

/*
The function [[changeSiblings]] replaces the old sibling [[oldSib]] of the
node by a new sibling [[newSib]].

If the node has [[oldSib]] as sibling, then it changes the
sibling pointer that references to [[oldSib]] and places [[newSib]]
at its position.

The function [[changeSiblings]] returns [[1]] if it succeeded in replacing
[[oldSib]] by [[newSib]]. Otherwise the function returns
[[0]], leaving with an error message.
*/
template<class T, class X, class Y>
bool PQNode<T, X, Y>::changeSiblings(PQNode<T, X, Y>* oldSib, PQNode<T, X, Y>* newSib) {
	if (m_sibLeft == oldSib) {
		m_sibLeft = newSib;
		return true;
	} else if (m_sibRight == oldSib) {
		m_sibRight = newSib;
		return true;
	}
	return false;
}

/*
The (first) constructor combines the node with its information and
will automatically set the [[m_nodePointer]] (see \ref{basicKey}) of
the element of type [[PQNodeKey]] (see \ref{PQNodeKey}).
*/
template<class T, class X, class Y>
PQNode<T, X, Y>::PQNode(int count, PQNodeKey<T, X, Y>* infoPtr) {
	m_identificationNumber = count;
	m_childCount = 0;
	m_pertChildCount = 0;
	m_pertLeafCount = 0;
	m_debugTreeNumber = 0;
	m_parentType = PQNodeType::Undefined;

	m_parent = nullptr;
	m_firstFull = nullptr;
	m_sibLeft = nullptr;
	m_sibRight = nullptr;
	m_referenceChild = nullptr;
	m_referenceParent = nullptr;
	m_leftEndmost = nullptr;
	m_rightEndmost = nullptr;

	fullChildren = new List<PQNode<T, X, Y>*>;
	partialChildren = new List<PQNode<T, X, Y>*>;

	m_pointerToInfo = infoPtr;
	infoPtr->setNodePointer(this);
}

/*
The (second) constructor is called,
if no information is available or neccessary.
*/
template<class T, class X, class Y>
PQNode<T, X, Y>::PQNode(int count) {
	m_identificationNumber = count;
	m_childCount = 0;
	m_pertChildCount = 0;
	m_pertLeafCount = 0;
	m_debugTreeNumber = 0;
	m_parentType = PQNodeType::Undefined;

	m_parent = nullptr;
	m_firstFull = nullptr;
	m_sibLeft = nullptr;
	m_sibRight = nullptr;
	m_referenceChild = nullptr;
	m_referenceParent = nullptr;
	m_leftEndmost = nullptr;
	m_rightEndmost = nullptr;

	fullChildren = new List<PQNode<T, X, Y>*>;
	partialChildren = new List<PQNode<T, X, Y>*>;

	m_pointerToInfo = nullptr;
}

}
