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