1 /*******************************************************************************
2 * Copyright (c) 2011 Association for Decentralized Information Management in
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.diagram.connection;
14 import java.awt.geom.Line2D;
15 import java.awt.geom.Path2D;
16 import java.awt.geom.Rectangle2D;
17 import java.io.PrintStream;
18 import java.io.Serializable;
19 import java.util.ArrayList;
20 import java.util.Collection;
21 import java.util.Collections;
22 import java.util.Comparator;
23 import java.util.Iterator;
25 import java.util.TreeMap;
27 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
28 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
29 import org.simantics.diagram.connection.segments.Segment;
30 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
32 import gnu.trove.list.array.TDoubleArrayList;
33 import gnu.trove.map.hash.THashMap;
34 import gnu.trove.map.hash.TObjectIntHashMap;
35 import gnu.trove.set.hash.THashSet;
37 public class RouteGraph implements Serializable {
39 private static final long serialVersionUID = 2004022454972623908L;
41 public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
42 public static final boolean CHECK_PARAMERS = true;
44 ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
45 ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
47 ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
49 boolean isSimpleConnection;
50 boolean needsUpdate = false;
52 public void updateTerminals() {
53 boolean changed = false;
54 for(RouteTerminal terminal : terminals)
55 changed |= terminal.updateDynamicPosition();
60 * Adds a route line to the graph.
61 * @param isHorizontal true, if the line is horizontal
62 * @param position y coordinate of the line if horizontal, x coordinate if vertical
63 * @return The new line.
65 public RouteLine addLine(boolean isHorizontal, double position) {
66 RouteLine line = new RouteLine(isHorizontal, position);
72 * Adds a route terminal to the graph.
73 * @param x The location of the terminal.
75 * @param minX The avoidance area of the terminal.
79 * @param allowedDirections Allowed directions.
80 * First four bits tell with which directions
81 * a connection can leave the terminal. The
82 * Fifth bit indicates whether direct lines
83 * can be drawn to the terminal. Directions are
90 * @param style Tells what kind of line end is drawn
92 * @param position a provider for a dynamic position for the terminal or
93 * <code>null</code> if terminal position is not dynamic
94 * @return The new terminal.
96 public RouteTerminal addTerminal(double x, double y,
97 double minX, double minY,
98 double maxX, double maxY,
99 int allowedDirections,
100 ILineEndStyle style, RouteTerminalPosition position) {
101 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
104 public RouteTerminal addTerminal(double x, double y,
105 double minX, double minY,
106 double maxX, double maxY,
107 int allowedDirections,
108 ILineEndStyle style) {
109 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
112 public RouteTerminal addTerminal(double x, double y,
113 double minX, double minY,
114 double maxX, double maxY,
115 int allowedDirections,
116 ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
118 if(allowedDirections > 0x1f)
119 throw new IllegalArgumentException("Illegal allowedDirection flags.");
120 if(minX > x || x > maxX || minY > y || y > maxY)
121 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
124 style = PlainLineEndStyle.INSTANCE;
125 RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
126 maxX, maxY, allowedDirections, false, style, position);
127 terminal.setDynamicStyle(dynamicStyle);
128 terminals.add(terminal);
132 public RouteTerminal addBigTerminal(
133 double minX, double minY,
134 double maxX, double maxY,
135 ILineEndStyle style) {
136 return addBigTerminal(minX, minY, maxX, maxY, style, null);
138 public RouteTerminal addBigTerminal(
139 double minX, double minY,
140 double maxX, double maxY,
141 ILineEndStyle style, ILineEndStyle dynamicStyle) {
143 style = PlainLineEndStyle.INSTANCE;
144 RouteTerminal terminal = new RouteTerminal(
145 0.5*(minX+maxX), 0.5*(minY+maxY),
148 0xf, true, style, null);
149 terminal.setDynamicStyle(dynamicStyle);
151 terminals.add(terminal);
156 * Adds a route terminal to the graph. The avoidance
157 * area is given as a rectangle.
158 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
160 public RouteTerminal addTerminal(double x, double y,
162 int allowedDirections,
163 ILineEndStyle style) {
164 return addTerminal(x, y,
165 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
166 allowedDirections, style, null);
170 * Adds a copy of the given terminal to the graph.
172 public RouteTerminal addTerminal(RouteTerminal terminal) {
173 RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
174 terminal.getMinX(), terminal.getMinY(),
175 terminal.getMaxX(), terminal.getMaxY(),
176 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
177 newTerminal.setData(terminal.getData());
182 * Adds a route terminal to the graph. A default line end style is used.
183 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
185 public RouteTerminal addTerminal(double x, double y,
186 double minX, double minY,
187 double maxX, double maxY,
188 int allowedDirections) {
189 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
190 PlainLineEndStyle.INSTANCE, null);
193 private Collection<Link> initialLinks;
194 public void setInitialLinks(Collection<Link> initialLinks) {
195 this.initialLinks = initialLinks;
198 public Collection<Link> getInitialLinks() {
205 public void link(RouteNode node1, RouteNode node2) {
206 if(node1 instanceof RouteLine) {
207 if(node2 instanceof RouteLine) {
208 link((RouteLine)node1, (RouteLine)node2);
211 link((RouteLine)node1, (RouteTerminal)node2);
215 if(node2 instanceof RouteLine) {
216 link((RouteTerminal)node1, (RouteLine)node2);
219 link((RouteTerminal)node1, (RouteTerminal)node2);
227 public void link(RouteNode ... nodes) {
228 for(int i=1;i<nodes.length;++i)
229 link(nodes[i-1], nodes[i]);
235 public void link(RouteLine node1, RouteLine node2) {
236 new RouteLink(node1, node2);
241 * Links a terminal and a line.
243 public void link(RouteTerminal node1, RouteLine node2) {
246 throw new NullPointerException();
247 if(node1.line != null)
248 throw new IllegalStateException("Terminal is already connected.");
255 * Links a line and a terminal.
257 public void link(RouteLine node1, RouteTerminal node2) {
260 throw new NullPointerException();
261 if(node2.line != null)
262 throw new IllegalStateException("Terminal is already connected.");
269 * Links two terminals.
271 public void link(RouteTerminal node1, RouteTerminal node2) {
274 throw new NullPointerException();
276 throw new NullPointerException();
278 isSimpleConnection = true;
282 void removeTransientRouteLines() {
283 for(RouteLine line : transientLines)
285 transientLines.clear();
289 * Rotates given terminal clockwise by given amount
290 * (also negative numbers are allowed).
292 public void rotate(RouteTerminal terminal, int amount) {
293 terminal.rotate(amount);
298 * Moves the given route line so that its position correspond
299 * to given x or y depending on the orientation of the line.
301 public void setLocation(RouteLine line, double x, double y) {
302 makePersistent(line);
303 line.setLocation(x, y);
308 * Moves the terminal to given location.
310 public void setLocation(RouteTerminal terminal, double x, double y) {
311 terminal.setLocation(x, y);
316 * Updates transient route lines, route link positions
317 * and sorts route points of each route line.
319 public void update() {
321 removeTransientRouteLines();
325 for(RouteLine line : lines)
327 for(RouteTerminal terminal : terminals)
328 if(terminal.hasDirectConnection() && terminal.line != null)
329 terminal.line.hidden = true;
332 if(isSimpleConnection) {
333 RouteTerminal a = terminals.get(0);
334 RouteTerminal b = terminals.get(1);
335 if(a.hasDirectConnection() || b.hasDirectConnection())
337 caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
338 //System.out.println("caseId = " + caseId);
340 case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
341 case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
342 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
343 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
347 transientLines.add(line);
350 case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
351 RouteLine line1 = new RouteLine(true, a.y);
352 RouteLine line2 = new RouteLine(false, b.x);
353 new RouteLink(line1, line2);
358 transientLines.add(line1);
359 transientLines.add(line2);
362 case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
363 RouteLine line1 = new RouteLine(false, a.x);
364 RouteLine line2 = new RouteLine(true, b.y);
365 new RouteLink(line1, line2);
370 transientLines.add(line1);
371 transientLines.add(line2);
374 case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
375 case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
377 SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
378 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
380 terminals.get(0).line = line;
381 terminals.get(1).line = line;
382 transientLines.add(line);
383 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
389 caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
390 routeFromTerminals(false);
393 // Find positions of route points
394 for(RouteLine line : lines)
395 line.setPointPositions();
396 for(RouteLine line : transientLines)
397 line.setPointPositions();
399 // Sort route points in route lines
400 for(RouteLine line : lines) {
403 for(RouteLine line : transientLines) {
408 static class Interval {
409 public final double min;
410 public final double max;
411 public Interval(double min, double max) {
417 class IntervalCache {
418 THashMap<RouteLine, Interval> cache =
419 new THashMap<RouteLine, Interval>();
420 public Interval get(RouteLine line) {
421 Interval result = cache.get(line);
425 result = create(line);
426 cache.put(line, result);
430 private Interval create(RouteLine line) {
431 double min = Double.POSITIVE_INFINITY;
432 double max = Double.NEGATIVE_INFINITY;
434 for(RoutePoint point : line.points) {
436 if(point instanceof RouteLink) {
437 RouteLink link = (RouteLink)point;
439 temp = link.b.position;
441 temp = link.a.position;
444 RouteTerminal terminal = (RouteTerminal)point;
445 if(line.isHorizontal)
455 for(RouteTerminal terminal : terminals) {
456 if(terminal.line == line) {
457 double temp = terminal.approximatePositionToLine();
465 return new Interval(min, max);
469 private void routeFromTerminals(boolean boundingBoxesIntersect) {
470 IntervalCache cache = new IntervalCache();
471 for(RouteTerminal terminal : terminals)
472 if(terminal.line != null) {
473 if(!terminal.hasDirectConnection())
474 terminal.route(transientLines, cache, boundingBoxesIntersect);
479 * Returns a RouteLine near the given point (x,y) (within tolerance).
481 public RouteLine pickLine(double x, double y, double tolerance, int mask) {
484 if(isSimpleConnection && transientLines.isEmpty()) {
485 if(terminals.size() == 2) {
486 if((mask & PICK_TRANSIENT_LINES) == 0)
488 RouteTerminal a = terminals.get(0);
489 RouteTerminal b = terminals.get(1);
490 if(a.hasDirectConnection() || b.hasDirectConnection()) {
491 if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
492 RouteLine dummy = new RouteLine(false, y);
493 return dummy; // There are no lines to return
500 if((mask & PICK_PERSISTENT_LINES) != 0)
501 for(RouteLine line : lines)
502 if(line.isNear(x, y, tolerance))
504 if((mask & PICK_TRANSIENT_LINES) != 0)
505 for(RouteLine line : transientLines)
506 if(line.isNear(x, y, tolerance))
508 if((mask & PICK_DIRECT_LINES) != 0) {
509 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
511 return terminal.line;
516 public RouteLine pickLine(double x, double y, double tolerance) {
517 return pickLine(x, y, tolerance, PICK_LINES);
520 private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
521 double toleranceSq = tolerance * tolerance;
522 for(RouteTerminal terminal : terminals)
523 if((terminal.getAllowedDirections()&0x10) != 0) {
525 RouteLine line = terminal.getLine();
528 RoutePoint b = line.getBegin();
529 double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
530 if(distSq <= toleranceSq) {
531 //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
534 } catch(NullPointerException e) {
535 //if terminal does not have a line
537 } catch(IndexOutOfBoundsException e) {
538 // if line does not contain points
545 public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
546 if(isSimpleConnection)
550 RouteLine line = pickLine(x, y, tolerance);
553 RouteLink link = null;
554 RoutePoint begin = line.getBegin();
555 RoutePoint end = line.getEnd();
556 if(line.isHorizontal) {
557 double mx = 0.5*(begin.getX() + end.getX());
559 if(begin instanceof RouteLink)
560 link = (RouteLink)begin;
563 if(end instanceof RouteLink)
564 link = (RouteLink)line.getEnd();
568 double my = 0.5*(begin.getY() + end.getY());
570 if(begin instanceof RouteLink)
571 link = (RouteLink)begin;
574 if(end instanceof RouteLink)
575 link = (RouteLink)end;
580 if(link.getOther(line).isTransient())
582 return new RouteLineHalf(line, link);
585 public Collection<RouteLineHalf> getLineHalves() {
586 return getLineHalves(new ArrayList<RouteLineHalf>());
589 public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
590 for(RouteLine line : getAllLines()) {
592 RoutePoint p = line.getBegin();
593 if(p instanceof RouteLink) {
594 RouteLink link = (RouteLink)p;
595 if(!link.getOther(line).isTransient())
596 result.add(new RouteLineHalf(line, link));
600 RoutePoint p = line.getEnd();
601 if(p instanceof RouteLink) {
602 RouteLink link = (RouteLink)p;
603 if(!link.getOther(line).isTransient())
604 result.add(new RouteLineHalf(line, link));
612 * Returns a RoutePoint near the given point (x,y) (within tolerance).
614 public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
617 if((mask&PICK_TERMINALS) != 0)
618 for(RouteTerminal terminal : terminals)
619 if(terminal.isNear(x, y))
621 if((mask&PICK_INTERIOR_POINTS) != 0) {
622 for(RouteLine line : lines) {
623 for(RoutePoint point : line.points)
624 if(point.isNear(x, y, tolerance))
627 for(RouteLine line : transientLines) {
628 for(RoutePoint point : line.points)
629 if(point.isNear(x, y, tolerance))
636 public RoutePoint pickPoint(double x, double y, double tolerance) {
637 return pickPoint(x, y, tolerance, PICK_POINTS);
640 public static final int PICK_INTERIOR_POINTS = 1;
641 public static final int PICK_TERMINALS = 2;
642 public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
644 public static final int PICK_PERSISTENT_LINES = 4;
645 public static final int PICK_TRANSIENT_LINES = 8;
646 public static final int PICK_DIRECT_LINES = 16;
647 public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
649 public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
652 * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
654 public Object pick(double x, double y, double tolerance, int mask) {
655 if((mask & PICK_POINTS) != 0) {
656 Object point = pickPoint(x, y, tolerance, mask);
660 /*if((mask & PICK_DIRECT_LINES) != 0) {
661 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
663 return terminal.line.getBegin();
665 if((mask & PICK_LINES) != 0)
666 return pickLine(x, y, tolerance, mask);
671 public Object pick(double x, double y, double tolerance) {
672 return pick(x, y, tolerance, PICK_ALL);
676 * Returns RoutePoint or RouteLine exactly under the given point (x,y).
678 public Object pick(double x, double y) {
679 return pick(x, y, 0.0);
683 * Prints the contents of the route graph to stdout.
685 public void print() {
690 * Prints the contents of the route graph to given print stream.
692 public void print(PrintStream out) {
695 if(isSimpleConnection)
696 out.println("=== SIMPLE CONNECTION ===");
698 out.println("=== COMPLEX CONNECTION ===");
699 for(RouteLine line : lines) {
703 for(RouteLine line : transientLines) {
707 for(RouteTerminal terminal : terminals) {
713 public void makePersistent(RouteLine line) {
714 prepareForModification();
715 if(isSimpleConnection || line.isTransient()) {
716 if(isSimpleConnection) {
717 isSimpleConnection = false;
718 for(RouteTerminal terminal : terminals)
719 terminal.line = line;
720 transientLines.remove(line);
722 Iterator<RoutePoint> it = line.points.iterator();
723 while(it.hasNext()) {
724 RoutePoint point = it.next();
725 if(point instanceof RouteTerminal)
728 line.terminal = null;
729 line.nextTransient = null;
732 line.terminal.line = line;
734 transientLines.remove(line);
736 Iterator<RoutePoint> it = line.points.iterator();
737 while(it.hasNext()) {
738 RoutePoint point = it.next();
739 if(point instanceof RouteTerminal)
742 line.terminal = null;
743 RouteLine temp = line.nextTransient;
744 line.nextTransient = null;
746 } while(line != null);
752 void prepareForModification() {
754 RouteLine line = transientLines.remove(0);
755 line.terminal = null;
757 for(RouteTerminal terminal : terminals)
758 terminal.line = line;
759 isSimpleConnection = false;
764 public double[] getLineLengths(RouteTerminal terminal) {
767 if(lines.size()==0 && transientLines.size()==1)
768 return new double[] { transientLines.get(0).getLength() };
770 RouteLine line = null;
772 for(RouteLine l : transientLines)
773 if(l.isTransient()) {
774 for(RoutePoint p : l.points)
775 if(!(p instanceof RouteLink)) {
780 TDoubleArrayList result = new TDoubleArrayList();
781 THashSet<RouteLine> set = new THashSet<RouteLine>();
785 result.add(line.getLength());
786 for(RoutePoint point : line.points)
787 if(point instanceof RouteLink) {
788 RouteLink link = (RouteLink)point;
789 if(set.add(link.a)) {
793 if(set.add(link.b)) {
800 return result.toArray();
803 public void split(RouteLine rl1, double splitPosition) {
806 boolean isHorizontal = rl1.isHorizontal();
807 if(isSimpleConnection) {
808 isSimpleConnection = false;
810 RouteLine sp = addLine(!isHorizontal, splitPosition);
811 for(RouteTerminal terminal : terminals)
816 else if(caseId < 4) {
817 RouteLine sp = addLine(!isHorizontal, splitPosition);
818 RouteLine l = addLine(isHorizontal, rl1.position);
820 rl1.terminal.line = sp;
821 for(RouteTerminal terminal : terminals)
822 if(terminal != rl1.terminal)
828 prepareForModification();
831 RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
832 RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
834 ArrayList<RoutePoint> points = rl1.points;
839 int maxPos = points.size();
840 while(minPos != maxPos) {
841 int c = (minPos + maxPos)/2;
843 ? points.get(c).getX() > splitPosition
844 : points.get(c).getY() > splitPosition)
852 for(int i=points.size()-1;i>=splitPos;--i) {
853 RoutePoint point = points.remove(i);
854 if(point instanceof RouteLink) {
855 RouteLink link = (RouteLink)point;
856 link.replace(rl1, rl2);
860 if(rl1.isTransient()) {
861 boolean p1 = rl1.isConnectedToPeristentLine();
862 boolean p2 = rl2.isConnectedToPeristentLine();
864 RouteTerminal terminal = rl1.terminal;
867 transientLines.add(rl2);
873 transientLines.add(rl2);
875 for(RouteTerminal t : terminals)
883 new RouteLink(rl1, sp);
884 new RouteLink(sp, rl2);
889 public boolean merge(RouteLine line) {
892 for(RoutePoint point : line.points) {
893 if(point instanceof RouteLink) {
894 RouteLink link = (RouteLink)point;
895 RouteLine other = link.getOther(line);
896 if(!other.isTransient()) {
897 sum += other.position;
902 return merge(line, sum / count);
906 * Removes given route line and collapses all its neighbor
907 * route lines into one line with given position.
909 public boolean merge(RouteLine line, double position) {
912 if(isSimpleConnection || line.isTransient())
915 if(lines.size() == 1) {
916 if(terminals.size() != 2)
919 isSimpleConnection = true;
920 for(RouteTerminal terminal : terminals)
921 terminal.line = null;
926 ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
927 for(RoutePoint point : line.points) {
928 /* Because line.terminal == null, there should be
931 * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
933 if (point instanceof RouteLink) {
934 RouteLine l = ((RouteLink)point).getOther(line);
935 l.points.remove(point);
943 RouteLine merged = nLines.remove(nLines.size()-1);
944 merged.position = position;
945 for(RouteLine l : nLines) {
946 for(RoutePoint point : l.points) {
947 /* Because l.terminal == null, there should be
950 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
952 if (point instanceof RouteLink) {
953 RouteLink link = (RouteLink)point;
954 link.replace(l, merged);
958 THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
959 removedLines.addAll(nLines);
960 lines.removeAll(removedLines);
961 removedLines.add(line);
963 for(RouteTerminal terminal : terminals)
964 if(removedLines.contains(terminal.line))
965 terminal.line = merged;
970 public void deleteCorner(RouteLink link) {
973 RouteLine a = link.getA();
974 RouteLine b = link.getB();
975 if(a.isTransient() || b.isTransient()
976 || a.points.size() != 2 || b.points.size() != 2)
978 RouteLine na=null, nb=null;
979 for(RoutePoint p : a.points) {
980 RouteLink l = (RouteLink)p;
981 if(l.a == a && l.b != b) {
985 else if(l.b == a && l.a != b) {
990 for(RoutePoint p : b.points) {
991 RouteLink l = (RouteLink)p;
992 if(l.a == b && l.b != a) {
996 else if(l.b == b && l.a != a) {
1001 if(na == null || nb == null) {
1002 System.err.println("Internal error in router.");
1010 if(na.terminal != null)
1011 na.terminal.line = nb;
1012 if(nb.terminal != null)
1013 nb.terminal.line = na;
1017 public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1018 Object target = pick(x, y, tolerance);
1019 if(target instanceof RouteLine) {
1020 RouteLine line = (RouteLine)target;
1021 RouteTerminal involvedTerminal =
1022 line.isTransient() ? line.terminal : null;
1023 makePersistent(line);
1024 terminal.line = null; // TODO this is a workaround
1026 int lineDir = line.isHorizontal
1027 ? (line.position < terminal.y ? 3 : 1)
1028 : (line.position < terminal.x ? 2 : 0)
1031 if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1033 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1034 RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1035 l2 = addLine(false, x);
1036 link(terminal, l1, l2, line);
1039 l2 = addLine(false, x);
1040 link(terminal, l2, line);
1042 if(involvedTerminal != null)
1043 involvedTerminal.line = l2;
1045 else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1047 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1048 RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1049 l2 = addLine(true, y);
1050 link(terminal, l1, l2, line);
1053 l2 = addLine(true, y);
1054 link(terminal, l2, line);
1056 if(involvedTerminal != null)
1057 involvedTerminal.line = l2;
1060 link(terminal, line);
1069 public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1070 Object target = pick(x, y, tolerance);
1071 if(target instanceof RouteLine) {
1072 RouteLine line = (RouteLine)target;
1073 RouteTerminal involvedTerminal =
1074 line.isTransient() ? line.terminal : null;
1075 makePersistent(line);
1076 if(line.isHorizontal == sLine.isHorizontal) {
1077 RouteLine l = addLine(!sLine.isHorizontal,
1078 sLine.isHorizontal ? x : y);
1079 link(sLine, l, line);
1080 if(involvedTerminal != null)
1081 involvedTerminal.line = l;
1085 if(involvedTerminal != null)
1086 involvedTerminal.line = sLine;
1096 * Makes a deep copy of the route graph and stores
1097 * the correspondences between original and copied
1098 * objects into the given map.
1100 public RouteGraph copy(THashMap<Object, Object> map) {
1101 RouteGraph copy = new RouteGraph();
1102 copy.isSimpleConnection = isSimpleConnection;
1103 copy.caseId = caseId;
1104 copy.needsUpdate = needsUpdate;
1105 for(RouteLine line : lines)
1106 copy.lines.add(line.copy(map));
1107 for(RouteLine line : transientLines)
1108 copy.transientLines.add(line.copy(map));
1109 for(RouteTerminal terminal : terminals)
1110 copy.terminals.add(terminal.copy(map));
1115 * Makes a deep copy of the route graph.
1117 public RouteGraph copy() {
1118 THashMap<Object, Object> map = new THashMap<Object, Object>();
1123 * Removes route lines that are conneted to at most
1124 * one other route line or terminal.
1126 public void removeExtraConnections() {
1127 TObjectIntHashMap<RouteLine> counts =
1128 new TObjectIntHashMap<RouteLine>();
1129 removeTransientRouteLines();
1130 for(RouteLine line : lines) {
1132 for(RoutePoint point : line.points)
1133 if(point instanceof RouteLink)
1135 counts.put(line, count);
1137 for(RouteTerminal terminal : terminals)
1138 counts.adjustOrPutValue(terminal.line, 1, 1);
1142 Iterator<RouteLine> it = lines.iterator();
1143 while(it.hasNext()) {
1144 RouteLine line = it.next();
1145 if(counts.get(line) <= 1) {
1146 for(RoutePoint point : line.points)
1147 if(point instanceof RouteLink)
1148 counts.adjustValue(((RouteLink)point).getOther(line), -1);
1159 * Removes a terminal and all route lines that become degenerated by the removal.
1161 public void remove(RouteTerminal terminal) {
1162 terminals.remove(terminal);
1163 removeExtraConnections();
1166 public void disconnect(RouteTerminal terminal) {
1167 terminal.line = null;
1168 removeExtraConnections();
1171 public void remove(RouteLink link) {
1172 link.a.points.remove(link);
1173 link.b.points.remove(link);
1176 public void toggleDirectLines(RouteTerminal terminal) {
1177 terminal.toggleDirectLines();
1182 * Returns all persistent route lines of the route graph.
1184 public Collection<RouteLine> getLines() {
1187 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1188 return Collections.unmodifiableList(lines);
1194 * Returns all transient route lines of the route graph.
1196 public Collection<RouteLine> getTransientLines() {
1199 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1200 return Collections.unmodifiableList(transientLines);
1202 return transientLines;
1206 * Returns all terminals of the route graph.
1208 public Collection<RouteTerminal> getTerminals() {
1209 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1210 return Collections.unmodifiableList(terminals);
1216 * Returns all route lines, both persistent and transient,
1217 * of the route graph.
1219 public Collection<RouteLine> getAllLines() {
1222 ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1223 allLines.addAll(lines);
1224 allLines.addAll(transientLines);
1229 * Returns all route lines, both persistent and transient, of the route
1230 * graph, added to the specified collection. Avoids allocation of new
1231 * {@link ArrayList} compared to {@link #getAllLines()}.
1233 public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1235 throw new NullPointerException("null result collection");
1238 result.addAll(lines);
1239 result.addAll(transientLines);
1244 * Returns true, if the route graph is connected and contains no cycles.
1246 public boolean isTree() {
1247 if(isSimpleConnection)
1249 for(RouteTerminal terminal : terminals)
1250 if(terminal.line == null)
1252 THashSet<RouteLine> visited = new THashSet<RouteLine>();
1253 ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1255 visited.add(lines.get(0));
1256 stack.add(lines.get(0));
1257 while(!stack.isEmpty()) {
1258 RouteLine cur = stack.remove(stack.size()-1);
1259 for(RouteLine n : cur.getPersistentNeighbors()) {
1265 return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1269 * Returns if the connection is simple. A connection is simple, if it has just
1270 * two terminals connected together directly without (persistent) route lines.
1272 public boolean isSimpleConnection() {
1273 return isSimpleConnection;
1276 public void replaceBy(RouteGraph rg) {
1277 this.lines = rg.lines;
1278 this.terminals = rg.terminals;
1279 this.transientLines = rg.transientLines;
1280 this.caseId = rg.caseId;
1281 this.isSimpleConnection = rg.isSimpleConnection;
1282 this.needsUpdate = rg.needsUpdate;
1286 private void reset() {
1287 lines = new ArrayList<RouteLine>();
1288 terminals = new ArrayList<RouteTerminal>();
1289 transientLines = new ArrayList<RouteLine>();
1291 isSimpleConnection = false;
1292 needsUpdate = false;
1295 public Rectangle2D getBounds() {
1296 Rectangle2D bounds = new Rectangle2D.Double();
1301 public void getBounds(Rectangle2D bounds) {
1304 double minX = Double.POSITIVE_INFINITY;
1305 double maxX = Double.NEGATIVE_INFINITY;
1306 double minY = Double.POSITIVE_INFINITY;
1307 double maxY = Double.NEGATIVE_INFINITY;
1308 for(RouteLine line : lines) {
1309 double position = line.position;
1310 if(line.isHorizontal) {
1311 minY = Math.min(minY, position);
1312 maxY = Math.max(maxY, position);
1315 minX = Math.min(minX, position);
1316 maxX = Math.max(maxX, position);
1319 for(RouteLine line : transientLines) {
1320 double position = line.position;
1321 if(line.isHorizontal) {
1322 minY = Math.min(minY, position);
1323 maxY = Math.max(maxY, position);
1326 minX = Math.min(minX, position);
1327 maxX = Math.max(maxX, position);
1330 for(RouteTerminal terminal : terminals) {
1331 double x = terminal.x;
1332 double y = terminal.y;
1333 minX = Math.min(minX, x);
1334 maxX = Math.max(maxX, x);
1335 minY = Math.min(minY, y);
1336 maxY = Math.max(maxY, y);
1338 bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1341 private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1342 double x = cur.x, y = cur.y;
1343 if(cur instanceof RouteTerminal) {
1344 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1345 if(line.isHorizontal()) {
1346 if(cur == line.getBegin())
1347 x += style.getLineEndLength(0);
1349 x -= style.getLineEndLength(2);
1352 if(cur == line.getBegin())
1353 y += style.getLineEndLength(1);
1355 y -= style.getLineEndLength(3);
1361 private static final Comparator<RoutePoint> RG_COMP = (o1, o2) -> {
1362 if (o1.getX() < o2.getX())
1364 else if (o1.getX() > o2.getX())
1366 if (o1.getY() < o2.getY())
1368 else if (o1.getY() > o2.getY())
1373 private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1374 double x = cur.x, y = cur.y;
1375 if(cur instanceof RouteTerminal) {
1376 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1377 if(line.isHorizontal()) {
1378 if(cur == line.getBegin())
1379 x += style.getLineEndLength(0);
1381 x -= style.getLineEndLength(2);
1384 if(cur == line.getBegin())
1385 y += style.getLineEndLength(1);
1387 y -= style.getLineEndLength(3);
1393 public void getPath2D(Path2D path) {
1397 if(isSimpleConnection && transientLines.isEmpty()) {
1398 if(terminals.size() == 2) {
1399 RouteTerminal a = terminals.get(0);
1400 RouteTerminal b = terminals.get(1);
1401 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1402 path.moveTo(a.x, a.y);
1403 path.lineTo(b.x, b.y);
1410 Map<RoutePoint, RouteLine> begins =
1411 // new THashMap<RoutePoint, RouteLine>(); //The ordering of the coordinates in the path should be deterministic between scenegraphs
1412 new TreeMap<RoutePoint, RouteLine>(RG_COMP);
1413 for(RouteLine line : lines) {
1416 for(RouteLine line : transientLines) {
1419 for(RouteTerminal terminal : terminals)
1420 if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1421 begins.remove(terminal.line.getBegin());
1422 drawContinuousPath(path, begins, terminal, terminal.line);
1426 for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1427 RouteLine curLine = begins.remove(begin);
1428 drawContinuousPath(path, begins, begin, curLine);
1432 private void drawContinuousPath(Path2D path, Map<RoutePoint, RouteLine> begins,
1433 RoutePoint cur, RouteLine curLine) {
1436 addPathBegin(path, cur, curLine);
1439 if(cur != curLine.getEnd())
1440 cur = curLine.getEnd();
1442 cur = curLine.getBegin();
1443 if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1444 addPathEnd(path, cur, curLine);
1447 if(cur instanceof RouteLink) {
1448 if(!curLine.isDegenerated() ||
1449 path.getCurrentPoint().getX() != cur.x ||
1450 path.getCurrentPoint().getY() != cur.y)
1451 path.lineTo(cur.x, cur.y);
1452 RouteLink link = (RouteLink)cur;
1453 if(link.a != curLine)
1461 private static void add(Map<RoutePoint, RouteLine> begins,
1463 if(line.points.size() > 1) {
1465 RoutePoint p = line.getBegin();
1466 if(begins.remove(p) == null)
1467 begins.put(p, line);
1470 RoutePoint p = line.getEnd();
1471 if(begins.remove(p) == null)
1472 begins.put(p, line);
1477 public Collection<Segment> getSegments() {
1480 ArrayList<Segment> segments = new ArrayList<Segment>();
1481 for(RouteLine routeLine : lines)
1482 routeLine.collectSegments(segments);
1483 for(RouteLine routeLine : transientLines)
1484 routeLine.collectSegments(segments);
1488 public Path2D getPath2D() {
1489 Path2D result = new Path2D.Double();
1494 public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1495 THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1496 THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1497 THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1498 THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1499 THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1500 THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1502 if(splitLine.isTransient()) {
1503 RouteTerminal terminal = splitLine.terminal;
1505 if(splitLine.beginsWithTerminal()) {
1506 lines2.addAll(getLines());
1507 terminals2.addAll(getTerminals());
1508 terminals1.add(terminal);
1509 terminals2.remove(terminal);
1510 interfaceNodes1.add(terminal);
1511 if(isSimpleConnection())
1512 interfaceNodes2.addAll(terminals2);
1514 interfaceNodes2.add(terminal.line);
1517 lines1.addAll(getLines());
1518 terminals1.addAll(getTerminals());
1519 terminals2.add(terminal);
1520 terminals1.remove(terminal);
1521 interfaceNodes2.add(terminal);
1522 if(isSimpleConnection())
1523 interfaceNodes1.addAll(terminals1);
1525 interfaceNodes1.add(terminal.line);
1529 for(RoutePoint rp : splitLine.getPoints()) {
1530 double p = splitLine.isHorizontal ? rp.x : rp.y;
1531 if(rp instanceof RouteLink) {
1532 RouteLink link = (RouteLink)rp;
1533 RouteLine otherLine = link.getA() != splitLine ? link.getA()
1535 if(otherLine.isTransient()) {
1537 interfaceNodes1.add(otherLine.terminal);
1538 terminals1.add(otherLine.terminal);
1541 interfaceNodes2.add(otherLine.terminal);
1542 terminals2.add(otherLine.terminal);
1548 interfaceNodes1.add(otherLine);
1549 traverseGraph(link, otherLine, lines1);
1552 interfaceNodes2.add(otherLine);
1553 traverseGraph(link, otherLine, lines2);
1558 for(RouteTerminal terminal : getTerminals())
1559 if(lines1.contains(terminal.line))
1560 terminals1.add(terminal);
1561 else if(lines2.contains(terminal.line))
1562 terminals2.add(terminal);
1565 return new SplittedRouteGraph(splitLine,
1566 interfaceNodes1, lines1, terminals1,
1567 interfaceNodes2, lines2, terminals2);
1570 private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1571 THashSet<RouteLine> lines) {
1572 if(lines.add(line)) {
1573 for(RoutePoint rp : line.getPoints()) {
1574 if(rp != previousPoint && rp instanceof RouteLink) {
1575 RouteLink link = (RouteLink)rp;
1576 RouteLine otherLine = line != link.getA()
1577 ? link.getA() : link.getB();
1578 if(otherLine.isTransient())
1580 traverseGraph(rp, otherLine, lines);
1586 public void reclaimTransientMemory() {
1587 removeTransientRouteLines();