de.upb.swtpra05.group03.shuttle.util
Class EfficientBitSet

java.lang.Object
  java.util.BitSet
      de.upb.swtpra05.group03.shuttle.util.EfficientBitSet

All Implemented Interfaces:

java.lang.Cloneable, java.io.Serializable

public class EfficientBitSet

extends java.util.BitSet

This is a memory efficient variant of a BitSet. A BitSet is not memory efficient for large bit indices. If one sets e.g. only 8-digit numbers a BitSet would also allocate the indices from zero to these numbers. This is inefficient cause some methods of the BitSet iterate trough the whole set which takes a lot of time. This extension saves the smallest known index number and offers the lower bits only implicitly. These are set to false. This is realized completely transparent, so that the EfficientBitSet can be used in the same way. It is possible to set the lowest index in a new constructor or via the method normalizeTo(int).

Version:

$Revision: 1.3 $

See Also:

BitSet, Serialized Form

Field Summary

private int

smallestBitIndex The smallest known index number.

Fields inherited from class java.util.BitSet

Constructor Summary

EfficientBitSet()
The intially smallest index number is Integer.MAX_VALUE.

EfficientBitSet(int nbits)
The intially smallest index number is Integer.MAX_VALUE.

EfficientBitSet(int nbits, int smallestBitIndex)
The intially smallest index number is smallestBitIndex.

Method Summary

void	and(java.util.BitSet set) This method overrides BitSet.and(BitSet) so that a logical AND can only be used with another EfficientBitSet
void	and(EfficientBitSet set) Performs a logical AND of this target bit set with the argument bit set.
void	andNot(java.util.BitSet set) This method overrides BitSet.andNot(BitSet) so that a logical ANDNOT can only be used with another EfficientBitSet
void	andNot(EfficientBitSet set) Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.
int	cardinality()
void	clear()
void	clear(int bitIndex)
void	clear(int fromIndex, int toIndex)
java.lang.Object	clone()
boolean	equals(java.lang.Object obj)
int	explicitSize() The explicit size of this set is the number of bits of space in use.
void	flip(int bitIndex)
void	flip(int fromIndex, int toIndex)
boolean	get(int bitIndex)
java.util.BitSet	get(int fromIndex, int toIndex)
int	getSmallestBitIndex() Gets the current smallest known index number
int	hashCode()
int	implicitSize() The implicit size ot this set is the number of bits of space in use plus the implicit number of bits which are smaller than the lowest known index.
boolean	intersects(java.util.BitSet set) This method overrides BitSet.intersects(BitSet) so that an EfficientBitSet can only be intersected with an EfficientBitSet.
boolean	intersects(EfficientBitSet set) Returns true if the specified EfficientBitSet has any bits set to true that are also set to true in this EfficientBitSet.
boolean	isEmpty()
int	length()
int	nextClearBit(int fromIndex)
int	nextSetBit(int fromIndex)
void	normalizeTo(int newSmallestBitIndex) Normalizes this set to the newSmallestBitIndex number which is either smaller or bigger than the current smallest known index.
void	or(java.util.BitSet set) This method overrides BitSet.or(BitSet) so that a logical OR can only be used with another EfficientBitSet
void	or(EfficientBitSet set) Performs a logical OR of this bit set with the bit set argument.
void	set(int bitIndex)
void	set(int bitIndex, boolean value)
void	set(int fromIndex, int toIndex)
void	set(int fromIndex, int toIndex, boolean value)
int	size() Deprecated. use EfficientBitSet.implicitSize() or EfficientBitSet.explicitSize() instead.
java.lang.String	toString()
void	xor(java.util.BitSet set) This method overrides BitSet.xor(BitSet) so that a logical XOR can only be used with another EfficientBitSet
void	xor(EfficientBitSet set) Performs a logical XOR of this bit set with the bit set argument.

Methods inherited from class java.util.BitSet

Methods inherited from class java.lang.Object

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

Field Detail

smallestBitIndex

private int smallestBitIndex

The smallest known index number. All lower indices are implicitly false.

Constructor Detail

EfficientBitSet

public EfficientBitSet()

The intially smallest index number is Integer.MAX_VALUE.

See Also:

java.util.BitSet#EfficientBitSet()

EfficientBitSet

public EfficientBitSet(int nbits)

The intially smallest index number is Integer.MAX_VALUE.

Parameters:

nbits - No description provided

See Also:

java.util.BitSet#EfficientBitSet(int)

EfficientBitSet

public EfficientBitSet(int nbits,
                       int smallestBitIndex)

The intially smallest index number is smallestBitIndex.

Parameters:

smallestBitIndex - The intial value of the smallest index number.

nbits - No description provided

See Also:

java.util.BitSet#EfficientBitSet(int)

Method Detail

flip

public void flip(int bitIndex)

Parameters:

bitIndex - No description provided

See Also:

BitSet.flip(int)

flip

public void flip(int fromIndex,
                 int toIndex)

Parameters:

fromIndex - No description provided

toIndex - No description provided

See Also:

BitSet.flip(int,int)

set

public void set(int bitIndex)

Parameters:

bitIndex - No description provided

See Also:

BitSet.set(int)

set

public void set(int bitIndex,
                boolean value)

Parameters:

bitIndex - No description provided

value - No description provided

See Also:

BitSet.set(int, boolean)

set

public void set(int fromIndex,
                int toIndex)

Parameters:

fromIndex - No description provided

toIndex - No description provided

See Also:

BitSet.set(int,int)

set

public void set(int fromIndex,
                int toIndex,
                boolean value)

Parameters:

fromIndex - No description provided

toIndex - No description provided

value - No description provided

See Also:

BitSet.set(int,int,boolean)

clear

public void clear(int bitIndex)

Parameters:

bitIndex - No description provided

See Also:

BitSet.clear(int)

clear

public void clear(int fromIndex,
                  int toIndex)

Parameters:

fromIndex - No description provided

toIndex - No description provided

See Also:

BitSet.clear(int,int)

clear

public void clear()

See Also:

BitSet.clear()

get

public boolean get(int bitIndex)

Parameters:

bitIndex - No description provided

Returns:

No description provided

See Also:

BitSet.get(int)

get

public java.util.BitSet get(int fromIndex,
                            int toIndex)

Parameters:

fromIndex - No description provided

toIndex - No description provided

Returns:

No description provided

See Also:

BitSet.get(int,int)

nextSetBit

public int nextSetBit(int fromIndex)

Parameters:

fromIndex - No description provided

Returns:

No description provided

See Also:

BitSet.nextSetBit(int)

nextClearBit

public int nextClearBit(int fromIndex)

Parameters:

fromIndex - No description provided

Returns:

No description provided

See Also:

BitSet.nextClearBit(int)

length

public int length()

Returns:

No description provided

See Also:

BitSet.length()

isEmpty

public boolean isEmpty()

Returns:

The empty value

See Also:

BitSet.isEmpty()

intersects

public boolean intersects(java.util.BitSet set)

This method overrides BitSet.intersects(BitSet) so that an EfficientBitSet can only be intersected with an EfficientBitSet.

Parameters:

set - No description provided

Returns:

No description provided

See Also:

BitSet.intersects(java.util.BitSet)

intersects

public boolean intersects(EfficientBitSet set)

Returns true if the specified EfficientBitSet has any bits set to true that are also set to true in this EfficientBitSet.

Parameters:

set - EfficientBitSet to intersect with

Returns:

boolean indicating whether this BitSet intersects the specified EfficientBitSet.

cardinality

public int cardinality()

Returns:

No description provided

See Also:

BitSet.cardinality()

and

public void and(java.util.BitSet set)

This method overrides BitSet.and(BitSet) so that a logical AND can only be used with another EfficientBitSet

Parameters:

set - No description provided

See Also:

BitSet.and(java.util.BitSet)

and

public void and(EfficientBitSet set)

Performs a logical AND of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also had the value true.

Parameters:

set - a bit set.

or

public void or(java.util.BitSet set)

This method overrides BitSet.or(BitSet) so that a logical OR can only be used with another EfficientBitSet

Parameters:

set - No description provided

See Also:

BitSet.or(java.util.BitSet)

or

public void or(EfficientBitSet set)

Performs a logical OR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value true.

Parameters:

set - a bit set.

xor

public void xor(java.util.BitSet set)

This method overrides BitSet.xor(BitSet) so that a logical XOR can only be used with another EfficientBitSet

Parameters:

set - No description provided

See Also:

BitSet.xor(java.util.BitSet)

xor

public void xor(EfficientBitSet set)

Performs a logical XOR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if one of the following statements holds:

• The bit initially has the value true, and the corresponding bit in the argument has the value false.
• The bit initially has the value false, and the corresponding bit in the argument has the value true.

Parameters:

set - a bit set.

andNot

public void andNot(java.util.BitSet set)

This method overrides BitSet.andNot(BitSet) so that a logical ANDNOT can only be used with another EfficientBitSet

Parameters:

set - No description provided

See Also:

BitSet.andNot(java.util.BitSet)

andNot

public void andNot(EfficientBitSet set)

Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.

Parameters:

set - the BitSet with which to mask this BitSet.

hashCode

public int hashCode()

Returns:

No description provided

See Also:

BitSet.hashCode()

size

public int size()

Deprecated. use EfficientBitSet.implicitSize() or EfficientBitSet.explicitSize() instead.

This method shouldn't be used anymore. explicitSize() has the same result.

Returns:

No description provided

See Also:

BitSet.size()

implicitSize

public int implicitSize()

The implicit size ot this set is the number of bits of space in use plus the implicit number of bits which are smaller than the lowest known index.

Returns:

the number of bits currently in this bit set plus the number of implicit bits

See Also:

BitSet.size()

explicitSize

public int explicitSize()

The explicit size of this set is the number of bits of space in use.

Returns:

the number of bits currently in this bit set

See Also:

BitSet.size()

equals

public boolean equals(java.lang.Object obj)

Parameters:

obj - No description provided

Returns:

No description provided

See Also:

BitSet.equals(java.lang.Object)

clone

public java.lang.Object clone()

Returns:

No description provided

See Also:

BitSet.clone()

toString

public java.lang.String toString()

Returns:

No description provided

See Also:

BitSet.toString()

normalizeTo

public void normalizeTo(int newSmallestBitIndex)
                 throws java.lang.Exception

Normalizes this set to the newSmallestBitIndex number which is either smaller or bigger than the current smallest known index.

Parameters:

newSmallestBitIndex - the new smallest index number

Throws:

java.lang.Exception - if the new smallest index number is bigger than the current one and there are bits set to true below the new one

getSmallestBitIndex

public int getSmallestBitIndex()

Gets the current smallest known index number

Returns:

The smallest known index number