net.i2p.util

Class ArraySet<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<E>

net.i2p.util.ArraySet<E>

Type Parameters:

E - type of elements in this set

All Implemented Interfaces:

Iterable<E>, Collection<E>, Set<E>

Direct Known Subclasses:

UnmodifiableSortedSet

public class ArraySet<E>
extends AbstractSet<E>
implements Set<E>

A small, fast Set with a maximum size, backed by a fixed-size array. Much more space-efficient than HashSet. Unsynchronized, not thread-safe. Null elements are not permitted. Not appropriate for large Sets that are modified. add(), remove(), and contains() are O(n). Warning: addAll() and the Collection constructor are O(n**2).

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ArraySet.SetFullException Exception thrown when attempting to add an element to a full ArraySet.

Field Summary

Fields

Modifier and Type	Field and Description
protected Object[]	_entries The underlying array of entries
static int	MAX_CAPACITY The maximum capacity for this set

Constructor Summary

Constructors

Constructor and Description
ArraySet() A fixed capacity of MAX_CAPACITY.
ArraySet(Collection<? extends E> c) A fixed capacity of max(MAX_CAPACITY, c.size()), which may be more than the resulting set size if there are duplicates in c.
ArraySet(Collection<? extends E> c, int capacity) A fixed capacity of max(capacity, c.size()), which may be more than the resulting set size if there are duplicates in c.
ArraySet(E[] arr) A fixed capacity of arr.length.
ArraySet(int capacity) Adds over capacity will throw a SetFullException.
ArraySet(int capacity, boolean throwOnFull) If throwOnFull is false, adds over capacity will overwrite starting at slot zero.
ArraySet(Set<? extends E> c) A fixed capacity of max(MAX_CAPACITY, c.size()) Adds over capacity will throw a SetFullException.
ArraySet(Set<? extends E> c, int capacity) A fixed capacity of max(capacity, c.size()) Adds over capacity will throw a SetFullException.

Method Summary

Modifier and Type	Method and Description
boolean	add(E o)
void	addUnique(E o) Unconditionally add o to the set.
void	clear()
boolean	contains(Object o)
E	get(int index) Returns the element at the specified index.
protected int	indexOf(Object o) Finds the index of the given object in the set.
boolean	isEmpty()
Iterator<E>	iterator() Supports remove.
boolean	remove(Object o)
int	size()

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, spliterator, toArray, toArray

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

_entries

protected final Object[] _entries

The underlying array of entries

MAX_CAPACITY

public static final int MAX_CAPACITY

The maximum capacity for this set

See Also:

Constant Field Values

Constructor Detail

ArraySet

public ArraySet()

A fixed capacity of MAX_CAPACITY. Adds over capacity will throw a SetFullException.

ArraySet

public ArraySet(Collection<? extends E> c)

A fixed capacity of max(MAX_CAPACITY, c.size()), which may be more than the resulting set size if there are duplicates in c. Adds over capacity will throw a SetFullException. Warning: O(n**2).

Parameters:

c - the collection to copy

ArraySet

public ArraySet(Collection<? extends E> c,
                int capacity)

A fixed capacity of max(capacity, c.size()), which may be more than the resulting set size if there are duplicates in c. Adds over capacity will throw a SetFullException. Warning: O(n**2).

Parameters:

c - the collection to copy

capacity - the maximum capacity

ArraySet

public ArraySet(E[] arr)

A fixed capacity of arr.length. Adds over capacity will throw a SetFullException. arr must not contain duplicates, no checks are done. arr may contain nulls but they must be at the end.

Parameters:

arr - the array to copy

ArraySet

public ArraySet(int capacity)

Adds over capacity will throw a SetFullException.

Parameters:

capacity - the maximum size

Throws:

IllegalArgumentException - if capacity less than 1.

ArraySet

public ArraySet(int capacity,
                boolean throwOnFull)

If throwOnFull is false, adds over capacity will overwrite starting at slot zero. This breaks the AbstractCollection invariant that "a Collection will always contain the specified element after add() returns", but it prevents unexpected exceptions. If throwOnFull is true, adds over capacity will throw a SetFullException.

Parameters:

capacity - the maximum size

throwOnFull - whether to throw on overflow

Throws:

IllegalArgumentException - if capacity less than 1.

ArraySet

public ArraySet(Set<? extends E> c)

A fixed capacity of max(MAX_CAPACITY, c.size()) Adds over capacity will throw a SetFullException.

Parameters:

c - the collection to copy

ArraySet

public ArraySet(Set<? extends E> c,
                int capacity)

A fixed capacity of max(capacity, c.size()) Adds over capacity will throw a SetFullException.

Parameters:

c - the collection to copy

capacity - the maximum capacity

Method Detail

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>

Parameters:

o - the element to add

Throws:

ArraySet.SetFullException - if throwOnFull was true in constructor

NullPointerException - if o is null

addUnique

public void addUnique(E o)

Unconditionally add o to the set. This avoids the O(n) time of add(), but it's the caller's responsibility to ensure that o is not a duplicate. Any duplicate added will appear in the iterator.

Parameters:

o - non-null, NPE will not be thrown

Throws:

ArraySet.SetFullException - if throwOnFull was true in constructor

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>

get

public E get(int index)

Returns the element at the specified index.

Parameters:

index - the index to retrieve

Returns:

the element at the specified index

Throws:

IndexOutOfBoundsException - if index is out of bounds

indexOf

protected int indexOf(Object o)

Finds the index of the given object in the set.

Parameters:

o - the object to find the index of

Returns:

-1 if not found or if o is null

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface Set<E>

Overrides:

isEmpty in class AbstractCollection<E>

iterator

public Iterator<E> iterator()

Supports remove. Supports comodification checks.

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>

Returns:

an iterator over this set

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>