home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / 3rdParty / jbuilder / unsupported / JDK1.2beta3 / SOURCE / SRC.ZIP / java / util / BitSet.java < prev    next >
Encoding:
Java Source  |  1998-03-20  |  15.3 KB  |  454 lines
  1. /*
  2.  * @(#)BitSet.java    1.32 98/03/18
  3.  *
  4.  * Copyright 1995-1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. import java.io.*;
  18.  
  19. /**
  20.  * This class implements a vector of bits that grows as needed. Each 
  21.  * component of the bit set has a <code>boolean</code> value. The 
  22.  * bits of a <code>BitSet</code> are indexed by nonnegative integers. 
  23.  * Individual indexed bits can be examined, set, or cleared. One 
  24.  * <code>BitSet</code> may be used to modify the contents of another 
  25.  * <code>BitSet</code> through logical AND, logical inclusive OR, and 
  26.  * logical exclusive OR operations.
  27.  * <p>
  28.  * By default, all bits in the set initially have the value 
  29.  * <code>false</code>. 
  30.  * <p>
  31.  * Every bit set has a current size, which is the number of bits 
  32.  * currently in the bit set. 
  33.  *
  34.  * @author  Arthur van Hoff
  35.  * @author  Michael McCloskey
  36.  * @version 1.32, 03/18/98
  37.  * @since   JDK1.0
  38.  */
  39. public final class BitSet implements Cloneable, java.io.Serializable {
  40.     /*
  41.      * BitSets are packed into arrays of "units."  Currently a unit is a long,
  42.      * which consists of 64 bits, requiring 6 address bits.  The choice of unit
  43.      * is determined purely by performance concerns.
  44.      */
  45.     private final static int ADDRESS_BITS_PER_UNIT = 6;
  46.     private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
  47.     private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;
  48.     private long bits[];  // this should be called unit[]
  49.     private transient int unitsInUse; //# of units in logical size
  50.  
  51.     /**
  52.      * Given a bit index return unit index containing it.
  53.      */
  54.     private static int unitIndex(int bitIndex) {
  55.         return bitIndex >> ADDRESS_BITS_PER_UNIT;
  56.     }
  57.  
  58.     /**
  59.      * Given a bit index, return a unit that masks that bit in its unit.
  60.      */
  61.     private static long bit(int bitIndex) {
  62.         return 1L << (bitIndex & BIT_INDEX_MASK);
  63.     }
  64.  
  65.     /**
  66.      * Set the field unitsInUse with the logical size in units of the bit
  67.      * set.  WARNING:This function assumes that the number of units actually
  68.      * in use is less than or equal to the current value of unitsInUse!
  69.      */
  70.     private void recalculateUnitsInUse() {
  71.         /* Traverse the bitset until a used unit is found */
  72.         int i;
  73.         for (i = unitsInUse-1; i >= 0; i--)
  74.         if(bits[i] != 0)
  75.         break; //this unit is in use!
  76.  
  77.         unitsInUse = i+1; //the new logical size
  78.     }
  79.  
  80.     /* use serialVersionUID from JDK 1.0.2 for interoperability */
  81.     private static final long serialVersionUID = 7997698588986878753L;
  82.  
  83.     /**
  84.      * Creates a new bit set. All bits are initially <code>false</code>.
  85.      */
  86.     public BitSet() {
  87.     this(BITS_PER_UNIT);
  88.     }
  89.  
  90.     /**
  91.      * Creates a bit set whose initial size is the specified number of 
  92.      * bits. Enough space is reserved to explicitly represent bits with 
  93.      * indices in the range <code>0</code> through <code>nbits-1</code>. 
  94.      * All bits are initially <code>false</code>. 
  95.      *
  96.      * @param     nbits   the initial size of the bit set.
  97.      * @exception NegativeArraySizeException if the specified initial size
  98.      *               is negative.
  99.      */
  100.     public BitSet(int nbits) {
  101.     /* nbits can't be negative; size 0 is OK */
  102.     if (nbits < 0)
  103.         throw new NegativeArraySizeException(Integer.toString(nbits));
  104.  
  105.     bits = new long[(unitIndex(nbits-1) + 1)];
  106.     }
  107.  
  108.     /**
  109.      * Ensures that the BitSet can hold enough units.
  110.      * @param    unitsRequired the minimum acceptable number of units.
  111.      */
  112.     private void ensureCapacity(int unitsRequired) {
  113.     if (bits.length < unitsRequired) {
  114.         /* Allocate larger of doubled size or required size */
  115.         int request = Math.max(2 * bits.length, unitsRequired);
  116.         long newBits[] = new long[request];
  117.         System.arraycopy(bits, 0, newBits, 0, unitsInUse);
  118.         bits = newBits;
  119.     }
  120.     }
  121.  
  122.     /**
  123.      * The bit with index <code>bitIndex</code> in this <code>BitSet</code> 
  124.      * is changed to the "set" (<code>true</code>) state. If 
  125.      * <code>bitIndex</code> is not smaller than the value that would be 
  126.      * returned by the <a href="#size"><code>size</code></a> method, then 
  127.      * the size of this <code>BitSet</code> is increased to be larger 
  128.      * than <code>bitIndex</code>.
  129.      *
  130.      * @param     bitIndex   a bit index.
  131.      * @exception IndexOutOfBoundsException if the specified index is negative.
  132.      */
  133.     public void set(int bitIndex) {
  134.     if (bitIndex < 0)
  135.         throw new IndexOutOfBoundsException(Integer.toString(bitIndex));
  136.  
  137.         int unitIndex = unitIndex(bitIndex);
  138.         int unitsRequired = unitIndex+1;
  139.  
  140.         if (unitsInUse < unitsRequired) {
  141.             ensureCapacity(unitsRequired);
  142.             bits[unitIndex] |= bit(bitIndex);
  143.             unitsInUse = unitsRequired;
  144.         } else {
  145.             bits[unitIndex] |= bit(bitIndex);
  146.         }            
  147.     }
  148.  
  149.     /**
  150.      * The bit with index <code>bitIndex</code> in this <code>BitSet</code> 
  151.      * is changed to the "clear" (<code>false</code>) state. If 
  152.      * <code>bitIndex</code> is not smaller than the value that would be 
  153.      * returned by the <a href="#size"><code>size</code></a> method, then 
  154.      * the size of this <code>BitSet</code> is increased to be larger 
  155.      * than <code>bitIndex</code>.
  156.      *
  157.      * @param     bitIndex   the index of the bit to be cleared.
  158.      * @exception IndexOutOfBoundsException if the specified index is negative.
  159.      */
  160.     public void clear(int bitIndex) {
  161.     if (bitIndex < 0)
  162.         throw new IndexOutOfBoundsException(Integer.toString(bitIndex));
  163.     int unitIndex = unitIndex(bitIndex);
  164.     if (unitIndex >= unitsInUse)
  165.         return;
  166.  
  167.     bits[unitIndex] &= ~bit(bitIndex);
  168.         if (unitIndex == unitsInUse-1)
  169.             recalculateUnitsInUse();
  170.     }
  171.  
  172.     /**
  173.      * Returns the value of the bit with the specified index. The value 
  174.      * is <code>true</code> if the bit iwth the index <code>bitIndex</code> 
  175.      * is currently set in this <code>BitSet</code>; otherwise, the result 
  176.      * is <code>false</code>.
  177.      *
  178.      * @param     bitIndex   the bit index.
  179.      * @return    the value of the bit with the specified index.
  180.      * @exception IndexOutOfBoundsException if the specified index is negative.
  181.      */
  182.     public boolean get(int bitIndex) {
  183.     if (bitIndex < 0)
  184.         throw new IndexOutOfBoundsException(Integer.toString(bitIndex));
  185.  
  186.     boolean result = false;
  187.     int unitIndex = unitIndex(bitIndex);
  188.     if (unitIndex < unitsInUse)
  189.         result = ((bits[unitIndex] & bit(bitIndex)) != 0);
  190.  
  191.     return result;
  192.     }
  193.  
  194.     /**
  195.      * Performs a logical <b>AND</b> of this target bit set with the 
  196.      * argument bit set. This bit set is modified so that each bit in it 
  197.      * has the value <code>true</code> if and only if it both initially 
  198.      * had the value <code>true</code> and the corresponding bit in the 
  199.      * bit set argument also had the value <code>true</code>. 
  200.      *
  201.      * @param   set   a bit set. 
  202.      */
  203.     public void and(BitSet set) {
  204.     if (this == set)
  205.         return;
  206.  
  207.     // perform logical AND on bits in common
  208.     int oldUnitsInUse = unitsInUse;
  209.         int i;
  210.     unitsInUse = Math.min(unitsInUse,set.unitsInUse);
  211.     for(i=0; i<unitsInUse; i++)
  212.         bits[i] &= set.bits[i];
  213.  
  214.     // clear out units no longer used
  215.     for( ; i < oldUnitsInUse; i++)
  216.         bits[i] = 0;
  217.     }
  218.  
  219.     /**
  220.      * Performs a logical <b>OR</b> of this bit set with the bit set 
  221.      * argument. This bit set is modified so that a bit in it has the 
  222.      * value <code>true</code> if and only if it either already had the 
  223.      * value <code>true</code> or the corresponding bit in the bit set 
  224.      * argument has the value <code>true</code>.
  225.      *
  226.      * @param   set   a bit set.
  227.      */
  228.     public void or(BitSet set) {
  229.     if (this == set)
  230.         return;
  231.  
  232.     ensureCapacity(set.unitsInUse);
  233.  
  234.     // perform logical OR on bits in common
  235.     int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
  236.         int i;
  237.     for(i=0; i<unitsInCommon; i++)
  238.         bits[i] |= set.bits[i];
  239.  
  240.     // copy any remaining bits
  241.     for(; i<set.unitsInUse; i++)
  242.         bits[i] = set.bits[i];
  243.  
  244.         if (unitsInUse < set.unitsInUse)
  245.             unitsInUse = set.unitsInUse;
  246.     }
  247.  
  248.     /**
  249.      * Performs a logical <b>XOR</b> of this bit set with the bit set 
  250.      * argument. This bit set is modified so that a bit in it has the 
  251.      * value <code>true</code> if and only if one of the following 
  252.      * statements holds: 
  253.      * <ul>
  254.      * <li>The bit initially has the value <code>true</code>, and the 
  255.      *     corresponding bit in the argument has the value <code>false</code>.
  256.      * <li>The bit initially has the value <code>false</code>, and the 
  257.      *     corresponding bit in the argument has the value <code>true</code>. 
  258.      * </ul>
  259.      *
  260.      * @param   set   a bit set.
  261.      */
  262.     public void xor(BitSet set) {
  263.         int unitsInCommon;
  264.  
  265.         if (unitsInUse >= set.unitsInUse) {
  266.             unitsInCommon = set.unitsInUse;
  267.         } else {
  268.             unitsInCommon = unitsInUse;
  269.  
  270.             int newUnitsInUse = set.unitsInUse;
  271.             ensureCapacity(newUnitsInUse);
  272.             unitsInUse = newUnitsInUse;
  273.         }
  274.  
  275.     // perform logical XOR on bits in common
  276.         int i;
  277.         for (i=0; i<unitsInCommon; i++)
  278.         bits[i] ^= set.bits[i];
  279.  
  280.     // copy any remaining bits
  281.         for ( ; i<set.unitsInUse; i++)
  282.             bits[i] = set.bits[i];
  283.  
  284.         recalculateUnitsInUse();
  285.     }
  286.  
  287.     /**
  288.      * Returns a hash code value for this bit set. The has code 
  289.      * depends only on which bits have been set within this 
  290.      * <code>BitSet</code>. The algorithm used to compute it may 
  291.      * be described as follows.<p>
  292.      * Suppose the bits in the <code>BitSet</code> were to be stored 
  293.      * in an array of <code>long</code> integers called, say, 
  294.      * <code>bits</code>, in such a manner that bit <code>k</code> is 
  295.      * set in the <code>BitSet</code> (for nonnegative values of 
  296.      * <code>k</code>) if and only if the expression 
  297.      * <pre>((k>>6) < bits.length) && ((bits[k>>6] & (1L << (bit & 0x3F))) != 0)</pre>
  298.      * is true. Then the following definition of the <code>hashCode</code> 
  299.      * method would be a correct implementation of the actual algorithm:
  300.      * <pre>
  301.      * public synchronized int hashCode() {
  302.      *      long h = 1234;
  303.      *      for (int i = bits.length; --i >= 0; ) {
  304.      *           h ^= bits[i] * (i + 1);
  305.      *      }
  306.      *      return (int)((h >> 32) ^ h);
  307.      * }</pre>
  308.      * Note that the hash code values change if the set of bits is altered.
  309.      * <p>Overrides the <code>hashCode</code> method of <code>Object</code>.
  310.      *
  311.      * @return  a hash code value for this bit set.
  312.      */
  313.     public int hashCode() {
  314.     long h = 1234;
  315.     for (int i = bits.length; --i >= 0; )
  316.             h ^= bits[i] * (i + 1);
  317.  
  318.     return (int)((h >> 32) ^ h);
  319.     }
  320.     
  321.     /**
  322.      * Returns the number of bits of space actually in use by this 
  323.      * <code>BitSet</code> to represent bit values. 
  324.      * The maximum element in the set is the size - 1st element.
  325.      *
  326.      * @return  the number of bits currently in this bit set.
  327.      */
  328.     public int size() {
  329.     return bits.length << ADDRESS_BITS_PER_UNIT;
  330.     }
  331.  
  332.     /**
  333.      * Compares this object against the specified object.
  334.      * The result is <code>true</code> if and only if the argument is 
  335.      * not <code>null</code> and is a <code>Bitset</code> object that has 
  336.      * exactly the same set of bits set to <code>true</code> as this bit 
  337.      * set. That is, for every nonnegative <code>int</code> index <code>k</code>, 
  338.      * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
  339.      * must be true. The current sizes of the two bit sets are not compared. 
  340.      * <p>Overrides the <code>equals</code> method of <code>Object</code>.
  341.      * @param   obj   the object to compare with.
  342.      * @return  <code>true</code> if the objects are the same;
  343.      *          <code>false</code> otherwise.
  344.      * @see     java.util.BitSet#size()
  345.      */
  346.     public boolean equals(Object obj) {
  347.     if (obj == null || !(obj instanceof BitSet))
  348.         return false;
  349.     if (this == obj)
  350.         return true;
  351.  
  352.     BitSet set = (BitSet) obj;
  353.     int minUnitsInUse = Math.min(unitsInUse, set.unitsInUse);
  354.  
  355.     // Check units in use by both BitSets
  356.     for (int i = 0; i < minUnitsInUse; i++)
  357.         if (bits[i] != set.bits[i])
  358.         return false;
  359.  
  360.     // Check any units in use by only one BitSet (must be 0 in other)
  361.     if (unitsInUse > minUnitsInUse) {
  362.         for (int i = minUnitsInUse; i<unitsInUse; i++)
  363.         if (bits[i] != 0)
  364.             return false;
  365.     } else {
  366.         for (int i = minUnitsInUse; i<set.unitsInUse; i++)
  367.         if (set.bits[i] != 0)
  368.             return false;
  369.     }
  370.  
  371.     return true;
  372.     }
  373.  
  374.     /**
  375.      * Cloning this <code>BitSet</code> produces a new <code>BitSet</code> 
  376.      * that is equal to it.
  377.      * The clone of the bit set is another bit set that has exactly the 
  378.      * same bits set to <code>true</code> as this bit set and the same 
  379.      * current size. 
  380.      * <p>Overrides the <code>clone</code> method of <code>Object</code>.
  381.      *
  382.      * @return  a clone of this bit set.
  383.      * @see     java.util.BitSet#size()
  384.      */
  385.     public Object clone() {
  386.     BitSet result = null;
  387.     try {
  388.         result = (BitSet) super.clone();
  389.     } catch (CloneNotSupportedException e) {
  390.         throw new InternalError();
  391.     }
  392.     result.bits = new long[bits.length];
  393.     System.arraycopy(bits, 0, result.bits, 0, unitsInUse);
  394.     return result;
  395.     }
  396.  
  397.     /**
  398.      * This override of readObject makes sure unitsInUse is set properly
  399.      * when deserializing a bitset
  400.      *
  401.      */
  402.     private void readObject(java.io.ObjectInputStream in)
  403.         throws IOException, ClassNotFoundException {
  404.         
  405.         in.defaultReadObject();
  406.         //assume maximum length then find real length
  407.         //because recalculateUnitsInUse assumes maintenance
  408.         //or reduction in logical size
  409.         unitsInUse = bits.length;
  410.         recalculateUnitsInUse();
  411.     }
  412.  
  413.     /**
  414.      * Returns a string representation of this bit set. For every index 
  415.      * for which this <code>BitSet</code> contains a bit in the set 
  416.      * state, the decimal representation of that index is included in 
  417.      * the result. Such indeces aer listed in order from lowest to 
  418.      * highest, separated by ",$nbsp;" (a comma and a space) and 
  419.      * surrounded by braces, resulting in the usual mathematical 
  420.      * notation for a set of integers.<p>
  421.      * Overrides the <code>toString</code> method of <code>Object</code>.
  422.      * <p>Example:
  423.      * <pre>
  424.      * BitSet drPepper = new BitSet();</pre>
  425.      * Now <code>drPepper.toString()</code> returns "<code>{}</code>".<p>
  426.      * <pre>
  427.      * drPepper.set(2);</pre>
  428.      * Now <code>drPepper.toString()</code> returns "<code>{2}</code>".<p>
  429.      * <pre>
  430.      * drPepper.set(4);
  431.      * drPepper.set(10);</pre>
  432.      * Now <code>drPepper.toString()</code> returns "<code>{2, 4, 10}</code>".
  433.      *
  434.      * @return  a string representation of this bit set.
  435.      */
  436.     public String toString() {
  437.     int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT;
  438.     StringBuffer buffer = new StringBuffer(8*numBits + 2);
  439.     String separator = "";
  440.     buffer.append('{');
  441.  
  442.     for (int i = 0 ; i < numBits; i++) {
  443.         if (get(i)) {
  444.         buffer.append(separator);
  445.         separator = ", ";
  446.             buffer.append(i);
  447.         }
  448.         }
  449.  
  450.     buffer.append('}');
  451.     return buffer.toString();
  452.     }
  453. }
  454.