1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
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
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.g2d.routing.algorithm1;
14 import gnu.trove.list.array.TIntArrayList;
16 import java.util.Arrays;
17 import java.util.Collection;
18 import java.util.Comparator;
20 public class StopSet {
21 public static class Line {
23 * The size of xs is even. The array is strictly ordered.
24 * For all n, (xs[2n], xs[2n+1]) is an obstacle.
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
34 * Penalty of crossing the stop (null, if no penalty)
36 public Penalty[] penalty;
38 * Next line of stop with positive penalty
42 * Index of the first interval in the nextLine[i]
43 * that blocks fronts from this interval.
47 public Line(double[] xs, double y, Penalty[] penalty, Line[] nextLine, int[] nextPosition) {
50 this.penalty = penalty;
51 this.nextLine = nextLine;
52 this.nextPosition = nextPosition;
58 public static class Stop {
63 public Stop(Penalty penalty, double x0, double x1, double y) {
64 this.penalty = penalty;
71 public static final Comparator<Stop> stopComparator = new Comparator<Stop>() {
74 public int compare(Stop o1, Stop o2) {
79 else if(o1.x0 < o2.x0)
81 else if(o1.x0 > o2.x0)
89 public StopSet(Collection<Stop> _stops) {
92 Stop[] stops = _stops.toArray(new Stop[_stops.size()]);
93 Arrays.sort(stops, stopComparator);
95 TIntArrayList lineBegins = new TIntArrayList();
97 for(int i=1;i<stops.length;++i)
98 if(stops[i-1].y < stops[i].y)
101 lines = new Line[lineBegins.size()];
103 int from = stops.length;
104 for(int i=lineBegins.size()-1;i>=0;--i) {
106 from = lineBegins.get(i);
108 // Calculate xs and penalty
110 double[] xs = new double[(to-from)*2];
111 Penalty[] penalty = new Penalty[(to-from)*2+1];
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;
121 else if(stop.penalty.equals(penalty[pointCount-1])) {
122 if(stop.x1 > xs[pointCount-1])
123 xs[pointCount-1] = stop.x1;
126 if(stop.x0 == xs[pointCount-1]) {
127 penalty[pointCount] = stop.penalty;
128 xs[pointCount++] = stop.x1;
130 else if(stop.x1 > xs[pointCount-1]) {
131 if(stop.penalty.penalty > penalty[pointCount-1].penalty) {
132 if(xs[pointCount-2] == stop.x0)
135 xs[pointCount-1] = stop.x0;
137 penalty[pointCount] = stop.penalty;
138 xs[pointCount++] = stop.x1;
140 else if(stop.penalty.penalty > penalty[pointCount-1].penalty) {
141 // FIXME Not correct if more than two intersecting stops
145 penalty[pointCount] = null;
146 if(pointCount < xs.length) {
147 xs = Arrays.copyOf(xs, pointCount);
148 penalty = Arrays.copyOf(penalty, pointCount+1);
151 // Calculate nextLine and nextPosition
153 Line[] nextLine = new Line[pointCount + 1];
154 int[] nextPosition = new int[pointCount + 1];
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];
162 while(prevI < prevXs.length && prevXs[prevI] <= min)
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];
175 while(prevI2 < prevXs2.length && prevXs2[prevI2] <= min)
179 nextPosition[j] = prevI2;
182 lines[i] = prev = new Line(xs, stops[from].y, penalty, nextLine, nextPosition);
186 public static interface IStopProcedure {
187 void blockEnd(double y);
188 void continuation(double min, double max, int pos, Line line);
191 public void findStops(double min, double max, double y, IStopProcedure proc) {
193 proc.blockEnd(Double.POSITIVE_INFINITY);
197 int maxJ = lines.length;
198 while(maxJ > minJ+1) {
199 int middleJ = (minJ+maxJ) >>> 1;
200 double middleY = lines[middleJ].y;
206 minJ = maxJ = middleJ;
211 if(maxJ == lines.length)
212 proc.blockEnd(Double.POSITIVE_INFINITY);
214 double[] xs = lines[maxJ].xs;
216 int maxI = xs.length;
217 while(maxI > minI+1) {
218 int middleI = (minI+maxI) >>> 1;
219 double middleX = xs[middleI];
222 else if(middleX > min)
225 minI = maxI = middleI;
228 findStops(maxI, lines[maxJ], min, max, y, proc);
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];
242 while(pos < xs.length && xs[pos] <= min)
246 proc.blockEnd(Double.POSITIVE_INFINITY);
249 proc.blockEnd(line.y);
250 if(pos==xs.length || xs[pos] >= max)
251 proc.continuation(min, max, pos, line);
253 proc.continuation(min, xs[pos], pos, line);
254 while(pos+1 < xs.length && xs[pos+1] < max) {
256 proc.continuation(xs[pos-1], xs[pos], pos, line);
258 proc.continuation(xs[pos], max, pos+1, line);
263 static public void continueStop(final int pos, final Line line, double min, double max, IStopProcedure proc) {
264 Line newLine = line.nextLine[pos];
266 proc.blockEnd(Double.POSITIVE_INFINITY);
268 int newPos = line.nextPosition[pos];
269 double[] xs = newLine.xs;
270 while(newPos < xs.length && xs[newPos] <= min)
272 findStops(newPos, newLine, min, max, line.y, proc);