com.neoworks.util
Interface SortedMultiMap

All Superinterfaces:

MultiMap

public interface SortedMultiMap

extends MultiMap

A multimap that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted multimap creation time. This order is reflected when iterating over the sorted multimap's collection views (returned by the entrySet, keys and values methods). Several additional operations are provided to take advantage of the ordering.

All keys inserted into a sorted multimap must implement the Comparable interface (or be accepted by the specified comparator). Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) (or comparator.compare(k1, k2)) must not throw a ClassCastException for any elements k1 and k2 in the sorted multimap. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a ClassCastException.

Note that the ordering maintained by a sorted multimap (whether or not an explicit comparator is provided) must be onsistent with equals if the sorted multimap is to correctly implement the MultiMap interface. (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the MultiMap interface is defined in terms of the equals operation, but a sorted multimap performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted multimap, equal.

All general-purpose sorted multimap implementation classes should provide four "standard" constructors: 1) A void (no arguments) constructor, which creates an empty sorted multimap sorted according to the natural order of its keys. 2) A constructor with a single argument of type Comparator, which creates an empty sorted multimap sorted according to the specified comparator. 3) A constructor with a single argument of type MultiMap, which creates a new multimap with the same key-value mappings as its argument, sorted according to the keys' natural ordering. 4) A constructor with a single argument of type sorted multimap, which creates a new sorted multimap with the same key-value mappings and the same ordering as the input sorted multimap. There is no way to enforce this recommendation (as interfaces cannot contain constructors) but the SDK implementation (TreeMap) complies.

Version:

0.1

Author:

Stuart Farnan stuart@neoworks.com

Nested Class Summary

Nested classes inherited from class com.neoworks.util.MultiMap

MultiMap.Entry

Method Summary

java.util.Comparator	comparator() Returns the comparator associated with this sorted multimap, or null if it uses its keys' natural ordering.
java.lang.Object	firstKey() Returns the first (lowest) key currently in this sorted multimap.
SortedMultiMap	headMap(java.lang.Object toKey) Returns a view of the portion of this sorted multimap whose keys are strictly less than toKey.
java.lang.Object	lastKey() Returns the last (highest) key currently in this sorted multimap.
SortedMultiMap	subMap(java.lang.Object fromKey, java.lang.Object toKey) Returns a view of the portion of this sorted multimap whose keys range from fromKey, inclusive, to toKey, exclusive.
SortedMultiMap	tailMap(java.lang.Object fromKey) Returns a view of the portion of this sorted multimap whose keys are greater than or equal to fromKey.

Methods inherited from interface com.neoworks.util.MultiMap

clear, containsKey, containsValue, entrySet, equals, get, hashCode, isEmpty, keys, put, putAll, remove, remove, size, uniqueKeys, values

Method Detail

comparator

public java.util.Comparator comparator()

Returns the comparator associated with this sorted multimap, or null if it uses its keys' natural ordering.

Returns:

the comparator associated with this sorted multimap, or null if it uses its keys' natural ordering.

subMap

public SortedMultiMap subMap(java.lang.Object fromKey,
                             java.lang.Object toKey)

Returns a view of the portion of this sorted multimap whose keys range from fromKey, inclusive, to toKey, exclusive. (If fromKey and toKey are equal, the returned sorted map is empty.) The returned sorted multimap is backed by this sorted multimap, so changes in the returned sorted multimap are reflected in this sorted multimap, and vice-versa. The returned Map supports all optional multimap operations that this sorted multimap supports.

The multimap returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.

Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you need a closed range (which includes both endpoints), and the key type allows for calculation of the successor a given key, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that m is a multimap whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, inclusive:

MultiMap sub = m.subMap(low, high+"\0");

A similarly technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, exclusive:

MultiMap sub = m.subMap(low+"\0", high);

Parameters:

fromKey - Low endpoint (inclusive) of the subMap.

toKey - High endpoint (exclusive) of the subMap.

Returns:

A view of the specified range within this sorted multimap.

headMap

public SortedMultiMap headMap(java.lang.Object toKey)

Returns a view of the portion of this sorted multimap whose keys are strictly less than toKey. The returned sorted multimap is backed by this sorted multimap, so changes in the returned sorted multimap are reflected in this sorted multimap, and vice-versa. The returned multimap supports all optional map operations that this sorted multimap supports.

The multimap returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.

Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded by successor(highEndpoint). For example, suppose that suppose that m is a multimap whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are less than or equal to * high:

MultiMap head = m.headMap(high+"\0");

Parameters:

toKey - High endpoint (exclusive) of the subMap.

Returns:

A view of the specified initial range of this sorted map.

tailMap

public SortedMultiMap tailMap(java.lang.Object fromKey)

Returns a view of the portion of this sorted multimap whose keys are greater than or equal to fromKey. The returned sorted multimap is backed by this sorted multimap, so changes in the returned sorted multimap are reflected in this sorted multimap, and vice-versa. The returned multimap supports all optional multimap operations that this sorted multimap supports.

The multimap returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.

Note: this method always returns a view that contains its (low endpoint. If you need a view that does not contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a tailMap bounded by successor(lowEndpoint). For example, suppose that suppose that m is a multimap whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are strictly greater than low:

MultiMap tail = m.tailMap(low+"\0");

Parameters:

fromKey - Low endpoint (inclusive) of the tailMap.

Returns:

A view of the specified final range of this sorted multimap.

firstKey

public java.lang.Object firstKey()

Returns the first (lowest) key currently in this sorted multimap.

Returns:

the first (lowest) key currently in this sorted multimap.

lastKey

public java.lang.Object lastKey()

Returns the last (highest) key currently in this sorted multimap.

Returns:

the last (highest) key currently in this sorted multimap.