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     public String toString() {
  73         StringBuffer ret = new StringBuffer();
  74         ret.append(length()+"");
  75         ret.append("'b");
  76         for(int i=length()-1; i>=0; i--)
  77             ret.append(get(i) ? '1' : '0');
  78         return ret.toString();
  79     }
  80
  81     /** makes this BitVector immutable; cannot be undone */
  82     public void setImmutable() {
  83         immutable = true;
  84     }
  85
  86     /** indicates if this BitVector has been marked as immutable */
  87     public boolean getImmutable() {
  88         return immutable;
  89     }
  90
  91     public int hashCode() {
  92         int ret = 0;
  93         for(int i=0; i<length(); i++)
  94             if (get(i))
  95                 ret ^= (1L << (i % 32));
  96         return ret;
  97     }
  98
  99     public boolean equalsZeroExtended(BitVector bv) {
 100         for(int i=0; i<Math.min(bv.bits.length, bits.length); i++)
 101             if (bits[i] != bv.bits[i])
 102                 return false;
 103         return true;
 104     }
 105
 106     public boolean equals(Object o) {
 107         if (o==null || !(o instanceof BitVector)) return false;
 108         BitVector bv = (BitVector)o;
 109         if (bv.bits.length != bits.length) return false;
 110         return equalsZeroExtended(bv);
 111     }
 112
 113     /**
 114      *  Converts this BitVector to a long, sign-extending if
 115      *  length()<64 and throwing an exception if length()>64
 116      */
 117     public long toLong() {
 118         if (length() > 64)
 119             throw new RuntimeException("a " + length() + "-bit BitVector cannot fit in a Java long");
 120         long ret = 0;
 121         for(int i=0; i<64; i++)
 122             if (i<length() ? get(i) : get(length()-1))
 123                 ret |= (1L << i);
 124         return ret;
 125     }
 126 }
 127
 128