Object
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 # 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).
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 # 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 # 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[10]+ is set it will return the number 10. If the bit vector has been negated than you should use the # 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 # 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[10]+ is unset it will return the number 10. If the bit vector has not been negated than you should use the # 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; }
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; }
Disabled; run with --debug to generate this.
Generated with the Darkfish Rdoc Generator 1.1.6.