/**
* A sequence of bits with a fixed length. This class performs
* important error-checking not found in the Java BitSet and
- * BigInteger classes.
+ * BigInteger classes. Bits are numbered starting with LSB as "bit
+ * zero".
+ *
+ * The toLong(), set(long), and setAndSignExtend(long) methods offer
+ * the following guarantee: for all i, unless an exception is thrown
+ * the following identities will hold:
+ *
+ * bv.set(i).toLong() == i
+ * bv.equals(new BitVector(bv.length()).set(bv.toLong()))
+ *
+ * An exception is thrown if the BitVector in question is more than
+ * 64 bits long (in which case it cannot be converted to a long with
+ * toLong()) or the long in question cannot be represented as a two's
+ * complement number using the number of bits allocated in the
+ * BitVector.
*/
-public class BitVector {
+public class BitVector implements DeferredBitVector {
private final boolean[] bits;
return this;
}
+ public BitVector set(BitVector bv) {
+ if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
+ if (length()!=bv.length()) throw new RuntimeException("attempt to copy between BitVectors of unequal sizes");
+ for(int i=0; i<length(); i++)
+ set(i, bv.get(i));
+ return this;
+ }
+
/** copy the low-order bits of the argument into this BitVector and sign extend; returns <tt>this</tt> */
public BitVector setAndSignExtend(long value) {
if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
- for(int i=0; i<Math.min(length(), 64); i++)
- set(i, ((value >>> i) & 1L) != 0);
- if (value < 0)
- for(int i=64; i<length(); i++)
- set(i, true);
+ for(int i=0; i<length(); i++)
+ set(i, i<64 ? (((value >>> i) & 1L) != 0) : value<0 ? true : false);
return this;
}
+ /** returns the length of this BitVector */
public int length() {
return bits.length;
}
- public void set(int bit, boolean value) {
+ /** sets the specified bit to the given value */
+ public BitVector set(int bit, boolean value) {
if (immutable) throw new RuntimeException("attempt to modify an immutable BitVector");
bits[bit] = value;
+ return this;
}
+ /** returns the value of the specified bit */
public boolean get(int bit) {
return bits[bit];
}
+ /** get a sub-BitVector of a BitVector */
+ public BitVector get(int high, int low) {
+ if (low < 0 || high < 0 || high>low)
+ throw new RuntimeException("attempt to invoke BitVector("+high+","+low+")");
+ if (high > length()-1)
+ throw new RuntimeException("attempt to invoke BitVector("+high+","+low+") on an "+length()+"-bit BitVector");
+ BitVector ret = new BitVector(1+high-low);
+ for(int i=low; i<=high; i++)
+ ret.set(i-low, get(i));
+ return ret;
+ }
+
public String toString() {
StringBuffer ret = new StringBuffer();
ret.append(length()+"");
return ret.toString();
}
+ /** makes this BitVector immutable; cannot be undone */
public void setImmutable() {
immutable = true;
}
+ /** indicates if this BitVector has been marked as immutable */
+ public boolean getImmutable() {
+ return immutable;
+ }
+
public int hashCode() {
int ret = 0;
for(int i=0; i<length(); i++)
return ret;
}
+ public boolean equalsZeroExtended(BitVector bv) {
+ for(int i=0; i<Math.min(bv.bits.length, bits.length); i++)
+ if (bits[i] != bv.bits[i])
+ return false;
+ return true;
+ }
+
public boolean equals(Object o) {
if (o==null || !(o instanceof BitVector)) return false;
BitVector bv = (BitVector)o;
if (bv.bits.length != bits.length) return false;
- for(int i=0; i<bits.length; i++)
- if (bits[i] != bv.bits[i])
- return false;
- return true;
+ return equalsZeroExtended(bv);
+ }
+
+ /**
+ * Converts this BitVector to a long, sign-extending if
+ * length()<64 and throwing an exception if length()>64
+ */
+ public long toLong() {
+ if (length() > 64)
+ throw new RuntimeException("a " + length() + "-bit BitVector cannot fit in a Java long");
+ long ret = 0;
+ for(int i=0; i<64; i++)
+ if (i<length() ? get(i) : get(length()-1))
+ ret |= (1L << i);
+ return ret;
+ }
+
+ public BitVector getBitVector() {
+ return this;
+ }
+
+ public BitVector and(BitVector bv) {
+ if (bv.length() != this.length())
+ throw new RuntimeException("attempt to invoke BitVector.and() on BitVectors "+
+ "of mismatched size: this="+this+", bv="+bv);
+ BitVector ret = new BitVector(length());
+ for(int i=0; i<length(); i++)
+ ret.set(i, get(i) && bv.get(i));
+ return ret;
+ }
+
+ public BitVector or(BitVector bv) {
+ if (bv.length() != this.length())
+ throw new RuntimeException("attempt to invoke BitVector.or() on BitVectors "+
+ "of mismatched size: this="+this+", bv="+bv);
+ BitVector ret = new BitVector(length());
+ for(int i=0; i<length(); i++)
+ ret.set(i, get(i) || bv.get(i));
+ return ret;
+ }
+
+ public BitVector not() {
+ BitVector ret = new BitVector(length());
+ for(int i=0; i<length(); i++)
+ ret.set(i, !get(i));
+ return ret;
}
}