Spans.java

/*
 * 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<Span> 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<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.
     */
    static class Span implements Comparable<Span> {

        /**
         * 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 {@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 {@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(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 {@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.
         */
        static final SpanIntersection instance =
                                      new SpanIntersection();

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

    }
}