/*
 * Copyright (C) 2020 MicroEJ Corp. - EDC compliance and optimizations.
 * 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.
 */

/*
 * This file is available under and governed by the GNU General Public
 * License version 2 only, as published by the Free Software Foundation.
 * However, the following notice accompanied the original version of this
 * file:
 *
 * Written by Doug Lea and Josh Bloch with assistance from members of JCP
 * JSR-166 Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util;

import ej.annotation.Nullable;

/**
 * A {@link SortedSet} extended with navigation methods reporting closest matches for given search targets. Methods
 * {@code lower}, {@code floor}, {@code ceiling}, and {@code higher} return elements respectively less than, less than
 * or equal, greater than or equal, and greater than a given element, returning {@code null} if there is no such
 * element. A {@code NavigableSet} may be accessed and traversed in either ascending or descending order. The {@code
 * descendingSet} method returns a view of the set with the senses of all relational and directional methods inverted.
 * The performance of ascending operations and views is likely to be faster than that of descending ones. This interface
 * additionally defines methods {@code pollFirst} and {@code pollLast} that return and remove the lowest and highest
 * element, if one exists, else returning {@code
 * null}. Methods {@code subSet}, {@code headSet}, and {@code tailSet} differ from the like-named {@code
 * SortedSet} methods in accepting additional arguments describing whether lower and upper bounds are inclusive versus
 * exclusive. Subsets of any {@code NavigableSet} must implement the {@code
 * NavigableSet} interface.
 *
 * <p>
 * The return values of navigation methods may be ambiguous in implementations that permit {@code null} elements.
 * However, even in this case the result can be disambiguated by checking {@code contains(null)}. To avoid such issues,
 * implementations of this interface are encouraged to <em>not</em> permit insertion of {@code null} elements. (Note
 * that sorted sets of {@link Comparable} elements intrinsically do not permit {@code null}.)
 *
 * <p>
 * Methods {@link #subSet(Object, Object) subSet(E, E)}, {@link #headSet(Object) headSet(E)}, and
 * {@link #tailSet(Object) tailSet(E)} are specified to return {@code SortedSet} to allow existing implementations of
 * {@code SortedSet} to be compatibly retrofitted to implement {@code NavigableSet}, but extensions and implementations
 * of this interface are encouraged to override these methods to return {@code NavigableSet}.
 *
 * <p>
 * This interface is a member of the <a href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections
 * Framework</a>.
 *
 * @author Doug Lea
 * @author Josh Bloch
 * @param <E>
 *            the type of elements maintained by this set
 * @since 1.6
 */
public interface NavigableSet<E> extends SortedSet<E> {
	/**
	 * Returns the greatest element in this set strictly less than the given element, or {@code null} if there is no
	 * such element.
	 *
	 * @param e
	 *            the value to match
	 * @return the greatest element less than {@code e}, or {@code null} if there is no such element
	 * @throws ClassCastException
	 *             if the specified element cannot be compared with the elements currently in the set
	 * @throws NullPointerException
	 *             if the specified element is null and this set does not permit null elements
	 */
	@Nullable
	E lower(E e);

	/**
	 * Returns the greatest element in this set less than or equal to the given element, or {@code null} if there is no
	 * such element.
	 *
	 * @param e
	 *            the value to match
	 * @return the greatest element less than or equal to {@code e}, or {@code null} if there is no such element
	 * @throws ClassCastException
	 *             if the specified element cannot be compared with the elements currently in the set
	 * @throws NullPointerException
	 *             if the specified element is null and this set does not permit null elements
	 */
	@Nullable
	E floor(E e);

	/**
	 * Returns the least element in this set greater than or equal to the given element, or {@code null} if there is no
	 * such element.
	 *
	 * @param e
	 *            the value to match
	 * @return the least element greater than or equal to {@code e}, or {@code null} if there is no such element
	 * @throws ClassCastException
	 *             if the specified element cannot be compared with the elements currently in the set
	 * @throws NullPointerException
	 *             if the specified element is null and this set does not permit null elements
	 */
	@Nullable
	E ceiling(E e);

	/**
	 * Returns the least element in this set strictly greater than the given element, or {@code null} if there is no
	 * such element.
	 *
	 * @param e
	 *            the value to match
	 * @return the least element greater than {@code e}, or {@code null} if there is no such element
	 * @throws ClassCastException
	 *             if the specified element cannot be compared with the elements currently in the set
	 * @throws NullPointerException
	 *             if the specified element is null and this set does not permit null elements
	 */
	@Nullable
	E higher(E e);

	/**
	 * Retrieves and removes the first (lowest) element, or returns {@code null} if this set is empty.
	 *
	 * @return the first element, or {@code null} if this set is empty
	 */
	@Nullable
	E pollFirst();

	/**
	 * Retrieves and removes the last (highest) element, or returns {@code null} if this set is empty.
	 *
	 * @return the last element, or {@code null} if this set is empty
	 */
	@Nullable
	E pollLast();

	/**
	 * Returns an iterator over the elements in this set, in ascending order.
	 *
	 * @return an iterator over the elements in this set, in ascending order
	 */
	@Override
	Iterator<E> iterator();

	/**
	 * Returns a reverse order view of the elements contained in this set. The descending set is backed by this set, so
	 * changes to the set are reflected in the descending set, and vice-versa. If either set is modified while an
	 * iteration over either set is in progress (except through the iterator's own {@code remove} operation), the
	 * results of the iteration are undefined.
	 *
	 * <p>
	 * The returned set has an ordering equivalent to
	 * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>. The expression
	 * {@code s.descendingSet().descendingSet()} returns a view of {@code s} essentially equivalent to {@code s}.
	 *
	 * @return a reverse order view of this set
	 */
	NavigableSet<E> descendingSet();

	/**
	 * Returns an iterator over the elements in this set, in descending order. Equivalent in effect to
	 * {@code descendingSet().iterator()}.
	 *
	 * @return an iterator over the elements in this set, in descending order
	 */
	Iterator<E> descendingIterator();

	/**
	 * Returns a view of the portion of this set whose elements range from {@code fromElement} to {@code toElement}. If
	 * {@code fromElement} and {@code toElement} are equal, the returned set is empty unless {@code
	 * fromInclusive} and {@code toInclusive} are both true. The returned set is backed by this set, so changes in the
	 * returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations
	 * that this set supports.
	 *
	 * <p>
	 * The returned set will throw an {@code IllegalArgumentException} on an attempt to insert an element outside its
	 * range.
	 *
	 * @param fromElement
	 *            low endpoint of the returned set
	 * @param fromInclusive
	 *            {@code true} if the low endpoint is to be included in the returned view
	 * @param toElement
	 *            high endpoint of the returned set
	 * @param toInclusive
	 *            {@code true} if the high endpoint is to be included in the returned view
	 * @return a view of the portion of this set whose elements range from {@code fromElement}, inclusive, to
	 *         {@code toElement}, exclusive
	 * @throws ClassCastException
	 *             if {@code fromElement} and {@code toElement} cannot be compared to one another using this set's
	 *             comparator (or, if the set has no comparator, using natural ordering). Implementations may, but are
	 *             not required to, throw this exception if {@code fromElement} or {@code toElement} cannot be compared
	 *             to elements currently in the set.
	 * @throws NullPointerException
	 *             if {@code fromElement} or {@code toElement} is null and this set does not permit null elements
	 * @throws IllegalArgumentException
	 *             if {@code fromElement} is greater than {@code toElement}; or if this set itself has a restricted
	 *             range, and {@code fromElement} or {@code toElement} lies outside the bounds of the range.
	 */
	NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);

	/**
	 * Returns a view of the portion of this set whose elements are less than (or equal to, if {@code inclusive} is
	 * true) {@code toElement}. The returned set is backed by this set, so changes in the returned set are reflected in
	 * this set, and vice-versa. The returned set supports all optional set operations that this set supports.
	 *
	 * <p>
	 * The returned set will throw an {@code IllegalArgumentException} on an attempt to insert an element outside its
	 * range.
	 *
	 * @param toElement
	 *            high endpoint of the returned set
	 * @param inclusive
	 *            {@code true} if the high endpoint is to be included in the returned view
	 * @return a view of the portion of this set whose elements are less than (or equal to, if {@code inclusive} is
	 *         true) {@code toElement}
	 * @throws ClassCastException
	 *             if {@code toElement} is not compatible with this set's comparator (or, if the set has no comparator,
	 *             if {@code toElement} does not implement {@link Comparable}). Implementations may, but are not
	 *             required to, throw this exception if {@code toElement} cannot be compared to elements currently in
	 *             the set.
	 * @throws NullPointerException
	 *             if {@code toElement} is null and this set does not permit null elements
	 * @throws IllegalArgumentException
	 *             if this set itself has a restricted range, and {@code toElement} lies outside the bounds of the range
	 */
	NavigableSet<E> headSet(E toElement, boolean inclusive);

	/**
	 * Returns a view of the portion of this set whose elements are greater than (or equal to, if {@code inclusive} is
	 * true) {@code fromElement}. The returned set is backed by this set, so changes in the returned set are reflected
	 * in this set, and vice-versa. The returned set supports all optional set operations that this set supports.
	 *
	 * <p>
	 * The returned set will throw an {@code IllegalArgumentException} on an attempt to insert an element outside its
	 * range.
	 *
	 * @param fromElement
	 *            low endpoint of the returned set
	 * @param inclusive
	 *            {@code true} if the low endpoint is to be included in the returned view
	 * @return a view of the portion of this set whose elements are greater than or equal to {@code fromElement}
	 * @throws ClassCastException
	 *             if {@code fromElement} is not compatible with this set's comparator (or, if the set has no
	 *             comparator, if {@code fromElement} does not implement {@link Comparable}). Implementations may, but
	 *             are not required to, throw this exception if {@code fromElement} cannot be compared to elements
	 *             currently in the set.
	 * @throws NullPointerException
	 *             if {@code fromElement} is null and this set does not permit null elements
	 * @throws IllegalArgumentException
	 *             if this set itself has a restricted range, and {@code fromElement} lies outside the bounds of the
	 *             range
	 */
	NavigableSet<E> tailSet(E fromElement, boolean inclusive);

	/**
	 * {@inheritDoc}
	 *
	 * <p>
	 * Equivalent to {@code subSet(fromElement, true, toElement, false)}.
	 *
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 */
	@Override
	SortedSet<E> subSet(E fromElement, E toElement);

	/**
	 * {@inheritDoc}
	 *
	 * <p>
	 * Equivalent to {@code headSet(toElement, false)}.
	 *
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 */
	@Override
	SortedSet<E> headSet(E toElement);

	/**
	 * {@inheritDoc}
	 *
	 * <p>
	 * Equivalent to {@code tailSet(fromElement, true)}.
	 *
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 */
	@Override
	SortedSet<E> tailSet(E fromElement);
}