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.UnaryProcedure;
29
30 /**
31 * Fixed size bit matrix in one dimension, indexed by <code>long</code>s.
32 *
33 * @author Michael Heuer
34 */
35 public final class BitMatrix1D
36 {
37 /** Bit set. */
38 private final MutableBitSet bitset;
39
40 /** Size. */
41 private final long size;
42
43
44 /**
45 * Create a new 1D bit matrix of the specified size.
46 *
47 * @param size size, must be <code>>= 0</code>
48 * @throws IllegalArgumentException if <code>size</code> is negative
49 */
50 public BitMatrix1D(final long size)
51 {
52 if (size < 0)
53 {
54 throw new IllegalArgumentException("size must be >= 0");
55 }
56 this.size = size;
57 this.bitset = new MutableBitSet(size);
58 }
59
60
61 /**
62 * Return the size of this 1D bit matrix.
63 *
64 * @return the size of this 1D bit matrix
65 */
66 public long size()
67 {
68 return size;
69 }
70
71 /**
72 * Return the cardinality of this 1D bit matrix, the
73 * number of bits set to true.
74 *
75 * @return the cardinality of this 1D bit matrix
76 */
77 public long cardinality()
78 {
79 return bitset.cardinality();
80 }
81
82 /**
83 * Return true if the cardinality of this 1D bit matrix is zero.
84 *
85 * @return true if the cardinality of this 1D bit matrix is zero
86 */
87 public boolean isEmpty()
88 {
89 return bitset.isEmpty();
90 }
91
92 /**
93 * Clear all the values in this 1D bit matrix.
94 */
95 public void clear()
96 {
97 for (long i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i + 1))
98 {
99 bitset.clear(i);
100 }
101 }
102
103 /**
104 * Return the bit value at the specified index.
105 *
106 * @param index index, must be <code>>= 0</code> and <code>< size()</code>
107 * @return the bit value at the specified index
108 * @throws IndexOutOfBoundsException if <code>index</code> is negative
109 * or if <code>index</code> is greater than or equal to <code>size()</code>
110 */
111 public boolean get(final long index)
112 {
113 if (index < 0)
114 {
115 throw new IndexOutOfBoundsException(index + " < 0");
116 }
117 if (index >= size)
118 {
119 throw new IndexOutOfBoundsException(index + " >= " + size);
120 }
121 return getQuick(index);
122 }
123
124 /**
125 * Return the bit value at the specified index without checking bounds.
126 *
127 * @param index index
128 * @return the bit value at the specified index
129 */
130 public boolean getQuick(final long index)
131 {
132 return bitset.getQuick(index);
133 }
134
135 /**
136 * Set the bit value at the specified index to <code>value</code>.
137 *
138 * @param index index, must be <code>>= 0</code> and <code>< size()</code>
139 * @param value value
140 * @throws IndexOutOfBoundsException if <code>index</code> is negative
141 * or if <code>index</code> is greater than or equal to <code>size()</code>
142 */
143 public void set(final long index, final boolean value)
144 {
145 if (index < 0)
146 {
147 throw new IndexOutOfBoundsException(index + " < 0");
148 }
149 if (index >= size)
150 {
151 throw new IndexOutOfBoundsException(index + " >= " + size);
152 }
153 setQuick(index, value);
154 }
155
156 /**
157 * Set the bit value at the specified index to <code>value</code> without checking bounds.
158 *
159 * @param index index
160 * @param value value
161 */
162 public void setQuick(final long index, final boolean value)
163 {
164 if (value)
165 {
166 bitset.setQuick(index);
167 }
168 else
169 {
170 bitset.clearQuick(index);
171 }
172 }
173
174 /**
175 * Set all of the bit values from <code>index0</code>, inclusive, to
176 * <code>index1</code>, exclusive, to the specified value.
177 *
178 * @param index0 first index, must be <code>>= 0</code> and <code>< size()</code>
179 * @param index1 second index, must be <code>>= 0</code>, <code><= size()</code>
180 * and <code>>= index0</code>
181 * @param value value
182 * @throws IllegalArgumentException if <code>index1</code> is less than <code>index0</code>
183 * @throws IndexOutOfBoundsException if either <code>index0</code>
184 * or <code>index1</code> are negative or if <code>index0</code> is greater than
185 * or equal to <code>size()</code> or if <code>index1</code> is strictly greater
186 * than <code>size()</code>
187 */
188 public void set(final long index0, final long index1, final boolean value)
189 {
190 if (index0 >= size)
191 {
192 throw new IndexOutOfBoundsException(index0 + " >= " + size);
193 }
194 if (index1 > size)
195 {
196 throw new IndexOutOfBoundsException(index1 + " > " + size);
197 }
198 if (value)
199 {
200 bitset.set(index0, index1);
201 }
202 else
203 {
204 bitset.clear(index0, index1);
205 }
206 }
207
208 /**
209 * Set the bit value at the specified index to the complement
210 * of its current bit value.
211 *
212 * @param index index, must be <code>>= 0</code> and <code>< size()</code>
213 * @throws IndexOutOfBoundsException if <code>index</code> is negative
214 * or if <code>index</code> is greater than or equal to <code>size()</code>
215 */
216 public void flip(final long index)
217 {
218 if (index < 0)
219 {
220 throw new IndexOutOfBoundsException(index + " < 0");
221 }
222 if (index >= size)
223 {
224 throw new IndexOutOfBoundsException(index + " >= " + size);
225 }
226 flipQuick(index);
227 }
228
229 /**
230 * Set the bit value at the specified index to the complement
231 * of its current bit value without checking bounds.
232 *
233 * @param index index
234 */
235 public void flipQuick(final long index)
236 {
237 bitset.flipQuick(index);
238 }
239
240 /**
241 * Set all of the bit values from <code>index0</code>, inclusive, to
242 * <code>index1</code>, exclusive, to the complement of their current
243 * bit values.
244 *
245 * @param index0 first index, must be <code>>= 0</code> and <code>< size()</code>
246 * @param index1 second index, must be <code>>= 0</code>, <code><= size()</code>
247 * and <code>>= index0</code>
248 * @throws IllegalArgumentException if <code>index1</code> is less than <code>index0</code>
249 * @throws IndexOutOfBoundsException if either <code>index0</code>
250 * or <code>index1</code> are negative or if <code>index0</code> is greater than
251 * or equal to <code>size()</code> or if <code>index1</code> is strictly greater
252 * than <code>size()</code>
253 */
254 public void flip(final long index0, final long index1)
255 {
256 if (index0 >= size)
257 {
258 throw new IndexOutOfBoundsException(index0 + " >= " + size);
259 }
260 if (index1 > size)
261 {
262 throw new IndexOutOfBoundsException(index1 + " > " + size);
263 }
264 bitset.flip(index0, index1);
265 }
266
267 /**
268 * Assign all values in this 1D bit matrix to <code>value</code>.
269 *
270 * @param value value
271 * @return this 1D bit matrix, for convenience
272 */
273 public BitMatrix1D assign(final boolean value)
274 {
275 if (size > 0)
276 {
277 set(0, size, value);
278 }
279 return this;
280 }
281
282 /**
283 * Return true if the specified 1D bit matrix has any bits set
284 * to true that are also set to true in this 1D bit matrix.
285 *
286 * @param other other 1D bit matrix, must not be null and must
287 * be the same size as this 1D bit matrix
288 * @return true if the specified 1D bit matrix has any bits set
289 * to true that are also set to true in this 1D bit matrix
290 * @throws IllegalArgumentException if <code>other</code> is null
291 * or if <code>other</code> is not the same size as <code>this</code>
292 */
293 public boolean intersects(final BitMatrix1D other)
294 {
295 if (other == null)
296 {
297 throw new IllegalArgumentException("other must not be null");
298 }
299 if (size != other.size())
300 {
301 throw new IllegalArgumentException("this and other must be the same size");
302 }
303 return bitset.intersects(other.bitset);
304 }
305
306 /**
307 * Perform a logical <b>AND</b> of this 1D bit matrix
308 * and the specified 1D bit matrix.
309 *
310 * @param other other 1D bit matrix, must not be null and must
311 * be the same size as this 1D bit matrix
312 * @return this 1D bit matrix, for convenience
313 * @throws IllegalArgumentException if <code>other</code> is null
314 * or if <code>other</code> is not the same size as <code>this</code>
315 */
316 public BitMatrix1D and(final BitMatrix1D other)
317 {
318 if (other == null)
319 {
320 throw new IllegalArgumentException("other must not be null");
321 }
322 if (!(size == other.size()))
323 {
324 throw new IllegalArgumentException("this and other must be the same size");
325 }
326 bitset.and(other.bitset);
327 return this;
328 }
329
330 /**
331 * Clear all of the bits in this 1D bit matrix whose corresponding
332 * bit is set in the specified 1D bit matrix.
333 *
334 * @param other other 1D bit matrix, must not be null and must
335 * be the same size as this 1D bit matrix
336 * @return this 1D bit matrix, for convenience
337 * @throws IllegalArgumentException if <code>other</code> is null
338 * or if <code>other</code> is not the same size as <code>this</code>
339 */
340 public BitMatrix1D andNot(final BitMatrix1D other)
341 {
342 if (other == null)
343 {
344 throw new IllegalArgumentException("other must not be null");
345 }
346 if (size != other.size())
347 {
348 throw new IllegalArgumentException("this and other must be the same size");
349 }
350 bitset.andNot(other.bitset);
351 return this;
352 }
353
354 /**
355 * Perform a logical <b>OR</b> of this 1D bit matrix
356 * and the specified 1D bit matrix.
357 *
358 * @param other other 1D bit matrix, must not be null and must
359 * be the same size as this 1D bit matrix
360 * @return this 1D bit matrix, for convenience
361 * @throws IllegalArgumentException if <code>other</code> is null
362 * or if <code>other</code> is not the same size as <code>this</code>
363 */
364 public BitMatrix1D or(final BitMatrix1D other)
365 {
366 if (other == null)
367 {
368 throw new IllegalArgumentException("other must not be null");
369 }
370 if (size != other.size())
371 {
372 throw new IllegalArgumentException("this and other must be the same size");
373 }
374 bitset.or(other.bitset);
375 return this;
376 }
377
378 /**
379 * Perform a logical <b>XOR</b> of this 1D bit matrix
380 * and the specified 1D bit matrix.
381 *
382 * @param other other 1D bit matrix, must not be null and must
383 * be the same size as this 1D bit matrix
384 * @return this 1D bit matrix, for convenience
385 * @throws IllegalArgumentException if <code>other</code> is null
386 * or if <code>other</code> is not the same size as <code>this</code>
387 */
388 public BitMatrix1D xor(final BitMatrix1D other)
389 {
390 if (other == null)
391 {
392 throw new IllegalArgumentException("other must not be null");
393 }
394 if (size != other.size())
395 {
396 throw new IllegalArgumentException("this and other must be the same size");
397 }
398 bitset.xor(other.bitset);
399 return this;
400 }
401
402 /**
403 * Apply the specified procedure to each index in this 1D bit
404 * matrix with a bit equal to the specified value.
405 *
406 * @param value value
407 * @param procedure procedure, must not be null
408 */
409 public void forEach(final boolean value, final UnaryProcedure<Long> procedure)
410 {
411 if (procedure == null)
412 {
413 throw new IllegalArgumentException("procedure must not be null");
414 }
415 if (value)
416 {
417 for (long i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i + 1))
418 {
419 procedure.run(Long.valueOf(i));
420 }
421 }
422 else
423 {
424 // less efficient
425 for (long i = 0; i < size; i++)
426 {
427 if (!bitset.getQuick(i))
428 {
429 procedure.run(Long.valueOf(i));
430 }
431 }
432 }
433 }
434
435 /** {@inheritDoc} */
436 public boolean equals(final Object o)
437 {
438 if (o == null)
439 {
440 return false;
441 }
442 if (!(o instanceof BitMatrix1D))
443 {
444 return false;
445 }
446
447 BitMatrix1D bm = (BitMatrix1D) o;
448
449 if (size != bm.size())
450 {
451 return false;
452 }
453 return bitset.equals(bm.bitset);
454 }
455
456 /** {@inheritDoc} */
457 public int hashCode()
458 {
459 int hashCode = 37;
460 hashCode = 17 * hashCode + (int) (size ^ (size >>> 32));
461 hashCode = 17 * hashCode + bitset.hashCode();
462 return hashCode;
463 }
464 }