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