1 /* 2 * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.java2d; 27 28 import java.util.Comparator; 29 import java.util.Collections; 30 import java.util.Iterator; 31 import java.util.List; 32 import java.util.Vector; 33 34 /** 35 * Maintains a list of half-open intervals, called Spans. 36 * A Span can be tested against the list of Spans 37 * for intersection. 38 */ 39 public class Spans { 40 41 /** 42 * This class will sort and collapse its span 43 * entries after this many span additions via 44 * the <code>add</code> method. 45 */ 46 private static final int kMaxAddsSinceSort = 256; 47 48 /** 49 * Holds a list of individual 50 * Span instances. 51 */ 52 private List<Span> mSpans = new Vector<>(kMaxAddsSinceSort); 53 54 /** 55 * The number of <code>Span</code> 56 * instances that have been added 57 * to this object without a sort 58 * and collapse taking place. 59 */ 60 private int mAddsSinceSort = 0; 61 62 public Spans() { 63 64 } 65 66 /** 67 * Add a span covering the half open interval 68 * including <code>start</code> up to 69 * but not including <code>end</code>. 70 */ 71 public void add(float start, float end) { 72 73 if (mSpans != null) { 74 mSpans.add(new Span(start, end)); 75 76 if (++mAddsSinceSort >= kMaxAddsSinceSort) { 77 sortAndCollapse(); 78 } 79 } 80 } 81 82 /** 83 * Add a span which covers the entire range. 84 * This call is logically equivalent to 85 * <code>add(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY)</code> 86 * The result of making this call is that 87 * all future <code>add</code> calls are ignored 88 * and the <code>intersects</code> method always 89 * returns true. 90 */ 91 public void addInfinite() { 92 mSpans = null; 93 } 94 95 /** 96 * Returns true if the span defined by the half-open 97 * interval from <code>start</code> up to, 98 * but not including, <code>end</code> intersects 99 * any of the spans defined by this instance. 100 */ 101 public boolean intersects(float start, float end) { 102 boolean doesIntersect; 103 104 if (mSpans != null) { 105 106 /* If we have added any spans since we last 107 * sorted and collapsed our list of spans 108 * then we need to resort and collapse. 109 */ 110 if (mAddsSinceSort > 0) { 111 sortAndCollapse(); 112 } 113 114 /* The SpanIntersection comparator considers 115 * two spans equal if they intersect. If 116 * the search finds a match then we have an 117 * intersection. 118 */ 119 int found = Collections.binarySearch(mSpans, 120 new Span(start, end), 121 SpanIntersection.instance); 122 123 doesIntersect = found >= 0; 124 125 /* The addInfinite() method has been invoked so 126 * everything intersect this instance. 127 */ 128 } else { 129 doesIntersect = true; 130 } 131 132 return doesIntersect; 133 } 134 135 /** 136 * Sort the spans in ascending order by their 137 * start position. After the spans are sorted 138 * collapse any spans that intersect into a 139 * single span. The result is a sorted, 140 * non-overlapping list of spans. 141 */ 142 private void sortAndCollapse() { 143 144 Collections.sort(mSpans); 145 mAddsSinceSort = 0; 146 147 Iterator<Span> iter = mSpans.iterator(); 148 149 /* Have 'span' start at the first span in 150 * the collection. The collection may be empty 151 * so we're careful. 152 */ 153 Span span = null; 154 if (iter.hasNext()) { 155 span = iter.next(); 156 } 157 158 /* Loop over the spans collapsing those that intersect 159 * into a single span. 160 */ 161 while (iter.hasNext()) { 162 163 Span nextSpan = iter.next(); 164 165 /* The spans are in ascending start position 166 * order and so the next span's starting point 167 * is either in the span we are trying to grow 168 * or it is beyond the first span and thus the 169 * two spans do not intersect. 170 * 171 * span: <----------< 172 * nextSpan: <------ (intersects) 173 * nextSpan: <------ (doesn't intersect) 174 * 175 * If the spans intersect then we'll remove 176 * nextSpan from the list. If nextSpan's 177 * ending was beyond the first's then 178 * we extend the first. 179 * 180 * span: <----------< 181 * nextSpan: <-----< (don't change span) 182 * nextSpan: <-----------< (grow span) 183 */ 184 185 if (span.subsume(nextSpan)) { 186 iter.remove(); 187 188 /* The next span did not intersect the current 189 * span and so it can not be collapsed. Instead 190 * it becomes the start of the next set of spans 191 * to be collapsed. 192 */ 193 } else { 194 span = nextSpan; 195 } 196 } 197 } 198 199 /* 200 // For debugging. 201 202 private void printSpans() { 203 System.out.println("----------"); 204 if (mSpans != null) { 205 Iterator<Span> iter = mSpans.iterator(); 206 while (iter.hasNext()) { 207 Span span = iter.next(); 208 System.out.println(span); 209 } 210 } 211 System.out.println("----------"); 212 213 } 214 */ 215 216 /** 217 * Holds a single half-open interval. 218 */ 219 static class Span implements Comparable<Span> { 220 221 /** 222 * The span includes the starting point. 223 */ 224 private float mStart; 225 226 /** 227 * The span goes up to but does not include 228 * the ending point. 229 */ 230 private float mEnd; 231 232 /** 233 * Create a half-open interval including 234 * <code>start</code> but not including 235 * <code>end</code>. 236 */ 237 Span(float start, float end) { 238 mStart = start; 239 mEnd = end; 240 } 241 242 /** 243 * Return the start of the <code>Span</code>. 244 * The start is considered part of the 245 * half-open interval. 246 */ 247 final float getStart() { 248 return mStart; 249 } 250 251 /** 252 * Return the end of the <code>Span</code>. 253 * The end is not considered part of the 254 * half-open interval. 255 */ 256 final float getEnd() { 257 return mEnd; 258 } 259 260 /** 261 * Change the initial position of the 262 * <code>Span</code>. 263 */ 264 final void setStart(float start) { 265 mStart = start; 266 } 267 268 /** 269 * Change the terminal position of the 270 * <code>Span</code>. 271 */ 272 final void setEnd(float end) { 273 mEnd = end; 274 } 275 276 /** 277 * Attempt to alter this <code>Span</code> 278 * to include <code>otherSpan</code> without 279 * altering this span's starting position. 280 * If <code>otherSpan</code> can be so consumed 281 * by this <code>Span</code> then <code>true</code> 282 * is returned. 283 */ 284 boolean subsume(Span otherSpan) { 285 286 /* We can only subsume 'otherSpan' if 287 * its starting position lies in our 288 * interval. 289 */ 290 boolean isSubsumed = contains(otherSpan.mStart); 291 292 /* If the other span's starting position 293 * was in our interval and the other span 294 * was longer than this span, then we need 295 * to grow this span to cover the difference. 296 */ 297 if (isSubsumed && otherSpan.mEnd > mEnd) { 298 mEnd = otherSpan.mEnd; 299 } 300 301 return isSubsumed; 302 } 303 304 /** 305 * Return true if the passed in position 306 * lies in the half-open interval defined 307 * by this <code>Span</code>. 308 */ 309 boolean contains(float pos) { 310 return mStart <= pos && pos < mEnd; 311 } 312 313 /** 314 * Rank spans according to their starting 315 * position. The end position is ignored 316 * in this ranking. 317 */ 318 public int compareTo(Span otherSpan) { 319 float otherStart = otherSpan.getStart(); 320 int result; 321 322 if (mStart < otherStart) { 323 result = -1; 324 } else if (mStart > otherStart) { 325 result = 1; 326 } else { 327 result = 0; 328 } 329 330 return result; 331 } 332 333 public String toString() { 334 return "Span: " + mStart + " to " + mEnd; 335 } 336 337 } 338 339 /** 340 * This class ranks a pair of <code>Span</code> 341 * instances. If the instances intersect they 342 * are deemed equal otherwise they are ranked 343 * by their relative position. Use 344 * <code>SpanIntersection.instance</code> to 345 * get the single instance of this class. 346 */ 347 static class SpanIntersection implements Comparator<Span> { 348 349 /** 350 * This class is a Singleton and the following 351 * is the single instance. 352 */ 353 static final SpanIntersection instance = 354 new SpanIntersection(); 355 356 /** 357 * Only this class can create instances of itself. 358 */ 359 private SpanIntersection() { 360 361 } 362 363 public int compare(Span span1, Span span2) { 364 int result; 365 366 /* Span 1 is entirely to the left of span2. 367 * span1: <-----< 368 * span2: <-----< 369 */ 370 if (span1.getEnd() <= span2.getStart()) { 371 result = -1; 372 373 /* Span 2 is entirely to the right of span2. 374 * span1: <-----< 375 * span2: <-----< 376 */ 377 } else if (span1.getStart() >= span2.getEnd()) { 378 result = 1; 379 380 /* Otherwise they intersect and we declare them equal. 381 */ 382 } else { 383 result = 0; 384 } 385 386 return result; 387 } 388 389 } 390 }