public class ArraySortedSet<E>
extends java.util.AbstractSet<E>
implements java.util.SortedSet<E>, java.lang.Cloneable
ArraySortedSet
is an array implementation of the SortedSet
interface. This implementation has significantly lower memory overhead than TreeSet
(about 4 bytes per element vs. 40 bytes per element) and is intended to be a replacement for the use of TreeSet
for sets containing under 3000 elements.
The main drawback of the array implementation is its worst-case performance characteristics when adding or removing elements in reverse sorted order.
This implementation does not support null
elements.
Constructor and Description |
---|
ArraySortedSet()
Construct a new
ArraySortedSet of default size, using the default sorting order of the objects added to the set. |
ArraySortedSet(java.util.Collection<? extends E> initialContents, java.util.Comparator<? super E> comparator)
Construct a new
ArraySortedSet with the given contents and comparator. |
ArraySortedSet(java.util.Comparator<? super E> comparator)
Construct a new
ArraySortedSet of default size, using the specified comparator. |
ArraySortedSet(E[] initialContents, java.util.Comparator<? super E> comparator)
Construct a new
ArraySortedSet with the given contents and comparator. |
ArraySortedSet(int initialSize)
Construct a new
ArraySortedSet of specified size, using the default sorting order of the objects addded to the set. |
ArraySortedSet(int initialSize, java.util.Comparator<? super E> comparator)
Construct a new
ArraySortedSet of specified size, using the specified comparator. |
Modifier and Type | Method and Description |
---|---|
boolean |
add(E o)
Adds the specified element to this set if it is not already present (optional operation).
|
void |
addAll(E[] objects)
Adds all objects in the specified array to the set.
|
void |
clear()
Removes all of the elements from this set (optional operation).
|
java.lang.Object |
clone()
Creates and returns a copy of this set.
|
java.util.Comparator<? super E> |
comparator()
Returns the comparator associated with this sorted set, or null if it uses its elements' natural ordering.
|
boolean |
contains(java.lang.Object o)
Returns true if this set contains the specified element.
|
E |
first()
Returns the first (lowest) element currently in this sorted set.
|
java.util.SortedSet<E> |
headSet(E toElement)
Returns a view of the portion of this sorted set whose elements are strictly less than toElement.
|
protected java.lang.Object |
intern(E o)
Utility routine which ensures that the Set will contain the given object.
|
boolean |
isEmpty()
Returns true if this set contains no elements.
|
java.util.Iterator<E> |
iterator()
Returns an iterator over the elements in this set.
|
E |
last()
Returns the last (highest) element currently in this sorted set.
|
E |
lookup(E o)
Looks up the specified object in the set, and returns that object found (instead of the one provided.) This can be used, for example, to implement an
intern() type method for an object pool. |
protected ArraySortedSet<E> |
newArraySortedSet(int initialSize, java.util.Comparator<? super E> comparator) |
boolean |
remove(java.lang.Object o)
Removes the specified element from this set if it is present (optional operation).
|
int |
size()
Returns the number of elements in this set (its cardinality).
|
java.util.SortedSet<E> |
subSet(E fromElement, E toElement)
Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive.
|
java.util.SortedSet<E> |
tailSet(E fromElement)
Returns a view of the portion of this sorted set whose elements are greater than or equal to fromElement.
|
java.lang.Object[] |
toArray()
Returns an array containing all of the elements in this set.
|
java.lang.Object[] |
toArray(java.lang.Object[] a)
Returns an array containing all of the elements in this set - the runtime type of the returned array is that of the specified array.
|
void |
trimToSize()
Utility routine to trim the size of the backing array to the minimum necessary to support the size of the set.
|
public ArraySortedSet()
ArraySortedSet
of default size, using the default sorting order of the objects added to the set.public ArraySortedSet(int initialSize)
ArraySortedSet
of specified size, using the default sorting order of the objects addded to the set.initialSize
- the initial capacity of the setpublic ArraySortedSet(java.util.Comparator<? super E> comparator)
ArraySortedSet
of default size, using the specified comparator.comparator
- the comparator to usepublic ArraySortedSet(int initialSize, java.util.Comparator<? super E> comparator)
ArraySortedSet
of specified size, using the specified comparator.initialSize
- the initial capacity of the setcomparator
- the comparator to usepublic ArraySortedSet(E[] initialContents, java.util.Comparator<? super E> comparator)
ArraySortedSet
with the given contents and comparator. All objects in the array will be added to the set.initialContents
- the initial contents to add to the setcomparator
- the comparator to usepublic ArraySortedSet(java.util.Collection<? extends E> initialContents, java.util.Comparator<? super E> comparator)
ArraySortedSet
with the given contents and comparator. All objects in the collection will be added to the set.initialContents
- the initial contents to add to the setcomparator
- the comparator to use.public void addAll(E[] objects)
objects
- the objects to addpublic void trimToSize()
public E lookup(E o)
intern()
type method for an object pool.o
- element whose presence in this set is to be tested.java.lang.ClassCastException
- if the type of the specified element is incompatible with this set (optional).protected ArraySortedSet<E> newArraySortedSet(int initialSize, java.util.Comparator<? super E> comparator)
public java.lang.Object clone()
clone
in class java.lang.Object
public java.util.Comparator<? super E> comparator()
comparator
in interface java.util.SortedSet<E>
public java.util.SortedSet<E> subSet(E fromElement, E toElement)
subSet
in interface java.util.SortedSet<E>
public java.util.SortedSet<E> headSet(E toElement)
headSet
in interface java.util.SortedSet<E>
public java.util.SortedSet<E> tailSet(E fromElement)
tailSet
in interface java.util.SortedSet<E>
public E first()
first
in interface java.util.SortedSet<E>
public E last()
last
in interface java.util.SortedSet<E>
public int size()
public boolean isEmpty()
public java.util.Iterator<E> iterator()
public java.lang.Object[] toArray()
public java.lang.Object[] toArray(java.lang.Object[] a)
public boolean add(E o)
o
, to this set if this set contains no element e
such that (o==null ? e==null : o.equals(e))
. If this set already contains the specified element, the call leaves this set unchanged and returns false. In combination with the restriction on constructors, this ensures that sets never contain duplicate elements.
The stipulation above does not imply that sets must accept all elements; sets may refuse to add any particular element, including null, and throwing an exception, as described in the specification for Collection.add. Individual set implementations should clearly document any restrictions on the the elements that they may contain.
add
in interface java.util.Collection<E>
add
in interface java.util.Set<E>
add
in class java.util.AbstractCollection<E>
o
- element to be added to this set.java.lang.UnsupportedOperationException
- if the add method is not supported by this set.java.lang.ClassCastException
- if the class of the specified element prevents it from being added to this set.java.lang.NullPointerException
- if the specified element is null and this set does not support null elements.java.lang.IllegalArgumentException
- if some aspect of the specified element prevents it from being added to this set.public boolean remove(java.lang.Object o)
e
such that (o==null ? e==null : o.equals(e))
, if the set contains such an element. Returns true if the set contained the specified element (or equivalently, if the set changed as a result of the call). (The set will not contain the specified element once the call returns.)remove
in interface java.util.Collection<E>
remove
in interface java.util.Set<E>
remove
in class java.util.AbstractCollection<E>
o
- object to be removed from this set, if present.java.lang.ClassCastException
- if the type of the specified element is incompatible with this set (optional).java.lang.NullPointerException
- if the specified element is null and this set does not support null elements (optional).java.lang.UnsupportedOperationException
- if the remove method is not supported by this set.public boolean contains(java.lang.Object o)
e
such that (o==null ? e==null : o.equals(e))
.contains
in interface java.util.Collection<E>
contains
in interface java.util.Set<E>
contains
in class java.util.AbstractCollection<E>
o
- element whose presence in this set is to be tested.java.lang.ClassCastException
- if the type of the specified element is incompatible with this set (optional).java.lang.NullPointerException
- if the specified element is null and this set does not support null elements (optional).public void clear()
protected java.lang.Object intern(E o)
o
- the object to ensure exists in the Set