org.eclipse.gmf.runtime.draw2d.ui/src/org/eclipse/gmf/runtime/draw2d/ui/graph/EdgeEndPointsAssignment.java

/******************************************************************************
 * Copyright (c) 2008 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.gmf.runtime.draw2d.ui.graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import org.eclipse.draw2d.PositionConstants;
import org.eclipse.draw2d.geometry.Dimension;
import org.eclipse.draw2d.geometry.Point;
import org.eclipse.draw2d.graph.DirectedGraph;
import org.eclipse.draw2d.graph.Edge;
import org.eclipse.draw2d.graph.EdgeList;
import org.eclipse.draw2d.graph.Node;

/**
 * Assigns the locations to edges end points as well as lays out border nodes
 * 
 * @author aboyko
 * @since 2.1
 */
class EdgeEndPointsAssignment {
	
	private DirectedGraph graph;
	
	public EdgeEndPointsAssignment(DirectedGraph g) {
		this.graph = g;
	}	
	
	void assignEdgesEndPoints() {
		for (int i = 0; i < graph.edges.size(); i++) {
			Edge e = graph.edges.getEdge(i);
			e.start = null;
			e.end = null;
		}
		
		Collections.sort(graph.nodes, new Comparator<Node>() {
			public int compare(Node arg0, Node arg1) {
				return arg0.width - arg1.width;
			}
		});
		
		for (int i = 0; i < graph.nodes.size(); i++) {
			Node node = graph.nodes.getNode(i);
			assignEndPointsForEdgesFromNode(node);
		}
	}
	
	private void assignEndPointsForEdgesFromNode(Node node) {
		EdgeList incoming = new EdgeList(), outgoing = new EdgeList();
		List<BorderNode> specialBorderNodes = new ArrayList<BorderNode>();
		if (node instanceof ConstantSizeNode) {
			initEdgesSets((ConstantSizeNode)node, incoming, outgoing, specialBorderNodes);
		} else {
			incoming = node.incoming;
			outgoing = node.outgoing;
		}
		
		if (node instanceof ConstantSizeNode && ((ConstantSizeNode)node).minIncomingPadding > 0) {
			assignEdgesEndPoints(incoming, (ConstantSizeNode) node, true);
		} else {
			for (int i = 0; i < incoming.size(); i++) {
				setEndPoint(incoming.getEdge(i), new Point(node.x + node.getOffsetIncoming(), node.y));
			}
		}
		
		if (node instanceof ConstantSizeNode && ((ConstantSizeNode)node).minOutgoingPadding > 0) {
			assignEdgesEndPoints(outgoing, (ConstantSizeNode) node, false);
		} else {
			for (int i = 0; i < outgoing.size(); i++) {
				setStartPoint(outgoing.getEdge(i), new Point(node.x + node.getOffsetOutgoing(), node.y + node.height));
			}
		}
		
		if (node instanceof ConstantSizeNode) {
			assignEndPointsForJointEdgeWithIncomingAndOutgoingEdges((ConstantSizeNode)node, specialBorderNodes);
		}
	}
	
	private void initEdgesSets(ConstantSizeNode n, EdgeList incoming, EdgeList outgoing, List<BorderNode> specialBorderNodes) {
		for (int i = 0; i < n.outgoing.size(); i++) {
			Edge e = n.outgoing.getEdge(i);
			if (e instanceof ConstrainedEdge) {
				ConstrainedEdge ce = (ConstrainedEdge) e;
				if (ce.sourceConstraint != null) {
					continue;
				}
			}
			outgoing.add(e);
		}
		
		for (int i = 0;  i < n.incoming.size(); i++) {
			Edge e = n.incoming.getEdge(i);
			if (e instanceof ConstrainedEdge) {
				ConstrainedEdge ce = (ConstrainedEdge) e;
				if (ce.targetConstraint != null) {
					continue;
				}
			}
			incoming.add(e);
		}
		
		for (Iterator<BorderNode> itr = n.borderNodes.iterator(); itr.hasNext();) {
			BorderNode borderNode = itr.next();
			if (!(borderNode.incomingJointEdges.edges.isEmpty() ^ borderNode.outgoingJointEdges.edges.isEmpty())) {
				specialBorderNodes.add(borderNode);
			} else if (borderNode.incomingJointEdges.edges.isEmpty()) {
				outgoing.add(borderNode.outgoingJointEdges);
			} else {
				incoming.add(borderNode.incomingJointEdges);
			}
		}
		
		Collections.sort(incoming, new Comparator<Edge>() {
			public int compare(Edge e1, Edge e2) {
				return GraphUtilities.getIncomingEdgeBendpointX(e1, graph) - GraphUtilities.getIncomingEdgeBendpointX(e2, graph);
			}
		});
		
		Collections.sort(outgoing, new Comparator<Edge>() {
			public int compare(Edge e1, Edge e2) {
				return GraphUtilities.getOutogingEdgeBendpointX(e1, graph) - GraphUtilities.getOutogingEdgeBendpointX(e2, graph);
			}
		});
	}

	private void assignEdgesEndPoints(EdgeList edges, ConstantSizeNode n, boolean end) {
		int leftIndex;
		int rightIndex;
		int padding = end ? n.minIncomingPadding : n.minOutgoingPadding;
		int leftX = n.x;
		int rightX = n.x + n.width;
		int leftBendpointX = 0;
		int rightBendpointX = 0;
		for (leftIndex = 0; leftIndex < edges.size(); leftIndex++) {
			Edge e = edges.getEdge(leftIndex);
			leftBendpointX = end ? GraphUtilities.getIncomingEdgeBendpointX(e, graph) : GraphUtilities.getOutogingEdgeBendpointX(e, graph);			
			if (leftX < leftBendpointX && leftBendpointX < rightX && (float)(leftBendpointX - leftX)/(leftIndex + 1) >= padding) {
				break;
			}
		}
		for (rightIndex = edges.size() - 1; rightIndex >= leftIndex; rightIndex--) {
			Edge e = edges.getEdge(rightIndex);
			rightBendpointX = end ? GraphUtilities.getIncomingEdgeBendpointX(e, graph) : GraphUtilities.getOutogingEdgeBendpointX(e, graph);			
			if (leftX < rightBendpointX && rightBendpointX < rightX && (float)(rightX - rightBendpointX)/(edges.size() - rightIndex) >= padding) {
				break;
			}
		}
		
		int y = end ? n.y : n.y + n.height;
		if (rightIndex >= leftIndex) {
			uniformlyPadEdges(edges, 0, leftIndex, new Point(leftX, y), new Point(leftBendpointX, y), end);
			uniformlyPadEdges(edges, rightIndex + 1, edges.size(), new Point(rightBendpointX, y), new Point(rightX, y), end);
			makeStraight(edges, leftIndex, rightIndex + 1, end);
		} else {
			uniformlyPadEdges(edges, 0, edges.size(), new Point(leftX, y), new Point(rightX, y), end);
		}
	}
	
	private void uniformlyPadEdges(List edges, int startIndex, int endIndex, Point startPoint, Point endPoint, boolean end) {
		Dimension diff = endPoint.getDifference(startPoint);
		int numPieces = endIndex - startIndex + 1;
		for (int i = startIndex; i < endIndex; i++) {
			Edge e = (Edge) edges.get(i);
			float coefficient = (float) (i - startIndex + 1) / numPieces;
			Point p = startPoint.getCopy().translate(diff.getCopy().scale(coefficient));
			if (end) {
				setEndPoint(e, p);
			} else {
				setStartPoint(e, p);
			}
		}
	}
	
	private void makeStraight(EdgeList edges, int startIndex, int endIndex, boolean end) {
		for (int i = startIndex; i < endIndex; i++) {
			Edge e = edges.getEdge(i);
			int y = end ? e.target.y : e.source.y + e.source.height;
			if (e instanceof ConstrainedEdge) {
				ConstrainedEdge ce = (ConstrainedEdge) e;
				if (end && ce.targetConstraint != null) {
					y = ce.targetConstraint.y;
				} else if (!end && ce.sourceConstraint != null) {
					y = ce.sourceConstraint.y + ce.sourceConstraint.height;
				}
			}
			if (end) {
				setEndPoint(e, new Point(GraphUtilities.getIncomingEdgeBendpointX(e, graph), y));
			} else {
				setStartPoint(e, new Point(GraphUtilities.getOutogingEdgeBendpointX(e, graph), y));
			}
		}
	}
	
	private void setStartPoint(Edge e, Point p) {
		if (e instanceof JointEdges) {
			JointEdges je = (JointEdges) e;
			je.getJoint().setPoint(p);
			assignEndPointsForEdgesFromBorderNode(je.getJoint());
		} else {
			if (p == null) {
				if (e instanceof ConstrainedEdge && ((ConstrainedEdge) e).sourceConstraint != null) {
					p = ((ConstrainedEdge) e).sourceConstraint.getEdgesDefaultEndPoint();
				} else {
					p = new Point(e.source.x + e.source.getOffsetOutgoing(), e.source.y + e.source.height);
				}
			}
			e.start = p;
		}
	}
	
	private void setEndPoint(Edge e, Point p) {
		if (e instanceof JointEdges) {
			JointEdges je = (JointEdges) e;
			je.getJoint().setPoint(p);
			assignEndPointsForEdgesFromBorderNode(je.getJoint());
		} else {
			if (p == null) {
				if (e instanceof ConstrainedEdge && ((ConstrainedEdge) e).targetConstraint != null) {
					p = ((ConstrainedEdge) e).targetConstraint.getEdgesDefaultEndPoint();
				} else {
					p = new Point(e.target.x + e.target.getOffsetIncoming(), e.target.y);
				}
			}
			e.end = p;
		}
	}
	
	private void assignEndPointsForJointEdgeWithIncomingAndOutgoingEdges(ConstantSizeNode node, List<BorderNode> specialBorderNodes) {
		Collections.sort(specialBorderNodes, new Comparator<BorderNode>() {
			public int compare(BorderNode bn1, BorderNode bn2) {
				return bn1.incomingJointEdges.edges.size() + bn1.outgoingJointEdges.edges.size() - bn2.incomingJointEdges.edges.size() - bn2.outgoingJointEdges.edges.size(); 
			}
		});
		
		List<BorderNode> leftSideBorderNodes = new ArrayList<BorderNode>(specialBorderNodes.size() / 2 + 1);
		List<BorderNode> rightSideBorderNodes = new ArrayList<BorderNode>(specialBorderNodes.size() / 2 + 1);
		
		for (Iterator<BorderNode> itr = specialBorderNodes.iterator(); itr.hasNext();) {
			leftSideBorderNodes.add(itr.next());
			itr.remove();
			if (itr.hasNext()) {
				rightSideBorderNodes.add(itr.next());
				itr.remove();
			}
		}
		
		Collections.sort(leftSideBorderNodes, new Comparator<BorderNode>() {
			public int compare(BorderNode bn1, BorderNode bn2) {
				return bn1.outgoingJointEdges.edges.size() - bn1.incomingJointEdges.edges.size() - (bn2.outgoingJointEdges.edges.size() - bn2.incomingJointEdges.edges.size());
			}		
		});
		Collections.sort(rightSideBorderNodes, new Comparator<BorderNode>() {
			public int compare(BorderNode bn1, BorderNode bn2) {
				return bn1.outgoingJointEdges.edges.size() - bn1.incomingJointEdges.edges.size() - (bn2.outgoingJointEdges.edges.size() - bn2.incomingJointEdges.edges.size());
			}		
		});
		
		uniformlyPadBorderNodes(leftSideBorderNodes, 0, leftSideBorderNodes.size(), new Point(node.x, node.y), new Point(node.x, node.y + node.height));
		uniformlyPadBorderNodes(rightSideBorderNodes, 0, rightSideBorderNodes.size(), new Point(node.x + node.width, node.y), new Point(node.x + node.width, node.y + node.height));
		
		for (Iterator<BorderNode> itr = leftSideBorderNodes.iterator(); itr.hasNext();) {
			BorderNode bn = itr.next();
			if (!bn.incomingJointEdges.edges.isEmpty() || !bn.outgoingJointEdges.edges.isEmpty()) {
				assignEndPointsForEdgesFromBorderNode(bn);
			}
		}
		for (Iterator<BorderNode> itr = rightSideBorderNodes.iterator(); itr.hasNext();) {
			BorderNode bn = itr.next();
			if (!bn.incomingJointEdges.edges.isEmpty() || !bn.outgoingJointEdges.edges.isEmpty()) {
				assignEndPointsForEdgesFromBorderNode(bn);
			}
		}		
	}
	
	private void uniformlyPadBorderNodes(List<BorderNode> borderNodes, int startIndex, int endIndex, Point startPoint, Point endPoint) {
		Dimension diff = endPoint.getDifference(startPoint);
		int numPieces = endIndex - startIndex + 1;
		for (int i = startIndex; i < endIndex; i++) {
			float coefficient = (float) (i - startIndex + 1) / numPieces;
			Point p = startPoint.getCopy().translate(diff.getCopy().scale(coefficient));
			borderNodes.get(i).setPoint(p);
		}
		
	}
	
	private void assignEndPointsForEdgesFromBorderNode(BorderNode node) {
		Collections.sort(node.incomingJointEdges.edges, new Comparator<Edge>() {
			public int compare(Edge e1, Edge e2) {
				return GraphUtilities.getIncomingEdgeBendpointX(e1, graph) - GraphUtilities.getIncomingEdgeBendpointX(e2, graph);				}
		});
		Collections.sort(node.outgoingJointEdges.edges, new Comparator<Edge>() {
			public int compare(Edge e1, Edge e2) {
				return GraphUtilities.getOutogingEdgeBendpointX(e1, graph) - GraphUtilities.getOutogingEdgeBendpointX(e2, graph);				}
		});
		if (node.minIncomingPadding > 0 || node.minOutgoingPadding > 0) {
			if (node.position == PositionConstants.NORTH) {
				assignEdgesEndPoints(node.incomingJointEdges.edges, node, true);
			} else if (node.position == PositionConstants.SOUTH) {
				assignEdgesEndPoints(node.outgoingJointEdges.edges, node, false);
			} else {
				Point incomingStartPt, incomingEndPt, outgoingStartPt, outgoingEndPt;
				if (node.position == PositionConstants.WEST) {
					incomingStartPt = new Point(node.x, node.y + (node.incomingJointEdges.edges.size() + 1) * node.height / (node.incomingJointEdges.edges.size() + node.outgoingJointEdges.edges.size() + 1));
					incomingEndPt = new Point(node.x, node.y);
					outgoingStartPt = new Point(node.x, node.y + node.incomingJointEdges.edges.size() * node.height / (node.incomingJointEdges.edges.size() + node.outgoingJointEdges.edges.size() + 1));
					outgoingEndPt = new Point(node.x, node.y + node.height);
				} else {
					incomingStartPt = new Point(node.x + node.width, node.y);
					incomingEndPt = new Point(node.x + node.width, node.y + (node.incomingJointEdges.edges.size() + 1) * node.height / (node.incomingJointEdges.edges.size() + node.outgoingJointEdges.edges.size() + 1));
					outgoingStartPt = new Point(node.x + node.width, node.y + node.height);
					outgoingEndPt = new Point(node.x + node.width, node.y + node.incomingJointEdges.edges.size() * node.height / (node.incomingJointEdges.edges.size() + node.outgoingJointEdges.edges.size() + 1));
				}
				uniformlyPadEdges(node.incomingJointEdges.edges, 0, node.incomingJointEdges.edges.size(), incomingStartPt, incomingEndPt, true);
				uniformlyPadEdges(node.outgoingJointEdges.edges, 0, node.outgoingJointEdges.edges.size(), outgoingStartPt, outgoingEndPt, false);	
			}
		} else {
			Point defaultPt = node.getEdgesDefaultEndPoint();
			for (int i = 0; i < node.incomingJointEdges.edges.size(); i++) {
				setEndPoint(node.incomingJointEdges.edges.getEdge(i), defaultPt);
			}
			for (int i = 0; i < node.outgoingJointEdges.edges.size(); i++) {
				setStartPoint(node.outgoingJointEdges.edges.getEdge(i), defaultPt);
			}
		}
	}
	
}