src/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 {
  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     /** copy the low-order bits of the argument into this BitVector and sign extend; returns <tt>this</tt> */
  48     public BitVector setAndSignExtend(long value) {
  49         if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
  50         for(int i=0; i<length(); i++)
  51             set(i, i<64 ? (((value >>> i) & 1L) != 0) : value<0 ? true : false);
  52         return this;
  53     }
  54
  55     /** returns the length of this BitVector */
  56     public int length() {
  57         return bits.length;
  58     }
  59
  60     /** sets the specified bit to the given value */
  61     public BitVector set(int bit, boolean value) {
  62         if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
  63         bits[bit] = value;
  64         return this;
  65     }
  66
  67     /** returns the value of the specified bit */
  68     public boolean get(int bit) {
  69         return bits[bit];
  70     }
  71
  72     /** get a sub-BitVector of a BitVector */
  73     public BitVector get(int high, int low) {
  74         if (low < 0 || high < 0 || high>low)
  75             throw new RuntimeException("attempt to invoke BitVector("+high+","+low+")");
  76         if (high > length()-1)
  77             throw new RuntimeException("attempt to invoke BitVector("+high+","+low+") on an "+length()+"-bit BitVector");
  78         BitVector ret = new BitVector(1+high-low);
  79         for(int i=low; i<=high; i++)
  80             ret.set(i-low, get(i));
  81         return ret;
  82     }
  83
  84     public String toString() {
  85         StringBuffer ret = new StringBuffer();
  86         ret.append(length()+"");
  87         ret.append("'b");
  88         for(int i=length()-1; i>=0; i--)
  89             ret.append(get(i) ? '1' : '0');
  90         return ret.toString();
  91     }
  92
  93     /** makes this BitVector immutable; cannot be undone */
  94     public void setImmutable() {
  95         immutable = true;
  96     }
  97
  98     /** indicates if this BitVector has been marked as immutable */
  99     public boolean getImmutable() {
 100         return immutable;
 101     }
 102
 103     public int hashCode() {
 104         int ret = 0;
 105         for(int i=0; i<length(); i++)
 106             if (get(i))
 107                 ret ^= (1L << (i % 32));
 108         return ret;
 109     }
 110
 111     public boolean equalsZeroExtended(BitVector bv) {
 112         for(int i=0; i<Math.min(bv.bits.length, bits.length); i++)
 113             if (bits[i] != bv.bits[i])
 114                 return false;
 115         return true;
 116     }
 117
 118     public boolean equals(Object o) {
 119         if (o==null || !(o instanceof BitVector)) return false;
 120         BitVector bv = (BitVector)o;
 121         if (bv.bits.length != bits.length) return false;
 122         return equalsZeroExtended(bv);
 123     }
 124
 125     /**
 126      *  Converts this BitVector to a long, sign-extending if
 127      *  length()<64 and throwing an exception if length()>64
 128      */
 129     public long toLong() {
 130         if (length() > 64)
 131             throw new RuntimeException("a " + length() + "-bit BitVector cannot fit in a Java long");
 132         long ret = 0;
 133         for(int i=0; i<64; i++)
 134             if (i<length() ? get(i) : get(length()-1))
 135                 ret |= (1L << i);
 136         return ret;
 137     }
 138 }
 139
 140