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 }