src/main/gov/nasa/jpf/util/BitSet64.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  */
  24 public class BitSet64 extends AbstractFixedBitSet implements Cloneable {
  25
  26   static final int INDEX_MASK = 0xffffffc0; // ( i>=0 && i<64)
  27
  28   long l0;
  29
  30   public BitSet64 (){
  31     // nothing in here
  32   }
  33
  34   public BitSet64 (int i){
  35     set(i);
  36   }
  37
  38   public BitSet64 (int... idx){
  39     for (int i : idx){
  40       set(i);
  41     }
  42   }
  43
  44   @Override
  45   public void hash (HashData hd){
  46     hd.add(l0);
  47   }
  48
  49
  50   private final int computeCardinality (){
  51     return Long.bitCount(l0);
  52   }
  53
  54   //--- public interface (much like java.util.BitSet)
  55
  56   @Override
  57   public void set (int i){
  58     if ((i & INDEX_MASK) == 0){
  59       long bitPattern = (1L << i);
  60       if ((l0 & bitPattern) == 0L) {
  61         cardinality++;
  62         l0 |= bitPattern;
  63       }
  64     } else {
  65       throw new IndexOutOfBoundsException("BitSet64 index out of range: " + i);
  66     }
  67   }
  68
  69   @Override
  70   public void clear (int i){
  71     if ((i & INDEX_MASK) == 0){
  72       long bitPattern = (1L << i);
  73       if ((l0 & bitPattern) != 0L) { // bit is set
  74         cardinality--;
  75         l0 &= ~bitPattern;
  76       }
  77     } else {
  78       throw new IndexOutOfBoundsException("BitSet64 index out of range: " + i);
  79     }
  80   }
  81
  82
  83   @Override
  84   public boolean get (int i){
  85     if ((i & INDEX_MASK) == 0){
  86       long bitPattern = (1L << i);
  87       return ((l0 & bitPattern) != 0);
  88     } else {
  89       throw new IndexOutOfBoundsException("BitSet64 index out of range: " + i);
  90     }
  91   }
  92
  93   @Override
  94   public int capacity(){
  95     return 64;
  96   }
  97
  98   /**
  99    * number of bits we can store
 100    */
 101   @Override
 102   public int size() {
 103     return 64;
 104   }
 105
 106   /**
 107    * index of highest set bit + 1
 108    */
 109   @Override
 110   public int length() {
 111     return 64 - Long.numberOfLeadingZeros(l0);
 112   }
 113
 114
 115   @Override
 116   public void clear() {
 117     l0 = 0L;
 118     cardinality = 0;
 119   }
 120
 121   @Override
 122   public int nextSetBit (int fromIdx){
 123     if ((fromIdx & INDEX_MASK) == 0){
 124       //int n = Long.numberOfTrailingZeros(l0 & (0xffffffffffffffffL << fromIdx));
 125       int n = Long.numberOfTrailingZeros(l0 >> fromIdx) + fromIdx;
 126       if (n < 64) {
 127         return n;
 128       } else {
 129         return -1;
 130       }
 131     } else {
 132       //throw new IndexOutOfBoundsException("BitSet64 index out of range: " + fromIdx);
 133       return -1;
 134     }
 135   }
 136
 137   @Override
 138   public int nextClearBit (int fromIdx){
 139     if ((fromIdx & INDEX_MASK) == 0){
 140       //int n = Long.numberOfTrailingZeros(~l0 & (0xffffffffffffffffL << fromIdx));
 141       int n = Long.numberOfTrailingZeros(~l0 >> fromIdx) + fromIdx;
 142       if (n < 64) {
 143         return n;
 144       } else {
 145         return -1;
 146       }
 147     } else {
 148       //throw new IndexOutOfBoundsException("BitSet64 index out of range: " + fromIdx);
 149       return -1;
 150     }
 151   }
 152
 153   public void and (BitSet64 other){
 154     l0 &= other.l0;
 155
 156     cardinality = computeCardinality();
 157   }
 158
 159   public void andNot (BitSet64 other){
 160     l0 &= ~other.l0;
 161
 162     cardinality = computeCardinality();
 163   }
 164
 165   public void or (BitSet64 other){
 166     l0 |= other.l0;
 167
 168     cardinality = computeCardinality();
 169   }
 170
 171   @Override
 172   public boolean equals (Object o){
 173     if (o instanceof BitSet64){
 174       BitSet64 other = (BitSet64)o;
 175       if (l0 != other.l0) return false;
 176       return true;
 177     } else {
 178       // <2do> we could compare to a normal java.util.BitSet here
 179       return false;
 180     }
 181   }
 182
 183
 184   /**
 185    * answer the same hashCodes as java.util.BitSet
 186    */
 187   @Override
 188   public int hashCode() {
 189     long hc = 1234;
 190     hc ^= l0;
 191     return (int) ((hc >>32) ^ hc);
 192   }
 193
 194 }