com.carrotsearch.hppc
Class IntDoubleLinkedSet

java.lang.Object
  com.carrotsearch.hppc.IntDoubleLinkedSet

All Implemented Interfaces:

IntCollection, IntContainer, IntLookupContainer, IntSet, java.lang.Cloneable, java.lang.Iterable<IntCursor>

public class IntDoubleLinkedSet
extends java.lang.Object
implements IntLookupContainer, IntSet, java.lang.Cloneable

A double-linked set of 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"

Field Summary

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 Summary

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.

Method Summary

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> T	forEach(T predicate) Applies a predicate to container elements as long, as the predicate returns true.
<T extends IntProcedure> T	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.
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()

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface com.carrotsearch.hppc.IntSet

equals, hashCode

Field Detail

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY

Default capacity if no other capacity is given in the constructor.

See Also:

Constant Field Values

dense

public int[] dense

Dense array of set elements.

sparse

public int[] sparse

Sparse, element value-indexed array pointing back at dense.

elementsCount

public int elementsCount

Current number of elements stored in the set (dense).

resizer

protected final ArraySizingStrategy resizer

Buffer resizing strategy.

Constructor Detail

IntDoubleLinkedSet

public IntDoubleLinkedSet()

Create with default sizing strategy and initial dense capacity of 5 elements and initial sparse capacity of zero (first insert will cause reallocation).

See Also:

BoundedProportionalArraySizingStrategy

IntDoubleLinkedSet

public IntDoubleLinkedSet(int denseCapacity,
                          int sparseCapacity)

Create with default sizing strategy and the given initial capacity.

See Also:

BoundedProportionalArraySizingStrategy

IntDoubleLinkedSet

public IntDoubleLinkedSet(int denseCapacity,
                          int sparseCapacity,
                          ArraySizingStrategy resizer)

Create with a custom dense array resizing strategy.

IntDoubleLinkedSet

public IntDoubleLinkedSet(IntContainer container)

Creates a set from elements of another container.

Method Detail

ensureDenseCapacity

protected final void ensureDenseCapacity(int expectedAdditions)

Ensures the internal dense buffer has enough free slots to store expectedAdditions.

ensureSparseCapacity

protected final void ensureSparseCapacity(int value)

Ensures the internal sparse buffer has enough free slots to store index of value.

size

public int size()

Description copied from interface: IntContainer

Return the current number of elements in this container. The time for calculating the container's size may take O(n) time, although implementing classes should try to maintain the current size and return in constant time.

Specified by:

size in interface IntContainer

toArray

public int[] toArray()

Description copied from interface: IntContainer

Copies all elements from this container to an array of this container's component type. The returned array is always a copy, regardless of the storage used by the container.

Specified by:

toArray in interface IntContainer

isEmpty

public boolean isEmpty()

Description copied from interface: IntContainer

Shortcut for size() == 0.

Specified by:

isEmpty in interface IntContainer

clear

public void clear()

Description copied from interface: IntCollection

Removes all elements from this collection.

Specified by:

clear in interface IntCollection

contains

public boolean contains(int value)

Description copied from interface: IntContainer

Lookup a given element in the container. This operation has no speed guarantees (may be linear with respect to the size of this container).

Specified by:

contains in interface IntContainer

Specified by:

contains in interface IntLookupContainer

Returns:

Returns true if this container has an element equal to e.

add

public boolean add(int value)

Description copied from interface: IntSet

Adds k to the set.

Specified by:

add in interface IntSet

Returns:

Returns true if this element was not part of the set before. Returns false if an equal element is part of the set, and replaces the existing equal element with the argument (if keys are object types).

add

public int add(int e1,
               int e2)

Adds two elements to the set.

add

public int add(int... elements)

Vararg-signature method for adding elements to this set.

This method is handy, but costly if used in tight loops (anonymous array passing)

Returns:

Returns the number of elements that were added to the set (were not present in the set).

addAll

public final int addAll(IntContainer container)

Adds all elements from a given container to this set.

Returns:

Returns the number of elements actually added as a result of this call (not previously present in the set).

addAll

public final int addAll(java.lang.Iterable<? extends IntCursor> iterable)

Adds all elements from a given iterable to this set.

Returns:

Returns the number of elements actually added as a result of this call (not previously present in the set).

removeAllOccurrences

public int removeAllOccurrences(int value)

Description copied from interface: IntCollection

Removes all occurrences of e from this collection.

Specified by:

removeAllOccurrences in interface IntCollection

Parameters:

value - Element to be removed from this collection, if present.

Returns:

The number of removed elements as a result of this call.

remove

public boolean remove(int key)

An alias for the (preferred) removeAllOccurrences(int).

iterator

public java.util.Iterator<IntCursor> iterator()

Description copied from interface: IntContainer

Returns an iterator to a cursor traversing the collection. The order of traversal is not defined. More than one cursor may be active at a time. The behavior of iterators is undefined if structural changes are made to the underlying collection.

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);
 }
 

Specified by:

iterator in interface IntContainer

Specified by:

iterator in interface java.lang.Iterable<IntCursor>

forEach

public <T extends IntProcedure> T forEach(T procedure)

Description copied from interface: IntContainer

Applies a 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;
 

Specified by:

forEach in interface IntContainer

forEach

public <T extends IntPredicate> T forEach(T predicate)

Description copied from interface: IntContainer

Applies a predicate to container elements as long, as the predicate returns true. The iteration is interrupted otherwise.

Specified by:

forEach in interface IntContainer

removeAll

public int removeAll(IntLookupContainer c)

Description copied from interface: IntCollection

Removes all elements in this collection that are present in c. Runs in time proportional to the number of elements in this collection. Equivalent of sets difference.

Specified by:

removeAll in interface IntCollection

Returns:

Returns the number of removed elements.

removeAll

public int removeAll(IntPredicate predicate)

Description copied from interface: IntCollection

Removes all elements in this collection for which the given predicate returns true.

Specified by:

removeAll in interface IntCollection

retainAll

public int retainAll(IntLookupContainer c)

Description copied from interface: IntCollection

Keeps all elements in this collection that are present in c. Runs in time proportional to the number of elements in this collection. Equivalent of sets intersection.

Specified by:

retainAll in interface IntCollection

Returns:

Returns the number of removed elements.

retainAll

public int retainAll(IntPredicate predicate)

Description copied from interface: IntCollection

Keeps all elements in this collection for which the given predicate returns true.

Specified by:

retainAll in interface IntCollection

from

public static IntDoubleLinkedSet from(int... elements)

Create a set from a variable number of arguments or an array of int. The elements are copied from the argument to the internal buffer.

from

public static IntDoubleLinkedSet from(IntContainer container)

Create a set from elements of another container.

clone

public IntDoubleLinkedSet clone()

Clone this object.

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object