/*
 * Copyright (C) 2011 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 libcore.java.util;

import java.nio.ByteBuffer;
import java.nio.LongBuffer;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Random;

public class BitSetTest extends junit.framework.TestCase {
    public void test_toString() throws Exception {
        // From the RI javadoc.
        BitSet bs = new BitSet();
        assertEquals("{}", bs.toString());
        bs.set(2);
        assertEquals("{2}", bs.toString());
        bs.set(4);
        bs.set(10);
        assertEquals("{2, 4, 10}", bs.toString());
    }

    private static void assertBitSet(BitSet bs, long[] longs, String s) {
        for (int i = 0; i < 64 * longs.length; ++i) {
            assertEquals(bs.toString(), ((longs[i / 64] & (1L << (i % 64))) != 0), bs.get(i));
        }
        int cardinality = 0;
        for (int i = 0; i < longs.length; ++i) {
            cardinality += Long.bitCount(longs[i]);
        }
        if (cardinality != 0) {
            assertFalse(bs.isEmpty());
        } else {
            assertTrue(bs.isEmpty());
        }
        assertEquals(cardinality, bs.cardinality());
        assertEquals(64 * longs.length, bs.size());
        assertEquals(s, bs.toString());
    }

    private static void assertBitSet(long[] longs, String s) {
        // Test BitSet.valueOf(long[]).
        assertBitSet(BitSet.valueOf(longs), longs, s);
        // Test BitSet.valueOf(LongBuffer).
        assertBitSet(BitSet.valueOf(LongBuffer.wrap(longs)), longs, s);
        // Surround 'longs' with junk set bits but exclude them from the LongBuffer.
        long[] paddedLongs = new long[1 + longs.length + 1];
        paddedLongs[0] = paddedLongs[paddedLongs.length - 1] = -1L;
        System.arraycopy(longs, 0, paddedLongs, 1, longs.length);
        assertBitSet(BitSet.valueOf(LongBuffer.wrap(paddedLongs, 1, longs.length)), longs, s);

        // Check that the long[] is copied.
        if (longs.length > 0) {
            BitSet original = BitSet.valueOf(longs);
            longs[0] = ~longs[0];
            assertFalse(BitSet.valueOf(longs).equals(original));
        }
    }

    public void test_valueOf_long() throws Exception {
        assertBitSet(new long[0], "{}");
        assertBitSet(new long[] { 1L }, "{0}");
        assertBitSet(new long[] { 0x111L }, "{0, 4, 8}");
        assertBitSet(new long[] { 0x101L, 0x4000000000000000L }, "{0, 8, 126}");
    }

    private static void assertBitSet(BitSet bs, byte[] bytes, String s) {
        for (int i = 0; i < 8 * bytes.length; ++i) {
            assertEquals(bs.toString(), ((bytes[i / 8] & (1L << (i % 8))) != 0), bs.get(i));
        }
        int cardinality = 0;
        for (int i = 0; i < bytes.length; ++i) {
            cardinality += Integer.bitCount(((int) bytes[i]) & 0xff);
        }
        if (cardinality != 0) {
            assertFalse(bs.isEmpty());
        } else {
            assertTrue(bs.isEmpty());
        }
        assertEquals(cardinality, bs.cardinality());
        assertEquals(roundUp(8 * bytes.length, 64), bs.size());
        assertEquals(s, bs.toString());
    }

    private static int roundUp(int n, int multiple) {
        return (n == 0) ? 0 : ((n + multiple - 1) / multiple) * multiple;
    }

    private static void assertBitSet(byte[] bytes, String s) {
        // Test BitSet.valueOf(byte[]).
        assertBitSet(BitSet.valueOf(bytes), bytes, s);
        // Test BitSet.valueOf(ByteBuffer).
        assertBitSet(BitSet.valueOf(ByteBuffer.wrap(bytes)), bytes, s);
        // Surround 'bytes' with junk set bits but exclude them from the ByteBuffer.
        byte[] paddedBytes = new byte[1 + bytes.length + 1];
        paddedBytes[0] = paddedBytes[paddedBytes.length - 1] = (byte) -1;
        System.arraycopy(bytes, 0, paddedBytes, 1, bytes.length);
        assertBitSet(BitSet.valueOf(ByteBuffer.wrap(paddedBytes, 1, bytes.length)), bytes, s);

        // Check that the byte[] is copied.
        if (bytes.length > 0) {
            BitSet original = BitSet.valueOf(bytes);
            bytes[0] = (byte) ~bytes[0];
            assertFalse(BitSet.valueOf(bytes).equals(original));
        }
    }

    public void test_valueOf_byte() throws Exception {
        // Nothing...
        assertBitSet(new byte[0], "{}");
        // Less than a long...
        assertBitSet(new byte[] { 0x01 }, "{0}");
        assertBitSet(new byte[] { 0x01, 0x11 }, "{0, 8, 12}");
        assertBitSet(new byte[] { 0x01, 0x01, 0x00, 0x00, 0x01 }, "{0, 8, 32}");
        // Exactly one long....
        assertBitSet(new byte[] { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, (byte) 0x80 }, "{0, 63}");
        // One long and a byte left over...
        assertBitSet(new byte[] { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 }, "{0, 64}");
        // Two longs...
        byte[] bytes = new byte[] { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, (byte) 0x80,
                                    0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, (byte) 0x80 };
        assertBitSet(bytes, "{0, 63, 64, 127}");
    }

    public void test_toLongArray() throws Exception {
        assertEquals("[]", Arrays.toString(BitSet.valueOf(new long[0]).toLongArray()));
        assertEquals("[1]", Arrays.toString(BitSet.valueOf(new long[] { 1 }).toLongArray()));
        assertEquals("[1, 2]", Arrays.toString(BitSet.valueOf(new long[] { 1, 2 }).toLongArray()));

        // Check that we're not returning trailing empty space.
        assertEquals("[]", Arrays.toString(new BitSet(128).toLongArray()));
        BitSet bs = new BitSet();
        bs.set(0);
        bs.set(64, 66);
        bs.clear(64, 66);
        assertEquals("[1]", Arrays.toString(bs.toLongArray()));
    }

    public void test_toByteArray() throws Exception {
        assertEquals("[]", Arrays.toString(BitSet.valueOf(new long[0]).toByteArray()));
        assertEquals("[1]", Arrays.toString(BitSet.valueOf(new long[] { 1 }).toByteArray()));
        assertEquals("[-17, -51, -85, -112, 120, 86, 52, 18]",
                Arrays.toString(BitSet.valueOf(new long[] { 0x1234567890abcdefL }).toByteArray()));
        assertEquals("[1, 0, 0, 0, 0, 0, 0, 0, 2]",
                Arrays.toString(BitSet.valueOf(new long[] { 1, 2 }).toByteArray()));
    }

    public void test_previousSetBit() {
        assertEquals(-1, new BitSet().previousSetBit(666));

        BitSet bs;

        bs = new BitSet();
        bs.set(32);
        assertEquals(32, bs.previousSetBit(999));
        assertEquals(32, bs.previousSetBit(33));
        assertEquals(32, bs.previousSetBit(32));
        assertEquals(-1, bs.previousSetBit(31));

        bs = new BitSet();
        bs.set(0);
        bs.set(1);
        bs.set(32);
        bs.set(192);
        bs.set(666);

        assertEquals(666, bs.previousSetBit(999));
        assertEquals(666, bs.previousSetBit(667));
        assertEquals(666, bs.previousSetBit(666));
        assertEquals(192, bs.previousSetBit(665));
        assertEquals(32, bs.previousSetBit(191));
        assertEquals(1, bs.previousSetBit(31));
        assertEquals(0, bs.previousSetBit(0));
        assertEquals(-1, bs.previousSetBit(-1));
    }

    private static BitSet big() {
        BitSet result = new BitSet();
        result.set(1000);
        return result;
    }

    private static BitSet small() {
        BitSet result = new BitSet();
        result.set(10);
        return result;
    }

    public void test_differentSizes() {
        BitSet result = big();
        result.and(small());
        assertEquals("{}", result.toString());
        result = small();
        result.and(big());
        assertEquals("{}", result.toString());

        result = big();
        result.andNot(small());
        assertEquals("{1000}", result.toString());
        result = small();
        result.andNot(big());
        assertEquals("{10}", result.toString());

        assertFalse(big().intersects(small()));
        assertFalse(small().intersects(big()));

        result = big();
        result.or(small());
        assertEquals("{10, 1000}", result.toString());
        result = small();
        result.or(big());
        assertEquals("{10, 1000}", result.toString());

        result = big();
        result.xor(small());
        assertEquals("{10, 1000}", result.toString());
        result = small();
        result.xor(big());
        assertEquals("{10, 1000}", result.toString());
    }

    public void test_stream() {
        final int size = 128;

        // Generate an arbitrary array of bytes.
        byte[] bytes = new byte[size];
        new Random(0).nextBytes(bytes);

        BitSet bs = BitSet.valueOf(bytes);

        assertEquals(bs.cardinality(), bs.stream().count());
        bs.stream().forEach(x -> assertTrue(bs.get(x)));
    }
}