bitset.java

this gcc-g++-3.3.1.tar.gz is a source file of gcc, you can learn more about gcc through this codes f

        int len = Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset);
        System.arraycopy(bits, lo_offset, bs.bits, 0, len);
        if (hi_offset < bits.length)
          bs.bits[hi_offset - lo_offset] &= (1L << to) - 1;
        return bs;
      }

    int len = Math.min(hi_offset, bits.length - 1);
    int reverse = ~lo_bit;
    int i;
    for (i = 0; lo_offset < len; lo_offset++, i++)
      bs.bits[i] = ((bits[lo_offset] >>> lo_bit)
                    | (bits[lo_offset + 1] << reverse));
    if ((to & LONG_MASK) > lo_bit)
      bs.bits[i++] = bits[lo_offset] >>> lo_bit;
    if (hi_offset < bits.length)
      bs.bits[i - 1] &= (1L << (to - from)) - 1;
    return bs;
  }

  /**
   * Returns a hash code value for this bit set.  The hash code of
   * two bit sets containing the same integers is identical.  The algorithm
   * used to compute it is as follows:
   *
   * Suppose the bits in the BitSet were to be stored in an array of
   * long integers called <code>bits</code>, in such a manner that
   * bit <code>k</code> is set in the BitSet (for non-negative values
   * of <code>k</code>) if and only if
   *
   * <code>((k/64) &lt; bits.length)
   * && ((bits[k/64] & (1L &lt;&lt; (bit % 64))) != 0)
   * </code>
   *
   * Then the following definition of the hashCode method
   * would be a correct implementation of the actual algorithm:
   *
   * 
<pre>public int hashCode()
{
  long h = 1234;
  for (int i = bits.length-1; i &gt;= 0; i--)
  {
    h ^= bits[i] * (i + 1);
  }

  return (int)((h >> 32) ^ h);
}</pre>
   *
   * Note that the hash code values changes, if the set is changed.
   *
   * @return the hash code value for this bit set.
   */
  public int hashCode()
  {
    long h = 1234;
    for (int i = bits.length; i > 0; )
      h ^= i * bits[--i];
    return (int) ((h >> 32) ^ h);
  }

  /**
   * Returns true if the specified BitSet and this one share at least one
   * common true bit.
   *
   * @param set the set to check for intersection
   * @return true if the sets intersect
   * @throws NullPointerException if set is null
   * @since 1.4
   */
  public boolean intersects(BitSet set)
  {
    int i = Math.min(bits.length, set.bits.length);
    while (--i >= 0)
      if ((bits[i] & set.bits[i]) != 0)
        return true;
    return false;
  }

  /**
   * Returns true if this set contains no true bits.
   *
   * @return true if all bits are false
   * @since 1.4
   */
  public boolean isEmpty()
  {
    for (int i = bits.length - 1; i >= 0; i--)
      if (bits[i] != 0)
        return false;
    return true;
  }

  /**
   * Returns the logical number of bits actually used by this bit
   * set.  It returns the index of the highest set bit plus one.
   * Note that this method doesn't return the number of set bits.
   *
   * @return the index of the highest set bit plus one.
   */
  public int length()
  {
    // Set i to highest index that contains a non-zero value.
    int i;
    for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i)
      ;

    // if i < 0 all bits are cleared.
    if (i < 0)
      return 0;

    // Now determine the exact length.
    long b = bits[i];
    int len = (i + 1) * 64;
    // b >= 0 checks if the highest bit is zero.
    while (b >= 0)
      {
        --len;
        b <<= 1;
      }

    return len;
  }

  /**
   * Returns the index of the next false bit, from the specified bit
   * (inclusive).
   *
   * @param from the start location
   * @return the first false bit
   * @throws IndexOutOfBoundsException if from is negative
   * @since 1.4
   */
  public int nextClearBit(int from)
  {
    int offset = from >> 6;
    long mask = 1L << from;
    while (offset < bits.length)
      {
        // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
        // so we'll just let that be our exception.
        long h = bits[offset];
        do
          {
            if ((h & mask) == 0)
              return from;
            mask <<= 1;
            from++;
          }
        while (mask != 0);
        mask = 1;
        offset++;
      }
    return from;
  }

  /**
   * Returns the index of the next true bit, from the specified bit
   * (inclusive). If there is none, -1 is returned. You can iterate over
   * all true bits with this loop:<br>
   * 
<pre>for (int i = bs.nextSetBit(0); i &gt;= 0; i = bs.nextSetBit(i + 1))
{
  // operate on i here
}</pre>
   *
   * @param from the start location
   * @return the first true bit, or -1
   * @throws IndexOutOfBoundsException if from is negative
   * @since 1.4
   */
  public int nextSetBit(int from)
  {
    int offset = from >> 6;
    long mask = 1L << from;
    while (offset < bits.length)
      {
        // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
        // so we'll just let that be our exception.
        long h = bits[offset];
        do
          {
            if ((h & mask) != 0)
              return from;
            mask <<= 1;
            from++;
          }
        while (mask != 0);
        mask = 1;
        offset++;
      }
    return -1;
  }

  /**
   * Performs the logical OR operation on this bit set and the
   * given <code>set</code>.  This means it builds the union
   * of the two sets.  The result is stored into this bit set, which
   * grows as necessary.
   *
   * @param bs the second bit set
   * @throws NullPointerException if bs is null
   */
  public void or(BitSet bs)
  {
    ensure(bs.bits.length - 1);
    for (int i = bs.bits.length - 1; i >= 0; i--)
      bits[i] |= bs.bits[i];
  }

  /**
   * Add the integer <code>bitIndex</code> to this set.  That is
   * the corresponding bit is set to true.  If the index was already in
   * the set, this method does nothing.  The size of this structure
   * is automatically increased as necessary.
   *
   * @param pos a non-negative integer.
   * @throws IndexOutOfBoundsException if pos is negative
   */
  public void set(int pos)
  {
    int offset = pos >> 6;
    ensure(offset);
    // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
    // so we'll just let that be our exception.
    bits[offset] |= 1L << pos;
  }

  /**
   * Sets the bit at the given index to the specified value. The size of
   * this structure is automatically increased as necessary.
   *
   * @param index the position to set
   * @param value the value to set it to
   * @throws IndexOutOfBoundsException if index is negative
   * @since 1.4
   */
  public void set(int index, boolean value)
  {
    if (value)
      set(index);
    else
      clear(index);
  }

  /**
   * Sets the bits between from (inclusive) and to (exclusive) to true.
   *
   * @param from the start range (inclusive)
   * @param to the end range (exclusive)
   * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to
   * @since 1.4
   */
  public void set(int from, int to)
  {
    if (from < 0 || from > to)
      throw new IndexOutOfBoundsException();
    if (from == to)
      return;
    int lo_offset = from >>> 6;
    int hi_offset = to >>> 6;
    ensure(hi_offset);
    if (lo_offset == hi_offset)
      {
        bits[hi_offset] |= (-1L << from) & ((1L << to) - 1);
        return;
      }

    bits[lo_offset] |= -1L << from;
    bits[hi_offset] |= (1L << to) - 1;
    for (int i = lo_offset + 1; i < hi_offset; i++)
      bits[i] = -1;
  }

  /**
   * Sets the bits between from (inclusive) and to (exclusive) to the
   * specified value.
   *
   * @param from the start range (inclusive)
   * @param to the end range (exclusive)
   * @param value the value to set it to
   * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to
   * @since 1.4
   */
  public void set(int from, int to, boolean value)
  {
    if (value)
      set(from, to);
    else
      clear(from, to);
  }

  /**
   * Returns the number of bits actually used by this bit set.  Note
   * that this method doesn't return the number of set bits, and that
   * future requests for larger bits will make this automatically grow.
   *
   * @return the number of bits currently used.
   */
  public int size()
  {
    return bits.length * 64;
  }

  /**
   * Returns the string representation of this bit set.  This
   * consists of a comma separated list of the integers in this set
   * surrounded by curly braces.  There is a space after each comma.
   * A sample string is thus "{1, 3, 53}".
   * @return the string representation.
   */
  public String toString()
  {
    StringBuffer r = new StringBuffer("{");
    boolean first = true;
    for (int i = 0; i < bits.length; ++i)
      {
        long bit = 1;
        long word = bits[i];
        if (word == 0)
          continue;
        for (int j = 0; j < 64; ++j)
          {
            if ((word & bit) != 0)
              {
                if (! first)
                  r.append(", ");
                r.append(64 * i + j);
                first = false;
              }
            bit <<= 1;
          }
      }
    return r.append("}").toString();
  }

  /**
   * Performs the logical XOR operation on this bit set and the
   * given <code>set</code>.  This means it builds the symmetric
   * remainder of the two sets (the elements that are in one set,
   * but not in the other).  The result is stored into this bit set,
   * which grows as necessary.
   *
   * @param bs the second bit set
   * @throws NullPointerException if bs is null
   */
  public void xor(BitSet bs)
  {
    ensure(bs.bits.length - 1);
    for (int i = bs.bits.length - 1; i >= 0; i--)
      bits[i] ^= bs.bits[i];
  }

  /**
   * Make sure the vector is big enough.
   *
   * @param lastElt the size needed for the bits array
   */
  private final void ensure(int lastElt)
  {
    if (lastElt >= bits.length)
      {
        long[] nd = new long[lastElt + 1];
        System.arraycopy(bits, 0, nd, 0, bits.length);
        bits = nd;
      }
  }
}