javolution.util

Class FastBitSet

java.lang.Object

javolution.util.FastCollection<Index>

javolution.util.FastBitSet

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<Index>, java.util.Collection<Index>, java.util.Set<Index>, Realtime, Reusable, XMLSerializable

public class FastBitSet
extends FastCollection<Index>
implements java.util.Set<Index>, Reusable

This class represents either a table of bits or a set of non-negative numbers.

This class is integrated with the collection framework (as a set of indices and obeys the collection semantic for methods such as size() (cardinality) or equals(java.lang.Object) (same set of indices).

Version:

5.3, February 24, 2008

Author:

Jean-Marie Dautelle

See Also:

Serialized Form

Nested Class Summary

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

FastCollection.Record

Constructor Summary

Constructors

Constructor and Description
FastBitSet() Creates a bit set of small initial capacity.
FastBitSet(int bitSize) Creates a bit set of specified initial capacity (in bits).

Method Summary

Modifier and Type	Method and Description
boolean	add(Index index) Adds the specified index to this set.
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	delete(FastCollection.Record record) Deletes the specified record from this collection.
boolean	equals(java.lang.Object obj) Compares the specified object with this collection for equality.
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.
int	hashCode() Returns the hash code for this collection.
FastCollection.Record	head() Returns the head record of this collection; it is the record such as head().getNext() holds the first collection value.
boolean	intersects(FastBitSet that) Returns true if this bit set shares at least one common bit with the specified bit set.
int	length() Returns the logical number of bits actually used by this bit set.
static FastBitSet	newInstance() Returns a new, preallocated or recycled set instance (on the stack when executing in a StackContext).
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).
void	or(FastBitSet that) Performs the logical OR operation on this bit set and the one specified.
static void	recycle(FastBitSet instance) Recycles a set instance immediately (on the stack when executing in a StackContext).
void	reset() Resets the internal state of this object to its default values.
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.
int	size() Returns the cardinality of this bit set (number of bits set).
FastCollection.Record	tail() Returns the tail record of this collection; it is the record such as tail().getPrevious() holds the last collection value.
Index	valueOf(FastCollection.Record record) Returns the collection value for the specified record.
void	xor(FastBitSet that) Performs the logical XOR operation on this bit set and the one specified.

Methods inherited from class javolution.util.FastCollection

addAll, contains, containsAll, getValueComparator, isEmpty, iterator, remove, removeAll, retainAll, shared, toArray, toArray, toString, toText, unmodifiable

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Set

addAll, contains, containsAll, isEmpty, iterator, remove, removeAll, retainAll, spliterator, toArray, toArray

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

FastBitSet

public FastBitSet()

Creates a bit set of small initial capacity. All bits are initially false.

FastBitSet

public FastBitSet(int bitSize)

Creates a bit set of specified initial capacity (in bits). All bits are initially false. This constructor reserves enough space to represent the integers from 0 to bitSize-1.

Parameters:

bitSize - the initial capacity in bits.

Method Detail

newInstance

public static FastBitSet newInstance()

Returns a new, preallocated or recycled set instance (on the stack when executing in a StackContext).

Returns:

a new, preallocated or recycled set instance.

recycle

public static void recycle(FastBitSet instance)

Recycles a set instance immediately (on the stack when executing in a StackContext).

add

public boolean add(Index index)

Adds the specified index to this set. This method is equivalent to set(index.intValue()).

Specified by:

add in interface java.util.Collection<Index>

Specified by:

add in interface java.util.Set<Index>

Overrides:

add in class FastCollection<Index>

Parameters:

index - the integer value to be appended to this set.

Returns:

true if this set did not contains the specified index; false otherwise.

and

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

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 java.util.Collection<Index>

Specified by:

clear in interface java.util.Set<Index>

Overrides:

clear in class FastCollection<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:

java.lang.IndexOutOfBoundsException - if index < 0

clear

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:

java.lang.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:

java.lang.IndexOutOfBoundsException - if bitIndex < 0

flip

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:

java.lang.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:

java.lang.IndexOutOfBoundsException - if bitIndex < 0

get

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:

java.lang.IndexOutOfBoundsException - if (fromIndex < 0) | (toIndex < fromIndex)

intersects

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.

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 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:

java.lang.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)) {
         ...
    }

Parameters:

fromIndex - the start location.

Returns:

the first false bit.

Throws:

java.lang.IndexOutOfBoundsException - if fromIndex < 0

or

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:

java.lang.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:

java.lang.IndexOutOfBoundsException - if bitIndex < 0

set

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:

java.lang.IndexOutOfBoundsException - if (fromIndex < 0) | (toIndex < fromIndex)

set

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:

java.lang.IndexOutOfBoundsException - if bitIndex < 0

size

public int size()

Returns the cardinality of this bit set (number of bits set).

Note: Unlike java.util.BitSet this method does not returns an approximation of the number of bits of space actually in use. This method is compliant with java.util.Collection meaning for size().

Specified by:

size in interface java.util.Collection<Index>

Specified by:

size in interface java.util.Set<Index>

Specified by:

size in class FastCollection<Index>

Returns:

the cardinality of this bit set.

xor

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.

equals

public boolean equals(java.lang.Object obj)

Description copied from class: FastCollection

Compares the specified object with this collection for equality. The default behavior is to consider two collections equal if they hold the same values and have the same iterative order if any of the collections is an ordered collection (List instances). Equality comparisons are performed using this collection value comparator.

Specified by:

equals in interface java.util.Collection<Index>

Specified by:

equals in interface java.util.Set<Index>

Overrides:

equals in class FastCollection<Index>

Parameters:

obj - the object to be compared for equality with this collection

Returns:

true if the specified object is a collection with the same content and iteration order when necessary; false otherwise.

hashCode

public int hashCode()

Description copied from class: FastCollection

Returns the hash code for this collection. For non-ordered collection the hashcode of this collection is the sum of the hashcode of its values.

Specified by:

hashCode in interface java.util.Collection<Index>

Specified by:

hashCode in interface java.util.Set<Index>

Overrides:

hashCode in class FastCollection<Index>

Returns:

the hash code for this collection.

reset

public void reset()

Description copied from interface: Reusable

Resets the internal state of this object to its default values.

Specified by:

reset in interface Reusable

head

public FastCollection.Record head()

Description copied from class: FastCollection

Returns the head record of this collection; it is the record such as head().getNext() holds the first collection value.

Specified by:

head in class FastCollection<Index>

Returns:

the head record.

tail

public FastCollection.Record tail()

Description copied from class: FastCollection

Returns the tail record of this collection; it is the record such as tail().getPrevious() holds the last collection value.

Specified by:

tail in class FastCollection<Index>

Returns:

the tail record.

valueOf

public Index valueOf(FastCollection.Record record)

Description copied from class: FastCollection

Returns the collection value for the specified record.

Specified by:

valueOf in class FastCollection<Index>

Parameters:

record - the record whose current value is returned.

Returns:

the current value.

delete

public void delete(FastCollection.Record record)

Description copied from class: FastCollection

Deletes the specified record from this collection.

Implementation must ensure that removing a record from the collection does not affect in any way the records preceding the record being removed (it might affect the next records though, e.g. in a list collection, the indices of the subsequent records will change).

Specified by:

delete in class FastCollection<Index>

Parameters:

record - the record to be removed.