Mercurial > hg > Members > kono > jpf-core

comparison src/main/gov/nasa/jpf/util/BitSet1024.java @ 0:61d41facf527

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial v8 import (history reset)
author Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
date Fri, 23 Jan 2015 10:14:01 -0800
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:61d41facf527
1 /*
2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
4 * All rights reserved.
5 *
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
8 * in compliance with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0.
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 package gov.nasa.jpf.util;
20
21
22 /**
23 * a fixed size BitSet with 1024 bits.
24 *
25 * The main motivation for this class is to minimize memory size while maximizing
26 * performance and keeping a java.util.BitSet compatible interface. The only
27 * deviation from the standard BitSet is that we assume more cardinality() calls
28 * than set()/clear() calls, i.e. we want to cache this value
29 *
30 * Instances of this class do not allocate any additional memory, we keep all
31 * data in builtin type fields
32 */
33 public class BitSet1024 extends AbstractFixedBitSet {
34
35 public static final int INDEX_MASK = 0xfffffc00;
36
37 long l0, l1, l2, l3, l4, l5, l6, l7, l8, l9, l10, l11, l12, l13, l14, l15;
38
39 public BitSet1024 (){
40 // nothing in here
41 }
42
43 public BitSet1024 (int i){
44 set(i);
45 }
46
47 public BitSet1024 (int... idx){
48 for (int i : idx){
49 set(i);
50 }
51 }
52
53 private final int computeCardinality (){
54 int n= Long.bitCount(l0);
55 n += Long.bitCount(l1);
56 n += Long.bitCount(l2);
57 n += Long.bitCount(l3);
58 n += Long.bitCount(l4);
59 n += Long.bitCount(l5);
60 n += Long.bitCount(l6);
61 n += Long.bitCount(l7);
62 n += Long.bitCount(l8);
63 n += Long.bitCount(l9);
64 n += Long.bitCount(l10);
65 n += Long.bitCount(l11);
66 n += Long.bitCount(l12);
67 n += Long.bitCount(l13);
68 n += Long.bitCount(l14);
69 n += Long.bitCount(l15);
70 return n;
71 }
72
73 //--- public interface (much like java.util.BitSet)
74
75 @Override
76 public void set (int i){
77 if ((i & INDEX_MASK) == 0) {
78 long bitPattern = (1L << i);
79
80 switch (i >> 6) {
81 case 0:
82 if ((l0 & bitPattern) == 0L) {
83 cardinality++;
84 l0 |= bitPattern;
85 }
86 break;
87 case 1:
88 if ((l1 & bitPattern) == 0L) {
89 cardinality++;
90 l1 |= bitPattern;
91 }
92 break;
93 case 2:
94 if ((l2 & bitPattern) == 0L) {
95 cardinality++;
96 l2 |= bitPattern;
97 }
98 break;
99 case 3:
100 if ((l3 & bitPattern) == 0L) {
101 cardinality++;
102 l3 |= bitPattern;
103 }
104 break;
105 case 4:
106 if ((l4 & bitPattern) == 0L) {
107 cardinality++;
108 l4 |= bitPattern;
109 }
110 break;
111 case 5:
112 if ((l5 & bitPattern) == 0L) {
113 cardinality++;
114 l5 |= bitPattern;
115 }
116 break;
117 case 6:
118 if ((l6 & bitPattern) == 0L) {
119 cardinality++;
120 l6 |= bitPattern;
121 }
122 break;
123 case 7:
124 if ((l7 & bitPattern) == 0L) {
125 cardinality++;
126 l7 |= bitPattern;
127 }
128 break;
129 case 8:
130 if ((l8 & bitPattern) == 0L) {
131 cardinality++;
132 l8 |= bitPattern;
133 }
134 break;
135 case 9:
136 if ((l9 & bitPattern) == 0L) {
137 cardinality++;
138 l9 |= bitPattern;
139 }
140 break;
141 case 10:
142 if ((l10 & bitPattern) == 0L) {
143 cardinality++;
144 l10 |= bitPattern;
145 }
146 break;
147 case 11:
148 if ((l11 & bitPattern) == 0L) {
149 cardinality++;
150 l11 |= bitPattern;
151 }
152 break;
153 case 12:
154 if ((l12 & bitPattern) == 0L) {
155 cardinality++;
156 l12 |= bitPattern;
157 }
158 break;
159 case 13:
160 if ((l13 & bitPattern) == 0L) {
161 cardinality++;
162 l13 |= bitPattern;
163 }
164 break;
165 case 14:
166 if ((l14 & bitPattern) == 0L) {
167 cardinality++;
168 l14 |= bitPattern;
169 }
170 break;
171 case 15:
172 if ((l15 & bitPattern) == 0L) {
173 cardinality++;
174 l15 |= bitPattern;
175 }
176 }
177 } else {
178 throw new IndexOutOfBoundsException("BitSet1024 index out of range: " + i);
179 }
180 }
181
182 @Override
183 public void clear (int i){
184 if ((i & INDEX_MASK) == 0) {
185 long bitPattern = (1L << i);
186
187 switch (i >> 6) {
188 case 0:
189 if ((l0 & bitPattern) != 0L) {
190 cardinality--;
191 l0 &= ~bitPattern;
192 }
193 break;
194 case 1:
195 if ((l1 & bitPattern) != 0L) {
196 cardinality--;
197 l1 &= ~bitPattern;
198 }
199 break;
200 case 2:
201 if ((l2 & bitPattern) != 0L) {
202 cardinality--;
203 l2 &= ~bitPattern;
204 }
205 break;
206 case 3:
207 if ((l3 & bitPattern) != 0L) {
208 cardinality--;
209 l3 &= ~bitPattern;
210 }
211 case 4:
212 if ((l4 & bitPattern) != 0L) {
213 cardinality--;
214 l4 &= ~bitPattern;
215 }
216 break;
217 case 5:
218 if ((l5 & bitPattern) != 0L) {
219 cardinality--;
220 l5 &= ~bitPattern;
221 }
222 break;
223 case 6:
224 if ((l6 & bitPattern) != 0L) {
225 cardinality--;
226 l6 &= ~bitPattern;
227 }
228 break;
229 case 7:
230 if ((l7 & bitPattern) != 0L) {
231 cardinality--;
232 l7 &= ~bitPattern;
233 }
234 break;
235 case 8:
236 if ((l8 & bitPattern) != 0L) {
237 cardinality--;
238 l8 &= ~bitPattern;
239 }
240 break;
241 case 9:
242 if ((l9 & bitPattern) != 0L) {
243 cardinality--;
244 l9 &= ~bitPattern;
245 }
246 break;
247 case 10:
248 if ((l10 & bitPattern) != 0L) {
249 cardinality--;
250 l10 &= ~bitPattern;
251 }
252 break;
253 case 11:
254 if ((l11 & bitPattern) != 0L) {
255 cardinality--;
256 l11 &= ~bitPattern;
257 }
258 break;
259 case 12:
260 if ((l12 & bitPattern) != 0L) {
261 cardinality--;
262 l12 &= ~bitPattern;
263 }
264 break;
265 case 13:
266 if ((l13 & bitPattern) != 0L) {
267 cardinality--;
268 l13 &= ~bitPattern;
269 }
270 break;
271 case 14:
272 if ((l14 & bitPattern) != 0L) {
273 cardinality--;
274 l14 &= ~bitPattern;
275 }
276 break;
277 case 15:
278 if ((l15 & bitPattern) != 0L) {
279 cardinality--;
280 l15 &= ~bitPattern;
281 }
282 }
283 } else {
284 throw new IndexOutOfBoundsException("BitSet1024 index out of range: " + i);
285 }
286 }
287
288 @Override
289 public boolean get (int i){
290 if ((i & INDEX_MASK) == 0) {
291 long bitPattern = (1L << i);
292
293 switch (i >> 6) {
294 case 0:
295 return ((l0 & bitPattern) != 0);
296 case 1:
297 return ((l1 & bitPattern) != 0);
298 case 2:
299 return ((l2 & bitPattern) != 0);
300 case 3:
301 return ((l3 & bitPattern) != 0);
302 case 4:
303 return ((l4 & bitPattern) != 0);
304 case 5:
305 return ((l5 & bitPattern) != 0);
306 case 6:
307 return ((l6 & bitPattern) != 0);
308 case 7:
309 return ((l7 & bitPattern) != 0);
310 case 8:
311 return ((l8 & bitPattern) != 0);
312 case 9:
313 return ((l9 & bitPattern) != 0);
314 case 10:
315 return ((l10 & bitPattern) != 0);
316 case 11:
317 return ((l11 & bitPattern) != 0);
318 case 12:
319 return ((l12 & bitPattern) != 0);
320 case 13:
321 return ((l13 & bitPattern) != 0);
322 case 14:
323 return ((l14 & bitPattern) != 0);
324 case 15:
325 return ((l15 & bitPattern) != 0);
326 }
327 }
328
329 throw new IndexOutOfBoundsException("BitSet1024 index out of range: " + i);
330 }
331
332 @Override
333 public int size() {
334 return 1024;
335 }
336
337 /**
338 * number of bits we can store
339 */
340 @Override
341 public int capacity() {
342 return 1024;
343 }
344
345 /**
346 * index of highest set bit + 1
347 */
348 @Override
349 public int length() {
350 if (l15 != 0){
351 return 1024 - Long.numberOfLeadingZeros(l15);
352 } else if (l14 != 0) {
353 return 960 - Long.numberOfLeadingZeros(l14);
354 } else if (l13 != 0) {
355 return 896 - Long.numberOfLeadingZeros(l13);
356 } else if (l12 != 0) {
357 return 832 - Long.numberOfLeadingZeros(l12);
358 } else if (l11 != 0) {
359 return 768 - Long.numberOfLeadingZeros(l11);
360 } else if (l10 != 0) {
361 return 704 - Long.numberOfLeadingZeros(l10);
362 } else if (l9 != 0) {
363 return 640 - Long.numberOfLeadingZeros(l9);
364 } else if (l8 != 0) {
365 return 576 - Long.numberOfLeadingZeros(l8);
366 } else if (l7 != 0) {
367 return 512 - Long.numberOfLeadingZeros(l7);
368 } else if (l6 != 0) {
369 return 448 - Long.numberOfLeadingZeros(l6);
370 } else if (l5 != 0) {
371 return 384 - Long.numberOfLeadingZeros(l5);
372 } else if (l4 != 0) {
373 return 320 - Long.numberOfLeadingZeros(l4);
374 } else if (l3 != 0){
375 return 256 - Long.numberOfLeadingZeros(l3);
376 } else if (l2 != 0){
377 return 192 - Long.numberOfLeadingZeros(l2);
378 } else if (l1 != 0){
379 return 128 - Long.numberOfLeadingZeros(l1);
380 } else if (l1 != 0){
381 return 64 - Long.numberOfLeadingZeros(l0);
382 } else {
383 return 0;
384 }
385 }
386
387 @Override
388 public void clear() {
389 l0 = l1 = l2 = l3 = l4 = l5 = l6 = l7
390 = l8 = l9= l10 = l11 = l12 = l13 = l14
391 = l15 =0L;
392 cardinality = 0;
393 }
394
395
396 @Override
397 public int nextSetBit (int fromIdx){
398 if ((fromIdx & INDEX_MASK) == 0) {
399 int i;
400 int i0 = fromIdx & 0x3f;
401 switch (fromIdx >> 6){
402 case 0:
403 if ((i=Long.numberOfTrailingZeros(l0 & (0xffffffffffffffffL << i0))) <64) return i;
404 if ((i=Long.numberOfTrailingZeros(l1)) <64) return i + 64;
405 if ((i=Long.numberOfTrailingZeros(l2)) <64) return i + 128;
406 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
407 if ((i=Long.numberOfTrailingZeros(l4)) <64) return i + 256;
408 if ((i=Long.numberOfTrailingZeros(l5)) <64) return i + 320;
409 if ((i=Long.numberOfTrailingZeros(l6)) <64) return i + 384;
410 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
411 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
412 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
413 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
414 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
415 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
416 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
417 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
418 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
419 break;
420 case 1:
421 if ((i=Long.numberOfTrailingZeros(l1 & (0xffffffffffffffffL << i0))) <64) return i + 64;
422 if ((i=Long.numberOfTrailingZeros(l2)) <64) return i + 128;
423 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
424 if ((i=Long.numberOfTrailingZeros(l4)) <64) return i + 256;
425 if ((i=Long.numberOfTrailingZeros(l5)) <64) return i + 320;
426 if ((i=Long.numberOfTrailingZeros(l6)) <64) return i + 384;
427 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
428 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
429 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
430 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
431 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
432 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
433 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
434 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
435 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
436 break;
437 case 2:
438 if ((i=Long.numberOfTrailingZeros(l2 & (0xffffffffffffffffL << i0))) <64) return i + 128;
439 if ((i=Long.numberOfTrailingZeros(l3)) <64) return i + 192;
440 if ((i=Long.numberOfTrailingZeros(l4)) <64) return i + 256;
441 if ((i=Long.numberOfTrailingZeros(l5)) <64) return i + 320;
442 if ((i=Long.numberOfTrailingZeros(l6)) <64) return i + 384;
443 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
444 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
445 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
446 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
447 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
448 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
449 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
450 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
451 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
452 break;
453 case 3:
454 if ((i=Long.numberOfTrailingZeros(l3 & (0xffffffffffffffffL << i0))) <64) return i + 192;
455 if ((i=Long.numberOfTrailingZeros(l4)) <64) return i + 256;
456 if ((i=Long.numberOfTrailingZeros(l5)) <64) return i + 320;
457 if ((i=Long.numberOfTrailingZeros(l6)) <64) return i + 384;
458 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
459 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
460 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
461 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
462 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
463 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
464 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
465 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
466 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
467 break;
468 case 4:
469 if ((i=Long.numberOfTrailingZeros(l4 & (0xffffffffffffffffL << i0))) <64) return i + 256;
470 if ((i=Long.numberOfTrailingZeros(l5)) <64) return i + 320;
471 if ((i=Long.numberOfTrailingZeros(l6)) <64) return i + 384;
472 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
473 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
474 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
475 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
476 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
477 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
478 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
479 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
480 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
481 break;
482 case 5:
483 if ((i=Long.numberOfTrailingZeros(l5 & (0xffffffffffffffffL << i0))) <64) return i + 320;
484 if ((i=Long.numberOfTrailingZeros(l6)) <64) return i + 384;
485 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
486 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
487 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
488 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
489 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
490 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
491 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
492 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
493 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
494 break;
495 case 6:
496 if ((i=Long.numberOfTrailingZeros(l6 & (0xffffffffffffffffL << i0))) <64) return i + 384;
497 if ((i=Long.numberOfTrailingZeros(l7)) <64) return i + 448;
498 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
499 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
500 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
501 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
502 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
503 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
504 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
505 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
506 break;
507 case 7:
508 if ((i=Long.numberOfTrailingZeros(l7 & (0xffffffffffffffffL << i0))) <64) return i + 448;
509 if ((i=Long.numberOfTrailingZeros(l8)) <64) return i + 512;
510 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
511 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
512 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
513 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
514 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
515 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
516 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
517 break;
518 case 8:
519 if ((i=Long.numberOfTrailingZeros(l8 & (0xffffffffffffffffL << i0))) <64) return i + 512;
520 if ((i=Long.numberOfTrailingZeros(l9)) <64) return i + 576;
521 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
522 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
523 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
524 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
525 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
526 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
527 break;
528 case 9:
529 if ((i=Long.numberOfTrailingZeros(l9 & (0xffffffffffffffffL << i0))) <64) return i + 576;
530 if ((i=Long.numberOfTrailingZeros(l10)) <64) return i + 640;
531 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
532 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
533 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
534 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
535 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
536 break;
537 case 10:
538 if ((i=Long.numberOfTrailingZeros(l10 & (0xffffffffffffffffL << i0))) <64) return i + 640;
539 if ((i=Long.numberOfTrailingZeros(l11)) <64) return i + 704;
540 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
541 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
542 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
543 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
544 break;
545 case 11:
546 if ((i=Long.numberOfTrailingZeros(l11 & (0xffffffffffffffffL << i0))) <64) return i + 704;
547 if ((i=Long.numberOfTrailingZeros(l12)) <64) return i + 768;
548 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
549 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
550 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
551 break;
552 case 12:
553 if ((i=Long.numberOfTrailingZeros(l12 & (0xffffffffffffffffL << i0))) <64) return i + 768;
554 if ((i=Long.numberOfTrailingZeros(l13)) <64) return i + 832;
555 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
556 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
557 break;
558 case 13:
559 if ((i=Long.numberOfTrailingZeros(l13 & (0xffffffffffffffffL << i0))) <64) return i + 832;
560 if ((i=Long.numberOfTrailingZeros(l14)) <64) return i + 896;
561 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
562 break;
563 case 14:
564 if ((i=Long.numberOfTrailingZeros(l14 & (0xffffffffffffffffL << i0))) <64) return i + 896;
565 if ((i=Long.numberOfTrailingZeros(l15)) <64) return i + 960;
566 break;
567 case 15:
568 if ((i=Long.numberOfTrailingZeros(l15 & (0xffffffffffffffffL << i0))) <64) return i + 960;
569 break;
570 }
571 return -1;
572
573 }
574 return -1;
575 }
576
577 @Override
578 public int nextClearBit (int fromIdx){
579 if ((fromIdx & INDEX_MASK) == 0) {
580 int i;
581 int i0 = fromIdx & 0x3f;
582 switch (fromIdx >> 6){
583 case 0:
584 if ((i=Long.numberOfTrailingZeros(~l0 & (0xffffffffffffffffL << i0))) <64) return i;
585 if ((i=Long.numberOfTrailingZeros(~l1)) <64) return i + 64;
586 if ((i=Long.numberOfTrailingZeros(~l2)) <64) return i + 128;
587 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
588 if ((i=Long.numberOfTrailingZeros(~l4)) <64) return i + 256;
589 if ((i=Long.numberOfTrailingZeros(~l5)) <64) return i + 320;
590 if ((i=Long.numberOfTrailingZeros(~l6)) <64) return i + 384;
591 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
592 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
593 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
594 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
595 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
596 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
597 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
598 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
599 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
600 break;
601 case 1:
602 if ((i=Long.numberOfTrailingZeros(~l1 & (0xffffffffffffffffL << i0))) <64) return i + 64;
603 if ((i=Long.numberOfTrailingZeros(~l2)) <64) return i + 128;
604 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
605 if ((i=Long.numberOfTrailingZeros(~l4)) <64) return i + 256;
606 if ((i=Long.numberOfTrailingZeros(~l5)) <64) return i + 320;
607 if ((i=Long.numberOfTrailingZeros(~l6)) <64) return i + 384;
608 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
609 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
610 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
611 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
612 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
613 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
614 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
615 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
616 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
617 break;
618 case 2:
619 if ((i=Long.numberOfTrailingZeros(~l2 & (0xffffffffffffffffL << i0))) <64) return i + 128;
620 if ((i=Long.numberOfTrailingZeros(~l3)) <64) return i + 192;
621 if ((i=Long.numberOfTrailingZeros(~l4)) <64) return i + 256;
622 if ((i=Long.numberOfTrailingZeros(~l5)) <64) return i + 320;
623 if ((i=Long.numberOfTrailingZeros(~l6)) <64) return i + 384;
624 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
625 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
626 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
627 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
628 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
629 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
630 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
631 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
632 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
633 break;
634 case 3:
635 if ((i=Long.numberOfTrailingZeros(~l3 & (0xffffffffffffffffL << i0))) <64) return i + 192;
636 if ((i=Long.numberOfTrailingZeros(~l4)) <64) return i + 256;
637 if ((i=Long.numberOfTrailingZeros(~l5)) <64) return i + 320;
638 if ((i=Long.numberOfTrailingZeros(~l6)) <64) return i + 384;
639 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
640 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
641 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
642 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
643 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
644 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
645 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
646 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
647 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
648 break;
649 case 4:
650 if ((i=Long.numberOfTrailingZeros(~l4 & (0xffffffffffffffffL << i0))) <64) return i + 256;
651 if ((i=Long.numberOfTrailingZeros(~l5)) <64) return i + 320;
652 if ((i=Long.numberOfTrailingZeros(~l6)) <64) return i + 384;
653 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
654 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
655 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
656 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
657 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
658 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
659 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
660 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
661 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
662 break;
663 case 5:
664 if ((i=Long.numberOfTrailingZeros(~l5 & (0xffffffffffffffffL << i0))) <64) return i + 320;
665 if ((i=Long.numberOfTrailingZeros(~l6)) <64) return i + 384;
666 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
667 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
668 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
669 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
670 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
671 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
672 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
673 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
674 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
675 break;
676 case 6:
677 if ((i=Long.numberOfTrailingZeros(~l6 & (0xffffffffffffffffL << i0))) <64) return i + 384;
678 if ((i=Long.numberOfTrailingZeros(~l7)) <64) return i + 448;
679 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
680 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
681 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
682 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
683 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
684 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
685 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
686 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
687 break;
688 case 7:
689 if ((i=Long.numberOfTrailingZeros(~l7 & (0xffffffffffffffffL << i0))) <64) return i + 448;
690 if ((i=Long.numberOfTrailingZeros(~l8)) <64) return i + 512;
691 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
692 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
693 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
694 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
695 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
696 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
697 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
698 break;
699 case 8:
700 if ((i=Long.numberOfTrailingZeros(~l8 & (0xffffffffffffffffL << i0))) <64) return i + 512;
701 if ((i=Long.numberOfTrailingZeros(~l9)) <64) return i + 576;
702 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
703 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
704 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
705 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
706 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
707 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
708 break;
709 case 9:
710 if ((i=Long.numberOfTrailingZeros(~l9 & (0xffffffffffffffffL << i0))) <64) return i + 576;
711 if ((i=Long.numberOfTrailingZeros(~l10)) <64) return i + 640;
712 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
713 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
714 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
715 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
716 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
717 break;
718 case 10:
719 if ((i=Long.numberOfTrailingZeros(~l10 & (0xffffffffffffffffL << i0))) <64) return i + 640;
720 if ((i=Long.numberOfTrailingZeros(~l11)) <64) return i + 704;
721 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
722 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
723 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
724 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
725 break;
726 case 11:
727 if ((i=Long.numberOfTrailingZeros(~l11 & (0xffffffffffffffffL << i0))) <64) return i + 704;
728 if ((i=Long.numberOfTrailingZeros(~l12)) <64) return i + 768;
729 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
730 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
731 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
732 break;
733 case 12:
734 if ((i=Long.numberOfTrailingZeros(~l12 & (0xffffffffffffffffL << i0))) <64) return i + 768;
735 if ((i=Long.numberOfTrailingZeros(~l13)) <64) return i + 832;
736 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
737 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
738 break;
739 case 13:
740 if ((i=Long.numberOfTrailingZeros(~l13 & (0xffffffffffffffffL << i0))) <64) return i + 832;
741 if ((i=Long.numberOfTrailingZeros(~l14)) <64) return i + 896;
742 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
743 break;
744 case 14:
745 if ((i=Long.numberOfTrailingZeros(~l14 & (0xffffffffffffffffL << i0))) <64) return i + 896;
746 if ((i=Long.numberOfTrailingZeros(~l15)) <64) return i + 960;
747 break;
748 case 15:
749 if ((i=Long.numberOfTrailingZeros(~l15 & (0xffffffffffffffffL << i0))) <64) return i + 960;
750 break;
751 }
752
753 return -1;
754
755 } else {
756 //throw new IndexOutOfBoundsException("BitSet256 index out of range: " + fromIdx);
757 return -1;
758 }
759 }
760
761 public void and (BitSet1024 other){
762 l0 &= other.l0;
763 l1 &= other.l1;
764 l2 &= other.l2;
765 l3 &= other.l3;
766 l4 &= other.l4;
767 l5 &= other.l5;
768 l6 &= other.l6;
769 l7 &= other.l7;
770 l8 &= other.l8;
771 l9 &= other.l9;
772 l10 &= other.l10;
773 l11 &= other.l11;
774 l12 &= other.l12;
775 l13 &= other.l13;
776 l14 &= other.l14;
777 l15 &= other.l15;
778
779 cardinality = computeCardinality();
780 }
781
782 public void andNot (BitSet1024 other){
783 l0 &= ~other.l0;
784 l1 &= ~other.l1;
785 l2 &= ~other.l2;
786 l3 &= ~other.l3;
787 l4 &= ~other.l4;
788 l5 &= ~other.l5;
789 l6 &= ~other.l6;
790 l7 &= ~other.l7;
791 l8 &= ~other.l8;
792 l9 &= ~other.l9;
793 l10 &= ~other.l10;
794 l11 &= ~other.l11;
795 l12 &= ~other.l12;
796 l13 &= ~other.l13;
797 l14 &= ~other.l14;
798 l15 &= ~other.l15;
799
800 cardinality = computeCardinality();
801 }
802
803 public void or (BitSet1024 other){
804 l0 |= other.l0;
805 l1 |= other.l1;
806 l2 |= other.l2;
807 l3 |= other.l3;
808 l4 |= other.l4;
809 l5 |= other.l5;
810 l6 |= other.l6;
811 l7 |= other.l7;
812 l8 |= other.l8;
813 l9 |= other.l9;
814 l10 |= other.l10;
815 l11 |= other.l11;
816 l12 |= other.l12;
817 l13 |= other.l13;
818 l14 |= other.l14;
819 l15 |= other.l15;
820
821 cardinality = computeCardinality();
822 }
823
824 @Override
825 public boolean equals (Object o){
826 if (o instanceof BitSet1024){
827 BitSet1024 other = (BitSet1024)o;
828 if (l0 != other.l0) return false;
829 if (l1 != other.l1) return false;
830 if (l2 != other.l2) return false;
831 if (l3 != other.l3) return false;
832 if (l4 != other.l4) return false;
833 if (l5 != other.l5) return false;
834 if (l6 != other.l6) return false;
835 if (l7 != other.l7) return false;
836 if (l8 != other.l8) return false;
837 if (l9 != other.l9) return false;
838 if (l10 != other.l10) return false;
839 if (l11 != other.l11) return false;
840 if (l12 != other.l12) return false;
841 if (l13 != other.l13) return false;
842 if (l14 != other.l14) return false;
843 if (l15 != other.l15) return false;
844
845 return true;
846 } else {
847 // <2do> we could compare to a normal java.util.BitSet here
848 return false;
849 }
850 }
851
852 /**
853 * answer the same hashCodes as java.util.BitSet
854 */
855 @Override
856 public int hashCode() {
857 long hc = 1234;
858 hc ^= l0;
859 hc ^= l1*2;
860 hc ^= l2*3;
861 hc ^= l4*4;
862 hc ^= l5*5;
863 hc ^= l6*6;
864 hc ^= l7*7;
865 hc ^= l8*8;
866 hc ^= l9*9;
867 hc ^= l10*10;
868 hc ^= l11*11;
869 hc ^= l12*12;
870 hc ^= l13*13;
871 hc ^= l14*14;
872 hc ^= l15*15;
873 return (int) ((hc >>32) ^ hc);
874 }
875
876
877 @Override
878 public void hash (HashData hd){
879 hd.add(l0);
880 hd.add(l1);
881 hd.add(l2);
882 hd.add(l3);
883 hd.add(l4);
884 hd.add(l5);
885 hd.add(l6);
886 hd.add(l7);
887 hd.add(l8);
888 hd.add(l9);
889 hd.add(l10);
890 hd.add(l11);
891 hd.add(l12);
892 hd.add(l13);
893 hd.add(l14);
894 hd.add(l15);
895 }
896 }