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