marina/testCode/edu/berkeley/fleet/api/BitVector.java

   1 package edu.berkeley.fleet.api;
   2
   3 /**
   4  *  A sequence of bits with a fixed length.  This class performs
   5  *  important error-checking not found in the Java BitSet and
   6  *  BigInteger classes.  Bits are numbered starting with LSB as "bit
   7  *  zero".
   8  *
   9  *  The toLong(), set(long), and setAndSignExtend(long) methods offer
  10  *  the following guarantee: for all i, unless an exception is thrown
  11  *  the following identities will hold:
  12  *
  13  *     bv.set(i).toLong() == i
  14  *     bv.equals(new BitVector(bv.length()).set(bv.toLong()))
  15  *
  16  *  An exception is thrown if the BitVector in question is more than
  17  *  64 bits long (in which case it cannot be converted to a long with
  18  *  toLong()) or the long in question cannot be represented as a two's
  19  *  complement number using the number of bits allocated in the
  20  *  BitVector.
  21  */
  22 public class BitVector implements DeferredBitVector {
  23
  24     private final boolean[] bits;
  25
  26     private boolean immutable = false;
  27
  28     public BitVector(int length) {
  29         this.bits = new boolean[length];
  30     }
  31
  32     /** copy constructor */
  33     public BitVector(BitVector bv) {
  34         this(bv.length());
  35         for(int i=0; i<bv.length(); i++)
  36             set(i, bv.get(i));
  37     }
  38
  39     /** copy the low-order bits of the argument into this BitVector; returns <tt>this</tt> */
  40     public BitVector set(long value) {
  41         if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
  42         for(int i=0; i<length(); i++)
  43             set(i, ((value >>> i) & 1L) != 0);
  44         return this;
  45     }
  46
  47     public BitVector set(BitVector bv) {
  48         if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
  49         if (length()!=bv.length()) throw new RuntimeException("attempt to copy between BitVectors of unequal sizes");
  50         for(int i=0; i<length(); i++)
  51             set(i, bv.get(i));
  52         return this;
  53     }
  54
  55     /** copy the low-order bits of the argument into this BitVector and sign extend; returns <tt>this</tt> */
  56     public BitVector setAndSignExtend(long value) {
  57         if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
  58         for(int i=0; i<length(); i++)
  59             set(i, i<64 ? (((value >>> i) & 1L) != 0) : value<0 ? true : false);
  60         return this;
  61     }
  62
  63     /** returns the length of this BitVector */
  64     public int length() {
  65         return bits.length;
  66     }
  67
  68     /** sets the specified bit to the given value */
  69     public BitVector set(int bit, boolean value) {
  70         if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
  71         bits[bit] = value;
  72         return this;
  73     }
  74
  75     /** returns the value of the specified bit */
  76     public boolean get(int bit) {
  77         return bits[bit];
  78     }
  79
  80     /** get a sub-BitVector of a BitVector */
  81     public BitVector get(int high, int low) {
  82         if (low < 0 || high < 0 || high>low)
  83             throw new RuntimeException("attempt to invoke BitVector("+high+","+low+")");
  84         if (high > length()-1)
  85             throw new RuntimeException("attempt to invoke BitVector("+high+","+low+") on an "+length()+"-bit BitVector");
  86         BitVector ret = new BitVector(1+high-low);
  87         for(int i=low; i<=high; i++)
  88             ret.set(i-low, get(i));
  89         return ret;
  90     }
  91
  92     public String toString() {
  93         StringBuffer ret = new StringBuffer();
  94         ret.append(length()+"");
  95         ret.append("'b");
  96         for(int i=length()-1; i>=0; i--)
  97             ret.append(get(i) ? '1' : '0');
  98         return ret.toString();
  99     }
 100
 101     /** makes this BitVector immutable; cannot be undone */
 102     public void setImmutable() {
 103         immutable = true;
 104     }
 105
 106     /** indicates if this BitVector has been marked as immutable */
 107     public boolean getImmutable() {
 108         return immutable;
 109     }
 110
 111     public int hashCode() {
 112         int ret = 0;
 113         for(int i=0; i<length(); i++)
 114             if (get(i))
 115                 ret ^= (1L << (i % 32));
 116         return ret;
 117     }
 118
 119     public boolean equalsZeroExtended(BitVector bv) {
 120         for(int i=0; i<Math.min(bv.bits.length, bits.length); i++)
 121             if (bits[i] != bv.bits[i])
 122                 return false;
 123         return true;
 124     }
 125
 126     public boolean equals(Object o) {
 127         if (o==null || !(o instanceof BitVector)) return false;
 128         BitVector bv = (BitVector)o;
 129         if (bv.bits.length != bits.length) return false;
 130         return equalsZeroExtended(bv);
 131     }
 132
 133     /**
 134      *  Converts this BitVector to a long, sign-extending if
 135      *  length()<64 and throwing an exception if length()>64
 136      */
 137     public long toLong() {
 138         if (length() > 64)
 139             throw new RuntimeException("a " + length() + "-bit BitVector cannot fit in a Java long");
 140         long ret = 0;
 141         for(int i=0; i<64; i++)
 142             if (i<length() ? get(i) : get(length()-1))
 143                 ret |= (1L << i);
 144         return ret;
 145     }
 146
 147     public BitVector getBitVector() {
 148         return this;
 149     }
 150 }
 151
 152