/** \file
 * \brief declaration of the FastSimpleHierarchyLayout
 * (third phase of sugiyama)
 *
 * \author Till Schäfer, Carsten Gutwenger
 *
 * \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/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/layered/CrossingMinInterfaces.h>
#include <ogdf/layered/HierarchyLayoutModule.h>

namespace ogdf {
class GraphAttributes;
class GraphCopy;

/**
 * \brief Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf
 *
 * @ingroup gd-hlm
 *
 * This class implements a hierarchy layout algorithm, i.e., it layouts
 * hierarchies with a given order of nodes on each layer. It is used as a third
 * phase of the Sugiyama algorithm.
 *
 * The Algorithm runs in three phases.<br>
 * - Alignment (4x)<br>
 * - Horizontal Compactation (4x)<br>
 * - Balancing
 *
 * The <i>Alignment</i> and <i>Horzontal Compactation</i> phase are calculated downward, upward,
 * left-to-right and right-to-left. The four resulting layouts are combined in a balancing step.
 *
 * The implementation is based on:
 *
 * Ulrik Brandes, Boris Köpf: <i>Fast and Simple Horizontal Coordinate Assignment</i>.
 * LNCS 2002, Volume 2265/2002, pp. 33-36
 *
 * <h3>Optional Parameters</h3>
 *
 * <table>
 *   <tr>
 *     <th>Option</th><th>Type</th><th>Default</th><th>Description</th>
 *   </tr><tr>
 *     <td><i>node distance</i></td><td>int</td><td>150</td>
 *     <td>the minimal horizontal distance between two nodes on the same layer</td>
 *   </tr><tr>
 *     <td><i>layer distance</i></td><td>int</td><td>75</td>
 *     <td>the minimal vertical distance between two nodes on adjacent layers</td>
 *   </tr><tr>
 *     <td><i>balanced</i></td><td>bool</td><td>true</td>
 *     <td>determines whether balancing is used</td>
 *   </tr><tr>
 *     <td><i>left-to-right</i></td><td>bool</td><td>true</td>
 *     <td>determines whether block alignment is computed by a left-to-right (true) or right-to-left traversal</td>
 *   </tr><tr>
 *     <td><i>downward</i></td><td>bool</td><td>true</td>
 *     <td>determines whether block alignment is computed by a downward (true) or upward traversal</td>
 *   </tr>
 * </table>
 */
class OGDF_EXPORT FastSimpleHierarchyLayout : public HierarchyLayoutModule {
private:
	double m_minXSep; //!< stores the option <i>node distance</i>.
	double m_ySep; //!< stores the option <i>layer distance</i>.
	bool m_balanced; //!< stores the option <i>balanced</i>.
	bool m_downward; //!< stores the option <i>downward</i>.
	bool m_leftToRight; //!< stores the option <i>left-to-right</i>.

protected:
	virtual void doCall(const HierarchyLevelsBase& levels, GraphAttributes& AGC) override;

public:
	//! Creates an instance of fast simple hierarchy layout.
	/**
	 * Sets the options to default values, i.e., use balanced layout with left-to-right node
	 * direction on each layer, node distance as given by LayoutStandards, and layer distance as
	 * 1.5 times node distance.
	 */
	FastSimpleHierarchyLayout();


	//! Copy constructor.
	FastSimpleHierarchyLayout(const FastSimpleHierarchyLayout&);

	// destructor
	virtual ~FastSimpleHierarchyLayout() { }

	//! Assignment operator
	FastSimpleHierarchyLayout& operator=(const FastSimpleHierarchyLayout&);

	//! Returns the option <i>node distance</i>.
	double nodeDistance() const { return m_minXSep; }

	//! Sets the option node distance to \p dist.
	void nodeDistance(double dist) { m_minXSep = dist; }

	//! Returns the option <i>layer distance</i>.
	double layerDistance() const { return m_ySep; }

	//! Sets the option <i>layer distance</i> to \p dist.
	void layerDistance(double dist) { m_ySep = dist; }

	//! Returns the option <i>downward</i>.
	bool downward() const { return m_downward; }

	//! Sets the option <i>downward</i> to \p d.
	void downward(bool d) { m_downward = d; }

	//! Returns the option <i>left-to-right</i>.
	bool leftToRight() const { return m_leftToRight; }

	//! Sets the option <i>left-to-right</i> to \p b.
	void leftToRight(bool b) { m_leftToRight = b; }

	//! Returns the option <i>balanced</i>.
	bool balanced() const { return m_balanced; }

	//! Sets the option <i>balanced</i> to \p b.
	void balanced(bool b) { m_balanced = b; }


private:
	/**
	 * Preprocessing step to find all type1 conflicts.
	 * A type1 conflict is a crossing of a inner segment with a non-inner segment.
	 *
	 * This is for preferring straight inner segments.
	 *
	 * @param levels The Hierarchy
	 * @param downward The level direction
	 * @param type1Conflicts is assigned the conflicts, (type1Conflicts[v])[u]=true means (u,v) is marked, u is the upper node
	 */
	void markType1Conflicts(const HierarchyLevelsBase& levels, bool downward,
			NodeArray<NodeArray<bool>>& type1Conflicts);

	/**
	 * Align each node to a node on the next higher level. The result is a blockgraph where each
	 * node is in a block whith a nother node when they have the same root.
	 *
	 * @param levels The Hierarchy
	 * @param root The root for each node (calculated by this method)
	 * @param align The alignment to the next level node (align(v)=u <=> u is aligned to v) (calculated by this method)
	 * @param type1Conflicts Type1 conflicts to prefer straight inner segments
	 * @param downward The level direction
	 * @param leftToRight The node direction on each level
	 */
	void verticalAlignment(const HierarchyLevelsBase& levels, NodeArray<node>& root,
			NodeArray<node>& align, const NodeArray<NodeArray<bool>>& type1Conflicts,
			const bool downward, const bool leftToRight);

	/**
	 * Computes the width of each block, i.e., the maximal width of a node in the block, and
	 * stores it in blockWidth for the root of the block.
	 *
	 * @param GC The input graph copy
	 * @param GCA The input graph copies (gives in particular the widths of nodes)
	 * @param root The root for each node (calculated by this method)
	 * @param blockWidth Is assigned the width of each block (stored for the root)
	 */
	void computeBlockWidths(const GraphCopy& GC, const GraphAttributes& GCA, NodeArray<node>& root,
			NodeArray<double>& blockWidth);

	/**
	 * Calculate the coordinates for each node
	 *
	 * @param align The alignment to the next level node (align(v)=u <=> u is aligned to v)
	 * @param levels The Hierarchy
	 * @param root The root for each node
	 * @param blockWidth The width of each block
	 * @param x The x-coordinates for each node (calculated by this method)
	 * @param leftToRight The node direction on each level
	 * @param downward The level direction
	 */
	void horizontalCompactation(const NodeArray<node>& align, const HierarchyLevelsBase& levels,
			const NodeArray<node>& root, const NodeArray<double>& blockWidth, NodeArray<double>& x,
			const bool leftToRight, bool downward);

	/**
	 * Calculate the coordinate for root nodes (placing)
	 *
	 * @param v The root node to place
	 * @param sink The Sink for each node. A sink identifies each block class (calculated by this method)
	 * @param shift The shift for each class (calculated by this method)
	 * @param x The class relative x-coordinate for each node (calculated by this method)
	 * @param align The alignment to the next level node (align(v)=u <=> u is aligned to v)
	 * @param levels The Hierarchy
	 * @param blockWidth The width of each block
	 * @param root The root for each node
	 * @param leftToRight The node direction on each level
	 */
	void placeBlock(node v, NodeArray<node>& sink, NodeArray<double>& shift, NodeArray<double>& x,
			const NodeArray<node>& align, const HierarchyLevelsBase& levels,
			const NodeArray<double>& blockWidth, const NodeArray<node>& root, const bool leftToRight);

	/**
	 * The twin of an inner Segment
	 *
	 * @return Parent node which is connected by an inner segment.
	 * nullptr if there is no parent segment or if the segment is not an inner segment.
	 */
	node virtualTwinNode(const HierarchyLevelsBase& levels, const node v,
			const HierarchyLevelsBase::TraversingDir dir) const;

	/**
	 * Predecessor of v on the same level,
	 *
	 * @param v The node for which the predecessor should be calculated.
	 * @param levels The Hierarchy
	 * @param leftToRight If true the left predecessor is choosen. Otherwise the right predecessor.
	 * @return Predescessor on the same level. nullptr if there is no predecessor.
	 */
	node pred(const node v, const HierarchyLevelsBase& levels, const bool leftToRight);
};

}
