/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.g2d.elementclass.connection;

import java.awt.geom.AffineTransform;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.simantics.g2d.canvas.ICanvasContext;
import org.simantics.g2d.diagram.IDiagram;
import org.simantics.g2d.diagram.handler.Topology;
import org.simantics.g2d.diagram.handler.Validator;
import org.simantics.g2d.diagram.handler.Topology.Connection;
import org.simantics.g2d.diagram.handler.impl.DiagramIssue;
import org.simantics.g2d.diagram.participant.pointertool.TerminalUtil;
import org.simantics.g2d.element.ElementUtils;
import org.simantics.g2d.element.IElement;
import org.simantics.g2d.element.handler.BendsHandler;
import org.simantics.g2d.element.handler.EdgeVisuals;
import org.simantics.g2d.element.handler.BendsHandler.AngleType;
import org.simantics.g2d.element.handler.BendsHandler.Bend;
import org.simantics.g2d.element.handler.EdgeVisuals.EdgeEnd;
import org.simantics.g2d.routing.algorithm1.Rectangle;
import org.simantics.g2d.utils.GeometryUtils;
import org.simantics.g2d.utils.PathUtils;
import org.simantics.g2d.utils.geom.DirectionSet;
import org.simantics.utils.datastructures.TreeProblem;
import org.simantics.utils.datastructures.TreeProblem.ProblemNode;

/**
 * Checks whether Topology meets geometry  
 * 
 * @author Toni Kalajainen
 */
public class ConnectionValidator implements Validator {



	public static final ConnectionValidator INSTANCE = new ConnectionValidator(); 
	private static final double TOLERANCE = 0.001;
	
	private static final Suggestion DISCONNECT_EDGES = new Suggestion() {
		@Override
		public boolean fix(IDiagram d, ICanvasContext ctx) {			
			return false;
		}
		@Override
		public String getMessage() {
			return "Disconnect edges";
		}
	};
	
	public static final double OBSTACLE_MARGINAL = 10.0; 
	
	static Collection<Rectangle> createObstacles(IDiagram d) {
		ArrayList<Rectangle> obstacles = new ArrayList<Rectangle>();
		for(IElement e : d.getElements())
		{
			if (e.getElementClass().containsClass(EdgeVisuals.class)) continue;
			Rectangle2D rect = ElementUtils.getElementBounds(e);
			obstacles.add(new Rectangle(
				rect.getMinX()-OBSTACLE_MARGINAL,
				rect.getMinY()-OBSTACLE_MARGINAL,
				rect.getMaxX()+OBSTACLE_MARGINAL,
				rect.getMaxY()+OBSTACLE_MARGINAL
			));
		}
		return obstacles;
	}
	
	// Force path to follow its path requirements 
	private static final Suggestion FORCE_PATH_TO_REQUIREMENTS = new Suggestion() {
		@Override
		public boolean fix(IDiagram d, ICanvasContext ctx) {
			
			// Get all edges
			ArrayList<PathRequirement> reqs = new ArrayList<PathRequirement>();			
			for (IElement e : d.getElements())
			{
				BendsHandler bends = e.getElementClass().getAtMostOneItemOfClass(BendsHandler.class);
				if (bends==null) continue;
				Path2D path = bends.getPath(e);
				assert(path!=null);
				reqs.clear();
				createPathRequirement(e, reqs);			
				if (reqs.isEmpty()) continue;
				if (pathFollowsRequirements(path, reqs)) continue;
				
				AngleType at = bends.getAngleType(e);
				if (at==AngleType.Linear) {
					path = createPathLinear(reqs);
				} else if (at==AngleType.RightAngled) {
					path = createPathRightAngled(reqs);					
				} else if (at==AngleType.Quadratic) {
					path = createPathQuadratic(reqs);
				} else if (at==AngleType.Line) {
					path = createPathLine(reqs);
				} else assert(false);
				
				// Make up something!
				if (path==null)
					path = createPathLine(reqs);

				AffineTransform elementToDiagramAt = ElementUtils.getInvTransform(e);
				path.transform(elementToDiagramAt);
				
				bends.setPath(e, path);
			}			
			return false;
		}
		@Override
		public String getMessage() {
			return "Update path";
		}
	};
	private static final Issue PATH_IS_BROKEN = 
		new DiagramIssue("Path does not follow its requirements (connects and bends)", FORCE_PATH_TO_REQUIREMENTS, DISCONNECT_EDGES);
	
	@Override
	public void validate(IDiagram d, ICanvasContext ctx, Collection<Issue> lst) {
		if (!validateDiagramOk(d, ctx, lst))
		{
			lst.add(PATH_IS_BROKEN);
		}
	}
	
	/**
	 * Return true if connections of a diagram are ok.
	 * @param d
	 * @param ctx
	 * @param lst
	 * @return
	 */
	boolean validateDiagramOk(IDiagram d, ICanvasContext ctx, Collection<Issue> lst)
	{
		// Get all edges
		ArrayList<PathRequirement> reqs = new ArrayList<PathRequirement>();
		for (IElement e : d.getElements())
		{
			BendsHandler bends = e.getElementClass().getAtMostOneItemOfClass(BendsHandler.class);
			if (bends==null) continue;
			Path2D path = bends.getPath(e);

			reqs.clear();
			createPathRequirement(e, reqs);			
			if (reqs.isEmpty()) continue;
			if (pathFollowsRequirements(path, reqs)) continue;
			return false;
		}
		return true;
	}
	
	/**
	 * Forces the path to follow path requirements.
	 *  
	 * @param e
	 * @param reqs path requirements.
	 * @return true if path matches requirements
	 */
	public static boolean pathFollowsRequirements(Path2D path, List<PathRequirement> reqs)
	{
		if (reqs.size()==0) return true;
		// To validate path we need to make sure that 
		// 1) path goes thru control points		
		// 2) The tangent of the path at control points is in direction set
		int 				reqIndex	= 0;
		PathRequirement 		req			= reqs.get(reqIndex++); 
		PathIterator		pi			= path.getPathIterator(null);
		Iterator<double[]>	lsi			= PathUtils.toLineIterator(pi);
		if (!lsi.hasNext()) return false;
		
		// check begin
		double[]			seg			= lsi.next();
		Point2D				pos			= PathUtils.getLinePos(seg, 0);
		Rectangle2D			rect		= new Rectangle2D.Double(pos.getX()-TOLERANCE, pos.getY()-TOLERANCE, 2*TOLERANCE, 2*TOLERANCE);
		
		// Check pos
		if (!rect.contains(pos)) return false;
		// Check tangent
		Point2D				tang		= PathUtils.getLineTangent(seg, 0);
		double				dir			= GeometryUtils.getCompassDirection(tang);
		Double				closestDir	= req.set.getClosestDirection(dir, 0.1);
		if (closestDir == null) return false; 
		
		while (lsi.hasNext()) {
			seg				= lsi.next();
			pos				= PathUtils.getLinePos(seg, 1);
			rect			= new Rectangle2D.Double(pos.getX()-TOLERANCE, pos.getY()-TOLERANCE, 2*TOLERANCE, 2*TOLERANCE);
			
			if (rect.contains(pos)) {
				// check tangent
				tang			= PathUtils.getLineTangent(seg, 1);
				dir				= GeometryUtils.getCompassDirection(tang);
				closestDir		= req.set.getClosestDirection(dir, 0.1);
				if (closestDir != null) 
				{
					// next requirement
					req = reqs.get(reqIndex++);
				}
			}			
		}
		return reqIndex==reqs.size();
	}

	static class LinearEdgeSolutionNode implements ProblemNode {
		List<PathRequirement> reqs;
		LinearEdgeSolutionNode prevBranch;
		int index;
		double cost;
		Point2D p0, cp, p1;
		Point2D v0, v1, v1o; // v0=direction vector from p0, v1=direction vector to p1
		// v1o = opposite of v1o
		@Override
		public void branch(Collection<ProblemNode> list) {
			PathRequirement r0 = reqs.get(index  );
			PathRequirement r1 = reqs.get(index+1);
			Point2D		p0 = r0.pos;
			Point2D		p1 = r1.pos;
			Point2D		cp1 = new Point2D.Double();
			Point2D		cp2 = new Point2D.Double();
			Set<Object> controlPoints = new HashSet<Object>();
			for (Point2D v0 : r0.set.getUnitVectors())
				for (Point2D v1 : r1.set.getUnitVectors())
				{
					Point2D	i 	= PathUtils.findIntersection(p0, v0, p1, v1);
					if (i!=null) {
						controlPoints.add(i);
						
					} else {
						// Impossible requirements
						int flags = PathUtils.findNearestPoints(p0, v0, p1, v1, cp1, cp2); 
						if ((flags & 1) == 1) 
							controlPoints.add(cp1);
						if ((flags & 2) == 2)
							controlPoints.add(cp2);
						
					}
				}
			if (controlPoints.isEmpty()) {
				Point2D i = new Point2D.Double(
						(p0.getX() + p1.getX())/2,
						(p0.getY() + p1.getY())/2);
				controlPoints.add(i);
			}
			for (Object dada : controlPoints) {
				Point2D c0 = (Point2D) dada;
				double price = p0.distance(c0)+c0.distance(p1);
				price -= p0.distance(p1);
				
				LinearEdgeSolutionNode s = new LinearEdgeSolutionNode();					
				s.cost = cost + price;
				s.prevBranch = this;
				s.reqs = reqs;
				s.index = index+1;
				s.p0 = p0;
				s.p1 = p1;
				if (!c0.equals(p0) && !c0.equals(p1)) 
					s.cp = c0;
				
				Point2D np = s.cp == null ? p1 : c0;
				double dist = p0.distance(np);
				s.v0 = new Point2D.Double( (p0.getX() - np.getX())/dist, (p0.getY() - np.getY())/dist);

				np = s.cp == null ? p0 : c0;
				dist = p1.distance(np);
				s.v1 = new Point2D.Double( (p1.getX() - np.getX())/dist, (p1.getY() - np.getY())/dist);
				s.v1o = new Point2D.Double( (np.getX() - p1.getX())/dist, (np.getY() - p1.getY())/dist); 

				// Penalty for changing direction 
				if (v1!=null && !s.v0.equals(v1)) 
					s.cost += 1;
				// Penalty for going back
				if (v1o!=null && v1o.equals(s.v0)) 
					s.cost += 2;
				
				list.add(s);
			}
		}
		@Override
		public double getCost() {
			return cost;
		}
		@Override
		public boolean isComplete() {
			return index>=reqs.size()-1;
		}
		/**
		 * Create path from root to this node
		 * @return
		 */
		public List<LinearEdgeSolutionNode> toList() {
			LinkedList<LinearEdgeSolutionNode> res = new LinkedList<LinearEdgeSolutionNode>();
			LinearEdgeSolutionNode branch = this;
			while (branch!=null) {
				res.addFirst(branch);
				branch = branch.prevBranch;
			}
			return res;
		}
		public Path2D toPath() {
			Path2D p = new Path2D.Double();			
			for (LinearEdgeSolutionNode s : toList()) 
			{
				if (s.p0==null) continue;
				Point2D cur = p.getCurrentPoint();
				if (cur==null) 
					p.moveTo(s.p0.getX(), s.p0.getY());
				
				cur = p.getCurrentPoint();
				if ((s.cp!=null)&&(cur==null || !cur.equals(s.cp))) 
					p.lineTo(s.cp.getX(), s.cp.getY());				
				
				cur = p.getCurrentPoint();
				if (cur==null || !cur.equals(s.p1)) 
					p.lineTo(s.p1.getX(), s.p1.getY());				
			}
			
			return p;
		}
	}
	
	/**
	 * Create a linear path that follows path requirements
	 * @param reqs requirements
	 * @return path
	 */
	public static Path2D createPathLinear(final List<PathRequirement> reqs)
	{
		LinearEdgeSolutionNode s = new LinearEdgeSolutionNode();
		s.reqs = reqs;
		LinearEdgeSolutionNode solution = (LinearEdgeSolutionNode) TreeProblem.findSolution(s, 2);
		if (solution==null) return null;		
		return solution.toPath();		
	}
	
	/**
	 * Create a line that follows path requirements
	 * @param reqs
	 * @return
	 */
	public static Path2D createPathLine(final List<PathRequirement> reqs)
	{
		Path2D result = new Path2D.Double();
		int index = 0;
		for (PathRequirement r : reqs) {
			if (index++==0)
				result.moveTo(r.pos.getX(), r.pos.getY());
			else
				result.lineTo(r.pos.getX(), r.pos.getY());
		}
		return result;
	}
	

	/**
	 * Create a right-angled (90 deg angles) path that follows requirements 
	 * @param reqs requirements
	 * @return path
	 */
	public static Path2D createPathRightAngled(List<PathRequirement> reqs)
	{
		Path2D res = new Path2D.Double();
//		int i = 0;
//		for (PathRequirement r : reqs)
//		{
//				
//		}			
		
		return res;
	}
	
	/**
	 * Create a path that follows requirements
	 * @param reqs requirements
	 * @return path
	 */
	public static Path2D createPathQuadratic(List<PathRequirement> reqs)
	{
		Path2D res = new Path2D.Double();
//		int i = 0;
//		for (PathRequirement r : reqs)
//		{
//			
//		}			
		
		return res;
	}
	
	
	/**
	 * Path Requirement is a point thru which the path must "travel".
	 */
	static class PathRequirement {
		Point2D pos;  // Position on diagram
		DirectionSet set; // Allowed directions
		boolean isBegin, isEnd;
	}
	
	/**
	 * Takes a look at an edge and creates a path travel plan (requiremetn).
	 * Beginning of e must point to (possibly) connected terminal.
	 * End of e must point to (possibly) connected terminal.
	 * 
	 * @param e
	 * @param pathRequirement Path requirements
	 */
	public static void createPathRequirement(IElement e, List<PathRequirement> pathRequirement)
	{
		Topology t = ElementUtils.getDiagram(e).getDiagramClass().getSingleItem(Topology.class);
		pathRequirement.clear();
		if (t==null) return;
		
		// Add begin
		Connection c1 = t.getConnection(e, EdgeEnd.Begin);
		if (c1!=null) {
			PathRequirement req = new PathRequirement();
			AffineTransform at = TerminalUtil.getTerminalPosOnDiagram(c1.node, c1.terminal);			
			req.pos = new Point2D.Double( at.getTranslateX(), at.getTranslateY() );
			req.set = ElementUtils.getTerminalDirection(c1.node, c1.terminal);
			req.isBegin = true;
			pathRequirement.add(req);
		} 
		
		// Add control points
		AffineTransform elementTransform = ElementUtils.getTransform(e);
		BendsHandler bends = e.getElementClass().getSingleItem(BendsHandler.class);		
		ArrayList<Bend> controlPoints = new ArrayList<Bend>();
		bends.getBends(e, controlPoints);
		for (Bend cp : controlPoints) 
		{
			Point2D pos = new Point2D.Double();
			bends.getBendPosition(e, cp, pos);
			elementTransform.transform(pos, pos);
			PathRequirement req = new PathRequirement();
			req.set = DirectionSet.NESW;
			req.pos = pos;
			pathRequirement.add(req);
		}
	
		// TODO lisää transformit
		
		
		// Add end
		Connection c2 = t.getConnection(e, EdgeEnd.End);
		if (c2!=null) {
			PathRequirement req = new PathRequirement();
			AffineTransform at = TerminalUtil.getTerminalPosOnDiagram(c2.node, c2.terminal);			
			req.pos = new Point2D.Double( at.getTranslateX(), at.getTranslateY() );
			req.set					= ElementUtils.getTerminalDirection(c2.node, c2.terminal);
			req.set					= req.set.createInverse();
			req.isEnd				= true;
			pathRequirement.add(req);
		} 		
		
	}

}