1/*
2 * Copyright (C) 2007 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 com.android.dx.util;
18
19import junit.framework.TestCase;
20
21public final class BitsTest extends TestCase {
22    public void test_makeBitSet() {
23        assertEquals(label(0), 0, Bits.makeBitSet(0).length);
24
25        for (int i = 1; i <= 32; i++) {
26            assertEquals(label(i), 1, Bits.makeBitSet(i).length);
27        }
28
29        for (int i = 33; i <= 64; i++) {
30            assertEquals(label(i), 2, Bits.makeBitSet(i).length);
31        }
32
33        for (int i = 65; i < 4000; i += 101) {
34            int expect = i >> 5;
35            if ((expect * 32) < i) {
36                expect++;
37            }
38            assertEquals(label(i), expect, Bits.makeBitSet(i).length);
39        }
40    }
41
42    public void test_getMax() {
43        for (int i = 0; i < 4000; i += 59) {
44            int expect = i >> 5;
45            if ((expect * 32) < i) {
46                expect++;
47            }
48            assertEquals(label(i), expect * 32,
49                         Bits.getMax(new int[expect]));
50        }
51    }
52
53    public void test1_get() {
54        int[] bits = Bits.makeBitSet(100);
55
56        for (int i = 0; i < 100; i++) {
57            assertFalse(label(i), Bits.get(bits, i));
58        }
59    }
60
61    public void test2_get() {
62        int[] bits = Bits.makeBitSet(100);
63        for (int i = 0; i < bits.length; i++) {
64            bits[i] = -1;
65        }
66
67        for (int i = 0; i < 100; i++) {
68            assertTrue(label(i), Bits.get(bits, i));
69        }
70    }
71
72    public void test3_get() {
73        int[] bits = Bits.makeBitSet(100);
74
75        for (int i = 0; i < 100; i++) {
76            Bits.set(bits, i, (i % 5) == 0);
77        }
78
79        for (int i = 0; i < 100; i++) {
80            boolean expect = (i % 5) == 0;
81            assertTrue(label(i), Bits.get(bits, i) == expect);
82        }
83    }
84
85    public void test1_set1() {
86        int[] bits = Bits.makeBitSet(50);
87        bits[1] = -1;
88
89        Bits.set(bits, 0, true);
90        Bits.set(bits, 3, true);
91        Bits.set(bits, 6, true);
92        Bits.set(bits, 3, false);
93        Bits.set(bits, 35, false);
94        Bits.set(bits, 38, false);
95        Bits.set(bits, 42, false);
96        Bits.set(bits, 38, true);
97
98        assertEquals(label(1), 0x41, bits[0]);
99        assertEquals(label(2), 0xfffffbf7, bits[1]);
100    }
101
102    public void test2_set1() {
103        int[] bits = Bits.makeBitSet(100);
104
105        for (int i = 0; i < 100; i++) {
106            if ((i % 3) == 0) {
107                Bits.set(bits, i, true);
108            }
109        }
110
111        for (int i = 0; i < 100; i++) {
112            if ((i % 5) == 0) {
113                Bits.set(bits, i, false);
114            }
115        }
116
117        for (int i = 0; i < 100; i++) {
118            if ((i % 7) == 0) {
119                Bits.set(bits, i, true);
120            }
121        }
122
123        for (int i = 0; i < 100; i++) {
124            boolean expect = ((i % 7) == 0) ||
125                (((i % 3) == 0) && ((i % 5) != 0));
126            assertTrue(label(i), Bits.get(bits, i) == expect);
127        }
128    }
129
130    public void test_set2() {
131        int[] bits = Bits.makeBitSet(100);
132
133        for (int i = 0; i < 100; i++) {
134            if ((i % 11) == 0) {
135                Bits.set(bits, i);
136            }
137        }
138
139        for (int i = 0; i < 100; i++) {
140            boolean expect = (i % 11) == 0;
141            assertTrue(label(i), Bits.get(bits, i) == expect);
142        }
143    }
144
145    public void test_clear() {
146        int[] bits = Bits.makeBitSet(100);
147        for (int i = 0; i < bits.length; i++) {
148            bits[i] = -1;
149        }
150
151        for (int i = 0; i < 100; i++) {
152            if ((i % 5) == 0) {
153                Bits.clear(bits, i);
154            }
155        }
156
157        for (int i = 0; i < 100; i++) {
158            boolean expect = (i % 5) != 0;
159            assertTrue(label(i), Bits.get(bits, i) == expect);
160        }
161    }
162
163    public void test1_isEmpty() {
164        for (int i = 0; i < 10; i++) {
165            assertTrue(label(i), Bits.isEmpty(new int[i]));
166        }
167    }
168
169    public void test2_isEmpty() {
170        for (int i = 1; i < 1000; i += 11) {
171            int[] bits = Bits.makeBitSet(i);
172            for (int j = i % 11; j >= 0; j--) {
173                int x = i - 1 - (j * 13);
174                if (x >= 0) {
175                    Bits.set(bits, x);
176                }
177            }
178            assertFalse(label(i), Bits.isEmpty(bits));
179        }
180    }
181
182    public void test1_bitCount() {
183        for (int i = 0; i < 10; i++) {
184            assertEquals(label(i), 0, Bits.bitCount(new int[i]));
185        }
186    }
187
188    public void test2_bitCount() {
189        for (int i = 1; i < 1000; i += 13) {
190            int[] bits = Bits.makeBitSet(i);
191            int count = 0;
192            for (int j = 0; j < i; j += 20) {
193                Bits.set(bits, j);
194                count++;
195            }
196            for (int j = 7; j < i; j += 11) {
197                if (!Bits.get(bits, j)) {
198                    Bits.set(bits, j);
199                    count++;
200                }
201            }
202            for (int j = 3; j < i; j += 17) {
203                if (!Bits.get(bits, j)) {
204                    Bits.set(bits, j);
205                    count++;
206                }
207            }
208            assertEquals(label(i), count, Bits.bitCount(bits));
209        }
210    }
211
212    public void test1_anyInRange() {
213        int[] bits = new int[100];
214
215        for (int i = 0; i < 100; i += 11) {
216            assertFalse(label(i), Bits.anyInRange(bits, 0, i));
217        }
218    }
219
220    public void test2_anyInRange() {
221        int[] bits = new int[100];
222
223        for (int i = 0; i < 100; i += 11) {
224            assertFalse(label(i), Bits.anyInRange(bits, i, 100));
225        }
226    }
227
228    public void test3_anyInRange() {
229        int[] bits = new int[100];
230
231        for (int i = 0; i < 50; i += 7) {
232            assertFalse(label(i), Bits.anyInRange(bits, i, 100 - i));
233        }
234    }
235
236    public void test4_anyInRange() {
237        int[] bits = new int[100];
238        for (int i = 0; i < bits.length; i++) {
239            bits[i] = -1;
240        }
241
242        for (int i = 1; i < 100; i += 11) {
243            assertTrue(label(i), Bits.anyInRange(bits, 0, i));
244        }
245    }
246
247    public void test5_anyInRange() {
248        int[] bits = new int[100];
249        for (int i = 0; i < bits.length; i++) {
250            bits[i] = -1;
251        }
252
253        for (int i = 1; i < 100; i += 11) {
254            assertTrue(label(i), Bits.anyInRange(bits, i, 100));
255        }
256    }
257
258    public void test6_anyInRange() {
259        int[] bits = new int[100];
260        for (int i = 0; i < bits.length; i++) {
261            bits[i] = -1;
262        }
263
264        for (int i = 0; i < 50; i += 7) {
265            assertTrue(label(i), Bits.anyInRange(bits, i, 100 - i));
266        }
267    }
268
269    public void test1_findFirst1() {
270        int[] bits = new int[100];
271
272        for (int i = 0; i < 100; i++) {
273            assertEquals(label(i), -1, Bits.findFirst(bits, i));
274        }
275    }
276
277    public void test2_findFirst1() {
278        int[] bits = new int[100];
279        for (int i = 0; i < bits.length; i++) {
280            bits[i] = -1;
281        }
282
283        for (int i = 0; i < 100; i++) {
284            assertEquals(label(i), i, Bits.findFirst(bits, i));
285        }
286    }
287
288    public void test3_findFirst1() {
289        int[] bits = new int[100];
290
291        for (int i = 25; i < 80; i++) {
292            for (int j = 0; j < bits.length; j++) {
293                bits[j] = 0;
294            }
295
296            Bits.set(bits, i - 5);
297            Bits.set(bits, i + 5);
298            Bits.set(bits, i + 10);
299            Bits.set(bits, i + 20);
300            assertEquals(label(i), i + 5, Bits.findFirst(bits, i));
301        }
302    }
303
304    public void test1_findFirst2() {
305        for (int i = 0; i < 32; i++) {
306            assertEquals(label(i), -1, Bits.findFirst(0, i));
307        }
308    }
309
310    public void test2_findFirst2() {
311        for (int i = 0; i < 32; i++) {
312            assertEquals(label(i), i, Bits.findFirst(-1, i));
313        }
314    }
315
316    public void test3_findFirst2() {
317        for (int i = 0; i < 32; i++) {
318            assertEquals(label(i), -1, Bits.findFirst((1 << i) >>> 1, i));
319        }
320    }
321
322    public void test4_findFirst2() {
323        for (int i = 0; i < 32; i++) {
324            assertEquals(label(i), i, Bits.findFirst(1 << i, i));
325        }
326    }
327
328    public void test5_findFirst2() {
329        for (int i = 0; i < 31; i++) {
330            assertEquals(label(i), i + 1, Bits.findFirst(1 << (i + 1), i));
331        }
332    }
333
334    public void test6_findFirst2() {
335        for (int i = 0; i < 32; i++) {
336            int value = (1 << i);
337            value |= (value >>> 1);
338            assertEquals(label(i), i, Bits.findFirst(value, i));
339        }
340    }
341
342    private static String label(int n) {
343        return "(" + n + ")";
344    }
345}
346