duke@1: /*
vromero@1713:  * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
duke@1:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1:  *
duke@1:  * This code is free software; you can redistribute it and/or modify it
duke@1:  * under the terms of the GNU General Public License version 2 only, as
ohair@554:  * published by the Free Software Foundation.  Oracle designates this
duke@1:  * particular file as subject to the "Classpath" exception as provided
ohair@554:  * by Oracle in the LICENSE file that accompanied this code.
duke@1:  *
duke@1:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@1:  * version 2 for more details (a copy is included in the LICENSE file that
duke@1:  * accompanied this code).
duke@1:  *
duke@1:  * You should have received a copy of the GNU General Public License version
duke@1:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@1:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1:  *
ohair@554:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554:  * or visit www.oracle.com if you need additional information or have any
ohair@554:  * questions.
duke@1:  */
duke@1: 
duke@1: package com.sun.tools.javac.util;
duke@1: 
jjg@1339: import java.util.Arrays;
jjg@1339: 
vromero@1713: import static com.sun.tools.javac.util.Bits.BitsOpKind.*;
vromero@1713: 
duke@1: /** A class for extensible, mutable bit sets.
duke@1:  *
jjg@581:  *  <p><b>This is NOT part of any supported API.
jjg@581:  *  If you write code that depends on this, you do so at your own risk.
duke@1:  *  This code and its internal interfaces are subject to change or
duke@1:  *  deletion without notice.</b>
duke@1:  */
duke@1: public class Bits {
duke@1: 
vromero@1713:     public enum BitsOpKind {
vromero@1713:         INIT,
vromero@1713:         CLEAR,
vromero@1713:         INCL_BIT,
vromero@1713:         EXCL_BIT,
vromero@1713:         ASSIGN,
vromero@1713:         AND_SET,
vromero@1713:         OR_SET,
vromero@1713:         DIFF_SET,
vromero@1713:         XOR_SET,
vromero@1713:         INCL_RANGE,
vromero@1713:         EXCL_RANGE,
vromero@1713:     }
vromero@1713: 
vromero@1713:     //       ____________      reset    _________
vromero@1713:     //      /  UNKNOWN   \   <-------- / UNINIT  \
vromero@1713:     //      \____________/       |     \_________/
vromero@1713:     //            |              |          |
vromero@1713:     //            |assign        |          | any
vromero@1713:     //            |        ___________      |
vromero@1713:     //            ------> /  NORMAL   \ <----
vromero@1713:     //                    \___________/     |
vromero@1713:     //                            |         |
vromero@1713:     //                            |         |
vromero@1713:     //                            -----------
vromero@1713:     //                               any
vromero@1713:     private enum BitsState {
vromero@1713:         /*  A Bits instance is in UNKNOWN state if it has been explicitly reset.
vromero@1713:          *  It is possible to get to this state from any other by calling the
vromero@1713:          *  reset method. An instance in the UNKNOWN state can pass to the
vromero@1713:          *  NORMAL state after being assigned another Bits instance.
vromero@1713:          */
vromero@1713:         UNKNOWN,
vromero@1713:         /*  A Bits instance is in UNINIT when it is created with the default
vromero@1713:          *  constructor but it isn't explicitly reset. The main objective of this
vromero@1713:          *  internal state is to save some memory.
vromero@1713:          */
vromero@1713:         UNINIT,
vromero@1713:         /*  The normal state is reached after creating a Bits instance from an
vromero@1713:          *  existing one or after applying any operation to an instance on UNINIT
vromero@1713:          *  or NORMAL state. From this state a bits instance can pass to the
vromero@1713:          *  UNKNOWN state by calling the reset method.
vromero@1713:          */
vromero@1713:         NORMAL;
vromero@1713: 
vromero@1713:         static BitsState getState(int[] someBits, boolean reset) {
vromero@1713:             if (reset) {
vromero@1713:                 return UNKNOWN;
vromero@1713:             } else {
vromero@1713:                 if (someBits != unassignedBits) {
vromero@1713:                     return NORMAL;
vromero@1713:                 } else {
vromero@1713:                     return UNINIT;
vromero@1713:                 }
vromero@1713:             }
vromero@1713:         }
vromero@1713: 
vromero@1713:     }
duke@1: 
duke@1:     private final static int wordlen = 32;
duke@1:     private final static int wordshift = 5;
duke@1:     private final static int wordmask = wordlen - 1;
duke@1: 
vromero@1713:     public int[] bits = null;
vromero@1713:     // This field will store last version of bits after every change.
vromero@1713:     public int[] oldBits = null;
vromero@1713: 
vromero@1713:     public BitsOpKind lastOperation = null;
vromero@1713: 
vromero@1713:     private static final int[] unassignedBits = new int[0];
vromero@1713: 
vromero@1713:     private BitsState currentState;
duke@1: 
duke@1:     /** Construct an initially empty set.
duke@1:      */
duke@1:     public Bits() {
vromero@1713:         this(false);
vromero@1713:     }
vromero@1713: 
vromero@1713:     public Bits(Bits someBits) {
vromero@1713:         this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
vromero@1713:     }
vromero@1713: 
vromero@1713:     public Bits(boolean reset) {
vromero@1713:         this(unassignedBits, BitsState.getState(unassignedBits, reset));
duke@1:     }
duke@1: 
duke@1:     /** Construct a set consisting initially of given bit vector.
duke@1:      */
vromero@1713:     private Bits(int[] bits, BitsState initState) {
duke@1:         this.bits = bits;
vromero@1713:         this.currentState = initState;
vromero@1713:         switch (initState) {
vromero@1713:             case UNKNOWN:
vromero@1713:                 reset(); //this will also set current state;
vromero@1713:                 break;
vromero@1713:             case NORMAL:
vromero@1713:                 Assert.check(bits != unassignedBits);
vromero@1713:                 lastOperation = INIT;
vromero@1713:                 break;
vromero@1713:         }
duke@1:     }
duke@1: 
vromero@1713:     /** This method will be called after any operation that causes a change to
vromero@1713:      *  the bits. Subclasses can thus override it in order to extract information
vromero@1713:      *  from the changes produced to the bits by the given operation.
duke@1:      */
vromero@1713:     public void changed() {}
duke@1: 
duke@1:     private void sizeTo(int len) {
duke@1:         if (bits.length < len) {
jjg@1339:             bits = Arrays.copyOf(bits, len);
duke@1:         }
duke@1:     }
duke@1: 
duke@1:     /** This set = {}.
duke@1:      */
duke@1:     public void clear() {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = CLEAR;
duke@1:         for (int i = 0; i < bits.length; i++) bits[i] = 0;
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
vromero@1713:     }
vromero@1713: 
vromero@1713:     public void reset() {
vromero@1713:         bits = null;
vromero@1713:         oldBits = null;
vromero@1713:         currentState = BitsState.UNKNOWN;
vromero@1713:     }
vromero@1713: 
vromero@1713:     public boolean isReset() {
vromero@1713:         return currentState == BitsState.UNKNOWN;
vromero@1713:     }
vromero@1713: 
vromero@1713:     public Bits assign(Bits someBits) {
vromero@1713:         lastOperation = ASSIGN;
vromero@1713:         oldBits = bits;
vromero@1713:         bits = someBits.dup().bits;
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
vromero@1713:         return this;
duke@1:     }
duke@1: 
duke@1:     /** Return a copy of this set.
duke@1:      */
vromero@1713:     private Bits dup() {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         Bits tmp = new Bits();
vromero@1713:         if (currentState != BitsState.NORMAL) {
vromero@1713:             tmp.bits = bits;
vromero@1713:         } else {
vromero@1713:             tmp.bits = new int[bits.length];
vromero@1713:             System.arraycopy(bits, 0, tmp.bits, 0, bits.length);
vromero@1713:         }
vromero@1713:         currentState = BitsState.NORMAL;
vromero@1713:         return tmp;
duke@1:     }
duke@1: 
duke@1:     /** Include x in this set.
duke@1:      */
duke@1:     public void incl(int x) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
jjg@816:         Assert.check(x >= 0);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = INCL_BIT;
duke@1:         sizeTo((x >>> wordshift) + 1);
duke@1:         bits[x >>> wordshift] = bits[x >>> wordshift] |
duke@1:             (1 << (x & wordmask));
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
duke@1:     }
duke@1: 
duke@1: 
duke@1:     /** Include [start..limit) in this set.
duke@1:      */
duke@1:     public void inclRange(int start, int limit) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = INCL_RANGE;
duke@1:         sizeTo((limit >>> wordshift) + 1);
vromero@1713:         for (int x = start; x < limit; x++) {
duke@1:             bits[x >>> wordshift] = bits[x >>> wordshift] |
duke@1:                 (1 << (x & wordmask));
vromero@1713:         }
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
duke@1:     }
duke@1: 
mcimadamore@773:     /** Exclude [start...end] from this set.
mcimadamore@773:      */
mcimadamore@773:     public void excludeFrom(int start) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = EXCL_RANGE;
mcimadamore@773:         Bits temp = new Bits();
mcimadamore@773:         temp.sizeTo(bits.length);
mcimadamore@773:         temp.inclRange(0, start);
vromero@1713:         internalAndSet(temp);
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
mcimadamore@773:     }
mcimadamore@773: 
duke@1:     /** Exclude x from this set.
duke@1:      */
duke@1:     public void excl(int x) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
jjg@816:         Assert.check(x >= 0);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = EXCL_BIT;
duke@1:         sizeTo((x >>> wordshift) + 1);
duke@1:         bits[x >>> wordshift] = bits[x >>> wordshift] &
duke@1:             ~(1 << (x & wordmask));
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
duke@1:     }
duke@1: 
duke@1:     /** Is x an element of this set?
duke@1:      */
duke@1:     public boolean isMember(int x) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
duke@1:         return
duke@1:             0 <= x && x < (bits.length << wordshift) &&
duke@1:             (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
duke@1:     }
duke@1: 
jjg@1326:     /** {@literal this set = this set & xs}.
duke@1:      */
duke@1:     public Bits andSet(Bits xs) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = AND_SET;
vromero@1713:         internalAndSet(xs);
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
vromero@1713:         return this;
vromero@1713:     }
vromero@1713: 
vromero@1713:     private void internalAndSet(Bits xs) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
duke@1:         sizeTo(xs.bits.length);
vromero@1713:         for (int i = 0; i < xs.bits.length; i++) {
duke@1:             bits[i] = bits[i] & xs.bits[i];
vromero@1713:         }
duke@1:     }
duke@1: 
duke@1:     /** this set = this set | xs.
duke@1:      */
duke@1:     public Bits orSet(Bits xs) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = OR_SET;
duke@1:         sizeTo(xs.bits.length);
vromero@1713:         for (int i = 0; i < xs.bits.length; i++) {
duke@1:             bits[i] = bits[i] | xs.bits[i];
vromero@1713:         }
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
duke@1:         return this;
duke@1:     }
duke@1: 
duke@1:     /** this set = this set \ xs.
duke@1:      */
duke@1:     public Bits diffSet(Bits xs) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = DIFF_SET;
duke@1:         for (int i = 0; i < bits.length; i++) {
duke@1:             if (i < xs.bits.length) {
duke@1:                 bits[i] = bits[i] & ~xs.bits[i];
duke@1:             }
duke@1:         }
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
duke@1:         return this;
duke@1:     }
duke@1: 
duke@1:     /** this set = this set ^ xs.
duke@1:      */
duke@1:     public Bits xorSet(Bits xs) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
vromero@1713:         oldBits = bits;
vromero@1713:         lastOperation = XOR_SET;
duke@1:         sizeTo(xs.bits.length);
vromero@1713:         for (int i = 0; i < xs.bits.length; i++) {
duke@1:             bits[i] = bits[i] ^ xs.bits[i];
vromero@1713:         }
vromero@1713:         changed();
vromero@1713:         currentState = BitsState.NORMAL;
duke@1:         return this;
duke@1:     }
duke@1: 
duke@1:     /** Count trailing zero bits in an int. Algorithm from "Hacker's
duke@1:      *  Delight" by Henry S. Warren Jr. (figure 5-13)
duke@1:      */
duke@1:     private static int trailingZeroBits(int x) {
jjg@816:         Assert.check(wordlen == 32);
duke@1:         if (x == 0) return 32;
duke@1:         int n = 1;
duke@1:         if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
duke@1:         if ((x & 0x00ff) == 0) { n +=  8; x >>>=  8; }
duke@1:         if ((x & 0x000f) == 0) { n +=  4; x >>>=  4; }
duke@1:         if ((x & 0x0003) == 0) { n +=  2; x >>>=  2; }
duke@1:         return n - (x&1);
duke@1:     }
duke@1: 
jjg@1326:     /** Return the index of the least bit position &ge; x that is set.
duke@1:      *  If none are set, returns -1.  This provides a nice way to iterate
duke@1:      *  over the members of a bit set:
jjg@1326:      *  <pre>{@code
duke@1:      *  for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
jjg@1326:      *  }</pre>
duke@1:      */
duke@1:     public int nextBit(int x) {
vromero@1713:         Assert.check(currentState != BitsState.UNKNOWN);
duke@1:         int windex = x >>> wordshift;
duke@1:         if (windex >= bits.length) return -1;
duke@1:         int word = bits[windex] & ~((1 << (x & wordmask))-1);
duke@1:         while (true) {
duke@1:             if (word != 0)
duke@1:                 return (windex << wordshift) + trailingZeroBits(word);
duke@1:             windex++;
duke@1:             if (windex >= bits.length) return -1;
duke@1:             word = bits[windex];
duke@1:         }
duke@1:     }
duke@1: 
duke@1:     /** a string representation of this set.
duke@1:      */
duke@1:     public String toString() {
vromero@1713:         if (bits.length > 0) {
vromero@1713:             char[] digits = new char[bits.length * wordlen];
vromero@1713:             for (int i = 0; i < bits.length * wordlen; i++)
vromero@1713:                 digits[i] = isMember(i) ? '1' : '0';
vromero@1713:             return new String(digits);
vromero@1713:         } else {
vromero@1713:             return "[]";
vromero@1713:         }
duke@1:     }
duke@1: 
duke@1:     /** Test Bits.nextBit(int). */
duke@1:     public static void main(String[] args) {
duke@1:         java.util.Random r = new java.util.Random();
duke@1:         Bits bits = new Bits();
duke@1:         for (int i=0; i<125; i++) {
duke@1:             int k;
duke@1:             do {
duke@1:                 k = r.nextInt(250);
duke@1:             } while (bits.isMember(k));
duke@1:             System.out.println("adding " + k);
duke@1:             bits.incl(k);
duke@1:         }
duke@1:         int count = 0;
duke@1:         for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
duke@1:             System.out.println("found " + i);
duke@1:             count ++;
duke@1:         }
duke@1:         if (count != 125) throw new Error();
duke@1:     }
duke@1: }