bitset.java

来自「This is a resource based on j2me embedde」· Java 代码 · 共 1,067 行 · 第 1/3 页

/*
 * @(#)BitSet.java	1.53 06/10/10
 *
 * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.  
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
 *   
 * This program 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.   
 *   
 * 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 version 2 for more details (a copy is  
 * included at /legal/license.txt).   
 *   
 * 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 Sun Microsystems, Inc., 4150 Network Circle, Santa  
 * Clara, CA 95054 or visit www.sun.com if you need additional  
 * information or have any questions. 
 *
 */

package java.util;

import java.io.*;

/**
 * This class implements a vector of bits that grows as needed. Each 
 * component of the bit set has a <code>boolean</code> value. The 
 * bits of a <code>BitSet</code> are indexed by nonnegative integers. 
 * Individual indexed bits can be examined, set, or cleared. One 
 * <code>BitSet</code> may be used to modify the contents of another 
 * <code>BitSet</code> 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</code>. 
 * <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</code> will result in a
 * <code>NullPointerException</code>.
 *
 * A <code>BitSet</code> is not safe for multithreaded use without
 * external synchronization.
 *
 * @author  Arthur van Hoff
 * @author  Michael McCloskey
 * @version 1.46, 02/02/00
 * @since   JDK1.0
 */
public class BitSet implements Cloneable, java.io.Serializable {
    /*
     * BitSets are packed into arrays of "units."  Currently a unit is a long,
     * which consists of 64 bits, requiring 6 address bits.  The choice of unit
     * is determined purely by performance concerns.
     */
    private final static int ADDRESS_BITS_PER_UNIT = 6;
    private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
    private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;

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

    /**
     * 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).
     * INVARIANT: The words in bits[] above unitInUse-1 are zero.
     *
     * @serial
     */
    private long bits[];  // this should be called unit[]

    /**
     * The number of units in the logical size of this BitSet.
     * INVARIANT: unitsInUse is nonnegative.
     * INVARIANT: bits[unitsInUse-1] is nonzero unless unitsInUse is zero.
     */
    private transient int unitsInUse = 0;

    /* use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 7997698588986878753L;

    /**
     * Given a bit index return unit index containing it.
     */
    private static int unitIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_UNIT;
    }

    /**
     * Given a bit index, return a unit that masks that bit in its unit.
     */
    private static long bit(int bitIndex) {
        return 1L << (bitIndex & BIT_INDEX_MASK);
    }

    /**
     * Set the field unitsInUse with the logical size in units of the bit
     * set.  WARNING:This function assumes that the number of units actually
     * in use is less than or equal to the current value of unitsInUse!
     */
    private void recalculateUnitsInUse() {
        // Traverse the bitset until a used unit is found
        int i;
        for (i = unitsInUse-1; i >= 0; i--)
	    if(bits[i] != 0)
		break;

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

    /**
     * Creates a new bit set. All bits are initially <code>false</code>.
     */
    public BitSet() {
	this(BITS_PER_UNIT);
    }

    /**
     * Creates a bit set whose initial size is large enough to explicitly
     * represent bits with indices in the range <code>0</code> through
     * <code>nbits-1</code>. All bits are initially <code>false</code>. 
     *
     * @param     nbits   the initial size of the bit set.
     * @exception 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);

	bits = new long[(unitIndex(nbits-1) + 1)];
    }

    /**
     * Ensures that the BitSet can hold enough units.
     * @param	unitsRequired the minimum acceptable number of units.
     */
    private void ensureCapacity(int unitsRequired) {
	if (bits.length < unitsRequired) {
	    // Allocate larger of doubled size or required size
	    int request = Math.max(2 * bits.length, unitsRequired);
	    long newBits[] = new long[request];
	    System.arraycopy(bits, 0, newBits, 0, unitsInUse);
	    bits = newBits;
	}
    }

    /**
     * Sets the bit at the specified index to to the complement of its
     * current value.
     * 
     * @param   bitIndex the index of the bit to flip.
     * @exception 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 unitIndex = unitIndex(bitIndex);
        int unitsRequired = unitIndex+1;

        if (unitsInUse < unitsRequired) {
            ensureCapacity(unitsRequired);
            bits[unitIndex] ^= bit(bitIndex);
            unitsInUse = unitsRequired;
        } else {
            bits[unitIndex] ^= bit(bitIndex);
            if (bits[unitsInUse-1] == 0)
                recalculateUnitsInUse();
        }
    }

    /**
     * Sets each bit from the specified fromIndex(inclusive) to the
     * specified 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.
     * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
     *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
     *            larger than <tt>toIndex</tt>.
     * @since   1.4
     */
    public void flip(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);
        
        // Increase capacity if necessary
        int endUnitIndex = unitIndex(toIndex);
        int unitsRequired = endUnitIndex + 1;

        if (unitsInUse < unitsRequired) {
            ensureCapacity(unitsRequired);
            unitsInUse = unitsRequired;
        }

        int startUnitIndex = unitIndex(fromIndex);
        long bitMask = 0;
        if (startUnitIndex == endUnitIndex) {
            // Case 1: One word
            bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
                      (1L << (fromIndex & BIT_INDEX_MASK));
            bits[startUnitIndex] ^= bitMask;
            if (bits[unitsInUse-1] == 0)
                recalculateUnitsInUse();
            return;
        }
        
        // Case 2: Multiple words
        // Handle first word
        bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
        bits[startUnitIndex] ^= bitMask;

        // Handle intermediate words, if any
        if (endUnitIndex - startUnitIndex > 1) {
            for(int i=startUnitIndex+1; i<endUnitIndex; i++)
                bits[i] ^= WORD_MASK;
        }

        // Handle last word
        bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
        bits[endUnitIndex] ^= bitMask;

        // Check to see if we reduced size
        if (bits[unitsInUse-1] == 0)
            recalculateUnitsInUse();
    }

    /**
     * Returns a long that has all bits that are less significant
     * than the specified index set to 1. All other bits are 0.
     */
    private static long bitsRightOf(int x) {
        return (x==0 ? 0 : WORD_MASK >>> (64-x));
    }

    /**
     * Returns a long that has all the bits that are more significant
     * than or equal to the specified index set to 1. All other bits are 0.
     */
    private static long bitsLeftOf(int x) {
        return WORD_MASK << x;
    }

    /**
     * Sets the bit at the specified index to <code>true</code>.
     *
     * @param     bitIndex   a bit index.
     * @exception 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 unitIndex = unitIndex(bitIndex);
        int unitsRequired = unitIndex + 1;

        if (unitsInUse < unitsRequired) {
            ensureCapacity(unitsRequired);
            bits[unitIndex] |= bit(bitIndex);
            unitsInUse = unitsRequired;
        } else {
            bits[unitIndex] |= bit(bitIndex);
        }            
    }

    /**
     * Sets the bit at the specified index to the specified value.
     *
     * @param     bitIndex   a bit index.
     * @param     value a boolean value to set.
     * @exception 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 fromIndex(inclusive) to the
     * specified toIndex(exclusive) to <code>true</code>.
     *
     * @param     fromIndex   index of the first bit to be set.
     * @param     toIndex index after the last bit to be set.
     * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
     *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
     *            larger than <tt>toIndex</tt>.
     * @since     1.4
     */
    public void set(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);

        // Increase capacity if necessary
        int endUnitIndex = unitIndex(toIndex);
        int unitsRequired = endUnitIndex + 1;

        if (unitsInUse < unitsRequired) {
            ensureCapacity(unitsRequired);
            unitsInUse = unitsRequired;
        }

        int startUnitIndex = unitIndex(fromIndex);
        long bitMask = 0;
        if (startUnitIndex == endUnitIndex) {
            // Case 1: One word
            bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
                      (1L << (fromIndex & BIT_INDEX_MASK));
            bits[startUnitIndex] |= bitMask;
            return;
        }
        
        // Case 2: Multiple words
        // Handle first word
        bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
        bits[startUnitIndex] |= bitMask;

        // Handle intermediate words, if any
        if (endUnitIndex - startUnitIndex > 1) {
            for(int i=startUnitIndex+1; i<endUnitIndex; i++)
                bits[i] |= WORD_MASK;
        }

        // Handle last word
        bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
        bits[endUnitIndex] |= bitMask;