choco.mem
Class StoredBitSet

java.lang.Object
  choco.mem.StoredBitSet

public class StoredBitSet
extends java.lang.Object

A set of bits (0/1 values) with backtrackable structures. Implemented with a backtrackable vector of integer.

Field Summary

protected StoredIntVector

representedBy A stored integer vector containing the bit representation.

Constructor Summary

StoredBitSet(Environment env, int initialSize)
Builds a new stored bit set.

Method Summary

int	capacity()
int	cardinality() Number of bits on.
void	clear(int bitIndex) Puts the specified bit off.
void	ensureCapacity(int bitIndex)
boolean	get(int bitIndex)
IntIterator	getCycleButIterator(int avoidIndex)
int	nextSetBit(int fromIndex) Returns the index of the first bit that is set to true that occurs on or after the specified starting index.
int	prevSetBit(int fromIndex) Returns the index of the first bit that is set to true that occurs on or before the specified starting index.
void	set(int bitIndex) Puts the specified bit on.
void	set(int index, boolean value)
static int	startingZeroCnt(int val) Counts the number of clear bits starting from the heaviest (leftmost) one assumes val contains some bits that are set.
static int	trailingZeroCnt(int val) Counts the number of clear bits starting from the lightest (rightmost) one assumes val contains some bits that are set.

Methods inherited from class java.lang.Object

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

Field Detail

representedBy

protected final StoredIntVector representedBy

A stored integer vector containing the bit representation.

Constructor Detail

StoredBitSet

public StoredBitSet(Environment env,
                    int initialSize)

Builds a new stored bit set.

Parameters:

env - the environment reponsible of worlds management

initialSize - the initial size (number of bits needed)

Method Detail

cardinality

public int cardinality()

Number of bits on. Sums the number of on bits in each integer.

Returns:

the total number of bits on

set

public void set(int bitIndex)

Puts the specified bit on.

Parameters:

bitIndex - the bit to put on

clear

public void clear(int bitIndex)

Puts the specified bit off.

Parameters:

bitIndex - the bit to put off

set

public void set(int index,
                boolean value)

get

public boolean get(int bitIndex)

nextSetBit

public int nextSetBit(int fromIndex)

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:

fromIndex - 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.

Since:

1.4

trailingZeroCnt

public static int trailingZeroCnt(int val)

Counts the number of clear bits starting from the lightest (rightmost) one assumes val contains some bits that are set.

Parameters:

val - the integer, taken as a 32-bit set

Returns:

the index of the rightmost bit that is set

prevSetBit

public int prevSetBit(int fromIndex)

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.

Parameters:

fromIndex - 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 or too large

startingZeroCnt

public static int startingZeroCnt(int val)

Counts the number of clear bits starting from the heaviest (leftmost) one assumes val contains some bits that are set.

Parameters:

val - the integer, taken as a 32-bit set

Returns:

the index of the leftmost bit that is set

capacity

public int capacity()

ensureCapacity

public void ensureCapacity(int bitIndex)

getCycleButIterator

public IntIterator getCycleButIterator(int avoidIndex)