umontreal.iro.lecuyer.util
Class BitMatrix

java.lang.Object
  umontreal.iro.lecuyer.util.BitMatrix

All Implemented Interfaces:

Serializable, Cloneable

public class BitMatrix
extends Object
implements Serializable, Cloneable

This class implements matrices of bits of arbitrary dimensions. Basic facilities for bits operations, multiplications and exponentiations are provided.

See Also:

Serialized Form

Nested Class Summary

class

BitMatrix.IncompatibleDimensionException Runtime exception raised when the dimensions of the BitMatrix are not appropriate for the operation.

Constructor Summary

BitMatrix(BitMatrix that)
Copy constructor.

BitMatrix(BitVector[] rows)
Creates a new BitMatrix using the data in rows.

BitMatrix(int[][] data, int r, int c)
Creates a new BitMatrix with r rows and c columns using the data in data.

BitMatrix(int r, int c)
Creates a new BitMatrix with r rows and c columns filled with 0's.

Method Summary

BitMatrix	and(BitMatrix that) Returns the BitMatrix resulting from the application of the and operator on the original BitMatrix and that.
Object	clone() Creates a copy of the BitMatrix.
boolean	equals(BitMatrix that) Verifies that this and that are strictly identical.
boolean	getBool(int row, int column) Returns the value of the bit in the specified row and column.
BitMatrix	multiply(BitMatrix that) Multiplies two BitMatrix's together.
BitVector	multiply(BitVector vect) Multiplies the column BitVector by a BitMatrix and returns the result.
int	multiply(int vect) Multiplies vect, seen as a column BitVector, by a BitMatrix.
BitMatrix	not() Returns the BitMatrix resulting from the application of the not operator on the original BitMatrix.
int	numColumns() Returns the number of columns of the BitMatrix.
int	numRows() Returns the number of rows of the BitMatrix.
BitMatrix	or(BitMatrix that) Returns the BitMatrix resulting from the application of the or operator on the original BitMatrix and that.
BitMatrix	power(long p) Raises the BitMatrix to the power p.
BitMatrix	power2e(int e) Raises the BitMatrix to power 2e.
String	printData() Creates a String containing all the data of the BitMatrix.
void	setBool(int row, int column, boolean value) Changes the value of the bit in the specified row and column.
String	toString() Creates a String containing all the data of the BitMatrix.
BitMatrix	transpose() Returns the transposed matrix.
BitMatrix	xor(BitMatrix that) Returns the BitMatrix resulting from the application of the xor operator on the original BitMatrix and that.

Methods inherited from class java.lang.Object

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

Constructor Detail

BitMatrix

public BitMatrix(int r,
                 int c)

Creates a new BitMatrix with r rows and c columns filled with 0's.

Parameters:

r - the number of rows

c - the number of columns

BitMatrix

public BitMatrix(BitVector[] rows)

Creates a new BitMatrix using the data in rows. Each of the BitVector will be one of the rows of the BitMatrix.

Parameters:

rows - the rows of the new BitMatrix

BitMatrix

public BitMatrix(int[][] data,
                 int r,
                 int c)

Creates a new BitMatrix with r rows and c columns using the data in data. Note that the orders of the bits for the rows are using the same order than for the BitVector. This does mean that the first bit is the lowest order bit of the last int in the row and the last bit is the highest order bit of the first int int the row.

Parameters:

data - the data of the new BitMatrix

r - the number of rows

c - the number of columns

BitMatrix

public BitMatrix(BitMatrix that)

Copy constructor.

Parameters:

that - the BitMatrix to copy

Method Detail

clone

public Object clone()

Creates a copy of the BitMatrix.

Overrides:

clone in class Object

Returns:

a deep copy of the BitMatrix

equals

public boolean equals(BitMatrix that)

Verifies that this and that are strictly identical. They must both have the same dimensions and data.

Parameters:

that - the BitMatrix to compare

Returns:

if the two BitMatrix are identical

toString

public String toString()

Creates a String containing all the data of the BitMatrix. The result is displayed in a matrix form, with each row being put on a different line. Note that the bit at (0,0) is at the upper left of the matrix, while the bit at (0) in a BitVector is the least significant bit.

Overrides:

toString in class Object

Returns:

the content of the BitMatrix

printData

public String printData()

Creates a String containing all the data of the BitMatrix. The data is displayed in the same format as are the int[][] in Java code. This allows the user to print the representation of a BitMatrix to be put, directly in the source code, in the constructor BitMatrix(int[][], int, int). The output is not designed to be human-readable.

Returns:

the content of the BitMatrix

numRows

public int numRows()

Returns the number of rows of the BitMatrix.

Returns:

the number of rows

numColumns

public int numColumns()

Returns the number of columns of the BitMatrix.

Returns:

the number of columns

getBool

public boolean getBool(int row,
                       int column)

Returns the value of the bit in the specified row and column. If the value is 1, return true. If it is 0, return false.

Parameters:

row - the row of the selected bit

column - the column of the selected bit

Returns:

the value of the bit as a boolean

Throws:

IndexOutOfBoundsException - if the selected bit would be outside the BitMatrix

setBool

public void setBool(int row,
                    int column,
                    boolean value)

Changes the value of the bit in the specified row and column. If value is true, changes it to 1. If value is false changes it to 0.

Parameters:

row - the row of the selected bit

column - the column of the selected bit

value - the new value of the bit as a boolean

Throws:

IndexOutOfBoundsException - if the selected bit would be outside the BitMatrix

transpose

public BitMatrix transpose()

Returns the transposed matrix. The rows and columns are interchanged.

Returns:

the transposed matrix

not

public BitMatrix not()

Returns the BitMatrix resulting from the application of the not operator on the original BitMatrix. The effect is to swap all the bits of the BitMatrix, turning all 0 into 1 and all 1 into 0.

Returns:

the result of the not operator

and

public BitMatrix and(BitMatrix that)

Returns the BitMatrix resulting from the application of the and operator on the original BitMatrix and that. Only bits which were at 1 in both BitMatrix are set at 1 in the result. All others are set to 0.

Parameters:

that - the second operand of the and operator

Returns:

the result of the and operator

Throws:

BitMatrix.IncompatibleDimensionException - if the two BitMatrix are not of the same dimensions

or

public BitMatrix or(BitMatrix that)

Returns the BitMatrix resulting from the application of the or operator on the original BitMatrix and that. Only bits which were at 0 in both BitMatrix are set at 0 in the result. All others are set to 1.

Parameters:

that - the second operand of the or operator

Returns:

the result of the or operator

Throws:

BitMatrix.IncompatibleDimensionException - if the two BitMatrix are not of the same dimensions

xor

public BitMatrix xor(BitMatrix that)

Returns the BitMatrix resulting from the application of the xor operator on the original BitMatrix and that. Only bits which were at 1 in only one of the two BitMatrix are set at 1 in the result. All others are set to 0.

Parameters:

that - the second operand of the xor operator

Returns:

the result of the xor operator

Throws:

BitMatrix.IncompatibleDimensionException - if the two BitMatrix are not of the same dimensions

multiply

public BitVector multiply(BitVector vect)

Multiplies the column BitVector by a BitMatrix and returns the result. The result is A×v, where A is the BitMatrix, and v is the BitVector.

Parameters:

vect - the vector to multiply

Returns:

the result of the multiplication

multiply

public int multiply(int vect)

Multiplies vect, seen as a column BitVector, by a BitMatrix. (See BitVector to see the conversion between int and BitVector.) The result is A×v, where A is the BitMatrix, and v is the BitVector.

Parameters:

vect - the vector to multiply

Returns:

the result of the multiplication, as an int

multiply

public BitMatrix multiply(BitMatrix that)

Multiplies two BitMatrix's together. The result is A×B, where A is the this BitMatrix and B is the that BitMatrix.

Parameters:

that - the other BitMatrix to multiply

Returns:

the result of the multiplication

Throws:

BitMatrix.IncompatibleDimensionException - if the number of columns of the first BitMatrix is not equal to the number of rows of the second BitMatrix

power

public BitMatrix power(long p)

Raises the BitMatrix to the power p.

Parameters:

p - the power up to which to raise the BitMatrix

Returns:

the power of the BitMatrix

Throws:

BitMatrix.IncompatibleDimensionException - if the BitMatrix is not square

IllegalArgumentException - if p is negative

power2e

public BitMatrix power2e(int e)

Raises the BitMatrix to power 2^e.

Parameters:

e - the exponent of the power up to which to raise the BitMatrix

Returns:

the power of the BitMatrix

Throws:

BitMatrix.IncompatibleDimensionException - if the BitMatrix is not square