| java.lang.Object
 mlsub.typing.lowlevel.BitMatrix
| BitMatrix | | final public class BitMatrix (Code) | | A square matrix of bits, used to represent a relation between integers.
version:
$Revision: 1.11 $, $Date: 2005/03/30 23:07:58 $
author:
Alexandre Frey
author:
Daniel Bonniot (Optimization for sparse and reflexives matrices) |
| Method Summary | |
| public void | clear(int i, int j)
Set element at position (i, j) to false. | | public void | closure()
Performs in-place reflexive transitive closure of the relation. | | public boolean | equals(Object obj)
| | public int | extend()
Grow the matrix by one column and one row, initially empty. | | final public boolean | get(int i, int j)
get element at position (i, j), i.e., returns the value of i < j. | | final public int | getNextSetInRow(int i, int j)
get index next set bit greater than j in row i. | | final BitVector | getRow(int i)
Get ith row. | | public BitVector | ideal(int x)
Compute the set of y such that x <* y. | | public int[] | includedIn(int m, BitMatrix M)
Tests if this bit matrix is included in M on the first n columns and
lines. | | public void | indexMerge(int src, int dest)
Merge indexes src and dest, put the result in dest. | | public void | indexMove(int src, int dest)
Move index src to dest. | | public void | set(int i, int j)
Set element at position (i, j) to true. | | public void | setSize(int newSize)
Set the size of the matrix. | | public int | size()
| | public String | toString()
| | public void | topologicalSort(int m, int[] S)
Fills the array S with a topological sort of the relation on [m, size()[
described by this matrix. | | public BitMatrix | transpose()
|
| BitMatrix | | public BitMatrix()(Code) | | Constructs an empty matrix
|
| clear | | public void clear(int i, int j)(Code) | | Set element at position (i, j) to false. Assume i and j are valid indexes.
|
| closure | | public void closure()(Code) | | Performs in-place reflexive transitive closure of the relation.
|
| extend | | public int extend()(Code) | | Grow the matrix by one column and one row, initially empty. Returns the
index of the new row.
|
| get | | final public boolean get(int i, int j)(Code) | | get element at position (i, j), i.e., returns the value of i < j.
Assume i and j are valid indexes
|
| getNextSetInRow | | final public int getNextSetInRow(int i, int j)(Code) | | get index next set bit greater than j in row i.
Assume i and j are valid indexes.
|
| getRow | | final BitVector getRow(int i)(Code) | | Get ith row. May return null if it is empty or if row is beyond size()
If the matrix is reflexive, the row MUST NOT be modified by the caller.
|
| ideal | | public BitVector ideal(int x)(Code) | | Compute the set of y such that x <* y.
|
| includedIn | | public int[] includedIn(int m, BitMatrix M)(Code) | | Tests if this bit matrix is included in M on the first n columns and
lines. Assume m <= this.size() and m <= M.size(). If there exists (i, j)
< (m, m) such that this.get(i, j) but !M.get(i, j), return an array a
such that a[0] = i and a[1] = j. Otherwise, return null.
|
| indexMerge | | public void indexMerge(int src, int dest)(Code) | | Merge indexes src and dest, put the result in dest.
|
| indexMove | | public void indexMove(int src, int dest)(Code) | | Move index src to dest.
|
| set | | public void set(int i, int j)(Code) | | Set element at position (i, j) to true. Assume i and j are valid indexes.
|
| setSize | | public void setSize(int newSize)(Code) | | Set the size of the matrix. If the new size is greater than the current
size, new empty rows and columns are added. If the new size is less than
the current size, all rows and columns at index greater than newSize are
discarded.
|
| size | | public int size()(Code) | | Returns the number of rows and columns of this matrix
|
| topologicalSort | | public void topologicalSort(int m, int[] S)(Code) | | Fills the array S with a topological sort of the relation on [m, size()[
described by this matrix. Assume that S is large enough to hold size() -
m integers. Assume 0 <= m <= this.size().
After a call to topologicalSort() and if the relation is a DAG, for
all i, j such that this.get(i, j) is true, i appears before j in S
|
| transpose | | public BitMatrix transpose()(Code) | | Returns a newly-allocated BitMatrix initialized with the transpose
of this BitMatrix
|
|
|