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 }