1: /* SortedMap.java -- A map that makes guarantees about the order of its keys 2: Copyright (C) 1998, 2001, 2004, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.util; 40: 41: /** 42: * A map which guarantees its key's iteration order. The entries in the 43: * map are related by the <i>natural ordering</i> of the keys if they 44: * are Comparable, or by the provided Comparator. Additional operations 45: * take advantage of the sorted nature of the map. 46: * <p> 47: * 48: * All keys entered in the map must be mutually comparable; in other words, 49: * <code>k1.compareTo(k2)</code> or <code>comparator.compare(k1, k2)</code> 50: * must not throw a ClassCastException. The ordering must be <i>consistent 51: * with equals</i> (see {@link Comparator} for this definition), if the 52: * map is to obey the general contract of the Map interface. If not, 53: * the results are well-defined, but probably not what you wanted. 54: * <p> 55: * 56: * It is recommended that all implementing classes provide four constructors: 57: * 1) one that takes no arguments and builds an empty map sorted by natural 58: * order of the keys; 2) one that takes a Comparator for the sorting order; 59: * 3) one that takes a Map and sorts according to the natural order of its 60: * keys; and 4) one that takes a SortedMap and sorts by the same comparator. 61: * Unfortunately, the Java language does not provide a way to enforce this. 62: * 63: * @author Original author unknown 64: * @author Eric Blake (ebb9@email.byu.edu) 65: * @see Map 66: * @see TreeMap 67: * @see SortedSet 68: * @see Comparable 69: * @see Comparator 70: * @see Collection 71: * @see ClassCastException 72: * @since 1.2 73: * @status updated to 1.4 74: */ 75: public interface SortedMap<K, V> extends Map<K, V> 76: { 77: /** 78: * Returns the comparator used in sorting this map, or null if it is 79: * the keys' natural ordering. 80: * 81: * @return the sorting comparator 82: */ 83: Comparator<? super K> comparator(); 84: 85: /** 86: * Returns the first (lowest sorted) key in the map. 87: * 88: * @return the first key 89: * @throws NoSuchElementException if this map is empty. 90: */ 91: K firstKey(); 92: 93: /** 94: * Returns a view of the portion of the map strictly less than toKey. The 95: * view is backed by this map, so changes in one show up in the other. 96: * The submap supports all optional operations of the original. 97: * <p> 98: * 99: * The returned map throws an IllegalArgumentException any time a key is 100: * used which is out of the range of toKey. Note that the endpoint, toKey, 101: * is not included; if you want this value to be included, pass its successor 102: * object in to toKey. For example, for Integers, you could request 103: * <code>headMap(new Integer(limit.intValue() + 1))</code>. 104: * 105: * @param toKey the exclusive upper range of the submap 106: * @return the submap 107: * @throws ClassCastException if toKey is not comparable to the map contents 108: * @throws IllegalArgumentException if this is a subMap, and toKey is out 109: * of range 110: * @throws NullPointerException if toKey is null but the map does not allow 111: * null keys 112: */ 113: SortedMap<K, V> headMap(K toKey); 114: 115: /** 116: * Returns the last (highest sorted) key in the map. 117: * 118: * @return the last key 119: * @throws NoSuchElementException if this map is empty. 120: */ 121: K lastKey(); 122: 123: /** 124: * Returns a view of the portion of the map greater than or equal to 125: * fromKey, and strictly less than toKey. The view is backed by this map, 126: * so changes in one show up in the other. The submap supports all 127: * optional operations of the original. 128: * <p> 129: * 130: * The returned map throws an IllegalArgumentException any time a key is 131: * used which is out of the range of fromKey and toKey. Note that the 132: * lower endpoint is included, but the upper is not; if you want to 133: * change the inclusion or exclusion of an endpoint, pass its successor 134: * object in instead. For example, for Integers, you could request 135: * <code>subMap(new Integer(lowlimit.intValue() + 1), 136: * new Integer(highlimit.intValue() + 1))</code> to reverse 137: * the inclusiveness of both endpoints. 138: * 139: * @param fromKey the inclusive lower range of the submap 140: * @param toKey the exclusive upper range of the submap 141: * @return the submap 142: * @throws ClassCastException if fromKey or toKey is not comparable to 143: * the map contents 144: * @throws IllegalArgumentException if this is a subMap, and fromKey or 145: * toKey is out of range 146: * @throws NullPointerException if fromKey or toKey is null but the map 147: * does not allow null keys 148: */ 149: SortedMap<K, V> subMap(K fromKey, K toKey); 150: 151: /** 152: * Returns a view of the portion of the map greater than or equal to 153: * fromKey. The view is backed by this map, so changes in one show up 154: * in the other. The submap supports all optional operations of the original. 155: * <p> 156: * 157: * The returned map throws an IllegalArgumentException any time a key is 158: * used which is out of the range of fromKey. Note that the endpoint, fromKey, is 159: * included; if you do not want this value to be included, pass its successor object in 160: * to fromKey. For example, for Integers, you could request 161: * <code>tailMap(new Integer(limit.intValue() + 1))</code>. 162: * 163: * @param fromKey the inclusive lower range of the submap 164: * @return the submap 165: * @throws ClassCastException if fromKey is not comparable to the map 166: * contents 167: * @throws IllegalArgumentException if this is a subMap, and fromKey is out 168: * of range 169: * @throws NullPointerException if fromKey is null but the map does not allow 170: * null keys 171: */ 172: SortedMap<K, V> tailMap(K fromKey); 173: }