Class BitMatrix

java.lang.Object
cern.colt.PersistentObject
cern.colt.bitvector.BitMatrix
All Implemented Interfaces:
Serializable, Cloneable
public class BitMatrix extends PersistentObject
Fixed sized (non resizable) n*m bit matrix. A bit matrix has a number of columns and rows, which are assigned upon instance construction - The matrix's size is then columns()*rows(). Bits are accessed via (column,row) coordinates.

Individual bits can be examined, set, or cleared. Rectangular parts (boxes) can quickly be extracted, copied and replaced. Quick iteration over boxes is provided by optimized internal iterators (forEach() methods). One BitMatrix may be used to modify the contents of another BitMatrix through logical AND, OR, XOR and other similar operations.

Legal coordinates range from [0,0] to [columns()-1,rows()-1]. Any attempt to access a bit at a coordinate column<0 || column>=columns() || row<0 || row>=rows() will throw an IndexOutOfBoundsException. Operations involving two bit matrices (like AND, OR, XOR, etc.) will throw an IllegalArgumentException if both bit matrices do not have the same number of columns and rows.

If you need extremely quick access to individual bits: Although getting and setting individual bits with methods get(...) and put(...) is quick, it is even quicker (but not safe) to use getQuick(...) and putQuick(...).

Note that this implementation is not synchronized.

Version:
1.0, 09/24/99
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected long[]
    bits
     
    protected int
    columns
     
    protected int
    rows
     

    Fields inherited from class PersistentObject

    serialVersionUID

  • Constructor Summary

    Constructors
    Constructor
    Description
    BitMatrix(int columns, int rows)
    Constructs a bit matrix with a given number of columns and rows.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    and(BitMatrix other)
    Performs a logical AND of the receiver with another bit matrix.
    void
    andNot(BitMatrix other)
    Clears all of the bits in receiver whose corresponding bit is set in the other bit matrix.
    int
    cardinality()
    Returns the number of bits currently in the true state.
    protected void
    checkDimensionCompatibility(BitMatrix other)
    Sanity check for operations requiring matrices with the same number of columns and rows.
    void
    clear()
    Clears all bits of the receiver.
    Object
    clone()
    Cloning this BitMatrix produces a new BitMatrix that is equal to it.
    int
    columns()
    Returns the number of columns of the receiver.
    protected void
    containsBox(int column, int row, int width, int height)
    Checks whether the receiver contains the given box.
    BitMatrix
    copy()
    Returns a shallow clone of the receiver; calls clone() and casts the result.
    protected long[]
    elements()
     
    protected void
    elements(long[] bits, int columns, int rows)
    You normally need not use this method.
    boolean
    equals(Object obj)
    Compares this object against the specified object.
    boolean
    forEachCoordinateInState(boolean state, IntIntProcedure procedure)
    Applies a procedure to each coordinate that holds a bit in the given state.
    boolean
    get(int column, int row)
    Returns from the receiver the value of the bit at the specified coordinate.
    boolean
    getQuick(int column, int row)
    Returns from the receiver the value of the bit at the specified coordinate; WARNING: Does not check preconditions.
    int
    hashCode()
    Returns a hash code value for the receiver.
    void
    not()
    Performs a logical NOT on the bits of the receiver.
    void
    or(BitMatrix other)
    Performs a logical OR of the receiver with another bit matrix.
    BitMatrix
    part(int column, int row, int width, int height)
    Constructs and returns a new matrix with width columns and height rows which is a copy of the contents of the given box.
    void
    put(int column, int row, boolean value)
    Sets the bit at the specified coordinate to the state specified by value.
    void
    putQuick(int column, int row, boolean value)
    Sets the bit at the specified coordinate to the state specified by value; WARNING: Does not check preconditions.
    void
    replaceBoxWith(int column, int row, int width, int height, boolean value)
    Sets the bits in the given box to the state specified by value.
    void
    replaceBoxWith(int column, int row, int width, int height, BitMatrix source, int sourceColumn, int sourceRow)
    Replaces a box of the receiver with the contents of another matrix's box.
    int
    rows()
    Returns the number of rows of the receiver.
    int
    size()
    Returns the size of the receiver which is columns()*rows().
    BitVector
    toBitVector()
    Converts the receiver to a bitvector.
    String
    toString()
    Returns a (very crude) string representation of the receiver.
    void
    xor(BitMatrix other)
    Performs a logical XOR of the receiver with another bit matrix.

    Methods inherited from class Object

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

  • Field Details

    • columns

      protected int columns

    • rows

      protected int rows

    • bits

      protected long[] bits

  • Constructor Details

    • BitMatrix

      public BitMatrix(int columns, int rows)
      Constructs a bit matrix with a given number of columns and rows. All bits are initially false.
      Parameters:
      columns - the number of columns the matrix shall have.
      rows - the number of rows the matrix shall have.
      Throws:
      IllegalArgumentException - if columns < 0 || rows < 0.

  • Method Details

    • and

      public void and(BitMatrix other)
      Performs a logical AND of the receiver with another bit matrix. The receiver is modified so that a bit in it has the value true if and only if it already had the value true and the corresponding bit in the other bit matrix argument has the value true.
      Parameters:
      other - a bit matrix.
      Throws:
      IllegalArgumentException - if columns() != other.columns() || rows() != other.rows().

    • andNot

      public void andNot(BitMatrix other)
      Clears all of the bits in receiver whose corresponding bit is set in the other bit matrix. In other words, determines the difference (A\B) between two bit matrices.
      Parameters:
      other - a bit matrix with which to mask the receiver.
      Throws:
      IllegalArgumentException - if columns() != other.columns() || rows() != other.rows().

    • cardinality

      public int cardinality()
      Returns the number of bits currently in the true state. Optimized for speed. Particularly quick if the receiver is either sparse or dense.

    • checkDimensionCompatibility

      protected void checkDimensionCompatibility(BitMatrix other)
      Sanity check for operations requiring matrices with the same number of columns and rows.

    • clear

      public void clear()
      Clears all bits of the receiver.

    • clone

      public Object clone()
      Cloning this BitMatrix produces a new BitMatrix that is equal to it. The clone of the bit matrix is another bit matrix that has exactly the same bits set to true as this bit matrix and the same number of columns and rows.
      Overrides:
      clone in class PersistentObject
      Returns:
      a clone of this bit matrix.

    • columns

      public int columns()
      Returns the number of columns of the receiver.

    • containsBox

      protected void containsBox(int column, int row, int width, int height)
      Checks whether the receiver contains the given box.

    • copy

      public BitMatrix copy()
      Returns a shallow clone of the receiver; calls clone() and casts the result.
      Returns:
      a shallow clone of the receiver.

    • elements

      protected long[] elements()

    • elements

      protected void elements(long[] bits, int columns, int rows)
      You normally need not use this method. Use this method only if performance is critical. Sets the bit matrix's backing bits, columns and rows. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.
      Throws:
      IllegalArgumentException - if columns < 0 || rows < 0 || columns*rows > bits.length*64

    • equals

      public boolean equals(Object obj)
      Compares this object against the specified object. The result is true if and only if the argument is not null and is a BitMatrix object that has the same number of columns and rows as the receiver and that has exactly the same bits set to true as the receiver.
      Overrides:
      equals in class Object
      Parameters:
      obj - the object to compare with.
      Returns:
      true if the objects are the same; false otherwise.

    • forEachCoordinateInState

      public boolean forEachCoordinateInState(boolean state, IntIntProcedure procedure)
      Applies a procedure to each coordinate that holds a bit in the given state. Iterates rowwise downwards from [columns()-1,rows()-1] to [0,0]. Useful, for example, if you want to copy bits into an image or somewhere else. Optimized for speed. Particularly quick if one of the following conditions holds
      • state==true and the receiver is sparse (cardinality() is small compared to size()).
      • state==false and the receiver is dense (cardinality() is large compared to size()).
      Parameters:
      state - element to search for.
      procedure - a procedure object taking as first argument the current column and as second argument the current row. Stops iteration if the procedure returns false, otherwise continues.
      Returns:
      false if the procedure stopped before all elements where iterated over, true otherwise.

    • get

      public boolean get(int column, int row)
      Returns from the receiver the value of the bit at the specified coordinate. The value is true if this bit is currently set; otherwise, returns false.
      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      Returns:
      the value of the bit at the specified coordinate.
      Throws:
      IndexOutOfBoundsException - if column<0 || column>=columns() || row<0 || row>=rows()

    • getQuick

      public boolean getQuick(int column, int row)
      Returns from the receiver the value of the bit at the specified coordinate; WARNING: Does not check preconditions. The value is true if this bit is currently set; otherwise, returns false.

      Provided with invalid parameters this method may return invalid values without throwing any exception. You should only use this method when you are absolutely sure that the coordinate is within bounds. Precondition (unchecked): column>=0 invalid input: '&'invalid input: '&' column<columns() invalid input: '&'invalid input: '&' row>=0 invalid input: '&'invalid input: '&' row<rows().

      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      Returns:
      the value of the bit at the specified coordinate.

    • hashCode

      public int hashCode()
      Returns a hash code value for the receiver.
      Overrides:
      hashCode in class Object

    • not

      public void not()
      Performs a logical NOT on the bits of the receiver.

    • or

      public void or(BitMatrix other)
      Performs a logical OR of the receiver with another bit matrix. The receiver 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 other bit matrix argument has the value true.
      Parameters:
      other - a bit matrix.
      Throws:
      IllegalArgumentException - if columns() != other.columns() || rows() != other.rows().

    • part

      public BitMatrix part(int column, int row, int width, int height)
      Constructs and returns a new matrix with width columns and height rows which is a copy of the contents of the given box. The box ranges from [column,row] to [column+width-1,row+height-1], all inclusive.
      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      width - the width of the box.
      height - the height of the box.
      Throws:
      IndexOutOfBoundsException - if column<0 || column+width>columns() || row<0 || row+height>rows()

    • put

      public void put(int column, int row, boolean value)
      Sets the bit at the specified coordinate to the state specified by value.
      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      value - the value of the bit to be copied into the specified coordinate.
      Throws:
      IndexOutOfBoundsException - if column<0 || column>=columns() || row<0 || row>=rows()

    • putQuick

      public void putQuick(int column, int row, boolean value)
      Sets the bit at the specified coordinate to the state specified by value; WARNING: Does not check preconditions.

      Provided with invalid parameters this method may return invalid values without throwing any exception. You should only use this method when you are absolutely sure that the coordinate is within bounds. Precondition (unchecked): column>=0 invalid input: '&'invalid input: '&' column<columns() invalid input: '&'invalid input: '&' row>=0 invalid input: '&'invalid input: '&' row<rows().

      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      value - the value of the bit to be copied into the specified coordinate.

    • replaceBoxWith

      public void replaceBoxWith(int column, int row, int width, int height, BitMatrix source, int sourceColumn, int sourceRow)
      Replaces a box of the receiver with the contents of another matrix's box. The source box ranges from [sourceColumn,sourceRow] to [sourceColumn+width-1,sourceRow+height-1], all inclusive. The destination box ranges from [column,row] to [column+width-1,row+height-1], all inclusive. Does nothing if width <= 0 || height <= 0. If source==this and the source and destination box intersect in an ambiguous way, then replaces as if using an intermediate auxiliary copy of the receiver.
      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      width - the width of the box.
      height - the height of the box.
      source - the source matrix to copy from(may be identical to the receiver).
      sourceColumn - the index of the source column-coordinate.
      sourceRow - the index of the source row-coordinate.
      Throws:
      IndexOutOfBoundsException - if column<0 || column+width>columns() || row<0 || row+height>rows()
      IndexOutOfBoundsException - if sourceColumn<0 || sourceColumn+width>source.columns() || sourceRow<0 || sourceRow+height>source.rows()

    • replaceBoxWith

      public void replaceBoxWith(int column, int row, int width, int height, boolean value)
      Sets the bits in the given box to the state specified by value. The box ranges from [column,row] to [column+width-1,row+height-1], all inclusive. (Does nothing if width <= 0 || height <= 0).
      Parameters:
      column - the index of the column-coordinate.
      row - the index of the row-coordinate.
      width - the width of the box.
      height - the height of the box.
      value - the value of the bit to be copied into the bits of the specified box.
      Throws:
      IndexOutOfBoundsException - if column<0 || column+width>columns() || row<0 || row+height>rows()

    • rows

      public int rows()
      Returns the number of rows of the receiver.

    • size

      public int size()
      Returns the size of the receiver which is columns()*rows().

    • toBitVector

      public BitVector toBitVector()
      Converts the receiver to a bitvector. In many cases this method only makes sense on one-dimensional matrices. WARNING: The returned bitvector and the receiver share the same backing bits. Modifying either of them will affect the other. If this behaviour is not what you want, you should first use copy() to make sure both objects use separate internal storage.

    • toString

      public String toString()
      Returns a (very crude) string representation of the receiver.
      Overrides:
      toString in class Object

    • xor

      public void xor(BitMatrix other)
      Performs a logical XOR of the receiver with another bit matrix. The receiver 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:
      other - a bit matrix.
      Throws:
      IllegalArgumentException - if columns() != other.columns() || rows() != other.rows().