dx/util/Bits.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.util;

/**
 * Utilities for treating {@code int[]}s as bit sets.
 */
public final class Bits {
    /**
     * This class is uninstantiable.
     */
    private Bits() {
        // This space intentionally left blank.
    }

    /**
     * Constructs a bit set to contain bits up to the given index (exclusive).
     *
     * @param max {@code >= 0;} the maximum bit index (exclusive)
     * @return {@code non-null;} an appropriately-constructed instance
     */
    public static int[] makeBitSet(int max) {
        int size = (max + 0x1f) >> 5;
        return new int[size];
    }

    /**
     * Gets the maximum index (exclusive) for the given bit set.
     *
     * @param bits {@code non-null;} bit set in question
     * @return {@code >= 0;} the maximum index (exclusive) that may be set
     */
    public static int getMax(int[] bits) {
        return bits.length * 0x20;
    }

    /**
     * Gets the value of the bit at the given index.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @param idx {@code >= 0, < getMax(set);} which bit
     * @return the value of the indicated bit
     */
    public static boolean get(int[] bits, int idx) {
        int arrayIdx = idx >> 5;
        int bit = 1 << (idx & 0x1f);
        return (bits[arrayIdx] & bit) != 0;
    }

    /**
     * Sets the given bit to the given value.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @param idx {@code >= 0, < getMax(set);} which bit
     * @param value the new value for the bit
     */
    public static void set(int[] bits, int idx, boolean value) {
        int arrayIdx = idx >> 5;
        int bit = 1 << (idx & 0x1f);

        if (value) {
            bits[arrayIdx] |= bit;
        } else {
            bits[arrayIdx] &= ~bit;
        }
    }

    /**
     * Sets the given bit to {@code true}.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @param idx {@code >= 0, < getMax(set);} which bit
     */
    public static void set(int[] bits, int idx) {
        int arrayIdx = idx >> 5;
        int bit = 1 << (idx & 0x1f);
        bits[arrayIdx] |= bit;
    }

    /**
     * Sets the given bit to {@code false}.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @param idx {@code >= 0, < getMax(set);} which bit
     */
    public static void clear(int[] bits, int idx) {
        int arrayIdx = idx >> 5;
        int bit = 1 << (idx & 0x1f);
        bits[arrayIdx] &= ~bit;
    }

    /**
     * Returns whether or not the given bit set is empty, that is, whether
     * no bit is set to {@code true}.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @return {@code true} iff all bits are {@code false}
     */
    public static boolean isEmpty(int[] bits) {
        int len = bits.length;

        for (int i = 0; i < len; i++) {
            if (bits[i] != 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * Gets the number of bits set to {@code true} in the given bit set.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @return {@code >= 0;} the bit count (aka population count) of the set
     */
    public static int bitCount(int[] bits) {
        int len = bits.length;
        int count = 0;

        for (int i = 0; i < len; i++) {
            count += Integer.bitCount(bits[i]);
        }

        return count;
    }

    /**
     * Returns whether any bits are set to {@code true} in the
     * specified range.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @param start {@code >= 0;} index of the first bit in the range (inclusive)
     * @param end {@code >= 0;} index of the last bit in the range (exclusive)
     * @return {@code true} if any bit is set to {@code true} in
     * the indicated range
     */
    public static boolean anyInRange(int[] bits, int start, int end) {
        int idx = findFirst(bits, start);
        return (idx >= 0) && (idx < end);
    }

    /**
     * Finds the lowest-order bit set at or after the given index in the
     * given bit set.
     *
     * @param bits {@code non-null;} bit set to operate on
     * @param idx {@code >= 0;} minimum index to return
     * @return {@code >= -1;} lowest-order bit set at or after {@code idx},
     * or {@code -1} if there is no appropriate bit index to return
     */
    public static int findFirst(int[] bits, int idx) {
        int len = bits.length;
        int minBit = idx & 0x1f;

        for (int arrayIdx = idx >> 5; arrayIdx < len; arrayIdx++) {
            int word = bits[arrayIdx];
            if (word != 0) {
                int bitIdx = findFirst(word, minBit);
                if (bitIdx >= 0) {
                    return (arrayIdx << 5) + bitIdx;
                }
            }
            minBit = 0;
        }

        return -1;
    }

    /**
     * Finds the lowest-order bit set at or after the given index in the
     * given {@code int}.
     *
     * @param value the value in question
     * @param idx 0..31 the minimum bit index to return
     * @return {@code >= -1;} lowest-order bit set at or after {@code idx},
     * or {@code -1} if there is no appropriate bit index to return
     */
    public static int findFirst(int value, int idx) {
        value &= ~((1 << idx) - 1); // Mask off too-low bits.
        int result = Integer.numberOfTrailingZeros(value);
        return (result == 32) ? -1 : result;
    }

    /**
     * Ors bit array {@code b} into bit array {@code a}.
     * {@code a.length} must be greater than or equal to
     * {@code b.length}.
     *
     * @param a {@code non-null;} int array to be ored with other argument. This
     * argument is modified.
     * @param b {@code non-null;} int array to be ored into {@code a}. This
     * argument is not modified.
     */
    public static void or(int[] a, int[] b) {
        for (int i = 0; i < b.length; i++) {
            a[i] |= b[i];
        }
    }

    public static String toHuman(int[] bits) {
        StringBuilder sb = new StringBuilder();

        boolean needsComma = false;

        sb.append('{');

        int bitsLength = 32 * bits.length;
        for (int i = 0; i < bitsLength; i++) {
            if (Bits.get(bits, i)) {
                if (needsComma) {
                    sb.append(',');
                }
                needsComma = true;
                sb.append(i);
            }
        }
        sb.append('}');

        return sb.toString();
    }
}