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