001: /*
002: * @(#)SortedMap.java 1.19 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: /**
031: * A map that further guarantees that it will be in ascending key order,
032: * sorted according to the <i>natural ordering</i> of its keys (see the
033: * <tt>Comparable</tt> interface), or by a comparator provided at sorted map
034: * creation time. This order is reflected when iterating over the sorted
035: * map's collection views (returned by the <tt>entrySet</tt>, <tt>keySet</tt>
036: * and <tt>values</tt> methods). Several additional operations are provided
037: * to take advantage of the ordering. (This interface is the map analogue of
038: * the <tt>SortedSet</tt> interface.)<p>
039: *
040: * All keys inserted into a sorted map must implement the <tt>Comparable</tt>
041: * interface (or be accepted by the specified comparator). Furthermore, all
042: * such keys must be <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> (or
043: * <tt>comparator.compare(k1, k2)</tt>) must not throw a
044: * <tt>ClassCastException</tt> for any elements <tt>k1</tt> and <tt>k2</tt> in
045: * the sorted map. Attempts to violate this restriction will cause the
046: * offending method or constructor invocation to throw a
047: * <tt>ClassCastException</tt>.<p>
048: *
049: * Note that the ordering maintained by a sorted map (whether or not an
050: * explicit comparator is provided) must be <i>consistent with equals</i> if
051: * the sorted map is to correctly implement the <tt>Map</tt> interface. (See
052: * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a
053: * precise definition of <i>consistent with equals</i>.) This is so because
054: * the <tt>Map</tt> interface is defined in terms of the <tt>equals</tt>
055: * operation, but a sorted map performs all key comparisons using its
056: * <tt>compareTo</tt> (or <tt>compare</tt>) method, so two keys that are
057: * deemed equal by this method are, from the standpoint of the sorted map,
058: * equal. The behavior of a tree map <i>is</i> well-defined even if its
059: * ordering is inconsistent with equals; it just fails to obey the general
060: * contract of the <tt>Map</tt> interface.<p>
061: *
062: * All general-purpose sorted map implementation classes should provide four
063: * "standard" constructors: 1) A void (no arguments) constructor, which
064: * creates an empty sorted map sorted according to the <i>natural order</i> of
065: * its keys. 2) A constructor with a single argument of type
066: * <tt>Comparator</tt>, which creates an empty sorted map sorted according to
067: * the specified comparator. 3) A constructor with a single argument of type
068: * <tt>Map</tt>, which creates a new map with the same key-value mappings as
069: * its argument, sorted according to the keys' natural ordering. 4) A
070: * constructor with a single argument of type sorted map, which creates a new
071: * sorted map with the same key-value mappings and the same ordering as the
072: * input sorted map. There is no way to enforce this recommendation (as
073: * interfaces cannot contain constructors) but the SDK implementation
074: * (TreeMap) complies.<p>
075: *
076: * This interface is a member of the
077: * <a href="{@docRoot}/../guide/collections/index.html">
078: * Java Collections Framework</a>.
079: *
080: * @author Josh Bloch
081: * @version 1.12, 02/02/00
082: * @see Map
083: * @see TreeMap
084: * @see SortedSet
085: * @see Comparator
086: * @see Comparable
087: * @see Collection
088: * @see ClassCastException
089: * @since 1.2
090: */
091:
092: public interface SortedMap extends Map {
093: /**
094: * Returns the comparator associated with this sorted map, or
095: * <tt>null</tt> if it uses its keys' natural ordering.
096: *
097: * @return the comparator associated with this sorted map, or
098: * <tt>null</tt> if it uses its keys' natural ordering.
099: */
100: Comparator comparator();
101:
102: /**
103: * Returns a view of the portion of this sorted map whose keys range from
104: * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
105: * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
106: * is empty.) The returned sorted map is backed by this sorted map, so
107: * changes in the returned sorted map are reflected in this sorted map,
108: * and vice-versa. The returned Map supports all optional map operations
109: * that this sorted map supports.<p>
110: *
111: * The map returned by this method will throw an
112: * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
113: * outside the specified range.<p>
114: *
115: * Note: this method always returns a <i>half-open range</i> (which
116: * includes its low endpoint but not its high endpoint). If you need a
117: * <i>closed range</i> (which includes both endpoints), and the key type
118: * allows for calculation of the successor a given key, merely request the
119: * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
120: * For example, suppose that <tt>m</tt> is a map whose keys are strings.
121: * The following idiom obtains a view containing all of the key-value
122: * mappings in <tt>m</tt> whose keys are between <tt>low</tt> and
123: * <tt>high</tt>, inclusive:
124: *
125: * <pre> Map sub = m.subMap(low, high+"\0");</pre>
126: *
127: * A similarly technique can be used to generate an <i>open range</i>
128: * (which contains neither endpoint). The following idiom obtains a
129: * view containing all of the key-value mappings in <tt>m</tt> whose keys
130: * are between <tt>low</tt> and <tt>high</tt>, exclusive:
131: *
132: * <pre> Map sub = m.subMap(low+"\0", high);</pre>
133: *
134: * @param fromKey low endpoint (inclusive) of the subMap.
135: * @param toKey high endpoint (exclusive) of the subMap.
136: * @return a view of the specified range within this sorted map.
137: *
138: * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
139: * cannot be compared to one another using this map's comparator
140: * (or, if the map has no comparator, using natural ordering).
141: * Implementations may, but are not required to, throw this
142: * exception if <tt>fromKey</tt> or <tt>toKey</tt>
143: * cannot be compared to keys currently in the map.
144: * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
145: * <tt>toKey</tt>; or if this map is itself a subMap, headMap,
146: * or tailMap, and <tt>fromKey</tt> or <tt>toKey</tt> are not
147: * within the specified range of the subMap, headMap, or tailMap.
148: * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
149: * <tt>null</tt> and this sorted map does not tolerate
150: * <tt>null</tt> keys.
151: */
152: SortedMap subMap(Object fromKey, Object toKey);
153:
154: /**
155: * Returns a view of the portion of this sorted map whose keys are
156: * strictly less than toKey. The returned sorted map is backed by this
157: * sorted map, so changes in the returned sorted map are reflected in this
158: * sorted map, and vice-versa. The returned map supports all optional map
159: * operations that this sorted map supports.<p>
160: *
161: * The map returned by this method will throw an IllegalArgumentException
162: * if the user attempts to insert a key outside the specified range.<p>
163: *
164: * Note: this method always returns a view that does not contain its
165: * (high) endpoint. If you need a view that does contain this endpoint,
166: * and the key type allows for calculation of the successor a given
167: * key, merely request a headMap bounded by successor(highEndpoint).
168: * For example, suppose that suppose that <tt>m</tt> is a map whose keys
169: * are strings. The following idiom obtains a view containing all of the
170: * key-value mappings in <tt>m</tt> whose keys are less than or equal to
171: * <tt>high</tt>:
172: *
173: * <pre> Map head = m.headMap(high+"\0");</pre>
174: *
175: * @param toKey high endpoint (exclusive) of the subMap.
176: * @return a view of the specified initial range of this sorted map.
177: * @throws ClassCastException if <tt>toKey</tt> is not compatible
178: * with this map's comparator (or, if the map has no comparator,
179: * if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
180: * Implementations may, but are not required to, throw this
181: * exception if <tt>toKey</tt> cannot be compared to keys
182: * currently in the map.
183: * @throws IllegalArgumentException if this map is itself a subMap,
184: * headMap, or tailMap, and <tt>toKey</tt> is not within the
185: * specified range of the subMap, headMap, or tailMap.
186: * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
187: * this sorted map does not tolerate <tt>null</tt> keys.
188: */
189: SortedMap headMap(Object toKey);
190:
191: /**
192: * Returns a view of the portion of this sorted map whose keys are greater
193: * than or equal to <tt>fromKey</tt>. The returned sorted map is backed
194: * by this sorted map, so changes in the returned sorted map are reflected
195: * in this sorted map, and vice-versa. The returned map supports all
196: * optional map operations that this sorted map supports.<p>
197: *
198: * The map returned by this method will throw an
199: * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
200: * outside the specified range.<p>
201: *
202: * Note: this method always returns a view that contains its (low)
203: * endpoint. If you need a view that does not contain this endpoint, and
204: * the element type allows for calculation of the successor a given value,
205: * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
206: * For example, suppose that suppose that <tt>m</tt> is a map whose keys
207: * are strings. The following idiom obtains a view containing all of the
208: * key-value mappings in <tt>m</tt> whose keys are strictly greater than
209: * <tt>low</tt>:
210: *
211: * <pre> Map tail = m.tailMap(low+"\0");</pre>
212: *
213: * @param fromKey low endpoint (inclusive) of the tailMap.
214: * @return a view of the specified final range of this sorted map.
215: * @throws ClassCastException if <tt>fromKey</tt> is not compatible
216: * with this map's comparator (or, if the map has no comparator,
217: * if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
218: * Implementations may, but are not required to, throw this
219: * exception if <tt>fromKey</tt> cannot be compared to keys
220: * currently in the map.
221: * @throws IllegalArgumentException if this map is itself a subMap,
222: * headMap, or tailMap, and <tt>fromKey</tt> is not within the
223: * specified range of the subMap, headMap, or tailMap.
224: * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
225: * this sorted map does not tolerate <tt>null</tt> keys.
226: */
227: SortedMap tailMap(Object fromKey);
228:
229: /**
230: * Returns the first (lowest) key currently in this sorted map.
231: *
232: * @return the first (lowest) key currently in this sorted map.
233: * @throws NoSuchElementException if this map is empty.
234: */
235: Object firstKey();
236:
237: /**
238: * Returns the last (highest) key currently in this sorted map.
239: *
240: * @return the last (highest) key currently in this sorted map.
241: * @throws NoSuchElementException if this map is empty.
242: */
243: Object lastKey();
244: }
|