Overview  Package   Class  Use  Deprecated  Index
Home >> All >> mlsub >> typing >> [ lowlevel overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

mlsub.typing.lowlevel
Class BitMatrix  

java.lang.Object
  mlsub.typing.lowlevel.BitMatrix

All Implemented Interfaces:

java.lang.Cloneable

---

public final class BitMatrix

extends java.lang.Object

implements java.lang.Cloneable

A square matrix of bits, used to represent a relation between integers.

Version:

$Revision: 1.8 $, $Date: 2003/04/06 19:00:17 $

---

Field Summary
private  boolean	reflexive
private static BitVector[]	reflexiveRow           To be able to return a correct row for reflexive matrices without allocating a new one, we share the short ones with only one bit set.
private  BitVector[]	rows           a vector of BitVectors.
private  int	size

 

Constructor Summary
	BitMatrix()           Constructs an empty matrix
private	BitMatrix(int rowCapacity)

 

Method Summary
private  void	addIdeal(int x, BitVector ideal)
void	clear(int i, int j)           Set element at position (i, j) to false.
java.lang.Object	clone()           This method may be called to create a new copy of the Object.
void	closure()           Performs in-place reflexive transitive closure of the relation.
private  void	closure1()
private  void	closure2()           This algorithm is O(n*m) (m = average number bits set per row) when there are no cylcic relations in the a matrix, while closure1 is O(n2).
private  void	colMerge(int src, int dest)           Merge column src and column dest, put the result in column dest.
private  void	colMove(int src, int dest)           copy column src to column dest and clear column src.
boolean	equals(java.lang.Object obj)           Determine whether this Object is semantically equal to another Object.
int	extend()           Grow the matrix by one column and one row, initially empty.
boolean	get(int i, int j)           get element at position (i, j), i.e., returns the value of i < j.
int	getNextSetInRow(int i, int j)           get index next set bit greater than j in row i.
(package private)  BitVector	getRow(int i)           Get ith row.
BitVector	ideal(int x)           Compute the set of y such that x <* y.
int[]	includedIn(int m, BitMatrix M)           Tests if this bit matrix is included in M on the first n columns and lines.
void	indexMerge(int src, int dest)           Merge indexes src and dest, put the result in dest.
void	indexMove(int src, int dest)           Move index src to dest.
private  void	rowMerge(int src, int dest)           Merge row src and row dest, put the result in row dest.
private  void	rowMove(int src, int dest)           In-place copy row src to row dest and clear row src.
void	set(int i, int j)           Set element at position (i, j) to true.
void	setSize(int newSize)           Set the size of the matrix.
int	size()           Returns the number of rows and columns of this matrix
void	topologicalSort(int m, int[] S)           Fills the array S with a topological sort of the relation on [m, size()[ described by this matrix.
java.lang.String	toString()           Convert this Object to a human-readable String.
BitMatrix	transpose()           Returns a newly-allocated BitMatrix initialized with the transpose of this BitMatrix

 

Methods inherited from class java.lang.Object

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

 

Field Detail

rows

private BitVector[] rows

a vector of BitVectors. rows.get(i) is the ith line of the matrix.

---

size

private int size

---

reflexive

private boolean reflexive

---

reflexiveRow

private static BitVector[] reflexiveRow

To be able to return a correct row for reflexive matrices without allocating a new one, we share the short ones with only one bit set.

Constructor Detail

BitMatrix

public BitMatrix()

Constructs an empty matrix

---

BitMatrix

private BitMatrix(int rowCapacity)

Method Detail

size

public int size()

Returns the number of rows and columns of this matrix

---

setSize

public void setSize(int newSize)

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.

---

extend

public int extend()

Grow the matrix by one column and one row, initially empty. Returns the index of the new row.

---

getRow

final BitVector getRow(int i)

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.

---

get

public final boolean get(int i,
                         int j)

get element at position (i, j), i.e., returns the value of i < j. Assume i and j are valid indexes

---

getNextSetInRow

public final int getNextSetInRow(int i,
                                 int j)

get index next set bit greater than j in row i. Assume i and j are valid indexes.

---

set

public void set(int i,
                int j)

Set element at position (i, j) to true. Assume i and j are valid indexes.

---

clear

public void clear(int i,
                  int j)

Set element at position (i, j) to false. Assume i and j are valid indexes.

---

closure

public void closure()

Performs in-place reflexive transitive closure of the relation.

---

closure1

private void closure1()

---

closure2

private void closure2()

This algorithm is O(n*m) (m = average number bits set per row) when there are no cylcic relations in the a matrix, while closure1 is O(n2). This algorithm has a much larger overhead so for small matrices the old one still faster.

---

transpose

public BitMatrix transpose()

Returns a newly-allocated BitMatrix initialized with the transpose of this BitMatrix

---

clone

public java.lang.Object clone()

Description copied from class: java.lang.Object

This method may be called to create a new copy of the Object. The typical behavior is as follows:

• o == o.clone() is false
• o.getClass() == o.clone().getClass() is true
• o.equals(o) is true

However, these are not strict requirements, and may be violated if necessary. Of the three requirements, the last is the most commonly violated, particularly if the subclass does not override Object.equals(Object)>Object.equals(Object) 55 .

If the Object you call clone() on does not implement java.lang.Cloneable (which is a placeholder interface), then a CloneNotSupportedException is thrown. Notice that Object does not implement Cloneable; this method exists as a convenience for subclasses that do.

Object's implementation of clone allocates space for the new Object using the correct class, without calling any constructors, and then fills in all of the new field values with the old field values. Thus, it is a shallow copy. However, subclasses are permitted to make a deep copy.

All array types implement Cloneable, and override this method as follows (it should never fail):

 public Object clone()
 {
   try
     {
       super.clone();
     }
   catch (CloneNotSupportedException e)
     {
       throw new InternalError(e.getMessage());
     }
 }
 

---

toString

public java.lang.String toString()

Description copied from class: java.lang.Object

Convert this Object to a human-readable String. There are no limits placed on how long this String should be or what it should contain. We suggest you make it as intuitive as possible to be able to place it into System.out.println() 55 and such.

It is typical, but not required, to ensure that this method never completes abruptly with a java.lang.RuntimeException.

This method will be called when performing string concatenation with this object. If the result is null, string concatenation will instead use "null".

The default implementation returns getClass().getName() + "@" + Integer.toHexString(hashCode()).

---

equals

public boolean equals(java.lang.Object obj)

Description copied from class: java.lang.Object

Determine whether this Object is semantically equal to another Object.

There are some fairly strict requirements on this method which subclasses must follow:

• It must be transitive. If a.equals(b) and b.equals(c), then a.equals(c) must be true as well.
• It must be symmetric. a.equals(b) and b.equals(a) must have the same value.
• It must be reflexive. a.equals(a) must always be true.
• It must be consistent. Whichever value a.equals(b) returns on the first invocation must be the value returned on all later invocations.
• a.equals(null) must be false.
• It must be consistent with hashCode(). That is, a.equals(b) must imply a.hashCode() == b.hashCode(). The reverse is not true; two objects that are not equal may have the same hashcode, but that has the potential to harm hashing performance.

This is typically overridden to throw a java.lang.ClassCastException if the argument is not comparable to the class performing the comparison, but that is not a requirement. It is legal for a.equals(b) to be true even though a.getClass() != b.getClass(). Also, it is typical to never cause a java.lang.NullPointerException.

In general, the Collections API (java.util) use the equals method rather than the == operator to compare objects. However, java.util.IdentityHashMap is an exception to this rule, for its own good reasons.

The default implementation returns this == o.

---

topologicalSort

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. 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

---

includedIn

public int[] includedIn(int m,
                        BitMatrix M)

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.

---

indexMove

public void indexMove(int src,
                      int dest)

Move index src to dest.

---

rowMove

private void rowMove(int src,
                     int dest)

In-place copy row src to row dest and clear row src. The previous results of getRow(src) must not be used after this call.

---

colMove

private void colMove(int src,
                     int dest)

copy column src to column dest and clear column src. Assume src != dest

---

indexMerge

public void indexMerge(int src,
                       int dest)

Merge indexes src and dest, put the result in dest.

---

rowMerge

private void rowMerge(int src,
                      int dest)

Merge row src and row dest, put the result in row dest. Assume src != dest. Previous results of getRow(src) must not be used after this call.

---

colMerge

private void colMerge(int src,
                      int dest)

Merge column src and column dest, put the result in column dest. Assume src != dest.

---

ideal

public BitVector ideal(int x)

Compute the set of y such that x <* y.

---

addIdeal

private void addIdeal(int x,
                      BitVector ideal)

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> mlsub >> typing >> [ lowlevel overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---