/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.collections.ints;

import java.util.*;

/**
 * Sorted set is a collection with no duplicate elements. Primitive sets have
 * some features not found in object sets. A primitive set is
 * associated with a <em>domain</em> with boundaries defined by {@link #min()}
 * and {@link #max()}. All numbers contained within this set must fit
 * between min and max, inclusive. Attempt to add a number from outside the
 * domain will have no effect.
 *
 * <p>
 * It is possible to obtain a complement view of a
 * primitive set, using {@link #complementSet()}. The complement view contains
 * all numbers between min and max, inclusive, which are not contained in
 * this set. (In other words, complement view never contains numbers from
 * outside of the domain of this set).
 *
 * <p>
 * Contrary to standard Java collections, intervals in this primitive collection
 * package are <em>inclusive</em> on both sides. In other words, interval
 * [min, max] contains all numbers c such that min <= c <= max. (Otherwise,
 * MAX_VALUE could not be put in the set).
 *
 * <p>
 * It is possible to obtain a subset view of a sorted set, using one of
 * the methods {@link #subSet()}, {@link #headSet()}, and {@link #tailSet()}.
 * The subset view narrows the domain, and its size is thus never bigger than
 * that of this set.
 *
 * <p>
 * Sorted sets define a family of navigation methods, analogous to that
 * found in {@link edu.emory.mathcs.backport.java.util.NavigableSet}.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public interface IntSortedSet extends IntSet {

    /**
     * A subset view containing all elements from this set between first,
     * inclusive, and last, inclusive. More precisely, the view is narrowed to
     * the domain [min, max]. Hence, complement set of this set will NOT
     * include any elements outside [min, max].
     *
     * @param first the minimum element of this view (inclusive).
     * @param last the maximum element of this view (inclusive).
     * @return the subset view
     */
    IntSortedSet subSet(int first, int last);

    /**
     * A subset view containing all elements from this set that are not greater
     * than last. More precisely, the view is narrowed to
     * the domain [MIN_VALUE, max]. Hence, complement set of this set will NOT
     * include any elements > max.
     *
     * @param last the maximum element of this view (inclusive).
     * @return the headset view
     */
    IntSortedSet headSet(int last);

    /**
     * A subset view containing all elements from this set that are not smaller
     * than first. More precisely, the view is narrowed to
     * the domain [min, MAX_VALUE]. Hence, complement set of this set will NOT
     * include any elements < min.
     *
     * @param first the minimum element of this view (inclusive).
     * @return the tailset view
     */
    IntSortedSet tailSet(int first);

    /**
     * Returns the smallest number in this set.
     *
     * @return the smallest number in this set.
     * @throws NoSuchElementException if the set is empty.
     */
    int first();

    /**
     * Returns the largest number in this set.
     *
     * @return the largest number in this set.
     * @throws NoSuchElementException if the set is empty.
     */
    int last();

    /**
     * Returns the smallest number in this set >= e.
     *
     * @return the smallest number in this set >= e.
     * @throws NoSuchElementException if all elements are < e.
     */
    int ceiling(int e);

    /**
     * Returns the smallest number in this set > e.
     *
     * @return the smallest number in this set > e.
     * @throws NoSuchElementException if all elements are <= e.
     */
    int higher(int e);

    /**
     * Returns the largest number in this set <= e.
     *
     * @return the largest number in this set <= e.
     * @throws NoSuchElementException if all elements are > e.
     */
    int floor(int e);

    /**
     * Returns the largest number in this set < e.
     *
     * @return the largest number in this set < e.
     * @throws NoSuchElementException if all elements are >= e.
     */
    int lower(int e);

    /**
     * Returns and removes the smallest number in this set.
     *
     * @return the smallest number in this set.
     * @throws NoSuchElementException if the set is empty.
     */
    int pollFirst();

    /**
     * Returns and removes the largest number in this set.
     *
     * @return the smallest number in this set.
     * @throws NoSuchElementException if the set is empty.
     */
    int pollLast();

    /**
     * Returns the minimum count of intervals into which this set can be
     * decomposed. For instance, {1, 3,4,5, 8,9}.intervalCount() == 3.
     *
     * @return int the interval count of this set.
     */
    int intervalCount();

    /**
     * Returns an iterator over intervals of this set, in an increasing
     * numerical order.
     *
     * @return an iterator over intervals of this set
     */
    Iterator intervalIterator();

    /**
     * Returns an iterator over intervals of this set, in a decreasing
     * numerical order.
     *
     * @return a descending iterator over intervals of this set
     */
    Iterator descendingIntervalIterator();

    /**
     * Returns an iterator over numbers in this set, in an increasing
     * numerical order.
     *
     * @return an iterator over numbers in this set
     */
    IntIterator iterator();

    /**
     * Returns an iterator over numbers in this set, in a decreasing
     * numerical order.
     *
     * @return a descending iterator over numbers in this set
     */
    IntIterator descendingIterator();

    /**
     * Returns the first (left-most), widest interval contained in this set,
     * or null if this set is empty.
     * @return the first interval contained in this set
     */
    IntInterval firstInterval();

    /**
     * Returns the last (right-most), widest interval contained in this set,
     * or null if this set is empty.
     * @return the last interval contained in this set
     */
    IntInterval lastInterval();

    /**
     * Returns the widest interval contained in this set that includes the
     * specified number, or null if this set does not include the specified
     * number.
     *
     * @return the interval containing the specified number.
     */
    IntInterval enclosingInterval(int e);

    /**
     * Returns the largest and widest interval contained in this set which
     * all elements are strictly less than the specified number.
     *
     * @return the largest interval smaller than the specified number.
     */
    IntInterval lowerInterval(int e);

    /**
     * Returns the smallest (left-most), widest interval contained in this set
     * which all elements are strictly greater than the specified number.
     *
     * @return the smallest interval greater than the specified number.
     */
    IntInterval higherInterval(int e);

    /**
     * Returns the largest (right-most), widest interval contained in this set
     * which elements are not all greater than the specified number. In other
     * words, it either includes the specified number or has all elements
     * strictly less than the specified number.
     *
     * @return the largest interval which lower bound is <= than the specified
     *         number.
     */
    IntInterval floorInterval(int e);

    /**
     * Returns the smallest (left-most), widest interval contained in this set
     * which elements are not all smaller than the specified number. In other
     * words, it either includes the specified number or has all elements
     * strictly greater than the specified number.
     *
     * @return the smallest interval which upper bound is >= than the specified
     *         number.
     */
    IntInterval ceilingInterval(int e);

    /**
     * Returns and removes the first (left-most), widest interval contained in
     * this set, or null if this set is empty.
     * @return the first interval contained in this set
     */
    IntInterval pollFirstInterval();

    /**
     * Returns and removes the last (right-most), widest interval contained in
     * this set, or null if this set is empty.
     * @return the last interval contained in this set
     */
    IntInterval pollLastInterval();

    String toString();

    /**
     * Returns the interval-string representation of this set (suitable for
     * representing sets that are possibly large but clustered).
     * @return String
     */
    String toCompactString();
}
