Java example source code file (Spans.java)

This example Java source code file (Spans.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

comparable, comparator, iterator, list, object, span, spanintersection, spans, string, util, vector

The Spans.java Java example source code

/*
 * 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 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
     * 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 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
     * <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 <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.
     */
    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 but not including
         * <code>end.
         */
        Span(float start, float end) {
            mStart = start;
            mEnd = end;
        }

        /**
         * 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 <code>Span.
         * The end is not considered part of the
         * half-open interval.
         */
        final float getEnd() {
            return mEnd;
        }

        /**
         * Change the initial position of the
         * <code>Span.
         */
        final void setStart(float start) {
            mStart = start;
        }

        /**
         * Change the terminal position of the
         * <code>Span.
         */
        final void setEnd(float end) {
            mEnd = end;
        }

        /**
         * 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 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 <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.
         */
        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
     * 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 {

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

    }
}