/* * 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; } }}
/*
* 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;
}
}
}