Source code: mlsub/typing/lowlevel/BitMatrix.java
1 package mlsub.typing.lowlevel;
2
3 import java.util.ArrayList;
4
5 /**
6 A square matrix of bits, used to represent a relation between integers.
7
8 @version $Revision: 1.8 $, $Date: 2003/04/06 19:00:17 $
9 @author Alexandre Frey
10 @author Daniel Bonniot (Optimization for sparse and reflexives matrices)
11 **/
12 final public class BitMatrix implements Cloneable {
13 /**
14 * a vector of BitVectors. rows.get(i) is the ith line of
15 * the matrix.
16 **/
17 private BitVector[] rows;
18 private int size;
19
20 // A BitVector instance can be saved if the only bit set is the one
21 // on the diagonal, which is usual here.
22 private boolean reflexive;
23
24 /**
25 * Constructs an empty matrix
26 **/
27 public BitMatrix() {
28 this(10);
29 }
30 private BitMatrix(int rowCapacity) {
31 if(rowCapacity==0)
32 rowCapacity=5;
33 rows = new BitVector[rowCapacity];
34 }
35
36 /**
37 * Returns the number of rows and columns of this matrix
38 **/
39 public int size() {
40 return size;
41 }
42
43 /**
44 * Set the size of the matrix. If the new size is greater than the current
45 * size, new empty rows and columns are added. If the new size is less than
46 * the current size, all rows and columns at index greater than newSize are
47 * discarded.
48 **/
49 public void setSize(int newSize) {
50 if (newSize < size) {
51 // clear the columns beyond newSize, so that subsequent calls to extend()
52 // or setSize will find them empty.
53 for (int i = 0; i < newSize; i++) {
54 BitVector row = rows[i];
55 if (row != null) {
56 row.truncate(newSize);
57 }
58 }
59 for (int i = size; i>newSize; )
60 rows[--i] = null;
61 }
62 else {
63 if(rows.length<newSize)
64 {
65 BitVector[] newRows = new BitVector[rows.length*2];
66 System.arraycopy(rows, 0, newRows, 0, rows.length);
67 rows = newRows;
68 }
69 }
70 size = newSize;
71 }
72
73 /**
74 * Grow the matrix by one column and one row, initially empty. Returns the
75 * index of the new row.
76 **/
77 public int extend() {
78 setSize(size+1);
79 return size-1;
80 }
81
82 /**
83 To be able to return a correct row for reflexive matrices
84 without allocating a new one, we share the short ones
85 with only one bit set.
86 */
87 private static BitVector[] reflexiveRow = new BitVector[256];
88
89 /**
90 * Get ith row. May return null if it is empty or if row is beyond size()
91 *
92 * <p>If the matrix is reflexive, the row MUST NOT be modified by the caller.
93 **/
94 final BitVector getRow(int i) {
95 if (i < size) {
96 if (reflexive && rows[i] == null)
97 {
98 if (i >= reflexiveRow.length || reflexiveRow[i] == null)
99 {
100 BitVector res = new BitVector(i+1);
101 res.set(i);
102 if (i < reflexiveRow.length)
103 reflexiveRow[i] = res;
104 return res;
105 }
106
107 return reflexiveRow[i];
108 }
109 else
110 {
111 if (reflexive)
112 rows[i].set(i);
113 return rows[i];
114 }
115 } else {
116 return null;
117 }
118 }
119
120 /**
121 * get element at position (i, j), i.e., returns the value of i < j.
122 * Assume i and j are valid indexes
123 **/
124 final public boolean get(int i, int j) {
125 if (i == j && reflexive)
126 return true;
127
128 BitVector row = rows[i];
129 return row != null && row.get(j);
130 }
131
132 /**
133 * get index next set bit greater than j in row i.
134 * Assume i and j are valid indexes.
135 **/
136 final public int getNextSetInRow(int i, int j) {
137 BitVector row = rows[i];
138 if (reflexive) {
139 if (row == null) {
140 if (i > j) return i;
141 return BitVector.UNDEFINED_INDEX;
142 }
143 int k = row.getNextBit(j);
144 if ( (i > j) && ((k < 0) || (k > i)) )
145 return i;
146 return k;
147 }
148 if (row == null) return BitVector.UNDEFINED_INDEX;
149 return row.getNextBit(j);
150 }
151
152
153
154 /**
155 * Set element at position (i, j) to true. Assume i and j are valid indexes.
156 **/
157 public void set(int i, int j) {
158 if (i == j && reflexive)
159 return;
160
161 BitVector row = rows[i];
162 if (row == null) {
163 row = new BitVector(size);
164 rows[i] = row;
165 }
166 row.set(j);
167 }
168
169 /**
170 * Set element at position (i, j) to false. Assume i and j are valid indexes.
171 **/
172 public void clear(int i, int j) {
173 if (i == j && reflexive)
174 {
175 // Outch! We have to get back to a non-reflexive representation
176 reflexive = false;
177 for (int k = 0; k<size; k++)
178 if (k != i)
179 set(k, k);
180 }
181
182 BitVector row = rows[i];
183 if (row != null) {
184 row.clear(j);
185 }
186 }
187
188 /**
189 * Performs in-place reflexive transitive closure of the relation.
190 **/
191 public void closure() {
192 if (S.debug) {
193 BitMatrix testcopy = (BitMatrix)this.clone();
194 BitMatrix original = (BitMatrix)this.clone();
195 this.closure2();
196 testcopy.closure1();
197 boolean equal = true;
198 for(int i = 0; i<size; i++)
199 if (! ( (this.getRow(i)==testcopy.getRow(i)) ||
200 (this.getRow(i).equals( testcopy.getRow(i)))))
201 equal = false;
202 if (!equal) {
203 Debug.println("Warning new closure method produced incorrect results.");
204 Debug.println("orginal matrix:");
205 Debug.println(original.toString());
206 Debug.println("closure using new method:");
207 Debug.println(this.toString());
208 Debug.println("closure using standard method:");
209 Debug.println(testcopy.toString());
210 }
211
212 } else if (size < 16)
213 closure1();
214 else
215 closure2();
216 }
217
218 private void closure1() {
219 // Warshall algorithm
220 int size = this.size;
221 for (int k = 0; k < size; k++) {
222 BitVector row_k = rows[k];
223 if (row_k != null) {
224 for (int i = 0; i < size; i++) {
225 BitVector row_i = rows[i];
226 if (row_i != null && row_i.get(k)) { // i < k
227 /* for all j such that k < j, add i < j */
228 row_i.or(row_k);
229 }
230 }
231 }
232 }
233 //for (int i = 0; i < size; i++) set(i, i);
234 reflexive = true;
235 }
236
237 /**
238 This algorithm is O(n*m) (m = average number bits set per row) when there
239 are no cylcic relations in the a matrix, while closure1 is O(n2).
240 This algorithm has a much larger overhead so for small matrices
241 the old one still faster.
242 */
243 private void closure2() {
244 int size = this.size;
245 boolean[] done = new boolean[size];
246 boolean[] busy = new boolean[size];
247 int[] index = new int[size];
248 int[] bitpos = new int[size];
249 int ndone = 0;
250 while (ndone < size) {
251 if ((rows[ndone] != null) && !done[ndone]) {
252 int stackpos = 0;
253 index[0] = ndone;
254 bitpos[0] = 0;
255 busy[ndone] = true;
256 BitVector current = rows[ndone];
257 while (stackpos >= 0) {
258 if (bitpos[stackpos] < 0) {
259 if (stackpos > 0){
260 rows[index[stackpos-1]].or(rows[index[stackpos]]);
261 current = rows[index[stackpos-1]];
262 }
263 done[index[stackpos]] = true;
264 busy[index[stackpos--]] = false;
265 } else {
266 int nextbitpos = current.getLowestSetBit(bitpos[stackpos]);
267 if (nextbitpos < 0 || nextbitpos >= size) bitpos[stackpos] = -1;
268 else{
269 bitpos[stackpos] = nextbitpos+1;
270 if (rows[nextbitpos] != null) {
271 if (done[nextbitpos]) {
272 rows[index[stackpos]].or(rows[nextbitpos]);
273 } else {
274 if (!busy[nextbitpos]) {
275 busy[nextbitpos] = true;
276 index[++stackpos] = nextbitpos;
277 bitpos[stackpos] = 0;
278 current = rows[index[stackpos]];
279 } else {
280 if (index[stackpos] != nextbitpos) {
281 int tempsp = stackpos-1;
282 BitVector cyclicmask = new BitVector(size);
283 do {
284 bitpos[tempsp] = -1;
285 rows[index[stackpos]].or(rows[index[tempsp]]);
286 cyclicmask.set(index[tempsp]);
287 } while (index[tempsp--] != nextbitpos);
288 current = (BitVector)current.clone();
289 current.andNot(cyclicmask);
290 bitpos[stackpos] = 0;
291 }
292 }
293 }
294 }
295 }
296 }
297 }
298 }
299 ndone++;
300 }
301 reflexive = true;
302 }
303
304 /**
305 * Returns a newly-allocated BitMatrix initialized with the transpose
306 * of this BitMatrix
307 **/
308 public BitMatrix transpose() {
309 BitMatrix m = new BitMatrix(size);
310 m.setSize(size);
311 for (int i = 0; i < size; i++) {
312 BitVector row = rows[i];
313 if (row != null) {
314 for (int j = row.getLowestSetBit();
315 j>=0;
316 j = row.getLowestSetBit(j+1))
317 m.set(j, i);
318 }
319 }
320 m.reflexive = reflexive;
321 return m;
322 }
323
324 public Object clone() {
325 try {
326 BitMatrix m = (BitMatrix)super.clone();
327 BitVector[] v = (BitVector[])rows.clone();
328
329 for (int i = 0; i < size; i++) {
330 BitVector row = v[i];
331 if (row != null) {
332 if (!row.isEmpty())
333 v[i] = (BitVector) row.clone();
334 else
335 v[i] = null;
336 }
337 }
338 m.rows = v;
339 m.size = size;
340 m.reflexive = reflexive;
341 return m;
342 } catch (CloneNotSupportedException e) {
343 throw new InternalError
344 ("Should never happen, since BitMatrix implements Cloneable");
345 }
346 }
347
348
349 public String toString() {
350 StringBuffer sb = new StringBuffer("{");
351
352 boolean needSeparator = false;
353
354 for (int row = 0; row < size; row++)
355 for (int col = 0; col < size; col++)
356 if (get(row, col))
357 {
358 if (needSeparator) {
359 sb.append(", ");
360 } else {
361 needSeparator = true;
362 }
363 sb.append("(").append(row).append(",").append(col).append(")");
364 }
365 return sb.append("}").toString();
366 }
367
368 public boolean equals(Object obj) {
369 if (this == obj)
370 return true;
371
372 if (obj == null || !(obj instanceof BitMatrix))
373 return false;
374
375 BitMatrix that = (BitMatrix) obj;
376
377 for (int row = 0; row < size; row++)
378 for (int col = 0; col < size; col++)
379 if (get(row, col) != that.get(row, col))
380 return false;
381
382 return true;
383 }
384
385 /**
386 * Fills the array S with a topological sort of the relation on [m, size()[
387 * described by this matrix. Assume that S is large enough to hold size() -
388 * m integers. Assume 0 <= m <= this.size().
389 *
390 * <p>After a call to topologicalSort() and if the relation is a DAG, for
391 * all i, j such that this.get(i, j) is true, i appears before j in S
392 **/
393 public void topologicalSort(int m, int[] S) {
394 // The algorithm should be modified to handle reflexive case.
395 // Easy way out: insert the reflexive points.
396 // However I'm not sure this case ever happens anyway:
397 // topologicalSort is only used in Satisfier on C which is not reflexive
398
399 int n = size;
400 int[] sortStack = new int[n - m];
401 int sp = -1; // index in sortStack
402 int s = n - m; // index in S
403 BitVector touched = new BitVector(n);
404 touched.fill(m);
405 for (int i = m; i < n; i++) {
406 if (!touched.get(i)) {
407 touched.set(i);
408 sortStack[++sp] = i;
409 loop: while(sp >= 0) {
410 int j = sortStack[sp];
411 BitVector row_j = getRow(j);
412 if (row_j != null) {
413 int succ = row_j.getLowestSetBitNotIn(touched);
414 if (succ >= 0) {
415 // do the successor first
416 touched.set(succ);
417 sortStack[++sp] = succ;
418 continue loop;
419 }
420 }
421 // no untouched successor found
422 sp--; // pop j
423 S[--s] = j; // push it on the sort array
424 }
425 }
426 }
427 }
428
429
430 /**
431 * Tests if this bit matrix is included in M on the first n columns and
432 * lines. Assume m <= this.size() and m <= M.size(). If there exists (i, j)
433 * < (m, m) such that this.get(i, j) but !M.get(i, j), return an array a
434 * such that a[0] = i and a[1] = j. Otherwise, return null.
435 **/
436 public int[] includedIn(int m, BitMatrix M) {
437 if (this == M) {
438 return null;
439 } else {
440 for (int i = 0; i < m; i++) {
441 BitVector row1 = this.getRow(i);
442 if (row1 != null) {
443 int j;
444 BitVector row2 = M.getRow(i);
445 if (row2 != null) {
446 j = row1.getLowestSetBitNotIn(row2);
447 } else {
448 j = row1.getLowestSetBit();
449 }
450 if (0 <= j && j < m) {
451 return new int[] {i, j};
452 }
453 }
454 }
455 return null;
456 }
457 }
458
459 /**
460 Move index src to dest.
461 */
462 public void indexMove(int src, int dest)
463 {
464 rowMove(src, dest);
465 colMove(src, dest);
466 }
467
468 /**
469 * In-place copy row src to row dest and clear row src. The previous results
470 * of getRow(src) must not be used after this call.
471 **/
472 private void rowMove(int src, int dest) {
473 rows[dest] = getRow(src);
474 rows[src] = null;
475 }
476
477 /**
478 * copy column src to column dest and clear column src.
479 * Assume src != dest
480 **/
481 private void colMove(int src, int dest) {
482 for (int i = 0; i < size; i++) {
483 BitVector row = getRow(i);
484 if (row != null) {
485 row.bitCopy(src, dest);
486 }
487 }
488 }
489
490 /**
491 Merge indexes src and dest, put the result in dest.
492 */
493 public void indexMerge(int src, int dest)
494 {
495 rowMerge(src, dest);
496 colMerge(src, dest);
497 }
498
499 /**
500 * Merge row src and row dest, put the result in row dest.
501 * Assume src != dest. Previous results of getRow(src) must not be used
502 * after this call.
503 **/
504 private void rowMerge(int src, int dest) {
505 BitVector srcRow = getRow(src);
506 if (srcRow != null) {
507 BitVector destRow = getRow(dest);
508 if (destRow == null) {
509 rows[dest] = srcRow;
510 } else {
511 destRow.or(srcRow);
512 }
513 }
514 rows[src] = null;
515 }
516
517 /**
518 * Merge column src and column dest, put the result in column dest. Assume
519 * src != dest.
520 **/
521 private void colMerge(int src, int dest) {
522 for (int i = 0; i < size; i++) {
523 BitVector row = getRow(i);
524 if (row != null) {
525 row.bitMerge(src, dest);
526 }
527 }
528 }
529
530 /**
531 * Compute the set of y such that x <* y.
532 **/
533 public BitVector ideal(int x) {
534 BitVector ideal = new BitVector(size);
535 addIdeal(x, ideal);
536 return ideal;
537 }
538
539 // assume !ideal.get(x)
540 private void addIdeal(int x, BitVector ideal) {
541 ideal.set(x);
542 BitVector xUp = getRow(x);
543 if (xUp != null) {
544 int y;
545 while ((y = xUp.getLowestSetBitNotIn(ideal)) >= 0) {
546 addIdeal(y, ideal);
547 }
548 }
549 }
550 }