edu.rice.cs.plt.collect
Class ExternallySortedSet<T,C extends Comparable<? super C>>

java.lang.Object
  edu.rice.cs.plt.collect.ExternallySortedSet<T,C>

All Implemented Interfaces:

SizedIterable<T>, Iterable<T>

public class ExternallySortedSet<T,C extends Comparable<? super C>>
extends Object
implements SizedIterable<T>

A container class that almost implements the SortedSet interface; the difference is that add() takes two parameters -- an element, along with a corresponding Comparable that will be used to sort the set. Thus, the set is not sorted based on any operations defined for the element type; rather, it is sorted according to an external orderBy value. The subSet(), etc., methods are also adjusted to take in orderBy values rather than set elements.

The result is a set that works essentially like a TreeSet of Pairs in which one of the Pair elements is a Comparable, and for which a Comparator is correctly defined. One significant difference is that this implementation does not return true for the expression add(1, 1) && add(1, 2), while the explicit Pair implementation would (assuming the Set were initially empty).

Note: the implementation relies heavily on hashing, so good performance is dependent on elements of the set having an efficient hashCode() implementation.

Constructor Summary

ExternallySortedSet()
Creates an empty set.

Method Summary

boolean	add(T element, C orderBy) Add element to the set, sorted by orderBy.
boolean	addAll(ExternallySortedSet<? extends T,? extends C> s) Add every element of s to this set (if it is not already present).
void	clear() Removes every element of this set.
boolean	contains(Object element)
boolean	containsAll(Iterable<?> i)
T	first()
boolean	hasFixedSize() true if this iterable is known to have a fixed size.
ExternallySortedSet<T,C>	headSet(C to)
boolean	isEmpty() Whether the iterable does not contain any elements.
boolean	isInfinite() true if the iterable is known to have infinite size.
boolean	isStatic() true if this iterable is unchanging.
Iterator<T>	iterator()
T	last()
boolean	remove(Object element) Removes the element specified from the set.
boolean	removeAll(Iterable<?> i) Removes every element of this set that is in c.
boolean	retainAll(Collection<?> c) Removes every element of this set that is not in c.
boolean	retainAll(ExternallySortedSet<?,?> s) Removes every element of this set that is not in s.
int	size() Compute the number of elements in the iterable.
int	size(int bound) Compute the number of elements in the iterable, up to the given bound.
ExternallySortedSet<T,C>	subSet(C from, C to)
ExternallySortedSet<T,C>	tailSet(C from)
Object[]	toArray()
<S> S[]	toArray(S[] a)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ExternallySortedSet

public ExternallySortedSet()

Creates an empty set.

Method Detail

isEmpty

public boolean isEmpty()

Description copied from interface: SizedIterable

Whether the iterable does not contain any elements.

Specified by:

isEmpty in interface SizedIterable<T>

size

public int size()

Description copied from interface: SizedIterable

Compute the number of elements in the iterable. If the size is infinite or too large to be represented as an int, Integer.MAX_VALUE should be returned. Otherwise, next() may be safely invoked on the iterator exactly this number of times.

Specified by:

size in interface SizedIterable<T>

size

public int size(int bound)

Description copied from interface: SizedIterable

Compute the number of elements in the iterable, up to the given bound. If the size is infinite or greater than bound, bound is returned.

Specified by:

size in interface SizedIterable<T>

Parameters:

bound - Maximum result. Assumed to be nonnegative.

isInfinite

public boolean isInfinite()

Description copied from interface: SizedIterable

true if the iterable is known to have infinite size. If true, an iterator over the iterable in its current state will never return false from hasNext().

Specified by:

isInfinite in interface SizedIterable<T>

hasFixedSize

public boolean hasFixedSize()

Description copied from interface: SizedIterable

true if this iterable is known to have a fixed size. This is the case if the iterable is immutable, or if changes can only replace values, not remove or add them. An infinite iterable may be fixed if it is guaranteed to never become finite.

Specified by:

hasFixedSize in interface SizedIterable<T>

isStatic

public boolean isStatic()

Description copied from interface: SizedIterable

true if this iterable is unchanging. This implies that hasFixedSize() is true, and that iterator() will always return the same (either == or equal() and immutable) elements in the same order. ("Immutable" here means that equals() invocations are consistent over time -- if two objects are equal, they will never become inequal, and vice versa.)

Specified by:

isStatic in interface SizedIterable<T>

contains

public boolean contains(Object element)

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<T>

Returns:

An Iterator over the elements of the set in their sorted order. The iterator supports Iterator.remove().

toArray

public Object[] toArray()

Returns:

An array of the set elements in their sorted order. As in the Set interface, changes to the array will not be reflected in the set.

toArray

public <S> S[] toArray(S[] a)

Returns:

An array of the set elements in their sorted order. As in the Set interface, changes to the array will not be reflected in the set.

add

public boolean add(T element,
                   C orderBy)

Add element to the set, sorted by orderBy.

Returns:

true iff element was not already in the set and could be added.

Throws:

IllegalArgumentException - if this is a subset of a larger set, and the element being added is outside the specified bounds.

NullPointerException - if element is null

remove

public boolean remove(Object element)

Removes the element specified from the set.

Returns:

true iff the set contained element.

containsAll

public boolean containsAll(Iterable<?> i)

Returns:

true iff the set contains each of the elements in i.

addAll

public boolean addAll(ExternallySortedSet<? extends T,? extends C> s)

Add every element of s to this set (if it is not already present).

Returns:

true iff the operation modified this set.

retainAll

public boolean retainAll(Collection<?> c)

Removes every element of this set that is not in c.

Returns:

true iff the operation modified this set.

retainAll

public boolean retainAll(ExternallySortedSet<?,?> s)

Removes every element of this set that is not in s.

Returns:

true iff the operation modified this set.

removeAll

public boolean removeAll(Iterable<?> i)

Removes every element of this set that is in c.

Returns:

true iff the operation modified this set.

clear

public void clear()

Removes every element of this set.

subSet

public ExternallySortedSet<T,C> subSet(C from,
                                       C to)

Returns:

A set containing every element in this set sorted from from (inclusive) to to (exclusive). The result is backed by this set and bounded by from and to; changes to either this or the result are reflected by both.

Throws:

IllegalArgumentException - if from or to is outside this set's bounds

headSet

public ExternallySortedSet<T,C> headSet(C to)

Returns:

A set containing every element in this set sorted before to (exclusive). The result is backed by this set, so changes to either are reflected by both.

Throws:

IllegalArgumentException - if to is outside this set's bounds

tailSet

public ExternallySortedSet<T,C> tailSet(C from)

Returns:

A set containing every element in this set sorted after from (inclusive). The result is backed by this set, so changes to either are reflected by both.

Throws:

IllegalArgumentException - if from is outside this set's bounds

first

public T first()

last

public T last()