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