Sunday, March 13, 2011

The SortedMap Interface

A SortedMap(in the API reference documentation)is a Map(in the API reference documentation)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 Comparators 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(in the API reference documentation).


Map Operations in SortedMap

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 the sorted map's Collection-views traverse the collections in order.
  • The arrays returned by the Collection-views' toArray operations contains the keys, values, or entries in 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 order.


Standard Constructors in SortedMap interface

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.


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 SortedSet with only trivial modifications.

No comments:

Post a Comment