/*******************************************************************************
 * Copyright (c) 2000, 2010 IBM Corporation and others.
 * 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:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.draw2d;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.draw2d.geometry.Point;
import org.eclipse.draw2d.geometry.PointList;
import org.eclipse.draw2d.geometry.PrecisionPoint;
import org.eclipse.draw2d.geometry.Rectangle;
import org.eclipse.draw2d.graph.Path;
import org.eclipse.draw2d.graph.ShortestPathRouter;

/**
 * Routes multiple connections around the children of a given container figure.
 * 
 * @author Whitney Sorenson
 * @author Randy Hudson
 * @since 3.1
 */
public final class ShortestPathConnectionRouter extends AbstractRouter {

	private class LayoutTracker extends LayoutListener.Stub {
		public void postLayout(IFigure container) {
			processLayout();
		}

		public void remove(IFigure child) {
			removeChild(child);
		}

		public void setConstraint(IFigure child, Object constraint) {
			addChild(child);
		}
	}

	private Map constraintMap = new HashMap();
	private Map figuresToBounds;
	private Map connectionToPaths;
	private boolean isDirty;
	private ShortestPathRouter algorithm = new ShortestPathRouter();
	private IFigure container;
	private Set staleConnections = new HashSet();
	private LayoutListener listener = new LayoutTracker();

	private FigureListener figureListener = new FigureListener() {
		public void figureMoved(IFigure source) {
			Rectangle newBounds = source.getBounds().getCopy();
			if (algorithm.updateObstacle(
					(Rectangle) figuresToBounds.get(source), newBounds)) {
				queueSomeRouting();
				isDirty = true;
			}

			figuresToBounds.put(source, newBounds);
		}
	};
	private boolean ignoreInvalidate;

	/**
	 * Creates a new shortest path router with the given container. The
	 * container contains all the figure's which will be treated as obstacles
	 * for the connections to avoid. Any time a child of the container moves,
	 * one or more connections will be revalidated to process the new obstacle
	 * locations. The connections being routed must not be contained within the
	 * container.
	 * 
	 * @param container
	 *            the container
	 */
	public ShortestPathConnectionRouter(IFigure container) {
		isDirty = false;
		algorithm = new ShortestPathRouter();
		this.container = container;
	}

	void addChild(IFigure child) {
		if (connectionToPaths == null)
			return;
		if (figuresToBounds.containsKey(child))
			return;
		Rectangle bounds = child.getBounds().getCopy();
		algorithm.addObstacle(bounds);
		figuresToBounds.put(child, bounds);
		child.addFigureListener(figureListener);
		isDirty = true;
	}

	private void hookAll() {
		figuresToBounds = new HashMap();
		for (int i = 0; i < container.getChildren().size(); i++)
			addChild((IFigure) container.getChildren().get(i));
		container.addLayoutListener(listener);
	}

	private void unhookAll() {
		container.removeLayoutListener(listener);
		if (figuresToBounds != null) {
			Iterator figureItr = figuresToBounds.keySet().iterator();
			while (figureItr.hasNext()) {
				// Must use iterator's remove to avoid concurrent modification
				IFigure child = (IFigure) figureItr.next();
				figureItr.remove();
				removeChild(child);
			}
			figuresToBounds = null;
		}
	}

	/**
	 * Gets the constraint for the given {@link Connection}. The constraint is
	 * the paths list of bend points for this connection.
	 * 
	 * @param connection
	 *            The connection whose constraint we are retrieving
	 * @return The constraint
	 */
	public Object getConstraint(Connection connection) {
		return constraintMap.get(connection);
	}

	/**
	 * Returns the default spacing maintained on either side of a connection.
	 * The default value is 4.
	 * 
	 * @return the connection spacing
	 * @since 3.2
	 */
	public int getSpacing() {
		return algorithm.getSpacing();
	}

	/**
	 * @see ConnectionRouter#invalidate(Connection)
	 */
	public void invalidate(Connection connection) {
		if (ignoreInvalidate)
			return;
		staleConnections.add(connection);
		isDirty = true;
	}

	private void processLayout() {
		if (staleConnections.isEmpty())
			return;
		((Connection) staleConnections.iterator().next()).revalidate();
	}

	private void processStaleConnections() {
		Iterator iter = staleConnections.iterator();
		if (iter.hasNext() && connectionToPaths == null) {
			connectionToPaths = new HashMap();
			hookAll();
		}

		while (iter.hasNext()) {
			Connection conn = (Connection) iter.next();

			Path path = (Path) connectionToPaths.get(conn);
			if (path == null) {
				path = new Path(conn);
				connectionToPaths.put(conn, path);
				algorithm.addPath(path);
			}

			List constraint = (List) getConstraint(conn);
			if (constraint == null)
				constraint = Collections.EMPTY_LIST;

			Point start = conn.getSourceAnchor().getReferencePoint().getCopy();
			Point end = conn.getTargetAnchor().getReferencePoint().getCopy();

			container.translateToRelative(start);
			container.translateToRelative(end);

			path.setStartPoint(start);
			path.setEndPoint(end);

			if (!constraint.isEmpty()) {
				PointList bends = new PointList(constraint.size());
				for (int i = 0; i < constraint.size(); i++) {
					Bendpoint bp = (Bendpoint) constraint.get(i);
					bends.addPoint(bp.getLocation());
				}
				path.setBendPoints(bends);
			} else
				path.setBendPoints(null);

			isDirty |= path.isDirty;
		}
		staleConnections.clear();
	}

	void queueSomeRouting() {
		if (connectionToPaths == null || connectionToPaths.isEmpty())
			return;
		try {
			ignoreInvalidate = true;
			((Connection) connectionToPaths.keySet().iterator().next())
					.revalidate();
		} finally {
			ignoreInvalidate = false;
		}
	}

	/**
	 * @see ConnectionRouter#remove(Connection)
	 */
	public void remove(Connection connection) {
		staleConnections.remove(connection);
		constraintMap.remove(connection);
		if (connectionToPaths == null)
			return;
		Path path = (Path) connectionToPaths.remove(connection);
		algorithm.removePath(path);
		isDirty = true;
		if (connectionToPaths.isEmpty()) {
			unhookAll();
			connectionToPaths = null;
		} else {
			// Make sure one of the remaining is revalidated so that we can
			// re-route again.
			queueSomeRouting();
		}
	}

	void removeChild(IFigure child) {
		if (connectionToPaths == null)
			return;
		Rectangle bounds = child.getBounds().getCopy();
		boolean change = algorithm.removeObstacle(bounds);
		figuresToBounds.remove(child);
		child.removeFigureListener(figureListener);
		if (change) {
			isDirty = true;
			queueSomeRouting();
		}
	}

	/**
	 * @see ConnectionRouter#route(Connection)
	 */
	public void route(Connection conn) {
		if (isDirty) {
			ignoreInvalidate = true;
			processStaleConnections();
			isDirty = false;
			List updated = algorithm.solve();
			Connection current;
			for (int i = 0; i < updated.size(); i++) {
				Path path = (Path) updated.get(i);
				current = (Connection) path.data;
				current.revalidate();

				PointList points = path.getPoints().getCopy();
				Point ref1, ref2, start, end;
				ref1 = new PrecisionPoint(points.getPoint(1));
				ref2 = new PrecisionPoint(points.getPoint(points.size() - 2));
				current.translateToAbsolute(ref1);
				current.translateToAbsolute(ref2);

				start = current.getSourceAnchor().getLocation(ref1).getCopy();
				end = current.getTargetAnchor().getLocation(ref2).getCopy();

				current.translateToRelative(start);
				current.translateToRelative(end);
				points.setPoint(start, 0);
				points.setPoint(end, points.size() - 1);

				current.setPoints(points);
			}
			ignoreInvalidate = false;
		}
	}

	/**
	 * @return All connection paths after routing dirty paths. Some of the paths
	 *         that were not dirty may change as well, as a consequence of new
	 *         routings.
	 * @since 3.5
	 */
	public List getPathsAfterRouting() {
		if (isDirty) {
			processStaleConnections();
			isDirty = false;
			List all = algorithm.solve();
			return all;

		}
		return null;
	}

	/**
	 * @see ConnectionRouter#setConstraint(Connection, Object)
	 */
	public void setConstraint(Connection connection, Object constraint) {
		// Connection.setConstraint() already calls revalidate, so we know that
		// a
		// route() call will follow.
		staleConnections.add(connection);
		constraintMap.put(connection, constraint);
		isDirty = true;
	}

	/**
	 * Sets the default space that should be maintained on either side of a
	 * connection. This causes the connections to be separated from each other
	 * and from the obstacles. The default value is 4.
	 * 
	 * @param spacing
	 *            the connection spacing
	 * @since 3.2
	 */
	public void setSpacing(int spacing) {
		algorithm.setSpacing(spacing);
	}

	/**
	 * @return true if there are connections routed by this router, false
	 *         otherwise
	 * @since 3.5
	 */
	public boolean hasMoreConnections() {
		return connectionToPaths != null && !connectionToPaths.isEmpty();
	}

	/**
	 * @return the container which contains connections routed by this router
	 * @since 3.5
	 */
	public IFigure getContainer() {
		return container;
	}

	/**
	 * Sets the value indicating if connection invalidation should be ignored.
	 * 
	 * @param b
	 *            true if invalidation should be skipped, false otherwise
	 * @since 3.5
	 */
	public void setIgnoreInvalidate(boolean b) {
		ignoreInvalidate = b;
	}

	/**
	 * Returns the value indicating if connection invalidation should be
	 * ignored.
	 * 
	 * @return true if invalidation should be skipped, false otherwise
	 * @since 3.5
	 */
	public boolean shouldIgnoreInvalidate() {
		return ignoreInvalidate;
	}

	/**
	 * Returns the value indicating if the router is dirty, i.e. if there are
	 * any outstanding connections that need to be routed
	 * 
	 * @return true if there are connections to be routed, false otherwise
	 * @since 3.5
	 */
	public boolean isDirty() {
		return isDirty;
	}

	/**
	 * Returns true if the given connection is routed by this router, false
	 * otherwise
	 * 
	 * @param conn
	 *            Connection whose router is questioned
	 * @return true if this is the router used for conn
	 * @since 3.5
	 */
	public boolean containsConnection(Connection conn) {
		return connectionToPaths != null && connectionToPaths.containsKey(conn);
	}

}