E - public class ArrayBasedSet<E> extends Object implements HGSortedSet<E>, CloneMe
An implementation SortedSet based on primitive arrays that grow
as needed without ever shrinking. Lookup is log(n), but insertion and removal
take longer obviously so this implementation is mainly suitable for small sets
of a few dozen elements, or for sets that are searched/iterated much more
frequently than they are changed. The main reason for being of this implementation
is space efficiency: a red-black tree holds additional 12 bytes per datum. So while
for a large set, a tree should be used, the array-based implementation is preferable
for many small sets like many of HyperGraphDB's incidence sets.
Some benchmarking experiments comparing this (rather simple) implementation to red-black trees (both LLRBTree and the standard Java TreeSet): working with about up to 10000 elements, insertion and removal have a comparable performance, with the array-based implementation being about 15% slower (elements inserted/removed in random order). The LLRBTree implementation is actually noticeably slower than TreeSet, probably due to recursion. However, in "read-mode", when iterating over the set, using it as a HGRandomAccessResult, the array-based implementation is 8-10 faster. Understandable since here moving to the next element amounts to incrementing an integer while in a tree a lookup for the successor must be performed (e.g. min(parent(current))). So for set of this order of magnitude and/or sets that are being read more than they are modified, it is strongly advisable to use the ArrayBasedSet.
| Constructor and Description |
|---|
ArrayBasedSet(E[] A)
Initialize from the given array.
|
ArrayBasedSet(E[] A,
Comparator<E> comparator)
Initialize from the given array and with the given
Comparator. |
ArrayBasedSet(E[] A,
int capacity)
Initialize an empty set with a given initial capacity.
|
ArrayBasedSet(E[] A,
int capacity,
Comparator<E> comparator)
Initialize an empty set with a given initial capacity, and a given
comparator.
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
add(E o) |
boolean |
addAll(Collection<? extends E> c) |
void |
clear() |
Comparator<? super E> |
comparator() |
boolean |
contains(Object o) |
boolean |
containsAll(Collection<?> c) |
ArrayBasedSet<E> |
duplicate() |
E |
first() |
E |
getAt(int i) |
ReadWriteLock |
getLock() |
HGRandomAccessResult<E> |
getSearchResult() |
SortedSet<E> |
headSet(E toElement) |
boolean |
isEmpty() |
Iterator<E> |
iterator() |
E |
last() |
boolean |
remove(Object o) |
boolean |
removeAll(Collection<?> c) |
E |
removeAt(int i) |
boolean |
retainAll(Collection<?> c) |
void |
setFromArray(E[] A) |
void |
setLock(ReadWriteLock lock) |
int |
size() |
SortedSet<E> |
subSet(E fromElement,
E toElement) |
SortedSet<E> |
tailSet(E fromElement) |
Object[] |
toArray() |
<T> T[] |
toArray(T[] a) |
public ArrayBasedSet(E[] A)
Initialize from the given array.
A - The array used to initialize. An internal array is created
with the same size as A and all its elements are copied.public ArrayBasedSet(E[] A, int capacity)
Initialize an empty set with a given initial capacity.
A - The array used to initialize. An internal array is created
with the same type as as A and with size number
of slots.public ArrayBasedSet(E[] A, int capacity, Comparator<E> comparator)
Initialize an empty set with a given initial capacity, and a given comparator.
A - The array used to initialize. An internal array is created
with the same type as as A and with size number
of slots.Comparator - The comparator used to compare elements.public ArrayBasedSet(E[] A, Comparator<E> comparator)
Initialize from the given array and with the given Comparator.
A - The array used to initialize. An internal array is created
with the same size as A and all its elements are copied.Comparator - The comparator used to compare elements.public void setFromArray(E[] A)
public ReadWriteLock getLock()
public void setLock(ReadWriteLock lock)
public Comparator<? super E> comparator()
comparator in interface SortedSet<E>public E getAt(int i)
public E removeAt(int i)
public boolean add(E o)
public boolean addAll(Collection<? extends E> c)
public void clear()
public boolean contains(Object o)
public boolean containsAll(Collection<?> c)
containsAll in interface Collection<E>containsAll in interface Set<E>public boolean isEmpty()
public HGRandomAccessResult<E> getSearchResult()
getSearchResult in interface HGSortedSet<E>public boolean remove(Object o)
public boolean removeAll(Collection<?> c)
public boolean retainAll(Collection<?> c)
public int size()
public Object[] toArray()
public ArrayBasedSet<E> duplicate()
Copyright © 2015. All rights reserved.