org.ka2ddo.util

Class HugeBitSet

java.lang.Object

org.ka2ddo.util.HugeBitSet

public final class HugeBitSet
extends java.lang.Object

This class implements a BitSet using a segmented array, so that growth to unreasonably huge sizes will not require having enough heap space for two contiguous copies of the bitset (to handle copying upon array growth). Instead, this class adds more segments, so existing segment data does not have to be copied and the size of contiguous heap allocations remains constant instead of growing.

Note that the maximum size of a HugeBitSet is 2**32 - 1 bits.

Author:

Andrew Pavlin, KA2DDO

Constructor Summary

Constructors

Constructor and Description
HugeBitSet() Create a HugeBitSet with no preallocated blocks.
HugeBitSet(int prealloc) Create a HugeBitSet with memory allocated for up to the specific bit number,

Method Summary

Modifier and Type	Method and Description
void	clear() Clear all the bits in the HugeBitSet.
boolean	clear(int index) Clear the specified bit in the HugeBitSet.
boolean	get(int index) Test if the specified bit is set in the HugeBitSet.
boolean	isSet(int index) Test if the specified bit is set in the HugeBitSet.
boolean	isSet(long index) Test if the specified bit is set in the HugeBitSet.
void	justSet(int index) Set the specified bit in the HugeBitSet without returning the former state.
void	justSet(long index) Set the specified bit in the HugeBitSet without returning the former state.
int	length() Get the maximum number of bits currently allocated in this HugeBitSet.
int	nextClearBit(int index) Returns the index of the first bit that is set to false that occurs on or after the specified starting index.
int	nextSetBit(int index) Returns the index of the first bit that is set to true that occurs on or after the specified starting index.
void	preallocate(int numBits) Ensure that enough storage has been allocated in the HugeBitSet to hold at least the specified range of bits.
int	previousClearBit(int index) Returns the index of the first bit that is set to false that occurs on or prior the specified starting index.
int	previousSetBit(int index) Returns the index of the first bit that is set to true that occurs on or before the specified starting index.
boolean	set(int index) Set the specified bit in the HugeBitSet.
boolean	setIfNot(int index) Set the specified bit in the HugeBitSet and indicate whether this was a change.
java.lang.String	toString() Generate a String describing this HugeBitSet.

Methods inherited from class java.lang.Object

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

Constructor Detail

HugeBitSet

public HugeBitSet()

Create a HugeBitSet with no preallocated blocks.

HugeBitSet

public HugeBitSet(int prealloc)

Create a HugeBitSet with memory allocated for up to the specific bit number,

Parameters:

prealloc - highest bit number to preallocate for

Method Detail

set

public boolean set(int index)

Set the specified bit in the HugeBitSet.

Parameters:

index - zero-based int index of the bit to set

Returns:

boolean true if the bit was set prior to this call, false if clear

justSet

public void justSet(int index)

Set the specified bit in the HugeBitSet without returning the former state.

Parameters:

index - zero-based int index of the bit to set

justSet

public void justSet(long index)

Set the specified bit in the HugeBitSet without returning the former state.

Parameters:

index - zero-based long index of the bit to set

setIfNot

public boolean setIfNot(int index)

Set the specified bit in the HugeBitSet and indicate whether this was a change.

Parameters:

index - zero-based int index of the bit to set

Returns:

boolean true if bit was formerly clear (freshly set), false otherwise

clear

public boolean clear(int index)

Clear the specified bit in the HugeBitSet.

Parameters:

index - zero-based int index of the bit to set

Returns:

boolean true if the bit was set prior to this call, false if clear

clear

public void clear()

Clear all the bits in the HugeBitSet. Note that this does not free any storage blocks allocated by previous calls to set() or justSet().

preallocate

public void preallocate(int numBits)

Ensure that enough storage has been allocated in the HugeBitSet to hold at least the specified range of bits.

Parameters:

numBits - highest bit number for which storage should be allocated when this method returns

get

public boolean get(int index)

Test if the specified bit is set in the HugeBitSet.

Parameters:

index - zero-based index of bit to test

Returns:

boolean true if bit is set, or false if bit is clear

isSet

public boolean isSet(int index)

Test if the specified bit is set in the HugeBitSet.

Parameters:

index - zero-based index of bit to test

Returns:

boolean true if bit is set, or false if bit is clear

isSet

public boolean isSet(long index)

Test if the specified bit is set in the HugeBitSet.

Parameters:

index - zero-based index of bit to test

Returns:

boolean true if bit is set, or false if bit is clear

toString

public java.lang.String toString()

Generate a String describing this HugeBitSet.

Overrides:

toString in class java.lang.Object

Returns:

descriptive String

length

public int length()

Get the maximum number of bits currently allocated in this HugeBitSet.

Returns:

maximum bit index + 1 currently allocated

nextSetBit

public int nextSetBit(int index)

Returns the index of the first bit that is set to true that occurs on or after the specified starting index. If no such bit exists then -1 is returned. To iterate over the true bits in a BitSet, use the following loop: for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { // operate on index i here }

Parameters:

index - the index to start checking from (inclusive).

Returns:

the index of the next set bit.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

nextClearBit

public int nextClearBit(int index)

Returns the index of the first bit that is set to false that occurs on or after the specified starting index. If no such bit exists then -1 is returned. To iterate over the false bits in a BitSet, use the following loop: for (int i = bs.nextClearBit(0); i >= 0; i = bs.nextClearBit(i+1)) { // operate on index i here }

Parameters:

index - the index to start checking from (inclusive).

Returns:

the index of the next clear bit.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

previousSetBit

public int previousSetBit(int index)

Returns the index of the first bit that is set to true that occurs on or before the specified starting index. If no such bit exists then -1 is returned. To iterate over the true bits in a BitSet, use the following loop: for (int i = bs.previousSetBit(Integer.MAX_VALUE); i >= 0; i = bs.previousSetBit(i-1)) { // operate on index i here }

Parameters:

index - the index to start checking from (inclusive).

Returns:

the index of the previous set bit.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

previousClearBit

public int previousClearBit(int index)

Returns the index of the first bit that is set to false that occurs on or prior the specified starting index. If no such bit exists then -1 is returned. To iterate over the false bits in a BitSet, use the following loop: for (int i = bs.previousClearBit(Integer.MAX_VALUE); i >= 0; i = bs.previousClearBit(i+1)) { // operate on index i here }

Parameters:

index - the index to start checking from (inclusive).

Returns:

the index of the previous clear bit.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.