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