1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package libcore.java.util; 18 19import java.nio.ByteBuffer; 20import java.nio.LongBuffer; 21import java.util.Arrays; 22import java.util.BitSet; 23import java.util.Random; 24 25public class BitSetTest extends junit.framework.TestCase { 26 public void test_toString() throws Exception { 27 // From the RI javadoc. 28 BitSet bs = new BitSet(); 29 assertEquals("{}", bs.toString()); 30 bs.set(2); 31 assertEquals("{2}", bs.toString()); 32 bs.set(4); 33 bs.set(10); 34 assertEquals("{2, 4, 10}", bs.toString()); 35 } 36 37 // b/31234459 38 public void test_toString_highestPossibleBitSet() { 39 // 2^28 bytes for the bits in the BitSet, plus extra bytes for everything else 40 int bytesRequired = (1 << 28) + (1 << 27); 41 if (Runtime.getRuntime().maxMemory() < bytesRequired) { 42 return; 43 } 44 try { 45 BitSet bitSet = new BitSet(); 46 bitSet.set(Integer.MAX_VALUE); 47 assertEquals("{2147483647}", bitSet.toString()); 48 } catch (OutOfMemoryError e) { 49 // ignore 50 } 51 } 52 53 private static void assertBitSet(BitSet bs, long[] longs, String s) { 54 for (int i = 0; i < 64 * longs.length; ++i) { 55 assertEquals(bs.toString(), ((longs[i / 64] & (1L << (i % 64))) != 0), bs.get(i)); 56 } 57 int cardinality = 0; 58 for (int i = 0; i < longs.length; ++i) { 59 cardinality += Long.bitCount(longs[i]); 60 } 61 if (cardinality != 0) { 62 assertFalse(bs.isEmpty()); 63 } else { 64 assertTrue(bs.isEmpty()); 65 } 66 assertEquals(cardinality, bs.cardinality()); 67 assertEquals(64 * longs.length, bs.size()); 68 assertEquals(s, bs.toString()); 69 } 70 71 private static void assertBitSet(long[] longs, String s) { 72 // Test BitSet.valueOf(long[]). 73 assertBitSet(BitSet.valueOf(longs), longs, s); 74 // Test BitSet.valueOf(LongBuffer). 75 assertBitSet(BitSet.valueOf(LongBuffer.wrap(longs)), longs, s); 76 // Surround 'longs' with junk set bits but exclude them from the LongBuffer. 77 long[] paddedLongs = new long[1 + longs.length + 1]; 78 paddedLongs[0] = paddedLongs[paddedLongs.length - 1] = -1L; 79 System.arraycopy(longs, 0, paddedLongs, 1, longs.length); 80 assertBitSet(BitSet.valueOf(LongBuffer.wrap(paddedLongs, 1, longs.length)), longs, s); 81 82 // Check that the long[] is copied. 83 if (longs.length > 0) { 84 BitSet original = BitSet.valueOf(longs); 85 longs[0] = ~longs[0]; 86 assertFalse(BitSet.valueOf(longs).equals(original)); 87 } 88 } 89 90 public void test_valueOf_long() throws Exception { 91 assertBitSet(new long[0], "{}"); 92 assertBitSet(new long[] { 1L }, "{0}"); 93 assertBitSet(new long[] { 0x111L }, "{0, 4, 8}"); 94 assertBitSet(new long[] { 0x101L, 0x4000000000000000L }, "{0, 8, 126}"); 95 } 96 97 private static void assertBitSet(BitSet bs, byte[] bytes, String s) { 98 for (int i = 0; i < 8 * bytes.length; ++i) { 99 assertEquals(bs.toString(), ((bytes[i / 8] & (1L << (i % 8))) != 0), bs.get(i)); 100 } 101 int cardinality = 0; 102 for (int i = 0; i < bytes.length; ++i) { 103 cardinality += Integer.bitCount(((int) bytes[i]) & 0xff); 104 } 105 if (cardinality != 0) { 106 assertFalse(bs.isEmpty()); 107 } else { 108 assertTrue(bs.isEmpty()); 109 } 110 assertEquals(cardinality, bs.cardinality()); 111 assertEquals(roundUp(8 * bytes.length, 64), bs.size()); 112 assertEquals(s, bs.toString()); 113 } 114 115 private static int roundUp(int n, int multiple) { 116 return (n == 0) ? 0 : ((n + multiple - 1) / multiple) * multiple; 117 } 118 119 private static void assertBitSet(byte[] bytes, String s) { 120 // Test BitSet.valueOf(byte[]). 121 assertBitSet(BitSet.valueOf(bytes), bytes, s); 122 // Test BitSet.valueOf(ByteBuffer). 123 assertBitSet(BitSet.valueOf(ByteBuffer.wrap(bytes)), bytes, s); 124 // Surround 'bytes' with junk set bits but exclude them from the ByteBuffer. 125 byte[] paddedBytes = new byte[1 + bytes.length + 1]; 126 paddedBytes[0] = paddedBytes[paddedBytes.length - 1] = (byte) -1; 127 System.arraycopy(bytes, 0, paddedBytes, 1, bytes.length); 128 assertBitSet(BitSet.valueOf(ByteBuffer.wrap(paddedBytes, 1, bytes.length)), bytes, s); 129 130 // Check that the byte[] is copied. 131 if (bytes.length > 0) { 132 BitSet original = BitSet.valueOf(bytes); 133 bytes[0] = (byte) ~bytes[0]; 134 assertFalse(BitSet.valueOf(bytes).equals(original)); 135 } 136 } 137 138 public void test_valueOf_byte() throws Exception { 139 // Nothing... 140 assertBitSet(new byte[0], "{}"); 141 // Less than a long... 142 assertBitSet(new byte[] { 0x01 }, "{0}"); 143 assertBitSet(new byte[] { 0x01, 0x11 }, "{0, 8, 12}"); 144 assertBitSet(new byte[] { 0x01, 0x01, 0x00, 0x00, 0x01 }, "{0, 8, 32}"); 145 // Exactly one long.... 146 assertBitSet(new byte[] { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, (byte) 0x80 }, "{0, 63}"); 147 // One long and a byte left over... 148 assertBitSet(new byte[] { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 }, "{0, 64}"); 149 // Two longs... 150 byte[] bytes = new byte[] { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, (byte) 0x80, 151 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, (byte) 0x80 }; 152 assertBitSet(bytes, "{0, 63, 64, 127}"); 153 } 154 155 public void test_toLongArray() throws Exception { 156 assertEquals("[]", Arrays.toString(BitSet.valueOf(new long[0]).toLongArray())); 157 assertEquals("[1]", Arrays.toString(BitSet.valueOf(new long[] { 1 }).toLongArray())); 158 assertEquals("[1, 2]", Arrays.toString(BitSet.valueOf(new long[] { 1, 2 }).toLongArray())); 159 160 // Check that we're not returning trailing empty space. 161 assertEquals("[]", Arrays.toString(new BitSet(128).toLongArray())); 162 BitSet bs = new BitSet(); 163 bs.set(0); 164 bs.set(64, 66); 165 bs.clear(64, 66); 166 assertEquals("[1]", Arrays.toString(bs.toLongArray())); 167 } 168 169 public void test_toByteArray() throws Exception { 170 assertEquals("[]", Arrays.toString(BitSet.valueOf(new long[0]).toByteArray())); 171 assertEquals("[1]", Arrays.toString(BitSet.valueOf(new long[] { 1 }).toByteArray())); 172 assertEquals("[-17, -51, -85, -112, 120, 86, 52, 18]", 173 Arrays.toString(BitSet.valueOf(new long[] { 0x1234567890abcdefL }).toByteArray())); 174 assertEquals("[1, 0, 0, 0, 0, 0, 0, 0, 2]", 175 Arrays.toString(BitSet.valueOf(new long[] { 1, 2 }).toByteArray())); 176 } 177 178 public void test_previousSetBit() { 179 assertEquals(-1, new BitSet().previousSetBit(666)); 180 181 BitSet bs; 182 183 bs = new BitSet(); 184 bs.set(32); 185 assertEquals(32, bs.previousSetBit(999)); 186 assertEquals(32, bs.previousSetBit(33)); 187 assertEquals(32, bs.previousSetBit(32)); 188 assertEquals(-1, bs.previousSetBit(31)); 189 190 bs = new BitSet(); 191 bs.set(0); 192 bs.set(1); 193 bs.set(32); 194 bs.set(192); 195 bs.set(666); 196 197 assertEquals(666, bs.previousSetBit(999)); 198 assertEquals(666, bs.previousSetBit(667)); 199 assertEquals(666, bs.previousSetBit(666)); 200 assertEquals(192, bs.previousSetBit(665)); 201 assertEquals(32, bs.previousSetBit(191)); 202 assertEquals(1, bs.previousSetBit(31)); 203 assertEquals(0, bs.previousSetBit(0)); 204 assertEquals(-1, bs.previousSetBit(-1)); 205 } 206 207 private static BitSet big() { 208 BitSet result = new BitSet(); 209 result.set(1000); 210 return result; 211 } 212 213 private static BitSet small() { 214 BitSet result = new BitSet(); 215 result.set(10); 216 return result; 217 } 218 219 public void test_differentSizes() { 220 BitSet result = big(); 221 result.and(small()); 222 assertEquals("{}", result.toString()); 223 result = small(); 224 result.and(big()); 225 assertEquals("{}", result.toString()); 226 227 result = big(); 228 result.andNot(small()); 229 assertEquals("{1000}", result.toString()); 230 result = small(); 231 result.andNot(big()); 232 assertEquals("{10}", result.toString()); 233 234 assertFalse(big().intersects(small())); 235 assertFalse(small().intersects(big())); 236 237 result = big(); 238 result.or(small()); 239 assertEquals("{10, 1000}", result.toString()); 240 result = small(); 241 result.or(big()); 242 assertEquals("{10, 1000}", result.toString()); 243 244 result = big(); 245 result.xor(small()); 246 assertEquals("{10, 1000}", result.toString()); 247 result = small(); 248 result.xor(big()); 249 assertEquals("{10, 1000}", result.toString()); 250 } 251 252 public void test_stream() { 253 final int size = 128; 254 255 // Generate an arbitrary array of bytes. 256 byte[] bytes = new byte[size]; 257 new Random(0).nextBytes(bytes); 258 259 BitSet bs = BitSet.valueOf(bytes); 260 261 assertEquals(bs.cardinality(), bs.stream().count()); 262 bs.stream().forEach(x -> assertTrue(bs.get(x))); 263 } 264} 265