public class KeyedSortedSet
extends java.util.AbstractSet
implements java.util.SortedSet
SortedSet
of elements with internal, ordered keys. The keys are
extracted from the elements by an KeyedSortedSet.Extractor
object supplied when the
set is created. The keys must be mutually comparable with the elements, and
must also be suitable for use as hash keys.
This implementation uses the keys to improve performance with large numbers of elements while maintaining element order and without imposing a large memory penalty. The basic approach is to partition the elements by key values and to use the keys to quickly narrow element searches down to the correct partition. Its effectiveness depends on the elements being evenly distributed among keys (loosely, performance should be more or less O(nlogn) where n is the size of the largest partition). The partitions are maintained redundantly in two collections, a sorted set of partitions and an unsorted hash map from key to partition. The sorted set is used when ordering is important (e.g., in the iterator); the faster hash map is used when ordering is not important. The hash map may have empty partitions in it which are not in the sorted set (when subsets are created which have keys for which the partition is empty).
Modifier and Type | Class and Description |
---|---|
static interface |
KeyedSortedSet.Extractor |
Constructor and Description |
---|
KeyedSortedSet(java.util.Comparator comparator,
KeyedSortedSet.Extractor keyExtractor) |
KeyedSortedSet(KeyedSortedSet.Extractor keyExtractor) |
KeyedSortedSet(KeyedSortedSet set) |
Modifier and Type | Method and Description |
---|---|
boolean |
add(java.lang.Object object) |
void |
clear() |
java.util.Comparator |
comparator() |
boolean |
contains(java.lang.Object object) |
java.lang.Object |
first() |
java.util.SortedSet |
headSet(java.lang.Object to) |
boolean |
isEmpty() |
java.util.Iterator |
iterator()
This iterator does not support the
remove operation. |
KeyedSortedSet.Extractor |
keyExtractor() |
java.lang.Object |
last() |
boolean |
remove(java.lang.Object object) |
int |
size() |
java.util.SortedSet |
subSet(java.lang.Object from,
java.lang.Object to) |
java.util.SortedSet |
tailSet(java.lang.Object from) |
addAll, containsAll, retainAll, toArray, toArray, toString
public KeyedSortedSet(KeyedSortedSet.Extractor keyExtractor)
public KeyedSortedSet(java.util.Comparator comparator, KeyedSortedSet.Extractor keyExtractor)
public KeyedSortedSet(KeyedSortedSet set)
public KeyedSortedSet.Extractor keyExtractor()
public java.util.Comparator comparator()
comparator
in interface java.util.SortedSet
public java.lang.Object first()
first
in interface java.util.SortedSet
public java.util.SortedSet headSet(java.lang.Object to)
headSet
in interface java.util.SortedSet
public java.lang.Object last()
last
in interface java.util.SortedSet
public java.util.SortedSet subSet(java.lang.Object from, java.lang.Object to)
subSet
in interface java.util.SortedSet
public java.util.SortedSet tailSet(java.lang.Object from)
tailSet
in interface java.util.SortedSet
public boolean add(java.lang.Object object)
add
in interface java.util.Collection
add
in interface java.util.Set
add
in class java.util.AbstractCollection
public void clear()
clear
in interface java.util.Collection
clear
in interface java.util.Set
clear
in class java.util.AbstractCollection
public boolean contains(java.lang.Object object)
contains
in interface java.util.Collection
contains
in interface java.util.Set
contains
in class java.util.AbstractCollection
public boolean isEmpty()
isEmpty
in interface java.util.Collection
isEmpty
in interface java.util.Set
isEmpty
in class java.util.AbstractCollection
public java.util.Iterator iterator()
remove
operation.iterator
in interface java.lang.Iterable
iterator
in interface java.util.Collection
iterator
in interface java.util.Set
iterator
in class java.util.AbstractCollection
public boolean remove(java.lang.Object object)
remove
in interface java.util.Collection
remove
in interface java.util.Set
remove
in class java.util.AbstractCollection
public int size()
size
in interface java.util.Collection
size
in interface java.util.Set
size
in class java.util.AbstractCollection