Back to index...

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

	}
	}

Back to index...