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;
49 * Adds a route line to the graph.
50 * @param isHorizontal true, if the line is horizontal
51 * @param position y coordinate of the line if horizontal, x coordinate if vertical
52 * @return The new line.
54 public RouteLine addLine(boolean isHorizontal, double position) {
55 RouteLine line = new RouteLine(isHorizontal, position);
61 * Adds a route terminal to the graph.
62 * @param x The location of the terminal.
64 * @param minX The avoidance area of the terminal.
68 * @param allowedDirections Allowed directions.
69 * First four bits tell with which directions
70 * a connection can leave the terminal. The
71 * Fifth bit indicates whether direct lines
72 * can be drawn to the terminal. Directions are
79 * @param style Tells what kind of line end is drawn
81 * @return The new terminal.
83 public RouteTerminal addTerminal(double x, double y,
84 double minX, double minY,
85 double maxX, double maxY,
86 int allowedDirections,
87 ILineEndStyle style) {
88 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null);
91 public RouteTerminal addTerminal(double x, double y,
92 double minX, double minY,
93 double maxX, double maxY,
94 int allowedDirections,
95 ILineEndStyle style, ILineEndStyle dynamicStyle) {
97 if(allowedDirections > 0x1f)
98 throw new IllegalArgumentException("Illegal allowedDirection flags.");
99 if(minX > x || x > maxX || minY > y || y > maxY)
100 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
103 style = PlainLineEndStyle.INSTANCE;
104 RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
105 maxX, maxY, allowedDirections, false, style);
106 terminal.setDynamicStyle(dynamicStyle);
107 terminals.add(terminal);
111 public RouteTerminal addBigTerminal(
112 double minX, double minY,
113 double maxX, double maxY,
114 ILineEndStyle style) {
115 return addBigTerminal(minX, minY, maxX, maxY, style, null);
117 public RouteTerminal addBigTerminal(
118 double minX, double minY,
119 double maxX, double maxY,
120 ILineEndStyle style, ILineEndStyle dynamicStyle) {
122 style = PlainLineEndStyle.INSTANCE;
123 RouteTerminal terminal = new RouteTerminal(
124 0.5*(minX+maxX), 0.5*(minY+maxY),
128 terminal.setDynamicStyle(dynamicStyle);
130 terminals.add(terminal);
135 * Adds a route terminal to the graph. The avoidance
136 * area is given as a rectangle.
137 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
139 public RouteTerminal addTerminal(double x, double y,
141 int allowedDirections,
142 ILineEndStyle style) {
143 return addTerminal(x, y,
144 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
145 allowedDirections, style);
149 * Adds a copy of the given terminal to the graph.
151 public RouteTerminal addTerminal(RouteTerminal terminal) {
152 RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
153 terminal.getMinX(), terminal.getMinY(),
154 terminal.getMaxX(), terminal.getMaxY(),
155 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle());
156 newTerminal.setData(terminal.getData());
161 * Adds a route terminal to the graph. A default line end style is used.
162 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
164 public RouteTerminal addTerminal(double x, double y,
165 double minX, double minY,
166 double maxX, double maxY,
167 int allowedDirections) {
168 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
169 PlainLineEndStyle.INSTANCE);
175 public void link(RouteNode node1, RouteNode node2) {
176 if(node1 instanceof RouteLine) {
177 if(node2 instanceof RouteLine) {
178 link((RouteLine)node1, (RouteLine)node2);
181 link((RouteLine)node1, (RouteTerminal)node2);
185 if(node2 instanceof RouteLine) {
186 link((RouteTerminal)node1, (RouteLine)node2);
189 link((RouteTerminal)node1, (RouteTerminal)node2);
197 public void link(RouteNode ... nodes) {
198 for(int i=1;i<nodes.length;++i)
199 link(nodes[i-1], nodes[i]);
205 public void link(RouteLine node1, RouteLine node2) {
206 new RouteLink(node1, node2);
211 * Links a terminal and a line.
213 public void link(RouteTerminal node1, RouteLine node2) {
216 throw new NullPointerException();
217 if(node1.line != null)
218 throw new IllegalStateException("Terminal is already connected.");
225 * Links a line and a terminal.
227 public void link(RouteLine node1, RouteTerminal node2) {
230 throw new NullPointerException();
231 if(node2.line != null)
232 throw new IllegalStateException("Terminal is already connected.");
239 * Links two terminals.
241 public void link(RouteTerminal node1, RouteTerminal node2) {
244 throw new NullPointerException();
246 throw new NullPointerException();
248 isSimpleConnection = true;
252 void removeTransientRouteLines() {
253 for(RouteLine line : transientLines)
255 transientLines.clear();
259 * Rotates given terminal clockwise by given amount
260 * (also negative numbers are allowed).
262 public void rotate(RouteTerminal terminal, int amount) {
263 terminal.rotate(amount);
268 * Moves the given route line so that its position correspond
269 * to given x or y depending on the orientation of the line.
271 public void setLocation(RouteLine line, double x, double y) {
272 makePersistent(line);
273 line.setLocation(x, y);
278 * Moves the terminal to given location.
280 public void setLocation(RouteTerminal terminal, double x, double y) {
281 terminal.setLocation(x, y);
286 * Updates transient route lines, route link positions
287 * and sorts route points of each route line.
289 public void update() {
291 removeTransientRouteLines();
295 for(RouteLine line : lines)
297 for(RouteTerminal terminal : terminals)
298 if(terminal.hasDirectConnection() && terminal.line != null)
299 terminal.line.hidden = true;
302 if(isSimpleConnection) {
303 RouteTerminal a = terminals.get(0);
304 RouteTerminal b = terminals.get(1);
305 if(a.hasDirectConnection() || b.hasDirectConnection())
307 caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
308 //System.out.println("caseId = " + caseId);
310 case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
311 case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
312 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
313 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
317 transientLines.add(line);
320 case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
321 RouteLine line1 = new RouteLine(true, a.y);
322 RouteLine line2 = new RouteLine(false, b.x);
323 new RouteLink(line1, line2);
328 transientLines.add(line1);
329 transientLines.add(line2);
332 case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
333 RouteLine line1 = new RouteLine(false, a.x);
334 RouteLine line2 = new RouteLine(true, b.y);
335 new RouteLink(line1, line2);
340 transientLines.add(line1);
341 transientLines.add(line2);
344 case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
345 case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
347 SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
348 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
350 terminals.get(0).line = line;
351 terminals.get(1).line = line;
352 transientLines.add(line);
353 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
359 caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
360 routeFromTerminals(false);
363 // Find positions of route points
364 for(RouteLine line : lines)
365 line.setPointPositions();
366 for(RouteLine line : transientLines)
367 line.setPointPositions();
369 // Sort route points in route lines
370 for(RouteLine line : lines) {
373 for(RouteLine line : transientLines) {
378 static class Interval {
379 public final double min;
380 public final double max;
381 public Interval(double min, double max) {
387 class IntervalCache {
388 THashMap<RouteLine, Interval> cache =
389 new THashMap<RouteLine, Interval>();
390 public Interval get(RouteLine line) {
391 Interval result = cache.get(line);
395 result = create(line);
396 cache.put(line, result);
400 private Interval create(RouteLine line) {
401 double min = Double.POSITIVE_INFINITY;
402 double max = Double.NEGATIVE_INFINITY;
404 for(RoutePoint point : line.points) {
406 if(point instanceof RouteLink) {
407 RouteLink link = (RouteLink)point;
409 temp = link.b.position;
411 temp = link.a.position;
414 RouteTerminal terminal = (RouteTerminal)point;
415 if(line.isHorizontal)
425 for(RouteTerminal terminal : terminals) {
426 if(terminal.line == line) {
427 double temp = terminal.approximatePositionToLine();
435 return new Interval(min, max);
439 private void routeFromTerminals(boolean boundingBoxesIntersect) {
440 IntervalCache cache = new IntervalCache();
441 for(RouteTerminal terminal : terminals)
442 if(terminal.line != null) {
443 if(!terminal.hasDirectConnection())
444 terminal.route(transientLines, cache, boundingBoxesIntersect);
449 * Returns a RouteLine near the given point (x,y) (within tolerance).
451 public RouteLine pickLine(double x, double y, double tolerance, int mask) {
454 if(isSimpleConnection && transientLines.isEmpty()) {
455 if(terminals.size() == 2) {
456 if((mask & PICK_TRANSIENT_LINES) == 0)
458 RouteTerminal a = terminals.get(0);
459 RouteTerminal b = terminals.get(1);
460 if(a.hasDirectConnection() || b.hasDirectConnection()) {
461 if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
462 RouteLine dummy = new RouteLine(false, y);
463 return dummy; // There are no lines to return
470 if((mask & PICK_PERSISTENT_LINES) != 0)
471 for(RouteLine line : lines)
472 if(line.isNear(x, y, tolerance))
474 if((mask & PICK_TRANSIENT_LINES) != 0)
475 for(RouteLine line : transientLines)
476 if(line.isNear(x, y, tolerance))
478 if((mask & PICK_DIRECT_LINES) != 0) {
479 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
481 return terminal.line;
486 public RouteLine pickLine(double x, double y, double tolerance) {
487 return pickLine(x, y, tolerance, PICK_LINES);
490 private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
491 double toleranceSq = tolerance * tolerance;
492 for(RouteTerminal terminal : terminals)
493 if((terminal.getAllowedDirections()&0x10) != 0) {
495 RouteLine line = terminal.getLine();
498 RoutePoint b = line.getBegin();
499 double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
500 if(distSq <= toleranceSq) {
501 //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
504 } catch(NullPointerException e) {
505 //if terminal does not have a line
507 } catch(IndexOutOfBoundsException e) {
508 // if line does not contain points
515 public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
516 if(isSimpleConnection)
520 RouteLine line = pickLine(x, y, tolerance);
523 RouteLink link = null;
524 RoutePoint begin = line.getBegin();
525 RoutePoint end = line.getEnd();
526 if(line.isHorizontal) {
527 double mx = 0.5*(begin.getX() + end.getX());
529 if(begin instanceof RouteLink)
530 link = (RouteLink)begin;
533 if(end instanceof RouteLink)
534 link = (RouteLink)line.getEnd();
538 double my = 0.5*(begin.getY() + end.getY());
540 if(begin instanceof RouteLink)
541 link = (RouteLink)begin;
544 if(end instanceof RouteLink)
545 link = (RouteLink)end;
550 if(link.getOther(line).isTransient())
552 return new RouteLineHalf(line, link);
555 public Collection<RouteLineHalf> getLineHalves() {
556 return getLineHalves(new ArrayList<RouteLineHalf>());
559 public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
560 for(RouteLine line : getAllLines()) {
562 RoutePoint p = line.getBegin();
563 if(p instanceof RouteLink) {
564 RouteLink link = (RouteLink)p;
565 if(!link.getOther(line).isTransient())
566 result.add(new RouteLineHalf(line, link));
570 RoutePoint p = line.getEnd();
571 if(p instanceof RouteLink) {
572 RouteLink link = (RouteLink)p;
573 if(!link.getOther(line).isTransient())
574 result.add(new RouteLineHalf(line, link));
582 * Returns a RoutePoint near the given point (x,y) (within tolerance).
584 public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
587 if((mask&PICK_TERMINALS) != 0)
588 for(RouteTerminal terminal : terminals)
589 if(terminal.isNear(x, y))
591 if((mask&PICK_INTERIOR_POINTS) != 0) {
592 for(RouteLine line : lines) {
593 for(RoutePoint point : line.points)
594 if(point.isNear(x, y, tolerance))
597 for(RouteLine line : transientLines) {
598 for(RoutePoint point : line.points)
599 if(point.isNear(x, y, tolerance))
606 public RoutePoint pickPoint(double x, double y, double tolerance) {
607 return pickPoint(x, y, tolerance, PICK_POINTS);
610 public static final int PICK_INTERIOR_POINTS = 1;
611 public static final int PICK_TERMINALS = 2;
612 public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
614 public static final int PICK_PERSISTENT_LINES = 4;
615 public static final int PICK_TRANSIENT_LINES = 8;
616 public static final int PICK_DIRECT_LINES = 16;
617 public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
619 public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
622 * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
624 public Object pick(double x, double y, double tolerance, int mask) {
625 if((mask & PICK_POINTS) != 0) {
626 Object point = pickPoint(x, y, tolerance, mask);
630 /*if((mask & PICK_DIRECT_LINES) != 0) {
631 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
633 return terminal.line.getBegin();
635 if((mask & PICK_LINES) != 0)
636 return pickLine(x, y, tolerance, mask);
641 public Object pick(double x, double y, double tolerance) {
642 return pick(x, y, tolerance, PICK_ALL);
646 * Returns RoutePoint or RouteLine exactly under the given point (x,y).
648 public Object pick(double x, double y) {
649 return pick(x, y, 0.0);
653 * Prints the contents of the route graph to stdout.
655 public void print() {
660 * Prints the contents of the route graph to given print stream.
662 public void print(PrintStream out) {
665 if(isSimpleConnection)
666 out.println("=== SIMPLE CONNECTION ===");
668 out.println("=== COMPLEX CONNECTION ===");
669 for(RouteLine line : lines) {
673 for(RouteLine line : transientLines) {
677 for(RouteTerminal terminal : terminals) {
683 public void makePersistent(RouteLine line) {
684 prepareForModification();
685 if(isSimpleConnection || line.isTransient()) {
686 if(isSimpleConnection) {
687 isSimpleConnection = false;
688 for(RouteTerminal terminal : terminals)
689 terminal.line = line;
690 transientLines.remove(line);
692 Iterator<RoutePoint> it = line.points.iterator();
693 while(it.hasNext()) {
694 RoutePoint point = it.next();
695 if(point instanceof RouteTerminal)
698 line.terminal = null;
699 line.nextTransient = null;
702 line.terminal.line = line;
704 transientLines.remove(line);
706 Iterator<RoutePoint> it = line.points.iterator();
707 while(it.hasNext()) {
708 RoutePoint point = it.next();
709 if(point instanceof RouteTerminal)
712 line.terminal = null;
713 RouteLine temp = line.nextTransient;
714 line.nextTransient = null;
716 } while(line != null);
722 void prepareForModification() {
724 RouteLine line = transientLines.remove(0);
725 line.terminal = null;
727 for(RouteTerminal terminal : terminals)
728 terminal.line = line;
729 isSimpleConnection = false;
734 public double[] getLineLengths(RouteTerminal terminal) {
737 if(lines.size()==0 && transientLines.size()==1)
738 return new double[] { transientLines.get(0).getLength() };
740 RouteLine line = null;
742 for(RouteLine l : transientLines)
743 if(l.isTransient()) {
744 for(RoutePoint p : l.points)
745 if(!(p instanceof RouteLink)) {
750 TDoubleArrayList result = new TDoubleArrayList();
751 THashSet<RouteLine> set = new THashSet<RouteLine>();
755 result.add(line.getLength());
756 for(RoutePoint point : line.points)
757 if(point instanceof RouteLink) {
758 RouteLink link = (RouteLink)point;
759 if(set.add(link.a)) {
763 if(set.add(link.b)) {
770 return result.toArray();
773 public void split(RouteLine rl1, double splitPosition) {
776 boolean isHorizontal = rl1.isHorizontal();
777 if(isSimpleConnection) {
778 isSimpleConnection = false;
780 RouteLine sp = addLine(!isHorizontal, splitPosition);
781 for(RouteTerminal terminal : terminals)
786 else if(caseId < 4) {
787 RouteLine sp = addLine(!isHorizontal, splitPosition);
788 RouteLine l = addLine(isHorizontal, rl1.position);
790 rl1.terminal.line = sp;
791 for(RouteTerminal terminal : terminals)
792 if(terminal != rl1.terminal)
798 prepareForModification();
801 RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
802 RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
804 ArrayList<RoutePoint> points = rl1.points;
809 int maxPos = points.size();
810 while(minPos != maxPos) {
811 int c = (minPos + maxPos)/2;
813 ? points.get(c).getX() > splitPosition
814 : points.get(c).getY() > splitPosition)
822 for(int i=points.size()-1;i>=splitPos;--i) {
823 RoutePoint point = points.remove(i);
824 if(point instanceof RouteLink) {
825 RouteLink link = (RouteLink)point;
826 link.replace(rl1, rl2);
830 if(rl1.isTransient()) {
831 boolean p1 = rl1.isConnectedToPeristentLine();
832 boolean p2 = rl2.isConnectedToPeristentLine();
834 RouteTerminal terminal = rl1.terminal;
837 transientLines.add(rl2);
843 transientLines.add(rl2);
845 for(RouteTerminal t : terminals)
853 new RouteLink(rl1, sp);
854 new RouteLink(sp, rl2);
859 public boolean merge(RouteLine line) {
862 for(RoutePoint point : line.points) {
863 if(point instanceof RouteLink) {
864 RouteLink link = (RouteLink)point;
865 RouteLine other = link.getOther(line);
866 if(!other.isTransient()) {
867 sum += other.position;
872 return merge(line, sum / count);
876 * Removes given route line and collapses all its neighbor
877 * route lines into one line with given position.
879 public boolean merge(RouteLine line, double position) {
882 if(isSimpleConnection || line.isTransient())
885 if(lines.size() == 1) {
886 if(terminals.size() != 2)
889 isSimpleConnection = true;
890 for(RouteTerminal terminal : terminals)
891 terminal.line = null;
896 ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
897 for(RoutePoint point : line.points) {
898 /* Because line.terminal == null, there should be
901 * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
903 if (point instanceof RouteLink) {
904 RouteLine l = ((RouteLink)point).getOther(line);
905 l.points.remove(point);
913 RouteLine merged = nLines.remove(nLines.size()-1);
914 merged.position = position;
915 for(RouteLine l : nLines) {
916 for(RoutePoint point : l.points) {
917 /* Because l.terminal == null, there should be
920 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
922 if (point instanceof RouteLink) {
923 RouteLink link = (RouteLink)point;
924 link.replace(l, merged);
928 THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
929 removedLines.addAll(nLines);
930 lines.removeAll(removedLines);
931 removedLines.add(line);
933 for(RouteTerminal terminal : terminals)
934 if(removedLines.contains(terminal.line))
935 terminal.line = merged;
940 public void deleteCorner(RouteLink link) {
943 RouteLine a = link.getA();
944 RouteLine b = link.getB();
945 if(a.isTransient() || b.isTransient()
946 || a.points.size() != 2 || b.points.size() != 2)
948 RouteLine na=null, nb=null;
949 for(RoutePoint p : a.points) {
950 RouteLink l = (RouteLink)p;
951 if(l.a == a && l.b != b) {
955 else if(l.b == a && l.a != b) {
960 for(RoutePoint p : b.points) {
961 RouteLink l = (RouteLink)p;
962 if(l.a == b && l.b != a) {
966 else if(l.b == b && l.a != a) {
971 if(na == null || nb == null) {
972 System.err.println("Internal error in router.");
980 if(na.terminal != null)
981 na.terminal.line = nb;
982 if(nb.terminal != null)
983 nb.terminal.line = na;
987 public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
988 Object target = pick(x, y, tolerance);
989 if(target instanceof RouteLine) {
990 RouteLine line = (RouteLine)target;
991 RouteTerminal involvedTerminal =
992 line.isTransient() ? line.terminal : null;
993 makePersistent(line);
994 terminal.line = null; // TODO this is a workaround
996 int lineDir = line.isHorizontal
997 ? (line.position < terminal.y ? 3 : 1)
998 : (line.position < terminal.x ? 2 : 0)
1001 if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1003 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1004 RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1005 l2 = addLine(false, x);
1006 link(terminal, l1, l2, line);
1009 l2 = addLine(false, x);
1010 link(terminal, l2, line);
1012 if(involvedTerminal != null)
1013 involvedTerminal.line = l2;
1015 else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1017 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1018 RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1019 l2 = addLine(true, y);
1020 link(terminal, l1, l2, line);
1023 l2 = addLine(true, y);
1024 link(terminal, l2, line);
1026 if(involvedTerminal != null)
1027 involvedTerminal.line = l2;
1030 link(terminal, line);
1039 public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1040 Object target = pick(x, y, tolerance);
1041 if(target instanceof RouteLine) {
1042 RouteLine line = (RouteLine)target;
1043 RouteTerminal involvedTerminal =
1044 line.isTransient() ? line.terminal : null;
1045 makePersistent(line);
1046 if(line.isHorizontal == sLine.isHorizontal) {
1047 RouteLine l = addLine(!sLine.isHorizontal,
1048 sLine.isHorizontal ? x : y);
1049 link(sLine, l, line);
1050 if(involvedTerminal != null)
1051 involvedTerminal.line = l;
1055 if(involvedTerminal != null)
1056 involvedTerminal.line = sLine;
1066 * Makes a deep copy of the route graph and stores
1067 * the correspondences between original and copied
1068 * objects into the given map.
1070 public RouteGraph copy(THashMap<Object, Object> map) {
1071 RouteGraph copy = new RouteGraph();
1072 copy.isSimpleConnection = isSimpleConnection;
1073 copy.caseId = caseId;
1074 copy.needsUpdate = needsUpdate;
1075 for(RouteLine line : lines)
1076 copy.lines.add(line.copy(map));
1077 for(RouteLine line : transientLines)
1078 copy.transientLines.add(line.copy(map));
1079 for(RouteTerminal terminal : terminals)
1080 copy.terminals.add(terminal.copy(map));
1085 * Makes a deep copy of the route graph.
1087 public RouteGraph copy() {
1088 THashMap<Object, Object> map = new THashMap<Object, Object>();
1093 * Removes route lines that are conneted to at most
1094 * one other route line or terminal.
1096 public void removeExtraConnections() {
1097 TObjectIntHashMap<RouteLine> counts =
1098 new TObjectIntHashMap<RouteLine>();
1099 removeTransientRouteLines();
1100 for(RouteLine line : lines) {
1102 for(RoutePoint point : line.points)
1103 if(point instanceof RouteLink)
1105 counts.put(line, count);
1107 for(RouteTerminal terminal : terminals)
1108 counts.adjustOrPutValue(terminal.line, 1, 1);
1112 Iterator<RouteLine> it = lines.iterator();
1113 while(it.hasNext()) {
1114 RouteLine line = it.next();
1115 if(counts.get(line) <= 1) {
1116 for(RoutePoint point : line.points)
1117 if(point instanceof RouteLink)
1118 counts.adjustValue(((RouteLink)point).getOther(line), -1);
1129 * Removes a terminal and all route lines that become degenerated by the removal.
1131 public void remove(RouteTerminal terminal) {
1132 terminals.remove(terminal);
1133 removeExtraConnections();
1136 public void disconnect(RouteTerminal terminal) {
1137 terminal.line = null;
1138 removeExtraConnections();
1141 public void remove(RouteLink link) {
1142 link.a.points.remove(link);
1143 link.b.points.remove(link);
1146 public void toggleDirectLines(RouteTerminal terminal) {
1147 terminal.toggleDirectLines();
1152 * Returns all persistent route lines of the route graph.
1154 public Collection<RouteLine> getLines() {
1157 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1158 return Collections.unmodifiableList(lines);
1164 * Returns all transient route lines of the route graph.
1166 public Collection<RouteLine> getTransientLines() {
1169 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1170 return Collections.unmodifiableList(transientLines);
1172 return transientLines;
1176 * Returns all terminals of the route graph.
1178 public Collection<RouteTerminal> getTerminals() {
1179 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1180 return Collections.unmodifiableList(terminals);
1186 * Returns all route lines, both persistent and transient,
1187 * of the route graph.
1189 public Collection<RouteLine> getAllLines() {
1192 ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1193 allLines.addAll(lines);
1194 allLines.addAll(transientLines);
1199 * Returns all route lines, both persistent and transient, of the route
1200 * graph, added to the specified collection. Avoids allocation of new
1201 * {@link ArrayList} compared to {@link #getAllLines()}.
1203 public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1205 throw new NullPointerException("null result collection");
1208 result.addAll(lines);
1209 result.addAll(transientLines);
1214 * Returns true, if the route graph is connected and contains no cycles.
1216 public boolean isTree() {
1217 if(isSimpleConnection)
1219 for(RouteTerminal terminal : terminals)
1220 if(terminal.line == null)
1222 THashSet<RouteLine> visited = new THashSet<RouteLine>();
1223 ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1225 visited.add(lines.get(0));
1226 stack.add(lines.get(0));
1227 while(!stack.isEmpty()) {
1228 RouteLine cur = stack.remove(stack.size()-1);
1229 for(RouteLine n : cur.getPersistentNeighbors()) {
1235 return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1239 * Returns if the connection is simple. A connection is simple, if it has just
1240 * two terminals connected together directly without (persistent) route lines.
1242 public boolean isSimpleConnection() {
1243 return isSimpleConnection;
1246 public void replaceBy(RouteGraph rg) {
1247 this.lines = rg.lines;
1248 this.terminals = rg.terminals;
1249 this.transientLines = rg.transientLines;
1250 this.caseId = rg.caseId;
1251 this.isSimpleConnection = rg.isSimpleConnection;
1252 this.needsUpdate = rg.needsUpdate;
1256 private void reset() {
1257 lines = new ArrayList<RouteLine>();
1258 terminals = new ArrayList<RouteTerminal>();
1259 transientLines = new ArrayList<RouteLine>();
1261 isSimpleConnection = false;
1262 needsUpdate = false;
1265 public Rectangle2D getBounds() {
1266 Rectangle2D bounds = new Rectangle2D.Double();
1271 public void getBounds(Rectangle2D bounds) {
1274 double minX = Double.POSITIVE_INFINITY;
1275 double maxX = Double.NEGATIVE_INFINITY;
1276 double minY = Double.POSITIVE_INFINITY;
1277 double maxY = Double.NEGATIVE_INFINITY;
1278 for(RouteLine line : lines) {
1279 double position = line.position;
1280 if(line.isHorizontal) {
1281 minY = Math.min(minY, position);
1282 maxY = Math.max(maxY, position);
1285 minX = Math.min(minX, position);
1286 maxX = Math.max(maxX, position);
1289 for(RouteLine line : transientLines) {
1290 double position = line.position;
1291 if(line.isHorizontal) {
1292 minY = Math.min(minY, position);
1293 maxY = Math.max(maxY, position);
1296 minX = Math.min(minX, position);
1297 maxX = Math.max(maxX, position);
1300 for(RouteTerminal terminal : terminals) {
1301 double x = terminal.x;
1302 double y = terminal.y;
1303 minX = Math.min(minX, x);
1304 maxX = Math.max(maxX, x);
1305 minY = Math.min(minY, y);
1306 maxY = Math.max(maxY, y);
1308 bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1311 private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1312 double x = cur.x, y = cur.y;
1313 if(cur instanceof RouteTerminal) {
1314 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1315 if(line.isHorizontal()) {
1316 if(cur == line.getBegin())
1317 x += style.getLineEndLength(0);
1319 x -= style.getLineEndLength(2);
1322 if(cur == line.getBegin())
1323 y += style.getLineEndLength(1);
1325 y -= style.getLineEndLength(3);
1331 private static void addPathEnd(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 public void getPath2D(Path2D path) {
1355 if(isSimpleConnection && transientLines.isEmpty()) {
1356 if(terminals.size() == 2) {
1357 RouteTerminal a = terminals.get(0);
1358 RouteTerminal b = terminals.get(1);
1359 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1360 path.moveTo(a.x, a.y);
1361 path.lineTo(b.x, b.y);
1368 THashMap<RoutePoint, RouteLine> begins =
1369 new THashMap<RoutePoint, RouteLine>();
1370 for(RouteLine line : lines) {
1373 for(RouteLine line : transientLines) {
1376 for(RouteTerminal terminal : terminals)
1377 if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1378 begins.remove(terminal.line.getBegin());
1379 drawContinuousPath(path, begins, terminal, terminal.line);
1383 for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1384 RouteLine curLine = begins.remove(begin);
1385 drawContinuousPath(path, begins, begin, curLine);
1389 private void drawContinuousPath(Path2D path, THashMap<RoutePoint, RouteLine> begins,
1390 RoutePoint cur, RouteLine curLine) {
1393 addPathBegin(path, cur, curLine);
1396 if(cur != curLine.getEnd())
1397 cur = curLine.getEnd();
1399 cur = curLine.getBegin();
1400 if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1401 addPathEnd(path, cur, curLine);
1404 if(cur instanceof RouteLink) {
1405 if(!curLine.isDegenerated() ||
1406 path.getCurrentPoint().getX() != cur.x ||
1407 path.getCurrentPoint().getY() != cur.y)
1408 path.lineTo(cur.x, cur.y);
1409 RouteLink link = (RouteLink)cur;
1410 if(link.a != curLine)
1418 private static void add(THashMap<RoutePoint, RouteLine> begins,
1420 if(line.points.size() > 1) {
1422 RoutePoint p = line.getBegin();
1423 if(begins.remove(p) == null)
1424 begins.put(p, line);
1427 RoutePoint p = line.getEnd();
1428 if(begins.remove(p) == null)
1429 begins.put(p, line);
1434 public Collection<Segment> getSegments() {
1437 ArrayList<Segment> segments = new ArrayList<Segment>();
1438 for(RouteLine routeLine : lines)
1439 routeLine.collectSegments(segments);
1440 for(RouteLine routeLine : transientLines)
1441 routeLine.collectSegments(segments);
1445 public Path2D getPath2D() {
1446 Path2D result = new Path2D.Double();
1451 public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1452 THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1453 THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1454 THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1455 THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1456 THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1457 THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1459 if(splitLine.isTransient()) {
1460 RouteTerminal terminal = splitLine.terminal;
1462 if(splitLine.beginsWithTerminal()) {
1463 lines2.addAll(getLines());
1464 terminals2.addAll(getTerminals());
1465 terminals1.add(terminal);
1466 terminals2.remove(terminal);
1467 interfaceNodes1.add(terminal);
1468 if(isSimpleConnection())
1469 interfaceNodes2.addAll(terminals2);
1471 interfaceNodes2.add(terminal.line);
1474 lines1.addAll(getLines());
1475 terminals1.addAll(getTerminals());
1476 terminals2.add(terminal);
1477 terminals1.remove(terminal);
1478 interfaceNodes2.add(terminal);
1479 if(isSimpleConnection())
1480 interfaceNodes1.addAll(terminals1);
1482 interfaceNodes1.add(terminal.line);
1486 for(RoutePoint rp : splitLine.getPoints()) {
1487 double p = splitLine.isHorizontal ? rp.x : rp.y;
1488 if(rp instanceof RouteLink) {
1489 RouteLink link = (RouteLink)rp;
1490 RouteLine otherLine = link.getA() != splitLine ? link.getA()
1492 if(otherLine.isTransient()) {
1494 interfaceNodes1.add(otherLine.terminal);
1495 terminals1.add(otherLine.terminal);
1498 interfaceNodes2.add(otherLine.terminal);
1499 terminals2.add(otherLine.terminal);
1505 interfaceNodes1.add(otherLine);
1506 traverseGraph(link, otherLine, lines1);
1509 interfaceNodes2.add(otherLine);
1510 traverseGraph(link, otherLine, lines2);
1515 for(RouteTerminal terminal : getTerminals())
1516 if(lines1.contains(terminal.line))
1517 terminals1.add(terminal);
1518 else if(lines2.contains(terminal.line))
1519 terminals2.add(terminal);
1522 return new SplittedRouteGraph(splitLine,
1523 interfaceNodes1, lines1, terminals1,
1524 interfaceNodes2, lines2, terminals2);
1527 private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1528 THashSet<RouteLine> lines) {
1529 if(lines.add(line)) {
1530 for(RoutePoint rp : line.getPoints()) {
1531 if(rp != previousPoint && rp instanceof RouteLink) {
1532 RouteLink link = (RouteLink)rp;
1533 RouteLine otherLine = line != link.getA()
1534 ? link.getA() : link.getB();
1535 if(otherLine.isTransient())
1537 traverseGraph(rp, otherLine, lines);
1543 public void reclaimTransientMemory() {
1544 removeTransientRouteLines();