/*
 * Copyright (c) 1995, 2014, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package conexp.fx.core.collections;

/*-
 * #%L
 * Concept Explorer FX
 * %%
 * Copyright (C) 2010 - 2023 Francesco Kriegel
 * %%
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 * 
 * This program 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 for more details.
 * 
 * You should have received a copy of the GNU General Public
 * License along with this program.  If not, see
 * <http://www.gnu.org/licenses/gpl-3.0.html>.
 * #L%
 */

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamField;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.nio.LongBuffer;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.PrimitiveIterator;
import java.util.SortedSet;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.Stream;
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.
 *
 * <p>
 * By default, all bits in the set initially have the value {@code false}.
 *
 * <p>
 * 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.
 *
 * <p>
 * Unless otherwise noted, passing a null parameter to any of the methods in a {@code BitSet} will result in a
 * {@code NullPointerException}.
 *
 * <p>
 * A {@code BitSet} is not safe for multithreaded use without external synchronization.
 *
 * @author Arthur van Hoff
 * @author Michael McCloskey
 * @author Martin Buchholz
 * @since JDK1.0
 */
public class BitSetFX extends AbstractSet<Integer> implements SortedSet<Integer>, 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 final static int                 ADDRESS_BITS_PER_WORD  = 6;
  private final static int                 BITS_PER_WORD          = 1 << ADDRESS_BITS_PER_WORD;
  private final static 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).
   */
  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 */
  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 BitSetFX() {
    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 BitSetFX(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 BitSetFX(long[] words) {
    this.words = words;
    this.wordsInUse = words.length;
    checkInvariants();
  }

  /**
   * Returns a new bit set containing all the bits in the given long array.
   *
   * <p>
   * More precisely, <br>
   * {@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} <br>
   * for all {@code n < 64 * longs.length}.
   *
   * <p>
   * 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 BitSetFX valueOf(long[] longs) {
    int n;
    for (n = longs.length; n > 0 && longs[n - 1] == 0; n--);
    return new BitSetFX(Arrays.copyOf(longs, n));
  }

  /**
   * Returns a new bit set containing all the bits in the given long buffer between its position and limit.
   *
   * <p>
   * More precisely, <br>
   * {@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)} <br>
   * for all {@code n < 64 * lb.remaining()}.
   *
   * <p>
   * 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 BitSetFX 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 BitSetFX(words);
  }

  /**
   * Returns a new bit set containing all the bits in the given byte array.
   *
   * <p>
   * More precisely, <br>
   * {@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} <br>
   * for all {@code n <  8 * bytes.length}.
   *
   * <p>
   * 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 BitSetFX valueOf(byte[] bytes) {
    return BitSetFX.valueOf(ByteBuffer.wrap(bytes));
  }

  /**
   * Returns a new bit set containing all the bits in the given byte buffer between its position and limit.
   *
   * <p>
   * More precisely, <br>
   * {@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)} <br>
   * for all {@code n < 8 * bb.remaining()}.
   *
   * <p>
   * 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 BitSetFX 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 BitSetFX(words);
  }

  /**
   * Returns a new byte array containing all the bits in this bit set.
   *
   * <p>
   * More precisely, if <br>
   * {@code byte[] bytes = s.toByteArray();} <br>
   * then {@code bytes.length == (s.length()+7)/8} and <br>
   * {@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} <br>
   * 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.
   *
   * <p>
   * More precisely, if <br>
   * {@code long[] longs = s.toLongArray();} <br>
   * then {@code longs.length == (s.length()+63)/64} and <br>
   * {@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} <br>
   * 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 JDK1.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 JDK1.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 BitSetFX 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 BitSetFX(0);

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

    BitSetFX result = new BitSetFX(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.
   *
   * <p>
   * 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.
   *
   * <p>
   * 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(BitSetFX 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 <b>AND</b> 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(BitSetFX 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 <b>OR</b> 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(BitSetFX 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 <b>XOR</b> 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(BitSetFX 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(BitSetFX 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}.
   *
   * <p>
   * 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 space() {
    return words.length * BITS_PER_WORD;
  }

  public int size() {
    return cardinality();
  }

  /**
   * 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 #space()
   */
  public boolean equals(Object obj) {
    if (!(obj instanceof BitSetFX))
      return false;
    if (this == obj)
      return true;

    BitSetFX set = (BitSetFX) obj;

    trimToSize();
    set.trimToSize();

    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 #space()
   */
  public Object clone() {
    if (!sizeIsSticky)
      trimToSize();

    try {
      BitSetFX result = (BitSetFX) 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 #space()} 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).
   */
  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).
   */
  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 ",&nbsp;" (a comma and a space) and surrounded by braces, resulting in the
   * usual mathematical notation for a set of integers.
   *
   * <p>
   * 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();

    int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse * BITS_PER_WORD;
    StringBuilder b = new StringBuilder(6 * numBits + 2);
    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.
   *
   * <p>
   * The bit set must remain constant during the execution of the terminal stream operation. Otherwise, the result of
   * the terminal stream operation is undefined.
   *
   * @return a stream of integers representing set indices
   * @since 1.8
   */
  public Stream<Integer> stream() {
    return StreamSupport.stream(
        () -> Spliterators
            .spliterator(iterator(), cardinality(), Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED),
        Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED,
        false);
  }

  public Iterator<Integer> iterator() {
    class BitSetIterator implements PrimitiveIterator.OfInt {

      int next = nextSetBit(0);

      @Override
      public boolean hasNext() {
        return next != -1;
      }

      @Override
      public int nextInt() {
        if (next != -1) {
          int ret = next;
          next = nextSetBit(next + 1);
          return ret;
        } else {
          throw new NoSuchElementException();
        }
      }
    }
    return new BitSetIterator();
  }

  public void and(final BitSetFX... sets) {
    and(Arrays.asList(sets));
  }

  public void and(final Collection<BitSetFX> sets) {
    if (sets.isEmpty())
      return;

    final Integer minWordsInUse = sets.stream().map(set -> set.wordsInUse).min(Integer::compare).get();
    while (wordsInUse > minWordsInUse)
      words[--wordsInUse] = 0;

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

    recalculateWordsInUse();
    checkInvariants();
  }

  public BitSetFX(final BitSetFX b) {
    this();
    or(b);
  }

  public BitSetFX(final Collection<? extends Integer> c) {
    this();
    addAll(c);
  }

  public boolean geq(final BitSetFX set) {
    trimToSize();
    set.trimToSize();

    checkInvariants();
    set.checkInvariants();

    if (set.wordsInUse == 0)
      return true;
    if (set.wordsInUse > wordsInUse)
      return false;
    for (int i = set.wordsInUse - 1; i >= 0; i--)
      if ((set.words[i] & words[i]) != set.words[i])
        return false;
    return true;
  }

  public boolean contains(Object o) {
    return get((Integer) o);
  }

  public boolean containsAll(Collection<?> c) {
    if (c instanceof BitSetFX) {
      final BitSetFX other = (BitSetFX) c;
      return this.geq(other);
    } else {
      for (Object o : c)
        if (!get((Integer) o))
          return false;
      return true;
    }
  }

  public boolean add(final Integer e) {
    if (get(e))
      return false;
    set(e);
    return true;
  }

  public boolean addAll(final Collection<? extends Integer> c) {
    if (c instanceof BitSetFX) {
      final int cardinality = cardinality();
      or((BitSetFX) c);
      return cardinality != cardinality();
    } else {
      boolean changed = false;
      for (int e : c)
        changed |= add(e);
      return changed;
    }
  }

  public void addRange(int start, int end) {
    set(start, end);
  }

  public boolean remove(Object o) {
    if (o instanceof Integer) {
      final int e = (Integer) o;
      if (get(e)) {
        clear(e);
        return true;
      }
    }
    return false;
  }

  public boolean removeAll(Collection<?> c) {
    if (c instanceof BitSetFX) {
      final int cardinality = cardinality();
      andNot((BitSetFX) c);
      return cardinality != cardinality();
    } else {
      boolean changed = false;
      for (Object e : c)
        changed |= remove(e);
      return changed;
    }
  }

  @Override
  public boolean retainAll(Collection<?> c) {
    if (c instanceof BitSetFX) {
      final int cardinality = cardinality();
      and((BitSetFX) c);
      return cardinality != cardinality();
    } else {
      boolean changed = false;
      for (int i = nextSetBit(0); i != -1; i = nextSetBit(i))
        if (!c.contains(i)) {
          clear(i);
          changed = true;
        }
      return changed;
    }
  }

  public Comparator<? super Integer> comparator() {
    return Integer::compare;
  }

  public SortedSet<Integer> subSet(Integer fromElement, Integer toElement) {
    return get(fromElement, toElement);
  }

  public SortedSet<Integer> headSet(Integer toElement) {
    return get(0, toElement);
  }

  public SortedSet<Integer> tailSet(Integer fromElement) {
    return get(fromElement, length());
  }

  public Integer first() {
    return nextSetBit(0);
  }

  public Integer last() {
    return length() - 1;
  }

}