// SPDX-FileCopyrightText: 2020 Roberto Posenato <roberto.posenato@univr.it>
//
// SPDX-License-Identifier: LGPL-3.0-or-later
package it.univr.di.cstnu.visualization;

import com.google.common.base.Function;
import edu.uci.ics.jung.algorithms.layout.AbstractLayout;
import edu.uci.ics.jung.algorithms.util.IterativeContext;
import edu.uci.ics.jung.graph.Graph;
import it.unimi.dsi.fastutil.objects.ObjectArrayFIFOQueue;
import it.unimi.dsi.fastutil.objects.ObjectList;
import it.unimi.dsi.fastutil.objects.ObjectOpenHashSet;
import it.unimi.dsi.fastutil.objects.ObjectSet;
import it.univr.di.Debug;
import it.univr.di.cstnu.graph.*;
import it.univr.di.cstnu.util.ExtendedPriorityQueue;
import it.univr.di.labeledvalue.Constants;
import it.univr.di.labeledvalue.Literal;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.awt.*;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Allows the layout of a CSTN(U) determined by transforming a workflow generated by Atapis Random generator tool. Such
 * class is highly depended on the name conventions used in Atapis Random generator tool. So, it is not general, and it
 * cannot be used in other contexts.
 *
 * @author posenato
 * @version $Rev$
 */
@SuppressWarnings("AutoBoxing")
public class CSTNLayout extends edu.uci.ics.jung.algorithms.layout.StaticLayout<LabeledNode, CSTNEdge>
	implements IterativeContext {

	/**
	 * Returns the coordinates of a node as Point2d object.
	 */
	@SuppressWarnings("ReturnOfNull")
	static public final Function<LabeledNode, Point2D> positionInitializer = v -> {
		if (v == null) {
			return null;
		}
		return new Point2D.Double(v.getX(), v.getY());
	};

	/**
	 * x shift for next node
	 */
	private static final double xShift = 100;
	/**
	 * y shift for next node if not particular condition applies.
	 */
	private static final double yShift = 100;

	/**
	 * @param s node name
	 *
	 * @return true if s is the name of a node that represent the starting event of an activity or a connector.
	 */
	static public boolean isAStartingNode(String s) {
		return (s != null && s.charAt(s.length() - 1) == 'S');
	}

	/**
	 * @param s node name
	 *
	 * @return true if s is the name of a node that represent the starting event of an activity or a connector.
	 */
	static public boolean isAnEndingNode(String s) {
		return (s != null && (s.charAt(s.length() - 1) == 'E' || s.charAt(s.length() - 1) == '?'));
	}

	/**
	 * @param s node name
	 *
	 * @return the name of corresponding end node.
	 */
	@Nullable
	static public String nameCorrespondingEndNode(String s) {
		if (!isAStartingNode(s)) {return null;}
		return s.substring(0, s.length() - 1) + "E";
	}

	/**
	 * Version
	 */
	static final public String VERSIONandDATE = "Version  1.0 - October, 20 2017";
	/**
	 *
	 */
	public static final long serialVersionUID = 1L;
	/**
	 * Logger
	 */
	private static final Logger LOG = Logger.getLogger(CSTNLayout.class.getName());
	/**
	 * half of the yShiftA length
	 */
	private int halfLengthOfyShiftArray;
	/**
	 * half of y shift for next node if not particular condition applies.
	 */
	private double halfYShift;

	/**
	 * X position first node.
	 */
	private double initialX = 25;

	/**
	 * Y position first node.
	 */
	private double initialY = 200;

	/**
	 * max X
	 */
	private double maxX;

	/**
	 * max Y
	 */
	private double maxY;

	/**
	 * @param s node name
	 *
	 * @return the name of corresponding start node.
	 */
	@Nullable
	static public String nameCorrespondingStartNode(String s) {
		if (!isAnEndingNode(s)) {return null;}
		final int offset = (s.charAt(s.length() - 1) == 'E') ? 0 : 1;
		return s.substring(offset, s.length() - 1) + "S";
	}

	/**
	 * @param s node name
	 *
	 * @return the name of corresponding end node of an XOR connector
	 */
	@Nullable
	static public String nameCorrespondingXOREndNode(String s) {
		if (!isAStartingNode(s)) {return null;}
		return 'X' + nameCorrespondingEndNode(s) + '?';
	}

	/**
	 * array of possible y shifts.
	 */
	private double[] yShiftA;

	/**
	 * Current layout from which take current node positions.
	 */
	private AbstractLayout<LabeledNode, ? extends Edge> currentLayout;

	/**
	 * Creates an instance for the specified graph and default size; vertex locations are determined by
	 * {@link #positionInitializer}.
	 *
	 * @param graph1 a {@link edu.uci.ics.jung.graph.Graph} object.
	 */
	public CSTNLayout(final Graph<LabeledNode, CSTNEdge> graph1) {
		super(graph1);
	}

	/**
	 * Creates an instance for the specified graph and size.
	 *
	 * @param graph1 a {@link edu.uci.ics.jung.graph.Graph} object.
	 * @param size1  a {@link java.awt.Dimension} object.
	 */
	public CSTNLayout(final Graph<LabeledNode, CSTNEdge> graph1, final Dimension size1) {
		super(graph1, positionInitializer, size1);
	}

	/**
	 * @return the initialX
	 */
	public double getInitialX() {
		return initialX;
	}

	/**
	 * @param initialX1 the initialX to set
	 */
	public void setInitialX(int initialX1) {
		initialX = initialX1;
	}

	/**
	 * @return the initialY
	 */
	public double getInitialY() {
		return initialY;
	}

	/**
	 * @param initialY1 the initialY to set
	 */
	public void setInitialY(int initialY1) {
		initialY = initialY1;
	}

//    /**
//     * @return the xShift
//     */
//    public double getxShift() {
//        return xShift;
//    }
//
//    /**
//     * @param xShift1 the xShift to set
//     */
//    public void setxShift(int xShift1) {
//        xShift = xShift1;
//    }
//
//    /**
//     * @return the yShift
//     */
//    public double getyShift() {
//        return yShift;
//    }
//
//    /**
//     * @param yShift1 the yShift to set
//     */
//    public void setyShift(int yShift1) {
//        yShift = yShift1;
//        halfYShift = yShift1 / 2.0;
//    }

	@Override
	public void initialize() {
		final it.univr.di.cstnu.graph.TNGraph<CSTNEdge> g = (it.univr.di.cstnu.graph.TNGraph<CSTNEdge>) graph;
		final LabeledNode Z = g.getZ();
		// Approximate number of AND split = (n-6*obs -5)/6;
		final int nAnd = (g.getVertexCount() - 6 * g.getObserverCount() - 5) / 6;
		final int nSplit = g.getObserverCount() + nAnd;
		final int possiblyShift = 20;//20 is oversize but it costs quasi nothing
		yShiftA = new double[possiblyShift];
		halfLengthOfyShiftArray = yShiftA.length / 2;
		//first half of yShiftA must be negative, the other positive
		double y =
			-yShift / 2 * (halfLengthOfyShiftArray); //in this way, it holds that yShiftA[halfLengthOfyShiftArray] == 0
		for (int i = 0; i < possiblyShift; i++) {
			yShiftA[i] = y;
			y += yShift / 2;
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finest("yShiftA = " + Arrays.toString(yShiftA));
			}
		}

		halfYShift = yShift / 2;
		maxX = initialX;
		maxY = initialY;

		final Collection<LabeledNode> allNodes = g.getVertices();
		if (currentLayout != null) {
			for (final LabeledNode node : allNodes) {
				node.setX(currentLayout.getX(node));
				node.setY(currentLayout.getY(node));
			}
		}
		/*
		 * Draw the graph
		 */
		final ObjectSet<LabeledNode> marked = draw(Z, initialX, initialY, g, nSplit);

		while (marked != null && !marked.containsAll(allNodes)) {
			LabeledNode otherZ = Z;
			for (final LabeledNode node : allNodes) {
				if (!marked.contains(node)) {
					otherZ = node;
					break;
				}
			}
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINER)) {
					LOG.finest("A node has not laid out because has not negative out outgoing edges: " + otherZ
					           + "\nStart a new layout phase for such nodes and its successors.");
				}
			}
			assert otherZ != null;
			marked.addAll(draw(otherZ, otherZ.getX(), otherZ.getY(), g, nSplit));
		}

		// check if some node has a negative y
		double negativeY = halfYShift;
		for (final LabeledNode node : g.getVertices()) {
			final double lY = node.getY();
			if (lY < halfYShift) {
				if (lY < negativeY) {
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINER)) {
							LOG.finest("A negative value for y coordinate found: " + lY + ". It belongs to node "
							           + node.getName());
						}
					}
					negativeY = lY;
				}
			}
		}
		if (negativeY < halfYShift) {
			// it is necessary to shift every thing
			negativeY = (negativeY < 0) ? -negativeY + yShift / 2 : yShift / 2;
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINER)) {
					LOG.info("It is necessary to translate the graph of " + negativeY + " pixels.");
				}
			}
			for (final LabeledNode node : g.getVertices()) {
				final double lY = node.getY();
				node.setY(lY + negativeY);
			}
			maxY = maxY + negativeY;
		}

		size = new Dimension((int) (maxX + xShift / 4), (int) (maxY + yShift / 4));
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finest("This size is " + size + " pixels.");
			}
		}
	}

	/**
	 * @param firstNode  first node
	 * @param firstNodeX x coordinate of first node
	 * @param firstNodeY y coordinate of first node
	 * @param g          the network where node is present
	 * @param nSplits    the {@link AbstractLayout#apply(Object)} of open split
	 *
	 * @return the set of nodes that have been laid out.
	 */
	public ObjectSet<LabeledNode> draw(LabeledNode firstNode, double firstNodeX, double firstNodeY,
	                                   @Nonnull TNGraph<CSTNEdge> g, int nSplits) {
		final ObjectSet<LabeledNode> marked = new ObjectOpenHashSet<>(g.getVertexCount());
		if (firstNode == null) {
			return marked;
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("Node root " + firstNode.getName() + ": (" + firstNodeX + ", " + firstNodeY + ")");
			}
		}
		firstNode.setX(firstNodeX);
		firstNode.setY(firstNodeY);
		if (firstNodeX > maxX) {
			maxX = firstNodeX;
		}
		if (firstNodeY > maxY) {
			maxY = firstNodeY;
		}

		// Breadth-first traversal
		final ObjectArrayFIFOQueue<LabeledNode> queue = new ObjectArrayFIFOQueue<>();
		queue.enqueue(firstNode);
		marked.add(firstNode);
		while (!queue.isEmpty()) {
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest(String.format("DRAW. Queue: %4d. Marked size: %4d.", queue.size(), marked.size()));
				}
			}
			final LabeledNode node = queue.dequeue();
			final String nodeName = node.getName();

			final double xNode = node.getX();
			final double yNode = node.getY();
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest("Node father " + node.getName() + ": (" + xNode + ", " + yNode + ")");
				}
			}

			final Collection<LabeledNode> successors = getOrderedSuccessors(node, g);
			int i = halfLengthOfyShiftArray - successors.size() / 2;
			for (final LabeledNode adjacent : successors) {
				if (marked.contains(adjacent)) {
					// the adjacent has been already laid out.
					if (adjacent.getX() <= xNode || adjacent.getX() >= xNode + xShift) {
						if (nodeName.endsWith("w1") || nodeName.endsWith("w0") || node.getLabel()
							.equals(adjacent.getLabel()) || (node.getLabel().subsumes(adjacent.getLabel())
						                                     && !adjacent.getLabel().subsumes(node.getLabel()))) {
							final double newY;
							if (adjacent.getY() > yNode + halfYShift) {
								newY = (yNode + (adjacent.getY() - halfYShift - yNode) / 2);
								if (newY > maxY) {
									maxY = newY;
								}
							} else {
								if (adjacent.getY() < yNode - halfYShift) {
									newY = (yNode - (yNode - adjacent.getY() + halfYShift) / 2);
									if (newY > maxY) {
										maxY = newY;
									}
								} else {
									newY = adjacent.getY();
								}
							}
							final double newX = ((adjacent.getX() <= xNode) ? xNode + xShift : adjacent.getX());
							if (Double.compare(adjacent.getY(), newY) == 0
							    && Double.compare(adjacent.getX(), newX) == 0) {
								continue;
							}
							if (newX > maxX) {
								maxX = newX;
							}
							redraw(adjacent, newX, newY, g, marked);
						}
					}
					continue;
				}
				final double x = xNode + xShift;
				final double y;
				if (node.isObserver() || nodeName.endsWith("E AND SPLIT")) {
					if (i == halfLengthOfyShiftArray) {
						i++; // no child must be drawn just right the father. Right above or right below is better.
					}
					y = yNode + yShiftA[i++] * nSplits;
				} else {
					if (nodeName.endsWith("w1") || nodeName.endsWith("w0")) {
						y = yNode + ((nodeName.endsWith("w1") ? -1 : 1)) * halfYShift;
					} else {
						if (node.getLabel().subsumes(adjacent.getLabel()) && !adjacent.getLabel()
							.subsumes(node.getLabel())) {
							final Literal l = node.getLabel().getUniqueDifferentLiteral(adjacent.getLabel());
							if (l == null || l.isNegated()) {
								y = yNode + halfYShift;
							} else {
								y = yNode - halfYShift;
							}
						} else {
							y = yNode + yShiftA[i++];// if there is only one adjacent, this.yShiftA[i++] is 0.
						}
					}
				}

				if (Debug.ON) {
					if (LOG.isLoggable(Level.FINEST)) {
						LOG.finest("Node adjacent " + adjacent.getName() + ": (" + x + ", " + y + ")");
					}
				}
				adjacent.setX(x);
				adjacent.setY(y);
				if (y > maxY) {
					maxY = y;
				}
				if (x > maxX) {
					maxX = x;
				}
				marked.add(adjacent);
				queue.enqueue(adjacent);
			}
			if (node.isObserver() || nodeName.endsWith("E AND SPLIT")) {
				nSplits--;
			}
		}
		return marked;
	}

	/**
	 * Relocate some marked adjacent nodes of given node because node has been relocated. The relocation is realized by
	 * shifting nodes as much as the given node has been shifted.
	 *
	 * @param firstNode first node
	 * @param nodeX     x coordinate
	 * @param nodeY     y coordinate
	 * @param g         the network
	 * @param marked    the marked nodes.
	 */
	private void redraw(LabeledNode firstNode, double nodeX, double nodeY, it.univr.di.cstnu.graph.TNGraph<CSTNEdge> g,
	                    ObjectSet<LabeledNode> marked) {
		if (firstNode == null) {
			return;
		}
		double shiftX = nodeX - firstNode.getX();
		final double shiftY = nodeY - firstNode.getY();
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finest("Shift to apply: (" + shiftX + ", " + shiftY + ")");
			}
		}
		final ObjectArrayFIFOQueue<LabeledNode> queue = new ObjectArrayFIFOQueue<>();
		final ObjectSet<LabeledNode> markedInternal = new ObjectOpenHashSet<>();
		queue.enqueue(firstNode);
		markedInternal.add(firstNode);
		while (!queue.isEmpty()) {
			final LabeledNode node = queue.dequeue();
			final String nodeName = node.getName();
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINER)) {
					LOG.finer(
						String.format("REDRAW. Queue length: %4d. Marked size: %4d.", queue.size(), marked.size()));
				}
			}
			if (!marked.contains(node)) {
				continue;
			}
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINER)) {
					LOG.finest(
						"Relocated node " + nodeName + ": (" + node.getX() + ", " + node.getY() + ")-->" + "("
						+ (node.getX() + shiftX) + ", " + (node.getY() + shiftY) + ")");
				}
			}
			final double newX = node.getX() + shiftX;
			final double newY = node.getY() + shiftY;

			node.setX(newX);
			node.setY(newY);

			if (newX > maxX) {
				maxX = newX;
			}
			if (newY > maxY) {
				maxY = newY;
			}

			if (isAnEndingNode(nodeName)) {
				final String sourceName = nameCorrespondingStartNode(nodeName);
				assert sourceName != null;
				final LabeledNode source = g.getNode(sourceName);
				if (source != null) {
					final double sourceY = source.getY();
					if (Double.compare(sourceY, node.getY()) != 0) {
						node.setY(sourceY);
					}
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINER)) {
							LOG.finest(
								"Adjusted y coordinate to node " + nodeName + ": (" + node.getX() + ", " + node.getY() +
								")");
						}
					}
				}
			}

			final ObjectList<CSTNEdge> inEdge = g.getInEdges(node);
			inEdge.removeIf(e -> e.getMinValue() > 0 || (e.getConstraintType() == Edge.ConstraintType.contingent
			                                             && ((BasicCSTNUEdge) e).lowerCaseValueSize() > 0));
			double minDistanceAdjNode = Constants.INT_POS_INFINITE;
			for (final CSTNEdge e : inEdge) {
				final LabeledNode adjacent = g.getSource(e);
				if (!marked.contains(adjacent) || markedInternal.contains(adjacent)) {
					continue;
				}
				assert adjacent != null;
				final double distanceAdjNode = (adjacent.getX() + shiftX) - node.getX();
				if (distanceAdjNode < minDistanceAdjNode) {
					minDistanceAdjNode = distanceAdjNode;
				}
				queue.enqueue(adjacent);
				markedInternal.add(adjacent);
			}
			//if all adjacent nodes are more distant than the xShift, update the shiftX for
			//next rounds in order to avoid to move adjacent nearer.
			//noinspection FloatingPointEquality
			if (minDistanceAdjNode != Constants.INT_POS_INFINITE && minDistanceAdjNode > xShift) {
				shiftX = shiftX - minDistanceAdjNode + xShift;
			}
			//in any case, xShift is the minimum.
			if (shiftX < xShift) {
				shiftX = xShift;
			}
		}
	}

	/**
	 * @param currentLayout1 the currentLayout to set
	 */
	@edu.umd.cs.findbugs.annotations.SuppressFBWarnings(value = "EI_EXPOSE_REP2",
		justification = "For efficiency reason, it includes an external mutable object.")
	public void setCurrentLayout(AbstractLayout<LabeledNode, ? extends Edge> currentLayout1) {
		currentLayout = currentLayout1;
	}

	@Override
	public String toString() {
		return CSTNLayout.VERSIONandDATE;
	}

	@Override
	public void step() {
		// no action
	}

	@Override
	public boolean done() {
		return false;
	}

	/**
	 * @param node node name. It must be not null.
	 *
	 * @return an array of successor of {@code node}. Such array is ordered in a such a way that in the middle of the
	 * 	array there are successors with high number of relative successors. This should guarantee that the graph is
	 * 	layout along a central line as much as possible. empty collection if the input is incorrect.
	 */
	private static Collection<LabeledNode> getOrderedSuccessors(@Nonnull LabeledNode node,
	                                                            @Nonnull TNGraph<CSTNEdge> g) {
		final ExtendedPriorityQueue<LabeledNode> nodeMaxPriority = new ExtendedPriorityQueue<>();
		final String nodeName = node.getName();
		if (isAStartingNode(nodeName)) {
			// Consider only the corresponding node when the node is a start node.
			String adjName = nameCorrespondingEndNode(nodeName);
			CSTNEdge e = g.findEdge(adjName, nodeName);
			if (e == null && "1S".equals(nodeName)) {// in some graph, 1E has been replaced by Ω
				e = g.findEdge("Ω", nodeName);
			}
			if (e != null) {
				nodeMaxPriority.insertOrUpdate(Objects.requireNonNull(g.getSource(e)), 1);
			} else {
				adjName = nameCorrespondingXOREndNode(nodeName);
				e = g.findEdge(adjName, nodeName);
				if (e != null) {
					nodeMaxPriority.insertOrUpdate(Objects.requireNonNull(g.getSource(e)), 1);
				} else {
					throw new IllegalStateException("Node name unplanned: " + nodeName);
				}
			}
		} else {
			// Consider successor nodes
			for (final CSTNEdge e : g.getInEdges(node)) {
				if (e.getMinValue() > 0 || (e.getConstraintType() == Edge.ConstraintType.contingent
				                            && ((BasicCSTNUEdge) e).lowerCaseValueSize() > 0)) {
					continue;
				}
				final LabeledNode d = g.getSource(e);
				assert d != null;
				final int p = g.getInEdges(d).size();
				nodeMaxPriority.insertOrUpdate(d,
				                               -p);//negative value because ExtendedPriorityQueue is min ExtendedPriorityQueue
			}
			final Set<LabeledNode> nodeToRemove = new TreeSet<>();
			//if a node in the priority queue is successor of any other node in the priority queue,
			//it must be removed because it must be layout later.
			for (final LabeledNode n : nodeMaxPriority.getElements()) {
				for (final CSTNEdge e : g.getInEdges(n)) {
					if (e.getMinValue() > 0 || (e.getConstraintType() == Edge.ConstraintType.contingent
					                            && ((BasicCSTNUEdge) e).lowerCaseValueSize() > 0)) {
						continue;
					}
					final LabeledNode d = g.getSource(e);
					if (nodeMaxPriority.getPriority(d) != Constants.INT_POS_INFINITE) {//it will be removed
						nodeToRemove.add(d);
						nodeMaxPriority.insertOrUpdate(n, nodeMaxPriority.getPriority(n) + 1);
					}
				}
			}
			//remove all successors that must be drawn later
			for (final LabeledNode n : nodeToRemove) {
				nodeMaxPriority.delete(n);
			}
		}
		return nodeMaxPriority.getElements();
	}

}