/*
 * Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code 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.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code 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 in the LICENSE file that
 * accompanied this code).
 *
 * 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package com.sun.tools.javac.util;

import java.util.Arrays;

A class for extensible, mutable bit sets.
 
This is NOT part of any supported API.
 If you write code that depends on this, you do so at your own risk.
 This code and its internal interfaces are subject to change or
 deletion without notice.
/** A class for extensible, mutable bit sets.
 *
 *  <p><b>This is NOT part of any supported API.
 *  If you write code that depends on this, you do so at your own risk.
 *  This code and its internal interfaces are subject to change or
 *  deletion without notice.</b>
 */
public class Bits {

    //       ____________      reset    _________
    //      /  UNKNOWN   \   <-------- / UNINIT  \
    //      \____________/       |     \_________/
    //            |              |          |
    //            |assign        |          | any
    //            |        ___________      |
    //            ------> /  NORMAL   \ <----
    //                    \___________/     |
    //                            |         |
    //                            |         |
    //                            -----------
    //                               any
    protected enum BitsState {
        /*  A Bits instance is in UNKNOWN state if it has been explicitly reset.
         *  It is possible to get to this state from any other by calling the
         *  reset method. An instance in the UNKNOWN state can pass to the
         *  NORMAL state after being assigned another Bits instance.
         *
         *  Bits instances are final fields in Flow so the UNKNOWN state models
         *  the null assignment.
         */
        UNKNOWN,
        /*  A Bits instance is in UNINIT when it is created with the default
         *  constructor but it isn't explicitly reset. The main objective of this
         *  internal state is to save some memory.
         */
        UNINIT,
        /*  The normal state is reached after creating a Bits instance from an
         *  existing one or after applying any operation to an instance on UNINIT
         *  or NORMAL state. From this state a bits instance can pass to the
         *  UNKNOWN state by calling the reset method.
         */
        NORMAL;

        static BitsState getState(int[] someBits, boolean reset) {
            if (reset) {
                return UNKNOWN;
            } else {
                if (someBits != unassignedBits) {
                    return NORMAL;
                } else {
                    return UNINIT;
                }
            }
        }

    }

    private final static int wordlen = 32;
    private final static int wordshift = 5;
    private final static int wordmask = wordlen - 1;

    public int[] bits = null;
    // This field will store last version of bits after every change.
    private static final int[] unassignedBits = new int[0];

    protected BitsState currentState;

    
Construct an initially empty set.
/** Construct an initially empty set.
     */
    public Bits() {
        this(false);
    }

    public Bits(Bits someBits) {
        this(someBits.dup().bits, BitsState.getState(someBits.bits, false));
    }

    public Bits(boolean reset) {
        this(unassignedBits, BitsState.getState(unassignedBits, reset));
    }

    
Construct a set consisting initially of given bit vector.
/** Construct a set consisting initially of given bit vector.
     */
    protected Bits(int[] bits, BitsState initState) {
        this.bits = bits;
        this.currentState = initState;
        switch (initState) {
            case UNKNOWN:
                this.bits = null;
                break;
            case NORMAL:
                Assert.check(bits != unassignedBits);
                break;
        }
    }

    protected void sizeTo(int len) {
        if (bits.length < len) {
            bits = Arrays.copyOf(bits, len);
        }
    }

    
This set = {}.
/** This set = {}.
     */
    public void clear() {
        Assert.check(currentState != BitsState.UNKNOWN);
        for (int i = 0; i < bits.length; i++) {
            bits[i] = 0;
        }
        currentState = BitsState.NORMAL;
    }

    public void reset() {
        internalReset();
    }

    protected void internalReset() {
        bits = null;
        currentState = BitsState.UNKNOWN;
    }

    public boolean isReset() {
        return currentState == BitsState.UNKNOWN;
    }

    public Bits assign(Bits someBits) {
        bits = someBits.dup().bits;
        currentState = BitsState.NORMAL;
        return this;
    }

    
Return a copy of this set.
/** Return a copy of this set.
     */
    public Bits dup() {
        Assert.check(currentState != BitsState.UNKNOWN);
        Bits tmp = new Bits();
        tmp.bits = dupBits();
        currentState = BitsState.NORMAL;
        return tmp;
    }

    protected int[] dupBits() {
        int [] result;
        if (currentState != BitsState.NORMAL) {
            result = bits;
        } else {
            result = new int[bits.length];
            System.arraycopy(bits, 0, result, 0, bits.length);
        }
        return result;
    }

    
Include x in this set.
/** Include x in this set.
     */
    public void incl(int x) {
        Assert.check(currentState != BitsState.UNKNOWN);
        Assert.check(x >= 0);
        sizeTo((x >>> wordshift) + 1);
        bits[x >>> wordshift] = bits[x >>> wordshift] |
            (1 << (x & wordmask));
        currentState = BitsState.NORMAL;
    }


    
Include [start..limit) in this set.
/** Include [start..limit) in this set.
     */
    public void inclRange(int start, int limit) {
        Assert.check(currentState != BitsState.UNKNOWN);
        sizeTo((limit >>> wordshift) + 1);
        for (int x = start; x < limit; x++) {
            bits[x >>> wordshift] = bits[x >>> wordshift] |
                (1 << (x & wordmask));
        }
        currentState = BitsState.NORMAL;
    }

    
Exclude [start...end] from this set.
/** Exclude [start...end] from this set.
     */
    public void excludeFrom(int start) {
        Assert.check(currentState != BitsState.UNKNOWN);
        Bits temp = new Bits();
        temp.sizeTo(bits.length);
        temp.inclRange(0, start);
        internalAndSet(temp);
        currentState = BitsState.NORMAL;
    }

    
Exclude x from this set.
/** Exclude x from this set.
     */
    public void excl(int x) {
        Assert.check(currentState != BitsState.UNKNOWN);
        Assert.check(x >= 0);
        sizeTo((x >>> wordshift) + 1);
        bits[x >>> wordshift] = bits[x >>> wordshift] &
            ~(1 << (x & wordmask));
        currentState = BitsState.NORMAL;
    }

    
Is x an element of this set?
/** Is x an element of this set?
     */
    public boolean isMember(int x) {
        Assert.check(currentState != BitsState.UNKNOWN);
        return
            0 <= x && x < (bits.length << wordshift) &&
            (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
    }

    
this set = this set & xs. /** {@literal this set = this set & xs}.
     */
    public Bits andSet(Bits xs) {
        Assert.check(currentState != BitsState.UNKNOWN);
        internalAndSet(xs);
        currentState = BitsState.NORMAL;
        return this;
    }

    protected void internalAndSet(Bits xs) {
        Assert.check(currentState != BitsState.UNKNOWN);
        sizeTo(xs.bits.length);
        for (int i = 0; i < xs.bits.length; i++) {
            bits[i] = bits[i] & xs.bits[i];
        }
    }

    
this set = this set | xs.
/** this set = this set | xs.
     */
    public Bits orSet(Bits xs) {
        Assert.check(currentState != BitsState.UNKNOWN);
        sizeTo(xs.bits.length);
        for (int i = 0; i < xs.bits.length; i++) {
            bits[i] = bits[i] | xs.bits[i];
        }
        currentState = BitsState.NORMAL;
        return this;
    }

    
this set = this set \ xs.
/** this set = this set \ xs.
     */
    public Bits diffSet(Bits xs) {
        Assert.check(currentState != BitsState.UNKNOWN);
        for (int i = 0; i < bits.length; i++) {
            if (i < xs.bits.length) {
                bits[i] = bits[i] & ~xs.bits[i];
            }
        }
        currentState = BitsState.NORMAL;
        return this;
    }

    
this set = this set ^ xs.
/** this set = this set ^ xs.
     */
    public Bits xorSet(Bits xs) {
        Assert.check(currentState != BitsState.UNKNOWN);
        sizeTo(xs.bits.length);
        for (int i = 0; i < xs.bits.length; i++) {
            bits[i] = bits[i] ^ xs.bits[i];
        }
        currentState = BitsState.NORMAL;
        return this;
    }

    
Count trailing zero bits in an int. Algorithm from "Hacker's
 Delight" by Henry S. Warren Jr. (figure 5-13)
/** 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.check(wordlen == 32);
        if (x == 0) {
            return 32;
        }
        int n = 1;
        if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
        if ((x & 0x00ff) == 0) { n +=  8; x >>>=  8; }
        if ((x & 0x000f) == 0) { n +=  4; x >>>=  4; }
        if ((x & 0x0003) == 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:
 

 for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
 
/** Return the index of the least bit position &ge; 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>{@code
     *  for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
     *  }</pre>
     */
    public int nextBit(int x) {
        Assert.check(currentState != BitsState.UNKNOWN);
        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.
/** a string representation of this set.
     */
    @Override
    public String toString() {
        if (bits != null && bits.length > 0) {
            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);
        } else {
            return "[]";
        }
    }

}