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 {
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 /** 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);
55 /** returns the length of this BitVector */
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");
67 /** returns the value of the specified bit */
68 public boolean get(int bit) {
72 public String toString() {
73 StringBuffer ret = new StringBuffer();
74 ret.append(length()+"");
76 for(int i=length()-1; i>=0; i--)
77 ret.append(get(i) ? '1' : '0');
78 return ret.toString();
81 /** makes this BitVector immutable; cannot be undone */
82 public void setImmutable() {
86 /** indicates if this BitVector has been marked as immutable */
87 public boolean getImmutable() {
91 public int hashCode() {
93 for(int i=0; i<length(); i++)
95 ret ^= (1L << (i % 32));
99 public boolean equals(Object o) {
100 if (o==null || !(o instanceof BitVector)) return false;
101 BitVector bv = (BitVector)o;
102 if (bv.bits.length != bits.length) return false;
103 for(int i=0; i<bits.length; i++)
104 if (bits[i] != bv.bits[i])
110 * Converts this BitVector to a long, sign-extending if
111 * length()<64 and throwing an exception if length()>64
113 public long toLong() {
115 throw new RuntimeException("a " + length() + "-bit BitVector cannot fit in a Java long");
117 for(int i=0; i<64; i++)
118 if (i<length() ? get(i) : get(length()-1))