com.google.common.collect
Class SortedArraySet<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          com.google.common.collect.SortedArraySet<E>

All Implemented Interfaces:

Serializable, Iterable<E>, Collection<E>, Set<E>, SortedSet<E>

public final class SortedArraySet<E>
extends AbstractSet<E>
implements SortedSet<E>, Serializable

A sorted set that keeps its elements in a sorted ArrayList. Null elements are allowed when the SortedArraySet is constructed with an explicit comparator that supports nulls.

This class is useful when you may have many sorted sets that only have zero or one elements each. The performance of this implementation does not scale to large numbers of elements as well as TreeSet, but it is much more memory-efficient per entry.

Each SortedArraySet has a capacity, because it is backed by an ArrayList. The capacity is the size of the array used to store the elements in the set. It is always at least as large as the set size. As elements are added to the set, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has O(lg n) amortized time cost.

An application can increase the capacity of the set before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

This implementation is not synchronized. As with ArrayList, external synchronization is needed if multiple threads access a SortedArraySet instance concurrently and at least one adds or deletes any elements.

Author:

Matthew Harris, Mike Bostock

See Also:

Serialized Form

Constructor Summary

SortedArraySet()
Constructs a new empty sorted set, sorted according to the element's natural order, with an initial capacity of ten.

SortedArraySet(Collection<? extends E> collection)
Creates a new sorted set with the same elements as the specified collection.

SortedArraySet(Comparator<? super E> comparator)
Creates a new empty sorted set, sorted according to the specified comparator, with the initial capacity of ten.

SortedArraySet(Comparator<? super E> comparator, int initialCapacity)
Creates a new empty sorted set, sorted according to the specified comparator, with the specified initial capacity.

SortedArraySet(int initialCapacity)
Constructs a new empty sorted set, sorted according to the element's natural order, with the specified initial capacity.

SortedArraySet(SortedSet<E> set)
Creates a new sorted set with the same elements and the same ordering as the specified sorted set.

Method Summary

boolean	add(E o)
boolean	addAll(Collection<? extends E> c)
void	clear()
Comparator<? super E>	comparator() Returns the comparator associated with this sorted set, or Comparators.naturalOrder if it uses its elements' natural ordering.
boolean	contains(Object o)
void	ensureCapacity(int minCapacity) Increases the capacity of this sorted set, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
boolean	equals(Object o)
E	first()
SortedSet<E>	headSet(E toElement)
Iterator<E>	iterator()
E	last()
boolean	remove(Object o)
int	size()
SortedSet<E>	subSet(E fromElement, E toElement)
SortedSet<E>	tailSet(E fromElement)
void	trimToSize() Trims the capacity of this sorted set to be the set's current size.

Methods inherited from class java.util.AbstractSet

hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

containsAll, isEmpty, 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

containsAll, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

Constructor Detail

SortedArraySet

public SortedArraySet()

Constructs a new empty sorted set, sorted according to the element's natural order, with an initial capacity of ten. All elements inserted into the set must implement the Comparable interface. Furthermore, all such elements must be mutally comparable: e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint (for example, the user attempts to add a string element to a set whose elements are integers), the add method may throw a ClassCastException.

See Also:

Comparable, Comparators.naturalOrder()

SortedArraySet

public SortedArraySet(int initialCapacity)

Constructs a new empty sorted set, sorted according to the element's natural order, with the specified initial capacity. All elements inserted into the set must implement the Comparable interface. Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint (for example, the user attempts to add a string element to a set whose elements are integers), the add method may throw a ClassCastException.

Parameters:

initialCapacity - the initial capacity of the list

Throws:

IllegalArgumentException - if initialCapacity is negative

See Also:

Comparators.naturalOrder()

SortedArraySet

public SortedArraySet(Comparator<? super E> comparator)

Creates a new empty sorted set, sorted according to the specified comparator, with the initial capacity of ten. All elements inserted into the set must be mutually comparable by the specified comparator: comparator.compare(e1,e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint, the add method may throw a ClassCastException.

Parameters:

comparator - the comparator used to sort elements in this set

SortedArraySet

public SortedArraySet(Comparator<? super E> comparator,
                      int initialCapacity)

Creates a new empty sorted set, sorted according to the specified comparator, with the specified initial capacity. All elements inserted into the set must be mutually comparable by the specified comparator: comparator.compare(e1,e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint, the add method may throw a ClassCastException.

Parameters:

comparator - the comparator used to sort elements in this set

SortedArraySet

public SortedArraySet(Collection<? extends E> collection)

Creates a new sorted set with the same elements as the specified collection. If the specified collection is a SortedSet instance, this constructor behaves identically to SortedArraySet(SortedSet). Otherwise, the elements are sorted according to the elements' natural order; see SortedArraySet().

Parameters:

collection - the elements that will comprise the new set

Throws:

ClassCastException - if the elements in the specified collection are not mutually comparable

SortedArraySet

public SortedArraySet(SortedSet<E> set)

Creates a new sorted set with the same elements and the same ordering as the specified sorted set.

Parameters:

set - the set whose elements will comprise the new set

Method Detail

ensureCapacity

public void ensureCapacity(int minCapacity)

Increases the capacity of this sorted set, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

Parameters:

minCapacity - the desired minimum capacity

trimToSize

public void trimToSize()

Trims the capacity of this sorted set to be the set's current size. An application can use this operation to minimize the storage of a sorted set.

add

public boolean add(E o)

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

Overrides:

add in class AbstractCollection<E>

addAll

public boolean addAll(Collection<? extends E> c)

Specified by:

addAll in interface Collection<E>

Specified by:

addAll in interface Set<E>

Overrides:

addAll in class AbstractCollection<E>

clear

public void clear()

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

Overrides:

clear in class AbstractCollection<E>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface Set<E>

Overrides:

contains in class AbstractCollection<E>

equals

public boolean equals(Object o)

Specified by:

equals in interface Collection<E>

Specified by:

equals in interface Set<E>

Overrides:

equals in class AbstractSet<E>

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Set<E>

Specified by:

iterator in class AbstractCollection<E>

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface Set<E>

Overrides:

remove in class AbstractCollection<E>

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

Specified by:

size in class AbstractCollection<E>

comparator

public Comparator<? super E> comparator()

Returns the comparator associated with this sorted set, or Comparators.naturalOrder if it uses its elements' natural ordering.

Specified by:

comparator in interface SortedSet<E>

subSet

public SortedSet<E> subSet(E fromElement,
                           E toElement)

Specified by:

subSet in interface SortedSet<E>

headSet

public SortedSet<E> headSet(E toElement)

Specified by:

headSet in interface SortedSet<E>

tailSet

public SortedSet<E> tailSet(E fromElement)

Specified by:

tailSet in interface SortedSet<E>

first

public E first()

Specified by:

first in interface SortedSet<E>

last

public E last()

Specified by:

last in interface SortedSet<E>