javolution.util

Class FastBitSet

java.lang.Object

javolution.util.FastCollection<E>

javolution.util.FastSet<Index>

javolution.util.FastBitSet

All Implemented Interfaces:

Serializable, Iterable<Index>, Collection<Index>, Set<Index>

public class FastBitSet
extends FastSet<Index>

A high-performance bitset integrated with the collection framework as a set of indices and obeying the collection semantic for methods such as FastSet.size() (cardinality) or FastCollection.equals(java.lang.Object) (same set of indices).

Version:

6.0, July 21, 2013

Author:

Jean-Marie Dautelle

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class javolution.util.FastCollection

FastCollection.Text

Constructor Summary

Constructors

Modifier	Constructor and Description
	FastBitSet() Creates an empty bit set.
protected	FastBitSet(BitSetService impl) Creates a fast bit set based on the specified implementation.
	FastBitSet(long[] bits) Creates a bit set holding the specified bits.

Method Summary

Methods

Modifier and Type	Method and Description
void	and(FastBitSet that) Performs the logical AND operation on this bit set and the given bit set.
void	andNot(FastBitSet that) Performs the logical AND operation on this bit set and the complement of the given bit set.
int	cardinality() Returns the number of bits set to true (or the size of this set).
void	clear() Sets all bits in the set to false (empty the set).
void	clear(int bitIndex) Removes the specified integer value from this set.
void	clear(int fromIndex, int toIndex) Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to false.
void	flip(int bitIndex) Sets the bit at the index to the opposite value.
void	flip(int fromIndex, int toIndex) Sets a range of bits to the opposite value.
boolean	get(int bitIndex) Returns true if the specified integer is in this bit set; false otherwise.
FastBitSet	get(int fromIndex, int toIndex) Returns a new bit set composed of a range of bits from this one.
boolean	intersects(FastBitSet that) Returns true if this bit set shares at least one common bit with the specified bit set.
boolean	isEmpty() Returns true if no bits in this set are set to 1 (cardinality == 0)
int	length() Returns the logical number of bits actually used by this bit set.
int	nextClearBit(int fromIndex) Returns the index of the next false bit, from the specified bit (inclusive).
int	nextSetBit(int fromIndex) Returns the index of the next true bit, from the specified bit (inclusive).
static FastBitSet	of(Index... indices) Returns a new bit set holding the specified indices (convenience method).
void	or(FastBitSet that) Performs the logical OR operation on this bit set and the one specified.
int	previousClearBit(int fromIndex) Returns the index of the previous false bit, from the specified bit (inclusive).
int	previousSetBit(int fromIndex) Returns the index of the previous true bit, from the specified bit (inclusive).
protected BitSetService	service() Returns the service implementation of this collection (for sub-classes).
void	set(int bitIndex) Adds the specified integer to this set (corresponding bit is set to true.
void	set(int bitIndex, boolean value) Sets the bit at the given index to the specified value.
void	set(int fromIndex, int toIndex) Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to true.
void	set(int fromIndex, int toIndex, boolean value) Sets the bits between from (inclusive) and to (exclusive) to the specified value.
FastBitSet	unmodifiable() Returns an unmodifiable view over this collection.
void	xor(FastBitSet that) Performs the logical XOR operation on this bit set and the one specified.

Methods inherited from class javolution.util.FastSet

atomic, contains, filtered, of, of, remove, shared, size

Methods inherited from class javolution.util.FastCollection

add, addAll, any, comparator, comparator, containsAll, distinct, equals, forEach, hashCode, iterator, mapped, max, min, parallel, perform, reduce, removeAll, removeIf, retainAll, reversed, sequential, serviceOf, sorted, sorted, toArray, toArray, toString, update

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

add, addAll, containsAll, equals, hashCode, iterator, removeAll, retainAll, toArray, toArray

Constructor Detail

FastBitSet

public FastBitSet()

Creates an empty bit set.

FastBitSet

public FastBitSet(@Constant
          long[] bits)

Creates a bit set holding the specified bits.

Parameters:

bits - a long array containing a little-endian representation of a sequence of bits to be used as the initial bits of the new bit set.

FastBitSet

protected FastBitSet(BitSetService impl)

Creates a fast bit set based on the specified implementation.

Method Detail

of

public static FastBitSet of(Index... indices)

Returns a new bit set holding the specified indices (convenience method).

unmodifiable

public FastBitSet unmodifiable()

Description copied from class: FastCollection

Returns an unmodifiable view over this collection. Any attempt to modify the collection through this view will result into a UnsupportedOperationException being raised.

Overrides:

unmodifiable in class FastSet<Index>

and

@Realtime(limit=LINEAR)
public void and(FastBitSet that)

Performs the logical AND operation on this bit set and the given bit set. This means it builds the intersection of the two sets. The result is stored into this bit set.

Parameters:

that - the second bit set.

andNot

@Realtime(limit=LINEAR)
public void andNot(FastBitSet that)

Performs the logical AND operation on this bit set and the complement of the given bit set. This means it selects every element in the first set, that isn't in the second set. The result is stored into this bit set.

Parameters:

that - the second bit set

cardinality

public int cardinality()

Returns the number of bits set to true (or the size of this set).

Returns:

the number of bits being set.

clear

public void clear()

Sets all bits in the set to false (empty the set).

Specified by:

clear in interface Collection<Index>

Specified by:

clear in interface Set<Index>

Overrides:

clear in class FastSet<Index>

clear

public void clear(int bitIndex)

Removes the specified integer value from this set. That is the corresponding bit is cleared.

Parameters:

bitIndex - a non-negative integer.

Throws:

IndexOutOfBoundsException - if index < 0

clear

@Realtime(limit=LINEAR)
public void clear(int fromIndex,
                             int toIndex)

Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to false.

Parameters:

fromIndex - index of the first bit to be cleared.

toIndex - index after the last bit to be cleared.

Throws:

IndexOutOfBoundsException - if (fromIndex < 0) | (toIndex < fromIndex)

flip

public void flip(int bitIndex)

Sets the bit at the index to the opposite value.

Parameters:

bitIndex - the index of the bit.

Throws:

IndexOutOfBoundsException - if bitIndex < 0

flip

@Realtime(limit=LINEAR)
public void flip(int fromIndex,
                            int toIndex)

Sets a range of bits to the opposite value.

Parameters:

fromIndex - the low index (inclusive).

toIndex - the high index (exclusive).

Throws:

IndexOutOfBoundsException - if (fromIndex < 0) | (toIndex < fromIndex)

get

public boolean get(int bitIndex)

Returns true if the specified integer is in this bit set; false otherwise.

Parameters:

bitIndex - a non-negative integer.

Returns:

the value of the bit at the specified index.

Throws:

IndexOutOfBoundsException - if bitIndex < 0

get

@Realtime(limit=LINEAR)
public FastBitSet get(int fromIndex,
                                 int toIndex)

Returns a new bit set composed of a range of bits from this one.

Parameters:

fromIndex - the low index (inclusive).

toIndex - the high index (exclusive).

Returns:

a context allocated bit set instance.

Throws:

IndexOutOfBoundsException - if (fromIndex < 0) | (toIndex < fromIndex)

intersects

@Realtime(limit=LINEAR)
public boolean intersects(FastBitSet that)

Returns true if this bit set shares at least one common bit with the specified bit set.

Parameters:

that - the bit set to check for intersection

Returns:

true if the sets intersect; false otherwise.

isEmpty

public boolean isEmpty()

Returns true if no bits in this set are set to 1 (cardinality == 0)

Specified by:

isEmpty in interface Collection<Index>

Specified by:

isEmpty in interface Set<Index>

Overrides:

isEmpty in class FastSet<Index>

Returns:

true if all bits are 0, false otherwise.

length

public int length()

Returns the logical number of bits actually used by this bit set. It returns the index of the highest set bit plus one.

Note: This method does not return the number of set bits which is returned by FastSet.size()

Returns:

the index of the highest set bit plus one.

nextClearBit

public int nextClearBit(int fromIndex)

Returns the index of the next false bit, from the specified bit (inclusive).

Parameters:

fromIndex - the start location.

Returns:

the first false bit.

Throws:

IndexOutOfBoundsException - if fromIndex < 0

nextSetBit

public int nextSetBit(int fromIndex)

Returns the index of the next true bit, from the specified bit (inclusive). If there is none, -1 is returned. The following code will iterates through the bit set:

    for (int i=nextSetBit(0); i >= 0; i = nextSetBit(i+1)) {
         ...
    }

Parameters:

fromIndex - the start location.

Returns:

the first false bit.

Throws:

IndexOutOfBoundsException - if fromIndex < 0

previousClearBit

public int previousClearBit(int fromIndex)

Returns the index of the previous false bit, from the specified bit (inclusive).

Parameters:

fromIndex - the start location.

Returns:

the first false bit.

Throws:

IndexOutOfBoundsException - if fromIndex < -1

previousSetBit

public int previousSetBit(int fromIndex)

Returns the index of the previous true bit, from the specified bit (inclusive). If there is none, -1 is returned. The following code will iterates through the bit set:

     for (int i = length(); (i = previousSetBit(i-1)) >= 0; ) {
        ...
     }

Parameters:

fromIndex - the start location.

Returns:

the first false bit.

Throws:

IndexOutOfBoundsException - if fromIndex < -1

or

@Realtime(limit=LINEAR)
public void or(FastBitSet that)

Performs the logical OR operation on this bit set and the one specified. In other words, builds the union of the two sets. The result is stored into this bit set.

Parameters:

that - the second bit set.

set

public void set(int bitIndex)

Adds the specified integer to this set (corresponding bit is set to true.

Parameters:

bitIndex - a non-negative integer.

Throws:

IndexOutOfBoundsException - if bitIndex < 0

set

public void set(int bitIndex,
       boolean value)

Sets the bit at the given index to the specified value.

Parameters:

bitIndex - the position to set.

value - the value to set it to.

Throws:

IndexOutOfBoundsException - if bitIndex < 0

set

@Realtime(limit=LINEAR)
public void set(int fromIndex,
                           int toIndex)

Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to true.

Parameters:

fromIndex - index of the first bit to be set.

toIndex - index after the last bit to be set.

Throws:

IndexOutOfBoundsException - if (fromIndex < 0) | (toIndex < fromIndex)

set

@Realtime(limit=LINEAR)
public void set(int fromIndex,
                           int toIndex,
                           boolean value)

Sets the bits between from (inclusive) and to (exclusive) to the specified value.

Parameters:

fromIndex - the start range (inclusive).

toIndex - the end range (exclusive).

value - the value to set it to.

Throws:

IndexOutOfBoundsException - if bitIndex < 0

xor

@Realtime(limit=LINEAR)
public void xor(FastBitSet that)

Performs the logical XOR operation on this bit set and the one specified. In other words, builds the symmetric remainder of the two sets (the elements that are in one set, but not in the other). The result is stored into this bit set.

Parameters:

that - the second bit set.

service

protected BitSetService service()

Description copied from class: FastCollection

Returns the service implementation of this collection (for sub-classes).

Overrides:

service in class FastSet<Index>