Don't create degenerated transient RouteLines to RouteGraph
[simantics/platform.git] / bundles / org.simantics.diagram.connection / src / org / simantics / diagram / connection / RouteGraph.java
1 /*******************************************************************************
2  * Copyright (c) 2011 Association for Decentralized Information Management in
3  * Industry THTH ry.
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
8  *
9  * Contributors:
10  *     VTT Technical Research Centre of Finland - initial API and implementation
11  *******************************************************************************/
12 package org.simantics.diagram.connection;
13
14 import java.awt.geom.Line2D;
15 import java.awt.geom.Path2D;
16 import java.awt.geom.Point2D;
17 import java.awt.geom.Rectangle2D;
18 import java.io.PrintStream;
19 import java.io.Serializable;
20 import java.util.ArrayList;
21 import java.util.Collection;
22 import java.util.Collections;
23 import java.util.Comparator;
24 import java.util.HashMap;
25 import java.util.Iterator;
26 import java.util.Map;
27 import java.util.stream.Collectors;
28
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;
33
34 import gnu.trove.list.array.TDoubleArrayList;
35 import gnu.trove.map.hash.THashMap;
36 import gnu.trove.map.hash.TObjectIntHashMap;
37 import gnu.trove.set.hash.THashSet;
38
39 public class RouteGraph implements Serializable {
40
41     private static final long serialVersionUID = 2004022454972623908L;
42
43     public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
44     public static final boolean CHECK_PARAMERS = true;
45
46     protected ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
47     protected ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
48     protected ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
49     protected int caseId;
50     protected boolean isSimpleConnection;
51     protected boolean needsUpdate = false;
52
53     public void updateTerminals() {
54         boolean changed = false;
55         for(RouteTerminal terminal : terminals)
56             changed |= terminal.updateDynamicPosition();
57         if(changed) update();
58     }
59
60     /**
61      * Adds a route line to the graph.
62      * @param isHorizontal true, if the line is horizontal
63      * @param position y coordinate of the line if horizontal, x coordinate if vertical
64      * @return The new line.
65      */
66     public RouteLine addLine(boolean isHorizontal, double position) {
67         RouteLine line = new RouteLine(isHorizontal, position); 
68         lines.add(line);
69         return line;
70     }
71
72     /**
73      * Adds a route terminal to the graph.
74      * @param x The location of the terminal.
75      * @param y 
76      * @param minX The avoidance area of the terminal.
77      * @param minY
78      * @param maxX
79      * @param maxY
80      * @param allowedDirections Allowed directions. 
81      *        First four bits tell with which directions
82      *        a connection can leave the terminal. The
83      *        Fifth bit indicates whether direct lines
84      *        can be drawn to the terminal. Directions are
85      * <pre>
86      * 0 right (1,0)
87      * 1 down  (0,1)
88      * 2 left  (-1,0)
89      * 3 up    (0,-1)
90      * </pre>
91      * @param style Tells what kind of line end is drawn 
92      *        to the connection.
93      * @param position a provider for a dynamic position for the terminal or
94      *        <code>null</code> if terminal position is not dynamic
95      * @return The new terminal.
96      */
97     public RouteTerminal addTerminal(double x, double y, 
98             double minX, double minY,
99             double maxX, double maxY, 
100             int allowedDirections,
101             ILineEndStyle style, RouteTerminalPosition position) {
102         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
103     }
104
105     public RouteTerminal addTerminal(double x, double y, 
106             double minX, double minY,
107             double maxX, double maxY, 
108             int allowedDirections,
109             ILineEndStyle style) {
110         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
111     }
112
113     public RouteTerminal addTerminal(double x, double y, 
114             double minX, double minY,
115             double maxX, double maxY, 
116             int allowedDirections,
117             ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
118         if(CHECK_PARAMERS) {
119             if(allowedDirections > 0x1f)
120                 throw new IllegalArgumentException("Illegal allowedDirection flags.");
121             if(minX > x || x > maxX || minY > y || y > maxY)
122                 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
123         }
124         if(style == null)
125             style = PlainLineEndStyle.INSTANCE;
126         RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
127                 maxX, maxY, allowedDirections, false, style, position); 
128         terminal.setDynamicStyle(dynamicStyle);
129         terminals.add(terminal);
130         return terminal;
131     }
132     
133     public RouteTerminal addBigTerminal( 
134             double minX, double minY,
135             double maxX, double maxY,
136             ILineEndStyle style) {
137         return addBigTerminal(minX, minY, maxX, maxY, style, null);
138     }
139     public RouteTerminal addBigTerminal( 
140             double minX, double minY,
141             double maxX, double maxY,
142             ILineEndStyle style, ILineEndStyle dynamicStyle) {
143         if(style == null)
144             style = PlainLineEndStyle.INSTANCE;
145         RouteTerminal terminal = new RouteTerminal(
146                 0.5*(minX+maxX), 0.5*(minY+maxY),
147                 minX, minY,
148                 maxX, maxY, 
149                 0xf, true, style, null); 
150         terminal.setDynamicStyle(dynamicStyle);
151         
152         terminals.add(terminal);
153         return terminal;
154     }
155
156     /**
157      * Adds a route terminal to the graph. The avoidance
158      * area is given as a rectangle.
159      * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
160      */
161     public RouteTerminal addTerminal(double x, double y, 
162             Rectangle2D bounds, 
163             int allowedDirections,
164             ILineEndStyle style) {
165         return addTerminal(x, y, 
166                 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(), 
167                 allowedDirections, style, null);
168     }
169
170     /**
171      * Adds a copy of the given terminal to the graph.
172      */
173     public RouteTerminal addTerminal(RouteTerminal terminal) {
174         RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
175                 terminal.getMinX(), terminal.getMinY(),
176                 terminal.getMaxX(), terminal.getMaxY(),
177                 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
178         newTerminal.setData(terminal.getData());
179         return terminal;
180     }
181
182     /**
183      * Adds a route terminal to the graph. A default line end style is used.
184      * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
185      */
186     public RouteTerminal addTerminal(double x, double y, 
187             double minX, double minY,
188             double maxX, double maxY, 
189             int allowedDirections) {
190         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, 
191                 PlainLineEndStyle.INSTANCE, null);
192     }
193     
194     /**
195      * Links nodes.
196      */
197     public void link(RouteNode node1, RouteNode node2) {
198         if(node1 instanceof RouteLine) {
199             if(node2 instanceof RouteLine) {
200                 link((RouteLine)node1, (RouteLine)node2);
201             }
202             else {
203                 link((RouteLine)node1, (RouteTerminal)node2);
204             }
205         }
206         else {
207             if(node2 instanceof RouteLine) {
208                 link((RouteTerminal)node1, (RouteLine)node2);
209             }
210             else {
211                 link((RouteTerminal)node1, (RouteTerminal)node2);
212             }
213         }
214     }
215     
216     /**
217      * Links nodes.
218      */
219     public void link(RouteNode ... nodes) {
220         for(int i=1;i<nodes.length;++i)
221             link(nodes[i-1], nodes[i]);
222     }
223     
224     /**
225      * Links lines.
226      */
227     public void link(RouteLine node1, RouteLine node2) {
228         new RouteLink(node1, node2);
229         needsUpdate = true;
230     }
231     
232     /**
233      * Links a terminal and a line.
234      */
235     public void link(RouteTerminal node1, RouteLine node2) {
236         if(CHECK_PARAMERS) {
237             if(node2 == null)
238                 throw new NullPointerException();
239             if(node1.line != null)
240                 throw new IllegalStateException("Terminal is already connected.");
241         }
242         node1.line = node2;
243         needsUpdate = true;
244     }
245
246     /**
247      * Links a line and a terminal.
248      */
249     public void link(RouteLine node1, RouteTerminal node2) {
250         if(CHECK_PARAMERS) {
251             if(node1 == null)
252                 throw new NullPointerException();
253             if(node2.line != null)
254                 throw new IllegalStateException("Terminal is already connected.");
255         }
256         node2.line = node1;
257         needsUpdate = true;
258     }
259
260     /**
261      * Links two terminals.
262      */
263     public void link(RouteTerminal node1, RouteTerminal node2) {
264         if(CHECK_PARAMERS) {
265             if(node1 == null)
266                 throw new NullPointerException();
267             if(node2 == null)
268                 throw new NullPointerException();
269         }
270         isSimpleConnection = true;
271         needsUpdate = true;
272     }
273     
274     protected void removeTransientRouteLines() {
275         for(RouteLine line : transientLines)
276             line.remove();
277         transientLines.clear();
278     }
279     
280     protected void removeRouteTerminalsFromRouteLines() {
281         for(RouteLine line : lines) {
282             line.removeRouteTerminals();
283         }
284     }
285
286     /**
287      * Rotates given terminal clockwise by given amount
288      * (also negative numbers are allowed). 
289      */
290     public void rotate(RouteTerminal terminal, int amount) {
291         terminal.rotate(amount);
292         needsUpdate = true;
293     }
294     
295     /**
296      * Moves the given route line so that its position correspond
297      * to given x or y depending on the orientation of the line. 
298      */
299     public void setLocation(RouteLine line, double x, double y) {
300         makePersistent(line);
301         line.setLocation(x, y);
302         needsUpdate = true;
303     }
304     
305     /**
306      * Moves the terminal to given location.
307      */
308     public void setLocation(RouteTerminal terminal, double x, double y) {
309         terminal.setLocation(x, y);
310         needsUpdate = true;
311     }
312
313     /**
314      * Updates transient route lines, route link positions
315      * and sorts route points of each route line.
316      */
317     public void update() {
318         needsUpdate = false;
319         removeTransientRouteLines();
320         removeRouteTerminalsFromRouteLines();
321
322         //print();
323         
324         for(RouteLine line : lines)
325             line.hidden = false;
326         for(RouteTerminal terminal : terminals)
327             if(terminal.hasDirectConnection() && terminal.line != null)
328                 terminal.line.hidden = true;
329
330         // Choose a strategy
331         if(isSimpleConnection) {
332             RouteTerminal a = terminals.get(0);
333             RouteTerminal b = terminals.get(1);
334             if(a.hasDirectConnection() || b.hasDirectConnection())
335                 return;
336             caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
337             //System.out.println("caseId = " + caseId);
338             switch(caseId) {
339             case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION: 
340             case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
341                 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
342                 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
343                 line.addPoint(a);
344                 line.addPoint(b);
345                 line.terminal = a;
346                 transientLines.add(line);
347                 
348                 // Path terminal
349                 a.line = line;
350                 b.line = line;
351                 
352                 break;
353             }
354             case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
355                 RouteLine line1 = new RouteLine(true, a.y);
356                 RouteLine line2 = new RouteLine(false, b.x);
357                 new RouteLink(line1, line2);
358                 line1.addPoint(a);
359                 line2.addPoint(b);
360                 line1.terminal = a;
361                 line2.terminal = b;
362                 transientLines.add(line1);
363                 transientLines.add(line2);
364                
365                 // Path terminal
366                 a.line = line1;
367                 b.line = line2;
368                 break;
369             }
370             case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
371                 RouteLine line1 = new RouteLine(false, a.x);
372                 RouteLine line2 = new RouteLine(true, b.y);
373                 new RouteLink(line1, line2);
374                 line1.addPoint(a);
375                 line2.addPoint(b);
376                 line1.terminal = a;
377                 line2.terminal = b;
378                 transientLines.add(line1);
379                 transientLines.add(line2);
380                 
381                 //Path terminal
382                 a.line = line1;
383                 b.line = line2;
384                 break;
385             }
386             case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT: 
387             case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
388                 RouteLine line =
389                         SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
390                                 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
391                                 ;
392                 terminals.get(0).line = line;
393                 terminals.get(1).line = line;
394                 transientLines.add(line);
395                 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
396                 break;
397             }
398             }
399             //routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
400         }
401         else {
402             caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
403             routeFromTerminals(false);
404         }
405         
406         // Find positions of route points
407         for(RouteLine line : lines) 
408             line.setPointPositions();
409         for(RouteLine line : transientLines) 
410             line.setPointPositions();
411         
412         // Sort route points in route lines
413         for(RouteLine line : lines) {
414             line.sortPoints();
415         }
416         for(RouteLine line : transientLines) {
417             line.sortPoints();
418         }
419     }
420     
421     public static class Interval {
422         public final double min;
423         public final double max;
424         public Interval(double min, double max) {
425             this.min = min;
426             this.max = max;
427         }
428     }
429     
430     public class IntervalCache {
431         THashMap<RouteLine, Interval> cache = 
432                 new THashMap<RouteLine, Interval>();
433         public Interval get(RouteLine line) {
434             Interval result = cache.get(line);
435             if(result != null)
436                 return result;
437             
438             result = create(line);
439             cache.put(line, result);
440             return result;
441         }
442         
443         private Interval create(RouteLine line) {
444             double min = Double.POSITIVE_INFINITY;
445             double max = Double.NEGATIVE_INFINITY;
446             
447             for(RoutePoint point : line.points) {
448                 double temp;
449                 if(point instanceof RouteLink) {
450                     RouteLink link = (RouteLink)point;
451                     if(link.a == line)
452                         temp = link.b.position;
453                     else
454                         temp = link.a.position;
455                 }
456                 else {
457                     RouteTerminal terminal = (RouteTerminal)point;
458                     if(line.isHorizontal)
459                         temp = terminal.x;
460                     else
461                         temp = terminal.y;
462                 }
463                 if(temp < min)
464                     min = temp;
465                 if(temp > max)
466                     max = temp;
467             }
468             for(RouteTerminal terminal : terminals) {
469                 if(terminal.line == line) {
470                     double temp = terminal.approximatePositionToLine();
471                     if(temp < min)
472                         min = temp;
473                     if(temp > max)
474                         max = temp;
475                 }
476             }
477             
478             return new Interval(min, max);
479         }
480     } 
481     
482     protected void routeFromTerminals(boolean boundingBoxesIntersect) {
483         IntervalCache cache = new IntervalCache();
484         for(RouteTerminal terminal : terminals) 
485             if(terminal.line != null) {
486                 if(!terminal.hasDirectConnection())
487                     terminal.route(transientLines, cache, boundingBoxesIntersect);
488             }
489     }
490         
491     /**
492      * Returns a RouteLine near the given point (x,y) (within tolerance).
493      */
494     public RouteLine pickLine(double x, double y, double tolerance, int mask) {
495         if(needsUpdate)
496             update();
497         if(isSimpleConnection && transientLines.isEmpty()) {
498             if(terminals.size() == 2) {
499                 if((mask & PICK_TRANSIENT_LINES) == 0)
500                     return null;
501                 RouteTerminal a = terminals.get(0);
502                 RouteTerminal b = terminals.get(1);
503                 if(a.hasDirectConnection() || b.hasDirectConnection()) {
504                     if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
505                         RouteLine dummy = new RouteLine(false, y);
506                         return dummy; // There are no lines to return
507                     }
508                     else
509                         return null;
510                 }
511             }
512         }
513         if((mask & PICK_PERSISTENT_LINES) != 0)
514             for(RouteLine line : lines)
515                 if(line.isNear(x, y, tolerance))
516                     return line;
517         if((mask & PICK_TRANSIENT_LINES) != 0)
518             for(RouteLine line : transientLines)
519                 if(line.isNear(x, y, tolerance))
520                     return line;
521         if((mask & PICK_DIRECT_LINES) != 0) {
522             RouteTerminal terminal = pickDirectLine(x, y, tolerance);
523             if(terminal != null)
524                 return terminal.line;
525         }
526         return null;
527     }
528     
529     public RouteLine pickLine(double x, double y, double tolerance) {
530         return pickLine(x, y, tolerance, PICK_LINES);
531     }
532     
533     private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
534         double toleranceSq = tolerance * tolerance;
535         for(RouteTerminal terminal : terminals)
536             if((terminal.getAllowedDirections()&0x10) != 0) {     
537                 try {
538                     RouteLine line = terminal.getLine();
539                     if(line == null)
540                         continue;
541                     RoutePoint b = line.getBegin();
542                     double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y); 
543                     if(distSq <= toleranceSq) {
544                         //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
545                         return terminal;
546                     }
547                 } catch(NullPointerException e) {
548                     //if terminal does not have a line
549                     e.printStackTrace();
550                 } catch(IndexOutOfBoundsException e) {
551                     // if line does not contain points
552                     e.printStackTrace();
553                 }
554             }
555         return null;
556     }
557
558     public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
559         if(isSimpleConnection)
560             return null;
561         if(needsUpdate)
562             update();
563         RouteLine line = pickLine(x, y, tolerance);
564         if(line == null)
565             return null;
566         RouteLink link = null;
567         RoutePoint begin = line.getBegin();
568         RoutePoint end = line.getEnd();
569         if(line.isHorizontal) {
570             double mx = 0.5*(begin.getX() + end.getX());
571             if(x < mx) {
572                 if(begin instanceof RouteLink)
573                     link = (RouteLink)begin;
574             }
575             else {
576                 if(end instanceof RouteLink)
577                     link = (RouteLink)line.getEnd();
578             }
579         }
580         else {
581             double my = 0.5*(begin.getY() + end.getY());
582             if(y < my) {
583                 if(begin instanceof RouteLink)
584                     link = (RouteLink)begin;
585             }
586             else {
587                 if(end instanceof RouteLink)
588                     link = (RouteLink)end;
589             }
590         }
591         if(link == null)
592             return null;
593         if(link.getOther(line).isTransient())
594             return null;
595         return new RouteLineHalf(line, link);
596     }
597
598     public Collection<RouteLineHalf> getLineHalves() {
599         return getLineHalves(new ArrayList<RouteLineHalf>());
600     }
601
602     public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
603         for(RouteLine line : getAllLines()) {
604             {
605                 RoutePoint p = line.getBegin();
606                 if(p instanceof RouteLink) {
607                     RouteLink link = (RouteLink)p;
608                     if(!link.getOther(line).isTransient())
609                         result.add(new RouteLineHalf(line, link));
610                 }
611             }
612             {
613                 RoutePoint p = line.getEnd();
614                 if(p instanceof RouteLink) {
615                     RouteLink link = (RouteLink)p;
616                     if(!link.getOther(line).isTransient())
617                         result.add(new RouteLineHalf(line, link));
618                 }
619             }
620         }
621         return result;
622     }
623
624     /**
625      * Returns a RoutePoint near the given point (x,y) (within tolerance).
626      */
627     public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
628         if(needsUpdate)
629             update();
630         if((mask&PICK_TERMINALS) != 0)
631             for(RouteTerminal terminal : terminals)
632                 if(terminal.isNear(x, y))
633                     return terminal;
634         if((mask&PICK_INTERIOR_POINTS) != 0) {
635             for(RouteLine line : lines) {
636                 for(RoutePoint point : line.points)
637                     if(point.isNear(x, y, tolerance))
638                         return point;
639             }
640             for(RouteLine line : transientLines) {
641                 for(RoutePoint point : line.points)
642                     if(point.isNear(x, y, tolerance))
643                         return point;
644             }
645         }
646         return null;
647     }
648     
649     public RoutePoint pickPoint(double x, double y, double tolerance) {
650         return pickPoint(x, y, tolerance, PICK_POINTS);
651     }
652     
653     public static final int PICK_INTERIOR_POINTS = 1;
654     public static final int PICK_TERMINALS = 2;
655     public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
656     
657     public static final int PICK_PERSISTENT_LINES = 4;
658     public static final int PICK_TRANSIENT_LINES = 8;
659     public static final int PICK_DIRECT_LINES = 16;
660     public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
661     
662     public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
663     
664     /**
665      * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
666      */
667     public Object pick(double x, double y, double tolerance, int mask) {
668         if((mask & PICK_POINTS) != 0) {
669             Object point = pickPoint(x, y, tolerance, mask);
670             if(point != null)
671                 return point;
672         }
673         /*if((mask & PICK_DIRECT_LINES) != 0) {
674             RouteTerminal terminal = pickDirectLine(x, y, tolerance);
675             if(terminal != null)
676                 return terminal.line.getBegin();
677         }*/
678         if((mask & PICK_LINES) != 0)
679             return pickLine(x, y, tolerance, mask);
680         else
681             return null;
682     }
683     
684     public Object pick(double x, double y, double tolerance) {
685         return pick(x, y, tolerance, PICK_ALL);
686     }
687     
688     /**
689      * Returns RoutePoint or RouteLine exactly under the given point (x,y).
690      */
691     public Object pick(double x, double y) {
692         return pick(x, y, 0.0);
693     }
694     
695     /**
696      * Prints the contents of the route graph to stdout.
697      */
698     public void print() {
699         print(System.out);
700     }
701     
702     /**
703      * Prints the contents of the route graph to given print stream.
704      */
705     public void print(PrintStream out) {
706         if(needsUpdate)
707             update();
708         if(isSimpleConnection)
709             out.println("=== SIMPLE CONNECTION ===");
710         else
711             out.println("=== COMPLEX CONNECTION ===");
712         for(RouteLine line : lines) {
713             out.print("perst");
714             line.print(out);
715         }
716         for(RouteLine line : transientLines) {
717             out.print("trans");
718             line.print(out);
719         }
720         for(RouteTerminal terminal : terminals) {
721             out.print("term");
722             terminal.print(out);
723         }
724     }
725
726     public void makePersistent(RouteLine line) {
727         prepareForModification();
728         if(isSimpleConnection || line.isTransient()) {
729             if(isSimpleConnection) {
730                 isSimpleConnection = false;
731                 for(RouteTerminal terminal : terminals)
732                     terminal.line = line;
733                 transientLines.remove(line);
734                 lines.add(line);  
735                 Iterator<RoutePoint> it = line.points.iterator();
736                 while(it.hasNext()) {
737                     RoutePoint point = it.next();
738                     if(point instanceof RouteTerminal)
739                         it.remove();
740                 }
741                 line.terminal = null;
742                 line.nextTransient = null;
743             }
744             else {
745                 line.terminal.line = line;
746                 do {
747                     transientLines.remove(line);
748                     lines.add(line);  
749                     Iterator<RoutePoint> it = line.points.iterator();
750                     while(it.hasNext()) {
751                         RoutePoint point = it.next();
752                         if(point instanceof RouteTerminal)
753                             it.remove();
754                     }
755                     line.terminal = null;
756                     RouteLine temp = line.nextTransient;
757                     line.nextTransient = null;
758                     line = temp;
759                 } while(line != null);
760             }
761             needsUpdate = true;
762         }
763     }
764
765     void prepareForModification() {
766         if(caseId == 4) {
767             RouteLine line = transientLines.remove(0);
768             line.terminal = null;
769             lines.add(line);
770             for(RouteTerminal terminal : terminals)
771                 terminal.line = line;
772             isSimpleConnection = false;
773             caseId = 6;
774         }
775     }
776     
777     public double[] getLineLengths(RouteTerminal terminal) {
778         if(needsUpdate)
779             update();
780         if(lines.size()==0 && transientLines.size()==1)
781             return new double[] { transientLines.get(0).getLength() };
782         
783         RouteLine line = null;
784         fLoop:
785         for(RouteLine l : transientLines)
786             if(l.isTransient()) {
787                 for(RoutePoint p : l.points)
788                     if(!(p instanceof RouteLink)) {
789                         line = l;
790                         break fLoop;
791                     }
792             }
793         TDoubleArrayList result = new TDoubleArrayList();
794         THashSet<RouteLine> set = new THashSet<RouteLine>();
795         set.add(line);
796         loop:
797         while(true) {            
798             result.add(line.getLength());
799             for(RoutePoint point : line.points)
800                 if(point instanceof RouteLink) {
801                     RouteLink link = (RouteLink)point; 
802                     if(set.add(link.a)) {
803                         line = link.a;
804                         continue loop;
805                     }
806                     if(set.add(link.b)) {
807                         line = link.b;
808                         continue loop;
809                     }
810                 }
811             break;
812         }
813         return result.toArray();
814     }
815
816     public void split(RouteLine rl1, double splitPosition) {
817         if(needsUpdate)
818             update();
819         boolean isHorizontal = rl1.isHorizontal();
820         if(isSimpleConnection) {
821             isSimpleConnection = false;
822             if(caseId < 2) {
823                 RouteLine sp = addLine(!isHorizontal, splitPosition);
824                 for(RouteTerminal terminal : terminals)
825                     terminal.line = sp;
826                 update();
827                 return;
828             }
829             else if(caseId < 4) {
830                 RouteLine sp = addLine(!isHorizontal, splitPosition);
831                 RouteLine l = addLine(isHorizontal, rl1.position);
832                 link(l, sp);
833                 rl1.terminal.line = sp;
834                 for(RouteTerminal terminal : terminals)
835                     if(terminal != rl1.terminal)
836                         terminal.line = l;
837                 update();
838                 return;
839             }
840             else
841                 prepareForModification();
842         }
843
844         RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
845         RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
846
847         ArrayList<RoutePoint> points = rl1.points;
848
849         int splitPos;
850         {
851             int minPos = 0;
852             int maxPos = points.size();
853             while(minPos != maxPos) {
854                 int c = (minPos + maxPos)/2;
855                 if(isHorizontal 
856                         ? points.get(c).getX() > splitPosition 
857                         : points.get(c).getY() > splitPosition)
858                     maxPos = c;
859                 else
860                     minPos = c+1;
861             }
862             splitPos = minPos;
863         }
864
865         for(int i=points.size()-1;i>=splitPos;--i) {
866             RoutePoint point = points.remove(i);
867             if(point instanceof RouteLink) {
868                 RouteLink link = (RouteLink)point;
869                 link.replace(rl1, rl2);
870             }
871         }
872
873         if(rl1.isTransient()) {
874             boolean p1 = rl1.isConnectedToPeristentLine();
875             boolean p2 = rl2.isConnectedToPeristentLine();
876
877             RouteTerminal terminal = rl1.terminal;
878             if(p1) {
879                 makePersistent(rl1);
880                 transientLines.add(rl2);
881             }
882             else if(p2) {
883                 lines.add(rl2);
884             }
885             else {
886                 transientLines.add(rl2);
887                 if(lines.isEmpty())
888                     for(RouteTerminal t : terminals)
889                         t.line = sp;
890             }
891             terminal.line = sp;
892         }
893         else
894             lines.add(rl2);
895
896         new RouteLink(rl1, sp);
897         new RouteLink(sp, rl2);
898         lines.add(sp);
899         update();
900     }
901
902     public boolean merge(RouteLine line) {
903         int count = 0;
904         double sum = 0;
905         for(RoutePoint point : line.points) {
906             if(point instanceof RouteLink) {
907                 RouteLink link = (RouteLink)point;
908                 RouteLine other = link.getOther(line);
909                 if(!other.isTransient()) {
910                     sum += other.position;
911                     ++count;
912                 }
913             }
914         }
915         return merge(line, sum / count);
916     }
917
918     /**
919      * Removes given route line and collapses all its neighbor
920      * route lines into one line with given position.
921      */
922     public boolean merge(RouteLine line, double position) {
923         if(needsUpdate)
924             update();
925         if(isSimpleConnection || line.isTransient())
926             return false;
927         
928         if(lines.size() == 1) {
929             if(terminals.size() != 2)
930                 return false;
931             lines.remove(0);
932             isSimpleConnection = true;
933             for(RouteTerminal terminal : terminals)
934                 terminal.line = null;
935             update();
936             return true;
937         }
938         
939         ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
940         for(RoutePoint point : line.points) {
941             /* Because line.terminal == null, there should be 
942              * not RouteTerminals 
943              * 
944              * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal. 
945              */
946             if (point instanceof RouteLink) {
947                 RouteLine l = ((RouteLink)point).getOther(line);
948                 l.points.remove(point);
949                 if(!l.isTransient())
950                     nLines.add(l);
951             }
952         }
953         
954         if(nLines.isEmpty())
955             return false;
956         RouteLine merged = nLines.remove(nLines.size()-1);
957         merged.position = position;
958         for(RouteLine l : nLines) {
959             for(RoutePoint point : l.points) {
960                 /* Because l.terminal == null, there should be 
961                  * not RouteTerminals 
962                  * 
963                  * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal. 
964                  */
965                 if (point instanceof RouteLink) {
966                     RouteLink link = (RouteLink)point;
967                     link.replace(l, merged);
968                 }
969             }
970         }
971         THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
972         removedLines.addAll(nLines);
973         lines.removeAll(removedLines);
974         removedLines.add(line);
975         lines.remove(line);
976         for(RouteTerminal terminal : terminals)
977             if(removedLines.contains(terminal.line))
978                 terminal.line = merged;
979         update();
980         return true;
981     }
982
983     public void deleteCorner(RouteLink link) {
984         if(needsUpdate)
985             update();
986         RouteLine a = link.getA();
987         RouteLine b = link.getB();
988         if(a.isTransient() || b.isTransient() 
989                 || a.points.size() != 2 || b.points.size() != 2)
990             return;
991         RouteLine na=null, nb=null;
992         for(RoutePoint p : a.points) {
993             RouteLink l = (RouteLink)p;
994             if(l.a == a && l.b != b) {
995                 na = l.b;
996                 break;
997             }
998             else if(l.b == a && l.a != b) {
999                 na = l.a;
1000                 break;
1001             }
1002         }        
1003         for(RoutePoint p : b.points) {
1004             RouteLink l = (RouteLink)p;
1005             if(l.a == b && l.b != a) {
1006                 nb = l.b;
1007                 break;
1008             }
1009             else if(l.b == b && l.a != a) {
1010                 nb = l.a;
1011                 break;
1012             }
1013         }
1014         if(na == null || nb == null) {
1015             System.err.println("Internal error in router.");
1016             return;
1017         }
1018         a.remove();
1019         b.remove();
1020         lines.remove(a);
1021         lines.remove(b);
1022         link(na, nb);
1023         if(na.terminal != null)
1024             na.terminal.line = nb;
1025         if(nb.terminal != null)
1026             nb.terminal.line = na;
1027         update();
1028     }
1029     
1030     public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1031         Object target = pick(x, y, tolerance);
1032         if(target instanceof RouteLine) {
1033             RouteLine line = (RouteLine)target;
1034             RouteTerminal involvedTerminal = 
1035                     line.isTransient() ? line.terminal : null;
1036             makePersistent(line);
1037             terminal.line = null; // TODO this is a workaround
1038             
1039             int lineDir = line.isHorizontal 
1040                     ? (line.position < terminal.y ? 3 : 1)
1041                     : (line.position < terminal.x ? 2 : 0)
1042                     ;
1043                     
1044             if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1045                 RouteLine l2;
1046                 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1047                     RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1048                     l2 = addLine(false, x);
1049                     link(terminal, l1, l2, line);
1050                 }
1051                 else {
1052                     l2 = addLine(false, x);
1053                     link(terminal, l2, line);
1054                 }
1055                 if(involvedTerminal != null)
1056                     involvedTerminal.line = l2;
1057             }
1058             else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1059                 RouteLine l2;
1060                 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1061                     RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1062                     l2 = addLine(true, y);
1063                     link(terminal, l1, l2, line);
1064                 }
1065                 else {
1066                     l2 = addLine(true, y);
1067                     link(terminal, l2, line);
1068                 }
1069                 if(involvedTerminal != null)
1070                     involvedTerminal.line = l2;
1071             }
1072             else {
1073                 link(terminal, line);
1074             }
1075             update();
1076             return true;
1077         }
1078         else
1079             return false;
1080     }
1081     
1082     public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1083         Object target = pick(x, y, tolerance);
1084         if(target instanceof RouteLine) {
1085             RouteLine line = (RouteLine)target;
1086             RouteTerminal involvedTerminal = 
1087                     line.isTransient() ? line.terminal : null;
1088             makePersistent(line);
1089             if(line.isHorizontal == sLine.isHorizontal) {
1090                 RouteLine l = addLine(!sLine.isHorizontal, 
1091                         sLine.isHorizontal ? x : y); 
1092                 link(sLine, l, line);
1093                 if(involvedTerminal != null)
1094                     involvedTerminal.line = l;
1095             }
1096             else {
1097                 link(sLine, line);
1098                 if(involvedTerminal != null)
1099                     involvedTerminal.line = sLine;
1100             }
1101             update();
1102             return true;
1103         }
1104         else
1105             return false;
1106     }
1107
1108     /**
1109      * Makes a deep copy of the route graph and stores
1110      * the correspondences between original and copied
1111      * objects into the given map.
1112      */
1113     public RouteGraph copy(THashMap<Object, Object> map) {
1114         RouteGraph copy = new RouteGraph();
1115         copy.isSimpleConnection = isSimpleConnection;
1116         copy.caseId = caseId;
1117         copy.needsUpdate = needsUpdate;
1118         for(RouteLine line : lines)
1119             copy.lines.add(line.copy(map));
1120         for(RouteLine line : transientLines)
1121             copy.transientLines.add(line.copy(map));
1122         for(RouteTerminal terminal : terminals)
1123             copy.terminals.add(terminal.copy(map));
1124         return copy;
1125     }
1126     
1127     /**
1128      * Makes a deep copy of the route graph.
1129      */
1130     public RouteGraph copy() {
1131         THashMap<Object, Object> map = new THashMap<Object, Object>(); 
1132         return copy(map);
1133     }
1134     
1135     /**
1136      * Removes route lines that are conneted to at most
1137      * one other route line or terminal.
1138      */
1139     public void removeExtraConnections() {
1140         TObjectIntHashMap<RouteLine> counts = 
1141                 new TObjectIntHashMap<RouteLine>();
1142         removeTransientRouteLines();
1143         for(RouteLine line : lines) {
1144             int count = 0;
1145             for(RoutePoint point : line.points)
1146                 if(point instanceof RouteLink)
1147                     ++count;
1148             counts.put(line, count);
1149         }
1150         for(RouteTerminal terminal : terminals)
1151             counts.adjustOrPutValue(terminal.line, 1, 1);
1152         boolean removed;
1153         do {
1154             removed = false;
1155             Iterator<RouteLine> it = lines.iterator();
1156             while(it.hasNext()) {
1157                 RouteLine line = it.next();
1158                 if(counts.get(line) <= 1) {
1159                     for(RoutePoint point : line.points)
1160                         if(point instanceof RouteLink)
1161                             counts.adjustValue(((RouteLink)point).getOther(line), -1);
1162                     line.remove();
1163                     it.remove();
1164                     removed = true;
1165                 }
1166             }
1167         } while(removed);
1168         update();
1169     }
1170     
1171     /**
1172      * Removes a terminal and all route lines that become degenerated by the removal. 
1173      */
1174     public void remove(RouteTerminal terminal) {
1175         terminals.remove(terminal);
1176         removeExtraConnections();
1177     }
1178     
1179     public void disconnect(RouteTerminal terminal) {
1180         terminal.line = null;
1181         removeExtraConnections();
1182     }
1183
1184     public void remove(RouteLink link) {
1185         link.a.points.remove(link);
1186         link.b.points.remove(link);
1187     }
1188
1189     public void toggleDirectLines(RouteTerminal terminal) {
1190         terminal.toggleDirectLines();
1191         needsUpdate = true;
1192     }
1193
1194     /**
1195      * Returns all persistent route lines of the route graph.
1196      */
1197     public Collection<RouteLine> getLines() {
1198         if(needsUpdate)
1199             update();
1200         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1201             return Collections.unmodifiableList(lines);
1202         else
1203             return lines;
1204     }
1205
1206     /*
1207      * Returns all transient route lines of the route graph.
1208      */
1209     public Collection<RouteLine> getTransientLines() {
1210         if(needsUpdate)
1211             update();
1212         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1213             return Collections.unmodifiableList(transientLines);
1214         else
1215             return transientLines;
1216     }
1217
1218     /**
1219      * Returns all terminals of the route graph.
1220      */
1221     public Collection<RouteTerminal> getTerminals() {
1222         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1223             return Collections.unmodifiableList(terminals);
1224         else
1225             return terminals;
1226     }
1227     
1228     /**
1229      * Returns all route lines, both persistent and transient,
1230      * of the route graph.
1231      */
1232     public Collection<RouteLine> getAllLines() {
1233         if(needsUpdate)
1234             update();
1235         ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1236         allLines.addAll(lines);
1237         allLines.addAll(transientLines);
1238         return allLines;
1239     }
1240     
1241     /**
1242      * Returns all route lines, both persistent and transient, of the route
1243      * graph, added to the specified collection. Avoids allocation of new
1244      * {@link ArrayList} compared to {@link #getAllLines()}.
1245      */
1246     public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1247         if (result == null)
1248             throw new NullPointerException("null result collection");
1249         if(needsUpdate)
1250             update();
1251         result.addAll(lines);
1252         result.addAll(transientLines);
1253         return result;
1254     }
1255     
1256     /**
1257      * Returns true, if the route graph is connected and contains no cycles.
1258      */
1259     public boolean isTree() {
1260         if(isSimpleConnection)
1261             return true;
1262         for(RouteTerminal terminal : terminals)
1263             if(terminal.line == null)
1264                 return false;
1265         THashSet<RouteLine> visited = new THashSet<RouteLine>(); 
1266         ArrayList<RouteLine> stack = new ArrayList<RouteLine>(); 
1267         int linkCount = 0;
1268         visited.add(lines.get(0));
1269         stack.add(lines.get(0));
1270         while(!stack.isEmpty()) {
1271             RouteLine cur = stack.remove(stack.size()-1);
1272             for(RouteLine n : cur.getPersistentNeighbors()) {
1273                 ++linkCount;
1274                 if(visited.add(n))
1275                     stack.add(n);
1276             }
1277         }
1278         return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1279     }
1280     
1281     /**
1282      * Returns if the connection is simple. A connection is simple, if it has just
1283      * two terminals connected together directly without (persistent) route lines.
1284      */
1285     public boolean isSimpleConnection() {
1286         return isSimpleConnection;
1287     }
1288
1289     public void replaceBy(RouteGraph rg) {
1290         this.lines = rg.lines;
1291         this.terminals = rg.terminals;
1292         this.transientLines = rg.transientLines;
1293         this.caseId = rg.caseId;
1294         this.isSimpleConnection = rg.isSimpleConnection;
1295         this.needsUpdate = rg.needsUpdate;
1296         rg.reset();
1297     }
1298
1299     private void reset() {
1300         lines = new ArrayList<RouteLine>();
1301         terminals = new ArrayList<RouteTerminal>();
1302         transientLines = new ArrayList<RouteLine>();
1303         caseId = 0;
1304         isSimpleConnection = false;
1305         needsUpdate = false;
1306     }
1307
1308     public Rectangle2D getBounds() {
1309         Rectangle2D bounds = new Rectangle2D.Double();
1310         getBounds(bounds);
1311         return bounds;
1312     }
1313
1314     public void getBounds(Rectangle2D bounds) {
1315         if(needsUpdate)
1316             update();
1317         double minX = Double.POSITIVE_INFINITY;
1318         double maxX = Double.NEGATIVE_INFINITY;
1319         double minY = Double.POSITIVE_INFINITY;
1320         double maxY = Double.NEGATIVE_INFINITY;
1321         for(RouteLine line : lines) {
1322             double position = line.position;
1323             if(line.isHorizontal) {
1324                 minY = Math.min(minY, position);
1325                 maxY = Math.max(maxY, position);
1326             }
1327             else {
1328                 minX = Math.min(minX, position);
1329                 maxX = Math.max(maxX, position);
1330             }
1331         }
1332         for(RouteLine line : transientLines) {
1333             double position = line.position;
1334             if(line.isHorizontal) {
1335                 minY = Math.min(minY, position);
1336                 maxY = Math.max(maxY, position);
1337             }
1338             else {
1339                 minX = Math.min(minX, position);
1340                 maxX = Math.max(maxX, position);
1341             }
1342         }
1343         for(RouteTerminal terminal : terminals) {
1344             double x = terminal.x;
1345             double y = terminal.y;
1346             minX = Math.min(minX, x);
1347             maxX = Math.max(maxX, x);
1348             minY = Math.min(minY, y);
1349             maxY = Math.max(maxY, y);
1350         }
1351         bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1352     }
1353
1354     private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1355         double x = cur.x, y = cur.y;
1356         if(cur instanceof RouteTerminal) {
1357             ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1358             if(line.isHorizontal()) {
1359                 if(cur == line.getBegin())
1360                     x += style.getLineEndLength(0);
1361                 else
1362                     x -= style.getLineEndLength(2);
1363             }
1364             else {
1365                 if(cur == line.getBegin())
1366                     y += style.getLineEndLength(1);
1367                 else
1368                     y -= style.getLineEndLength(3);
1369             }
1370         }
1371         path.moveTo(x, y);
1372     }
1373     
1374     private static final Comparator<RoutePoint> RG_COMP = (o1, o2) -> {
1375         if (o1.getX() < o2.getX())
1376             return -1;
1377         else if (o1.getX() > o2.getX())
1378             return 1;
1379         if (o1.getY() < o2.getY())
1380             return -1;
1381         else if (o1.getY() > o2.getY())
1382             return 1;
1383         return 0;
1384     };
1385     
1386     private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1387         double x = cur.x, y = cur.y;
1388         if(cur instanceof RouteTerminal) {
1389             ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1390             if(line.isHorizontal()) {
1391                 if(cur == line.getBegin())
1392                     x += style.getLineEndLength(0);
1393                 else
1394                     x -= style.getLineEndLength(2);
1395             }
1396             else {
1397                 if(cur == line.getBegin())
1398                     y += style.getLineEndLength(1);
1399                 else
1400                     y -= style.getLineEndLength(3);
1401             }
1402         }
1403         path.lineTo(x, y);
1404     }
1405     
1406     public void getPath2D(Path2D path) {
1407         if(needsUpdate)
1408             update();
1409         
1410         if(isSimpleConnection && transientLines.isEmpty()) {
1411             if(terminals.size() == 2) {
1412                 RouteTerminal a = terminals.get(0);
1413                 RouteTerminal b = terminals.get(1);
1414                 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1415                     path.moveTo(a.x, a.y);
1416                     path.lineTo(b.x, b.y);
1417                     return;
1418                 }
1419             }
1420         }
1421
1422         // Analyze graph
1423         Map<RoutePoint, RouteLine> begins = new HashMap<RoutePoint, RouteLine>();
1424         for(RouteLine line : lines) {
1425             add(begins, line);
1426         }
1427         for(RouteLine line : transientLines) {
1428             add(begins, line);
1429         }
1430         for(RouteTerminal terminal : terminals)
1431             if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1432                 begins.remove(terminal.line.getBegin());
1433                 drawContinuousPath(path, begins, terminal, terminal.line);
1434             }
1435
1436         // Create paths
1437         // Sort the begins so that the order of segments is deterministic. This is required when comparing e.g. SVG diagrams. 
1438         // In case of overlapping begins the order may vary.
1439         for(RoutePoint begin : begins.keySet().stream().sorted(RG_COMP).collect(Collectors.toList())) {
1440             RouteLine curLine = begins.remove(begin);
1441             drawContinuousPath(path, begins, begin, curLine);
1442         }
1443     }
1444     
1445     private void drawContinuousPath(Path2D path, Map<RoutePoint, RouteLine> begins,
1446             RoutePoint cur, RouteLine curLine) {
1447         if(curLine == null)
1448             return;
1449         addPathBegin(path, cur, curLine);
1450
1451         while(true) {
1452             if(cur != curLine.getEnd())                    
1453                 cur = curLine.getEnd();
1454             else
1455                 cur = curLine.getBegin();
1456             if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1457                 addPathEnd(path, cur, curLine);
1458                 return;
1459             }
1460             if(cur instanceof RouteLink) {
1461                 if(!curLine.isDegenerated() || 
1462                         path.getCurrentPoint().getX() != cur.x || 
1463                         path.getCurrentPoint().getY() != cur.y)
1464                     path.lineTo(cur.x, cur.y);
1465                 RouteLink link = (RouteLink)cur;
1466                 if(link.a != curLine)
1467                     curLine = link.a;
1468                 else
1469                     curLine = link.b;
1470             }
1471         }
1472     }
1473
1474     private static void add(Map<RoutePoint, RouteLine> begins,
1475             RouteLine line) { 
1476         if(line.points.size() > 1) {
1477             {
1478                 RoutePoint p = line.getBegin();
1479                 if(begins.remove(p) == null)
1480                     begins.put(p, line);
1481             }
1482             {
1483                 RoutePoint p = line.getEnd();
1484                 if(begins.remove(p) == null)
1485                     begins.put(p, line);
1486             }
1487         }
1488     }
1489
1490     public Collection<Segment> getSegments() {
1491         if (needsUpdate)
1492             update();
1493         ArrayList<Segment> segments = new ArrayList<Segment>();
1494         for(RouteLine routeLine : lines)
1495             routeLine.collectSegments(segments);
1496         for(RouteLine routeLine : transientLines)
1497             routeLine.collectSegments(segments);
1498         return segments;
1499     }
1500     
1501     public Segment findNearestSegment(double x, double y) {
1502         Segment nearest = null;
1503         double minDistanceSq = Double.MAX_VALUE;
1504
1505         for (Segment segment : getSegments()) {
1506             RoutePoint p1 = segment.p1;
1507             RoutePoint p2 = segment.p2;
1508
1509             double distanceSq = Line2D.ptSegDistSq(p1.x, p1.y, p2.x, p2.y, x, y);
1510             if (distanceSq < minDistanceSq) {
1511                 minDistanceSq = distanceSq;
1512                 nearest = segment;
1513             }
1514         }
1515         return nearest;
1516     }
1517
1518     public Point2D findNearestPoint(double x, double y) {
1519         Segment nearest = findNearestSegment(x, y);
1520         if (nearest == null) return null;
1521
1522         RoutePoint p1 = nearest.p1;
1523         RoutePoint p2 = nearest.p2;
1524
1525         double d = Math.pow(p2.x - p1.x, 2.0) + Math.pow(p2.y - p1.y, 2.0);
1526
1527         if (d == 0) {
1528             return new Point2D.Double(p1.x, p1.y);
1529         } else {
1530             double u = ((x - p1.x) * (p2.x - p1.x) + (y - p1.y) * (p2.y - p1.y)) / d;
1531             if (u > 1.0) {
1532                 return new Point2D.Double(p2.x, p2.y);
1533             } else if (u <= 0.0) {
1534                 return new Point2D.Double(p1.x, p1.y);
1535             } else {
1536                 return new Point2D.Double(p2.x * u + p1.x * (1.0-u), (p2.y * u + p1.y * (1.0- u)));
1537             }
1538         }
1539     }
1540
1541     public Path2D getPath2D() {
1542         Path2D result = new Path2D.Double();
1543         getPath2D(result);
1544         return result;
1545     }
1546     
1547     public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1548         THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1549         THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1550         THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1551         THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1552         THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1553         THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1554
1555         if(splitLine.isTransient()) {
1556             RouteTerminal terminal = splitLine.terminal;
1557             
1558             if(splitLine.beginsWithTerminal()) {
1559                 lines2.addAll(getLines());
1560                 terminals2.addAll(getTerminals());
1561                 terminals1.add(terminal);
1562                 terminals2.remove(terminal);
1563                 interfaceNodes1.add(terminal);
1564                 if(isSimpleConnection())
1565                     interfaceNodes2.addAll(terminals2);
1566                 else
1567                     interfaceNodes2.add(terminal.line);
1568             }
1569             else {
1570                 lines1.addAll(getLines());
1571                 terminals1.addAll(getTerminals());
1572                 terminals2.add(terminal);
1573                 terminals1.remove(terminal);
1574                 interfaceNodes2.add(terminal);
1575                 if(isSimpleConnection())
1576                     interfaceNodes1.addAll(terminals1);
1577                 else
1578                     interfaceNodes1.add(terminal.line);
1579             }
1580         }
1581         else {
1582             for(RoutePoint rp : splitLine.getPoints()) {
1583                 double p = splitLine.isHorizontal ? rp.x : rp.y;
1584                 if(rp instanceof RouteLink) {
1585                     RouteLink link = (RouteLink)rp;
1586                     RouteLine otherLine = link.getA() != splitLine ? link.getA()
1587                             : link.getB();
1588                     if(otherLine.isTransient()) {
1589                         if(p < position) {
1590                             interfaceNodes1.add(otherLine.terminal);
1591                             terminals1.add(otherLine.terminal);
1592                         }
1593                         else {
1594                             interfaceNodes2.add(otherLine.terminal);
1595                             terminals2.add(otherLine.terminal);
1596                         }
1597                         continue;
1598                     }                
1599                 
1600                     if(p < position) {
1601                         interfaceNodes1.add(otherLine);
1602                         traverseGraph(link, otherLine, lines1);
1603                     }
1604                     else {
1605                         interfaceNodes2.add(otherLine);
1606                         traverseGraph(link, otherLine, lines2);
1607                     }   
1608                 }
1609             }
1610             
1611             for(RouteTerminal terminal : getTerminals())
1612                 if(lines1.contains(terminal.line))
1613                     terminals1.add(terminal);
1614                 else if(lines2.contains(terminal.line))
1615                     terminals2.add(terminal);        
1616         }
1617         
1618         return new SplittedRouteGraph(splitLine, 
1619                 interfaceNodes1, lines1, terminals1, 
1620                 interfaceNodes2, lines2, terminals2);
1621     }
1622
1623     private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1624             THashSet<RouteLine> lines) {
1625         if(lines.add(line)) {
1626             for(RoutePoint rp : line.getPoints()) {
1627                 if(rp != previousPoint && rp instanceof RouteLink) {
1628                     RouteLink link = (RouteLink)rp;
1629                     RouteLine otherLine = line != link.getA() 
1630                             ? link.getA() : link.getB();
1631                     if(otherLine.isTransient())
1632                         continue;
1633                     traverseGraph(rp, otherLine, lines);
1634                 }
1635             }
1636         }
1637     }
1638     
1639     public void reclaimTransientMemory() {
1640         removeTransientRouteLines();
1641         needsUpdate = true;
1642     }
1643
1644 }