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 gnu.trove.list.array.TDoubleArrayList;
15 import gnu.trove.map.hash.THashMap;
16 import gnu.trove.map.hash.TObjectIntHashMap;
17 import gnu.trove.set.hash.THashSet;
19 import java.awt.geom.Line2D;
20 import java.awt.geom.Path2D;
21 import java.awt.geom.Rectangle2D;
22 import java.io.PrintStream;
23 import java.io.Serializable;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.Collections;
27 import java.util.Comparator;
28 import java.util.Iterator;
30 import java.util.TreeMap;
32 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
33 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
34 import org.simantics.diagram.connection.segments.Segment;
35 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
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);
46 ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
48 boolean isSimpleConnection;
49 boolean needsUpdate = false;
51 public void updateTerminals() {
52 boolean changed = false;
53 for(RouteTerminal terminal : terminals)
54 changed |= terminal.updateDynamicPosition();
59 * Adds a route line to the graph.
60 * @param isHorizontal true, if the line is horizontal
61 * @param position y coordinate of the line if horizontal, x coordinate if vertical
62 * @return The new line.
64 public RouteLine addLine(boolean isHorizontal, double position) {
65 RouteLine line = new RouteLine(isHorizontal, position);
71 * Adds a route terminal to the graph.
72 * @param x The location of the terminal.
74 * @param minX The avoidance area of the terminal.
78 * @param allowedDirections Allowed directions.
79 * First four bits tell with which directions
80 * a connection can leave the terminal. The
81 * Fifth bit indicates whether direct lines
82 * can be drawn to the terminal. Directions are
89 * @param style Tells what kind of line end is drawn
91 * @param position a provider for a dynamic position for the terminal or
92 * <code>null</code> if terminal position is not dynamic
93 * @return The new terminal.
95 public RouteTerminal addTerminal(double x, double y,
96 double minX, double minY,
97 double maxX, double maxY,
98 int allowedDirections,
99 ILineEndStyle style, RouteTerminalPosition position) {
100 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
103 public RouteTerminal addTerminal(double x, double y,
104 double minX, double minY,
105 double maxX, double maxY,
106 int allowedDirections,
107 ILineEndStyle style) {
108 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
111 public RouteTerminal addTerminal(double x, double y,
112 double minX, double minY,
113 double maxX, double maxY,
114 int allowedDirections,
115 ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
117 if(allowedDirections > 0x1f)
118 throw new IllegalArgumentException("Illegal allowedDirection flags.");
119 if(minX > x || x > maxX || minY > y || y > maxY)
120 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
123 style = PlainLineEndStyle.INSTANCE;
124 RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
125 maxX, maxY, allowedDirections, false, style, position);
126 terminal.setDynamicStyle(dynamicStyle);
127 terminals.add(terminal);
131 public RouteTerminal addBigTerminal(
132 double minX, double minY,
133 double maxX, double maxY,
134 ILineEndStyle style) {
135 return addBigTerminal(minX, minY, maxX, maxY, style, null);
137 public RouteTerminal addBigTerminal(
138 double minX, double minY,
139 double maxX, double maxY,
140 ILineEndStyle style, ILineEndStyle dynamicStyle) {
142 style = PlainLineEndStyle.INSTANCE;
143 RouteTerminal terminal = new RouteTerminal(
144 0.5*(minX+maxX), 0.5*(minY+maxY),
147 0xf, true, style, null);
148 terminal.setDynamicStyle(dynamicStyle);
150 terminals.add(terminal);
155 * Adds a route terminal to the graph. The avoidance
156 * area is given as a rectangle.
157 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
159 public RouteTerminal addTerminal(double x, double y,
161 int allowedDirections,
162 ILineEndStyle style) {
163 return addTerminal(x, y,
164 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
165 allowedDirections, style, null);
169 * Adds a copy of the given terminal to the graph.
171 public RouteTerminal addTerminal(RouteTerminal terminal) {
172 RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
173 terminal.getMinX(), terminal.getMinY(),
174 terminal.getMaxX(), terminal.getMaxY(),
175 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
176 newTerminal.setData(terminal.getData());
181 * Adds a route terminal to the graph. A default line end style is used.
182 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
184 public RouteTerminal addTerminal(double x, double y,
185 double minX, double minY,
186 double maxX, double maxY,
187 int allowedDirections) {
188 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
189 PlainLineEndStyle.INSTANCE, null);
195 public void link(RouteNode node1, RouteNode node2) {
196 if(node1 instanceof RouteLine) {
197 if(node2 instanceof RouteLine) {
198 link((RouteLine)node1, (RouteLine)node2);
201 link((RouteLine)node1, (RouteTerminal)node2);
205 if(node2 instanceof RouteLine) {
206 link((RouteTerminal)node1, (RouteLine)node2);
209 link((RouteTerminal)node1, (RouteTerminal)node2);
217 public void link(RouteNode ... nodes) {
218 for(int i=1;i<nodes.length;++i)
219 link(nodes[i-1], nodes[i]);
225 public void link(RouteLine node1, RouteLine node2) {
226 new RouteLink(node1, node2);
231 * Links a terminal and a line.
233 public void link(RouteTerminal node1, RouteLine node2) {
236 throw new NullPointerException();
237 if(node1.line != null)
238 throw new IllegalStateException("Terminal is already connected.");
245 * Links a line and a terminal.
247 public void link(RouteLine node1, RouteTerminal node2) {
250 throw new NullPointerException();
251 if(node2.line != null)
252 throw new IllegalStateException("Terminal is already connected.");
259 * Links two terminals.
261 public void link(RouteTerminal node1, RouteTerminal node2) {
264 throw new NullPointerException();
266 throw new NullPointerException();
268 isSimpleConnection = true;
272 void removeTransientRouteLines() {
273 for(RouteLine line : transientLines)
275 transientLines.clear();
279 * Rotates given terminal clockwise by given amount
280 * (also negative numbers are allowed).
282 public void rotate(RouteTerminal terminal, int amount) {
283 terminal.rotate(amount);
288 * Moves the given route line so that its position correspond
289 * to given x or y depending on the orientation of the line.
291 public void setLocation(RouteLine line, double x, double y) {
292 makePersistent(line);
293 line.setLocation(x, y);
298 * Moves the terminal to given location.
300 public void setLocation(RouteTerminal terminal, double x, double y) {
301 terminal.setLocation(x, y);
306 * Updates transient route lines, route link positions
307 * and sorts route points of each route line.
309 public void update() {
311 removeTransientRouteLines();
315 for(RouteLine line : lines)
317 for(RouteTerminal terminal : terminals)
318 if(terminal.hasDirectConnection() && terminal.line != null)
319 terminal.line.hidden = true;
322 if(isSimpleConnection) {
323 RouteTerminal a = terminals.get(0);
324 RouteTerminal b = terminals.get(1);
325 if(a.hasDirectConnection() || b.hasDirectConnection())
327 caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
328 //System.out.println("caseId = " + caseId);
330 case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
331 case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
332 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
333 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
337 transientLines.add(line);
340 case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
341 RouteLine line1 = new RouteLine(true, a.y);
342 RouteLine line2 = new RouteLine(false, b.x);
343 new RouteLink(line1, line2);
348 transientLines.add(line1);
349 transientLines.add(line2);
352 case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
353 RouteLine line1 = new RouteLine(false, a.x);
354 RouteLine line2 = new RouteLine(true, b.y);
355 new RouteLink(line1, line2);
360 transientLines.add(line1);
361 transientLines.add(line2);
364 case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
365 case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
367 SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
368 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
370 terminals.get(0).line = line;
371 terminals.get(1).line = line;
372 transientLines.add(line);
373 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
379 caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
380 routeFromTerminals(false);
383 // Find positions of route points
384 for(RouteLine line : lines)
385 line.setPointPositions();
386 for(RouteLine line : transientLines)
387 line.setPointPositions();
389 // Sort route points in route lines
390 for(RouteLine line : lines) {
393 for(RouteLine line : transientLines) {
398 static class Interval {
399 public final double min;
400 public final double max;
401 public Interval(double min, double max) {
407 class IntervalCache {
408 THashMap<RouteLine, Interval> cache =
409 new THashMap<RouteLine, Interval>();
410 public Interval get(RouteLine line) {
411 Interval result = cache.get(line);
415 result = create(line);
416 cache.put(line, result);
420 private Interval create(RouteLine line) {
421 double min = Double.POSITIVE_INFINITY;
422 double max = Double.NEGATIVE_INFINITY;
424 for(RoutePoint point : line.points) {
426 if(point instanceof RouteLink) {
427 RouteLink link = (RouteLink)point;
429 temp = link.b.position;
431 temp = link.a.position;
434 RouteTerminal terminal = (RouteTerminal)point;
435 if(line.isHorizontal)
445 for(RouteTerminal terminal : terminals) {
446 if(terminal.line == line) {
447 double temp = terminal.approximatePositionToLine();
455 return new Interval(min, max);
459 private void routeFromTerminals(boolean boundingBoxesIntersect) {
460 IntervalCache cache = new IntervalCache();
461 for(RouteTerminal terminal : terminals)
462 if(terminal.line != null) {
463 if(!terminal.hasDirectConnection())
464 terminal.route(transientLines, cache, boundingBoxesIntersect);
469 * Returns a RouteLine near the given point (x,y) (within tolerance).
471 public RouteLine pickLine(double x, double y, double tolerance, int mask) {
474 if(isSimpleConnection && transientLines.isEmpty()) {
475 if(terminals.size() == 2) {
476 if((mask & PICK_TRANSIENT_LINES) == 0)
478 RouteTerminal a = terminals.get(0);
479 RouteTerminal b = terminals.get(1);
480 if(a.hasDirectConnection() || b.hasDirectConnection()) {
481 if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
482 RouteLine dummy = new RouteLine(false, y);
483 return dummy; // There are no lines to return
490 if((mask & PICK_PERSISTENT_LINES) != 0)
491 for(RouteLine line : lines)
492 if(line.isNear(x, y, tolerance))
494 if((mask & PICK_TRANSIENT_LINES) != 0)
495 for(RouteLine line : transientLines)
496 if(line.isNear(x, y, tolerance))
498 if((mask & PICK_DIRECT_LINES) != 0) {
499 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
501 return terminal.line;
506 public RouteLine pickLine(double x, double y, double tolerance) {
507 return pickLine(x, y, tolerance, PICK_LINES);
510 private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
511 double toleranceSq = tolerance * tolerance;
512 for(RouteTerminal terminal : terminals)
513 if((terminal.getAllowedDirections()&0x10) != 0) {
515 RouteLine line = terminal.getLine();
518 RoutePoint b = line.getBegin();
519 double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
520 if(distSq <= toleranceSq) {
521 //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
524 } catch(NullPointerException e) {
525 //if terminal does not have a line
527 } catch(IndexOutOfBoundsException e) {
528 // if line does not contain points
535 public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
536 if(isSimpleConnection)
540 RouteLine line = pickLine(x, y, tolerance);
543 RouteLink link = null;
544 RoutePoint begin = line.getBegin();
545 RoutePoint end = line.getEnd();
546 if(line.isHorizontal) {
547 double mx = 0.5*(begin.getX() + end.getX());
549 if(begin instanceof RouteLink)
550 link = (RouteLink)begin;
553 if(end instanceof RouteLink)
554 link = (RouteLink)line.getEnd();
558 double my = 0.5*(begin.getY() + end.getY());
560 if(begin instanceof RouteLink)
561 link = (RouteLink)begin;
564 if(end instanceof RouteLink)
565 link = (RouteLink)end;
570 if(link.getOther(line).isTransient())
572 return new RouteLineHalf(line, link);
575 public Collection<RouteLineHalf> getLineHalves() {
576 return getLineHalves(new ArrayList<RouteLineHalf>());
579 public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
580 for(RouteLine line : getAllLines()) {
582 RoutePoint p = line.getBegin();
583 if(p instanceof RouteLink) {
584 RouteLink link = (RouteLink)p;
585 if(!link.getOther(line).isTransient())
586 result.add(new RouteLineHalf(line, link));
590 RoutePoint p = line.getEnd();
591 if(p instanceof RouteLink) {
592 RouteLink link = (RouteLink)p;
593 if(!link.getOther(line).isTransient())
594 result.add(new RouteLineHalf(line, link));
602 * Returns a RoutePoint near the given point (x,y) (within tolerance).
604 public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
607 if((mask&PICK_TERMINALS) != 0)
608 for(RouteTerminal terminal : terminals)
609 if(terminal.isNear(x, y))
611 if((mask&PICK_INTERIOR_POINTS) != 0) {
612 for(RouteLine line : lines) {
613 for(RoutePoint point : line.points)
614 if(point.isNear(x, y, tolerance))
617 for(RouteLine line : transientLines) {
618 for(RoutePoint point : line.points)
619 if(point.isNear(x, y, tolerance))
626 public RoutePoint pickPoint(double x, double y, double tolerance) {
627 return pickPoint(x, y, tolerance, PICK_POINTS);
630 public static final int PICK_INTERIOR_POINTS = 1;
631 public static final int PICK_TERMINALS = 2;
632 public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
634 public static final int PICK_PERSISTENT_LINES = 4;
635 public static final int PICK_TRANSIENT_LINES = 8;
636 public static final int PICK_DIRECT_LINES = 16;
637 public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
639 public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
642 * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
644 public Object pick(double x, double y, double tolerance, int mask) {
645 if((mask & PICK_POINTS) != 0) {
646 Object point = pickPoint(x, y, tolerance, mask);
650 /*if((mask & PICK_DIRECT_LINES) != 0) {
651 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
653 return terminal.line.getBegin();
655 if((mask & PICK_LINES) != 0)
656 return pickLine(x, y, tolerance, mask);
661 public Object pick(double x, double y, double tolerance) {
662 return pick(x, y, tolerance, PICK_ALL);
666 * Returns RoutePoint or RouteLine exactly under the given point (x,y).
668 public Object pick(double x, double y) {
669 return pick(x, y, 0.0);
673 * Prints the contents of the route graph to stdout.
675 public void print() {
680 * Prints the contents of the route graph to given print stream.
682 public void print(PrintStream out) {
685 if(isSimpleConnection)
686 out.println("=== SIMPLE CONNECTION ===");
688 out.println("=== COMPLEX CONNECTION ===");
689 for(RouteLine line : lines) {
693 for(RouteLine line : transientLines) {
697 for(RouteTerminal terminal : terminals) {
703 public void makePersistent(RouteLine line) {
704 prepareForModification();
705 if(isSimpleConnection || line.isTransient()) {
706 if(isSimpleConnection) {
707 isSimpleConnection = false;
708 for(RouteTerminal terminal : terminals)
709 terminal.line = line;
710 transientLines.remove(line);
712 Iterator<RoutePoint> it = line.points.iterator();
713 while(it.hasNext()) {
714 RoutePoint point = it.next();
715 if(point instanceof RouteTerminal)
718 line.terminal = null;
719 line.nextTransient = null;
722 line.terminal.line = line;
724 transientLines.remove(line);
726 Iterator<RoutePoint> it = line.points.iterator();
727 while(it.hasNext()) {
728 RoutePoint point = it.next();
729 if(point instanceof RouteTerminal)
732 line.terminal = null;
733 RouteLine temp = line.nextTransient;
734 line.nextTransient = null;
736 } while(line != null);
742 void prepareForModification() {
744 RouteLine line = transientLines.remove(0);
745 line.terminal = null;
747 for(RouteTerminal terminal : terminals)
748 terminal.line = line;
749 isSimpleConnection = false;
754 public double[] getLineLengths(RouteTerminal terminal) {
757 if(lines.size()==0 && transientLines.size()==1)
758 return new double[] { transientLines.get(0).getLength() };
760 RouteLine line = null;
762 for(RouteLine l : transientLines)
763 if(l.isTransient()) {
764 for(RoutePoint p : l.points)
765 if(!(p instanceof RouteLink)) {
770 TDoubleArrayList result = new TDoubleArrayList();
771 THashSet<RouteLine> set = new THashSet<RouteLine>();
775 result.add(line.getLength());
776 for(RoutePoint point : line.points)
777 if(point instanceof RouteLink) {
778 RouteLink link = (RouteLink)point;
779 if(set.add(link.a)) {
783 if(set.add(link.b)) {
790 return result.toArray();
793 public void split(RouteLine rl1, double splitPosition) {
796 boolean isHorizontal = rl1.isHorizontal();
797 if(isSimpleConnection) {
798 isSimpleConnection = false;
800 RouteLine sp = addLine(!isHorizontal, splitPosition);
801 for(RouteTerminal terminal : terminals)
806 else if(caseId < 4) {
807 RouteLine sp = addLine(!isHorizontal, splitPosition);
808 RouteLine l = addLine(isHorizontal, rl1.position);
810 rl1.terminal.line = sp;
811 for(RouteTerminal terminal : terminals)
812 if(terminal != rl1.terminal)
818 prepareForModification();
821 RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
822 RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
824 ArrayList<RoutePoint> points = rl1.points;
829 int maxPos = points.size();
830 while(minPos != maxPos) {
831 int c = (minPos + maxPos)/2;
833 ? points.get(c).getX() > splitPosition
834 : points.get(c).getY() > splitPosition)
842 for(int i=points.size()-1;i>=splitPos;--i) {
843 RoutePoint point = points.remove(i);
844 if(point instanceof RouteLink) {
845 RouteLink link = (RouteLink)point;
846 link.replace(rl1, rl2);
850 if(rl1.isTransient()) {
851 boolean p1 = rl1.isConnectedToPeristentLine();
852 boolean p2 = rl2.isConnectedToPeristentLine();
854 RouteTerminal terminal = rl1.terminal;
857 transientLines.add(rl2);
863 transientLines.add(rl2);
865 for(RouteTerminal t : terminals)
873 new RouteLink(rl1, sp);
874 new RouteLink(sp, rl2);
879 public boolean merge(RouteLine line) {
882 for(RoutePoint point : line.points) {
883 if(point instanceof RouteLink) {
884 RouteLink link = (RouteLink)point;
885 RouteLine other = link.getOther(line);
886 if(!other.isTransient()) {
887 sum += other.position;
892 return merge(line, sum / count);
896 * Removes given route line and collapses all its neighbor
897 * route lines into one line with given position.
899 public boolean merge(RouteLine line, double position) {
902 if(isSimpleConnection || line.isTransient())
905 if(lines.size() == 1) {
906 if(terminals.size() != 2)
909 isSimpleConnection = true;
910 for(RouteTerminal terminal : terminals)
911 terminal.line = null;
916 ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
917 for(RoutePoint point : line.points) {
918 /* Because line.terminal == null, there should be
921 * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
923 if (point instanceof RouteLink) {
924 RouteLine l = ((RouteLink)point).getOther(line);
925 l.points.remove(point);
933 RouteLine merged = nLines.remove(nLines.size()-1);
934 merged.position = position;
935 for(RouteLine l : nLines) {
936 for(RoutePoint point : l.points) {
937 /* Because l.terminal == null, there should be
940 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
942 if (point instanceof RouteLink) {
943 RouteLink link = (RouteLink)point;
944 link.replace(l, merged);
948 THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
949 removedLines.addAll(nLines);
950 lines.removeAll(removedLines);
951 removedLines.add(line);
953 for(RouteTerminal terminal : terminals)
954 if(removedLines.contains(terminal.line))
955 terminal.line = merged;
960 public void deleteCorner(RouteLink link) {
963 RouteLine a = link.getA();
964 RouteLine b = link.getB();
965 if(a.isTransient() || b.isTransient()
966 || a.points.size() != 2 || b.points.size() != 2)
968 RouteLine na=null, nb=null;
969 for(RoutePoint p : a.points) {
970 RouteLink l = (RouteLink)p;
971 if(l.a == a && l.b != b) {
975 else if(l.b == a && l.a != b) {
980 for(RoutePoint p : b.points) {
981 RouteLink l = (RouteLink)p;
982 if(l.a == b && l.b != a) {
986 else if(l.b == b && l.a != a) {
991 if(na == null || nb == null) {
992 System.err.println("Internal error in router.");
1000 if(na.terminal != null)
1001 na.terminal.line = nb;
1002 if(nb.terminal != null)
1003 nb.terminal.line = na;
1007 public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1008 Object target = pick(x, y, tolerance);
1009 if(target instanceof RouteLine) {
1010 RouteLine line = (RouteLine)target;
1011 RouteTerminal involvedTerminal =
1012 line.isTransient() ? line.terminal : null;
1013 makePersistent(line);
1014 terminal.line = null; // TODO this is a workaround
1016 int lineDir = line.isHorizontal
1017 ? (line.position < terminal.y ? 3 : 1)
1018 : (line.position < terminal.x ? 2 : 0)
1021 if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1023 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1024 RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1025 l2 = addLine(false, x);
1026 link(terminal, l1, l2, line);
1029 l2 = addLine(false, x);
1030 link(terminal, l2, line);
1032 if(involvedTerminal != null)
1033 involvedTerminal.line = l2;
1035 else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1037 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1038 RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1039 l2 = addLine(true, y);
1040 link(terminal, l1, l2, line);
1043 l2 = addLine(true, y);
1044 link(terminal, l2, line);
1046 if(involvedTerminal != null)
1047 involvedTerminal.line = l2;
1050 link(terminal, line);
1059 public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1060 Object target = pick(x, y, tolerance);
1061 if(target instanceof RouteLine) {
1062 RouteLine line = (RouteLine)target;
1063 RouteTerminal involvedTerminal =
1064 line.isTransient() ? line.terminal : null;
1065 makePersistent(line);
1066 if(line.isHorizontal == sLine.isHorizontal) {
1067 RouteLine l = addLine(!sLine.isHorizontal,
1068 sLine.isHorizontal ? x : y);
1069 link(sLine, l, line);
1070 if(involvedTerminal != null)
1071 involvedTerminal.line = l;
1075 if(involvedTerminal != null)
1076 involvedTerminal.line = sLine;
1086 * Makes a deep copy of the route graph and stores
1087 * the correspondences between original and copied
1088 * objects into the given map.
1090 public RouteGraph copy(THashMap<Object, Object> map) {
1091 RouteGraph copy = new RouteGraph();
1092 copy.isSimpleConnection = isSimpleConnection;
1093 copy.caseId = caseId;
1094 copy.needsUpdate = needsUpdate;
1095 for(RouteLine line : lines)
1096 copy.lines.add(line.copy(map));
1097 for(RouteLine line : transientLines)
1098 copy.transientLines.add(line.copy(map));
1099 for(RouteTerminal terminal : terminals)
1100 copy.terminals.add(terminal.copy(map));
1105 * Makes a deep copy of the route graph.
1107 public RouteGraph copy() {
1108 THashMap<Object, Object> map = new THashMap<Object, Object>();
1113 * Removes route lines that are conneted to at most
1114 * one other route line or terminal.
1116 public void removeExtraConnections() {
1117 TObjectIntHashMap<RouteLine> counts =
1118 new TObjectIntHashMap<RouteLine>();
1119 removeTransientRouteLines();
1120 for(RouteLine line : lines) {
1122 for(RoutePoint point : line.points)
1123 if(point instanceof RouteLink)
1125 counts.put(line, count);
1127 for(RouteTerminal terminal : terminals)
1128 counts.adjustOrPutValue(terminal.line, 1, 1);
1132 Iterator<RouteLine> it = lines.iterator();
1133 while(it.hasNext()) {
1134 RouteLine line = it.next();
1135 if(counts.get(line) <= 1) {
1136 for(RoutePoint point : line.points)
1137 if(point instanceof RouteLink)
1138 counts.adjustValue(((RouteLink)point).getOther(line), -1);
1149 * Removes a terminal and all route lines that become degenerated by the removal.
1151 public void remove(RouteTerminal terminal) {
1152 terminals.remove(terminal);
1153 removeExtraConnections();
1156 public void disconnect(RouteTerminal terminal) {
1157 terminal.line = null;
1158 removeExtraConnections();
1161 public void remove(RouteLink link) {
1162 link.a.points.remove(link);
1163 link.b.points.remove(link);
1166 public void toggleDirectLines(RouteTerminal terminal) {
1167 terminal.toggleDirectLines();
1172 * Returns all persistent route lines of the route graph.
1174 public Collection<RouteLine> getLines() {
1177 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1178 return Collections.unmodifiableList(lines);
1184 * Returns all transient route lines of the route graph.
1186 public Collection<RouteLine> getTransientLines() {
1189 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1190 return Collections.unmodifiableList(transientLines);
1192 return transientLines;
1196 * Returns all terminals of the route graph.
1198 public Collection<RouteTerminal> getTerminals() {
1199 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1200 return Collections.unmodifiableList(terminals);
1206 * Returns all route lines, both persistent and transient,
1207 * of the route graph.
1209 public Collection<RouteLine> getAllLines() {
1212 ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1213 allLines.addAll(lines);
1214 allLines.addAll(transientLines);
1219 * Returns all route lines, both persistent and transient, of the route
1220 * graph, added to the specified collection. Avoids allocation of new
1221 * {@link ArrayList} compared to {@link #getAllLines()}.
1223 public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1225 throw new NullPointerException("null result collection");
1228 result.addAll(lines);
1229 result.addAll(transientLines);
1234 * Returns true, if the route graph is connected and contains no cycles.
1236 public boolean isTree() {
1237 if(isSimpleConnection)
1239 for(RouteTerminal terminal : terminals)
1240 if(terminal.line == null)
1242 THashSet<RouteLine> visited = new THashSet<RouteLine>();
1243 ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1245 visited.add(lines.get(0));
1246 stack.add(lines.get(0));
1247 while(!stack.isEmpty()) {
1248 RouteLine cur = stack.remove(stack.size()-1);
1249 for(RouteLine n : cur.getPersistentNeighbors()) {
1255 return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1259 * Returns if the connection is simple. A connection is simple, if it has just
1260 * two terminals connected together directly without (persistent) route lines.
1262 public boolean isSimpleConnection() {
1263 return isSimpleConnection;
1266 public void replaceBy(RouteGraph rg) {
1267 this.lines = rg.lines;
1268 this.terminals = rg.terminals;
1269 this.transientLines = rg.transientLines;
1270 this.caseId = rg.caseId;
1271 this.isSimpleConnection = rg.isSimpleConnection;
1272 this.needsUpdate = rg.needsUpdate;
1276 private void reset() {
1277 lines = new ArrayList<RouteLine>();
1278 terminals = new ArrayList<RouteTerminal>();
1279 transientLines = new ArrayList<RouteLine>();
1281 isSimpleConnection = false;
1282 needsUpdate = false;
1285 public Rectangle2D getBounds() {
1286 Rectangle2D bounds = new Rectangle2D.Double();
1291 public void getBounds(Rectangle2D bounds) {
1294 double minX = Double.POSITIVE_INFINITY;
1295 double maxX = Double.NEGATIVE_INFINITY;
1296 double minY = Double.POSITIVE_INFINITY;
1297 double maxY = Double.NEGATIVE_INFINITY;
1298 for(RouteLine line : lines) {
1299 double position = line.position;
1300 if(line.isHorizontal) {
1301 minY = Math.min(minY, position);
1302 maxY = Math.max(maxY, position);
1305 minX = Math.min(minX, position);
1306 maxX = Math.max(maxX, position);
1309 for(RouteLine line : transientLines) {
1310 double position = line.position;
1311 if(line.isHorizontal) {
1312 minY = Math.min(minY, position);
1313 maxY = Math.max(maxY, position);
1316 minX = Math.min(minX, position);
1317 maxX = Math.max(maxX, position);
1320 for(RouteTerminal terminal : terminals) {
1321 double x = terminal.x;
1322 double y = terminal.y;
1323 minX = Math.min(minX, x);
1324 maxX = Math.max(maxX, x);
1325 minY = Math.min(minY, y);
1326 maxY = Math.max(maxY, y);
1328 bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1331 private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1332 double x = cur.x, y = cur.y;
1333 if(cur instanceof RouteTerminal) {
1334 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1335 if(line.isHorizontal()) {
1336 if(cur == line.getBegin())
1337 x += style.getLineEndLength(0);
1339 x -= style.getLineEndLength(2);
1342 if(cur == line.getBegin())
1343 y += style.getLineEndLength(1);
1345 y -= style.getLineEndLength(3);
1351 private static final Comparator<RoutePoint> RG_COMP = (o1, o2) -> {
1352 if (o1.getX() < o2.getX())
1354 else if (o1.getX() > o2.getX())
1356 if (o1.getY() < o2.getY())
1358 else if (o1.getY() > o2.getY())
1363 private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1364 double x = cur.x, y = cur.y;
1365 if(cur instanceof RouteTerminal) {
1366 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1367 if(line.isHorizontal()) {
1368 if(cur == line.getBegin())
1369 x += style.getLineEndLength(0);
1371 x -= style.getLineEndLength(2);
1374 if(cur == line.getBegin())
1375 y += style.getLineEndLength(1);
1377 y -= style.getLineEndLength(3);
1383 public void getPath2D(Path2D path) {
1387 if(isSimpleConnection && transientLines.isEmpty()) {
1388 if(terminals.size() == 2) {
1389 RouteTerminal a = terminals.get(0);
1390 RouteTerminal b = terminals.get(1);
1391 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1392 path.moveTo(a.x, a.y);
1393 path.lineTo(b.x, b.y);
1400 Map<RoutePoint, RouteLine> begins =
1401 // new THashMap<RoutePoint, RouteLine>(); //The ordering of the coordinates in the path should be deterministic between scenegraphs
1402 new TreeMap<RoutePoint, RouteLine>(RG_COMP);
1403 for(RouteLine line : lines) {
1406 for(RouteLine line : transientLines) {
1409 for(RouteTerminal terminal : terminals)
1410 if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1411 begins.remove(terminal.line.getBegin());
1412 drawContinuousPath(path, begins, terminal, terminal.line);
1416 for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1417 RouteLine curLine = begins.remove(begin);
1418 drawContinuousPath(path, begins, begin, curLine);
1422 private void drawContinuousPath(Path2D path, Map<RoutePoint, RouteLine> begins,
1423 RoutePoint cur, RouteLine curLine) {
1426 addPathBegin(path, cur, curLine);
1429 if(cur != curLine.getEnd())
1430 cur = curLine.getEnd();
1432 cur = curLine.getBegin();
1433 if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1434 addPathEnd(path, cur, curLine);
1437 if(cur instanceof RouteLink) {
1438 if(!curLine.isDegenerated() ||
1439 path.getCurrentPoint().getX() != cur.x ||
1440 path.getCurrentPoint().getY() != cur.y)
1441 path.lineTo(cur.x, cur.y);
1442 RouteLink link = (RouteLink)cur;
1443 if(link.a != curLine)
1451 private static void add(Map<RoutePoint, RouteLine> begins,
1453 if(line.points.size() > 1) {
1455 RoutePoint p = line.getBegin();
1456 if(begins.remove(p) == null)
1457 begins.put(p, line);
1460 RoutePoint p = line.getEnd();
1461 if(begins.remove(p) == null)
1462 begins.put(p, line);
1467 public Collection<Segment> getSegments() {
1470 ArrayList<Segment> segments = new ArrayList<Segment>();
1471 for(RouteLine routeLine : lines)
1472 routeLine.collectSegments(segments);
1473 for(RouteLine routeLine : transientLines)
1474 routeLine.collectSegments(segments);
1478 public Path2D getPath2D() {
1479 Path2D result = new Path2D.Double();
1484 public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1485 THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1486 THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1487 THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1488 THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1489 THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1490 THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1492 if(splitLine.isTransient()) {
1493 RouteTerminal terminal = splitLine.terminal;
1495 if(splitLine.beginsWithTerminal()) {
1496 lines2.addAll(getLines());
1497 terminals2.addAll(getTerminals());
1498 terminals1.add(terminal);
1499 terminals2.remove(terminal);
1500 interfaceNodes1.add(terminal);
1501 if(isSimpleConnection())
1502 interfaceNodes2.addAll(terminals2);
1504 interfaceNodes2.add(terminal.line);
1507 lines1.addAll(getLines());
1508 terminals1.addAll(getTerminals());
1509 terminals2.add(terminal);
1510 terminals1.remove(terminal);
1511 interfaceNodes2.add(terminal);
1512 if(isSimpleConnection())
1513 interfaceNodes1.addAll(terminals1);
1515 interfaceNodes1.add(terminal.line);
1519 for(RoutePoint rp : splitLine.getPoints()) {
1520 double p = splitLine.isHorizontal ? rp.x : rp.y;
1521 if(rp instanceof RouteLink) {
1522 RouteLink link = (RouteLink)rp;
1523 RouteLine otherLine = link.getA() != splitLine ? link.getA()
1525 if(otherLine.isTransient()) {
1527 interfaceNodes1.add(otherLine.terminal);
1528 terminals1.add(otherLine.terminal);
1531 interfaceNodes2.add(otherLine.terminal);
1532 terminals2.add(otherLine.terminal);
1538 interfaceNodes1.add(otherLine);
1539 traverseGraph(link, otherLine, lines1);
1542 interfaceNodes2.add(otherLine);
1543 traverseGraph(link, otherLine, lines2);
1548 for(RouteTerminal terminal : getTerminals())
1549 if(lines1.contains(terminal.line))
1550 terminals1.add(terminal);
1551 else if(lines2.contains(terminal.line))
1552 terminals2.add(terminal);
1555 return new SplittedRouteGraph(splitLine,
1556 interfaceNodes1, lines1, terminals1,
1557 interfaceNodes2, lines2, terminals2);
1560 private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1561 THashSet<RouteLine> lines) {
1562 if(lines.add(line)) {
1563 for(RoutePoint rp : line.getPoints()) {
1564 if(rp != previousPoint && rp instanceof RouteLink) {
1565 RouteLink link = (RouteLink)rp;
1566 RouteLine otherLine = line != link.getA()
1567 ? link.getA() : link.getB();
1568 if(otherLine.isTransient())
1570 traverseGraph(rp, otherLine, lines);
1576 public void reclaimTransientMemory() {
1577 removeTransientRouteLines();