Start of Tutorial > Start of Trail > Start of Lesson |
Search
Feedback Form |
ASortedSet
is aSet
that maintains its elements in ascending order, sorted according to the elements' natural order or according to aComparator
provided atSortedSet
creation time. In addition to the normalSet
operations, theSortedSet
interface provides operations for:The
- Range view: Allows arbitrary range operations on the sorted set.
- Endpoints: Returns the first or last element in the sorted set.
- Comparator access: Returns the
Comparator
, if any, used to sort the set.SortedSet
interface follows:public interface SortedSet<E> extends Set<E> { //Range-view SortedSet<E> subSet(E fromElement, E toElement); SortedSet<E> headSet(E toElement); SortedSet<E> tailSet(E fromElement); //Endpoints E first(); E last(); //Comparator access ComparatorComparator<? super E> comparator(); }
The operations thatSortedSet
inherits fromSet
behave identically on sorted sets and normal sets with two exceptions:Although the interface doesn't guarantee it, the
- The
Iterator
returned by theiterator
operation traverses the sorted set in order.- The array returned by
toArray
contains the sorted set's elements in order.toString
method of the Java platform'sSortedSet
implementations returns a string containing all the elements of the sorted set, in order.
By convention, all general-purposeCollection
implementations provide a standard conversion constructor that takes aCollection
;SortedSet
implementations are no exception. InTreeSet
, this constructor creates an instance that sorts its elements according to their natural order. This was probably a mistake. It would have been better to check dynamically if the specified collection were aSortedSet
instance, and if so, to sort the newTreeSet
according to the same criterion (comparator or natural ordering). BecauseTreeSet
took the approach that it did, it also provides a constructor that takes aSortedSet
and returns a newTreeSet
containing the same elements sorted according to the same criterion. Note that it is the compile-time type of the argument, not its runtime type, that determines which of these two constructors is invoked (and whether the sorting criterion is preserved).
SortedSet
implementations also provide by convention a constructor that takes aComparator
and returns an empty set sorted according to the specifiedComparator
. Ifnull
is passed to this constructor, it returns a set that sorts its elements according to their natural order.
The range-view operations are somewhat analogous to those provided by theList
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 okay 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, likesubList
. Rather than indices, the endpoints are objects and must be comparable to the elements in the sorted set, using the set'sComparator
or the natural ordering of its elements, whichever the set uses to order itself. LikesubList
, the range is half open, including its low endpoint but excluding the high one.Thus, the following one of code tells you how many words between "doorbell" and "pickle," including "doorbell" but excluding "pickle," are contained in a
SortedSet
of strings calleddictionary
:Similarly, the following one-liner removes all the elements beginning with the letter "int count = dictionary.subSet("doorbell", "pickle").size();f
":A similar trick can be used to print a table telling you how many words begin with each letter:dictionary.subSet("f", "g").clear();Suppose that you want to view a closed interval, which contains both of its endpoints, instead of an open interval. If the element type allows for the calculation of the successor of a given value in the element space, merely request thefor (char ch = 'a'; ch <= 'z'; ) { String from = String.valueOf(ch++); String to = String.valueOf(ch); System.out.println(from + ": " + dictionary.subSet(from, to).size()); }subSet
fromlowEndpoint
tosuccessor(highEndpoint)
. Although it isn't entirely obvious, the successor of a strings
inString
's natural ordering iss + "\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 the dictionary:
A similar technique can be used to view an open interval, which contains neither endpoint. The open-interval view fromcount = dictionary.subSet("doorbell", "pickle\0").size();lowEndpoint
tohighEndpoint
is the half-open interval fromsuccessor(lowEndpoint)
tohighEndpoint
. To calculate the number of words between "doorbell" and "pickle," excluding both:Thecount = dictionary.subSet("doorbell\0", "pickle").size();SortedSet
interface contains two more range-view operations,headSet
andtailSet
, both of which take a singleObject
argument. The former returns a view of the initial portion of the backingSortedSet
, up to but not including the specified object. The latter returns a view of the final portion of the backingSortedSet
, beginning with the specified object and continuing to the end of the backingSortedSet
. Thus, the following code allows you to view the dictionary as two disjoint "volumes" (a m and n z):SortedSet<String> volume1 = dictionary.headSet("n"); SortedSet<String>> volume2 = dictionary.tailSet("n");
TheSortedSet
interface contains operations to return the first and last elements in the sorted set, called (not surprisingly)first
andlast
. In addition to their obvious uses,last
allows a workaround for a deficiency in theSortedSet
interface. One thing you'd like to do with aSortedSet
is to go into the interior of the set and iterate forward or backward. It's easy enough to go forward from the interior: Just get atailSet
and iterate over it. Unfortunately, there's no easy way to go backwards.The following idiom obtains the first element that is less than a specified object
o
in the element-space:This is a fine way to go one element backward from a point in the interior of a sorted set. It could be applied repeatedly to iterate backward, but this is very inefficient, requiring a lookup for each element returned.Object predecessor = ss.headSet(o).last();
TheSortedSet
interface contains an accessor method calledcomparator
that returns theComparator
used to sort the set, ornull
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 theSortedSet
constructor, described previously.
Start of Tutorial > Start of Trail > Start of Lesson |
Search
Feedback Form |
Copyright 1995-2005 Sun Microsystems, Inc. All rights reserved.