public class IntDoubleLinkedSet extends java.lang.Object implements IntLookupContainer, IntSet, java.lang.Cloneable
int
values. This data structure is characterized by
constant-time lookup, insertions, deletions and removal of all set elements (unlike a
BitSet
which takes time proportional to the maximum element's length).
The implementation in based on Preston Briggs and Linda Torczon's paper "An Efficient Representation for Sparse Sets"
Modifier and Type | Field and Description |
---|---|
static int |
DEFAULT_CAPACITY
Default capacity if no other capacity is given in the constructor.
|
int[] |
dense
Dense array of set elements.
|
int |
elementsCount
Current number of elements stored in the set (
dense ). |
protected ArraySizingStrategy |
resizer
Buffer resizing strategy.
|
int[] |
sparse
Sparse, element value-indexed array pointing back at
dense . |
Constructor and Description |
---|
IntDoubleLinkedSet()
Create with default sizing strategy and initial dense capacity of
5 elements and initial sparse capacity of zero (first insert
will cause reallocation).
|
IntDoubleLinkedSet(IntContainer container)
Creates a set from elements of another container.
|
IntDoubleLinkedSet(int denseCapacity,
int sparseCapacity)
Create with default sizing strategy and the given initial capacity.
|
IntDoubleLinkedSet(int denseCapacity,
int sparseCapacity,
ArraySizingStrategy resizer)
Create with a custom dense array resizing strategy.
|
Modifier and Type | Method and Description |
---|---|
int |
add(int... elements)
Vararg-signature method for adding elements to this set.
|
boolean |
add(int value)
Adds
k to the set. |
int |
add(int e1,
int e2)
Adds two elements to the set.
|
int |
addAll(IntContainer container)
Adds all elements from a given container to this set.
|
int |
addAll(java.lang.Iterable<? extends IntCursor> iterable)
Adds all elements from a given iterable to this set.
|
void |
clear()
Removes all elements from this collection.
|
IntDoubleLinkedSet |
clone()
Clone this object.
|
boolean |
contains(int value)
Lookup a given element in the container.
|
protected void |
ensureDenseCapacity(int expectedAdditions)
Ensures the internal dense buffer has enough free slots to store
expectedAdditions . |
protected void |
ensureSparseCapacity(int value)
Ensures the internal sparse buffer has enough free slots to store
index of
value . |
<T extends IntPredicate> |
forEach(T predicate)
Applies a
predicate to container elements as long, as the predicate
returns true . |
<T extends IntProcedure> |
forEach(T procedure)
Applies a
procedure to all container elements. |
static IntDoubleLinkedSet |
from(int... elements)
Create a set from a variable number of arguments or an array of
int . |
static IntDoubleLinkedSet |
from(IntContainer container)
Create a set from elements of another container.
|
boolean |
isEmpty()
Shortcut for
size() == 0 . |
java.util.Iterator<IntCursor> |
iterator()
Returns an iterator to a cursor traversing the collection.
|
static IntDoubleLinkedSet |
newInstance()
Static constructor-like method similar to other (generic) collections.
|
boolean |
remove(int key)
An alias for the (preferred)
removeAllOccurrences(int) . |
int |
removeAll(IntLookupContainer c)
Removes all elements in this collection that are present
in
c . |
int |
removeAll(IntPredicate predicate)
Removes all elements in this collection for which the
given predicate returns
true . |
int |
removeAllOccurrences(int value)
Removes all occurrences of
e from this collection. |
int |
retainAll(IntLookupContainer c)
Keeps all elements in this collection that are present
in
c . |
int |
retainAll(IntPredicate predicate)
Keeps all elements in this collection for which the
given predicate returns
true . |
int |
size()
Return the current number of elements in this container.
|
int[] |
toArray()
Copies all elements from this container to an array of this container's component
type.
|
java.lang.String |
toString() |
public static final int DEFAULT_CAPACITY
public int[] dense
public int[] sparse
dense
.public int elementsCount
dense
).protected final ArraySizingStrategy resizer
public IntDoubleLinkedSet()
BoundedProportionalArraySizingStrategy
public IntDoubleLinkedSet(int denseCapacity, int sparseCapacity)
BoundedProportionalArraySizingStrategy
public IntDoubleLinkedSet(int denseCapacity, int sparseCapacity, ArraySizingStrategy resizer)
public IntDoubleLinkedSet(IntContainer container)
protected void ensureDenseCapacity(int expectedAdditions)
expectedAdditions
.protected void ensureSparseCapacity(int value)
value
.public int size()
IntContainer
O(n)
time, although implementing classes
should try to maintain the current size and return in constant time.size
in interface IntContainer
public int[] toArray()
IntContainer
toArray
in interface IntContainer
public boolean isEmpty()
IntContainer
size() == 0
.isEmpty
in interface IntContainer
public void clear()
IntCollection
clear
in interface IntCollection
public boolean contains(int value)
IntContainer
contains
in interface IntContainer
contains
in interface IntLookupContainer
true
if this container has an element
equal to e
.public boolean add(int value)
IntSet
k
to the set.public int add(int e1, int e2)
public int add(int... elements)
This method is handy, but costly if used in tight loops (anonymous array passing)
public int addAll(IntContainer container)
public int addAll(java.lang.Iterable<? extends IntCursor> iterable)
public int removeAllOccurrences(int value)
IntCollection
e
from this collection.removeAllOccurrences
in interface IntCollection
value
- Element to be removed from this collection, if present.public boolean remove(int key)
removeAllOccurrences(int)
.public java.util.Iterator<IntCursor> iterator()
IntContainer
The iterator is implemented as a
cursor and it returns the same cursor instance on every call to
Iterator.next()
(to avoid boxing of primitive types). To read the current
list's value (or index in the list) use the cursor's public fields. An example is
shown below.
for (IntCursor<int> c : container) { System.out.println("index=" + c.index + " value=" + c.value); }
iterator
in interface IntContainer
iterator
in interface java.lang.Iterable<IntCursor>
public <T extends IntProcedure> T forEach(T procedure)
IntContainer
procedure
to all container elements. Returns the argument (any
subclass of IntProcedure
. This lets the caller to call methods of the argument
by chaining the call (even if the argument is an anonymous type) to retrieve computed values,
for example (IntContainer):
int count = container.forEach(new IntProcedure() { int count; // this is a field declaration in an anonymous class. public void apply(int value) { count++; }}).count;
forEach
in interface IntContainer
public <T extends IntPredicate> T forEach(T predicate)
IntContainer
predicate
to container elements as long, as the predicate
returns true
. The iteration is interrupted otherwise.forEach
in interface IntContainer
public int removeAll(IntLookupContainer c)
IntCollection
c
. Runs in time proportional to the number
of elements in this collection. Equivalent of sets difference.removeAll
in interface IntCollection
public int removeAll(IntPredicate predicate)
IntCollection
true
.removeAll
in interface IntCollection
public int retainAll(IntLookupContainer c)
IntCollection
c
. Runs in time proportional to the number
of elements in this collection. Equivalent of sets intersection.retainAll
in interface IntCollection
public int retainAll(IntPredicate predicate)
IntCollection
true
.retainAll
in interface IntCollection
public static IntDoubleLinkedSet from(int... elements)
int
.
The elements are copied from the argument to the internal buffer.public static IntDoubleLinkedSet from(IntContainer container)
public static IntDoubleLinkedSet newInstance()
public IntDoubleLinkedSet clone()
clone
in class java.lang.Object
public java.lang.String toString()
toString
in class java.lang.Object
Copyright © 2018 Carrot Search s.c.. All rights reserved.