/** * @(#)Bits.java	1.14 03/01/23 * * Copyright 2003 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */package com.sun.tools.javac.v8.util;/** * A class for extensible, mutable bit sets. */public class Bits {    private static final int wordlen = 32;    private static final int wordshift = 5;    private static final int wordmask = wordlen - 1;    private int[] bits;    /**     * Construct an initially empty set.     */    public Bits() {        this(new int[1]);    }    /**      * Construct a set consisting initially of given bit vector.      */    public Bits(int[] bits) {        super();        this.bits = bits;    }    /**      * Construct a set consisting initially of given range.      */    public Bits(int start, int limit) {        this();        inclRange(start, limit);    }    private void sizeTo(int len) {        if (bits.length < len) {            int[] newbits = new int[len];            System.arraycopy(bits, 0, newbits, 0, bits.length);            bits = newbits;        }    }    /**      * This set = {}.      */    public void clear() {        for (int i = 0; i < bits.length; i++)            bits[i] = 0;    }    /**      * Return a copy of this set.      */    public Bits dup() {        int[] newbits = new int[bits.length];        System.arraycopy(bits, 0, newbits, 0, bits.length);        return new Bits(newbits);    }    /**      * Include x in this set.      */    public void incl(int x) {        assert x >= 0;        sizeTo((x >>> wordshift) + 1);        bits[x >>> wordshift] = bits[x >>> wordshift] | (1 << (x & wordmask));    }    /**      * Include [start..limit) in this set.      */    public void inclRange(int start, int limit) {        sizeTo((limit >>> wordshift) + 1);        for (int x = start; x < limit; x++)            bits[x >>> wordshift] = bits[x >>> wordshift] | (1 << (x & wordmask));    }    /**      * Exclude x from this set.      */    public void excl(int x) {        assert x >= 0;        sizeTo((x >>> wordshift) + 1);        bits[x >>> wordshift] = bits[x >>> wordshift] & ~(1 << (x & wordmask));    }    /**      * Is x an element of this set?      */    public boolean isMember(int x) {        return 0 <= x && x < (bits.length << wordshift) &&                (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;    }    /**      * this set = this set & xs.      */    public Bits andSet(Bits xs) {        sizeTo(xs.bits.length);        for (int i = 0; i < xs.bits.length; i++)            bits[i] = bits[i] & xs.bits[i];        return this;    }    /**      * this set = this set | xs.      */    public Bits orSet(Bits xs) {        sizeTo(xs.bits.length);        for (int i = 0; i < xs.bits.length; i++)            bits[i] = bits[i] | xs.bits[i];        return this;    }    /**      * this set = this set \ xs.      */    public Bits diffSet(Bits xs) {        for (int i = 0; i < bits.length; i++) {            if (i < xs.bits.length) {                bits[i] = bits[i] & ~xs.bits[i];            }        }        return this;    }    /**      * this set = this set ^ xs.      */    public Bits xorSet(Bits xs) {        sizeTo(xs.bits.length);        for (int i = 0; i < xs.bits.length; i++)            bits[i] = bits[i] ^ xs.bits[i];        return this;    }    /**      * Count trailing zero bits in an int. Algorithm from "Hacker's      *  Delight" by Henry S. Warren Jr. (figure 5-13)      */    private static int trailingZeroBits(int x) {        assert wordlen == 32;        if (x == 0)            return 32;        int n = 1;        if ((x & 65535) == 0) {            n += 16;            x >>>= 16;        }        if ((x & 255) == 0) {            n += 8;            x >>>= 8;        }        if ((x & 15) == 0) {            n += 4;            x >>>= 4;        }        if ((x & 3) == 0) {            n += 2;            x >>>= 2;        }        return n - (x & 1);    }    /**      * Return the index of the least bit position >= x that is set.      *  If none are set, returns -1.  This provides a nice way to iterate      *  over the members of a bit set:      *  <pre>      *  for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...      *  </pre>      */    public int nextBit(int x) {        int windex = x >>> wordshift;        if (windex >= bits.length)            return -1;        int word = bits[windex] & ~((1 << (x & wordmask)) - 1);        while (true) {            if (word != 0)                return (windex << wordshift) + trailingZeroBits(word);            windex++;            if (windex >= bits.length)                return -1;            word = bits[windex];        }    }    /**      * a string representation of this set.      */    public String toString() {        char[] digits = new char[bits.length * wordlen];        for (int i = 0; i < bits.length * wordlen; i++)            digits[i] = isMember(i) ? '1' : '0';        return new String(digits);    }    /**      * Test Bits.nextBit(int).      */    public static void main(String[] args) {        java.util.Random r = new java.util.Random();        Bits bits = new Bits();        int dupCount = 0;        for (int i = 0; i < 125; i++) {            int k;            do {                k = r.nextInt(250);            } while (bits.isMember(k))                ;            System.out.println("adding " + k);            bits.incl(k);        }        int count = 0;        for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i + 1)) {            System.out.println("found " + i);            count++;        }        if (count != 125)            throw new Error();    }}