bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm1/StopSet.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
   3  * in 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.g2d.routing.algorithm1;
  13
  14 import gnu.trove.list.array.TIntArrayList;
  15
  16 import java.util.Arrays;
  17 import java.util.Collection;
  18 import java.util.Comparator;
  19
  20 public class StopSet {
  21         public static class Line {
  22                 /**
  23                  * The size of xs is even. The array is strictly ordered.
  24                  * For all n, (xs[2n], xs[2n+1]) is an obstacle.
  25                  */
  26                 double[] xs;
  27                 public double y;
  28
  29                 /* Following tables are indexed by intervals 0..xs.length such that
  30                    interval i is (xs[i-1],xs[i]), where xs[-1] = -INFINITY and
  31                    xs[xs.length] = INFINITY
  32                  */
  33                 /**
  34                  * Penalty of crossing the stop (null, if no penalty)
  35                  */
  36                 public Penalty[] penalty;
  37                 /**
  38                  * Next line of stop with positive penalty
  39                  */
  40                 Line[] nextLine;
  41                 /**
  42                  * Index of the first interval in the nextLine[i]
  43                  * that blocks fronts from this interval.
  44                  */
  45                 int[] nextPosition;
  46
  47                 public Line(double[] xs, double y, Penalty[] penalty, Line[] nextLine, int[] nextPosition) {
  48                         this.xs = xs;
  49                         this.y = y;
  50                         this.penalty = penalty;
  51                         this.nextLine = nextLine;
  52                         this.nextPosition = nextPosition;
  53                 }
  54         }
  55
  56         Line[] lines;
  57
  58         public static class Stop {
  59                 double x0, x1;
  60                 double y;
  61                 Penalty penalty;
  62
  63                 public Stop(Penalty penalty, double x0, double x1, double y) {
  64                         this.penalty = penalty;
  65                         this.x0 = x0;
  66                         this.x1 = x1;
  67                         this.y = y;
  68                 }
  69         }
  70
  71         public static final Comparator<Stop> stopComparator = new Comparator<Stop>() {
  72
  73                 @Override
  74                 public int compare(Stop o1, Stop o2) {
  75                         if(o1.y < o2.y)
  76                                 return -1;
  77                         else if(o1.y > o2.y)
  78                                 return 1;
  79                         else if(o1.x0 < o2.x0)
  80                                 return -1;
  81                         else if(o1.x0 > o2.x0)
  82                                 return 1;
  83                         else
  84                                 return 0;
  85                 }
  86
  87         };
  88
  89         public StopSet(Collection<Stop> _stops) {
  90                 if(_stops.isEmpty())
  91                         return;
  92                 Stop[] stops = _stops.toArray(new Stop[_stops.size()]);
  93                 Arrays.sort(stops, stopComparator);
  94
  95                 TIntArrayList lineBegins = new TIntArrayList();
  96                 lineBegins.add(0);
  97                 for(int i=1;i<stops.length;++i)
  98                         if(stops[i-1].y < stops[i].y)
  99                                 lineBegins.add(i);
 100
 101                 lines = new Line[lineBegins.size()];
 102                 Line prev = null;
 103                 int from = stops.length;
 104                 for(int i=lineBegins.size()-1;i>=0;--i) {
 105                         int to = from;
 106                         from = lineBegins.get(i);
 107
 108                         // Calculate xs and penalty
 109
 110                         double[] xs = new double[(to-from)*2];
 111                         Penalty[] penalty = new Penalty[(to-from)*2+1];
 112                         int pointCount = 0;
 113                         for(int j=from;j<to;++j) {
 114                                 Stop stop = stops[j];
 115                                 if(pointCount == 0 || xs[pointCount-1] < stop.x0) {
 116                                         penalty[pointCount] = null;
 117                                         xs[pointCount++] = stop.x0;
 118                                         penalty[pointCount] = stop.penalty;
 119                                         xs[pointCount++] = stop.x1;
 120                                 }
 121                                 else if(stop.penalty.equals(penalty[pointCount-1])) {
 122                                         if(stop.x1 > xs[pointCount-1])
 123                                                 xs[pointCount-1] = stop.x1;
 124                                 }
 125                                 else {
 126                                         if(stop.x0 == xs[pointCount-1]) {
 127                                                 penalty[pointCount] = stop.penalty;
 128                                                 xs[pointCount++] = stop.x1;
 129                                         }
 130                                         else if(stop.x1 > xs[pointCount-1]) {
 131                                                 if(stop.penalty.penalty > penalty[pointCount-1].penalty) {
 132                                                         if(xs[pointCount-2] == stop.x0)
 133                                                                 --pointCount;
 134                                                         else
 135                                                                 xs[pointCount-1] = stop.x0;
 136                                                 }
 137                                                 penalty[pointCount] = stop.penalty;
 138                                                 xs[pointCount++] = stop.x1;
 139                                         }
 140                                         else if(stop.penalty.penalty > penalty[pointCount-1].penalty) {
 141                                                 // FIXME Not correct if more than two intersecting stops
 142                                         }
 143                                 }
 144                         }
 145                         penalty[pointCount] = null;
 146                         if(pointCount < xs.length) {
 147                                 xs = Arrays.copyOf(xs, pointCount);
 148                                 penalty = Arrays.copyOf(penalty, pointCount+1);
 149                         }
 150
 151                         // Calculate nextLine and nextPosition
 152
 153                         Line[] nextLine = new Line[pointCount + 1];
 154                         int[] nextPosition = new int[pointCount + 1];
 155                         if(prev != null) {
 156                                 int prevI = 0;
 157                                 double[] prevXs = prev.xs;
 158                                 for(int j=0;j<=pointCount;++j) {
 159                                         double min = j==0 ? Double.NEGATIVE_INFINITY : xs[j-1];
 160                                         double max = j==pointCount ? Double.POSITIVE_INFINITY : xs[j];
 161
 162                                         while(prevI < prevXs.length && prevXs[prevI] <= min)
 163                                                 ++prevI;
 164
 165                                         Line prev2 = prev;
 166                                         int prevI2 = prevI;
 167                                         double[] prevXs2 = prevXs;
 168                                         while(prev2.penalty[prevI2]==null && (prevI2==prevXs2.length || prevXs2[prevI2] >= max)) {
 169                                                 int temp = prev2.nextPosition[prevI2];
 170                                                 prev2 = prev2.nextLine[prevI2];
 171                                                 if(prev2 == null)
 172                                                         break;
 173                                                 prevI2 = temp;
 174                                                 prevXs2 = prev2.xs;
 175                                                 while(prevI2 < prevXs2.length && prevXs2[prevI2] <= min)
 176                                                         ++prevI2;
 177                                         }
 178                                         nextLine[j] = prev2;
 179                                         nextPosition[j] = prevI2;
 180                                 }
 181                         }
 182                         lines[i] = prev = new Line(xs, stops[from].y, penalty, nextLine, nextPosition);
 183                 }
 184         }
 185
 186         public static interface IStopProcedure {
 187                 void blockEnd(double y);
 188                 void continuation(double min, double max, int pos, Line line);
 189         }
 190
 191         public void findStops(double min, double max, double y, IStopProcedure proc) {
 192                 if(lines == null) {
 193                         proc.blockEnd(Double.POSITIVE_INFINITY);
 194                         return;
 195                 }
 196                 int minJ = -1;
 197                 int maxJ = lines.length;
 198                 while(maxJ > minJ+1) {
 199                         int middleJ = (minJ+maxJ) >>> 1;
 200                         double middleY = lines[middleJ].y;
 201                         if(middleY < y)
 202                                 minJ = middleJ;
 203                         else if(middleY > y)
 204                                 maxJ = middleJ;
 205                         else {
 206                                 minJ = maxJ = middleJ;
 207                                 break;
 208                         }
 209                 }
 210
 211                 if(maxJ == lines.length)
 212                         proc.blockEnd(Double.POSITIVE_INFINITY);
 213                 else {
 214                         double[] xs = lines[maxJ].xs;
 215                         int minI = -1;
 216                         int maxI = xs.length;
 217                         while(maxI > minI+1) {
 218                                 int middleI = (minI+maxI) >>> 1;
 219                                 double middleX = xs[middleI];
 220                                 if(middleX < min)
 221                                         minI = middleI;
 222                                 else if(middleX > min)
 223                                         maxI = middleI;
 224                                 else {
 225                                         minI = maxI = middleI;
 226                                 }
 227                         }
 228                         findStops(maxI, lines[maxJ], min, max, y, proc);
 229                 }
 230
 231         }
 232
 233         static private void findStops(int pos, Line line, double min, double max, double y, IStopProcedure proc) {
 234                 double[] xs = line.xs;
 235                 while(line.penalty[pos]==null && (pos==xs.length || xs[pos] >= max)) {
 236                         int temp = line.nextPosition[pos];
 237                         line = line.nextLine[pos];
 238                         if(line == null)
 239                                 break;
 240                         xs = line.xs;
 241                         pos = temp;
 242                         while(pos < xs.length && xs[pos] <= min)
 243                                 ++pos;
 244                 }
 245                 if(line == null)
 246                         proc.blockEnd(Double.POSITIVE_INFINITY);
 247                 else {
 248                         if(line.y > y)
 249                                 proc.blockEnd(line.y);
 250                         if(pos==xs.length || xs[pos] >= max)
 251                                 proc.continuation(min, max, pos, line);
 252                         else {
 253                                 proc.continuation(min, xs[pos], pos, line);
 254                                 while(pos+1 < xs.length && xs[pos+1] < max) {
 255                                         ++pos;
 256                                         proc.continuation(xs[pos-1], xs[pos], pos, line);
 257                                 }
 258                                 proc.continuation(xs[pos], max, pos+1, line);
 259                         }
 260                 }
 261         }
 262
 263         static public void continueStop(final int pos, final Line line, double min, double max, IStopProcedure proc) {
 264                 Line newLine = line.nextLine[pos];
 265                 if(newLine == null)
 266                         proc.blockEnd(Double.POSITIVE_INFINITY);
 267                 else {
 268                         int newPos = line.nextPosition[pos];
 269                         double[] xs = newLine.xs;
 270                         while(newPos < xs.length && xs[newPos] <= min)
 271                                 ++newPos;
 272                         findStops(newPos, newLine, min, max, line.y, proc);
 273                 }
 274         }
 275
 276 }