The Java TM Tutorial

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

Trail: Collections
Lesson: Interfaces

## The SortedSet Interface

> A `SortedSet` is a `Set` that maintains its elements in ascending order, sorted according to the elements' natural order, or according to a `Comparator` provided at `SortedSet` creation time. (Natural order and `Comparator`s are discussed in the previous section, on Object Ordering.) In addition to the normal `Set` operations, the `Set` interface provides operations for:
> - Range-view: Performs arbitrary range operations on the sorted set.
> - Endpoints: Returns the first or last element in the sorted set.
> - Comparator access: Returns the `Comparator` used to sort the set (if any).
> The `SortedSet` interface is shown below:

> >     public interface SortedSet extends Set {
> >         // Range-view
> >         SortedSet subSet(Object fromElement, Object toElement);
> >         SortedSet headSet(Object toElement);
> >         SortedSet tailSet(Object fromElement);

> >         // Endpoints
> >         Object first();
> >         Object last();

> >         // Comparator access
> >         Comparator comparator();
> >     }

### Set Operations

> The operations that `SortedSet` inherits from `Set` behave identically on sorted sets and normal sets with two exceptions:
> - The `Iterator` returned by the `iterator` operation traverses the sorted set in order.
> - The array returned by `toArray` contains the sorted set's elements in order.
> Although the interface doesn't guarantee it, the `toString` method of the JDK's `SortedSet` implementations returns a string containing all the elements of the sorted set, in order.

### Standard Constructors

> By convention, all `Collection` implementations provide a standard constructor that takes a `Collection`, and `SortedSet` implementations are no exception. This constructor creates a `SortedSet` object that orders its elements according to their natural order. Additionally, by convention, `SortedSet` implementations provide two other standard constructors:
> - One that takes a `Comparator` and returns a new (empty) `SortedSet` sorted according to the specified `Comparator`.
> - One that takes a `SortedSet` and returns a new `SortedSet` containing the same elements as the given `SortedSet`, and sorted according to the same `Comparator` (or using the elements' natural ordering, if the specified `SortedSet` did too). Note that the compile-time type of the argument determines whether this constructor is invoked in preference to the ordinary `Set` constructor, and not the runtime type!
> The first of these standard constructors is the normal way to create an empty `SortedSet` with an explicit `Comparator`. The second is similar in spirit to the standard `Collection` constructor: it creates a copy of a `SortedSet` with the same ordering, but with a programmer-specified implementation type.

### Range-view Operations

> The Range-view operations are somewhat analogous to those provided by the `List` interface, but there is one big difference. Range-views of a sorted set remain valid even if the backing sorted set is modified directly. This is feasible because the endpoints of a range view of a sorted set are absolute points in the element-space, rather than specific elements in the backing collection (as is the case for lists). A range-view of a sorted set is really just a window onto whatever portion of the set lies in the designated part of the element-space. Changes to the range-view write back to the backing sorted set and vice-versa. Thus, it's OK to use range-views on sorted sets for long periods of time (unlike range-views on lists).

> Sorted sets provide three range-view operations. The first, `subSet` takes two endpoints (like `subList`). Rather than indices, the endpoints are objects. They must be comparable to the elements in the sorted set (using the set's `Comparator` or the natural ordering of its elements, whichever the set uses to order itself). Like `subList` the range is half-open, including its low endpoint but excluding the high one.

> Thus, the following one-liner tells you how many words between "doorbell" and "pickle", including "doorbell" but excluding "pickle", are contained in a `SortedSet` of strings called dictionary:

> >     int count = dictionary.subSet("doorbell", "pickle").size();

> Similarly, the following one-liner removes all of the elements beginning with the letter "`f`" (a rather heavy-handed approach to censorship?):

> >     dictionary.subSet("f", "g").clear();

> A similar trick can be used to print a table telling you how many words begin with each letter:

> >     for (char ch='a'; ch<='z'; ch++) {
> >         String from = new String(new char[] {ch});
> >         String to = new String(new char[] {(char)(ch+1)});
> >         System.out.println(from + ": " +
> >                            dictionary.subSet(from, to).size());
> >     }

> Suppose that you want to view a closed interval (which contains both its endpoints) instead of an open interval. If the element type allows for the calculation of the successor a given value (in the element-space), merely request the `subSet` from `lowEndpoint` to `successor(highEndpoint)` . Although it isn't entirely obvious, the successor of a string `s` in `String`'s natural ordering is `s+"\0"` (that is, `s` with a null character appended).

> Thus, the following one-liner tells you how many words between "doorbell" and "pickle," including "doorbell" and "pickle," are contained in a the dictionary:

> >     int count = dictionary.subSet("doorbell", "pickle\0").size();

> A similarly technique can be used to view an open interval (which contains neither endpoint). The open interval view from `lowEndpoint` to `highEndpoint` is the half-open interval from `successor(lowEndpoint)` to `highEndpoint`. To calculate the number of words between "doorbell" and "pickle", excluding both:

> >     int count = dictionary.subSet("doorbell\0", "pickle").size();

> The `SortedSet` interface contains two more range-view operations, `headSet` and `tailSet`, both of which take a single `Object` argument. The former returns a view of the initial portion of the backing `SortedSet`, up to but not including the specified object. The latter returns a view of the final portion of the the backing `SortedSet`, beginning with the specified object, and continuing to the end of the backing `SortedSet` Thus, the following code allows you to view the dictionary as two disjoint "volumes" (a-m and n-z):

> >     SortedSet volume1 = dictionary.headSet("n");
> >     SortedSet volume2 = dictionary.tailSet("n");

### Endpoint Operations

> The `SortedSet` interface contains operations to return the first and last elements in the sorted set, called (not surprisingly) `first` and `last`. In addition to their obvious uses, `last` allows a workaround for a deficiency in the `SortedSet` interface. One thing you'd like to do with a `SortedSet` is to go into the interior of the set and iterate forwards or backwards. It's easy enough to go forwards from the interior: Just get a `tailSet` and iterate over it. Unfortunately, there's no easy way to go backwards.

> The following idiom obtains the first element in a sorted set that is less than a specified object `o` in the element-space:

> >     Object predecessor = ss.headSet(o).last();

> This is a fine way to go one element backwards from a point in the interior of a sorted set. It could be applied repeatedly to iterate backwards, but unfortunately this is very inefficient, requiring a lookup for each element returned.

### Comparator Accessor

> The `SortedSet` interface contains an accessor method called `comparator` that returns the `Comparator` used to sort the set, or `null` if the set is sorted according to the natural order of its elements. This method is provided so that sorted sets can be copied into new sorted sets with the same ordering. It is used by the standard `SortedSet` constructor, described above.

| Start of Tutorial > Start of Trail | Search