bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/RouteGraph.java

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