| 1 |
771 |
jeremybenn |
/* 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 |
|
|
}
|
