/*
 * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.java2d;

import java.util.Comparator;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;

Maintains a list of half-open intervals, called Spans. A Span can be tested against the list of Spans for intersection.
/** * Maintains a list of half-open intervals, called Spans. * A Span can be tested against the list of Spans * for intersection. */
public class Spans {
This class will sort and collapse its span entries after this many span additions via the add method.
/** * This class will sort and collapse its span * entries after this many span additions via * the {@code add} method. */
private static final int kMaxAddsSinceSort = 256;
Holds a list of individual Span instances.
/** * Holds a list of individual * Span instances. */
private List<Span> mSpans = new Vector<>(kMaxAddsSinceSort);
The number of Span instances that have been added to this object without a sort and collapse taking place.
/** * The number of {@code Span} * instances that have been added * to this object without a sort * and collapse taking place. */
private int mAddsSinceSort = 0; public Spans() { }
Add a span covering the half open interval including start up to but not including end.
/** * Add a span covering the half open interval * including {@code start} up to * but not including {@code end}. */
public void add(float start, float end) { if (mSpans != null) { mSpans.add(new Span(start, end)); if (++mAddsSinceSort >= kMaxAddsSinceSort) { sortAndCollapse(); } } }
Add a span which covers the entire range. This call is logically equivalent to add(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY) The result of making this call is that all future add calls are ignored and the intersects method always returns true.
/** * Add a span which covers the entire range. * This call is logically equivalent to * {@code add(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY)} * The result of making this call is that * all future {@code add} calls are ignored * and the {@code intersects} method always * returns true. */
public void addInfinite() { mSpans = null; }
Returns true if the span defined by the half-open interval from start up to, but not including, end intersects any of the spans defined by this instance.
/** * Returns true if the span defined by the half-open * interval from {@code start} up to, * but not including, {@code end} intersects * any of the spans defined by this instance. */
public boolean intersects(float start, float end) { boolean doesIntersect; if (mSpans != null) { /* If we have added any spans since we last * sorted and collapsed our list of spans * then we need to resort and collapse. */ if (mAddsSinceSort > 0) { sortAndCollapse(); } /* The SpanIntersection comparator considers * two spans equal if they intersect. If * the search finds a match then we have an * intersection. */ int found = Collections.binarySearch(mSpans, new Span(start, end), SpanIntersection.instance); doesIntersect = found >= 0; /* The addInfinite() method has been invoked so * everything intersect this instance. */ } else { doesIntersect = true; } return doesIntersect; }
Sort the spans in ascending order by their start position. After the spans are sorted collapse any spans that intersect into a single span. The result is a sorted, non-overlapping list of spans.
/** * Sort the spans in ascending order by their * start position. After the spans are sorted * collapse any spans that intersect into a * single span. The result is a sorted, * non-overlapping list of spans. */
private void sortAndCollapse() { Collections.sort(mSpans); mAddsSinceSort = 0; Iterator<Span> iter = mSpans.iterator(); /* Have 'span' start at the first span in * the collection. The collection may be empty * so we're careful. */ Span span = null; if (iter.hasNext()) { span = iter.next(); } /* Loop over the spans collapsing those that intersect * into a single span. */ while (iter.hasNext()) { Span nextSpan = iter.next(); /* The spans are in ascending start position * order and so the next span's starting point * is either in the span we are trying to grow * or it is beyond the first span and thus the * two spans do not intersect. * * span: <----------< * nextSpan: <------ (intersects) * nextSpan: <------ (doesn't intersect) * * If the spans intersect then we'll remove * nextSpan from the list. If nextSpan's * ending was beyond the first's then * we extend the first. * * span: <----------< * nextSpan: <-----< (don't change span) * nextSpan: <-----------< (grow span) */ if (span.subsume(nextSpan)) { iter.remove(); /* The next span did not intersect the current * span and so it can not be collapsed. Instead * it becomes the start of the next set of spans * to be collapsed. */ } else { span = nextSpan; } } } /* // For debugging. private void printSpans() { System.out.println("----------"); if (mSpans != null) { Iterator<Span> iter = mSpans.iterator(); while (iter.hasNext()) { Span span = iter.next(); System.out.println(span); } } System.out.println("----------"); } */
Holds a single half-open interval.
/** * Holds a single half-open interval. */
static class Span implements Comparable<Span> {
The span includes the starting point.
/** * The span includes the starting point. */
private float mStart;
The span goes up to but does not include the ending point.
/** * The span goes up to but does not include * the ending point. */
private float mEnd;
Create a half-open interval including start but not including end.
/** * Create a half-open interval including * {@code start} but not including * {@code end}. */
Span(float start, float end) { mStart = start; mEnd = end; }
Return the start of the Span. The start is considered part of the half-open interval.
/** * Return the start of the {@code Span}. * The start is considered part of the * half-open interval. */
final float getStart() { return mStart; }
Return the end of the Span. The end is not considered part of the half-open interval.
/** * Return the end of the {@code Span}. * The end is not considered part of the * half-open interval. */
final float getEnd() { return mEnd; }
Change the initial position of the Span.
/** * Change the initial position of the * {@code Span}. */
final void setStart(float start) { mStart = start; }
Change the terminal position of the Span.
/** * Change the terminal position of the * {@code Span}. */
final void setEnd(float end) { mEnd = end; }
Attempt to alter this Span to include otherSpan without altering this span's starting position. If otherSpan can be so consumed by this Span then true is returned.
/** * Attempt to alter this {@code Span} * to include {@code otherSpan} without * altering this span's starting position. * If {@code otherSpan} can be so consumed * by this {@code Span} then {@code true} * is returned. */
boolean subsume(Span otherSpan) { /* We can only subsume 'otherSpan' if * its starting position lies in our * interval. */ boolean isSubsumed = contains(otherSpan.mStart); /* If the other span's starting position * was in our interval and the other span * was longer than this span, then we need * to grow this span to cover the difference. */ if (isSubsumed && otherSpan.mEnd > mEnd) { mEnd = otherSpan.mEnd; } return isSubsumed; }
Return true if the passed in position lies in the half-open interval defined by this Span.
/** * Return true if the passed in position * lies in the half-open interval defined * by this {@code Span}. */
boolean contains(float pos) { return mStart <= pos && pos < mEnd; }
Rank spans according to their starting position. The end position is ignored in this ranking.
/** * Rank spans according to their starting * position. The end position is ignored * in this ranking. */
public int compareTo(Span otherSpan) { float otherStart = otherSpan.getStart(); int result; if (mStart < otherStart) { result = -1; } else if (mStart > otherStart) { result = 1; } else { result = 0; } return result; } public String toString() { return "Span: " + mStart + " to " + mEnd; } }
This class ranks a pair of Span instances. If the instances intersect they are deemed equal otherwise they are ranked by their relative position. Use SpanIntersection.instance to get the single instance of this class.
/** * This class ranks a pair of {@code Span} * instances. If the instances intersect they * are deemed equal otherwise they are ranked * by their relative position. Use * {@code SpanIntersection.instance} to * get the single instance of this class. */
static class SpanIntersection implements Comparator<Span> {
This class is a Singleton and the following is the single instance.
/** * This class is a Singleton and the following * is the single instance. */
static final SpanIntersection instance = new SpanIntersection();
Only this class can create instances of itself.
/** * Only this class can create instances of itself. */
private SpanIntersection() { } public int compare(Span span1, Span span2) { int result; /* Span 1 is entirely to the left of span2. * span1: <-----< * span2: <-----< */ if (span1.getEnd() <= span2.getStart()) { result = -1; /* Span 2 is entirely to the right of span2. * span1: <-----< * span2: <-----< */ } else if (span1.getStart() >= span2.getEnd()) { result = 1; /* Otherwise they intersect and we declare them equal. */ } else { result = 0; } return result; } } }