1 package edu.berkeley.fleet.api;
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
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:
13 * bv.set(i).toLong() == i
14 * bv.equals(new BitVector(bv.length()).set(bv.toLong()))
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
22 public class BitVector implements DeferredBitVector {
24 private final boolean[] bits;
26 private boolean immutable = false;
28 public BitVector(int length) {
29 this.bits = new boolean[length];
32 /** copy constructor */
33 public BitVector(BitVector bv) {
35 for(int i=0; i<bv.length(); i++)
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);
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++)
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);
63 /** returns the length of this BitVector */
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");
75 /** returns the value of the specified bit */
76 public boolean get(int bit) {
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));
92 public String toString() {
93 StringBuffer ret = new StringBuffer();
94 ret.append(length()+"");
96 for(int i=length()-1; i>=0; i--)
97 ret.append(get(i) ? '1' : '0');
98 return ret.toString();
101 /** makes this BitVector immutable; cannot be undone */
102 public void setImmutable() {
106 /** indicates if this BitVector has been marked as immutable */
107 public boolean getImmutable() {
111 public int hashCode() {
113 for(int i=0; i<length(); i++)
115 ret ^= (1L << (i % 32));
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])
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);
134 * Converts this BitVector to a long, sign-extending if
135 * length()<64 and throwing an exception if length()>64
137 public long toLong() {
139 throw new RuntimeException("a " + length() + "-bit BitVector cannot fit in a Java long");
141 for(int i=0; i<64; i++)
142 if (i<length() ? get(i) : get(length()-1))
147 public BitVector getBitVector() {