Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/sources/formale Sprachen/Java/Openjdk/src/java.base/share/classes/java/security/ (Sun/Oracle ^©) Datei vom 13.11.2022 mit Größe 5 kB

Impressum BitSet.java Sprache: JAVA

/*
* Copyright (c) 1995, 2020, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/

package java.util;

import java.io.*;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.nio.LongBuffer;
import java.util.function.IntConsumer;
import java.util.stream.IntStream;
import java.util.stream.StreamSupport;

/**
* This class implements a vector of bits that grows as needed. Each
* component of the bit set has a {@code boolean} value. The
* bits of a {@code BitSet} are indexed by nonnegative integers.
* Individual indexed bits can be examined, set, or cleared. One
* {@code BitSet} may be used to modify the contents of another
* {@code BitSet} through logical AND, logical inclusive OR, and
* logical exclusive OR operations.
*
* By default, all bits in the set initially have the value
* {@code false}.
*
* Every bit set has a current size, which is the number of bits
* of space currently in use by the bit set. Note that the size is
* related to the implementation of a bit set, so it may change with
* implementation. The length of a bit set relates to logical length
* of a bit set and is defined independently of implementation.
*
* Unless otherwise noted, passing a null parameter to any of the
* methods in a {@code BitSet} will result in a
* {@code NullPointerException}.
*
* A {@code BitSet} is not safe for multithreaded use without
* external synchronization.
*
* @author Arthur van Hoff
* @author Michael McCloskey
* @author Martin Buchholz
* @since 1.0
*/
public class BitSet implements Cloneable, java.io.Serializable {
 /*
 * BitSets are packed into arrays of "words." Currently a word is
 * a long, which consists of 64 bits, requiring 6 address bits.
 * The choice of word size is determined purely by performance concerns.
 */
 private static final int ADDRESS_BITS_PER_WORD = 6;
 private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
 private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1;

 /* Used to shift left or right for a partial word mask */
 private static final long WORD_MASK = 0xffffffffffffffffL;

 /**
 * @serialField bits long[]
 *
 * The bits in this BitSet. The ith bit is stored in bits[i/64] at
 * bit position i % 64 (where bit position 0 refers to the least
 * significant bit and 63 refers to the most significant bit).
 */
 @java.io.Serial
 private static final ObjectStreamField[] serialPersistentFields = {
 new ObjectStreamField("bits", long[].class),
 };

 /**
 * The internal field corresponding to the serialField "bits".
 */
 private long[] words;

 /**
 * The number of words in the logical size of this BitSet.
 */
 private transient int wordsInUse = 0;

 /**
 * Whether the size of "words" is user-specified. If so, we assume
 * the user knows what he's doing and try harder to preserve it.
 */
 private transient boolean sizeIsSticky = false;

 /* use serialVersionUID from JDK 1.0.2 for interoperability */
 @java.io.Serial
 private static final long serialVersionUID = 7997698588986878753L;

 /**
 * Given a bit index, return word index containing it.
 */
 private static int wordIndex(int bitIndex) {
 return bitIndex >> ADDRESS_BITS_PER_WORD;
 }

 /**
 * Every public method must preserve these invariants.
 */
 private void checkInvariants() {
 assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
 assert(wordsInUse >= 0 && wordsInUse <= words.length);
 assert(wordsInUse == words.length || words[wordsInUse] == 0);
 }

 /**
 * Sets the field wordsInUse to the logical size in words of the bit set.
 * WARNING:This method assumes that the number of words actually in use is
 * less than or equal to the current value of wordsInUse!
 */
 private void recalculateWordsInUse() {
 // Traverse the bitset until a used word is found
 int i;
 for (i = wordsInUse-1; i >= 0; i--)
 if (words[i] != 0)
 break;

 wordsInUse = i+1; // The new logical size
 }

 /**
 * Creates a new bit set. All bits are initially {@code false}.
 */
 public BitSet() {
 initWords(BITS_PER_WORD);
 sizeIsSticky = false;
 }

 /**
 * Creates a bit set whose initial size is large enough to explicitly
 * represent bits with indices in the range {@code 0} through
 * {@code nbits-1}. All bits are initially {@code false}.
 *
 * @param nbits the initial size of the bit set
 * @throws NegativeArraySizeException if the specified initial size
 * is negative
 */
 public BitSet(int nbits) {
 // nbits can't be negative; size 0 is OK
 if (nbits < 0)
 throw new NegativeArraySizeException("nbits < 0: " + nbits);

 initWords(nbits);
 sizeIsSticky = true;
 }

 private void initWords(int nbits) {
 words = new long[wordIndex(nbits-1) + 1];
 }

 /**
 * Creates a bit set using words as the internal representation.
 * The last word (if there is one) must be non-zero.
 */
 private BitSet(long[] words) {
 this.words = words;
 this.wordsInUse = words.length;
 checkInvariants();
 }

 /**
 * Returns a new bit set containing all the bits in the given long array.
 *
 * More precisely,
 * {@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
 * for all {@code n < 64 * longs.length}.
 *
 * This method is equivalent to
 * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
 *
 * @param longs a long array containing a little-endian representation
 * of a sequence of bits to be used as the initial bits of the
 * new bit set
 * @return a {@code BitSet} containing all the bits in the long array
 * @since 1.7
 */
 public static BitSet valueOf(long[] longs) {
 int n;
 for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
 ;
 return new BitSet(Arrays.copyOf(longs, n));
 }

 /**
 * Returns a new bit set containing all the bits in the given long
 * buffer between its position and limit.
 *
 * More precisely,
 * {@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
 * for all {@code n < 64 * lb.remaining()}.
 *
 * The long buffer is not modified by this method, and no
 * reference to the buffer is retained by the bit set.
 *
 * @param lb a long buffer containing a little-endian representation
 * of a sequence of bits between its position and limit, to be
 * used as the initial bits of the new bit set
 * @return a {@code BitSet} containing all the bits in the buffer in the
 * specified range
 * @since 1.7
 */
 public static BitSet valueOf(LongBuffer lb) {
 lb = lb.slice();
 int n;
 for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
 ;
 long[] words = new long[n];
 lb.get(words);
 return new BitSet(words);
 }

 /**
 * Returns a new bit set containing all the bits in the given byte array.
 *
 * More precisely,
 * {@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
 * for all {@code n < 8 * bytes.length}.
 *
 * This method is equivalent to
 * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
 *
 * @param bytes a byte array containing a little-endian
 * representation of a sequence of bits to be used as the
 * initial bits of the new bit set
 * @return a {@code BitSet} containing all the bits in the byte array
 * @since 1.7
 */
 public static BitSet valueOf(byte[] bytes) {
 return BitSet.valueOf(ByteBuffer.wrap(bytes));
 }

 /**
 * Returns a new bit set containing all the bits in the given byte
 * buffer between its position and limit.
 *
 * More precisely,
 * {@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
 * for all {@code n < 8 * bb.remaining()}.
 *
 * The byte buffer is not modified by this method, and no
 * reference to the buffer is retained by the bit set.
 *
 * @param bb a byte buffer containing a little-endian representation
 * of a sequence of bits between its position and limit, to be
 * used as the initial bits of the new bit set
 * @return a {@code BitSet} containing all the bits in the buffer in the
 * specified range
 * @since 1.7
 */
 public static BitSet valueOf(ByteBuffer bb) {
 bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
 int n;
 for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
 ;
 long[] words = new long[(n + 7) / 8];
 bb.limit(n);
 int i = 0;
 while (bb.remaining() >= 8)
 words[i++] = bb.getLong();
 for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
 words[i] |= (bb.get() & 0xffL) << (8 * j);
 return new BitSet(words);
 }

 /**
 * Returns a new byte array containing all the bits in this bit set.
 *
 * More precisely, if
 * {@code byte[] bytes = s.toByteArray();}
 * then {@code bytes.length == (s.length()+7)/8} and
 * {@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
 * for all {@code n < 8 * bytes.length}.
 *
 * @return a byte array containing a little-endian representation
 * of all the bits in this bit set
 * @since 1.7
 */
 public byte[] toByteArray() {
 int n = wordsInUse;
 if (n == 0)
 return new byte[0];
 int len = 8 * (n-1);
 for (long x = words[n - 1]; x != 0; x >>>= 8)
 len++;
 byte[] bytes = new byte[len];
 ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
 for (int i = 0; i < n - 1; i++)
 bb.putLong(words[i]);
 for (long x = words[n - 1]; x != 0; x >>>= 8)
 bb.put((byte) (x & 0xff));
 return bytes;
 }

 /**
 * Returns a new long array containing all the bits in this bit set.
 *
 * More precisely, if
 * {@code long[] longs = s.toLongArray();}
 * then {@code longs.length == (s.length()+63)/64} and
 * {@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
 * for all {@code n < 64 * longs.length}.
 *
 * @return a long array containing a little-endian representation
 * of all the bits in this bit set
 * @since 1.7
 */
 public long[] toLongArray() {
 return Arrays.copyOf(words, wordsInUse);
 }

 /**
 * Ensures that the BitSet can hold enough words.
 * @param wordsRequired the minimum acceptable number of words.
 */
 private void ensureCapacity(int wordsRequired) {
 if (words.length < wordsRequired) {
 // Allocate larger of doubled size or required size
 int request = Math.max(2 * words.length, wordsRequired);
 words = Arrays.copyOf(words, request);
 sizeIsSticky = false;
 }
 }

 /**
 * Ensures that the BitSet can accommodate a given wordIndex,
 * temporarily violating the invariants. The caller must
 * restore the invariants before returning to the user,
 * possibly using recalculateWordsInUse().
 * @param wordIndex the index to be accommodated.
 */
 private void expandTo(int wordIndex) {
 int wordsRequired = wordIndex+1;
 if (wordsInUse < wordsRequired) {
 ensureCapacity(wordsRequired);
 wordsInUse = wordsRequired;
 }
 }

 /**
 * Checks that fromIndex ... toIndex is a valid range of bit indices.
 */
 private static void checkRange(int fromIndex, int toIndex) {
 if (fromIndex < 0)
 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
 if (toIndex < 0)
 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
 if (fromIndex > toIndex)
 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
 " > toIndex: " + toIndex);
 }

 /**
 * Sets the bit at the specified index to the complement of its
 * current value.
 *
 * @param bitIndex the index of the bit to flip
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since 1.4
 */
 public void flip(int bitIndex) {
 if (bitIndex < 0)
 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

 int wordIndex = wordIndex(bitIndex);
 expandTo(wordIndex);

 words[wordIndex] ^= (1L << bitIndex);

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Sets each bit from the specified {@code fromIndex} (inclusive) to the
 * specified {@code toIndex} (exclusive) to the complement of its current
 * value.
 *
 * @param fromIndex index of the first bit to flip
 * @param toIndex index after the last bit to flip
 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
 * or {@code toIndex} is negative, or {@code fromIndex} is
 * larger than {@code toIndex}
 * @since 1.4
 */
 public void flip(int fromIndex, int toIndex) {
 checkRange(fromIndex, toIndex);

 if (fromIndex == toIndex)
 return;

 int startWordIndex = wordIndex(fromIndex);
 int endWordIndex = wordIndex(toIndex - 1);
 expandTo(endWordIndex);

 long firstWordMask = WORD_MASK << fromIndex;
 long lastWordMask = WORD_MASK >>> -toIndex;
 if (startWordIndex == endWordIndex) {
 // Case 1: One word
 words[startWordIndex] ^= (firstWordMask & lastWordMask);
 } else {
 // Case 2: Multiple words
 // Handle first word
 words[startWordIndex] ^= firstWordMask;

 // Handle intermediate words, if any
 for (int i = startWordIndex+1; i < endWordIndex; i++)
 words[i] ^= WORD_MASK;

 // Handle last word
 words[endWordIndex] ^= lastWordMask;
 }

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Sets the bit at the specified index to {@code true}.
 *
 * @param bitIndex a bit index
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since 1.0
 */
 public void set(int bitIndex) {
 if (bitIndex < 0)
 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

 int wordIndex = wordIndex(bitIndex);
 expandTo(wordIndex);

 words[wordIndex] |= (1L << bitIndex); // Restores invariants

 checkInvariants();
 }

 /**
 * Sets the bit at the specified index to the specified value.
 *
 * @param bitIndex a bit index
 * @param value a boolean value to set
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since 1.4
 */
 public void set(int bitIndex, boolean value) {
 if (value)
 set(bitIndex);
 else
 clear(bitIndex);
 }

 /**
 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
 * specified {@code toIndex} (exclusive) to {@code true}.
 *
 * @param fromIndex index of the first bit to be set
 * @param toIndex index after the last bit to be set
 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
 * or {@code toIndex} is negative, or {@code fromIndex} is
 * larger than {@code toIndex}
 * @since 1.4
 */
 public void set(int fromIndex, int toIndex) {
 checkRange(fromIndex, toIndex);

 if (fromIndex == toIndex)
 return;

 // Increase capacity if necessary
 int startWordIndex = wordIndex(fromIndex);
 int endWordIndex = wordIndex(toIndex - 1);
 expandTo(endWordIndex);

 long firstWordMask = WORD_MASK << fromIndex;
 long lastWordMask = WORD_MASK >>> -toIndex;
 if (startWordIndex == endWordIndex) {
 // Case 1: One word
 words[startWordIndex] |= (firstWordMask & lastWordMask);
 } else {
 // Case 2: Multiple words
 // Handle first word
 words[startWordIndex] |= firstWordMask;

 // Handle intermediate words, if any
 for (int i = startWordIndex+1; i < endWordIndex; i++)
 words[i] = WORD_MASK;

 // Handle last word (restores invariants)
 words[endWordIndex] |= lastWordMask;
 }

 checkInvariants();
 }

 /**
 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
 * specified {@code toIndex} (exclusive) to the specified value.
 *
 * @param fromIndex index of the first bit to be set
 * @param toIndex index after the last bit to be set
 * @param value value to set the selected bits to
 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
 * or {@code toIndex} is negative, or {@code fromIndex} is
 * larger than {@code toIndex}
 * @since 1.4
 */
 public void set(int fromIndex, int toIndex, boolean value) {
 if (value)
 set(fromIndex, toIndex);
 else
 clear(fromIndex, toIndex);
 }

 /**
 * Sets the bit specified by the index to {@code false}.
 *
 * @param bitIndex the index of the bit to be cleared
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since 1.0
 */
 public void clear(int bitIndex) {
 if (bitIndex < 0)
 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

 int wordIndex = wordIndex(bitIndex);
 if (wordIndex >= wordsInUse)
 return;

 words[wordIndex] &= ~(1L << bitIndex);

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
 * specified {@code toIndex} (exclusive) to {@code false}.
 *
 * @param fromIndex index of the first bit to be cleared
 * @param toIndex index after the last bit to be cleared
 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
 * or {@code toIndex} is negative, or {@code fromIndex} is
 * larger than {@code toIndex}
 * @since 1.4
 */
 public void clear(int fromIndex, int toIndex) {
 checkRange(fromIndex, toIndex);

 if (fromIndex == toIndex)
 return;

 int startWordIndex = wordIndex(fromIndex);
 if (startWordIndex >= wordsInUse)
 return;

 int endWordIndex = wordIndex(toIndex - 1);
 if (endWordIndex >= wordsInUse) {
 toIndex = length();
 endWordIndex = wordsInUse - 1;
 }

 long firstWordMask = WORD_MASK << fromIndex;
 long lastWordMask = WORD_MASK >>> -toIndex;
 if (startWordIndex == endWordIndex) {
 // Case 1: One word
 words[startWordIndex] &= ~(firstWordMask & lastWordMask);
 } else {
 // Case 2: Multiple words
 // Handle first word
 words[startWordIndex] &= ~firstWordMask;

 // Handle intermediate words, if any
 for (int i = startWordIndex+1; i < endWordIndex; i++)
 words[i] = 0;

 // Handle last word
 words[endWordIndex] &= ~lastWordMask;
 }

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Sets all of the bits in this BitSet to {@code false}.
 *
 * @since 1.4
 */
 public void clear() {
 while (wordsInUse > 0)
 words[--wordsInUse] = 0;
 }

 /**
 * Returns the value of the bit with the specified index. The value
 * is {@code true} if the bit with the index {@code bitIndex}
 * is currently set in this {@code BitSet}; otherwise, the result
 * is {@code false}.
 *
 * @param bitIndex the bit index
 * @return the value of the bit with the specified index
 * @throws IndexOutOfBoundsException if the specified index is negative
 */
 public boolean get(int bitIndex) {
 if (bitIndex < 0)
 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

 checkInvariants();

 int wordIndex = wordIndex(bitIndex);
 return (wordIndex < wordsInUse)
 && ((words[wordIndex] & (1L << bitIndex)) != 0);
 }

 /**
 * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
 * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
 *
 * @param fromIndex index of the first bit to include
 * @param toIndex index after the last bit to include
 * @return a new {@code BitSet} from a range of this {@code BitSet}
 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
 * or {@code toIndex} is negative, or {@code fromIndex} is
 * larger than {@code toIndex}
 * @since 1.4
 */
 public BitSet get(int fromIndex, int toIndex) {
 checkRange(fromIndex, toIndex);

 checkInvariants();

 int len = length();

 // If no set bits in range return empty bitset
 if (len <= fromIndex || fromIndex == toIndex)
 return new BitSet(0);

 // An optimization
 if (toIndex > len)
 toIndex = len;

 BitSet result = new BitSet(toIndex - fromIndex);
 int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
 int sourceIndex = wordIndex(fromIndex);
 boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);

 // Process all words but the last word
 for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
 result.words[i] = wordAligned ? words[sourceIndex] :
 (words[sourceIndex] >>> fromIndex) |
 (words[sourceIndex+1] << -fromIndex);

 // Process the last word
 long lastWordMask = WORD_MASK >>> -toIndex;
 result.words[targetWords - 1] =
 ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
 ? /* straddles source words */
 ((words[sourceIndex] >>> fromIndex) |
 (words[sourceIndex+1] & lastWordMask) << -fromIndex)
 :
 ((words[sourceIndex] & lastWordMask) >>> fromIndex);

 // Set wordsInUse correctly
 result.wordsInUse = targetWords;
 result.recalculateWordsInUse();
 result.checkInvariants();

 return result;
 }

 /**
 * Returns the index of the first bit that is set to {@code true}
 * that occurs on or after the specified starting index. If no such
 * bit exists then {@code -1} is returned.
 *
 * To iterate over the {@code true} bits in a {@code BitSet},
 * use the following loop:
 *
 * <pre> {@code
 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
 * // operate on index i here
 * if (i == Integer.MAX_VALUE) {
 * break; // or (i+1) would overflow
 * }
 * }}</pre>
 *
 * @param fromIndex the index to start checking from (inclusive)
 * @return the index of the next set bit, or {@code -1} if there
 * is no such bit
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since 1.4
 */
 public int nextSetBit(int fromIndex) {
 if (fromIndex < 0)
 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

 checkInvariants();

 int u = wordIndex(fromIndex);
 if (u >= wordsInUse)
 return -1;

 long word = words[u] & (WORD_MASK << fromIndex);

 while (true) {
 if (word != 0)
 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
 if (++u == wordsInUse)
 return -1;
 word = words[u];
 }
 }

 /**
 * Returns the index of the first bit that is set to {@code false}
 * that occurs on or after the specified starting index.
 *
 * @param fromIndex the index to start checking from (inclusive)
 * @return the index of the next clear bit
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since 1.4
 */
 public int nextClearBit(int fromIndex) {
 // Neither spec nor implementation handle bitsets of maximal length.
 // See 4816253.
 if (fromIndex < 0)
 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

 checkInvariants();

 int u = wordIndex(fromIndex);
 if (u >= wordsInUse)
 return fromIndex;

 long word = ~words[u] & (WORD_MASK << fromIndex);

 while (true) {
 if (word != 0)
 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
 if (++u == wordsInUse)
 return wordsInUse * BITS_PER_WORD;
 word = ~words[u];
 }
 }

 /**
 * Returns the index of the nearest bit that is set to {@code true}
 * that occurs on or before the specified starting index.
 * If no such bit exists, or if {@code -1} is given as the
 * starting index, then {@code -1} is returned.
 *
 * To iterate over the {@code true} bits in a {@code BitSet},
 * use the following loop:
 *
 * <pre> {@code
 * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
 * // operate on index i here
 * }}</pre>
 *
 * @param fromIndex the index to start checking from (inclusive)
 * @return the index of the previous set bit, or {@code -1} if there
 * is no such bit
 * @throws IndexOutOfBoundsException if the specified index is less
 * than {@code -1}
 * @since 1.7
 */
 public int previousSetBit(int fromIndex) {
 if (fromIndex < 0) {
 if (fromIndex == -1)
 return -1;
 throw new IndexOutOfBoundsException(
 "fromIndex < -1: " + fromIndex);
 }

 checkInvariants();

 int u = wordIndex(fromIndex);
 if (u >= wordsInUse)
 return length() - 1;

 long word = words[u] & (WORD_MASK >>> -(fromIndex+1));

 while (true) {
 if (word != 0)
 return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
 if (u-- == 0)
 return -1;
 word = words[u];
 }
 }

 /**
 * Returns the index of the nearest bit that is set to {@code false}
 * that occurs on or before the specified starting index.
 * If no such bit exists, or if {@code -1} is given as the
 * starting index, then {@code -1} is returned.
 *
 * @param fromIndex the index to start checking from (inclusive)
 * @return the index of the previous clear bit, or {@code -1} if there
 * is no such bit
 * @throws IndexOutOfBoundsException if the specified index is less
 * than {@code -1}
 * @since 1.7
 */
 public int previousClearBit(int fromIndex) {
 if (fromIndex < 0) {
 if (fromIndex == -1)
 return -1;
 throw new IndexOutOfBoundsException(
 "fromIndex < -1: " + fromIndex);
 }

 checkInvariants();

 int u = wordIndex(fromIndex);
 if (u >= wordsInUse)
 return fromIndex;

 long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));

 while (true) {
 if (word != 0)
 return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
 if (u-- == 0)
 return -1;
 word = ~words[u];
 }
 }

 /**
 * Returns the "logical size" of this {@code BitSet}: the index of
 * the highest set bit in the {@code BitSet} plus one. Returns zero
 * if the {@code BitSet} contains no set bits.
 *
 * @return the logical size of this {@code BitSet}
 * @since 1.2
 */
 public int length() {
 if (wordsInUse == 0)
 return 0;

 return BITS_PER_WORD * (wordsInUse - 1) +
 (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
 }

 /**
 * Returns true if this {@code BitSet} contains no bits that are set
 * to {@code true}.
 *
 * @return boolean indicating whether this {@code BitSet} is empty
 * @since 1.4
 */
 public boolean isEmpty() {
 return wordsInUse == 0;
 }

 /**
 * Returns true if the specified {@code BitSet} has any bits set to
 * {@code true} that are also set to {@code true} in this {@code BitSet}.
 *
 * @param set {@code BitSet} to intersect with
 * @return boolean indicating whether this {@code BitSet} intersects
 * the specified {@code BitSet}
 * @since 1.4
 */
 public boolean intersects(BitSet set) {
 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
 if ((words[i] & set.words[i]) != 0)
 return true;
 return false;
 }

 /**
 * Returns the number of bits set to {@code true} in this {@code BitSet}.
 *
 * @return the number of bits set to {@code true} in this {@code BitSet}
 * @since 1.4
 */
 public int cardinality() {
 int sum = 0;
 for (int i = 0; i < wordsInUse; i++)
 sum += Long.bitCount(words[i]);
 return sum;
 }

 /**
 * Performs a logical AND of this target bit set with the
 * argument bit set. This bit set is modified so that each bit in it
 * has the value {@code true} if and only if it both initially
 * had the value {@code true} and the corresponding bit in the
 * bit set argument also had the value {@code true}.
 *
 * @param set a bit set
 */
 public void and(BitSet set) {
 if (this == set)
 return;

 while (wordsInUse > set.wordsInUse)
 words[--wordsInUse] = 0;

 // Perform logical AND on words in common
 for (int i = 0; i < wordsInUse; i++)
 words[i] &= set.words[i];

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Performs a logical OR of this bit set with the bit set
 * argument. This bit set is modified so that a bit in it has the
 * value {@code true} if and only if it either already had the
 * value {@code true} or the corresponding bit in the bit set
 * argument has the value {@code true}.
 *
 * @param set a bit set
 */
 public void or(BitSet set) {
 if (this == set)
 return;

 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

 if (wordsInUse < set.wordsInUse) {
 ensureCapacity(set.wordsInUse);
 wordsInUse = set.wordsInUse;
 }

 // Perform logical OR on words in common
 for (int i = 0; i < wordsInCommon; i++)
 words[i] |= set.words[i];

 // Copy any remaining words
 if (wordsInCommon < set.wordsInUse)
 System.arraycopy(set.words, wordsInCommon,
 words, wordsInCommon,
 wordsInUse - wordsInCommon);

 // recalculateWordsInUse() is unnecessary
 checkInvariants();
 }

 /**
 * Performs a logical XOR of this bit set with the bit set
 * argument. This bit set is modified so that a bit in it has the
 * value {@code true} if and only if one of the following
 * statements holds:
 * <ul>
 * <li>The bit initially has the value {@code true}, and the
 * corresponding bit in the argument has the value {@code false}.
 * <li>The bit initially has the value {@code false}, and the
 * corresponding bit in the argument has the value {@code true}.
 * </ul>
 *
 * @param set a bit set
 */
 public void xor(BitSet set) {
 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

 if (wordsInUse < set.wordsInUse) {
 ensureCapacity(set.wordsInUse);
 wordsInUse = set.wordsInUse;
 }

 // Perform logical XOR on words in common
 for (int i = 0; i < wordsInCommon; i++)
 words[i] ^= set.words[i];

 // Copy any remaining words
 if (wordsInCommon < set.wordsInUse)
 System.arraycopy(set.words, wordsInCommon,
 words, wordsInCommon,
 set.wordsInUse - wordsInCommon);

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Clears all of the bits in this {@code BitSet} whose corresponding
 * bit is set in the specified {@code BitSet}.
 *
 * @param set the {@code BitSet} with which to mask this
 * {@code BitSet}
 * @since 1.2
 */
 public void andNot(BitSet set) {
 // Perform logical (a & !b) on words in common
 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
 words[i] &= ~set.words[i];

 recalculateWordsInUse();
 checkInvariants();
 }

 /**
 * Returns the hash code value for this bit set. The hash code depends
 * only on which bits are set within this {@code BitSet}.
 *
 * The hash code is defined to be the result of the following
 * calculation:
 * <pre> {@code
 * public int hashCode() {
 * long h = 1234;
 * long[] words = toLongArray();
 * for (int i = words.length; --i >= 0; )
 * h ^= words[i] * (i + 1);
 * return (int)((h >> 32) ^ h);
 * }}</pre>
 * Note that the hash code changes if the set of bits is altered.
 *
 * @return the hash code value for this bit set
 */
 public int hashCode() {
 long h = 1234;
 for (int i = wordsInUse; --i >= 0; )
 h ^= words[i] * (i + 1);

 return (int)((h >> 32) ^ h);
 }

 /**
 * Returns the number of bits of space actually in use by this
 * {@code BitSet} to represent bit values.
 * The maximum element in the set is the size - 1st element.
 *
 * @return the number of bits currently in this bit set
 */
 public int size() {
 return words.length * BITS_PER_WORD;
 }

 /**
 * Compares this object against the specified object.
 * The result is {@code true} if and only if the argument is
 * not {@code null} and is a {@code BitSet} object that has
 * exactly the same set of bits set to {@code true} as this bit
 * set. That is, for every nonnegative {@code int} index {@code k},
 * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
 * must be true. The current sizes of the two bit sets are not compared.
 *
 * @param obj the object to compare with
 * @return {@code true} if the objects are the same;
 * {@code false} otherwise
 * @see #size()
 */
 public boolean equals(Object obj) {
 if (!(obj instanceof BitSet set))
 return false;
 if (this == obj)
 return true;

 checkInvariants();
 set.checkInvariants();

 if (wordsInUse != set.wordsInUse)
 return false;

 // Check words in use by both BitSets
 for (int i = 0; i < wordsInUse; i++)
 if (words[i] != set.words[i])
 return false;

 return true;
 }

 /**
 * Cloning this {@code BitSet} produces a new {@code BitSet}
 * that is equal to it.
 * The clone of the bit set is another bit set that has exactly the
 * same bits set to {@code true} as this bit set.
 *
 * @return a clone of this bit set
 * @see #size()
 */
 public Object clone() {
 if (! sizeIsSticky)
 trimToSize();

 try {
 BitSet result = (BitSet) super.clone();
 result.words = words.clone();
 result.checkInvariants();
 return result;
 } catch (CloneNotSupportedException e) {
 throw new InternalError(e);
 }
 }

 /**
 * Attempts to reduce internal storage used for the bits in this bit set.
 * Calling this method may, but is not required to, affect the value
 * returned by a subsequent call to the {@link #size()} method.
 */
 private void trimToSize() {
 if (wordsInUse != words.length) {
 words = Arrays.copyOf(words, wordsInUse);
 checkInvariants();
 }
 }

 /**
 * Save the state of the {@code BitSet} instance to a stream (i.e.,
 * serialize it).
 */
 @java.io.Serial
 private void writeObject(ObjectOutputStream s)
 throws IOException {

 checkInvariants();

 if (! sizeIsSticky)
 trimToSize();

 ObjectOutputStream.PutField fields = s.putFields();
 fields.put("bits", words);
 s.writeFields();
 }

 /**
 * Reconstitute the {@code BitSet} instance from a stream (i.e.,
 * deserialize it).
 */
 @java.io.Serial
 private void readObject(ObjectInputStream s)
 throws IOException, ClassNotFoundException {

 ObjectInputStream.GetField fields = s.readFields();
 words = (long[]) fields.get("bits", null);

 // Assume maximum length then find real length
 // because recalculateWordsInUse assumes maintenance
 // or reduction in logical size
 wordsInUse = words.length;
 recalculateWordsInUse();
 sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
 checkInvariants();
 }

 /**
 * Returns a string representation of this bit set. For every index
 * for which this {@code BitSet} contains a bit in the set
 * state, the decimal representation of that index is included in
 * the result. Such indices are listed in order from lowest to
 * highest, separated by ", " (a comma and a space) and
 * surrounded by braces, resulting in the usual mathematical
 * notation for a set of integers.
 *
 * Example:
 * <pre>
 * BitSet drPepper = new BitSet();</pre>
 * Now {@code drPepper.toString()} returns "{@code {}}".
 * <pre>
 * drPepper.set(2);</pre>
 * Now {@code drPepper.toString()} returns "{@code {2}}".
 * <pre>
 * drPepper.set(4);
 * drPepper.set(10);</pre>
 * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
 *
 * @return a string representation of this bit set
 */
 public String toString() {
 checkInvariants();

 final int MAX_INITIAL_CAPACITY = Integer.MAX_VALUE - 8;
 int numBits = (wordsInUse > 128) ?
 cardinality() : wordsInUse * BITS_PER_WORD;
 // Avoid overflow in the case of a humongous numBits
 int initialCapacity = (numBits <= (MAX_INITIAL_CAPACITY - 2) / 6) ?
 6 * numBits + 2 : MAX_INITIAL_CAPACITY;
 StringBuilder b = new StringBuilder(initialCapacity);
 b.append('{');

 int i = nextSetBit(0);
 if (i != -1) {
 b.append(i);
 while (true) {
 if (++i < 0) break;
 if ((i = nextSetBit(i)) < 0) break;
 int endOfRun = nextClearBit(i);
 do { b.append(", ").append(i); }
 while (++i != endOfRun);
 }
 }

 b.append('}');
 return b.toString();
 }

 /**
 * Returns a stream of indices for which this {@code BitSet}
 * contains a bit in the set state. The indices are returned
 * in order, from lowest to highest. The size of the stream
 * is the number of bits in the set state, equal to the value
 * returned by the {@link #cardinality()} method.
 *
 * The stream binds to this bit set when the terminal stream operation
 * commences (specifically, the spliterator for the stream is
 * <a href="Spliterator.html#binding">late-binding</a>). If the
 * bit set is modified during that operation then the result is undefined.
 *
 * @return a stream of integers representing set indices
 * @since 1.8
 */
 public IntStream stream() {
 class BitSetSpliterator implements Spliterator.OfInt {
 private int index; // current bit index for a set bit
 private int fence; // -1 until used; then one past last bit index
 private int est; // size estimate
 private boolean root; // true if root and not split
 // root == true then size estimate is accurate
 // index == -1 or index >= fence if fully traversed
 // Special case when the max bit set is Integer.MAX_VALUE

 BitSetSpliterator(int origin, int fence, int est, boolean root) {
 this.index = origin;
 this.fence = fence;
 this.est = est;
 this.root = root;
 }

 private int getFence() {
 int hi;
 if ((hi = fence) < 0) {
 // Round up fence to maximum cardinality for allocated words
 // This is sufficient and cheap for sequential access
 // When splitting this value is lowered
 hi = fence = (wordsInUse >= wordIndex(Integer.MAX_VALUE))
 ? Integer.MAX_VALUE
 : wordsInUse << ADDRESS_BITS_PER_WORD;
 est = cardinality();
 index = nextSetBit(0);
 }
 return hi;
 }

 @Override
 public boolean tryAdvance(IntConsumer action) {
 Objects.requireNonNull(action);

 int hi = getFence();
 int i = index;
 if (i < 0 || i >= hi) {
 // Check if there is a final bit set for Integer.MAX_VALUE
 if (i == Integer.MAX_VALUE && hi == Integer.MAX_VALUE) {
 index = -1;
 action.accept(Integer.MAX_VALUE);
 return true;
 }
 return false;
 }

 index = nextSetBit(i + 1, wordIndex(hi - 1));
 action.accept(i);
 return true;
 }

 @Override
 public void forEachRemaining(IntConsumer action) {
 Objects.requireNonNull(action);

 int hi = getFence();
 int i = index;
 index = -1;

 if (i >= 0 && i < hi) {
 action.accept(i++);

 int u = wordIndex(i); // next lower word bound
 int v = wordIndex(hi - 1); // upper word bound

 words_loop:
 for (; u <= v && i <= hi; u++, i = u << ADDRESS_BITS_PER_WORD) {
 long word = words[u] & (WORD_MASK << i);
 while (word != 0) {
 i = (u << ADDRESS_BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
 if (i >= hi) {
 // Break out of outer loop to ensure check of
 // Integer.MAX_VALUE bit set
 break words_loop;
 }

 // Flip the set bit
 word &= ~(1L << i);

 action.accept(i);
 }
 }
 }

 // Check if there is a final bit set for Integer.MAX_VALUE
 if (i == Integer.MAX_VALUE && hi == Integer.MAX_VALUE) {
 action.accept(Integer.MAX_VALUE);
 }
 }

 @Override
 public OfInt trySplit() {
 int hi = getFence();
 int lo = index;
 if (lo < 0) {
 return null;
 }

 // Lower the fence to be the upper bound of last bit set
 // The index is the first bit set, thus this spliterator
 // covers one bit and cannot be split, or two or more
 // bits
 hi = fence = (hi < Integer.MAX_VALUE || !get(Integer.MAX_VALUE))
 ? previousSetBit(hi - 1) + 1
 : Integer.MAX_VALUE;

 // Find the mid point
 int mid = (lo + hi) >>> 1;
 if (lo >= mid) {
 return null;
 }

 // Raise the index of this spliterator to be the next set bit
 // from the mid point
 index = nextSetBit(mid, wordIndex(hi - 1));
 root = false;

 // Don't lower the fence (mid point) of the returned spliterator,
 // traversal or further splitting will do that work
 return new BitSetSpliterator(lo, mid, est >>>= 1, false);
 }

 @Override
 public long estimateSize() {
 getFence(); // force init
 return est;
 }

 @Override
 public int characteristics() {
 // Only sized when root and not split
 return (root ? Spliterator.SIZED : 0) |
 Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED;
 }

 @Override
 public Comparator<? super Integer> getComparator() {
 return null;
 }
 }
 return StreamSupport.intStream(new BitSetSpliterator(0, -1, 0, true), false);
 }

 /**
 * Returns the index of the first bit that is set to {@code true}
 * that occurs on or after the specified starting index and up to and
 * including the specified word index
 * If no such bit exists then {@code -1} is returned.
 *
 * @param fromIndex the index to start checking from (inclusive)
 * @param toWordIndex the last word index to check (inclusive)
 * @return the index of the next set bit, or {@code -1} if there
 * is no such bit
 */
 private int nextSetBit(int fromIndex, int toWordIndex) {
 int u = wordIndex(fromIndex);
 // Check if out of bounds
 if (u > toWordIndex)
 return -1;

 long word = words[u] & (WORD_MASK << fromIndex);

 while (true) {
 if (word != 0)
 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
 // Check if out of bounds
 if (++u > toWordIndex)
 return -1;
 word = words[u];
 }
 }

}

quality92%

¤ Dauer der Verarbeitung: 0.31 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.