Class Ferret::Utils::BitVector
In: ext/r_utils.c
Parent: Object

Summary

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.

Boolean Operations

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;

Set Bit Scanning

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).

Methods

&   ==   []   []=   ^   and   and!   clear   count   each   eql?   get   hash   new   next   next_from   next_unset   next_unset_from   not   not!   or   or!   reset_scan   set   to_a   unset   xor   xor!   |   ~  

Public Class methods

Returns a new empty bit vector object

Public Instance methods

Perform a boolean and operation on +bv1+ and +bv2+

Compares two bit vectors and returns true if both bit vectors have the same bits set.

Set the bit and i to val (true or false).

Perform a boolean xor operation on +bv1+ and +bv2+

Perform a boolean and operation on +bv1+ and +bv2+

Perform a boolean and operation on +bv1+ and +bv2+ in place on +bv1+

Clears all set bits in the bit vector. Negated bit vectors will still have all bits set to off.

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.

Iterate through all the set bits in the bit vector yielding each one in order

Compares two bit vectors and returns true if both bit vectors have the same bits set.

Used to store bit vectors in Hashes. Especially useful if you want to cache them.

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.

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 +next_unset_from+ method.

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.

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 +next_from+ method.

Perform a boolean not operation on bv

Perform a boolean not operation on bv in-place

Perform a boolean or operation on +bv1+ and +bv2+

Perform a boolean or operation on +bv1+ and +bv2+ in place on +bv1+

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.

Set the bit at i to on (true)

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)}

Set the bit at i to off (false)

Perform a boolean xor operation on +bv1+ and +bv2+

Perform a boolean xor operation on +bv1+ and +bv2+ in place on +bv1+

Perform a boolean or operation on +bv1+ and +bv2+

Perform a boolean not operation on bv

[Validate]