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.Iterator;
29 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
30 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
31 import org.simantics.diagram.connection.segments.Segment;
32 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
34 public class RouteGraph implements Serializable {
36 private static final long serialVersionUID = 2004022454972623908L;
38 public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
39 public static final boolean CHECK_PARAMERS = true;
41 ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
42 ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
43 ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
45 boolean isSimpleConnection;
46 boolean needsUpdate = false;
48 public void updateTerminals() {
49 boolean changed = false;
50 for(RouteTerminal terminal : terminals)
51 changed |= terminal.updateDynamicPosition();
56 * Adds a route line to the graph.
57 * @param isHorizontal true, if the line is horizontal
58 * @param position y coordinate of the line if horizontal, x coordinate if vertical
59 * @return The new line.
61 public RouteLine addLine(boolean isHorizontal, double position) {
62 RouteLine line = new RouteLine(isHorizontal, position);
68 * Adds a route terminal to the graph.
69 * @param x The location of the terminal.
71 * @param minX The avoidance area of the terminal.
75 * @param allowedDirections Allowed directions.
76 * First four bits tell with which directions
77 * a connection can leave the terminal. The
78 * Fifth bit indicates whether direct lines
79 * can be drawn to the terminal. Directions are
86 * @param style Tells what kind of line end is drawn
88 * @param position a provider for a dynamic position for the terminal or
89 * <code>null</code> if terminal position is not dynamic
90 * @return The new terminal.
92 public RouteTerminal addTerminal(double x, double y,
93 double minX, double minY,
94 double maxX, double maxY,
95 int allowedDirections,
96 ILineEndStyle style, RouteTerminalPosition position) {
97 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
100 public RouteTerminal addTerminal(double x, double y,
101 double minX, double minY,
102 double maxX, double maxY,
103 int allowedDirections,
104 ILineEndStyle style) {
105 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
108 public RouteTerminal addTerminal(double x, double y,
109 double minX, double minY,
110 double maxX, double maxY,
111 int allowedDirections,
112 ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
114 if(allowedDirections > 0x1f)
115 throw new IllegalArgumentException("Illegal allowedDirection flags.");
116 if(minX > x || x > maxX || minY > y || y > maxY)
117 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
120 style = PlainLineEndStyle.INSTANCE;
121 RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
122 maxX, maxY, allowedDirections, false, style, position);
123 terminal.setDynamicStyle(dynamicStyle);
124 terminals.add(terminal);
128 public RouteTerminal addBigTerminal(
129 double minX, double minY,
130 double maxX, double maxY,
131 ILineEndStyle style) {
132 return addBigTerminal(minX, minY, maxX, maxY, style, null);
134 public RouteTerminal addBigTerminal(
135 double minX, double minY,
136 double maxX, double maxY,
137 ILineEndStyle style, ILineEndStyle dynamicStyle) {
139 style = PlainLineEndStyle.INSTANCE;
140 RouteTerminal terminal = new RouteTerminal(
141 0.5*(minX+maxX), 0.5*(minY+maxY),
144 0xf, true, style, null);
145 terminal.setDynamicStyle(dynamicStyle);
147 terminals.add(terminal);
152 * Adds a route terminal to the graph. The avoidance
153 * area is given as a rectangle.
154 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
156 public RouteTerminal addTerminal(double x, double y,
158 int allowedDirections,
159 ILineEndStyle style) {
160 return addTerminal(x, y,
161 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
162 allowedDirections, style, null);
166 * Adds a copy of the given terminal to the graph.
168 public RouteTerminal addTerminal(RouteTerminal terminal) {
169 RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
170 terminal.getMinX(), terminal.getMinY(),
171 terminal.getMaxX(), terminal.getMaxY(),
172 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
173 newTerminal.setData(terminal.getData());
178 * Adds a route terminal to the graph. A default line end style is used.
179 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
181 public RouteTerminal addTerminal(double x, double y,
182 double minX, double minY,
183 double maxX, double maxY,
184 int allowedDirections) {
185 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
186 PlainLineEndStyle.INSTANCE, null);
192 public void link(RouteNode node1, RouteNode node2) {
193 if(node1 instanceof RouteLine) {
194 if(node2 instanceof RouteLine) {
195 link((RouteLine)node1, (RouteLine)node2);
198 link((RouteLine)node1, (RouteTerminal)node2);
202 if(node2 instanceof RouteLine) {
203 link((RouteTerminal)node1, (RouteLine)node2);
206 link((RouteTerminal)node1, (RouteTerminal)node2);
214 public void link(RouteNode ... nodes) {
215 for(int i=1;i<nodes.length;++i)
216 link(nodes[i-1], nodes[i]);
222 public void link(RouteLine node1, RouteLine node2) {
223 new RouteLink(node1, node2);
228 * Links a terminal and a line.
230 public void link(RouteTerminal node1, RouteLine node2) {
233 throw new NullPointerException();
234 if(node1.line != null)
235 throw new IllegalStateException("Terminal is already connected.");
242 * Links a line and a terminal.
244 public void link(RouteLine node1, RouteTerminal node2) {
247 throw new NullPointerException();
248 if(node2.line != null)
249 throw new IllegalStateException("Terminal is already connected.");
256 * Links two terminals.
258 public void link(RouteTerminal node1, RouteTerminal node2) {
261 throw new NullPointerException();
263 throw new NullPointerException();
265 isSimpleConnection = true;
269 void removeTransientRouteLines() {
270 for(RouteLine line : transientLines)
272 transientLines.clear();
276 * Rotates given terminal clockwise by given amount
277 * (also negative numbers are allowed).
279 public void rotate(RouteTerminal terminal, int amount) {
280 terminal.rotate(amount);
285 * Moves the given route line so that its position correspond
286 * to given x or y depending on the orientation of the line.
288 public void setLocation(RouteLine line, double x, double y) {
289 makePersistent(line);
290 line.setLocation(x, y);
295 * Moves the terminal to given location.
297 public void setLocation(RouteTerminal terminal, double x, double y) {
298 terminal.setLocation(x, y);
303 * Updates transient route lines, route link positions
304 * and sorts route points of each route line.
306 public void update() {
308 removeTransientRouteLines();
312 for(RouteLine line : lines)
314 for(RouteTerminal terminal : terminals)
315 if(terminal.hasDirectConnection() && terminal.line != null)
316 terminal.line.hidden = true;
319 if(isSimpleConnection) {
320 RouteTerminal a = terminals.get(0);
321 RouteTerminal b = terminals.get(1);
322 if(a.hasDirectConnection() || b.hasDirectConnection())
324 caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
325 //System.out.println("caseId = " + caseId);
327 case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
328 case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
329 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
330 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
334 transientLines.add(line);
337 case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
338 RouteLine line1 = new RouteLine(true, a.y);
339 RouteLine line2 = new RouteLine(false, b.x);
340 new RouteLink(line1, line2);
345 transientLines.add(line1);
346 transientLines.add(line2);
349 case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
350 RouteLine line1 = new RouteLine(false, a.x);
351 RouteLine line2 = new RouteLine(true, b.y);
352 new RouteLink(line1, line2);
357 transientLines.add(line1);
358 transientLines.add(line2);
361 case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
362 case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
364 SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
365 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
367 terminals.get(0).line = line;
368 terminals.get(1).line = line;
369 transientLines.add(line);
370 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
376 caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
377 routeFromTerminals(false);
380 // Find positions of route points
381 for(RouteLine line : lines)
382 line.setPointPositions();
383 for(RouteLine line : transientLines)
384 line.setPointPositions();
386 // Sort route points in route lines
387 for(RouteLine line : lines) {
390 for(RouteLine line : transientLines) {
395 static class Interval {
396 public final double min;
397 public final double max;
398 public Interval(double min, double max) {
404 class IntervalCache {
405 THashMap<RouteLine, Interval> cache =
406 new THashMap<RouteLine, Interval>();
407 public Interval get(RouteLine line) {
408 Interval result = cache.get(line);
412 result = create(line);
413 cache.put(line, result);
417 private Interval create(RouteLine line) {
418 double min = Double.POSITIVE_INFINITY;
419 double max = Double.NEGATIVE_INFINITY;
421 for(RoutePoint point : line.points) {
423 if(point instanceof RouteLink) {
424 RouteLink link = (RouteLink)point;
426 temp = link.b.position;
428 temp = link.a.position;
431 RouteTerminal terminal = (RouteTerminal)point;
432 if(line.isHorizontal)
442 for(RouteTerminal terminal : terminals) {
443 if(terminal.line == line) {
444 double temp = terminal.approximatePositionToLine();
452 return new Interval(min, max);
456 private void routeFromTerminals(boolean boundingBoxesIntersect) {
457 IntervalCache cache = new IntervalCache();
458 for(RouteTerminal terminal : terminals)
459 if(terminal.line != null) {
460 if(!terminal.hasDirectConnection())
461 terminal.route(transientLines, cache, boundingBoxesIntersect);
466 * Returns a RouteLine near the given point (x,y) (within tolerance).
468 public RouteLine pickLine(double x, double y, double tolerance, int mask) {
471 if(isSimpleConnection && transientLines.isEmpty()) {
472 if(terminals.size() == 2) {
473 if((mask & PICK_TRANSIENT_LINES) == 0)
475 RouteTerminal a = terminals.get(0);
476 RouteTerminal b = terminals.get(1);
477 if(a.hasDirectConnection() || b.hasDirectConnection()) {
478 if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
479 RouteLine dummy = new RouteLine(false, y);
480 return dummy; // There are no lines to return
487 if((mask & PICK_PERSISTENT_LINES) != 0)
488 for(RouteLine line : lines)
489 if(line.isNear(x, y, tolerance))
491 if((mask & PICK_TRANSIENT_LINES) != 0)
492 for(RouteLine line : transientLines)
493 if(line.isNear(x, y, tolerance))
495 if((mask & PICK_DIRECT_LINES) != 0) {
496 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
498 return terminal.line;
503 public RouteLine pickLine(double x, double y, double tolerance) {
504 return pickLine(x, y, tolerance, PICK_LINES);
507 private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
508 double toleranceSq = tolerance * tolerance;
509 for(RouteTerminal terminal : terminals)
510 if((terminal.getAllowedDirections()&0x10) != 0) {
512 RouteLine line = terminal.getLine();
515 RoutePoint b = line.getBegin();
516 double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
517 if(distSq <= toleranceSq) {
518 //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
521 } catch(NullPointerException e) {
522 //if terminal does not have a line
524 } catch(IndexOutOfBoundsException e) {
525 // if line does not contain points
532 public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
533 if(isSimpleConnection)
537 RouteLine line = pickLine(x, y, tolerance);
540 RouteLink link = null;
541 RoutePoint begin = line.getBegin();
542 RoutePoint end = line.getEnd();
543 if(line.isHorizontal) {
544 double mx = 0.5*(begin.getX() + end.getX());
546 if(begin instanceof RouteLink)
547 link = (RouteLink)begin;
550 if(end instanceof RouteLink)
551 link = (RouteLink)line.getEnd();
555 double my = 0.5*(begin.getY() + end.getY());
557 if(begin instanceof RouteLink)
558 link = (RouteLink)begin;
561 if(end instanceof RouteLink)
562 link = (RouteLink)end;
567 if(link.getOther(line).isTransient())
569 return new RouteLineHalf(line, link);
572 public Collection<RouteLineHalf> getLineHalves() {
573 return getLineHalves(new ArrayList<RouteLineHalf>());
576 public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
577 for(RouteLine line : getAllLines()) {
579 RoutePoint p = line.getBegin();
580 if(p instanceof RouteLink) {
581 RouteLink link = (RouteLink)p;
582 if(!link.getOther(line).isTransient())
583 result.add(new RouteLineHalf(line, link));
587 RoutePoint p = line.getEnd();
588 if(p instanceof RouteLink) {
589 RouteLink link = (RouteLink)p;
590 if(!link.getOther(line).isTransient())
591 result.add(new RouteLineHalf(line, link));
599 * Returns a RoutePoint near the given point (x,y) (within tolerance).
601 public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
604 if((mask&PICK_TERMINALS) != 0)
605 for(RouteTerminal terminal : terminals)
606 if(terminal.isNear(x, y))
608 if((mask&PICK_INTERIOR_POINTS) != 0) {
609 for(RouteLine line : lines) {
610 for(RoutePoint point : line.points)
611 if(point.isNear(x, y, tolerance))
614 for(RouteLine line : transientLines) {
615 for(RoutePoint point : line.points)
616 if(point.isNear(x, y, tolerance))
623 public RoutePoint pickPoint(double x, double y, double tolerance) {
624 return pickPoint(x, y, tolerance, PICK_POINTS);
627 public static final int PICK_INTERIOR_POINTS = 1;
628 public static final int PICK_TERMINALS = 2;
629 public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
631 public static final int PICK_PERSISTENT_LINES = 4;
632 public static final int PICK_TRANSIENT_LINES = 8;
633 public static final int PICK_DIRECT_LINES = 16;
634 public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
636 public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
639 * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
641 public Object pick(double x, double y, double tolerance, int mask) {
642 if((mask & PICK_POINTS) != 0) {
643 Object point = pickPoint(x, y, tolerance, mask);
647 /*if((mask & PICK_DIRECT_LINES) != 0) {
648 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
650 return terminal.line.getBegin();
652 if((mask & PICK_LINES) != 0)
653 return pickLine(x, y, tolerance, mask);
658 public Object pick(double x, double y, double tolerance) {
659 return pick(x, y, tolerance, PICK_ALL);
663 * Returns RoutePoint or RouteLine exactly under the given point (x,y).
665 public Object pick(double x, double y) {
666 return pick(x, y, 0.0);
670 * Prints the contents of the route graph to stdout.
672 public void print() {
677 * Prints the contents of the route graph to given print stream.
679 public void print(PrintStream out) {
682 if(isSimpleConnection)
683 out.println("=== SIMPLE CONNECTION ===");
685 out.println("=== COMPLEX CONNECTION ===");
686 for(RouteLine line : lines) {
690 for(RouteLine line : transientLines) {
694 for(RouteTerminal terminal : terminals) {
700 public void makePersistent(RouteLine line) {
701 prepareForModification();
702 if(isSimpleConnection || line.isTransient()) {
703 if(isSimpleConnection) {
704 isSimpleConnection = false;
705 for(RouteTerminal terminal : terminals)
706 terminal.line = line;
707 transientLines.remove(line);
709 Iterator<RoutePoint> it = line.points.iterator();
710 while(it.hasNext()) {
711 RoutePoint point = it.next();
712 if(point instanceof RouteTerminal)
715 line.terminal = null;
716 line.nextTransient = null;
719 line.terminal.line = line;
721 transientLines.remove(line);
723 Iterator<RoutePoint> it = line.points.iterator();
724 while(it.hasNext()) {
725 RoutePoint point = it.next();
726 if(point instanceof RouteTerminal)
729 line.terminal = null;
730 RouteLine temp = line.nextTransient;
731 line.nextTransient = null;
733 } while(line != null);
739 void prepareForModification() {
741 RouteLine line = transientLines.remove(0);
742 line.terminal = null;
744 for(RouteTerminal terminal : terminals)
745 terminal.line = line;
746 isSimpleConnection = false;
751 public double[] getLineLengths(RouteTerminal terminal) {
754 if(lines.size()==0 && transientLines.size()==1)
755 return new double[] { transientLines.get(0).getLength() };
757 RouteLine line = null;
759 for(RouteLine l : transientLines)
760 if(l.isTransient()) {
761 for(RoutePoint p : l.points)
762 if(!(p instanceof RouteLink)) {
767 TDoubleArrayList result = new TDoubleArrayList();
768 THashSet<RouteLine> set = new THashSet<RouteLine>();
772 result.add(line.getLength());
773 for(RoutePoint point : line.points)
774 if(point instanceof RouteLink) {
775 RouteLink link = (RouteLink)point;
776 if(set.add(link.a)) {
780 if(set.add(link.b)) {
787 return result.toArray();
790 public void split(RouteLine rl1, double splitPosition) {
793 boolean isHorizontal = rl1.isHorizontal();
794 if(isSimpleConnection) {
795 isSimpleConnection = false;
797 RouteLine sp = addLine(!isHorizontal, splitPosition);
798 for(RouteTerminal terminal : terminals)
803 else if(caseId < 4) {
804 RouteLine sp = addLine(!isHorizontal, splitPosition);
805 RouteLine l = addLine(isHorizontal, rl1.position);
807 rl1.terminal.line = sp;
808 for(RouteTerminal terminal : terminals)
809 if(terminal != rl1.terminal)
815 prepareForModification();
818 RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
819 RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
821 ArrayList<RoutePoint> points = rl1.points;
826 int maxPos = points.size();
827 while(minPos != maxPos) {
828 int c = (minPos + maxPos)/2;
830 ? points.get(c).getX() > splitPosition
831 : points.get(c).getY() > splitPosition)
839 for(int i=points.size()-1;i>=splitPos;--i) {
840 RoutePoint point = points.remove(i);
841 if(point instanceof RouteLink) {
842 RouteLink link = (RouteLink)point;
843 link.replace(rl1, rl2);
847 if(rl1.isTransient()) {
848 boolean p1 = rl1.isConnectedToPeristentLine();
849 boolean p2 = rl2.isConnectedToPeristentLine();
851 RouteTerminal terminal = rl1.terminal;
854 transientLines.add(rl2);
860 transientLines.add(rl2);
862 for(RouteTerminal t : terminals)
870 new RouteLink(rl1, sp);
871 new RouteLink(sp, rl2);
876 public boolean merge(RouteLine line) {
879 for(RoutePoint point : line.points) {
880 if(point instanceof RouteLink) {
881 RouteLink link = (RouteLink)point;
882 RouteLine other = link.getOther(line);
883 if(!other.isTransient()) {
884 sum += other.position;
889 return merge(line, sum / count);
893 * Removes given route line and collapses all its neighbor
894 * route lines into one line with given position.
896 public boolean merge(RouteLine line, double position) {
899 if(isSimpleConnection || line.isTransient())
902 if(lines.size() == 1) {
903 if(terminals.size() != 2)
906 isSimpleConnection = true;
907 for(RouteTerminal terminal : terminals)
908 terminal.line = null;
913 ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
914 for(RoutePoint point : line.points) {
915 /* Because line.terminal == null, there should be
918 * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
920 if (point instanceof RouteLink) {
921 RouteLine l = ((RouteLink)point).getOther(line);
922 l.points.remove(point);
930 RouteLine merged = nLines.remove(nLines.size()-1);
931 merged.position = position;
932 for(RouteLine l : nLines) {
933 for(RoutePoint point : l.points) {
934 /* Because l.terminal == null, there should be
937 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
939 if (point instanceof RouteLink) {
940 RouteLink link = (RouteLink)point;
941 link.replace(l, merged);
945 THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
946 removedLines.addAll(nLines);
947 lines.removeAll(removedLines);
948 removedLines.add(line);
950 for(RouteTerminal terminal : terminals)
951 if(removedLines.contains(terminal.line))
952 terminal.line = merged;
957 public void deleteCorner(RouteLink link) {
960 RouteLine a = link.getA();
961 RouteLine b = link.getB();
962 if(a.isTransient() || b.isTransient()
963 || a.points.size() != 2 || b.points.size() != 2)
965 RouteLine na=null, nb=null;
966 for(RoutePoint p : a.points) {
967 RouteLink l = (RouteLink)p;
968 if(l.a == a && l.b != b) {
972 else if(l.b == a && l.a != b) {
977 for(RoutePoint p : b.points) {
978 RouteLink l = (RouteLink)p;
979 if(l.a == b && l.b != a) {
983 else if(l.b == b && l.a != a) {
988 if(na == null || nb == null) {
989 System.err.println("Internal error in router.");
997 if(na.terminal != null)
998 na.terminal.line = nb;
999 if(nb.terminal != null)
1000 nb.terminal.line = na;
1004 public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1005 Object target = pick(x, y, tolerance);
1006 if(target instanceof RouteLine) {
1007 RouteLine line = (RouteLine)target;
1008 RouteTerminal involvedTerminal =
1009 line.isTransient() ? line.terminal : null;
1010 makePersistent(line);
1011 terminal.line = null; // TODO this is a workaround
1013 int lineDir = line.isHorizontal
1014 ? (line.position < terminal.y ? 3 : 1)
1015 : (line.position < terminal.x ? 2 : 0)
1018 if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1020 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1021 RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1022 l2 = addLine(false, x);
1023 link(terminal, l1, l2, line);
1026 l2 = addLine(false, x);
1027 link(terminal, l2, line);
1029 if(involvedTerminal != null)
1030 involvedTerminal.line = l2;
1032 else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1034 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1035 RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1036 l2 = addLine(true, y);
1037 link(terminal, l1, l2, line);
1040 l2 = addLine(true, y);
1041 link(terminal, l2, line);
1043 if(involvedTerminal != null)
1044 involvedTerminal.line = l2;
1047 link(terminal, line);
1056 public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1057 Object target = pick(x, y, tolerance);
1058 if(target instanceof RouteLine) {
1059 RouteLine line = (RouteLine)target;
1060 RouteTerminal involvedTerminal =
1061 line.isTransient() ? line.terminal : null;
1062 makePersistent(line);
1063 if(line.isHorizontal == sLine.isHorizontal) {
1064 RouteLine l = addLine(!sLine.isHorizontal,
1065 sLine.isHorizontal ? x : y);
1066 link(sLine, l, line);
1067 if(involvedTerminal != null)
1068 involvedTerminal.line = l;
1072 if(involvedTerminal != null)
1073 involvedTerminal.line = sLine;
1083 * Makes a deep copy of the route graph and stores
1084 * the correspondences between original and copied
1085 * objects into the given map.
1087 public RouteGraph copy(THashMap<Object, Object> map) {
1088 RouteGraph copy = new RouteGraph();
1089 copy.isSimpleConnection = isSimpleConnection;
1090 copy.caseId = caseId;
1091 copy.needsUpdate = needsUpdate;
1092 for(RouteLine line : lines)
1093 copy.lines.add(line.copy(map));
1094 for(RouteLine line : transientLines)
1095 copy.transientLines.add(line.copy(map));
1096 for(RouteTerminal terminal : terminals)
1097 copy.terminals.add(terminal.copy(map));
1102 * Makes a deep copy of the route graph.
1104 public RouteGraph copy() {
1105 THashMap<Object, Object> map = new THashMap<Object, Object>();
1110 * Removes route lines that are conneted to at most
1111 * one other route line or terminal.
1113 public void removeExtraConnections() {
1114 TObjectIntHashMap<RouteLine> counts =
1115 new TObjectIntHashMap<RouteLine>();
1116 removeTransientRouteLines();
1117 for(RouteLine line : lines) {
1119 for(RoutePoint point : line.points)
1120 if(point instanceof RouteLink)
1122 counts.put(line, count);
1124 for(RouteTerminal terminal : terminals)
1125 counts.adjustOrPutValue(terminal.line, 1, 1);
1129 Iterator<RouteLine> it = lines.iterator();
1130 while(it.hasNext()) {
1131 RouteLine line = it.next();
1132 if(counts.get(line) <= 1) {
1133 for(RoutePoint point : line.points)
1134 if(point instanceof RouteLink)
1135 counts.adjustValue(((RouteLink)point).getOther(line), -1);
1146 * Removes a terminal and all route lines that become degenerated by the removal.
1148 public void remove(RouteTerminal terminal) {
1149 terminals.remove(terminal);
1150 removeExtraConnections();
1153 public void disconnect(RouteTerminal terminal) {
1154 terminal.line = null;
1155 removeExtraConnections();
1158 public void remove(RouteLink link) {
1159 link.a.points.remove(link);
1160 link.b.points.remove(link);
1163 public void toggleDirectLines(RouteTerminal terminal) {
1164 terminal.toggleDirectLines();
1169 * Returns all persistent route lines of the route graph.
1171 public Collection<RouteLine> getLines() {
1174 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1175 return Collections.unmodifiableList(lines);
1181 * Returns all transient route lines of the route graph.
1183 public Collection<RouteLine> getTransientLines() {
1186 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1187 return Collections.unmodifiableList(transientLines);
1189 return transientLines;
1193 * Returns all terminals of the route graph.
1195 public Collection<RouteTerminal> getTerminals() {
1196 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1197 return Collections.unmodifiableList(terminals);
1203 * Returns all route lines, both persistent and transient,
1204 * of the route graph.
1206 public Collection<RouteLine> getAllLines() {
1209 ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1210 allLines.addAll(lines);
1211 allLines.addAll(transientLines);
1216 * Returns all route lines, both persistent and transient, of the route
1217 * graph, added to the specified collection. Avoids allocation of new
1218 * {@link ArrayList} compared to {@link #getAllLines()}.
1220 public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1222 throw new NullPointerException("null result collection");
1225 result.addAll(lines);
1226 result.addAll(transientLines);
1231 * Returns true, if the route graph is connected and contains no cycles.
1233 public boolean isTree() {
1234 if(isSimpleConnection)
1236 for(RouteTerminal terminal : terminals)
1237 if(terminal.line == null)
1239 THashSet<RouteLine> visited = new THashSet<RouteLine>();
1240 ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1242 visited.add(lines.get(0));
1243 stack.add(lines.get(0));
1244 while(!stack.isEmpty()) {
1245 RouteLine cur = stack.remove(stack.size()-1);
1246 for(RouteLine n : cur.getPersistentNeighbors()) {
1252 return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1256 * Returns if the connection is simple. A connection is simple, if it has just
1257 * two terminals connected together directly without (persistent) route lines.
1259 public boolean isSimpleConnection() {
1260 return isSimpleConnection;
1263 public void replaceBy(RouteGraph rg) {
1264 this.lines = rg.lines;
1265 this.terminals = rg.terminals;
1266 this.transientLines = rg.transientLines;
1267 this.caseId = rg.caseId;
1268 this.isSimpleConnection = rg.isSimpleConnection;
1269 this.needsUpdate = rg.needsUpdate;
1273 private void reset() {
1274 lines = new ArrayList<RouteLine>();
1275 terminals = new ArrayList<RouteTerminal>();
1276 transientLines = new ArrayList<RouteLine>();
1278 isSimpleConnection = false;
1279 needsUpdate = false;
1282 public Rectangle2D getBounds() {
1283 Rectangle2D bounds = new Rectangle2D.Double();
1288 public void getBounds(Rectangle2D bounds) {
1291 double minX = Double.POSITIVE_INFINITY;
1292 double maxX = Double.NEGATIVE_INFINITY;
1293 double minY = Double.POSITIVE_INFINITY;
1294 double maxY = Double.NEGATIVE_INFINITY;
1295 for(RouteLine line : lines) {
1296 double position = line.position;
1297 if(line.isHorizontal) {
1298 minY = Math.min(minY, position);
1299 maxY = Math.max(maxY, position);
1302 minX = Math.min(minX, position);
1303 maxX = Math.max(maxX, position);
1306 for(RouteLine line : transientLines) {
1307 double position = line.position;
1308 if(line.isHorizontal) {
1309 minY = Math.min(minY, position);
1310 maxY = Math.max(maxY, position);
1313 minX = Math.min(minX, position);
1314 maxX = Math.max(maxX, position);
1317 for(RouteTerminal terminal : terminals) {
1318 double x = terminal.x;
1319 double y = terminal.y;
1320 minX = Math.min(minX, x);
1321 maxX = Math.max(maxX, x);
1322 minY = Math.min(minY, y);
1323 maxY = Math.max(maxY, y);
1325 bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1328 private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1329 double x = cur.x, y = cur.y;
1330 if(cur instanceof RouteTerminal) {
1331 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1332 if(line.isHorizontal()) {
1333 if(cur == line.getBegin())
1334 x += style.getLineEndLength(0);
1336 x -= style.getLineEndLength(2);
1339 if(cur == line.getBegin())
1340 y += style.getLineEndLength(1);
1342 y -= style.getLineEndLength(3);
1348 private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1349 double x = cur.x, y = cur.y;
1350 if(cur instanceof RouteTerminal) {
1351 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1352 if(line.isHorizontal()) {
1353 if(cur == line.getBegin())
1354 x += style.getLineEndLength(0);
1356 x -= style.getLineEndLength(2);
1359 if(cur == line.getBegin())
1360 y += style.getLineEndLength(1);
1362 y -= style.getLineEndLength(3);
1368 public void getPath2D(Path2D path) {
1372 if(isSimpleConnection && transientLines.isEmpty()) {
1373 if(terminals.size() == 2) {
1374 RouteTerminal a = terminals.get(0);
1375 RouteTerminal b = terminals.get(1);
1376 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1377 path.moveTo(a.x, a.y);
1378 path.lineTo(b.x, b.y);
1385 THashMap<RoutePoint, RouteLine> begins =
1386 new THashMap<RoutePoint, RouteLine>();
1387 for(RouteLine line : lines) {
1390 for(RouteLine line : transientLines) {
1393 for(RouteTerminal terminal : terminals)
1394 if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1395 begins.remove(terminal.line.getBegin());
1396 drawContinuousPath(path, begins, terminal, terminal.line);
1400 for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1401 RouteLine curLine = begins.remove(begin);
1402 drawContinuousPath(path, begins, begin, curLine);
1406 private void drawContinuousPath(Path2D path, THashMap<RoutePoint, RouteLine> begins,
1407 RoutePoint cur, RouteLine curLine) {
1410 addPathBegin(path, cur, curLine);
1413 if(cur != curLine.getEnd())
1414 cur = curLine.getEnd();
1416 cur = curLine.getBegin();
1417 if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1418 addPathEnd(path, cur, curLine);
1421 if(cur instanceof RouteLink) {
1422 if(!curLine.isDegenerated() ||
1423 path.getCurrentPoint().getX() != cur.x ||
1424 path.getCurrentPoint().getY() != cur.y)
1425 path.lineTo(cur.x, cur.y);
1426 RouteLink link = (RouteLink)cur;
1427 if(link.a != curLine)
1435 private static void add(THashMap<RoutePoint, RouteLine> begins,
1437 if(line.points.size() > 1) {
1439 RoutePoint p = line.getBegin();
1440 if(begins.remove(p) == null)
1441 begins.put(p, line);
1444 RoutePoint p = line.getEnd();
1445 if(begins.remove(p) == null)
1446 begins.put(p, line);
1451 public Collection<Segment> getSegments() {
1454 ArrayList<Segment> segments = new ArrayList<Segment>();
1455 for(RouteLine routeLine : lines)
1456 routeLine.collectSegments(segments);
1457 for(RouteLine routeLine : transientLines)
1458 routeLine.collectSegments(segments);
1462 public Path2D getPath2D() {
1463 Path2D result = new Path2D.Double();
1468 public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1469 THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1470 THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1471 THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1472 THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1473 THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1474 THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1476 if(splitLine.isTransient()) {
1477 RouteTerminal terminal = splitLine.terminal;
1479 if(splitLine.beginsWithTerminal()) {
1480 lines2.addAll(getLines());
1481 terminals2.addAll(getTerminals());
1482 terminals1.add(terminal);
1483 terminals2.remove(terminal);
1484 interfaceNodes1.add(terminal);
1485 if(isSimpleConnection())
1486 interfaceNodes2.addAll(terminals2);
1488 interfaceNodes2.add(terminal.line);
1491 lines1.addAll(getLines());
1492 terminals1.addAll(getTerminals());
1493 terminals2.add(terminal);
1494 terminals1.remove(terminal);
1495 interfaceNodes2.add(terminal);
1496 if(isSimpleConnection())
1497 interfaceNodes1.addAll(terminals1);
1499 interfaceNodes1.add(terminal.line);
1503 for(RoutePoint rp : splitLine.getPoints()) {
1504 double p = splitLine.isHorizontal ? rp.x : rp.y;
1505 if(rp instanceof RouteLink) {
1506 RouteLink link = (RouteLink)rp;
1507 RouteLine otherLine = link.getA() != splitLine ? link.getA()
1509 if(otherLine.isTransient()) {
1511 interfaceNodes1.add(otherLine.terminal);
1512 terminals1.add(otherLine.terminal);
1515 interfaceNodes2.add(otherLine.terminal);
1516 terminals2.add(otherLine.terminal);
1522 interfaceNodes1.add(otherLine);
1523 traverseGraph(link, otherLine, lines1);
1526 interfaceNodes2.add(otherLine);
1527 traverseGraph(link, otherLine, lines2);
1532 for(RouteTerminal terminal : getTerminals())
1533 if(lines1.contains(terminal.line))
1534 terminals1.add(terminal);
1535 else if(lines2.contains(terminal.line))
1536 terminals2.add(terminal);
1539 return new SplittedRouteGraph(splitLine,
1540 interfaceNodes1, lines1, terminals1,
1541 interfaceNodes2, lines2, terminals2);
1544 private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1545 THashSet<RouteLine> lines) {
1546 if(lines.add(line)) {
1547 for(RoutePoint rp : line.getPoints()) {
1548 if(rp != previousPoint && rp instanceof RouteLink) {
1549 RouteLink link = (RouteLink)rp;
1550 RouteLine otherLine = line != link.getA()
1551 ? link.getA() : link.getB();
1552 if(otherLine.isTransient())
1554 traverseGraph(rp, otherLine, lines);
1560 public void reclaimTransientMemory() {
1561 removeTransientRouteLines();