001 /* SortedMap.java -- A map that makes guarantees about the order of its keys 002 Copyright (C) 1998, 2001, 2004, 2005 Free Software Foundation, Inc. 003 004 This file is part of GNU Classpath. 005 006 GNU Classpath is free software; you can redistribute it and/or modify 007 it under the terms of the GNU General Public License as published by 008 the Free Software Foundation; either version 2, or (at your option) 009 any later version. 010 011 GNU Classpath 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 for more details. 015 016 You should have received a copy of the GNU General Public License 017 along with GNU Classpath; see the file COPYING. If not, write to the 018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 019 02110-1301 USA. 020 021 Linking this library statically or dynamically with other modules is 022 making a combined work based on this library. Thus, the terms and 023 conditions of the GNU General Public License cover the whole 024 combination. 025 026 As a special exception, the copyright holders of this library give you 027 permission to link this library with independent modules to produce an 028 executable, regardless of the license terms of these independent 029 modules, and to copy and distribute the resulting executable under 030 terms of your choice, provided that you also meet, for each linked 031 independent module, the terms and conditions of the license of that 032 module. An independent module is a module which is not derived from 033 or based on this library. If you modify this library, you may extend 034 this exception to your version of the library, but you are not 035 obligated to do so. If you do not wish to do so, delete this 036 exception statement from your version. */ 037 038 039 package java.util; 040 041 /** 042 * A map which guarantees its key's iteration order. The entries in the 043 * map are related by the <i>natural ordering</i> of the keys if they 044 * are Comparable, or by the provided Comparator. Additional operations 045 * take advantage of the sorted nature of the map. 046 * <p> 047 * 048 * All keys entered in the map must be mutually comparable; in other words, 049 * <code>k1.compareTo(k2)</code> or <code>comparator.compare(k1, k2)</code> 050 * must not throw a ClassCastException. The ordering must be <i>consistent 051 * with equals</i> (see {@link Comparator} for this definition), if the 052 * map is to obey the general contract of the Map interface. If not, 053 * the results are well-defined, but probably not what you wanted. 054 * <p> 055 * 056 * It is recommended that all implementing classes provide four constructors: 057 * 1) one that takes no arguments and builds an empty map sorted by natural 058 * order of the keys; 2) one that takes a Comparator for the sorting order; 059 * 3) one that takes a Map and sorts according to the natural order of its 060 * keys; and 4) one that takes a SortedMap and sorts by the same comparator. 061 * Unfortunately, the Java language does not provide a way to enforce this. 062 * 063 * @author Original author unknown 064 * @author Eric Blake (ebb9@email.byu.edu) 065 * @see Map 066 * @see TreeMap 067 * @see SortedSet 068 * @see Comparable 069 * @see Comparator 070 * @see Collection 071 * @see ClassCastException 072 * @since 1.2 073 * @status updated to 1.4 074 */ 075 public interface SortedMap<K, V> extends Map<K, V> 076 { 077 /** 078 * Returns the comparator used in sorting this map, or null if it is 079 * the keys' natural ordering. 080 * 081 * @return the sorting comparator 082 */ 083 Comparator<? super K> comparator(); 084 085 /** 086 * Returns the first (lowest sorted) key in the map. 087 * 088 * @return the first key 089 * @throws NoSuchElementException if this map is empty. 090 */ 091 K firstKey(); 092 093 /** 094 * Returns a view of the portion of the map strictly less than toKey. The 095 * view is backed by this map, so changes in one show up in the other. 096 * The submap supports all optional operations of the original. 097 * <p> 098 * 099 * 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 }