View Javadoc
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 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 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 = (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 = (Span) 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 iter = mSpans.iterator();
206             while (iter.hasNext()) {
207                 Span 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 {
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(Object o) {
319             Span otherSpan = (Span) o;
320             float otherStart = otherSpan.getStart();
321             int result;
322 
323             if (mStart < otherStart) {
324                 result = -1;
325             } else if (mStart > otherStart) {
326                 result = 1;
327             } else {
328                 result = 0;
329             }
330 
331             return result;
332         }
333 
334         public String toString() {
335             return "Span: " + mStart + " to " + mEnd;
336         }
337 
338     }
339 
340     /**
341      * This class ranks a pair of <code>Span</code>
342      * instances. If the instances intersect they
343      * are deemed equal otherwise they are ranked
344      * by their relative position. Use
345      * <code>SpanIntersection.instance</code> to
346      * get the single instance of this class.
347      */
348     static class SpanIntersection implements Comparator {
349 
350         /**
351          * This class is a Singleton and the following
352          * is the single instance.
353          */
354         static final SpanIntersection instance =
355                                       new SpanIntersection();
356 
357         /**
358          * Only this class can create instances of itself.
359          */
360         private SpanIntersection() {
361 
362         }
363 
364         public int compare(Object o1, Object o2) {
365             int result;
366             Span span1 = (Span) o1;
367             Span span2 = (Span) o2;
368 
369             /* Span 1 is entirely to the left of span2.
370              * span1:   <-----<
371              * span2:            <-----<
372              */
373             if (span1.getEnd() <= span2.getStart()) {
374                 result = -1;
375 
376             /* Span 2 is entirely to the right of span2.
377              * span1:                     <-----<
378              * span2:            <-----<
379              */
380             } else if (span1.getStart() >= span2.getEnd()) {
381                 result = 1;
382 
383             /* Otherwise they intersect and we declare them equal.
384             */
385             } else {
386                 result = 0;
387             }
388 
389             return result;
390         }
391 
392     }
393 }