scale.common
Class BitVect

java.lang.Object
  scale.common.BitVect

All Implemented Interfaces:

java.lang.Cloneable

public final class BitVect
extends java.lang.Object
implements java.lang.Cloneable

A class which implements a vector of bits similar to java.util.BitSet.

$Id: BitVect.java,v 1.37 2007-10-04 19:58:10 burrill Exp $

Copyright 2007 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

This class differs from java.util.BitSet in that it saves space by not storing words, at the beginning and end of a vector, that are all zero bits.

See Also:

BitSet

Constructor Summary

BitVect()
Create a bit vector.

BitVect(int nbits)
Create a bit vector with pre-allocated size for nbits bits.

BitVect(int firstBit, int lastBit)
Create a bit vector with pre-allocated size for a range of bits.

Method Summary

void	and(BitVect o) And this bit vector with the specified bit vector.
void	andNot(BitVect o) And this bit vector with the logical complement of the specified bit vector.
void	andNotTo(int[] bits) And the specified array with the logical complement of this bit vector.
void	clear(int index) Clear the bit at the specified index.
BitVect	clone()
void	copyTo(int[] bits) Copy the bit vector into the specified int array.
int	count() Return the number of bits set.
void	define(int[] o) Set this bit vector with the specified array of bits.
boolean	empty() Return true if the bit vector is all zeros.
boolean	equivalent(BitVect o) Return true if the two bit vectors are identical.
boolean	get(int index) Return the bit at the specified index.
int[]	getSetBits() Return an array of integers specifying which bits are set.
int	getSetBits(int[] result) Set an array of integers specifying which bits are set.
static BitVect	getSlice(int slice, BitVect[] in) Return a column of a bit array that is represented by an array of BitVect instances.
void	histogram(int[] hist) Increase the histogram by one in every position there is a bit in the bit vector.
boolean	intersect(BitVect o) Return true if the intersection is non-null.
int	intersectCount(BitVect o) Return the number of intersections.
int	length() Return the index plus one of the last bit set.
void	or(BitVect o) Or this bit vector with the specified bit vector.
boolean	orAndTest(BitVect o) Or this bit vector with the specified bit vector.
boolean	orTo(int[] bits) Or this bit vector with the specified array.
void	outputSetBits() Display the bits set by their index values.
void	reset() Empty the bit vector.
void	set(int index) Set the bit at the specified index.
int	size() Return the number of bits actually in use to represent this bit vector.
java.lang.String	toString() Return a String representation of the bit vector.
static void	transpose(BitVect[] out, BitVect[] in) Transpose a matrix of bits.
void	trim() If possible, reduce the space required by this bit vector.
void	xor(BitVect o) Exclusive or this bit vector with the specified bit vector.

Methods inherited from class java.lang.Object

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

Constructor Detail

BitVect

public BitVect()

Create a bit vector.

BitVect

public BitVect(int nbits)

Create a bit vector with pre-allocated size for nbits bits.

BitVect

public BitVect(int firstBit,
               int lastBit)

Create a bit vector with pre-allocated size for a range of bits.

Method Detail

clone

public BitVect clone()

Overrides:

clone in class java.lang.Object

copyTo

public void copyTo(int[] bits)

Copy the bit vector into the specified int array. The bit vector is represented by 32 bits per int. Bits are numbered right to left within a word. The specified array must be large enough to hold all the bits.

reset

public void reset()

Empty the bit vector.

trim

public final void trim()

If possible, reduce the space required by this bit vector.

intersectCount

public int intersectCount(BitVect o)

Return the number of intersections.

intersect

public boolean intersect(BitVect o)

Return true if the intersection is non-null.

and

public void and(BitVect o)

And this bit vector with the specified bit vector.

andNot

public void andNot(BitVect o)

And this bit vector with the logical complement of the specified bit vector.

andNotTo

public void andNotTo(int[] bits)

And the specified array with the logical complement of this bit vector. This bit vector is not changed.

or

public void or(BitVect o)

Or this bit vector with the specified bit vector.

orAndTest

public boolean orAndTest(BitVect o)

Or this bit vector with the specified bit vector.

Returns:

true if this bit vector was modified.

orTo

public boolean orTo(int[] bits)

Or this bit vector with the specified array. This bit vector is not changed.

Returns:

true if the resulting array is not equivalent to this bit vector

define

public void define(int[] o)

Set this bit vector with the specified array of bits. The bit vector is represented by 32 bits per int. Bits are numbered right to left within a word.

xor

public void xor(BitVect o)

Exclusive or this bit vector with the specified bit vector.

equivalent

public boolean equivalent(BitVect o)

Return true if the two bit vectors are identical.

set

public void set(int index)

Set the bit at the specified index.

clear

public void clear(int index)

Clear the bit at the specified index.

get

public boolean get(int index)

Return the bit at the specified index.

length

public int length()

Return the index plus one of the last bit set.

count

public int count()

Return the number of bits set.

empty

public boolean empty()

Return true if the bit vector is all zeros.

size

public int size()

Return the number of bits actually in use to represent this bit vector.

toString

public java.lang.String toString()

Return a String representation of the bit vector.

Overrides:

toString in class java.lang.Object

Returns:

a String representation of the bit vector

histogram

public void histogram(int[] hist)

Increase the histogram by one in every position there is a bit in the bit vector.

transpose

public static void transpose(BitVect[] out,
                             BitVect[] in)

Transpose a matrix of bits. This algorithm is quick if the input array is sparse.

Parameters:

out - specifies the output array

in - is the array of BitVect instances

getSlice

public static BitVect getSlice(int slice,
                               BitVect[] in)

Return a column of a bit array that is represented by an array of BitVect instances.

Parameters:

slice - specifies the column

in - is the array of BitVect instances

getSetBits

public int[] getSetBits()

Return an array of integers specifying which bits are set.

getSetBits

public int getSetBits(int[] result)

Set an array of integers specifying which bits are set. It is assumed that the array is large enough; use the count() method to determine the proper size.

Returns:

the number set

outputSetBits

public void outputSetBits()

Display the bits set by their index values. The display goes to System.out.