378 lines
16 KiB
Java
378 lines
16 KiB
Java
|
/*
|
||
|
|
* 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/
|
||
|
|
*/
|
||
|
|
|
||
|
|
// BEGIN android-note
|
||
|
|
// removed link to collections framework docs
|
||
|
|
// END android-note
|
||
|
|
|
||
|
|
package java.util;
|
||
|
|
|
||
|
|
/**
|
||
|
|
* A {@link SortedSet} extended with navigation methods reporting
|
||
|
|
* closest matches for given search targets. Methods {@link #lower},
|
||
|
|
* {@link #floor}, {@link #ceiling}, and {@link #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.
|
||
|
|
*
|
||
|
|
* <p>A {@code NavigableSet} may be accessed and traversed in either
|
||
|
|
* ascending or descending order. The {@link #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 {@link
|
||
|
|
* #pollFirst} and {@link #pollLast} that return and remove the lowest
|
||
|
|
* and highest element, if one exists, else returning {@code null}.
|
||
|
|
* Methods
|
||
|
|
* {@link #subSet(Object, boolean, Object, boolean) subSet(E, boolean, E, boolean)},
|
||
|
|
* {@link #headSet(Object, boolean) headSet(E, boolean)}, and
|
||
|
|
* {@link #tailSet(Object, boolean) tailSet(E, boolean)}
|
||
|
|
* 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}.
|
||
|
|
*
|
||
|
|
* @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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
*/
|
||
|
|
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
|
||
|
|
* {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
|
||
|
|
* 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}
|
||
|
|
*/
|
||
|
|
SortedSet<E> subSet(E fromElement, E toElement);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* {@inheritDoc}
|
||
|
|
*
|
||
|
|
* <p>Equivalent to {@code headSet(toElement, false)}.
|
||
|
|
*
|
||
|
|
* @throws ClassCastException {@inheritDoc}
|
||
|
|
* @throws NullPointerException {@inheritDoc}
|
||
|
|
* @throws IllegalArgumentException {@inheritDoc}
|
||
|
|
*/
|
||
|
|
SortedSet<E> headSet(E toElement);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* {@inheritDoc}
|
||
|
|
*
|
||
|
|
* <p>Equivalent to {@code tailSet(fromElement, true)}.
|
||
|
|
*
|
||
|
|
* @throws ClassCastException {@inheritDoc}
|
||
|
|
* @throws NullPointerException {@inheritDoc}
|
||
|
|
* @throws IllegalArgumentException {@inheritDoc}
|
||
|
|
*/
|
||
|
|
SortedSet<E> tailSet(E fromElement);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* {@inheritDoc}
|
||
|
|
*
|
||
|
|
* @implSpec
|
||
|
|
* If this set is not empty, the implementation in this interface returns the result of calling
|
||
|
|
* the {@code pollFirst} method. Otherwise, it throws {@code NoSuchElementException}.
|
||
|
|
*
|
||
|
|
* @throws NoSuchElementException {@inheritDoc}
|
||
|
|
* @throws UnsupportedOperationException {@inheritDoc}
|
||
|
|
* @since 21
|
||
|
|
*/
|
||
|
|
default E removeFirst() {
|
||
|
|
if (this.isEmpty()) {
|
||
|
|
throw new NoSuchElementException();
|
||
|
|
} else {
|
||
|
|
return this.pollFirst();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* {@inheritDoc}
|
||
|
|
*
|
||
|
|
* @implSpec
|
||
|
|
* If this set is not empty, the implementation in this interface returns the result of calling
|
||
|
|
* the {@code pollLast} method. Otherwise, it throws {@code NoSuchElementException}.
|
||
|
|
*
|
||
|
|
* @throws NoSuchElementException {@inheritDoc}
|
||
|
|
* @throws UnsupportedOperationException {@inheritDoc}
|
||
|
|
* @since 21
|
||
|
|
*/
|
||
|
|
default E removeLast() {
|
||
|
|
if (this.isEmpty()) {
|
||
|
|
throw new NoSuchElementException();
|
||
|
|
} else {
|
||
|
|
return this.pollLast();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* {@inheritDoc}
|
||
|
|
* <p>
|
||
|
|
* This method is equivalent to {@link #descendingSet descendingSet}.
|
||
|
|
*
|
||
|
|
* @implSpec
|
||
|
|
* The implementation in this interface returns the result of calling the
|
||
|
|
* {@code descendingSet} method.
|
||
|
|
*
|
||
|
|
* @return a reverse-ordered view of this collection, as a {@code NavigableSet}
|
||
|
|
* @since 21
|
||
|
|
*/
|
||
|
|
default NavigableSet<E> reversed() {
|
||
|
|
return this.descendingSet();
|
||
|
|
}
|
||
|
|
}
|