home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1998 July & August / Pcwk78a98.iso / Internet / Javadraw / DATA.Z / BitSet.java < prev    next >
Text File  |  1997-08-30  |  9KB  |  343 lines
  1. /*
  2.  * @(#)BitSet.java    1.26 97/02/28
  3.  * 
  4.  * Copyright (c) 1995, 1996 Sun Microsystems, Inc. All Rights Reserved.
  5.  * 
  6.  * This software is the confidential and proprietary information of Sun
  7.  * Microsystems, Inc. ("Confidential Information").  You shall not
  8.  * disclose such Confidential Information and shall use it only in
  9.  * accordance with the terms of the license agreement you entered into
  10.  * with Sun.
  11.  * 
  12.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
  13.  * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  14.  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  15.  * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
  16.  * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
  17.  * THIS SOFTWARE OR ITS DERIVATIVES.
  18.  * 
  19.  * CopyrightVersion 1.1_beta
  20.  * 
  21.  */
  22.  
  23. package java.util;
  24.  
  25. /**
  26.  * A set of bits. The set automatically grows as more bits are needed. 
  27.  *
  28.  * @version     1.26, 02/28/97
  29.  * @author Arthur van Hoff
  30.  */
  31. public final class BitSet implements Cloneable, java.io.Serializable {
  32.     private final static int BITS_PER_UNIT = 6;
  33.     private final static int MASK = (1<<BITS_PER_UNIT)-1;
  34.     private long bits[];
  35.  
  36.     /**
  37.      * Convert bitIndex to a subscript into the bits[] array.
  38.      */
  39.     private static int subscript(int bitIndex) {
  40.     return bitIndex >> BITS_PER_UNIT;
  41.     }
  42.     /**
  43.      * Convert a subscript into the bits[] array to a (maximum) bitIndex.
  44.      */
  45.     private static int bitIndex(int subscript) {
  46.     return (subscript << BITS_PER_UNIT) + MASK;
  47.     }
  48.  
  49.     private static boolean debugging = (System.getProperty("debug") != null);
  50.  
  51.     /** use serialVersionUID from JDK 1.0.2 for interoperability */
  52.     private static final long serialVersionUID = 7997698588986878753L;
  53.  
  54.     /**
  55.      * Creates an empty set.
  56.      */
  57.     public BitSet() {
  58.     this(1 << BITS_PER_UNIT);
  59.     }
  60.  
  61.     /**
  62.      * Creates an empty set with the specified size.
  63.      * @param nbits the size of the set
  64.      */
  65.     public BitSet(int nbits) {
  66.     /* nbits can't be negative; size 0 is OK */
  67.     if (nbits < 0) {
  68.         throw new NegativeArraySizeException(Integer.toString(nbits));
  69.     }
  70.     /* On wraparound, truncate size; almost certain to o-flo memory. */
  71.     if (nbits + MASK < 0) {
  72.         nbits = Integer.MAX_VALUE - MASK;
  73.     }
  74.     /* subscript(nbits + MASK) is the length of the array needed to hold nbits */
  75.     bits = new long[subscript(nbits + MASK)];
  76.     }
  77.  
  78.     /**
  79.      * Ensures that the BitSet can hold at least an nth bit.
  80.      * This cannot leave the bits array at length 0.
  81.      * @param    nth    the 0-origin number of the bit to ensure is there.
  82.      */
  83.     private void ensureCapacity(int nth) {
  84.     /* Doesn't need to be synchronized because it's an internal method. */
  85.     int required = subscript(nth) + 1;    /* +1 to get length, not index */
  86.     if (required > bits.length) {
  87.         /* Ask for larger of doubled size or required size */
  88.         int request = Math.max(2 * bits.length, required);
  89.         long newBits[] = new long[request];
  90.         System.arraycopy(bits, 0, newBits, 0, bits.length);
  91.         bits = newBits;
  92.     }
  93.     }
  94.  
  95.     /**
  96.      * Sets a bit.
  97.      * @param bit the bit to be set
  98.      */
  99.     public void set(int bit) {
  100.     if (bit < 0) {
  101.         throw new IndexOutOfBoundsException(Integer.toString(bit));
  102.     }
  103.     synchronized (this) {
  104.         ensureCapacity(bit);
  105.         bits[subscript(bit)] |= (1L << (bit & MASK));
  106.     }
  107.     }
  108.  
  109.     /**
  110.      * Clears a bit.
  111.      * @param bit the bit to be cleared
  112.      */
  113.     public void clear(int bit) {
  114.     if (bit < 0) {
  115.         throw new IndexOutOfBoundsException(Integer.toString(bit));
  116.     }
  117.     synchronized (this) {
  118.         ensureCapacity(bit);
  119.         bits[subscript(bit)] &= ~(1L << (bit & MASK));
  120.     }
  121.     }
  122.  
  123.     /**
  124.      * Gets a bit.
  125.      * @param bit the bit to be gotten
  126.      */
  127.     public boolean get(int bit) {
  128.     if (bit < 0) {
  129.         throw new IndexOutOfBoundsException(Integer.toString(bit));
  130.     }
  131.     boolean result = false;
  132.     synchronized (this) {
  133.         int n = subscript(bit);        /* always positive */
  134.         if (n < bits.length) {
  135.         result = ((bits[n] & (1L << (bit & MASK))) != 0);
  136.         }
  137.     }
  138.     return result;
  139.     }
  140.  
  141.     /**
  142.      * Logically ANDs this bit set with the specified set of bits.
  143.      * @param set the bit set to be ANDed with
  144.      */
  145.     public void and(BitSet set) {
  146.     /*
  147.      * Need to synchronize  both this and set.
  148.      * This might lead to deadlock if one thread grabs them in one order
  149.      * while another thread grabs them the other order.
  150.      * Use a trick from Doug Lea's book on concurrency,
  151.      * somewhat complicated because BitSet overrides hashCode().
  152.      */
  153.     if (this == set) {
  154.         return;
  155.     }
  156.     BitSet first = this;
  157.     BitSet second = set;
  158.     if (System.identityHashCode(first) > System.identityHashCode(second)) {
  159.         first = set;
  160.         second = this;
  161.     }
  162.     synchronized (first) {
  163.         synchronized (second) {
  164.         int bitsLength = bits.length;
  165.         int setLength = set.bits.length;
  166.         int n = Math.min(bitsLength, setLength);
  167.         for (int i = n ; i-- > 0 ; ) {
  168.             bits[i] &= set.bits[i];
  169.         }
  170.         for (; n < bitsLength ; n++) {
  171.             bits[n] = 0;
  172.         }
  173.         }
  174.     }
  175.     }
  176.  
  177.     /**
  178.      * Logically ORs this bit set with the specified set of bits.
  179.      * @param set the bit set to be ORed with
  180.      */
  181.     public void or(BitSet set) {
  182.     if (this == set) {
  183.         return;
  184.     }
  185.     /* See the note about synchronization in and(), above. */
  186.     BitSet first = this;
  187.     BitSet second = set;
  188.     if (System.identityHashCode(first) > System.identityHashCode(second)) {
  189.         first = set;
  190.         second = this;
  191.     }
  192.     synchronized (first) {
  193.         synchronized (second) {
  194.         int setLength = set.bits.length;
  195.         if (setLength > 0) {
  196.             ensureCapacity(bitIndex(setLength-1));
  197.         }
  198.         for (int i = setLength; i-- > 0 ;) {
  199.             bits[i] |= set.bits[i];
  200.         }
  201.         }
  202.     }
  203.     }
  204.  
  205.     /**
  206.      * Logically XORs this bit set with the specified set of bits.
  207.      * @param set the bit set to be XORed with
  208.      */
  209.     public void xor(BitSet set) {
  210.     /* See the note about synchronization in and(), above. */
  211.     BitSet first = this;
  212.     BitSet second = set;
  213.     if (System.identityHashCode(first) > System.identityHashCode(second)) {
  214.         first = set;
  215.         second = this;
  216.     }
  217.     synchronized (first) {
  218.         synchronized (second) {
  219.         int setLength = set.bits.length;
  220.         if (setLength > 0) {
  221.             ensureCapacity(bitIndex(setLength-1));
  222.         }
  223.         for (int i = setLength; i-- > 0 ;) {
  224.             bits[i] ^= set.bits[i];
  225.         }
  226.         }
  227.     }
  228.     }
  229.  
  230.     /**
  231.      * Gets the hashcode.
  232.      */
  233.     public int hashCode() {
  234.     long h = 1234;
  235.     synchronized (this) {
  236.         for (int i = bits.length; --i >= 0; ) {
  237.         h ^= bits[i] * (i + 1);
  238.         }
  239.     }
  240.     return (int)((h >> 32) ^ h);
  241.     }
  242.     
  243.     /**
  244.      * Calculates and returns the set's size in bits.
  245.      * The maximum element in the set is the size - 1st element.
  246.      */
  247.     public int size() {
  248.     /* This doesn't need to be synchronized, since it just reads a field. */
  249.     return bits.length << BITS_PER_UNIT;
  250.     }
  251.  
  252.     /**
  253.      * Compares this object against the specified object.
  254.      * @param obj the object to compare with
  255.      * @return true if the objects are the same; false otherwise.
  256.      */
  257.     public boolean equals(Object obj) {
  258.     if ((obj != null) && (obj instanceof BitSet)) {
  259.         if (this == obj) {
  260.         return true;
  261.         }
  262.         BitSet set = (BitSet) obj;
  263.         /* See the note about synchronization in and(), above. */
  264.         BitSet first = this;
  265.         BitSet second = set;
  266.         if (System.identityHashCode(first) > System.identityHashCode(second)) {
  267.         first = set;
  268.         second = this;
  269.         }
  270.         synchronized (first) {
  271.         synchronized (second) {
  272.             int bitsLength = bits.length;
  273.             int setLength = set.bits.length;
  274.             int n = Math.min(bitsLength, setLength);
  275.             for (int i = n ; i-- > 0 ;) {
  276.             if (bits[i] != set.bits[i]) {
  277.                 return false;
  278.             }
  279.             }
  280.             if (bitsLength > n) {
  281.             for (int i = bitsLength ; i-- > n ;) {
  282.                 if (bits[i] != 0) {
  283.                 return false;
  284.                 }
  285.             }
  286.             } else if (setLength > n) {
  287.             for (int i = setLength ; i-- > n ;) {
  288.                 if (set.bits[i] != 0) {
  289.                 return false;
  290.                 }
  291.             }
  292.             }
  293.         }
  294.         }
  295.         return true;
  296.     }
  297.     return false;
  298.     }
  299.  
  300.     /**
  301.      * Clones the BitSet.
  302.      */
  303.     public Object clone() {
  304.     BitSet result = null;
  305.     synchronized (this) {
  306.         try {
  307.         result = (BitSet) super.clone();
  308.         } catch (CloneNotSupportedException e) {
  309.         // this shouldn't happen, since we are Cloneable
  310.         throw new InternalError();
  311.         }
  312.         result.bits = new long[bits.length];
  313.         System.arraycopy(bits, 0, result.bits, 0, result.bits.length);
  314.     }
  315.     return result;
  316.     }
  317.  
  318.     /**
  319.      * Converts the BitSet to a String.
  320.      */
  321.     public String toString() {
  322.     StringBuffer buffer = new StringBuffer();
  323.     boolean needSeparator = false;
  324.     buffer.append('{');
  325.     synchronized (this) {
  326.         int limit = size();
  327.         for (int i = 0 ; i < limit ; i++) {
  328.         if (get(i)) {
  329.             if (needSeparator) {
  330.             buffer.append(", ");
  331.             } else {
  332.             needSeparator = true;
  333.             }
  334.             buffer.append(i);
  335.         }
  336.         }
  337.     }
  338.     buffer.append('}');
  339.     return buffer.toString();
  340.     }
  341. }
  342.  
  343.