1 /*
2
3 dsh-matrix long-addressable bit and typed object matrix implementations.
4 Copyright (c) 2004-2013 held jointly by the individual authors.
5
6 This library is free software; you can redistribute it and/or modify it
7 under the terms of the GNU Lesser General Public License as published
8 by the Free Software Foundation; either version 3 of the License, or (at
9 your option) any later version.
10
11 This library is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; with out even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
14 License for more details.
15
16 You should have received a copy of the GNU Lesser General Public License
17 along with this library; if not, write to the Free Software Foundation,
18 Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
19
20 > http://www.fsf.org/licensing/licenses/lgpl.html
21 > http://www.opensource.org/licenses/lgpl-license.php
22
23 */
24 package org.dishevelled.matrix;
25
26 import org.dishevelled.bitset.MutableBitSet;
27
28 import org.dishevelled.functor.BinaryProcedure;
29
30 /**
31 * Fixed size bit matrix in two dimensions, indexed by <code>long</code>s.
32 *
33 * @author Michael Heuer
34 */
35 public final class BitMatrix2D
36 {
37 /** Bit set. */
38 private final MutableBitSet bitset;
39
40 /** Number of rows. */
41 private final long rows;
42
43 /** Number of columns. */
44 private final long columns;
45
46 /** Size. */
47 private final long size;
48
49
50 /**
51 * Create a new 2D bit matrix with the specified number of rows and columns.
52 *
53 * @param rows number of rows, must be <code>>= 0</code>
54 * @param columns number of columns, must be <code>>= 0</code>
55 * @throws IllegalArgumentException if either <code>rows</code> or
56 * <code>columns</code> is negative
57 */
58 public BitMatrix2D(final long rows, final long columns)
59 {
60 if (rows < 0)
61 {
62 throw new IllegalArgumentException("rows must be >= 0");
63 }
64 if (columns < 0)
65 {
66 throw new IllegalArgumentException("columns must be >= 0");
67 }
68 this.rows = rows;
69 this.columns = columns;
70 this.size = (rows * columns);
71 this.bitset = new MutableBitSet(this.size);
72 }
73
74
75 /**
76 * Return the size of this 2D bit matrix.
77 *
78 * @return the size of this 2D bit matrix
79 */
80 public long size()
81 {
82 return size;
83 }
84
85 /**
86 * Return the number of rows in this 2D bit matrix.
87 *
88 * @return the number of rows in this 2D bit matrix
89 */
90 public long rows()
91 {
92 return rows;
93 }
94
95 /**
96 * Return the number of columns in this 2D bit matrix.
97 *
98 * @return the number of columns in this 2D bit matrix
99 */
100 public long columns()
101 {
102 return columns;
103 }
104
105 /**
106 * Return the cardinality of this 2D bit matrix, the
107 * number of bits set to true.
108 *
109 * @return the cardinality of this 2D bit matrix
110 */
111 public long cardinality()
112 {
113 return bitset.cardinality();
114 }
115
116 /**
117 * Return true if the cardinality of this 2D bit matrix is zero.
118 *
119 * @return true if the cardinality of this 2D bit matrix is zero
120 */
121 public boolean isEmpty()
122 {
123 return (0 == cardinality());
124 }
125
126 /**
127 * Clear all the values in this 2D bit matrix.
128 */
129 public void clear()
130 {
131 for (long i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i + 1))
132 {
133 bitset.clear(i);
134 }
135 }
136
137 /**
138 * Return the bit value at the specified row and column.
139 *
140 * @param row row index, must be <code>>= 0</code> and <code>< rows()</code>
141 * @param column column index, must be <code>>= 0</code> and <code>< columns()</code>
142 * @return the bit value at the specified row and column
143 * @throws IndexOutOfBoundsException if <code>row</code> or <code>column</code>
144 * is negative or if <code>row</code> or <code>column</code> is greater than
145 * or equal to <code>rows()</code> or <code>columns()</code>, respectively
146 */
147 public boolean get(final long row, final long column)
148 {
149 if (row < 0)
150 {
151 throw new IndexOutOfBoundsException(row + " < 0");
152 }
153 if (row >= rows)
154 {
155 throw new IndexOutOfBoundsException(row + " >= " + rows);
156 }
157 if (column < 0)
158 {
159 throw new IndexOutOfBoundsException(column + " < 0");
160 }
161 if (column >= columns)
162 {
163 throw new IndexOutOfBoundsException(column + " >= " + columns);
164 }
165 return getQuick(row, column);
166 }
167
168 /**
169 * Return the bit value at the specified row and column without checking bounds.
170 *
171 * @param row row index
172 * @param column column index
173 * @return the bit value at the specified row and column
174 */
175 public boolean getQuick(final long row, final long column)
176 {
177 return bitset.getQuick(index(row, column));
178 }
179
180 /**
181 * Set the bit value at the specified row and column to <code>value</code>.
182 *
183 * @param row row index, must be <code>>= 0</code> and <code>< rows()</code>
184 * @param column column index, must be <code>>= 0</code> and <code>< columns()</code>
185 * @param value value
186 * @throws IndexOutOfBoundsException if <code>row</code> or <code>column</code>
187 * is negative or if <code>row</code> or <code>column</code> is greater than
188 * or equal to <code>rows()</code> or <code>columns()</code>, respectively
189 */
190 public void set(final long row, final long column, final boolean value)
191 {
192 if (row < 0)
193 {
194 throw new IndexOutOfBoundsException(row + " < 0");
195 }
196 if (row >= rows)
197 {
198 throw new IndexOutOfBoundsException(row + " >= " + rows);
199 }
200 if (column < 0)
201 {
202 throw new IndexOutOfBoundsException(column + " < 0");
203 }
204 if (column >= columns)
205 {
206 throw new IndexOutOfBoundsException(column + " >= " + columns);
207 }
208 setQuick(row, column, value);
209 }
210
211 /**
212 * Set the bit value at the specified row and column to <code>value</code> without checking bounds.
213 *
214 * @param row row index
215 * @param column column index
216 * @param value value
217 */
218 public void setQuick(final long row, final long column, final boolean value)
219 {
220 long index = index(row, column);
221 if (value)
222 {
223 bitset.setQuick(index);
224 }
225 else
226 {
227 bitset.clearQuick(index);
228 }
229 }
230
231 /**
232 * Set all of the bit values from (<code>row0, column0</code>), inclusive,
233 * to (<code>row1, column1</code>), exclusive, to the specified value.
234 *
235 * @param row0 first row, must be <code>>= 0</code> and <code>< rows()</code>
236 * @param column0 first column, must be <code>>= 0</code> and <code>< columns()</code>
237 * @param row1 second row, must be <code>>= 0</code>, <code><= rows()</code>
238 * and <code>>= row0</code>
239 * @param column1 second column, must be <code>>= 0</code>, <code><= columns()</code>
240 * and <code>>= column0</code>
241 * @param value value
242 * @throws IllegalArgumentException if either <code>row1</code> or <code>column1</code>
243 * are less than <code>row0</code> or <code>column0</code>, respectively
244 * @throws IndexOutOfBoundsException if any of <code>row0</code>, <code>column0</code>,
245 * <code>row1</code>, or <code>column1</code> are negative or if either <code>row0</code>
246 * or <code>column0</code> are greater than or equal to <code>rows()</code> or
247 * <code>columns()</code>, respectively, or if either <code>row1</code> or
248 * <code>column1</code> are strictly greater than <code>rows()</code> or <code>columns()</code>,
249 * respectively
250 */
251 public void set(final long row0, final long column0,
252 final long row1, final long column1, final boolean value)
253 {
254 if (row0 < 0)
255 {
256 throw new IndexOutOfBoundsException(row0 + " < 0");
257 }
258 if (row0 >= rows)
259 {
260 throw new IndexOutOfBoundsException(row0 + " >= " + rows);
261 }
262 if (column0 < 0)
263 {
264 throw new IndexOutOfBoundsException(column0 + " < 0");
265 }
266 if (column0 >= columns)
267 {
268 throw new IndexOutOfBoundsException(column0 + " >= " + columns);
269 }
270 if (row1 < 0)
271 {
272 throw new IndexOutOfBoundsException(row1 + " < 0");
273 }
274 if (row1 > rows)
275 {
276 throw new IndexOutOfBoundsException(row1 + " > " + rows);
277 }
278 if (column1 < 0)
279 {
280 throw new IndexOutOfBoundsException(column1 + " < 0");
281 }
282 if (column1 > columns)
283 {
284 throw new IndexOutOfBoundsException(column1 + " > " + columns);
285 }
286
287 for (long row = row0; row < row1; row++)
288 {
289 for (long column = column0; column < column1; column++)
290 {
291 setQuick(row, column, value);
292 }
293 }
294 }
295
296 /**
297 * Set the bit value at the specified row and column to the complement
298 * of its current bit value.
299 *
300 * @param row row index, must be <code>>= 0</code> and <code>< rows()</code>
301 * @param column column index, must be <code>>= 0</code> and <code>< columns()</code>
302 * @throws IndexOutOfBoundsException if <code>row</code> or <code>column</code>
303 * is negative or if <code>row</code> or <code>column</code> is greater than
304 * or equal to <code>rows()</code> or <code>columns()</code>, respectively
305 */
306 public void flip(final long row, final long column)
307 {
308 if (row < 0)
309 {
310 throw new IndexOutOfBoundsException(row + " < 0");
311 }
312 if (row >= rows)
313 {
314 throw new IndexOutOfBoundsException(row + " >= " + rows);
315 }
316 if (column < 0)
317 {
318 throw new IndexOutOfBoundsException(column + " < 0");
319 }
320 if (column >= columns)
321 {
322 throw new IndexOutOfBoundsException(column + " >= " + columns);
323 }
324 flipQuick(row, column);
325 }
326
327 /**
328 * Set the bit value at the specified row and column to the complement
329 * of its current bit value without checking bounds.
330 *
331 * @param row row index
332 * @param column column index
333 */
334 public void flipQuick(final long row, final long column)
335 {
336 bitset.flipQuick(index(row, column));
337 }
338
339 /**
340 * Set all of the bit values from (<code>row0, column0</code>), inclusive,
341 * to (<code>row1, column1</code>), exclusive, to the complement of their
342 * current bit values.
343 *
344 * @param row0 first row, must be <code>>= 0</code> and <code>< rows()</code>
345 * @param column0 first column, must be <code>>= 0</code> and <code>< columns()</code>
346 * @param row1 second row, must be <code>>= 0</code>, <code><= rows()</code>
347 * and <code>>= row0</code>
348 * @param column1 second column, must be <code>>= 0</code>, <code><= columns()</code>
349 * and <code>>= column0</code>
350 * @throws IllegalArgumentException if either <code>row1</code> or <code>column1</code>
351 * are less than <code>row0</code> or <code>column0</code>, respectively
352 * @throws IndexOutOfBoundsException if any of <code>row0</code>, <code>column0</code>,
353 * <code>row1</code>, or <code>column1</code> are negative or if either <code>row0</code>
354 * or <code>column0</code> are greater than or equal to <code>rows()</code> or
355 * <code>columns()</code>, respectively, or if either <code>row1</code> or
356 * <code>column1</code> are strictly greater than <code>rows()</code> or <code>columns()</code>,
357 * respectively
358 */
359 public void flip(final long row0, final long column0,
360 final long row1, final long column1)
361 {
362 if (row0 < 0)
363 {
364 throw new IndexOutOfBoundsException(row0 + " < 0");
365 }
366 if (row0 >= rows)
367 {
368 throw new IndexOutOfBoundsException(row0 + " >= " + rows);
369 }
370 if (column0 < 0)
371 {
372 throw new IndexOutOfBoundsException(column0 + " < 0");
373 }
374 if (column0 >= columns)
375 {
376 throw new IndexOutOfBoundsException(column0 + " >= " + columns);
377 }
378 if (row1 < 0)
379 {
380 throw new IndexOutOfBoundsException(row1 + " < 0");
381 }
382 if (row1 > rows)
383 {
384 throw new IndexOutOfBoundsException(row1 + " > " + rows);
385 }
386 if (column1 < 0)
387 {
388 throw new IndexOutOfBoundsException(column1 + " < 0");
389 }
390 if (column1 > columns)
391 {
392 throw new IndexOutOfBoundsException(column1 + " > " + columns);
393 }
394
395 for (long row = row0; row < row1; row++)
396 {
397 for (long column = column0; column < column1; column++)
398 {
399 flipQuick(row, column);
400 }
401 }
402 }
403
404 /**
405 * Assign all values in this 2D bit matrix to <code>value</code>.
406 *
407 * @param value value
408 * @return this 2D bit matrix, for convenience
409 */
410 public BitMatrix2D assign(final boolean value)
411 {
412 if (size > 0)
413 {
414 set(0, 0, rows, columns, value);
415 }
416 return this;
417 }
418
419 /**
420 * Return true if the specified 2D bit matrix has any bits set
421 * to true that are also set to true in this 2D bit matrix.
422 *
423 * @param other other 2D bit matrix, must not be null and must
424 * have the same dimensions as this 2D bit matrix
425 * @return true if the specified 2D bit matrix has any bits set
426 * to true that are also set to true in this 2D bit matrix
427 */
428 public boolean intersects(final BitMatrix2D other)
429 {
430 if (other == null)
431 {
432 throw new IllegalArgumentException("other must not be null");
433 }
434 if ((size != other.size()) || (rows != other.rows()) || (columns != other.columns()))
435 {
436 throw new IllegalArgumentException("this and other must have the same dimensions");
437 }
438 return bitset.intersects(other.bitset);
439 }
440
441 /**
442 * Perform a logical <b>AND</b> of this 2D bit matrix
443 * and the specified 2D bit matrix.
444 *
445 * @param other other 2D bit matrix, must not be null and must
446 * have the same dimensions as this 2D bit matrix
447 * @return this 2D bit matrix, for convenience
448 */
449 public BitMatrix2D and(final BitMatrix2D other)
450 {
451 if (other == null)
452 {
453 throw new IllegalArgumentException("other must not be null");
454 }
455 if ((size != other.size()) || (rows != other.rows()) || (columns != other.columns()))
456 {
457 throw new IllegalArgumentException("this and other must have the same dimensions");
458 }
459 bitset.and(other.bitset);
460 return this;
461 }
462
463 /**
464 * Clear all the bits in this 2D bit matrix whose corresponding
465 * bit is set in the specified 2D bit matrix.
466 *
467 * @param other other 2D bit matrix, must not be null and must
468 * have the same dimensions as this 2D bit matrix
469 * @return this 2D bit matrix, for convenience
470 */
471 public BitMatrix2D andNot(final BitMatrix2D other)
472 {
473 if (other == null)
474 {
475 throw new IllegalArgumentException("other must not be null");
476 }
477 if ((size != other.size()) || (rows != other.rows()) || (columns != other.columns()))
478 {
479 throw new IllegalArgumentException("this and other must have the same dimensions");
480 }
481 bitset.andNot(other.bitset);
482 return this;
483 }
484
485 /**
486 * Perform a logical <b>OR</b> of this 2D bit matrix
487 * and the specified 2D bit matrix.
488 *
489 * @param other other 2D bit matrix, must not be null and must
490 * have the same dimensions as this 2D bit matrix
491 * @return this 2D bit matrix, for convenience
492 */
493 public BitMatrix2D or(final BitMatrix2D other)
494 {
495 if (other == null)
496 {
497 throw new IllegalArgumentException("other must not be null");
498 }
499 if ((size != other.size()) || (rows != other.rows()) || (columns != other.columns()))
500 {
501 throw new IllegalArgumentException("this and other must have the same dimensions");
502 }
503 bitset.or(other.bitset);
504 return this;
505 }
506
507 /**
508 * Perform a logical <b>XOR</b> of this 2D bit matrix
509 * and the specified 2D bit matrix.
510 *
511 * @param other other 2D bit matrix, must not be null and must
512 * have the same dimensions as this 2D bit matrix
513 * @return this 2D bit matrix, for convenience
514 */
515 public BitMatrix2D xor(final BitMatrix2D other)
516 {
517 if (other == null)
518 {
519 throw new IllegalArgumentException("other must not be null");
520 }
521 if ((size != other.size()) || (rows != other.rows()) || (columns != other.columns()))
522 {
523 throw new IllegalArgumentException("this and other must have the same dimensions");
524 }
525 bitset.xor(other.bitset);
526 return this;
527 }
528
529 /**
530 * Apply the specified procedure to each row and column
531 * in this 2D bit matrix with a bit equal to the specified value.
532 *
533 * @param value value
534 * @param procedure procedure, must not be null
535 */
536 public void forEach(final boolean value, final BinaryProcedure<Long, Long> procedure)
537 {
538 if (procedure == null)
539 {
540 throw new IllegalArgumentException("procedure must not be null");
541 }
542
543 for (long row = 0; row < rows; row++)
544 {
545 for (long column = 0; column < columns; column++)
546 {
547 if (getQuick(row, column) == value)
548 {
549 procedure.run(Long.valueOf(row), Long.valueOf(column));
550 }
551 }
552 }
553 }
554
555 /** {@inheritDoc} */
556 public boolean equals(final Object o)
557 {
558 if (o == null)
559 {
560 return false;
561 }
562 if (!(o instanceof BitMatrix2D))
563 {
564 return false;
565 }
566
567 BitMatrix2D bm = (BitMatrix2D) o;
568
569 if ((size != bm.size()) || (rows != bm.rows()) || (columns != bm.columns()))
570 {
571 return false;
572 }
573 return bitset.equals(bm.bitset);
574 }
575
576 /** {@inheritDoc} */
577 public int hashCode()
578 {
579 int hashCode = 37;
580 hashCode = 17 * hashCode + (int) (size ^ (size >>> 32));
581 hashCode = 17 * hashCode + (int) (rows ^ (rows >>> 32));
582 hashCode = 17 * hashCode + (int) (columns ^ (columns >>> 32));
583 hashCode = 17 * hashCode + bitset.hashCode();
584 return hashCode;
585 }
586
587 /**
588 * Return the index for the specified row and column.
589 *
590 * @param row row index
591 * @param column column index
592 * @return the index for the specified row and column
593 */
594 private long index(final long row, final long column)
595 {
596 return (columns * row) + column;
597 }
598 }