org.hypergraphdb.util.ArrayBasedSet<E>
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object
E - public class ArrayBasedSet<E>
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 Summary | |
|---|---|
ArrayBasedSet(E[] A)
Initialize from the given array. |
|
ArrayBasedSet(E[] A,
java.util.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,
java.util.Comparator<E> comparator)
Initialize an empty set with a given initial capacity, and a given comparator. |
|
| Method Summary | ||
|---|---|---|
boolean |
add(E o)
|
|
boolean |
addAll(java.util.Collection<? extends E> c)
|
|
void |
clear()
|
|
java.util.Comparator<? super E> |
comparator()
|
|
boolean |
contains(java.lang.Object o)
|
|
boolean |
containsAll(java.util.Collection<?> c)
|
|
E |
first()
|
|
E |
getAt(int i)
|
|
java.util.concurrent.locks.ReadWriteLock |
getLock()
|
|
HGRandomAccessResult<E> |
getSearchResult()
|
|
java.util.SortedSet<E> |
headSet(E toElement)
|
|
boolean |
isEmpty()
|
|
java.util.Iterator<E> |
iterator()
|
|
E |
last()
|
|
boolean |
remove(java.lang.Object o)
|
|
boolean |
removeAll(java.util.Collection<?> c)
|
|
E |
removeAt(int i)
|
|
boolean |
retainAll(java.util.Collection<?> c)
|
|
void |
setFromArray(E[] A)
|
|
void |
setLock(java.util.concurrent.locks.ReadWriteLock lock)
|
|
int |
size()
|
|
java.util.SortedSet<E> |
subSet(E fromElement,
E toElement)
|
|
java.util.SortedSet<E> |
tailSet(E fromElement)
|
|
java.lang.Object[] |
toArray()
|
|
|
toArray(T[] a)
|
|
| Methods inherited from class java.lang.Object |
|---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Methods inherited from interface java.util.Set |
|---|
equals, hashCode |
| Constructor Detail |
|---|
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,
java.util.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,
java.util.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.| Method Detail |
|---|
public void setFromArray(E[] A)
public java.util.concurrent.locks.ReadWriteLock getLock()
public void setLock(java.util.concurrent.locks.ReadWriteLock lock)
public java.util.Comparator<? super E> comparator()
comparator in interface java.util.SortedSet<E>public E getAt(int i)
public E removeAt(int i)
public E first()
first in interface java.util.SortedSet<E>public java.util.SortedSet<E> headSet(E toElement)
headSet in interface java.util.SortedSet<E>public E last()
last 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> tailSet(E fromElement)
tailSet in interface java.util.SortedSet<E>public boolean add(E o)
add in interface java.util.Collection<E>add in interface java.util.Set<E>public boolean addAll(java.util.Collection<? extends E> c)
addAll in interface java.util.Collection<E>addAll in interface java.util.Set<E>public void clear()
clear in interface java.util.Collection<E>clear in interface java.util.Set<E>public boolean contains(java.lang.Object o)
contains in interface java.util.Collection<E>contains in interface java.util.Set<E>public boolean containsAll(java.util.Collection<?> c)
containsAll in interface java.util.Collection<E>containsAll in interface java.util.Set<E>public boolean isEmpty()
isEmpty in interface java.util.Collection<E>isEmpty in interface java.util.Set<E>public java.util.Iterator<E> iterator()
iterator in interface java.lang.Iterable<E>iterator in interface java.util.Collection<E>iterator in interface java.util.Set<E>public HGRandomAccessResult<E> getSearchResult()
getSearchResult in interface HGSortedSet<E>public boolean remove(java.lang.Object o)
remove in interface java.util.Collection<E>remove in interface java.util.Set<E>public boolean removeAll(java.util.Collection<?> c)
removeAll in interface java.util.Collection<E>removeAll in interface java.util.Set<E>public boolean retainAll(java.util.Collection<?> c)
retainAll in interface java.util.Collection<E>retainAll in interface java.util.Set<E>public int size()
size in interface java.util.Collection<E>size in interface java.util.Set<E>public java.lang.Object[] toArray()
toArray in interface java.util.Collection<E>toArray in interface java.util.Set<E>public <T> T[] toArray(T[] a)
toArray in interface java.util.Collection<E>toArray in interface java.util.Set<E>
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||