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
26package sun.java2d;
27
28import java.util.Comparator;
29import java.util.Collections;
30import java.util.Iterator;
31import java.util.List;
32import 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 */
39public 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} 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}
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} up to
69     * but not including {@code end}.
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)}
86     * The result of making this call is that
87     * all future {@code add} calls are ignored
88     * and the {@code intersects} 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} up to,
98     * but not including, {@code end} 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} but not including
235         * {@code end}.
236         */
237        Span(float start, float end) {
238            mStart = start;
239            mEnd = end;
240        }
241
242        /**
243         * Return the start of the {@code Span}.
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}.
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}.
263         */
264        final void setStart(float start) {
265            mStart = start;
266        }
267
268        /**
269         * Change the terminal position of the
270         * {@code Span}.
271         */
272        final void setEnd(float end) {
273            mEnd = end;
274        }
275
276        /**
277         * Attempt to alter this {@code Span}
278         * to include {@code otherSpan} without
279         * altering this span's starting position.
280         * If {@code otherSpan} can be so consumed
281         * by this {@code Span} then {@code true}
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}.
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}
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} 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}
391