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 17 package com.android.dx.util; 18 19 import junit.framework.TestCase; 20 21 public 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
