A BitVector is pretty easy to implement in
Ruby using Ruby's BigNum class. This BitVector however allows you to count the set
bits with the #count
method (or unset bits of flipped bit
vectors) and also to quickly scan the set bits.
BitVector handles four boolean operations;
+&+
+|+
+^+
+~+
bv1 = BitVector.new bv2 = BitVector.new bv3 = BitVector.new bv4 = (bv1 & bv2) | ~bv3
You can also do the operations in-place;
and!
or!
xor!
not!
bv4.and!(bv5).not!
Perhaps the most useful functionality in BitVector is the ability to quickly scan for set bits. To print all set bits;
bv.each {|bit| puts bit }
Alternatively you could use the lower level next
or
next_unset
methods. Note that the each
method
will automatically scan unset bits if the BitVector has been flipped (using
not
).
Returns a new empty bit vector object
static VALUE frb_bv_init(VALUE self) { return self; }
Perform a boolean and operation on bv1
and
bv2
VALUE frb_bv_and(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_and(bv1, bv2)); }
Compares two bit vectors and returns true if both bit vectors have the same bits set.
VALUE frb_bv_eql(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return bv_eq(bv1, bv2) ? Qtrue : Qfalse; }
Get the bit value at i
VALUE frb_bv_get(VALUE self, VALUE rindex) { BitVector *bv; int index = FIX2INT(rindex); GET_BV(bv, self); if (index < 0) { rb_raise(rb_eIndexError, "%d < 0", index); } return bv_get(bv, index) ? Qtrue : Qfalse; }
Set the bit and i to val (true
or
false
).
VALUE frb_bv_set(VALUE self, VALUE rindex, VALUE rstate) { BitVector *bv; int index = FIX2INT(rindex); GET_BV(bv, self); if (index < 0) { rb_raise(rb_eIndexError, "%d < 0", index); } if (RTEST(rstate)) { bv_set(bv, index); } else { bv_unset(bv, index); } return rstate; }
Perform a boolean xor operation on bv1
and
bv2
VALUE frb_bv_xor(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_xor(bv1, bv2)); }
Perform a boolean and operation on bv1
and
bv2
VALUE frb_bv_and(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_and(bv1, bv2)); }
Perform a boolean and operation on bv1
and
bv2
in place on bv1
VALUE frb_bv_and_x(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); bv_and_x(bv1, bv2); return self; }
Clears all set bits in the bit vector. Negated bit vectors will still have all bits set to off.
VALUE frb_bv_clear(VALUE self) { BitVector *bv; GET_BV(bv, self); bv_clear(bv); bv_scan_reset(bv); return self; }
Count the number of bits set in the bit vector. If the bit vector has been
negated using #not
then count the number of unset bits
instead.
VALUE frb_bv_count(VALUE self) { BitVector *bv; GET_BV(bv, self); return INT2FIX(bv->count); }
Iterate through all the set bits in the bit vector yielding each one in order
VALUE frb_bv_each(VALUE self) { BitVector *bv; int bit; GET_BV(bv, self); bv_scan_reset(bv); if (bv->extends_as_ones) { while ((bit = bv_scan_next_unset(bv)) >= 0) { rb_yield(INT2FIX(bit)); } } else { while ((bit = bv_scan_next(bv)) >= 0) { rb_yield(INT2FIX(bit)); } } return self; }
Compares two bit vectors and returns true if both bit vectors have the same bits set.
VALUE frb_bv_eql(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return bv_eq(bv1, bv2) ? Qtrue : Qfalse; }
Get the bit value at i
VALUE frb_bv_get(VALUE self, VALUE rindex) { BitVector *bv; int index = FIX2INT(rindex); GET_BV(bv, self); if (index < 0) { rb_raise(rb_eIndexError, "%d < 0", index); } return bv_get(bv, index) ? Qtrue : Qfalse; }
Used to store bit vectors in Hashes. Especially useful if you want to cache them.
VALUE frb_bv_hash(VALUE self) { BitVector *bv; GET_BV(bv, self); return LONG2NUM(bv_hash(bv)); }
Returns the next set bit in the bit vector scanning from low order to high
order. You should call #reset_scan
before calling this method
if you want to scan from the beginning. It is automatically reset when you
first create the bit vector.
VALUE frb_bv_next(VALUE self) { BitVector *bv; GET_BV(bv, self); return INT2FIX(bv_scan_next(bv)); }
Returns the next set bit in the bit vector scanning from low order to high
order and starting at from
. The scan is inclusive so if
from
is equal to 10 and +bv+ is set it
will return the number 10. If the bit vector has been negated than you
should use the #next_unset_from
method.
VALUE frb_bv_next_from(VALUE self, VALUE rfrom) { BitVector *bv; int from = FIX2INT(rfrom); GET_BV(bv, self); if (from < 0) { from = 0; } return INT2FIX(bv_scan_next_from(bv, from)); }
Returns the next unset bit in the bit vector scanning from low order to
high order. This method should only be called on bit vectors which have
been flipped (negated). You should call #reset_scan
before
calling this method if you want to scan from the beginning. It is
automatically reset when you first create the bit vector.
VALUE frb_bv_next_unset(VALUE self) { BitVector *bv; GET_BV(bv, self); return INT2FIX(bv_scan_next_unset(bv)); }
Returns the next unset bit in the bit vector scanning from low order to
high order and starting at from
. The scan is inclusive so if
from
is equal to 10 and +bv+ is unset
it will return the number 10. If the bit vector has not been negated than
you should use the #next_from
method.
VALUE frb_bv_next_unset_from(VALUE self, VALUE rfrom) { BitVector *bv; int from = FIX2INT(rfrom); GET_BV(bv, self); if (from < 0) { from = 0; } return INT2FIX(bv_scan_next_unset_from(bv, from)); }
Perform a boolean not operation on bv
VALUE frb_bv_not(VALUE self) { BitVector *bv; GET_BV(bv, self); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_not(bv)); }
Perform a boolean not operation on bv
in-place
VALUE frb_bv_not_x(VALUE self) { BitVector *bv; GET_BV(bv, self); bv_not_x(bv); return self; }
Perform a boolean or operation on bv1
and
bv2
VALUE frb_bv_or(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_or(bv1, bv2)); }
Perform a boolean or operation on bv1
and
bv2
in place on bv1
VALUE frb_bv_or_x(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); bv_or_x(bv1, bv2); return self; }
Resets the BitVector ready for scanning. You
should call this method before calling #next
or
#next_unset
. It isn't necessary for the other scan methods
or for the #each
method.
VALUE frb_bv_reset_scan(VALUE self) { BitVector *bv; GET_BV(bv, self); bv_scan_reset(bv); return self; }
Set the bit at i to on (true
)
VALUE frb_bv_set_on(VALUE self, VALUE rindex) { frb_bv_set(self, rindex, Qtrue); return self; }
Iterate through all the set bits in the bit vector adding the index of each set bit to an array. This is useful if you want to perform array methods on the bit vector. If you want to convert an array to a bit_vector simply do this;
bv = [1, 12, 45, 367, 455].inject(BitVector.new) {|bv, i| bv.set(i)}
VALUE frb_bv_to_a(VALUE self) { BitVector *bv; int bit; VALUE ary; GET_BV(bv, self); ary = rb_ary_new(); bv_scan_reset(bv); if (bv->extends_as_ones) { while ((bit = bv_scan_next_unset(bv)) >= 0) { rb_ary_push(ary, INT2FIX(bit)); } } else { while ((bit = bv_scan_next(bv)) >= 0) { rb_ary_push(ary, INT2FIX(bit)); } } return ary; }
Set the bit at i to off (false
)
VALUE frb_bv_set_off(VALUE self, VALUE rindex) { frb_bv_set(self, rindex, Qfalse); return self; }
Perform a boolean xor operation on bv1
and
bv2
VALUE frb_bv_xor(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_xor(bv1, bv2)); }
Perform a boolean xor operation on bv1
and
bv2
in place on bv1
VALUE frb_bv_xor_x(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); bv_xor_x(bv1, bv2); return self; }
Perform a boolean or operation on bv1
and
bv2
VALUE frb_bv_or(VALUE self, VALUE other) { BitVector *bv1, *bv2; GET_BV(bv1, self); GET_BV(bv2, other); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_or(bv1, bv2)); }
Perform a boolean not operation on bv
VALUE frb_bv_not(VALUE self) { BitVector *bv; GET_BV(bv, self); return Data_Wrap_Struct(cBitVector, NULL, &bv_destroy, bv_not(bv)); }