/* * @(#)SortedMap.java 1.21 04/06/28 * * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; /** * A map that further guarantees that it will be in ascending key order, * sorted according to the natural ordering of its keys (see the * Comparable interface), or by a comparator provided at sorted map * creation time. This order is reflected when iterating over the sorted * map's collection views (returned by the entrySet, keySet * and values methods). Several additional operations are provided * to take advantage of the ordering. (This interface is the map analogue of * the SortedSet interface.)

* * All keys inserted into a sorted map must implement the Comparable * interface (or be accepted by the specified comparator). Furthermore, all * such keys must be mutually comparable: k1.compareTo(k2) (or * comparator.compare(k1, k2)) must not throw a * ClassCastException for any elements k1 and k2 in * the sorted map. Attempts to violate this restriction will cause the * offending method or constructor invocation to throw a * ClassCastException.

* * Note that the ordering maintained by a sorted map (whether or not an * explicit comparator is provided) must be consistent with equals if * the sorted map is to correctly implement the Map interface. (See * the Comparable interface or Comparator interface for a * precise definition of consistent with equals.) This is so because * the Map interface is defined in terms of the equals * operation, but a sorted map performs all key comparisons using its * compareTo (or compare) method, so two keys that are * deemed equal by this method are, from the standpoint of the sorted map, * equal. The behavior of a tree map is well-defined even if its * ordering is inconsistent with equals; it just fails to obey the general * contract of the Map interface.

* * All general-purpose sorted map implementation classes should provide four * "standard" constructors: 1) A void (no arguments) constructor, which * creates an empty sorted map sorted according to the natural order of * its keys. 2) A constructor with a single argument of type * Comparator, which creates an empty sorted map sorted according to * the specified comparator. 3) A constructor with a single argument of type * Map, which creates a new map with the same key-value mappings as * its argument, sorted according to the keys' natural ordering. 4) A * constructor with a single argument of type sorted map, which creates a new * sorted map with the same key-value mappings and the same ordering as the * input sorted map. There is no way to enforce this recommendation (as * interfaces cannot contain constructors) but the JDK implementation * (TreeMap) complies.

* * This interface is a member of the * * Java Collections Framework. * * @author Josh Bloch * @version 1.21, 06/28/04 * @see Map * @see TreeMap * @see SortedSet * @see Comparator * @see Comparable * @see Collection * @see ClassCastException * @since 1.2 */ public interface SortedMap extends Map { /** * Returns the comparator associated with this sorted map, or * null if it uses its keys' natural ordering. * * @return the comparator associated with this sorted map, or * null if it uses its keys' natural ordering. */ Comparator comparator(); /** * Returns a view of the portion of this sorted map whose keys range from * fromKey, inclusive, to toKey, exclusive. (If * fromKey and toKey are equal, the returned sorted map * is empty.) The returned sorted map is backed by this sorted map, so * changes in the returned sorted map are reflected in this sorted map, * and vice-versa. The returned Map supports all optional map operations * that this sorted map supports.

* * The map returned by this method will throw an * IllegalArgumentException if the user attempts to insert a key * outside the specified range.

* * Note: this method always returns a half-open range (which * includes its low endpoint but not its high endpoint). If you need a * closed range (which includes both endpoints), and the key type * allows for calculation of the successor a given key, merely request the * subrange from lowEndpoint to successor(highEndpoint). * For example, suppose that m is a map whose keys are strings. * The following idiom obtains a view containing all of the key-value * mappings in m whose keys are between low and * high, inclusive: * * 

    Map sub = m.subMap(low, high+"\0");
* * A similarly technique can be used to generate an open range * (which contains neither endpoint). The following idiom obtains a * view containing all of the key-value mappings in m whose keys * are between low and high, exclusive: * * 
    Map sub = m.subMap(low+"\0", high);
* * @param fromKey low endpoint (inclusive) of the subMap. * @param toKey high endpoint (exclusive) of the subMap. * @return a view of the specified range within this sorted map. * * @throws ClassCastException if fromKey and toKey * cannot be compared to one another using this map's comparator * (or, if the map has no comparator, using natural ordering). * Implementations may, but are not required to, throw this * exception if fromKey or toKey * cannot be compared to keys currently in the map. * @throws IllegalArgumentException if fromKey is greater than * toKey; or if this map is itself a subMap, headMap, * or tailMap, and fromKey or toKey are not * within the specified range of the subMap, headMap, or tailMap. * @throws NullPointerException if fromKey or toKey is * null and this sorted map does not tolerate * null keys. */ SortedMap subMap(K fromKey, K toKey); /** * Returns a view of the portion of this sorted map whose keys are * strictly less than toKey. The returned sorted map is backed by this * sorted map, so changes in the returned sorted map are reflected in this * sorted map, and vice-versa. The returned map supports all optional map * operations that this sorted map supports.

* * The map returned by this method will throw an IllegalArgumentException * if the user attempts to insert a key outside the specified range.

* * Note: this method always returns a view that does not contain its * (high) endpoint. If you need a view that does contain this endpoint, * and the key type allows for calculation of the successor a given * key, merely request a headMap bounded by successor(highEndpoint). * For example, suppose that suppose that m is a map whose keys * are strings. The following idiom obtains a view containing all of the * key-value mappings in m whose keys are less than or equal to * high: * * 

    Map head = m.headMap(high+"\0");
* * @param toKey high endpoint (exclusive) of the subMap. * @return a view of the specified initial range of this sorted map. * @throws ClassCastException if toKey is not compatible * with this map's comparator (or, if the map has no comparator, * if toKey does not implement Comparable). * Implementations may, but are not required to, throw this * exception if toKey cannot be compared to keys * currently in the map. * @throws IllegalArgumentException if this map is itself a subMap, * headMap, or tailMap, and toKey is not within the * specified range of the subMap, headMap, or tailMap. * @throws NullPointerException if toKey is null and * this sorted map does not tolerate null keys. */ SortedMap headMap(K toKey); /** * Returns a view of the portion of this sorted map whose keys are greater * than or equal to fromKey. The returned sorted map is backed * by this sorted map, so changes in the returned sorted map are reflected * in this sorted map, and vice-versa. The returned map supports all * optional map operations that this sorted map supports.

* * The map returned by this method will throw an * IllegalArgumentException if the user attempts to insert a key * outside the specified range.

* * Note: this method always returns a view that contains its (low) * endpoint. If you need a view that does not contain this endpoint, and * the element type allows for calculation of the successor a given value, * merely request a tailMap bounded by successor(lowEndpoint). * For example, suppose that suppose that m is a map whose keys * are strings. The following idiom obtains a view containing all of the * key-value mappings in m whose keys are strictly greater than * low: * * 

    Map tail = m.tailMap(low+"\0");
* * @param fromKey low endpoint (inclusive) of the tailMap. * @return a view of the specified final range of this sorted map. * @throws ClassCastException if fromKey is not compatible * with this map's comparator (or, if the map has no comparator, * if fromKey does not implement Comparable). * Implementations may, but are not required to, throw this * exception if fromKey cannot be compared to keys * currently in the map. * @throws IllegalArgumentException if this map is itself a subMap, * headMap, or tailMap, and fromKey is not within the * specified range of the subMap, headMap, or tailMap. * @throws NullPointerException if fromKey is null and * this sorted map does not tolerate null keys. */ SortedMap tailMap(K fromKey); /** * Returns the first (lowest) key currently in this sorted map. * * @return the first (lowest) key currently in this sorted map. * @throws NoSuchElementException if this map is empty. */ K firstKey(); /** * Returns the last (highest) key currently in this sorted map. * * @return the last (highest) key currently in this sorted map. * @throws NoSuchElementException if this map is empty. */ K lastKey(); }