SortedMap


1   /*
2    * @(#)SortedMap.java   1.21 04/06/28
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   
10  /**
11   * A map that further guarantees that it will be in ascending key order,
12   * sorted according to the <i>natural ordering</i> of its keys (see the
13   * <tt>Comparable</tt> interface), or by a comparator provided at sorted map
14   * creation time.  This order is reflected when iterating over the sorted
15   * map's collection views (returned by the <tt>entrySet</tt>, <tt>keySet</tt>
16   * and <tt>values</tt> methods).  Several additional operations are provided
17   * to take advantage of the ordering.  (This interface is the map analogue of
18   * the <tt>SortedSet</tt> interface.)<p>
19   *
20   * All keys inserted into a sorted map must implement the <tt>Comparable</tt>
21   * interface (or be accepted by the specified comparator).  Furthermore, all
22   * such keys must be <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> (or
23   * <tt>comparator.compare(k1, k2)</tt>) must not throw a
24   * <tt>ClassCastException</tt> for any elements <tt>k1</tt> and <tt>k2</tt> in
25   * the sorted map.  Attempts to violate this restriction will cause the
26   * offending method or constructor invocation to throw a
27   * <tt>ClassCastException</tt>.<p>
28   *
29   * Note that the ordering maintained by a sorted map (whether or not an
30   * explicit comparator is provided) must be <i>consistent with equals</i> if
31   * the sorted map is to correctly implement the <tt>Map</tt> interface.  (See
32   * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a
33   * precise definition of <i>consistent with equals</i>.)  This is so because
34   * the <tt>Map</tt> interface is defined in terms of the <tt>equals</tt>
35   * operation, but a sorted map performs all key comparisons using its
36   * <tt>compareTo</tt> (or <tt>compare</tt>) method, so two keys that are
37   * deemed equal by this method are, from the standpoint of the sorted map,
38   * equal.  The behavior of a tree map <i>is</i> well-defined even if its
39   * ordering is inconsistent with equals; it just fails to obey the general
40   * contract of the <tt>Map</tt> interface.<p>
41   *
42   * All general-purpose sorted map implementation classes should provide four
43   * "standard" constructors: 1) A void (no arguments) constructor, which
44   * creates an empty sorted map sorted according to the <i>natural order</i> of
45   * its keys.  2) A constructor with a single argument of type
46   * <tt>Comparator</tt>, which creates an empty sorted map sorted according to
47   * the specified comparator.  3) A constructor with a single argument of type
48   * <tt>Map</tt>, which creates a new map with the same key-value mappings as
49   * its argument, sorted according to the keys' natural ordering.  4) A
50   * constructor with a single argument of type sorted map, which creates a new
51   * sorted map with the same key-value mappings and the same ordering as the
52   * input sorted map.  There is no way to enforce this recommendation (as
53   * interfaces cannot contain constructors) but the JDK implementation
54   * (TreeMap) complies.<p>
55   *
56   * This interface is a member of the 
57   * <a HREF="{@docRoot}/../guide/collections/index.html">
58   * Java Collections Framework</a>.
59   *
60   * @author  Josh Bloch
61   * @version 1.21, 06/28/04
62   * @see Map
63   * @see TreeMap
64   * @see SortedSet
65   * @see Comparator
66   * @see Comparable
67   * @see Collection
68   * @see ClassCastException
69   * @since 1.2
70   */
71  
72  public interface SortedMap<K,V> extends Map  <K,V> {
73      /**
74       * Returns the comparator associated with this sorted map, or
75       * <tt>null</tt> if it uses its keys' natural ordering.
76       *
77       * @return the comparator associated with this sorted map, or
78       *         <tt>null</tt> if it uses its keys' natural ordering.
79       */
80      Comparator  <? super K> comparator();
81  
82      /**
83       * Returns a view of the portion of this sorted map whose keys range from
84       * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
85       * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
86       * is empty.)  The returned sorted map is backed by this sorted map, so
87       * changes in the returned sorted map are reflected in this sorted map,
88       * and vice-versa.  The returned Map supports all optional map operations
89       * that this sorted map supports.<p>
90       *
91       * The map returned by this method will throw an
92       * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
93       * outside the specified range.<p>
94       *
95       * Note: this method always returns a <i>half-open range</i> (which
96       * includes its low endpoint but not its high endpoint).  If you need a
97       * <i>closed range</i> (which includes both endpoints), and the key type
98       * allows for calculation of the successor a given key, merely request the
99       * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
100      * For example, suppose that <tt>m</tt> is a map whose keys are strings.
101      * The following idiom obtains a view containing all of the key-value
102      * mappings in <tt>m</tt> whose keys are between <tt>low</tt> and
103      * <tt>high</tt>, inclusive:
104      * 
105      *      <pre>    Map sub = m.subMap(low, high+"\0");</pre>
106      * 
107      * A similarly technique can be used to generate an <i>open range</i>
108      * (which contains neither endpoint).  The following idiom obtains a
109      * view containing  all of the key-value mappings in <tt>m</tt> whose keys
110      * are between <tt>low</tt> and <tt>high</tt>, exclusive:
111      * 
112      *      <pre>    Map sub = m.subMap(low+"\0", high);</pre>
113      *
114      * @param fromKey low endpoint (inclusive) of the subMap.
115      * @param toKey high endpoint (exclusive) of the subMap.
116      * @return a view of the specified range within this sorted map.
117      * 
118      * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
119      *         cannot be compared to one another using this map's comparator
120      *         (or, if the map has no comparator, using natural ordering).
121      *         Implementations may, but are not required to, throw this
122      *         exception if <tt>fromKey</tt> or <tt>toKey</tt>
123      *         cannot be compared to keys currently in the map.
124      * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
125      *         <tt>toKey</tt>; or if this map is itself a subMap, headMap,
126      *         or tailMap, and <tt>fromKey</tt> or <tt>toKey</tt> are not
127      *         within the specified range of the subMap, headMap, or tailMap.
128      * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
129      *         <tt>null</tt> and this sorted map does not tolerate
130      *         <tt>null</tt> keys.
131      */
132     SortedMap  <K,V> subMap(K fromKey, K toKey);
133 
134     /**
135      * Returns a view of the portion of this sorted map whose keys are
136      * strictly less than toKey.  The returned sorted map is backed by this
137      * sorted map, so changes in the returned sorted map are reflected in this
138      * sorted map, and vice-versa.  The returned map supports all optional map
139      * operations that this sorted map supports.<p>
140      *
141      * The map returned by this method will throw an IllegalArgumentException
142      * if the user attempts to insert a key outside the specified range.<p>
143      *
144      * Note: this method always returns a view that does not contain its
145      * (high) endpoint.  If you need a view that does contain this endpoint,
146      * and the key type allows for calculation of the successor a given
147      * key, merely request a headMap bounded by successor(highEndpoint).
148      * For example, suppose that suppose that <tt>m</tt> is a map whose keys
149      * are strings.  The following idiom obtains a view containing all of the
150      * key-value mappings in <tt>m</tt> whose keys are less than or equal to
151      * <tt>high</tt>:
152      * 
153      *      <pre>    Map head = m.headMap(high+"\0");</pre>
154      *
155      * @param toKey high endpoint (exclusive) of the subMap.
156      * @return a view of the specified initial range of this sorted map.
157      * @throws ClassCastException if <tt>toKey</tt> is not compatible
158      *         with this map's comparator (or, if the map has no comparator,
159      *         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
160      *         Implementations may, but are not required to, throw this
161      *         exception if <tt>toKey</tt> cannot be compared to keys
162      *         currently in the map.
163      * @throws IllegalArgumentException if this map is itself a subMap,
164      *         headMap, or tailMap, and <tt>toKey</tt> is not within the
165      *         specified range of the subMap, headMap, or tailMap.
166      * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
167      *         this sorted map does not tolerate <tt>null</tt> keys.
168      */
169     SortedMap  <K,V> headMap(K toKey);
170 
171     /**
172      * Returns a view of the portion of this sorted map whose keys are greater
173      * than or equal to <tt>fromKey</tt>.  The returned sorted map is backed
174      * by this sorted map, so changes in the returned sorted map are reflected
175      * in this sorted map, and vice-versa.  The returned map supports all
176      * optional map operations that this sorted map supports.<p>
177      *
178      * The map returned by this method will throw an
179      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
180      * outside the specified range.<p>
181      *
182      * Note: this method always returns a view that contains its (low)
183      * endpoint.  If you need a view that does not contain this endpoint, and
184      * the element type allows for calculation of the successor a given value,
185      * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
186      * For example, suppose that suppose that <tt>m</tt> is a map whose keys
187      * are strings.  The following idiom obtains a view containing all of the
188      * key-value mappings in <tt>m</tt> whose keys are strictly greater than
189      * <tt>low</tt>:
190      * 
191      *      <pre>    Map tail = m.tailMap(low+"\0");</pre>
192      *
193      * @param fromKey low endpoint (inclusive) of the tailMap.
194      * @return a view of the specified final range of this sorted map.
195      * @throws ClassCastException if <tt>fromKey</tt> is not compatible
196      *         with this map's comparator (or, if the map has no comparator,
197      *         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
198      *         Implementations may, but are not required to, throw this
199      *         exception if <tt>fromKey</tt> cannot be compared to keys
200      *         currently in the map.
201      * @throws IllegalArgumentException if this map is itself a subMap,
202      *         headMap, or tailMap, and <tt>fromKey</tt> is not within the
203      *         specified range of the subMap, headMap, or tailMap.
204      * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
205      *         this sorted map does not tolerate <tt>null</tt> keys.
206      */
207     SortedMap  <K,V> tailMap(K fromKey);
208 
209     /**
210      * Returns the first (lowest) key currently in this sorted map.
211      *
212      * @return the first (lowest) key currently in this sorted map.
213      * @throws    NoSuchElementException if this map is empty.
214      */
215     K firstKey();
216 
217     /**
218      * Returns the last (highest) key currently in this sorted map.
219      *
220      * @return the last (highest) key currently in this sorted map.
221      * @throws     NoSuchElementException if this map is empty.
222      */
223     K lastKey();
224 }
225
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags