src/main/gov/nasa/jpf/util/BitSet1024.java

   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 }