oracle.jdevimpl.audit.util
Class KeyedSortedSet

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet
          oracle.jdevimpl.audit.util.KeyedSortedSet

All Implemented Interfaces:

java.lang.Iterable, java.util.Collection, java.util.Set, java.util.SortedSet

public class KeyedSortedSet
extends java.util.AbstractSet
implements java.util.SortedSet

A 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).

Nested Class Summary

static interface

KeyedSortedSet.Extractor

Constructor Summary

KeyedSortedSet(java.util.Comparator comparator, KeyedSortedSet.Extractor keyExtractor)

KeyedSortedSet(KeyedSortedSet.Extractor keyExtractor)

KeyedSortedSet(KeyedSortedSet set)

Method Summary

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)

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Constructor Detail

KeyedSortedSet

public KeyedSortedSet(KeyedSortedSet.Extractor keyExtractor)

KeyedSortedSet

public KeyedSortedSet(java.util.Comparator comparator,
                      KeyedSortedSet.Extractor keyExtractor)

KeyedSortedSet

public KeyedSortedSet(KeyedSortedSet set)

Method Detail

keyExtractor

public KeyedSortedSet.Extractor keyExtractor()

comparator

public java.util.Comparator comparator()

Specified by:

comparator in interface java.util.SortedSet

first

public java.lang.Object first()

Specified by:

first in interface java.util.SortedSet

headSet

public java.util.SortedSet headSet(java.lang.Object to)

Specified by:

headSet in interface java.util.SortedSet

last

public java.lang.Object last()

Specified by:

last in interface java.util.SortedSet

subSet

public java.util.SortedSet subSet(java.lang.Object from,
                                  java.lang.Object to)

Specified by:

subSet in interface java.util.SortedSet

tailSet

public java.util.SortedSet tailSet(java.lang.Object from)

Specified by:

tailSet in interface java.util.SortedSet

add

public boolean add(java.lang.Object object)

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.Set

Overrides:

add in class java.util.AbstractCollection

clear

public void clear()

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.Set

Overrides:

clear in class java.util.AbstractCollection

contains

public boolean contains(java.lang.Object object)

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.Set

Overrides:

contains in class java.util.AbstractCollection

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface java.util.Set

Overrides:

isEmpty in class java.util.AbstractCollection

iterator

public java.util.Iterator iterator()

This iterator does not support the remove operation.

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.Set

Specified by:

iterator in class java.util.AbstractCollection

remove

public boolean remove(java.lang.Object object)

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.Set

Overrides:

remove in class java.util.AbstractCollection

size

public int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.Set

Specified by:

size in class java.util.AbstractCollection