1 /*

     2  * Copyright 1998-2006 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any questions.

    24  */

    25 

    26 package java.util;

    27 

    28 /**

    29  * A {@link Map} that further provides a <i>total ordering</i> on its keys.

    30  * The map is ordered according to the {@linkplain Comparable natural

    31  * ordering} of its keys, or by a {@link Comparator} typically

    32  * provided at sorted map creation time.  This order is reflected when

    33  * iterating over the sorted map's collection views (returned by the

    34  * <tt>entrySet</tt>, <tt>keySet</tt> and <tt>values</tt> methods).

    35  * Several additional operations are provided to take advantage of the

    36  * ordering.  (This interface is the map analogue of {@link

    37  * SortedSet}.)

    38  *

    39  * <p>All keys inserted into a sorted map must implement the <tt>Comparable</tt>

    40  * interface (or be accepted by the specified comparator).  Furthermore, all

    41  * such keys must be <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> (or

    42  * <tt>comparator.compare(k1, k2)</tt>) must not throw a

    43  * <tt>ClassCastException</tt> for any keys <tt>k1</tt> and <tt>k2</tt> in

    44  * the sorted map.  Attempts to violate this restriction will cause the

    45  * offending method or constructor invocation to throw a

    46  * <tt>ClassCastException</tt>.

    47  *

    48  * <p>Note that the ordering maintained by a sorted map (whether or not an

    49  * explicit comparator is provided) must be <i>consistent with equals</i> if

    50  * the sorted map is to correctly implement the <tt>Map</tt> interface.  (See

    51  * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a

    52  * precise definition of <i>consistent with equals</i>.)  This is so because

    53  * the <tt>Map</tt> interface is defined in terms of the <tt>equals</tt>

    54  * operation, but a sorted map performs all key comparisons using its

    55  * <tt>compareTo</tt> (or <tt>compare</tt>) method, so two keys that are

    56  * deemed equal by this method are, from the standpoint of the sorted map,

    57  * equal.  The behavior of a tree map <i>is</i> well-defined even if its

    58  * ordering is inconsistent with equals; it just fails to obey the general

    59  * contract of the <tt>Map</tt> interface.

    60  *

    61  * <p>All general-purpose sorted map implementation classes should

    62  * provide four "standard" constructors: 1) A void (no arguments)

    63  * constructor, which creates an empty sorted map sorted according to

    64  * the natural ordering of its keys.  2) A constructor with a

    65  * single argument of type <tt>Comparator</tt>, which creates an empty

    66  * sorted map sorted according to the specified comparator.  3) A

    67  * constructor with a single argument of type <tt>Map</tt>, which

    68  * creates a new map with the same key-value mappings as its argument,

    69  * sorted according to the keys' natural ordering.  4) A constructor

    70  * with a single argument of type <tt>SortedMap</tt>,

    71  * which creates a new sorted map with the same key-value mappings and

    72  * the same ordering as the input sorted map.  There is no way to

    73  * enforce this recommendation, as interfaces cannot contain

    74  * constructors.

    75  *

    76  * <p>Note: several methods return submaps with restricted key ranges.

    77  * Such ranges are <i>half-open</i>, that is, they include their low

    78  * endpoint but not their high endpoint (where applicable).  If you need a

    79  * <i>closed range</i> (which includes both endpoints), and the key type

    80  * allows for calculation of the successor of a given key, merely request

    81  * the subrange from <tt>lowEndpoint</tt> to

    82  * <tt>successor(highEndpoint)</tt>.  For example, suppose that <tt>m</tt>

    83  * is a map whose keys are strings.  The following idiom obtains a view

    84  * containing all of the key-value mappings in <tt>m</tt> whose keys are

    85  * between <tt>low</tt> and <tt>high</tt>, inclusive:<pre>

    86  *   SortedMap&lt;String, V&gt; sub = m.subMap(low, high+"\0");</pre>

    87  *

    88  * A similar technique can be used to generate an <i>open range</i>

    89  * (which contains neither endpoint).  The following idiom obtains a

    90  * view containing all of the key-value mappings in <tt>m</tt> whose keys

    91  * are between <tt>low</tt> and <tt>high</tt>, exclusive:<pre>

    92  *   SortedMap&lt;String, V&gt; sub = m.subMap(low+"\0", high);</pre>

    93  *

    94  * <p>This interface is a member of the

    95  * <a href="{@docRoot}/../technotes/guides/collections/index.html">

    96  * Java Collections Framework</a>.

    97  *

    98  * @param <K> the type of keys maintained by this map

    99  * @param <V> the type of mapped values

   100  *

   101  * @author  Josh Bloch

   102  * @see Map

   103  * @see TreeMap

   104  * @see SortedSet

   105  * @see Comparator

   106  * @see Comparable

   107  * @see Collection

   108  * @see ClassCastException

   109  * @since 1.2

   110  */

   111 

   112 public interface SortedMap<K,V> extends Map<K,V> {

   113     /**

   114      * Returns the comparator used to order the keys in this map, or

   115      * <tt>null</tt> if this map uses the {@linkplain Comparable

   116      * natural ordering} of its keys.

   117      *

   118      * @return the comparator used to order the keys in this map,

   119      *         or <tt>null</tt> if this map uses the natural ordering

   120      *         of its keys

   121      */

   122     Comparator<? super K> comparator();

   123 

   124     /**

   125      * Returns a view of the portion of this map whose keys range from

   126      * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If

   127      * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned map

   128      * is empty.)  The returned map is backed by this map, so changes

   129      * in the returned map are reflected in this map, and vice-versa.

   130      * The returned map supports all optional map operations that this

   131      * map supports.

   132      *

   133      * <p>The returned map will throw an <tt>IllegalArgumentException</tt>

   134      * on an attempt to insert a key outside its range.

   135      *

   136      * @param fromKey low endpoint (inclusive) of the keys in the returned map

   137      * @param toKey high endpoint (exclusive) of the keys in the returned map

   138      * @return a view of the portion of this map whose keys range from

   139      *         <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive

   140      * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>

   141      *         cannot be compared to one another using this map's comparator

   142      *         (or, if the map has no comparator, using natural ordering).

   143      *         Implementations may, but are not required to, throw this

   144      *         exception if <tt>fromKey</tt> or <tt>toKey</tt>

   145      *         cannot be compared to keys currently in the map.

   146      * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt>

   147      *         is null and this map does not permit null keys

   148      * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than

   149      *         <tt>toKey</tt>; or if this map itself has a restricted

   150      *         range, and <tt>fromKey</tt> or <tt>toKey</tt> lies

   151      *         outside the bounds of the range

   152      */

   153     SortedMap<K,V> subMap(K fromKey, K toKey);

   154 

   155     /**

   156      * Returns a view of the portion of this map whose keys are

   157      * strictly less than <tt>toKey</tt>.  The returned map is backed

   158      * by this map, so changes in the returned map are reflected in

   159      * this map, and vice-versa.  The returned map supports all

   160      * optional map operations that this map supports.

   161      *

   162      * <p>The returned map will throw an <tt>IllegalArgumentException</tt>

   163      * on an attempt to insert a key outside its range.

   164      *

   165      * @param toKey high endpoint (exclusive) of the keys in the returned map

   166      * @return a view of the portion of this map whose keys are strictly

   167      *         less than <tt>toKey</tt>

   168      * @throws ClassCastException if <tt>toKey</tt> is not compatible

   169      *         with this map's comparator (or, if the map has no comparator,

   170      *         if <tt>toKey</tt> does not implement {@link Comparable}).

   171      *         Implementations may, but are not required to, throw this

   172      *         exception if <tt>toKey</tt> cannot be compared to keys

   173      *         currently in the map.

   174      * @throws NullPointerException if <tt>toKey</tt> is null and

   175      *         this map does not permit null keys

   176      * @throws IllegalArgumentException if this map itself has a

   177      *         restricted range, and <tt>toKey</tt> lies outside the

   178      *         bounds of the range

   179      */

   180     SortedMap<K,V> headMap(K toKey);

   181 

   182     /**

   183      * Returns a view of the portion of this map whose keys are

   184      * greater than or equal to <tt>fromKey</tt>.  The returned map is

   185      * backed by this map, so changes in the returned map are

   186      * reflected in this map, and vice-versa.  The returned map

   187      * supports all optional map operations that this map supports.

   188      *

   189      * <p>The returned map will throw an <tt>IllegalArgumentException</tt>

   190      * on an attempt to insert a key outside its range.

   191      *

   192      * @param fromKey low endpoint (inclusive) of the keys in the returned map

   193      * @return a view of the portion of this map whose keys are greater

   194      *         than or equal to <tt>fromKey</tt>

   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 {@link Comparable}).

   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 NullPointerException if <tt>fromKey</tt> is null and

   202      *         this map does not permit null keys

   203      * @throws IllegalArgumentException if this map itself has a

   204      *         restricted range, and <tt>fromKey</tt> lies outside the

   205      *         bounds of the range

   206      */

   207     SortedMap<K,V> tailMap(K fromKey);

   208 

   209     /**

   210      * Returns the first (lowest) key currently in this map.

   211      *

   212      * @return the first (lowest) key currently in this map

   213      * @throws NoSuchElementException if this map is empty

   214      */

   215     K firstKey();

   216 

   217     /**

   218      * Returns the last (highest) key currently in this map.

   219      *

   220      * @return the last (highest) key currently in this map

   221      * @throws NoSuchElementException if this map is empty

   222      */

   223     K lastKey();

   224 

   225     /**

   226      * Returns a {@link Set} view of the keys contained in this map.

   227      * The set's iterator returns the keys in ascending order.

   228      * The set is backed by the map, so changes to the map are

   229      * reflected in the set, and vice-versa.  If the map is modified

   230      * while an iteration over the set is in progress (except through

   231      * the iterator's own <tt>remove</tt> operation), the results of

   232      * the iteration are undefined.  The set supports element removal,

   233      * which removes the corresponding mapping from the map, via the

   234      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,

   235      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>

   236      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>

   237      * operations.

   238      *

   239      * @return a set view of the keys contained in this map, sorted in

   240      *         ascending order

   241      */

   242     Set<K> keySet();

   243 

   244     /**

   245      * Returns a {@link Collection} view of the values contained in this map.

   246      * The collection's iterator returns the values in ascending order

   247      * of the corresponding keys.

   248      * The collection is backed by the map, so changes to the map are

   249      * reflected in the collection, and vice-versa.  If the map is

   250      * modified while an iteration over the collection is in progress

   251      * (except through the iterator's own <tt>remove</tt> operation),

   252      * the results of the iteration are undefined.  The collection

   253      * supports element removal, which removes the corresponding

   254      * mapping from the map, via the <tt>Iterator.remove</tt>,

   255      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,

   256      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not

   257      * support the <tt>add</tt> or <tt>addAll</tt> operations.

   258      *

   259      * @return a collection view of the values contained in this map,

   260      *         sorted in ascending key order

   261      */

   262     Collection<V> values();

   263 

   264     /**

   265      * Returns a {@link Set} view of the mappings contained in this map.

   266      * The set's iterator returns the entries in ascending key order.

   267      * The set is backed by the map, so changes to the map are

   268      * reflected in the set, and vice-versa.  If the map is modified

   269      * while an iteration over the set is in progress (except through

   270      * the iterator's own <tt>remove</tt> operation, or through the

   271      * <tt>setValue</tt> operation on a map entry returned by the

   272      * iterator) the results of the iteration are undefined.  The set

   273      * supports element removal, which removes the corresponding

   274      * mapping from the map, via the <tt>Iterator.remove</tt>,

   275      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and

   276      * <tt>clear</tt> operations.  It does not support the

   277      * <tt>add</tt> or <tt>addAll</tt> operations.

   278      *

   279      * @return a set view of the mappings contained in this map,

   280      *         sorted in ascending key order

   281      */

   282     Set<Map.Entry<K, V>> entrySet();

   283 }