1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.lang3.util;
18
19 import java.io.IOException;
20 import java.io.InvalidObjectException;
21 import java.io.NotActiveException;
22 import java.io.ObjectInputStream;
23 import java.io.Serializable;
24 import java.util.BitSet;
25 import java.util.Objects;
26 import java.util.stream.IntStream;
27
28 import org.apache.commons.lang3.SerializationUtils;
29
30 /**
31 * A fluent {@link BitSet} with additional operations.
32 * <p>
33 * Originally from Apache Commons VFS with more added to act as a fluent replacement for {@link java.util.BitSet}.
34 * </p>
35 *
36 * @since 3.13.0
37 */
38 public final class FluentBitSet implements Cloneable, Serializable {
39
40 private static final long serialVersionUID = 1L;
41
42 /**
43 * Working BitSet.
44 */
45 private final BitSet bitSet;
46
47 /**
48 * Creates a new bit set. All bits are initially {@code false}.
49 */
50 public FluentBitSet() {
51 this(new BitSet());
52 }
53
54 /**
55 * Creates a new instance for the given bit set.
56 *
57 * @param set The bit set to wrap.
58 */
59 public FluentBitSet(final BitSet set) {
60 this.bitSet = Objects.requireNonNull(set, "set");
61 }
62
63 /**
64 * Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range {@code 0}
65 * through {@code nbits-1}. All bits are initially {@code false}.
66 *
67 * @param nbits The initial size of the bit set.
68 * @throws NegativeArraySizeException Thrown if the specified initial size is negative.
69 */
70 public FluentBitSet(final int nbits) {
71 this(new BitSet(nbits));
72 }
73
74 /**
75 * Performs a logical <strong>AND</strong> of this target bit set with the argument bit set. This bit set is modified so that each
76 * bit in it has the value {@code true} if and only if it both initially had the value {@code true} and the
77 * corresponding bit in the bit set argument also had the value {@code true}.
78 *
79 * @param set A bit set.
80 * @return {@code this} instance.
81 */
82 public FluentBitSet and(final BitSet set) {
83 bitSet.and(set);
84 return this;
85 }
86
87 /**
88 * Performs a logical <strong>AND</strong> of this target bit set with the argument bit set. This bit set is modified so that each
89 * bit in it has the value {@code true} if and only if it both initially had the value {@code true} and the
90 * corresponding bit in the bit set argument also had the value {@code true}.
91 *
92 * @param set A bit set.
93 * @return {@code this} instance.
94 */
95 public FluentBitSet and(final FluentBitSet set) {
96 bitSet.and(set.bitSet);
97 return this;
98 }
99
100 /**
101 * Clears all of the bits in this {@link BitSet} whose corresponding bit is set in the specified {@link BitSet}.
102 *
103 * @param set The {@link BitSet} with which to mask this {@link BitSet}.
104 * @return {@code this} instance.
105 */
106 public FluentBitSet andNot(final BitSet set) {
107 bitSet.andNot(set);
108 return this;
109 }
110
111 /**
112 * Clears all of the bits in this {@link BitSet} whose corresponding bit is set in the specified {@link BitSet}.
113 *
114 * @param set The {@link BitSet} with which to mask this {@link BitSet}.
115 * @return {@code this} instance.
116 */
117 public FluentBitSet andNot(final FluentBitSet set) {
118 this.bitSet.andNot(set.bitSet);
119 return this;
120 }
121
122 /**
123 * Gets the wrapped bit set.
124 *
125 * @return The wrapped bit set.
126 */
127 public BitSet bitSet() {
128 return bitSet;
129 }
130
131 /**
132 * Returns the number of bits set to {@code true} in this {@link BitSet}.
133 *
134 * @return The number of bits set to {@code true} in this {@link BitSet}.
135 */
136 public int cardinality() {
137 return bitSet.cardinality();
138 }
139
140 /**
141 * Sets all of the bits in this BitSet to {@code false}.
142 *
143 * @return {@code this} instance.
144 */
145 public FluentBitSet clear() {
146 bitSet.clear();
147 return this;
148 }
149
150 /**
151 * Sets the bits specified by the indexes to {@code false}.
152 *
153 * @param bitIndexArray The index of the bit to be cleared.
154 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
155 * @return {@code this} instance.
156 */
157 public FluentBitSet clear(final int... bitIndexArray) {
158 for (final int e : bitIndexArray) {
159 this.bitSet.clear(e);
160 }
161 return this;
162 }
163
164 /**
165 * Sets the bit specified by the index to {@code false}.
166 *
167 * @param bitIndex The index of the bit to be cleared.
168 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
169 * @return {@code this} instance.
170 */
171 public FluentBitSet clear(final int bitIndex) {
172 bitSet.clear(bitIndex);
173 return this;
174 }
175
176 /**
177 * Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to
178 * {@code false}.
179 *
180 * @param fromIndex index of the first bit to be cleared.
181 * @param toIndex index after the last bit to be cleared.
182 * @throws IndexOutOfBoundsException Thrown if {@code fromIndex} is negative, or {@code toIndex} is negative, or
183 * {@code fromIndex} is larger than {@code toIndex}.
184 * @return {@code this} instance.
185 */
186 public FluentBitSet clear(final int fromIndex, final int toIndex) {
187 bitSet.clear(fromIndex, toIndex);
188 return this;
189 }
190
191 /**
192 * Cloning this {@link BitSet} produces a new {@link BitSet} that is equal to it. The clone of the bit set is another
193 * bit set that has exactly the same bits set to {@code true} as this bit set.
194 *
195 * @return A clone of this bit set
196 * @see #size()
197 */
198 @Override
199 public Object clone() {
200 return new FluentBitSet((BitSet) bitSet.clone());
201 }
202
203 @Override
204 public boolean equals(final Object obj) {
205 if (this == obj) {
206 return true;
207 }
208 if (!(obj instanceof FluentBitSet)) {
209 return false;
210 }
211 final FluentBitSet other = (FluentBitSet) obj;
212 return Objects.equals(bitSet, other.bitSet);
213 }
214
215 /**
216 * Sets the bit at the specified index to the complement of its current value.
217 *
218 * @param bitIndex The index of the bit to flip.
219 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
220 * @return {@code this} instance.
221 */
222 public FluentBitSet flip(final int bitIndex) {
223 bitSet.flip(bitIndex);
224 return this;
225 }
226
227 /**
228 * Sets each bit from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to the
229 * complement of its current value.
230 *
231 * @param fromIndex index of the first bit to flip.
232 * @param toIndex index after the last bit to flip.
233 * @throws IndexOutOfBoundsException Thrown if {@code fromIndex} is negative, or {@code toIndex} is negative, or
234 * {@code fromIndex} is larger than {@code toIndex}.
235 * @return {@code this} instance.
236 */
237 public FluentBitSet flip(final int fromIndex, final int toIndex) {
238 bitSet.flip(fromIndex, toIndex);
239 return this;
240 }
241
242 /**
243 * Gets the value of the bit with the specified index. The value is {@code true} if the bit with the index
244 * {@code bitIndex} is currently set in this {@link BitSet}; otherwise, the result is {@code false}.
245 *
246 * @param bitIndex The bit index.
247 * @return The value of the bit with the specified index.
248 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
249 */
250 public boolean get(final int bitIndex) {
251 return bitSet.get(bitIndex);
252 }
253
254 /**
255 * Gets a new {@link BitSet} composed of bits from this {@link BitSet} from {@code fromIndex} (inclusive) to
256 * {@code toIndex} (exclusive).
257 *
258 * @param fromIndex index of the first bit to include.
259 * @param toIndex index after the last bit to include.
260 * @return A new {@link BitSet} from a range of this {@link BitSet}.
261 * @throws IndexOutOfBoundsException Thrown if {@code fromIndex} is negative, or {@code toIndex} is negative, or
262 * {@code fromIndex} is larger than {@code toIndex}.
263 */
264 public FluentBitSet get(final int fromIndex, final int toIndex) {
265 return new FluentBitSet(bitSet.get(fromIndex, toIndex));
266 }
267
268 @Override
269 public int hashCode() {
270 return bitSet.hashCode();
271 }
272
273 /**
274 * Returns true if the specified {@link BitSet} has any bits set to {@code true} that are also set to {@code true} in
275 * this {@link BitSet}.
276 *
277 * @param set {@link BitSet} to intersect with.
278 * @return boolean indicating whether this {@link BitSet} intersects the specified {@link BitSet}.
279 */
280 public boolean intersects(final BitSet set) {
281 return bitSet.intersects(set);
282 }
283
284 /**
285 * Returns true if the specified {@link BitSet} has any bits set to {@code true} that are also set to {@code true} in
286 * this {@link BitSet}.
287 *
288 * @param set {@link BitSet} to intersect with.
289 * @return boolean indicating whether this {@link BitSet} intersects the specified {@link BitSet}.
290 */
291 public boolean intersects(final FluentBitSet set) {
292 return bitSet.intersects(set.bitSet);
293 }
294
295 /**
296 * Tests whether if this {@link BitSet} contains no bits that are set to {@code true}.
297 *
298 * @return boolean indicating whether this {@link BitSet} is empty.
299 */
300 public boolean isEmpty() {
301 return bitSet.isEmpty();
302 }
303
304 /**
305 * Returns the "logical size" of this {@link BitSet}: the index of the highest set bit in the {@link BitSet} plus one.
306 * Returns zero if the {@link BitSet} contains no set bits.
307 *
308 * @return The logical size of this {@link BitSet}.
309 */
310 public int length() {
311 return bitSet.length();
312 }
313
314 /**
315 * Returns the index of the first bit that is set to {@code false} that occurs on or after the specified starting index.
316 *
317 * @param fromIndex The index to start checking from (inclusive).
318 * @return The index of the next clear bit.
319 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
320 */
321 public int nextClearBit(final int fromIndex) {
322 return bitSet.nextClearBit(fromIndex);
323 }
324
325 /**
326 * Returns the index of the first bit that is set to {@code true} that occurs on or after the specified starting index.
327 * If no such bit exists then {@code -1} is returned.
328 * <p>
329 * To iterate over the {@code true} bits in a {@link BitSet}, use the following loop:
330 * </p>
331 *
332 * <pre>
333 * {@code
334 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
335 * // operate on index i here
336 * if (i == Integer.MAX_VALUE) {
337 * break; // or (i+1) would overflow
338 * }
339 * }}
340 * </pre>
341 *
342 * @param fromIndex The index to start checking from (inclusive).
343 * @return The index of the next set bit, or {@code -1} if there is no such bit.
344 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
345 */
346 public int nextSetBit(final int fromIndex) {
347 return bitSet.nextSetBit(fromIndex);
348 }
349
350 /**
351 * Performs a logical <strong>OR</strong> of this bit set with the bit set argument. This bit set is modified so that a bit in it
352 * has the value {@code true} if and only if it either already had the value {@code true} or the corresponding bit in
353 * the bit set argument has the value {@code true}.
354 *
355 * @param set A bit set.
356 * @return {@code this} instance.
357 */
358 public FluentBitSet or(final BitSet set) {
359 bitSet.or(set);
360 return this;
361 }
362
363 /**
364 * Performs a logical <strong>OR</strong> of this bit set with the bit set arguments. This bit set is modified so that a bit in it
365 * has the value {@code true} if and only if it either already had the value {@code true} or the corresponding bit in
366 * the bit set argument has the value {@code true}.
367 *
368 * @param set A bit set.
369 * @return {@code this} instance.
370 */
371 public FluentBitSet or(final FluentBitSet... set) {
372 for (final FluentBitSet e : set) {
373 this.bitSet.or(e.bitSet);
374 }
375 return this;
376 }
377
378 /**
379 * Performs a logical <strong>OR</strong> of this bit set with the bit set argument. This bit set is modified so that a bit in it
380 * has the value {@code true} if and only if it either already had the value {@code true} or the corresponding bit in
381 * the bit set argument has the value {@code true}.
382 *
383 * @param set A bit set.
384 * @return {@code this} instance.
385 */
386 public FluentBitSet or(final FluentBitSet set) {
387 this.bitSet.or(set.bitSet);
388 return this;
389 }
390
391 /**
392 * Returns the index of the nearest bit that is set to {@code false} that occurs on or before the specified starting
393 * index. If no such bit exists, or if {@code -1} is given as the starting index, then {@code -1} is returned.
394 *
395 * @param fromIndex The index to start checking from (inclusive).
396 * @return The index of the previous clear bit, or {@code -1} if there is no such bit.
397 * @throws IndexOutOfBoundsException Thrown if the specified index is less than {@code -1}.
398 */
399 public int previousClearBit(final int fromIndex) {
400 return bitSet.previousClearBit(fromIndex);
401 }
402
403 /**
404 * Returns the index of the nearest bit that is set to {@code true} that occurs on or before the specified starting
405 * index. If no such bit exists, or if {@code -1} is given as the starting index, then {@code -1} is returned.
406 *
407 * <p>
408 * To iterate over the {@code true} bits in a {@link BitSet}, use the following loop:
409 *
410 * <pre>
411 * {@code
412 * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
413 * // operate on index i here
414 * }}
415 * </pre>
416 *
417 * @param fromIndex The index to start checking from (inclusive)
418 * @return The index of the previous set bit, or {@code -1} if there is no such bit
419 * @throws IndexOutOfBoundsException Thrown if the specified index is less than {@code -1}.
420 */
421 public int previousSetBit(final int fromIndex) {
422 return bitSet.previousSetBit(fromIndex);
423 }
424
425 /**
426 * Reads and restores the state of the object.
427 *
428 * @param in The source stream.
429 * @throws ClassNotFoundException Thrown if the class of a serialized object could not be found.
430 * @throws IOException Thrown if an I/O error occurs.
431 * @throws NotActiveException Thrown if the stream is not currently reading objects.
432 * @throws InvalidObjectException Thrown if {@code bitSet} is {@code null}.
433 */
434 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
435 in.defaultReadObject();
436 SerializationUtils.requireNonNull(bitSet, "bitSet null");
437 }
438
439 /**
440 * Sets the bit at the specified indexes to {@code true}.
441 *
442 * @param bitIndexArray A bit index array.
443 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
444 * @return {@code this} instance.
445 */
446 public FluentBitSet set(final int... bitIndexArray) {
447 for (final int e : bitIndexArray) {
448 bitSet.set(e);
449 }
450 return this;
451 }
452
453 /**
454 * Sets the bit at the specified index to {@code true}.
455 *
456 * @param bitIndex A bit index
457 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
458 * @return {@code this} instance.
459 */
460 public FluentBitSet set(final int bitIndex) {
461 bitSet.set(bitIndex);
462 return this;
463 }
464
465 /**
466 * Sets the bit at the specified index to the specified value.
467 *
468 * @param bitIndex A bit index.
469 * @param value A boolean value to set.
470 * @throws IndexOutOfBoundsException Thrown if the specified index is negative.
471 * @return {@code this} instance.
472 */
473 public FluentBitSet set(final int bitIndex, final boolean value) {
474 bitSet.set(bitIndex, value);
475 return this;
476 }
477
478 /**
479 * Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to
480 * {@code true}.
481 *
482 * @param fromIndex index of the first bit to be set.
483 * @param toIndex index after the last bit to be set.
484 * @throws IndexOutOfBoundsException Thrown if {@code fromIndex} is negative, or {@code toIndex} is negative, or
485 * {@code fromIndex} is larger than {@code toIndex}.
486 * @return {@code this} instance.
487 */
488 public FluentBitSet set(final int fromIndex, final int toIndex) {
489 bitSet.set(fromIndex, toIndex);
490 return this;
491 }
492
493 /**
494 * Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to the
495 * specified value.
496 *
497 * @param fromIndex index of the first bit to be set.
498 * @param toIndex index after the last bit to be set.
499 * @param value value to set the selected bits to.
500 * @throws IndexOutOfBoundsException Thrown if {@code fromIndex} is negative, or {@code toIndex} is negative, or
501 * {@code fromIndex} is larger than {@code toIndex}.
502 * @return {@code this} instance.
503 */
504 public FluentBitSet set(final int fromIndex, final int toIndex, final boolean value) {
505 bitSet.set(fromIndex, toIndex, value);
506 return this;
507 }
508
509 /**
510 * Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (inclusive) to
511 * {@code true}.
512 *
513 * @param fromIndex index of the first bit to be set
514 * @param toIndex index of the last bit to be set
515 * @throws IndexOutOfBoundsException Thrown if {@code fromIndex} is negative, or {@code toIndex} is negative, or {@code fromIndex} is larger than
516 * {@code toIndex}.
517 * @return {@code this} instance.
518 */
519 public FluentBitSet setInclusive(final int fromIndex, final int toIndex) {
520 if (toIndex == Integer.MAX_VALUE) {
521 // toIndex + 1 would overflow to Integer.MIN_VALUE.
522 bitSet.set(fromIndex, toIndex);
523 bitSet.set(toIndex);
524 } else {
525 bitSet.set(fromIndex, toIndex + 1);
526 }
527 return this;
528 }
529
530 /**
531 * Returns the number of bits of space actually in use by this {@link BitSet} to represent bit values. The maximum
532 * element in the set is the size - 1st element.
533 *
534 * @return The number of bits currently in this bit set.
535 */
536 public int size() {
537 return bitSet.size();
538 }
539
540 /**
541 * Returns a stream of indices for which this {@link BitSet} contains a bit in the set state. The indices are returned
542 * in order, from lowest to highest. The size of the stream is the number of bits in the set state, equal to the value
543 * returned by the {@link #cardinality()} method.
544 *
545 * <p>
546 * The bit set must remain constant during the execution of the terminal stream operation. Otherwise, the result of the
547 * terminal stream operation is undefined.
548 * </p>
549 *
550 * @return A stream of integers representing set indices.
551 * @since 1.8
552 */
553 public IntStream stream() {
554 return bitSet.stream();
555 }
556
557 /**
558 * Returns a new byte array containing all the bits in this bit set.
559 *
560 * <p>
561 * More precisely, if:
562 * </p>
563 * <ol>
564 * <li>{@code byte[] bytes = s.toByteArray();}</li>
565 * <li>then {@code bytes.length == (s.length()+7)/8} and</li>
566 * <li>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}</li>
567 * <li>for all {@code n < 8 * bytes.length}.</li>
568 * </ol>
569 *
570 * @return A byte array containing a little-endian representation of all the bits in this bit set
571 */
572 public byte[] toByteArray() {
573 return bitSet.toByteArray();
574 }
575
576 /**
577 * Returns a new byte array containing all the bits in this bit set.
578 *
579 * <p>
580 * More precisely, if:
581 * </p>
582 * <ol>
583 * <li>{@code long[] longs = s.toLongArray();}</li>
584 * <li>then {@code longs.length == (s.length()+63)/64} and</li>
585 * <li>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}</li>
586 * <li>for all {@code n < 64 * longs.length}.</li>
587 * </ol>
588 *
589 * @return A byte array containing a little-endian representation of all the bits in this bit set
590 */
591 public long[] toLongArray() {
592 return bitSet.toLongArray();
593 }
594
595 @Override
596 public String toString() {
597 return bitSet.toString();
598 }
599
600 /**
601 * Performs a logical <strong>XOR</strong> of this bit set with the bit set argument. This bit set is modified so that a bit in it
602 * has the value {@code true} if and only if one of the following statements holds:
603 * <ul>
604 * <li>The bit initially has the value {@code true}, and the corresponding bit in the argument has the value
605 * {@code false}.</li>
606 * <li>The bit initially has the value {@code false}, and the corresponding bit in the argument has the value
607 * {@code true}.</li>
608 * </ul>
609 *
610 * @param set A bit set
611 * @return {@code this} instance.
612 */
613 public FluentBitSet xor(final BitSet set) {
614 bitSet.xor(set);
615 return this;
616 }
617
618 /**
619 * Performs a logical <strong>XOR</strong> of this bit set with the bit set argument. This bit set is modified so that a bit in it
620 * has the value {@code true} if and only if one of the following statements holds:
621 * <ul>
622 * <li>The bit initially has the value {@code true}, and the corresponding bit in the argument has the value
623 * {@code false}.</li>
624 * <li>The bit initially has the value {@code false}, and the corresponding bit in the argument has the value
625 * {@code true}.</li>
626 * </ul>
627 *
628 * @param set A bit set
629 * @return {@code this} instance.
630 */
631 public FluentBitSet xor(final FluentBitSet set) {
632 bitSet.xor(set.bitSet);
633 return this;
634 }
635
636 }