View Javadoc

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.TernaryProcedure;
29  
30  /**
31   * Fixed size bit matrix in three dimensions, indexed by <code>long</code>s.
32   *
33   * @author  Michael Heuer
34   */
35  public final class BitMatrix3D
36  {
37      /** Bit set. */
38      private final MutableBitSet bitset;
39  
40      /** Number of slices. */
41      private final long slices;
42  
43      /** Number of rows. */
44      private final long rows;
45  
46      /** Number of columns. */
47      private final long columns;
48  
49      /** Size. */
50      private final long size;
51  
52  
53      /**
54       * Create a new 3D bit matrix with the specified number of
55       * slices, rows, and columns.
56       *
57       * @param slices number of slices, must be <code>&gt;= 0</code>
58       * @param rows number of rows, must be <code>&gt;= 0</code>
59       * @param columns number of columns, must be <code>&gt;= 0</code>
60       * @throws IllegalArgumentException if any of <code>slices</code>,
61       *    <code>rows</code>, or <code>columns</code> is negative
62       */
63      public BitMatrix3D(final long slices, final long rows, final long columns)
64      {
65          if (slices < 0)
66          {
67              throw new IllegalArgumentException("slices must be >= 0");
68          }
69          if (rows < 0)
70          {
71              throw new IllegalArgumentException("rows must be >= 0");
72          }
73          if (columns < 0)
74          {
75              throw new IllegalArgumentException("columns must be >= 0");
76          }
77          this.slices = slices;
78          this.rows = rows;
79          this.columns = columns;
80          this.size = (slices * rows * columns);
81          this.bitset = new MutableBitSet(size);
82      }
83  
84  
85      /**
86       * Return the size of this 3D bit matrix.
87       *
88       * @return the size of this 3D bit matrix
89       */
90      public long size()
91      {
92          return size;
93      }
94  
95      /**
96       * Return the number of slices in this 3D bit matrix.
97       *
98       * @return the number of slices in this 3D bit matrix
99       */
100     public long slices()
101     {
102         return slices;
103     }
104 
105     /**
106      * Return the number of rows in this 3D bit matrix.
107      *
108      * @return the number of rows in this 3D bit matrix
109      */
110     public long rows()
111     {
112         return rows;
113     }
114 
115     /**
116      * Return the number of columns in this 3D bit matrix.
117      *
118      * @return the number of columns in this 3D bit matrix
119      */
120     public long columns()
121     {
122         return columns;
123     }
124 
125     /**
126      * Return the cardinality of this 3D bit matrix, the
127      * number of bits set to true.
128      *
129      * @return the cardinality of this 3D bit matrix
130      */
131     public long cardinality()
132     {
133         return bitset.cardinality();
134     }
135 
136     /**
137      * Return true if the cardinality of this 3D bit matrix is zero.
138      *
139      * @return true if the cardinality of this 3D bit matrix is zero
140      */
141     public boolean isEmpty()
142     {
143         return (0 == cardinality());
144     }
145 
146     /**
147      * Clear all the values in this 3D bit matrix.
148      */
149     public void clear()
150     {
151         for (long i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i + 1))
152         {
153             bitset.clear(i);
154         }
155     }
156 
157     /**
158      * Return the bit value at the specified slice, row, and column.
159      *
160      * @param slice slice index, must be <code>&gt; 0</code> and <code>&lt; slices()</code>
161      * @param row row index, must be <code>&gt; 0</code> and <code>&lt; rows()</code>
162      * @param column column index, must be <code>&gt; 0</code> and <code>&lt; columns()</code>
163      * @return the bit value at the specified slice, row, and column
164      * @throws IndexOutOfBoundsException if any of <code>slice</code>, <code>row</code>, or
165      *    <code>column</code> are negative or if any of <code>slice</code>, <code>row</code>,
166      *    or <code>column</code> are greater than or equal to <code>slices()</code>,
167      *    <code>rows()</code>, or <code>columns()</code>, respectively
168      */
169     public boolean get(final long slice, final long row, final long column)
170     {
171         if (slice < 0)
172         {
173             throw new IndexOutOfBoundsException(slice + " < 0");
174         }
175         if (slice >= slices)
176         {
177             throw new IndexOutOfBoundsException(slice + " >= " + slices);
178         }
179         if (row < 0)
180         {
181             throw new IndexOutOfBoundsException(row + " < 0");
182         }
183         if (row >= rows)
184         {
185             throw new IndexOutOfBoundsException(row + " >= " + rows);
186         }
187         if (column < 0)
188         {
189             throw new IndexOutOfBoundsException(column + " < 0");
190         }
191         if (column >= columns)
192         {
193             throw new IndexOutOfBoundsException(column + " >= " + columns);
194         }
195         return getQuick(slice, row, column);
196     }
197 
198     /**
199      * Return the bit value at the specified slice, row, and column without checking bounds.
200      *
201      * @param slice slice index
202      * @param row row index
203      * @param column column index
204      * @return the bit value at the specified slice, row, and column
205      */
206     public boolean getQuick(final long slice, final long row, final long column)
207     {
208         return bitset.getQuick(index(slice, row, column));
209     }
210 
211     /**
212      * Set the bit value at the specified slice, row, and column to <code>value</code>.
213      *
214      * @param slice slice index, must be <code>&gt;= 0</code> and <code>&lt; slices()</code>
215      * @param row row index, must be <code>&gt;= 0</code> and <code>&lt; rows()</code>
216      * @param column column index, must be <code>&gt;= 0</code> and <code>&lt; columns()</code>
217      * @param value value
218      * @throws IndexOutOfBoundsException if any of <code>slice</code>, <code>row</code>, or
219      *    <code>column</code> are negative or if any of <code>slice</code>, <code>row</code>,
220      *    or <code>column</code> are greater than or equal to <code>slices()</code>,
221      *    <code>rows()</code>, or <code>columns()</code>, respectively
222      */
223     public void set(final long slice, final long row, final long column, final boolean value)
224     {
225         if (slice < 0)
226         {
227             throw new IndexOutOfBoundsException(slice + " < 0");
228         }
229         if (slice >= slices)
230         {
231             throw new IndexOutOfBoundsException(slice + " >= " + slices);
232         }
233         if (row < 0)
234         {
235             throw new IndexOutOfBoundsException(row + " < 0");
236         }
237         if (row >= rows)
238         {
239             throw new IndexOutOfBoundsException(row + " >= " + rows);
240         }
241         if (column < 0)
242         {
243             throw new IndexOutOfBoundsException(column + " < 0");
244         }
245         if (column >= columns)
246         {
247             throw new IndexOutOfBoundsException(column + " >= " + columns);
248         }
249         setQuick(slice, row, column, value);
250     }
251 
252     /**
253      * Set the bit value at the specified slice, row, and column to <code>value</code> without checking bounds.
254      *
255      * @param slice slice index
256      * @param row row index
257      * @param column column index
258      * @param value value
259      */
260     public void setQuick(final long slice, final long row, final long column, final boolean value)
261     {
262         long index = index(slice, row, column);
263         if (value)
264         {
265             bitset.setQuick(index);
266         }
267         else
268         {
269             bitset.clearQuick(index);
270         }
271     }
272 
273     /**
274      * Set all of the bit values from (<code>slice0, row0, column0</code>), inclusive,
275      * to (<code>slice1, row1, column1</code>), exclusive, to the specified value.
276      *
277      * @param slice0 first slice, must be <code>&gt;= 0</code> and <code>&lt; slices()</code>
278      * @param row0 first row, must be <code>&gt;= 0</code> and <code>&lt; rows()</code>
279      * @param column0 first column, must be <code>&gt;= 0</code> and <code>&lt; columns()</code>
280      * @param slice1 second slice, must be <code>&gt;= 0</code>, <code>&lt;= slices()</code>
281      *    and <code>&gt;= slice0</code>
282      * @param row1 second row, must be <code>&gt;= 0</code>, <code>&lt;= rows()</code>
283      *    and <code>&gt;= row0</code>
284      * @param column1 second column, must be <code>&gt;= 0</code>, <code>&lt;= columns()</code>
285      *    and <code>&gt;= column0</code>
286      * @param value value
287      * @throws IllegalArgumentException if any of <code>slice1</code>, <code>row1</code>, or
288      *    <code>column1</code> are less than <code>slice0</code>, <code>row0</code>, or
289      *    <code>column0</code>, respectively
290      * @throws IndexOutOfBoundsException if any of <code>slice0</code>, <code>row0</code>,
291      *    <code>column0</code>, <code>slice1</code>, <code>row1</code>, or <code>column1</code>
292      *    are negative or if any of <code>slice0</code>, <code>row0</code>, or <code>column0</code>
293      *    are greater than or equal to <code>slices()</code>, <code>rows()</code>, or
294      *    <code>columns()</code>, respectively, or if any of <code>slice1</code>, <code>row1</code>, or
295      *    <code>column1</code> are strictly greater than <code>slices()</code>, <code>rows()</code>,
296      *    or <code>columns()</code>, respectively
297      */
298     public void set(final long slice0, final long row0, final long column0,
299                     final long slice1, final long row1, final long column1, final boolean value)
300     {
301         if (slice0 < 0)
302         {
303             throw new IndexOutOfBoundsException(slice0 + " < 0");
304         }
305         if (slice0 >= slices)
306         {
307             throw new IndexOutOfBoundsException(slice0 + " >= " + slices);
308         }
309         if (row0 < 0)
310         {
311             throw new IndexOutOfBoundsException(row0 + " < 0");
312         }
313         if (row0 >= rows)
314         {
315             throw new IndexOutOfBoundsException(row0 + " >= " + rows);
316         }
317         if (column0 < 0)
318         {
319             throw new IndexOutOfBoundsException(column0 + " < 0");
320         }
321         if (column0 >= columns)
322         {
323             throw new IndexOutOfBoundsException(column0 + " >= " + columns);
324         }
325         if (slice1 < 0)
326         {
327             throw new IndexOutOfBoundsException(slice1 + " < 0");
328         }
329         if (slice1 > slices)
330         {
331             throw new IndexOutOfBoundsException(slice1 + " > " + slices);
332         }
333         if (row1 < 0)
334         {
335             throw new IndexOutOfBoundsException(row1 + " < 0");
336         }
337         if (row1 > rows)
338         {
339             throw new IndexOutOfBoundsException(row1 + " > " + rows);
340         }
341         if (column1 < 0)
342         {
343             throw new IndexOutOfBoundsException(column1 + " < 0");
344         }
345         if (column1 > columns)
346         {
347             throw new IndexOutOfBoundsException(column1 + " > " + columns);
348         }
349 
350         for (long slice = slice0; slice < slice1; slice++)
351         {
352             for (long row = row0; row < row1; row++)
353             {
354                 for (long column = column0; column < column1; column++)
355                 {
356                     setQuick(slice, row, column, value);
357                 }
358             }
359         }
360     }
361 
362     /**
363      * Set the bit value at the specified slice, row, and column to the complement
364      * of its current bit value.
365      *
366      * @param slice slice index, must be <code>&gt;= 0</code> and <code>&lt; slices()</code>
367      * @param row row index, must be <code>&gt;= 0</code> and <code>&lt; rows()</code>
368      * @param column column index, must be <code>&gt;= 0</code> and <code>&lt; columns()</code>
369      * @throws IndexOutOfBoundsException if any of <code>slice</code>, <code>row</code>, or
370      *    <code>column</code> are negative or if any of <code>slice</code>, <code>row</code>,
371      *    or <code>column</code> are greater than or equal to <code>slices()</code>,
372      *    <code>rows()</code>, or <code>columns()</code>, respectively
373      */
374     public void flip(final long slice, final long row, final long column)
375     {
376         if (slice < 0)
377         {
378             throw new IndexOutOfBoundsException(slice + " < 0");
379         }
380         if (slice >= slices)
381         {
382             throw new IndexOutOfBoundsException(slice + " >= " + slices);
383         }
384         if (row < 0)
385         {
386             throw new IndexOutOfBoundsException(row + " < 0");
387         }
388         if (row >= rows)
389         {
390             throw new IndexOutOfBoundsException(row + " >= " + rows);
391         }
392         if (column < 0)
393         {
394             throw new IndexOutOfBoundsException(column + " < 0");
395         }
396         if (column >= columns)
397         {
398             throw new IndexOutOfBoundsException(column + " >= " + columns);
399         }
400         flipQuick(slice, row, column);
401     }
402 
403     /**
404      * Set the bit value at the specified slice, row, and column to the complement
405      * of its current bit value without checking bounds.
406      *
407      * @param slice slice index
408      * @param row row index
409      * @param column column index
410      */
411     public void flipQuick(final long slice, final long row, final long column)
412     {
413         bitset.flipQuick(index(slice, row, column));
414     }
415 
416     /**
417      * Set all of the bit values from (<code>slice0, row0, column0</code>), inclusive,
418      * to (<code>slice1, row1, column1</code>), exclusive, to the complement of their
419      * current bit values.
420      *
421      * @param slice0 first slice, must be <code>&gt;= 0</code> and <code>&lt; slices()</code>
422      * @param row0 first row, must be <code>&gt;= 0</code> and <code>&lt; rows()</code>
423      * @param column0 first column, must be <code>&gt;= 0</code> and <code>&lt; columns()</code>
424      * @param slice1 second slice, must be <code>&gt;= 0</code>, <code>&lt;= slices()</code>
425      *    and <code>&gt;= slice0</code>
426      * @param row1 second row, must be <code>&gt;= 0</code>, <code>&lt;= rows()</code>
427      *    and <code>&gt;= row0</code>
428      * @param column1 second column, must be <code>&gt;= 0</code>, <code>&lt;= columns()</code>
429      *    and <code>&gt;= column0</code>
430      * @throws IllegalArgumentException if any of <code>slice1</code>, <code>row1</code>, or
431      *    <code>column1</code> are less than <code>slice0</code>, <code>row0</code>, or
432      *    <code>column0</code>, respectively
433      * @throws IndexOutOfBoundsException if any of <code>slice0</code>, <code>row0</code>,
434      *    <code>column0</code>, <code>slice1</code>, <code>row1</code>, or <code>column1</code>
435      *    are negative or if any of <code>slice0</code>, <code>row0</code>, or <code>column0</code>
436      *    are greater than or equal to <code>slices()</code>, <code>rows()</code>, or
437      *    <code>columns()</code>, respectively, or if any of <code>slice1</code>, <code>row1</code>, or
438      *    <code>column1</code> are strictly greater than <code>slices()</code>, <code>rows()</code>,
439      *    or <code>columns()</code>, respectively
440      */
441     public void flip(final long slice0, final long row0, final long column0,
442                      final long slice1, final long row1, final long column1)
443     {
444         if (slice0 < 0)
445         {
446             throw new IndexOutOfBoundsException(slice0 + " < 0");
447         }
448         if (slice0 >= slices)
449         {
450             throw new IndexOutOfBoundsException(slice0 + " >= " + slices);
451         }
452         if (row0 < 0)
453         {
454             throw new IndexOutOfBoundsException(row0 + " < 0");
455         }
456         if (row0 >= rows)
457         {
458             throw new IndexOutOfBoundsException(row0 + " >= " + rows);
459         }
460         if (column0 < 0)
461         {
462             throw new IndexOutOfBoundsException(column0 + " < 0");
463         }
464         if (column0 >= columns)
465         {
466             throw new IndexOutOfBoundsException(column0 + " >= " + columns);
467         }
468         if (slice1 < 0)
469         {
470             throw new IndexOutOfBoundsException(slice1 + " < 0");
471         }
472         if (slice1 > slices)
473         {
474             throw new IndexOutOfBoundsException(slice1 + " > " + slices);
475         }
476         if (row1 < 0)
477         {
478             throw new IndexOutOfBoundsException(row1 + " < 0");
479         }
480         if (row1 > rows)
481         {
482             throw new IndexOutOfBoundsException(row1 + " > " + rows);
483         }
484         if (column1 < 0)
485         {
486             throw new IndexOutOfBoundsException(column1 + " < 0");
487         }
488         if (column1 > columns)
489         {
490             throw new IndexOutOfBoundsException(column1 + " > " + columns);
491         }
492 
493         for (long slice = slice0; slice < slice1; slice++)
494         {
495             for (long row = row0; row < row1; row++)
496             {
497                 for (long column = column0; column < column1; column++)
498                 {
499                     flipQuick(slice, row, column);
500                 }
501             }
502         }
503     }
504 
505     /**
506      * Assign all values in this 3D bit matrix to <code>value</code>.
507      *
508      * @param value value
509      * @return this 3D bit matrix, for convenience
510      */
511     public BitMatrix3D assign(final boolean value)
512     {
513         if (size > 0)
514         {
515             set(0, 0, 0, slices, rows, columns, value);
516         }
517         return this;
518     }
519 
520     /**
521      * Return true if the specified 3D bit matrix has any bits set
522      * to true that are also set to true in this 3D bit matrix.
523      *
524      * @param other other 3D bit matrix, must not be null and must
525      *    have the same dimensions as this 3D bit matrix
526      * @return true if the specified 3D bit matrix has any bits set
527      *    to true that are also set to true in this 3D bit matrix
528      */
529     public boolean intersects(final BitMatrix3D other)
530     {
531         if (other == null)
532         {
533             throw new IllegalArgumentException("other must not be null");
534         }
535         if ((size != other.size()) || (slices != other.slices()) || (rows != other.rows())
536             || (columns != other.columns()))
537         {
538             throw new IllegalArgumentException("this and other must have the same dimensions");
539         }
540         return bitset.intersects(other.bitset);
541     }
542 
543     /**
544      * Perform a logical <b>AND</b> of this 3D bit matrix
545      * and the specified 3D bit matrix.
546      *
547      * @param other other 3D bit matrix, must not be null and must
548      *    have the same dimensions as this 3D bit matrix
549      * @return this 3D bit matrix, for convenience
550      */
551     public BitMatrix3D and(final BitMatrix3D other)
552     {
553         if (other == null)
554         {
555             throw new IllegalArgumentException("other must not be null");
556         }
557         if ((size != other.size()) || (slices != other.slices()) || (rows != other.rows())
558             || (columns != other.columns()))
559         {
560             throw new IllegalArgumentException("this and other must have the same dimensions");
561         }
562         bitset.and(other.bitset);
563         return this;
564 
565     }
566 
567     /**
568      * Clear all the bits in this 3D bit matrix whose corresponding
569      * bit is set in the specified 3D bit matrix.
570      *
571      * @param other other 3D bit matrix, must not be null and must
572      *    have the same dimensions as this 3D bit matrix
573      * @return this 3D bit matrix, for convenience
574      */
575     public BitMatrix3D andNot(final BitMatrix3D other)
576     {
577         if (other == null)
578         {
579             throw new IllegalArgumentException("other must not be null");
580         }
581         if ((size != other.size()) || (slices != other.slices()) || (rows != other.rows())
582             || (columns != other.columns()))
583         {
584             throw new IllegalArgumentException("this and other must have the same dimensions");
585         }
586         bitset.andNot(other.bitset);
587         return this;
588     }
589 
590     /**
591      * Perform a logical <b>OR</b> of this 3D bit matrix
592      * and the specified 3D bit matrix.
593      *
594      * @param other other 3D bit matrix, must not be null and must
595      *    have the same dimensions as this 3D bit matrix
596      * @return this 3D bit matrix, for convenience
597      */
598     public BitMatrix3D or(final BitMatrix3D other)
599     {
600         if (other == null)
601         {
602             throw new IllegalArgumentException("other must not be null");
603         }
604         if ((size != other.size()) || (slices != other.slices()) || (rows != other.rows())
605             || (columns != other.columns()))
606         {
607             throw new IllegalArgumentException("this and other must have the same dimensions");
608         }
609         bitset.or(other.bitset);
610         return this;
611     }
612 
613     /**
614      * Perform a logical <b>XOR</b> of this 3D bit matrix
615      * and the specified 3D bit matrix.
616      *
617      * @param other other 3D bit matrix, must not be null and must
618      *    have the same dimensions as this 3D bit matrix
619      * @return this 3D bit matrix, for convenience
620      */
621     public BitMatrix3D xor(final BitMatrix3D other)
622     {
623         if (other == null)
624         {
625             throw new IllegalArgumentException("other must not be null");
626         }
627         if ((size != other.size()) || (slices != other.slices()) || (rows != other.rows())
628             || (columns != other.columns()))
629         {
630             throw new IllegalArgumentException("this and other must have the same dimensions");
631         }
632         bitset.xor(other.bitset);
633         return this;
634     }
635 
636     /**
637      * Apply the specified procedure to each slice, row, and column
638      * in this 3D bit matrix with a bit equal to the specified value.
639      *
640      * @param value value
641      * @param procedure procedure, must not be null
642      */
643     public void forEach(final boolean value,
644                         final TernaryProcedure<Long, Long, Long> procedure)
645     {
646         if (procedure == null)
647         {
648             throw new IllegalArgumentException("procedure must not be null");
649         }
650 
651         for (long slice = 0; slice < slices; slice++)
652         {
653             for (long row = 0; row < rows; row++)
654             {
655                 for (long column = 0; column < columns; column++)
656                 {
657                     if (getQuick(slice, row, column) == value)
658                     {
659                         procedure.run(Long.valueOf(slice), Long.valueOf(row), Long.valueOf(column));
660                     }
661                 }
662             }
663         }
664     }
665 
666     /** {@inheritDoc} */
667     public boolean equals(final Object o)
668     {
669         if (o == null)
670         {
671             return false;
672         }
673         if (!(o instanceof BitMatrix3D))
674         {
675             return false;
676         }
677 
678         BitMatrix3D bm = (BitMatrix3D) o;
679 
680         if ((size != bm.size()) || (slices != bm.slices()) || (rows != bm.rows()) || (columns != bm.columns()))
681         {
682             return false;
683         }
684         return bitset.equals(bm.bitset);
685     }
686 
687     /** {@inheritDoc} */
688     public int hashCode()
689     {
690         int hashCode = 37;
691         hashCode = 17 * hashCode + (int) (size ^ (size >>> 32));
692         hashCode = 17 * hashCode + (int) (slices ^ (slices >>> 32));
693         hashCode = 17 * hashCode + (int) (rows ^ (rows >>> 32));
694         hashCode = 17 * hashCode + (int) (columns ^ (columns >>> 32));
695         hashCode = 17 * hashCode + bitset.hashCode();
696         return hashCode;
697     }
698 
699 
700     /**
701      * Return the index for the specified slice, row, and column.
702      *
703      * @param slice slice inddex
704      * @param row row index
705      * @param column column index
706      * @return the index for the specified slice, row, and column
707      */
708     private long index(final long slice, final long row, final long column)
709     {
710         return (rows * columns * slice) + (columns * row) + column;
711     }
712 }