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 }