src/main/gov/nasa/jpf/util/FixedBitSet.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 import gov.nasa.jpf.JPFException;
  22 import java.util.NoSuchElementException;
  23
  24 /**
  25  * BitSet like interface for fixed size bit sets
  26  *
  27  * We keep this as an interface so that we can have java.util.BitSet
  28  * subclasses as implementations
  29  */
  30 public interface FixedBitSet extends Cloneable, IntSet {
  31
  32   void set (int i);
  33   void set (int i, boolean val);
  34   boolean get (int i);
  35   void clear (int i);
  36
  37   int nextClearBit (int fromIndex);
  38   int nextSetBit (int fromIndex);
  39
  40   boolean isEmpty();
  41   int size();
  42
  43   int cardinality();
  44   int length();
  45   int capacity();
  46
  47   void clear();
  48
  49   void hash (HashData hd);
  50
  51   FixedBitSet clone();
  52 }
  53
  54 /**
  55  * this is the base class for our non java.util.BitSet based FixedBitSet implementations
  56  */
  57 abstract class AbstractFixedBitSet implements FixedBitSet {
  58
  59   class SetBitIterator implements IntIterator {
  60     int cur = 0;
  61     int nBits;
  62
  63     @Override
  64     public void remove() {
  65       if (cur >0){
  66         clear(cur-1);
  67       }
  68     }
  69
  70     @Override
  71     public boolean hasNext() {
  72       return nBits < cardinality;
  73     }
  74
  75     @Override
  76     public int next() {
  77       if (nBits < cardinality){
  78         int idx = nextSetBit(cur);
  79         if (idx >= 0){
  80           nBits++;
  81           cur = idx+1;
  82         }
  83         return idx;
  84
  85       } else {
  86         throw new NoSuchElementException();
  87       }
  88     }
  89   }
  90
  91
  92   protected int cardinality;
  93
  94   @Override
  95   public AbstractFixedBitSet clone(){
  96     try {
  97       return (AbstractFixedBitSet) super.clone();
  98     } catch (CloneNotSupportedException ex) {
  99       throw new JPFException("BitSet64 clone failed");
 100     }
 101   }
 102
 103   @Override
 104   public void set (int i, boolean val){
 105     if (val) {
 106       set(i);
 107     } else {
 108       clear(i);
 109     }
 110   }
 111
 112   @Override
 113   public int cardinality() {
 114     return cardinality;
 115   }
 116
 117   @Override
 118   public boolean isEmpty() {
 119     return (cardinality == 0);
 120   }
 121
 122   @Override
 123   public String toString() {
 124     StringBuilder sb = new StringBuilder();
 125     sb.append('{');
 126
 127     boolean first = true;
 128     for (int i=nextSetBit(0); i>= 0; i = nextSetBit(i+1)){
 129       if (!first){
 130         sb.append(',');
 131       } else {
 132         first = false;
 133       }
 134       sb.append(i);
 135     }
 136
 137     sb.append('}');
 138
 139     return sb.toString();
 140   }
 141
 142   //--- IntSet interface
 143
 144
 145   @Override
 146   public boolean add(int i) {
 147     if (get(i)) {
 148       return false;
 149     } else {
 150       set(i);
 151       return true;
 152     }
 153   }
 154
 155   @Override
 156   public boolean remove(int i) {
 157     if (get(i)) {
 158       clear(i);
 159       return true;
 160     } else {
 161       return false;
 162     }
 163   }
 164
 165   @Override
 166   public boolean contains(int i) {
 167     return get(i);
 168   }
 169
 170   @Override
 171   public IntIterator intIterator() {
 172     return new SetBitIterator();
 173   }
 174
 175 }