--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2011 Association for Decentralized Information Management in\r
+ * Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.diagram.connection;\r
+\r
+import gnu.trove.list.array.TDoubleArrayList;\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.map.hash.TObjectIntHashMap;\r
+import gnu.trove.set.hash.THashSet;\r
+\r
+import java.awt.geom.Line2D;\r
+import java.awt.geom.Path2D;\r
+import java.awt.geom.Rectangle2D;\r
+import java.io.PrintStream;\r
+import java.io.Serializable;\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.Collections;\r
+import java.util.Iterator;\r
+\r
+import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;\r
+import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;\r
+import org.simantics.diagram.connection.segments.Segment;\r
+import org.simantics.diagram.connection.splitting.SplittedRouteGraph;\r
+\r
+public class RouteGraph implements Serializable {\r
+\r
+ private static final long serialVersionUID = 2004022454972623908L;\r
+\r
+ public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;\r
+ public static final boolean CHECK_PARAMERS = true;\r
+\r
+ ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);\r
+ ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);\r
+ ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);\r
+ int caseId;\r
+ boolean isSimpleConnection;\r
+ boolean needsUpdate = false;\r
+\r
+ /**\r
+ * Adds a route line to the graph.\r
+ * @param isHorizontal true, if the line is horizontal\r
+ * @param position y coordinate of the line if horizontal, x coordinate if vertical\r
+ * @return The new line.\r
+ */\r
+ public RouteLine addLine(boolean isHorizontal, double position) {\r
+ RouteLine line = new RouteLine(isHorizontal, position); \r
+ lines.add(line);\r
+ return line;\r
+ }\r
+\r
+ /**\r
+ * Adds a route terminal to the graph.\r
+ * @param x The location of the terminal.\r
+ * @param y \r
+ * @param minX The avoidance area of the terminal.\r
+ * @param minY\r
+ * @param maxX\r
+ * @param maxY\r
+ * @param allowedDirections Allowed directions. \r
+ * First four bits tell with which directions\r
+ * a connection can leave the terminal. The\r
+ * Fifth bit indicates whether direct lines\r
+ * can be drawn to the terminal. Directions are\r
+ * <pre>\r
+ * 0 right (1,0)\r
+ * 1 down (0,1)\r
+ * 2 left (-1,0)\r
+ * 3 up (0,-1)\r
+ * </pre>\r
+ * @param style Tells what kind of line end is drawn \r
+ * to the connection.\r
+ * @return The new terminal.\r
+ */\r
+ public RouteTerminal addTerminal(double x, double y, \r
+ double minX, double minY,\r
+ double maxX, double maxY, \r
+ int allowedDirections,\r
+ ILineEndStyle style) {\r
+ return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null);\r
+ \r
+ }\r
+ public RouteTerminal addTerminal(double x, double y, \r
+ double minX, double minY,\r
+ double maxX, double maxY, \r
+ int allowedDirections,\r
+ ILineEndStyle style, ILineEndStyle dynamicStyle) {\r
+ if(CHECK_PARAMERS) {\r
+ if(allowedDirections > 0x1f)\r
+ throw new IllegalArgumentException("Illegal allowedDirection flags.");\r
+ if(minX > x || x > maxX || minY > y || y > maxY)\r
+ throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");\r
+ }\r
+ if(style == null)\r
+ style = PlainLineEndStyle.INSTANCE;\r
+ RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,\r
+ maxX, maxY, allowedDirections, false, style); \r
+ terminal.setDynamicStyle(dynamicStyle);\r
+ terminals.add(terminal);\r
+ return terminal;\r
+ }\r
+ \r
+ public RouteTerminal addBigTerminal( \r
+ double minX, double minY,\r
+ double maxX, double maxY,\r
+ ILineEndStyle style) {\r
+ return addBigTerminal(minX, minY, maxX, maxY, style, null);\r
+ }\r
+ public RouteTerminal addBigTerminal( \r
+ double minX, double minY,\r
+ double maxX, double maxY,\r
+ ILineEndStyle style, ILineEndStyle dynamicStyle) {\r
+ if(style == null)\r
+ style = PlainLineEndStyle.INSTANCE;\r
+ RouteTerminal terminal = new RouteTerminal(\r
+ 0.5*(minX+maxX), 0.5*(minY+maxY),\r
+ minX, minY,\r
+ maxX, maxY, \r
+ 0xf, true, style); \r
+ terminal.setDynamicStyle(dynamicStyle);\r
+ \r
+ terminals.add(terminal);\r
+ return terminal;\r
+ }\r
+\r
+ /**\r
+ * Adds a route terminal to the graph. The avoidance\r
+ * area is given as a rectangle.\r
+ * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)\r
+ */\r
+ public RouteTerminal addTerminal(double x, double y, \r
+ Rectangle2D bounds, \r
+ int allowedDirections,\r
+ ILineEndStyle style) {\r
+ return addTerminal(x, y, \r
+ bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(), \r
+ allowedDirections, style);\r
+ }\r
+\r
+ /**\r
+ * Adds a copy of the given terminal to the graph.\r
+ */\r
+ public RouteTerminal addTerminal(RouteTerminal terminal) {\r
+ RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,\r
+ terminal.getMinX(), terminal.getMinY(),\r
+ terminal.getMaxX(), terminal.getMaxY(),\r
+ terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle());\r
+ newTerminal.setData(terminal.getData());\r
+ return terminal;\r
+ }\r
+\r
+ /**\r
+ * Adds a route terminal to the graph. A default line end style is used.\r
+ * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)\r
+ */\r
+ public RouteTerminal addTerminal(double x, double y, \r
+ double minX, double minY,\r
+ double maxX, double maxY, \r
+ int allowedDirections) {\r
+ return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, \r
+ PlainLineEndStyle.INSTANCE);\r
+ }\r
+ \r
+ /**\r
+ * Links nodes.\r
+ */\r
+ public void link(RouteNode node1, RouteNode node2) {\r
+ if(node1 instanceof RouteLine) {\r
+ if(node2 instanceof RouteLine) {\r
+ link((RouteLine)node1, (RouteLine)node2);\r
+ }\r
+ else {\r
+ link((RouteLine)node1, (RouteTerminal)node2);\r
+ }\r
+ }\r
+ else {\r
+ if(node2 instanceof RouteLine) {\r
+ link((RouteTerminal)node1, (RouteLine)node2);\r
+ }\r
+ else {\r
+ link((RouteTerminal)node1, (RouteTerminal)node2);\r
+ }\r
+ }\r
+ }\r
+ \r
+ /**\r
+ * Links nodes.\r
+ */\r
+ public void link(RouteNode ... nodes) {\r
+ for(int i=1;i<nodes.length;++i)\r
+ link(nodes[i-1], nodes[i]);\r
+ }\r
+ \r
+ /**\r
+ * Links lines.\r
+ */\r
+ public void link(RouteLine node1, RouteLine node2) {\r
+ new RouteLink(node1, node2);\r
+ needsUpdate = true;\r
+ }\r
+ \r
+ /**\r
+ * Links a terminal and a line.\r
+ */\r
+ public void link(RouteTerminal node1, RouteLine node2) {\r
+ if(CHECK_PARAMERS) {\r
+ if(node2 == null)\r
+ throw new NullPointerException();\r
+ if(node1.line != null)\r
+ throw new IllegalStateException("Terminal is already connected.");\r
+ }\r
+ node1.line = node2;\r
+ needsUpdate = true;\r
+ }\r
+\r
+ /**\r
+ * Links a line and a terminal.\r
+ */\r
+ public void link(RouteLine node1, RouteTerminal node2) {\r
+ if(CHECK_PARAMERS) {\r
+ if(node1 == null)\r
+ throw new NullPointerException();\r
+ if(node2.line != null)\r
+ throw new IllegalStateException("Terminal is already connected.");\r
+ }\r
+ node2.line = node1;\r
+ needsUpdate = true;\r
+ }\r
+\r
+ /**\r
+ * Links two terminals.\r
+ */\r
+ public void link(RouteTerminal node1, RouteTerminal node2) {\r
+ if(CHECK_PARAMERS) {\r
+ if(node1 == null)\r
+ throw new NullPointerException();\r
+ if(node2 == null)\r
+ throw new NullPointerException();\r
+ }\r
+ isSimpleConnection = true;\r
+ needsUpdate = true;\r
+ }\r
+ \r
+ void removeTransientRouteLines() {\r
+ for(RouteLine line : transientLines)\r
+ line.remove();\r
+ transientLines.clear();\r
+ }\r
+ \r
+ /**\r
+ * Rotates given terminal clockwise by given amount\r
+ * (also negative numbers are allowed). \r
+ */\r
+ public void rotate(RouteTerminal terminal, int amount) {\r
+ terminal.rotate(amount);\r
+ needsUpdate = true;\r
+ }\r
+ \r
+ /**\r
+ * Moves the given route line so that its position correspond\r
+ * to given x or y depending on the orientation of the line. \r
+ */\r
+ public void setLocation(RouteLine line, double x, double y) {\r
+ makePersistent(line);\r
+ line.setLocation(x, y);\r
+ needsUpdate = true;\r
+ }\r
+ \r
+ /**\r
+ * Moves the terminal to given location.\r
+ */\r
+ public void setLocation(RouteTerminal terminal, double x, double y) {\r
+ terminal.setLocation(x, y);\r
+ needsUpdate = true;\r
+ }\r
+\r
+ /**\r
+ * Updates transient route lines, route link positions\r
+ * and sorts route points of each route line.\r
+ */\r
+ public void update() {\r
+ needsUpdate = false;\r
+ removeTransientRouteLines();\r
+\r
+ //print();\r
+ \r
+ for(RouteLine line : lines)\r
+ line.hidden = false;\r
+ for(RouteTerminal terminal : terminals)\r
+ if(terminal.hasDirectConnection() && terminal.line != null)\r
+ terminal.line.hidden = true;\r
+\r
+ // Choose a strategy\r
+ if(isSimpleConnection) {\r
+ RouteTerminal a = terminals.get(0);\r
+ RouteTerminal b = terminals.get(1);\r
+ if(a.hasDirectConnection() || b.hasDirectConnection())\r
+ return;\r
+ caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);\r
+ //System.out.println("caseId = " + caseId);\r
+ switch(caseId) {\r
+ case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION: \r
+ case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {\r
+ boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;\r
+ RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);\r
+ line.addPoint(a);\r
+ line.addPoint(b);\r
+ line.terminal = a;\r
+ transientLines.add(line);\r
+ break;\r
+ }\r
+ case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {\r
+ RouteLine line1 = new RouteLine(true, a.y);\r
+ RouteLine line2 = new RouteLine(false, b.x);\r
+ new RouteLink(line1, line2);\r
+ line1.addPoint(a);\r
+ line2.addPoint(b);\r
+ line1.terminal = a;\r
+ line2.terminal = b;\r
+ transientLines.add(line1);\r
+ transientLines.add(line2);\r
+ break;\r
+ }\r
+ case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {\r
+ RouteLine line1 = new RouteLine(false, a.x);\r
+ RouteLine line2 = new RouteLine(true, b.y);\r
+ new RouteLink(line1, line2);\r
+ line1.addPoint(a);\r
+ line2.addPoint(b);\r
+ line1.terminal = a;\r
+ line2.terminal = b;\r
+ transientLines.add(line1);\r
+ transientLines.add(line2);\r
+ break;\r
+ }\r
+ case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT: \r
+ case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {\r
+ RouteLine line =\r
+ SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),\r
+ caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )\r
+ ;\r
+ terminals.get(0).line = line;\r
+ terminals.get(1).line = line;\r
+ transientLines.add(line);\r
+ routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ else {\r
+ caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;\r
+ routeFromTerminals(false);\r
+ }\r
+ \r
+ // Find positions of route points\r
+ for(RouteLine line : lines) \r
+ line.setPointPositions();\r
+ for(RouteLine line : transientLines) \r
+ line.setPointPositions();\r
+ \r
+ // Sort route points in route lines\r
+ for(RouteLine line : lines) {\r
+ line.sortPoints();\r
+ }\r
+ for(RouteLine line : transientLines) {\r
+ line.sortPoints();\r
+ }\r
+ }\r
+ \r
+ static class Interval {\r
+ public final double min;\r
+ public final double max;\r
+ public Interval(double min, double max) {\r
+ this.min = min;\r
+ this.max = max;\r
+ }\r
+ }\r
+ \r
+ class IntervalCache {\r
+ THashMap<RouteLine, Interval> cache = \r
+ new THashMap<RouteLine, Interval>();\r
+ public Interval get(RouteLine line) {\r
+ Interval result = cache.get(line);\r
+ if(result != null)\r
+ return result;\r
+ \r
+ result = create(line);\r
+ cache.put(line, result);\r
+ return result;\r
+ }\r
+ \r
+ private Interval create(RouteLine line) {\r
+ double min = Double.POSITIVE_INFINITY;\r
+ double max = Double.NEGATIVE_INFINITY;\r
+ \r
+ for(RoutePoint point : line.points) {\r
+ double temp;\r
+ if(point instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)point;\r
+ if(link.a == line)\r
+ temp = link.b.position;\r
+ else\r
+ temp = link.a.position;\r
+ }\r
+ else {\r
+ RouteTerminal terminal = (RouteTerminal)point;\r
+ if(line.isHorizontal)\r
+ temp = terminal.x;\r
+ else\r
+ temp = terminal.y;\r
+ }\r
+ if(temp < min)\r
+ min = temp;\r
+ if(temp > max)\r
+ max = temp;\r
+ }\r
+ for(RouteTerminal terminal : terminals) {\r
+ if(terminal.line == line) {\r
+ double temp = terminal.approximatePositionToLine();\r
+ if(temp < min)\r
+ min = temp;\r
+ if(temp > max)\r
+ max = temp;\r
+ }\r
+ }\r
+ \r
+ return new Interval(min, max);\r
+ }\r
+ } \r
+ \r
+ private void routeFromTerminals(boolean boundingBoxesIntersect) {\r
+ IntervalCache cache = new IntervalCache();\r
+ for(RouteTerminal terminal : terminals) \r
+ if(terminal.line != null) {\r
+ if(!terminal.hasDirectConnection())\r
+ terminal.route(transientLines, cache, boundingBoxesIntersect);\r
+ }\r
+ }\r
+ \r
+ /**\r
+ * Returns a RouteLine near the given point (x,y) (within tolerance).\r
+ */\r
+ public RouteLine pickLine(double x, double y, double tolerance, int mask) {\r
+ if(needsUpdate)\r
+ update();\r
+ if(isSimpleConnection && transientLines.isEmpty()) {\r
+ if(terminals.size() == 2) {\r
+ if((mask & PICK_TRANSIENT_LINES) == 0)\r
+ return null;\r
+ RouteTerminal a = terminals.get(0);\r
+ RouteTerminal b = terminals.get(1);\r
+ if(a.hasDirectConnection() || b.hasDirectConnection()) {\r
+ if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {\r
+ RouteLine dummy = new RouteLine(false, y);\r
+ return dummy; // There are no lines to return\r
+ }\r
+ else\r
+ return null;\r
+ }\r
+ }\r
+ }\r
+ if((mask & PICK_PERSISTENT_LINES) != 0)\r
+ for(RouteLine line : lines)\r
+ if(line.isNear(x, y, tolerance))\r
+ return line;\r
+ if((mask & PICK_TRANSIENT_LINES) != 0)\r
+ for(RouteLine line : transientLines)\r
+ if(line.isNear(x, y, tolerance))\r
+ return line;\r
+ if((mask & PICK_DIRECT_LINES) != 0) {\r
+ RouteTerminal terminal = pickDirectLine(x, y, tolerance);\r
+ if(terminal != null)\r
+ return terminal.line;\r
+ }\r
+ return null;\r
+ }\r
+ \r
+ public RouteLine pickLine(double x, double y, double tolerance) {\r
+ return pickLine(x, y, tolerance, PICK_LINES);\r
+ }\r
+ \r
+ private RouteTerminal pickDirectLine(double x, double y, double tolerance) {\r
+ double toleranceSq = tolerance * tolerance;\r
+ for(RouteTerminal terminal : terminals)\r
+ if((terminal.getAllowedDirections()&0x10) != 0) { \r
+ try {\r
+ RouteLine line = terminal.getLine();\r
+ if(line == null)\r
+ continue;\r
+ RoutePoint b = line.getBegin();\r
+ double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y); \r
+ if(distSq <= toleranceSq) {\r
+ //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);\r
+ return terminal;\r
+ }\r
+ } catch(NullPointerException e) {\r
+ //if terminal does not have a line\r
+ e.printStackTrace();\r
+ } catch(IndexOutOfBoundsException e) {\r
+ // if line does not contain points\r
+ e.printStackTrace();\r
+ }\r
+ }\r
+ return null;\r
+ }\r
+\r
+ public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {\r
+ if(isSimpleConnection)\r
+ return null;\r
+ if(needsUpdate)\r
+ update();\r
+ RouteLine line = pickLine(x, y, tolerance);\r
+ if(line == null)\r
+ return null;\r
+ RouteLink link = null;\r
+ RoutePoint begin = line.getBegin();\r
+ RoutePoint end = line.getEnd();\r
+ if(line.isHorizontal) {\r
+ double mx = 0.5*(begin.getX() + end.getX());\r
+ if(x < mx) {\r
+ if(begin instanceof RouteLink)\r
+ link = (RouteLink)begin;\r
+ }\r
+ else {\r
+ if(end instanceof RouteLink)\r
+ link = (RouteLink)line.getEnd();\r
+ }\r
+ }\r
+ else {\r
+ double my = 0.5*(begin.getY() + end.getY());\r
+ if(y < my) {\r
+ if(begin instanceof RouteLink)\r
+ link = (RouteLink)begin;\r
+ }\r
+ else {\r
+ if(end instanceof RouteLink)\r
+ link = (RouteLink)end;\r
+ }\r
+ }\r
+ if(link == null)\r
+ return null;\r
+ if(link.getOther(line).isTransient())\r
+ return null;\r
+ return new RouteLineHalf(line, link);\r
+ }\r
+\r
+ public Collection<RouteLineHalf> getLineHalves() {\r
+ return getLineHalves(new ArrayList<RouteLineHalf>());\r
+ }\r
+\r
+ public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {\r
+ for(RouteLine line : getAllLines()) {\r
+ {\r
+ RoutePoint p = line.getBegin();\r
+ if(p instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)p;\r
+ if(!link.getOther(line).isTransient())\r
+ result.add(new RouteLineHalf(line, link));\r
+ }\r
+ }\r
+ {\r
+ RoutePoint p = line.getEnd();\r
+ if(p instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)p;\r
+ if(!link.getOther(line).isTransient())\r
+ result.add(new RouteLineHalf(line, link));\r
+ }\r
+ }\r
+ }\r
+ return result;\r
+ }\r
+\r
+ /**\r
+ * Returns a RoutePoint near the given point (x,y) (within tolerance).\r
+ */\r
+ public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {\r
+ if(needsUpdate)\r
+ update();\r
+ if((mask&PICK_TERMINALS) != 0)\r
+ for(RouteTerminal terminal : terminals)\r
+ if(terminal.isNear(x, y))\r
+ return terminal;\r
+ if((mask&PICK_INTERIOR_POINTS) != 0) {\r
+ for(RouteLine line : lines) {\r
+ for(RoutePoint point : line.points)\r
+ if(point.isNear(x, y, tolerance))\r
+ return point;\r
+ }\r
+ for(RouteLine line : transientLines) {\r
+ for(RoutePoint point : line.points)\r
+ if(point.isNear(x, y, tolerance))\r
+ return point;\r
+ }\r
+ }\r
+ return null;\r
+ }\r
+ \r
+ public RoutePoint pickPoint(double x, double y, double tolerance) {\r
+ return pickPoint(x, y, tolerance, PICK_POINTS);\r
+ }\r
+ \r
+ public static final int PICK_INTERIOR_POINTS = 1;\r
+ public static final int PICK_TERMINALS = 2;\r
+ public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;\r
+ \r
+ public static final int PICK_PERSISTENT_LINES = 4;\r
+ public static final int PICK_TRANSIENT_LINES = 8;\r
+ public static final int PICK_DIRECT_LINES = 16;\r
+ public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;\r
+ \r
+ public static final int PICK_ALL = PICK_POINTS | PICK_LINES;\r
+ \r
+ /**\r
+ * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).\r
+ */\r
+ public Object pick(double x, double y, double tolerance, int mask) {\r
+ if((mask & PICK_POINTS) != 0) {\r
+ Object point = pickPoint(x, y, tolerance, mask);\r
+ if(point != null)\r
+ return point;\r
+ }\r
+ /*if((mask & PICK_DIRECT_LINES) != 0) {\r
+ RouteTerminal terminal = pickDirectLine(x, y, tolerance);\r
+ if(terminal != null)\r
+ return terminal.line.getBegin();\r
+ }*/\r
+ if((mask & PICK_LINES) != 0)\r
+ return pickLine(x, y, tolerance, mask);\r
+ else\r
+ return null;\r
+ }\r
+ \r
+ public Object pick(double x, double y, double tolerance) {\r
+ return pick(x, y, tolerance, PICK_ALL);\r
+ }\r
+ \r
+ /**\r
+ * Returns RoutePoint or RouteLine exactly under the given point (x,y).\r
+ */\r
+ public Object pick(double x, double y) {\r
+ return pick(x, y, 0.0);\r
+ }\r
+ \r
+ /**\r
+ * Prints the contents of the route graph to stdout.\r
+ */\r
+ public void print() {\r
+ print(System.out);\r
+ }\r
+ \r
+ /**\r
+ * Prints the contents of the route graph to given print stream.\r
+ */\r
+ public void print(PrintStream out) {\r
+ if(needsUpdate)\r
+ update();\r
+ if(isSimpleConnection)\r
+ out.println("=== SIMPLE CONNECTION ===");\r
+ else\r
+ out.println("=== COMPLEX CONNECTION ===");\r
+ for(RouteLine line : lines) {\r
+ out.print("perst");\r
+ line.print(out);\r
+ }\r
+ for(RouteLine line : transientLines) {\r
+ out.print("trans");\r
+ line.print(out);\r
+ }\r
+ for(RouteTerminal terminal : terminals) {\r
+ out.print("term");\r
+ terminal.print(out);\r
+ }\r
+ }\r
+\r
+ public void makePersistent(RouteLine line) {\r
+ prepareForModification();\r
+ if(isSimpleConnection || line.isTransient()) {\r
+ if(isSimpleConnection) {\r
+ isSimpleConnection = false;\r
+ for(RouteTerminal terminal : terminals)\r
+ terminal.line = line;\r
+ transientLines.remove(line);\r
+ lines.add(line); \r
+ Iterator<RoutePoint> it = line.points.iterator();\r
+ while(it.hasNext()) {\r
+ RoutePoint point = it.next();\r
+ if(point instanceof RouteTerminal)\r
+ it.remove();\r
+ }\r
+ line.terminal = null;\r
+ line.nextTransient = null;\r
+ }\r
+ else {\r
+ line.terminal.line = line;\r
+ do {\r
+ transientLines.remove(line);\r
+ lines.add(line); \r
+ Iterator<RoutePoint> it = line.points.iterator();\r
+ while(it.hasNext()) {\r
+ RoutePoint point = it.next();\r
+ if(point instanceof RouteTerminal)\r
+ it.remove();\r
+ }\r
+ line.terminal = null;\r
+ RouteLine temp = line.nextTransient;\r
+ line.nextTransient = null;\r
+ line = temp;\r
+ } while(line != null);\r
+ }\r
+ needsUpdate = true;\r
+ }\r
+ }\r
+\r
+ void prepareForModification() {\r
+ if(caseId == 4) {\r
+ RouteLine line = transientLines.remove(0);\r
+ line.terminal = null;\r
+ lines.add(line);\r
+ for(RouteTerminal terminal : terminals)\r
+ terminal.line = line;\r
+ isSimpleConnection = false;\r
+ caseId = 6;\r
+ }\r
+ }\r
+ \r
+ public double[] getLineLengths(RouteTerminal terminal) {\r
+ if(needsUpdate)\r
+ update();\r
+ if(lines.size()==0 && transientLines.size()==1)\r
+ return new double[] { transientLines.get(0).getLength() };\r
+ \r
+ RouteLine line = null;\r
+ fLoop:\r
+ for(RouteLine l : transientLines)\r
+ if(l.isTransient()) {\r
+ for(RoutePoint p : l.points)\r
+ if(!(p instanceof RouteLink)) {\r
+ line = l;\r
+ break fLoop;\r
+ }\r
+ }\r
+ TDoubleArrayList result = new TDoubleArrayList();\r
+ THashSet<RouteLine> set = new THashSet<RouteLine>();\r
+ set.add(line);\r
+ loop:\r
+ while(true) { \r
+ result.add(line.getLength());\r
+ for(RoutePoint point : line.points)\r
+ if(point instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)point; \r
+ if(set.add(link.a)) {\r
+ line = link.a;\r
+ continue loop;\r
+ }\r
+ if(set.add(link.b)) {\r
+ line = link.b;\r
+ continue loop;\r
+ }\r
+ }\r
+ break;\r
+ }\r
+ return result.toArray();\r
+ }\r
+\r
+ public void split(RouteLine rl1, double splitPosition) {\r
+ if(needsUpdate)\r
+ update();\r
+ boolean isHorizontal = rl1.isHorizontal();\r
+ if(isSimpleConnection) {\r
+ isSimpleConnection = false;\r
+ if(caseId < 2) {\r
+ RouteLine sp = addLine(!isHorizontal, splitPosition);\r
+ for(RouteTerminal terminal : terminals)\r
+ terminal.line = sp;\r
+ update();\r
+ return;\r
+ }\r
+ else if(caseId < 4) {\r
+ RouteLine sp = addLine(!isHorizontal, splitPosition);\r
+ RouteLine l = addLine(isHorizontal, rl1.position);\r
+ link(l, sp);\r
+ rl1.terminal.line = sp;\r
+ for(RouteTerminal terminal : terminals)\r
+ if(terminal != rl1.terminal)\r
+ terminal.line = l;\r
+ update();\r
+ return;\r
+ }\r
+ else\r
+ prepareForModification();\r
+ }\r
+\r
+ RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());\r
+ RouteLine sp = new RouteLine(!isHorizontal, splitPosition);\r
+\r
+ ArrayList<RoutePoint> points = rl1.points;\r
+\r
+ int splitPos;\r
+ {\r
+ int minPos = 0;\r
+ int maxPos = points.size();\r
+ while(minPos != maxPos) {\r
+ int c = (minPos + maxPos)/2;\r
+ if(isHorizontal \r
+ ? points.get(c).getX() > splitPosition \r
+ : points.get(c).getY() > splitPosition)\r
+ maxPos = c;\r
+ else\r
+ minPos = c+1;\r
+ }\r
+ splitPos = minPos;\r
+ }\r
+\r
+ for(int i=points.size()-1;i>=splitPos;--i) {\r
+ RoutePoint point = points.remove(i);\r
+ if(point instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)point;\r
+ link.replace(rl1, rl2);\r
+ }\r
+ }\r
+\r
+ if(rl1.isTransient()) {\r
+ boolean p1 = rl1.isConnectedToPeristentLine();\r
+ boolean p2 = rl2.isConnectedToPeristentLine();\r
+\r
+ RouteTerminal terminal = rl1.terminal;\r
+ if(p1) {\r
+ makePersistent(rl1);\r
+ transientLines.add(rl2);\r
+ }\r
+ else if(p2) {\r
+ lines.add(rl2);\r
+ }\r
+ else {\r
+ transientLines.add(rl2);\r
+ if(lines.isEmpty())\r
+ for(RouteTerminal t : terminals)\r
+ t.line = sp;\r
+ }\r
+ terminal.line = sp;\r
+ }\r
+ else\r
+ lines.add(rl2);\r
+\r
+ new RouteLink(rl1, sp);\r
+ new RouteLink(sp, rl2);\r
+ lines.add(sp);\r
+ update();\r
+ }\r
+\r
+ public boolean merge(RouteLine line) {\r
+ int count = 0;\r
+ double sum = 0;\r
+ for(RoutePoint point : line.points) {\r
+ if(point instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)point;\r
+ RouteLine other = link.getOther(line);\r
+ if(!other.isTransient()) {\r
+ sum += other.position;\r
+ ++count;\r
+ }\r
+ }\r
+ }\r
+ return merge(line, sum / count);\r
+ }\r
+\r
+ /**\r
+ * Removes given route line and collapses all its neighbor\r
+ * route lines into one line with given position.\r
+ */\r
+ public boolean merge(RouteLine line, double position) {\r
+ if(needsUpdate)\r
+ update();\r
+ if(isSimpleConnection || line.isTransient())\r
+ return false;\r
+ \r
+ if(lines.size() == 1) {\r
+ if(terminals.size() != 2)\r
+ return false;\r
+ lines.remove(0);\r
+ isSimpleConnection = true;\r
+ for(RouteTerminal terminal : terminals)\r
+ terminal.line = null;\r
+ update();\r
+ return true;\r
+ }\r
+ \r
+ ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();\r
+ for(RoutePoint point : line.points) {\r
+ /* Because line.terminal == null, there should be \r
+ * not RouteTerminals \r
+ * \r
+ * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal. \r
+ */\r
+ if (point instanceof RouteLink) {\r
+ RouteLine l = ((RouteLink)point).getOther(line);\r
+ l.points.remove(point);\r
+ if(!l.isTransient())\r
+ nLines.add(l);\r
+ }\r
+ }\r
+ \r
+ if(nLines.isEmpty())\r
+ return false;\r
+ RouteLine merged = nLines.remove(nLines.size()-1);\r
+ merged.position = position;\r
+ for(RouteLine l : nLines) {\r
+ for(RoutePoint point : l.points) {\r
+ /* Because l.terminal == null, there should be \r
+ * not RouteTerminals \r
+ * \r
+ * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal. \r
+ */\r
+ if (point instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)point;\r
+ link.replace(l, merged);\r
+ }\r
+ }\r
+ }\r
+ THashSet<RouteLine> removedLines = new THashSet<RouteLine>();\r
+ removedLines.addAll(nLines);\r
+ lines.removeAll(removedLines);\r
+ removedLines.add(line);\r
+ lines.remove(line);\r
+ for(RouteTerminal terminal : terminals)\r
+ if(removedLines.contains(terminal.line))\r
+ terminal.line = merged;\r
+ update();\r
+ return true;\r
+ }\r
+\r
+ public void deleteCorner(RouteLink link) {\r
+ if(needsUpdate)\r
+ update();\r
+ RouteLine a = link.getA();\r
+ RouteLine b = link.getB();\r
+ if(a.isTransient() || b.isTransient() \r
+ || a.points.size() != 2 || b.points.size() != 2)\r
+ return;\r
+ RouteLine na=null, nb=null;\r
+ for(RoutePoint p : a.points) {\r
+ RouteLink l = (RouteLink)p;\r
+ if(l.a == a && l.b != b) {\r
+ na = l.b;\r
+ break;\r
+ }\r
+ else if(l.b == a && l.a != b) {\r
+ na = l.a;\r
+ break;\r
+ }\r
+ } \r
+ for(RoutePoint p : b.points) {\r
+ RouteLink l = (RouteLink)p;\r
+ if(l.a == b && l.b != a) {\r
+ nb = l.b;\r
+ break;\r
+ }\r
+ else if(l.b == b && l.a != a) {\r
+ nb = l.a;\r
+ break;\r
+ }\r
+ }\r
+ if(na == null || nb == null) {\r
+ System.err.println("Internal error in router.");\r
+ return;\r
+ }\r
+ a.remove();\r
+ b.remove();\r
+ lines.remove(a);\r
+ lines.remove(b);\r
+ link(na, nb);\r
+ if(na.terminal != null)\r
+ na.terminal.line = nb;\r
+ if(nb.terminal != null)\r
+ nb.terminal.line = na;\r
+ update();\r
+ }\r
+ \r
+ public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {\r
+ Object target = pick(x, y, tolerance);\r
+ if(target instanceof RouteLine) {\r
+ RouteLine line = (RouteLine)target;\r
+ RouteTerminal involvedTerminal = \r
+ line.isTransient() ? line.terminal : null;\r
+ makePersistent(line);\r
+ terminal.line = null; // TODO this is a workaround\r
+ \r
+ int lineDir = line.isHorizontal \r
+ ? (line.position < terminal.y ? 3 : 1)\r
+ : (line.position < terminal.x ? 2 : 0)\r
+ ;\r
+ \r
+ if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {\r
+ RouteLine l2;\r
+ if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {\r
+ RouteLine l1 = addLine(true, 0.5*(y+terminal.y));\r
+ l2 = addLine(false, x);\r
+ link(terminal, l1, l2, line);\r
+ }\r
+ else {\r
+ l2 = addLine(false, x);\r
+ link(terminal, l2, line);\r
+ }\r
+ if(involvedTerminal != null)\r
+ involvedTerminal.line = l2;\r
+ }\r
+ else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {\r
+ RouteLine l2;\r
+ if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {\r
+ RouteLine l1 = addLine(false, 0.5*(x+terminal.x));\r
+ l2 = addLine(true, y);\r
+ link(terminal, l1, l2, line);\r
+ }\r
+ else {\r
+ l2 = addLine(true, y);\r
+ link(terminal, l2, line);\r
+ }\r
+ if(involvedTerminal != null)\r
+ involvedTerminal.line = l2;\r
+ }\r
+ else {\r
+ link(terminal, line);\r
+ }\r
+ update();\r
+ return true;\r
+ }\r
+ else\r
+ return false;\r
+ }\r
+ \r
+ public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {\r
+ Object target = pick(x, y, tolerance);\r
+ if(target instanceof RouteLine) {\r
+ RouteLine line = (RouteLine)target;\r
+ RouteTerminal involvedTerminal = \r
+ line.isTransient() ? line.terminal : null;\r
+ makePersistent(line);\r
+ if(line.isHorizontal == sLine.isHorizontal) {\r
+ RouteLine l = addLine(!sLine.isHorizontal, \r
+ sLine.isHorizontal ? x : y); \r
+ link(sLine, l, line);\r
+ if(involvedTerminal != null)\r
+ involvedTerminal.line = l;\r
+ }\r
+ else {\r
+ link(sLine, line);\r
+ if(involvedTerminal != null)\r
+ involvedTerminal.line = sLine;\r
+ }\r
+ update();\r
+ return true;\r
+ }\r
+ else\r
+ return false;\r
+ }\r
+\r
+ /**\r
+ * Makes a deep copy of the route graph and stores\r
+ * the correspondences between original and copied\r
+ * objects into the given map.\r
+ */\r
+ public RouteGraph copy(THashMap<Object, Object> map) {\r
+ RouteGraph copy = new RouteGraph();\r
+ copy.isSimpleConnection = isSimpleConnection;\r
+ copy.caseId = caseId;\r
+ copy.needsUpdate = needsUpdate;\r
+ for(RouteLine line : lines)\r
+ copy.lines.add(line.copy(map));\r
+ for(RouteLine line : transientLines)\r
+ copy.transientLines.add(line.copy(map));\r
+ for(RouteTerminal terminal : terminals)\r
+ copy.terminals.add(terminal.copy(map));\r
+ return copy;\r
+ }\r
+ \r
+ /**\r
+ * Makes a deep copy of the route graph.\r
+ */\r
+ public RouteGraph copy() {\r
+ THashMap<Object, Object> map = new THashMap<Object, Object>(); \r
+ return copy(map);\r
+ }\r
+ \r
+ /**\r
+ * Removes route lines that are conneted to at most\r
+ * one other route line or terminal.\r
+ */\r
+ public void removeExtraConnections() {\r
+ TObjectIntHashMap<RouteLine> counts = \r
+ new TObjectIntHashMap<RouteLine>();\r
+ removeTransientRouteLines();\r
+ for(RouteLine line : lines) {\r
+ int count = 0;\r
+ for(RoutePoint point : line.points)\r
+ if(point instanceof RouteLink)\r
+ ++count;\r
+ counts.put(line, count);\r
+ }\r
+ for(RouteTerminal terminal : terminals)\r
+ counts.adjustOrPutValue(terminal.line, 1, 1);\r
+ boolean removed;\r
+ do {\r
+ removed = false;\r
+ Iterator<RouteLine> it = lines.iterator();\r
+ while(it.hasNext()) {\r
+ RouteLine line = it.next();\r
+ if(counts.get(line) <= 1) {\r
+ for(RoutePoint point : line.points)\r
+ if(point instanceof RouteLink)\r
+ counts.adjustValue(((RouteLink)point).getOther(line), -1);\r
+ line.remove();\r
+ it.remove();\r
+ removed = true;\r
+ }\r
+ }\r
+ } while(removed);\r
+ update();\r
+ }\r
+ \r
+ /**\r
+ * Removes a terminal and all route lines that become degenerated by the removal. \r
+ */\r
+ public void remove(RouteTerminal terminal) {\r
+ terminals.remove(terminal);\r
+ removeExtraConnections();\r
+ }\r
+ \r
+ public void disconnect(RouteTerminal terminal) {\r
+ terminal.line = null;\r
+ removeExtraConnections();\r
+ }\r
+\r
+ public void remove(RouteLink link) {\r
+ link.a.points.remove(link);\r
+ link.b.points.remove(link);\r
+ }\r
+\r
+ public void toggleDirectLines(RouteTerminal terminal) {\r
+ terminal.toggleDirectLines();\r
+ needsUpdate = true;\r
+ }\r
+\r
+ /**\r
+ * Returns all persistent route lines of the route graph.\r
+ */\r
+ public Collection<RouteLine> getLines() {\r
+ if(needsUpdate)\r
+ update();\r
+ if(RETURN_UNMODIFIABLE_COLLECTIONS)\r
+ return Collections.unmodifiableList(lines);\r
+ else\r
+ return lines;\r
+ }\r
+\r
+ /*\r
+ * Returns all transient route lines of the route graph.\r
+ */\r
+ public Collection<RouteLine> getTransientLines() {\r
+ if(needsUpdate)\r
+ update();\r
+ if(RETURN_UNMODIFIABLE_COLLECTIONS)\r
+ return Collections.unmodifiableList(transientLines);\r
+ else\r
+ return transientLines;\r
+ }\r
+\r
+ /**\r
+ * Returns all terminals of the route graph.\r
+ */\r
+ public Collection<RouteTerminal> getTerminals() {\r
+ if(RETURN_UNMODIFIABLE_COLLECTIONS)\r
+ return Collections.unmodifiableList(terminals);\r
+ else\r
+ return terminals;\r
+ }\r
+ \r
+ /**\r
+ * Returns all route lines, both persistent and transient,\r
+ * of the route graph.\r
+ */\r
+ public Collection<RouteLine> getAllLines() {\r
+ if(needsUpdate)\r
+ update();\r
+ ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());\r
+ allLines.addAll(lines);\r
+ allLines.addAll(transientLines);\r
+ return allLines;\r
+ }\r
+ \r
+ /**\r
+ * Returns all route lines, both persistent and transient, of the route\r
+ * graph, added to the specified collection. Avoids allocation of new\r
+ * {@link ArrayList} compared to {@link #getAllLines()}.\r
+ */\r
+ public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {\r
+ if (result == null)\r
+ throw new NullPointerException("null result collection");\r
+ if(needsUpdate)\r
+ update();\r
+ result.addAll(lines);\r
+ result.addAll(transientLines);\r
+ return result;\r
+ }\r
+ \r
+ /**\r
+ * Returns true, if the route graph is connected and contains no cycles.\r
+ */\r
+ public boolean isTree() {\r
+ if(isSimpleConnection)\r
+ return true;\r
+ for(RouteTerminal terminal : terminals)\r
+ if(terminal.line == null)\r
+ return false;\r
+ THashSet<RouteLine> visited = new THashSet<RouteLine>(); \r
+ ArrayList<RouteLine> stack = new ArrayList<RouteLine>(); \r
+ int linkCount = 0;\r
+ visited.add(lines.get(0));\r
+ stack.add(lines.get(0));\r
+ while(!stack.isEmpty()) {\r
+ RouteLine cur = stack.remove(stack.size()-1);\r
+ for(RouteLine n : cur.getPersistentNeighbors()) {\r
+ ++linkCount;\r
+ if(visited.add(n))\r
+ stack.add(n);\r
+ }\r
+ }\r
+ return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);\r
+ }\r
+ \r
+ /**\r
+ * Returns if the connection is simple. A connection is simple, if it has just\r
+ * two terminals connected together directly without (persistent) route lines.\r
+ */\r
+ public boolean isSimpleConnection() {\r
+ return isSimpleConnection;\r
+ }\r
+\r
+ public void replaceBy(RouteGraph rg) {\r
+ this.lines = rg.lines;\r
+ this.terminals = rg.terminals;\r
+ this.transientLines = rg.transientLines;\r
+ this.caseId = rg.caseId;\r
+ this.isSimpleConnection = rg.isSimpleConnection;\r
+ this.needsUpdate = rg.needsUpdate;\r
+ rg.reset();\r
+ }\r
+\r
+ private void reset() {\r
+ lines = new ArrayList<RouteLine>();\r
+ terminals = new ArrayList<RouteTerminal>();\r
+ transientLines = new ArrayList<RouteLine>();\r
+ caseId = 0;\r
+ isSimpleConnection = false;\r
+ needsUpdate = false;\r
+ }\r
+\r
+ public Rectangle2D getBounds() {\r
+ Rectangle2D bounds = new Rectangle2D.Double();\r
+ getBounds(bounds);\r
+ return bounds;\r
+ }\r
+\r
+ public void getBounds(Rectangle2D bounds) {\r
+ if(needsUpdate)\r
+ update();\r
+ double minX = Double.POSITIVE_INFINITY;\r
+ double maxX = Double.NEGATIVE_INFINITY;\r
+ double minY = Double.POSITIVE_INFINITY;\r
+ double maxY = Double.NEGATIVE_INFINITY;\r
+ for(RouteLine line : lines) {\r
+ double position = line.position;\r
+ if(line.isHorizontal) {\r
+ minY = Math.min(minY, position);\r
+ maxY = Math.max(maxY, position);\r
+ }\r
+ else {\r
+ minX = Math.min(minX, position);\r
+ maxX = Math.max(maxX, position);\r
+ }\r
+ }\r
+ for(RouteLine line : transientLines) {\r
+ double position = line.position;\r
+ if(line.isHorizontal) {\r
+ minY = Math.min(minY, position);\r
+ maxY = Math.max(maxY, position);\r
+ }\r
+ else {\r
+ minX = Math.min(minX, position);\r
+ maxX = Math.max(maxX, position);\r
+ }\r
+ }\r
+ for(RouteTerminal terminal : terminals) {\r
+ double x = terminal.x;\r
+ double y = terminal.y;\r
+ minX = Math.min(minX, x);\r
+ maxX = Math.max(maxX, x);\r
+ minY = Math.min(minY, y);\r
+ maxY = Math.max(maxY, y);\r
+ }\r
+ bounds.setFrame(minX, minY, maxX-minX, maxY-minY);\r
+ }\r
+\r
+ private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {\r
+ double x = cur.x, y = cur.y;\r
+ if(cur instanceof RouteTerminal) {\r
+ ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();\r
+ if(line.isHorizontal()) {\r
+ if(cur == line.getBegin())\r
+ x += style.getLineEndLength(0);\r
+ else\r
+ x -= style.getLineEndLength(2);\r
+ }\r
+ else {\r
+ if(cur == line.getBegin())\r
+ y += style.getLineEndLength(1);\r
+ else\r
+ y -= style.getLineEndLength(3);\r
+ }\r
+ }\r
+ path.moveTo(x, y);\r
+ }\r
+ \r
+ private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {\r
+ double x = cur.x, y = cur.y;\r
+ if(cur instanceof RouteTerminal) {\r
+ ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();\r
+ if(line.isHorizontal()) {\r
+ if(cur == line.getBegin())\r
+ x += style.getLineEndLength(0);\r
+ else\r
+ x -= style.getLineEndLength(2);\r
+ }\r
+ else {\r
+ if(cur == line.getBegin())\r
+ y += style.getLineEndLength(1);\r
+ else\r
+ y -= style.getLineEndLength(3);\r
+ }\r
+ }\r
+ path.lineTo(x, y);\r
+ }\r
+ \r
+ public void getPath2D(Path2D path) {\r
+ if(needsUpdate)\r
+ update();\r
+ \r
+ if(isSimpleConnection && transientLines.isEmpty()) {\r
+ if(terminals.size() == 2) {\r
+ RouteTerminal a = terminals.get(0);\r
+ RouteTerminal b = terminals.get(1);\r
+ if(a.hasDirectConnection() || b.hasDirectConnection()) {\r
+ path.moveTo(a.x, a.y);\r
+ path.lineTo(b.x, b.y);\r
+ return;\r
+ }\r
+ }\r
+ }\r
+\r
+ // Analyze graph\r
+ THashMap<RoutePoint, RouteLine> begins = \r
+ new THashMap<RoutePoint, RouteLine>();\r
+ for(RouteLine line : lines) {\r
+ add(begins, line);\r
+ }\r
+ for(RouteLine line : transientLines) {\r
+ add(begins, line);\r
+ }\r
+ for(RouteTerminal terminal : terminals)\r
+ if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {\r
+ begins.remove(terminal.line.getBegin());\r
+ drawContinuousPath(path, begins, terminal, terminal.line);\r
+ }\r
+\r
+ // Create paths\r
+ for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {\r
+ RouteLine curLine = begins.remove(begin);\r
+ drawContinuousPath(path, begins, begin, curLine);\r
+ }\r
+ }\r
+ \r
+ private void drawContinuousPath(Path2D path, THashMap<RoutePoint, RouteLine> begins,\r
+ RoutePoint cur, RouteLine curLine) {\r
+ if(curLine == null)\r
+ return;\r
+ addPathBegin(path, cur, curLine);\r
+\r
+ while(true) {\r
+ if(cur != curLine.getEnd()) \r
+ cur = curLine.getEnd();\r
+ else\r
+ cur = curLine.getBegin();\r
+ if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {\r
+ addPathEnd(path, cur, curLine);\r
+ return;\r
+ }\r
+ if(cur instanceof RouteLink) {\r
+ if(!curLine.isDegenerated() || \r
+ path.getCurrentPoint().getX() != cur.x || \r
+ path.getCurrentPoint().getY() != cur.y)\r
+ path.lineTo(cur.x, cur.y);\r
+ RouteLink link = (RouteLink)cur;\r
+ if(link.a != curLine)\r
+ curLine = link.a;\r
+ else\r
+ curLine = link.b;\r
+ }\r
+ }\r
+ }\r
+\r
+ private static void add(THashMap<RoutePoint, RouteLine> begins,\r
+ RouteLine line) { \r
+ if(line.points.size() > 1) {\r
+ {\r
+ RoutePoint p = line.getBegin();\r
+ if(begins.remove(p) == null)\r
+ begins.put(p, line);\r
+ }\r
+ {\r
+ RoutePoint p = line.getEnd();\r
+ if(begins.remove(p) == null)\r
+ begins.put(p, line);\r
+ }\r
+ }\r
+ }\r
+\r
+ public Collection<Segment> getSegments() {\r
+ if (needsUpdate)\r
+ update();\r
+ ArrayList<Segment> segments = new ArrayList<Segment>();\r
+ for(RouteLine routeLine : lines)\r
+ routeLine.collectSegments(segments);\r
+ for(RouteLine routeLine : transientLines)\r
+ routeLine.collectSegments(segments);\r
+ return segments;\r
+ }\r
+\r
+ public Path2D getPath2D() {\r
+ Path2D result = new Path2D.Double();\r
+ getPath2D(result);\r
+ return result;\r
+ }\r
+ \r
+ public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {\r
+ THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();\r
+ THashSet<RouteLine> lines1 = new THashSet<RouteLine>();\r
+ THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();\r
+ THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();\r
+ THashSet<RouteLine> lines2 = new THashSet<RouteLine>();\r
+ THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();\r
+\r
+ if(splitLine.isTransient()) {\r
+ RouteTerminal terminal = splitLine.terminal;\r
+ \r
+ if(splitLine.beginsWithTerminal()) {\r
+ lines2.addAll(getLines());\r
+ terminals2.addAll(getTerminals());\r
+ terminals1.add(terminal);\r
+ terminals2.remove(terminal);\r
+ interfaceNodes1.add(terminal);\r
+ if(isSimpleConnection())\r
+ interfaceNodes2.addAll(terminals2);\r
+ else\r
+ interfaceNodes2.add(terminal.line);\r
+ }\r
+ else {\r
+ lines1.addAll(getLines());\r
+ terminals1.addAll(getTerminals());\r
+ terminals2.add(terminal);\r
+ terminals1.remove(terminal);\r
+ interfaceNodes2.add(terminal);\r
+ if(isSimpleConnection())\r
+ interfaceNodes1.addAll(terminals1);\r
+ else\r
+ interfaceNodes1.add(terminal.line);\r
+ }\r
+ }\r
+ else {\r
+ for(RoutePoint rp : splitLine.getPoints()) {\r
+ double p = splitLine.isHorizontal ? rp.x : rp.y;\r
+ if(rp instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)rp;\r
+ RouteLine otherLine = link.getA() != splitLine ? link.getA()\r
+ : link.getB();\r
+ if(otherLine.isTransient()) {\r
+ if(p < position) {\r
+ interfaceNodes1.add(otherLine.terminal);\r
+ terminals1.add(otherLine.terminal);\r
+ }\r
+ else {\r
+ interfaceNodes2.add(otherLine.terminal);\r
+ terminals2.add(otherLine.terminal);\r
+ }\r
+ continue;\r
+ } \r
+ \r
+ if(p < position) {\r
+ interfaceNodes1.add(otherLine);\r
+ traverseGraph(link, otherLine, lines1);\r
+ }\r
+ else {\r
+ interfaceNodes2.add(otherLine);\r
+ traverseGraph(link, otherLine, lines2);\r
+ } \r
+ }\r
+ }\r
+ \r
+ for(RouteTerminal terminal : getTerminals())\r
+ if(lines1.contains(terminal.line))\r
+ terminals1.add(terminal);\r
+ else if(lines2.contains(terminal.line))\r
+ terminals2.add(terminal); \r
+ }\r
+ \r
+ return new SplittedRouteGraph(splitLine, \r
+ interfaceNodes1, lines1, terminals1, \r
+ interfaceNodes2, lines2, terminals2);\r
+ }\r
+\r
+ private void traverseGraph(RoutePoint previousPoint, RouteLine line,\r
+ THashSet<RouteLine> lines) {\r
+ if(lines.add(line)) {\r
+ for(RoutePoint rp : line.getPoints()) {\r
+ if(rp != previousPoint && rp instanceof RouteLink) {\r
+ RouteLink link = (RouteLink)rp;\r
+ RouteLine otherLine = line != link.getA() \r
+ ? link.getA() : link.getB();\r
+ if(otherLine.isTransient())\r
+ continue;\r
+ traverseGraph(rp, otherLine, lines);\r
+ }\r
+ }\r
+ }\r
+ }\r
+ \r
+ public void reclaimTransientMemory() {\r
+ removeTransientRouteLines();\r
+ needsUpdate = true;\r
+ }\r
+\r
+}\r