The JavaTM Tutorial

| Start of Tutorial > Start of Trail > Start of Lesson | Search

Trail: Collections
Lesson: Interfaces

## The SortedMap Interface

> A `SortedMap` is a `Map` that maintains its entries in ascending order, sorted according to the keys' natural order, or according to a `Comparator` provided at `SortedMap` creation time. (Natural order and `Comparator`s are discussed in the section on Object Ordering.) In addition to the normal `Map` operations, the `Map` interface provides operations for:
> - Range-view: Performs arbitrary range operations on the sorted map.
> - Endpoints: Returns the first or last key in the sorted map.
> - Comparator access: Returns the `Comparator` used to sort the map (if any).

> >     public interface SortedMap extends Map {
> >         Comparator comparator();

> >         SortedMap subMap(Object fromKey, Object toKey);
> >         SortedMap headMap(Object toKey);
> >         SortedMap tailMap(Object fromKey);

> >         Object first();
> >         Object last();
> >     }

> This interface is the `Map` analogue of `SortedSet`.

### Map Operations

> The operations that `SortedMap` inherits from `Map` behave identically on sorted maps and normal maps with two exceptions:
> - The `Iterator` returned by the `iterator` operation on any of the sorted map's `Collection`-views traverse the collections in key-order.
> - The arrays returned by the `Collection`-views' `toArray` operations contain the keys, values, or entries in key-order.
> Although it isn't guaranteed by the interface, the `toString` method of the `Collection`-views in all the JDK's `SortedMap` implementations returns a string containing all the elements of the view, in key-order.

> For example, consider the following snippet:

> >     SortedMap m = new TreeMap();
> >     m.put("Sneezy", "common cold");
> >     m.put("Sleepy", "narcolepsy");
> >     m.put("Grumpy", "seasonal affective disorder");

> >     System.out.println(m.keySet());
> >     System.out.println(m.values());
> >     System.out.println(m.entrySet());

> Running this snippet produces this output:

> >     [Grumpy, Sleepy, Sneezy]
> >     [seasonal affective disorder, narcolepsy, common cold]
> >     [Grumpy=seasonal affective disorder, Sleepy=narcolepsy, Sneezy=common cold]

### Standard Constructors

> By convention, all `Map` implementations provide a standard constructor that takes a `Map`, and `SortedMap` implementations are no exception. This constructor creates a `SortedMap` object that orders its entries according to their keys' natural order. Additionally, by convention, `SortedMap` implementations provide two other standard constructors:
> - One that takes a `Comparator` and returns a new (empty) `SortedMap` sorted according to the specified `Comparator`.
> - One that takes a `SortedMap` and returns a new `SortedMap` containing the same mappings as the given `SortedMap`, and sorted according to the same `Comparator` (or using the elements' natural ordering, if the specified `SortedMap` did too). Note that it is the compile-time type of the argument that determines whether this constructor is invoked in preference to the ordinary `Map` constructor, and not its runtime type!

> The first of these standard constructors is the normal way to create an empty `SortedMap` with an explicit `Comparator`. The second is similar in spirit to the standard `Map` constructor: It creates a copy of a `SortedMap` with the same ordering, but with a programmer specified implementation type.

> The following snippet illustrates how this works:

> >     final Comparator FUNNY_COMPARATOR = ... ;
> >     Map m = new TreeMap(FUNNY_COMPARATOR);

> >     // ... code to populate m

> >     Map m2 = new TreeMap(m);           // invokes TreeMap(Map)
> >     Map m3 = new TreeMap((SortedMap)m) // invokes TreeMap(SortedMap)

> Note that `m2.comparator()` will return `null` while `m3.comparator()` will return `FUNNY_COMPARATOR`. In other words, `m2` is sorted according to its keys' natural ordering, while `m3` is sorted according to the ordering induced by `FUNNY_COMPARATOR`.

### Comparison to SortedSet

> Because this interface is a precise `Map` analogue of `SortedSet`, all of the idioms and code examples in the `SortedSet` section apply to `SortedMap`, with only trivial modifications.

| Start of Tutorial > Start of Trail > Start of Lesson | Search