/*
* 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.
*/
public class Spans {
/**
* This class will sort and collapse its span
* entries after this many span additions via
* the <code>add</code> method.
*/
private static final int kMaxAddsSinceSort = 256;
/**
* Holds a list of individual
* Span instances.
*/
private List mSpans = new Vector(kMaxAddsSinceSort);
/**
* The number of <code>Span</code>
* 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 <code>start</code> up to
* but not including <code>end</code>.
*/
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
* <code>add(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY)</code>
* The result of making this call is that
* all future <code>add</code> calls are ignored
* and the <code>intersects</code> method always
* returns true.
*/
public void addInfinite() {
mSpans = null;
}
/**
* Returns true if the span defined by the half-open
* interval from <code>start</code> up to,
* but not including, <code>end</code> 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.
*/
private void sortAndCollapse() {
Collections.sort(mSpans);
mAddsSinceSort = 0;
Iterator 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 = (Span) iter.next();
}
/* Loop over the spans collapsing those that intersect
* into a single span.
*/
while (iter.hasNext()) {
Span nextSpan = (Span) 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 iter = mSpans.iterator();
while (iter.hasNext()) {
Span span = (Span) iter.next();
System.out.println(span);
}
}
System.out.println("----------");
}
*/
/**
* Holds a single half-open interval.
*/
static class Span implements Comparable {
/**
* The span includes the starting point.
*/
private float mStart;
/**
* The span goes up to but does not include
* the ending point.
*/
private float mEnd;
/**
* Create a half-open interval including
* <code>start</code> but not including
* <code>end</code>.
*/
Span(float start, float end) {
mStart = start;
mEnd = end;
}
/**
* Return the start of the <code>Span</code>.
* The start is considered part of the
* half-open interval.
*/
final float getStart() {
return mStart;
}
/**
* Return the end of the <code>Span</code>.
* The end is not considered part of the
* half-open interval.
*/
final float getEnd() {
return mEnd;
}
/**
* Change the initial position of the
* <code>Span</code>.
*/
final void setStart(float start) {
mStart = start;
}
/**
* Change the terminal position of the
* <code>Span</code>.
*/
final void setEnd(float end) {
mEnd = end;
}
/**
* Attempt to alter this <code>Span</code>
* to include <code>otherSpan</code> without
* altering this span's starting position.
* If <code>otherSpan</code> can be so consumed
* by this <code>Span</code> then <code>true</code>
* 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 <code>Span</code>.
*/
boolean contains(float pos) {
return mStart <= pos && pos < mEnd;
}
/**
* Rank spans according to their starting
* position. The end position is ignored
* in this ranking.
*/
public int compareTo(Object o) {
Span otherSpan = (Span) o;
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 <code>Span</code>
* instances. If the instances intersect they
* are deemed equal otherwise they are ranked
* by their relative position. Use
* <code>SpanIntersection.instance</code> to
* get the single instance of this class.
*/
static class SpanIntersection implements Comparator {
/**
* 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.
*/
private SpanIntersection() {
}
public int compare(Object o1, Object o2) {
int result;
Span span1 = (Span) o1;
Span span2 = (Span) o2;
/* 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;
}
}
}