luni/src/test/java/libcore/java/util/BitSetTest.java - platform/libcore - Git at Google

 /*
  * 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)));
     }
 }
	/*
	* 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)));
	}
	}