/* Copyright (c) 2001-2019, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


package org.hsqldb.map;

import org.hsqldb.lib.ArrayUtil;

Implementation of a bit map of any size. The map is initialised with
the given size with no bits set. The map is fixed length depending on
the constructor argument.
Static methods to manipulate int, byte and byte[] values as bit maps.
Author:
Fred Toussi (fredt@users dot sourceforge.net)
Version:
2.4.1
Since:
1.8.0/**
 * Implementation of a bit map of any size. The map is initialised with
 * the given size with no bits set. The map is fixed length depending on
 * the constructor argument.
 *
 * Static methods to manipulate int, byte and byte[] values as bit maps.
 *
 * @author Fred Toussi (fredt@users dot sourceforge.net)
 * @version 2.4.1
 * @since 1.8.0
*/
public class BitMap {

    private boolean canChangeSize;
    private int     initialSize;
    private int[]   map;
    private int     limitPos;

    public BitMap(int size, boolean extend) {

        int words = size / Integer.SIZE;

        if (size == 0 || size % Integer.SIZE != 0) {
            words++;
        }

        map           = new int[words];
        canChangeSize = extend;
        limitPos      = size;
        initialSize   = size;
    }

    public BitMap(int[] map) {

        this.map      = map;
        initialSize   = map.length * Integer.SIZE;
        limitPos      = initialSize;
        canChangeSize = false;
    }

    public BitMap duplicate() {

        BitMap newMap = new BitMap((int[]) ArrayUtil.duplicateArray(this.map));

        newMap.canChangeSize = this.canChangeSize;
        newMap.initialSize   = this.initialSize;
        newMap.limitPos      = this.limitPos;

        return newMap;
    }

    public int size() {
        return limitPos;
    }

    public void setSize(int newSize) {

        if (!canChangeSize) {
            throw new UnsupportedOperationException("BitMap");
        }

        ensureCapacity(newSize);

        // if newSize is smaller
        if (limitPos > newSize) {
            unsetRange(newSize, limitPos - newSize);

            limitPos = newSize;
        }
    }

    
Resets to bits not set with original size
/**
     * Resets to bits not set with original size
     */
    public void reset() {

        for (int i = 0; i < map.length; i++) {
            map[i] = 0;
        }

        limitPos = initialSize;
    }

    
Counts the bit positions that are set both in this and the other map.
/**
     * Counts the bit positions that are set both in this and the other map.
     */
    public int countSetMatches(BitMap other) {

        int matchCount = 0;

        for (int i = 0; i < map.length; i++) {
            int matches = this.map[i] & other.map[i];

            if (matches != 0) {
                matchCount += Integer.bitCount(matches);
            }
        }

        return matchCount;
    }

    public int setRange(int pos, int count) {
        return setOrUnsetRange(pos, count, true);
    }

    public int unsetRange(int pos, int count) {
        return setOrUnsetRange(pos, count, false);
    }

    
returns count of bits that change
/**
     * returns count of bits that change
     */
    private int setOrUnsetRange(int pos, int count, boolean set) {

        if (count == 0) {
            return 0;
        }

        ensureCapacity(pos + count);

        int windex    = pos >> 5;
        int windexend = (pos + count - 1) >> 5;
        int mask      = 0xffffffff >>> (pos & 0x1F);
        int maskend   = 0x80000000 >> ((pos + count - 1) & 0x1F);
        int word;
        int setCount;

        if (windex == windexend) {
            mask &= maskend;
        }

        word     = map[windex];
        setCount = Integer.bitCount(word & mask);

        if (set) {
            map[windex] = (word | mask);
        } else {
            mask        = ~mask;
            map[windex] = (word & mask);
        }

        if (windex != windexend) {
            word     = map[windexend];
            setCount += Integer.bitCount(word & maskend);

            if (set) {
                map[windexend] = (word | maskend);
            } else {
                maskend        = ~maskend;
                map[windexend] = (word & maskend);
            }

            for (int i = windex + 1; i < windexend; i++) {
                setCount += Integer.bitCount(map[i]);
                map[i]   = set ? 0xffffffff
                               : 0;
            }
        }

        return set ? count - setCount
                   : setCount;
    }

    public int setValue(int pos, boolean set) {
        return set ? set(pos)
                   : unset(pos);
    }

    
Sets pos and returns old value
/**
     * Sets pos and returns old value
     */
    public int set(int pos) {

        ensureCapacity(pos + 1);

        int windex = pos >> 5;
        int mask   = 0x80000000 >>> (pos & 0x1F);
        int word   = map[windex];
        int result = (word & mask) == 0 ? 0
                                        : 1;

        map[windex] = (word | mask);

        return result;
    }

    
Unsets pos and returns old value
/**
     * Unsets pos and returns old value
     */
    public int unset(int pos) {

        ensureCapacity(pos + 1);

        int windex = pos >> 5;
        int mask   = 0x80000000 >>> (pos & 0x1F);
        int word   = map[windex];
        int result = (word & mask) == 0 ? 0
                                        : 1;

        mask        = ~mask;
        map[windex] = (word & mask);

        return result;
    }

    public int get(int pos) {

        if (pos >= limitPos) {
            throw new ArrayIndexOutOfBoundsException(pos);
        }

        int windex = pos >> 5;
        int word   = map[windex];

        if (word == 0) {
            return 0;
        }

        if (word == -1) {
            return 1;
        }

        int mask = 0x80000000 >>> (pos & 0x1F);

        return (word & mask) == 0 ? 0
                                  : 1;
    }

    public boolean isSet(int pos) {
        return get(pos) == 1;
    }

    
Sets all bits that are set in the other map.
/**
     * Sets all bits that are set in the other map.
     */
    public void set(BitMap other) {

        for (int windex = 0; windex < map.length; windex++) {
            int word = other.map[windex];

            map[windex] |= word;
        }
    }

    public int countSet(int from, int count) {

        int set = 0;

        for (int i = from; i < from + count; i++) {
            if (isSet(i)) {
                set++;
            }
        }

        return set;
    }

    public int countSetBits() {

        int setCount = 0;

        for (int windex = 0; windex < limitPos / Integer.SIZE; windex++) {
            int word = map[windex];

            if (word == 0) {
                continue;
            }

            if (word == -1) {
                setCount += Integer.SIZE;

                continue;
            }

            setCount += Integer.bitCount(word);
        }

        if (limitPos % Integer.SIZE != 0) {
            int maskend = 0x80000000 >> ((limitPos - 1) & 0x1F);
            int word    = map[limitPos / Integer.SIZE] & maskend;

            setCount += Integer.bitCount(word);
        }

        return setCount;
    }

    
Only for word boundary map size
/**
     * Only for word boundary map size
     */
    public int countSetBitsEnd() {

        int count  = 0;
        int windex = (limitPos / Integer.SIZE) - 1;

        for (; windex >= 0; windex--) {
            if (map[windex] == 0xffffffff) {
                count += Integer.SIZE;

                continue;
            }

            int val = countSetBitsEnd(map[windex]);

            count += val;

            break;
        }

        return count;
    }

    public int[] getIntArray() {
        return map;
    }

    public byte[] getBytes() {

        byte[] buf = new byte[(limitPos + 7) / 8];

        if (buf.length == 0) {
            return buf;
        }

        for (int i = 0; ; ) {
            int v = map[i / 4];

            buf[i++] = (byte) (v >>> 24);

            if (i == buf.length) {
                break;
            }

            buf[i++] = (byte) (v >>> 16);

            if (i == buf.length) {
                break;
            }

            buf[i++] = (byte) (v >>> 8);

            if (i == buf.length) {
                break;
            }

            buf[i++] = (byte) v;

            if (i == buf.length) {
                break;
            }
        }

        return buf;
    }

    
Ensures capacity by enlarging the array if necessary.
Sets limitPos if capacity is increased.
/**
     * Ensures capacity by enlarging the array if necessary.
     * Sets limitPos if capacity is increased.
     */
    private void ensureCapacity(int newSize) {

        if (newSize > limitPos) {
            if (!canChangeSize) {
                throw new ArrayStoreException("BitMap extend");
            }
        }

        if (newSize <= map.length * Integer.SIZE) {
            if (newSize > limitPos) {
                limitPos = newSize;
            }

            return;
        }

        int newMapLength = map.length;

        while (newSize > newMapLength * Integer.SIZE) {
            newMapLength *= 2;
        }

        int[] newmap = new int[newMapLength];

        System.arraycopy(map, 0, newmap, 0, map.length);

        map      = newmap;
        limitPos = newSize;
    }

    
count the run of set bits at the low end
/**
     * count the run of set bits at the low end
     */
    public static int countSetBitsEnd(int map) {

        int mask  = 0x01;
        int count = 0;

        for (; count < Integer.SIZE; count++) {
            if ((map & mask) == 0) {
                break;
            }

            map >>= 1;
        }

        return count;
    }

    
count the run of unset bits at the high end
/**
     * count the run of unset bits at the high end
     */
    public static int countUnsetBitsStart(int map) {

        int mask  = 0x80000000;
        int count = 0;

        if (map == 0) {
            return Integer.SIZE;
        }

        for (; count < Integer.SIZE; count++) {
            if ((map & mask) != 0) {
                break;
            }

            mask >>>= 1;
        }

        return count;
    }

    
copy the byte value into the map at given position (0, 24)
/**
     * copy the byte value into the map at given position (0, 24)
     */
    public static int setByte(int map, byte value, int pos) {

        int intValue = (value & 0xff) << (24 - pos);
        int mask     = 0xff000000 >>> pos;

        mask = ~mask;
        map  &= mask;

        return (map | intValue);
    }

    public static int set(int map, int pos) {

        int mask = 0x80000000 >>> pos;

        return (map | mask);
    }

    public static byte set(byte map, int pos) {

        int mask = 0x00000080 >>> pos;

        return (byte) (map | mask);
    }

    public static int unset(int map, int pos) {

        int mask = 0x80000000 >>> pos;

        mask = ~mask;

        return (map & mask);
    }

    public static boolean isSet(int map, int pos) {

        int mask = 0x80000000 >>> pos;

        return (map & mask) == 0 ? false
                                 : true;
    }

    public static boolean isSet(byte map, int pos) {

        int mask = 0x00000080 >>> pos;

        return (map & mask) == 0 ? false
                                 : true;
    }

    public static boolean isSet(byte[] map, int pos) {

        int mask  = 0x00000080 >>> (pos & 0x07);
        int index = pos / 8;

        if (index >= map.length) {
            return false;
        }

        byte b = map[index];

        return (b & mask) == 0 ? false
                               : true;
    }

    public static void unset(byte[] map, int pos) {

        int mask = 0x00000080 >>> (pos & 0x07);

        mask = ~mask;

        int index = pos / 8;

        if (index >= map.length) {
            return;
        }

        byte b = map[index];

        map[index] = (byte) (b & mask);
    }

    public static void set(byte[] map, int pos) {

        int mask  = 0x00000080 >>> (pos & 0x07);
        int index = pos / 8;

        if (index >= map.length) {
            return;
        }

        byte b = map[index];

        map[index] = (byte) (b | mask);
    }

    
AND count bits from source with map contents starting at pos
/**
     * AND count bits from source with map contents starting at pos
     */
    public static void and(byte[] map, int pos, byte source, int count) {

        int shift     = pos & 0x07;
        int mask      = (source & 0xff) >>> shift;
        int innermask = 0xff >> shift;
        int index     = pos / 8;

        if (count < 8) {
            innermask = innermask >>> (8 - count);
            innermask = innermask << (8 - count);
        }

        mask      &= innermask;
        innermask = ~innermask;

        if (index >= map.length) {
            return;
        }

        byte b = map[index];

        map[index] = (byte) (b & innermask);
        b          = (byte) (b & mask);
        map[index] = (byte) (map[index] | b);

        if (shift == 0) {
            return;
        }

        shift = 8 - shift;

        if (count > shift) {
            mask           = ((source & 0xff) << 8) >>> shift;
            innermask      = 0xff00 >>> shift;
            innermask      = ~innermask;
            b              = map[index + 1];
            map[index + 1] = (byte) (b & innermask);
            b              = (byte) (b & mask);
            map[index + 1] = (byte) (map[index + 1] | b);
        }
    }

    
OR count bits from source with map contents starting at pos
/**
     * OR count bits from source with map contents starting at pos
     */
    public static void or(byte[] map, int pos, byte source, int count) {

        int shift = pos & 0x07;
        int mask  = (source & 0xff) >>> shift;
        int index = pos / 8;

        if (index >= map.length) {
            return;
        }

        byte b = (byte) (map[index] | mask);

        map[index] = b;

        if (shift == 0) {
            return;
        }

        shift = 8 - shift;

        if (count > shift) {
            mask           = ((source & 0xff) << 8) >>> shift;
            b              = (byte) (map[index + 1] | mask);
            map[index + 1] = b;
        }
    }

    
overlay count bits from source on map contents starting at pos
/**
     * overlay count bits from source on map contents starting at pos
     */
    public static void overlay(byte[] map, int pos, byte source, int count) {

        int shift     = pos & 0x07;
        int mask      = (source & 0xff) >>> shift;
        int innermask = 0xff >> shift;
        int index     = pos / 8;

        if (count < 8) {
            innermask = innermask >>> (8 - count);
            innermask = innermask << (8 - count);
        }

        mask      &= innermask;
        innermask = ~innermask;

        if (index >= map.length) {
            return;
        }

        byte b = map[index];

        b          = (byte) (b & innermask);
        map[index] = (byte) (b | mask);

        if (shift == 0) {
            return;
        }

        shift = 8 - shift;

        if (count > shift) {
            mask           = ((source & 0xff) << 8) >>> shift;
            innermask      = 0xff00 >>> shift;
            innermask      = ~innermask;
            b              = map[index + 1];
            b              = (byte) (b & innermask);
            map[index + 1] = (byte) (b | mask);
        }
    }

    public static byte[] and(byte[] a, byte[] b) {

        int    length      = a.length > b.length ? a.length
                                                 : b.length;
        int    shortLength = a.length > b.length ? b.length
                                                 : a.length;
        byte[] map         = new byte[length];

        for (int i = 0; i < shortLength; i++) {
            map[i] = (byte) (a[i] & b[i]);
        }

        return map;
    }

    public static byte[] or(byte[] a, byte[] b) {

        int    length      = a.length > b.length ? a.length
                                                 : b.length;
        int    shortLength = a.length > b.length ? b.length
                                                 : a.length;
        byte[] map         = new byte[length];

        if (length != shortLength) {
            byte[] source = a.length > b.length ? a
                                                : b;

            System.arraycopy(source, shortLength, map, shortLength,
                             length - shortLength);
        }

        for (int i = 0; i < shortLength; i++) {
            map[i] = (byte) (a[i] | b[i]);
        }

        return map;
    }

    public static byte[] xor(byte[] a, byte[] b) {

        int    length      = a.length > b.length ? a.length
                                                 : b.length;
        int    shortLength = a.length > b.length ? b.length
                                                 : a.length;
        byte[] map         = new byte[length];

        if (length != shortLength) {
            byte[] source = a.length > b.length ? a
                                                : b;

            System.arraycopy(source, shortLength, map, shortLength,
                             length - shortLength);
        }

        for (int i = 0; i < shortLength; i++) {
            map[i] = (byte) (a[i] ^ b[i]);
        }

        return map;
    }

    public static byte[] not(byte[] a) {

        byte[] map = new byte[a.length];

        for (int i = 0; i < a.length; i++) {
            map[i] = (byte) ~a[i];
        }

        return map;
    }

    public static boolean hasAnyBitSet(byte[] map) {

        for (int i = 0; i < map.length; i++) {
            if (map[i] != 0) {
                return true;
            }
        }

        return false;
    }

    public static byte[] leftShift(byte[] map, int shiftBits) {

        byte[] newMap     = new byte[map.length];
        int    shiftBytes = shiftBits / 8;

        if (shiftBytes >= map.length) {
            return newMap;
        }

        shiftBits = shiftBits % 8;

        if (shiftBits == 0) {
            for (int i = 0, j = shiftBytes; j < map.length; i++, j++) {
                newMap[i] = map[j];
            }
        } else {
            for (int i = 0, j = shiftBytes; j < map.length; i++, j++) {
                int shifted = (map[j] & 0xff) << shiftBits;

                newMap[i] = (byte) shifted;

                if (i > 0) {
                    newMap[i - 1] |= (byte) (shifted >>> 8);
                }
            }
        }

        return newMap;
    }
}