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;

- +and!+
- +or!+
- +xor!+
- +not!+

       bv4.and!(bv5).not!

## 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

BitVector.new() → new_bv

Returns a new empty bit vector object

### Public Instance methods

bv1 & bv2 → anded_bv
bv1.and(bv2) → anded_bv

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

bv1 == bv2 → bool
bv1 != bv2 → bool
bv1.eql(bv2) → bool

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

bv.get(i) → bool
bv[i] → bool

Get the bit value at i

bv[i] = bool → bool

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

bv1 ^ bv2 → xored_bv
bv1.xor(bv2) → xored_bv

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

bv1 & bv2 → anded_bv
bv1.and(bv2) → anded_bv

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

bv1.and!(bv2) → self

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

bv.clear → self

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

bv.count → bit_count

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.

bv.each { |bit_num| }

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

bv1 == bv2 → bool
bv1 != bv2 → bool
bv1.eql(bv2) → bool

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

bv.get(i) → bool
bv[i] → bool

Get the bit value at i

bv.hash → int

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

bv.next → bit_num

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.

bv.next_from(from) → bit_num

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.

bv.next_unset → bit_num

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.

bv.next_unset_from(from) → bit_num

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.

~bv → bv
bv.not → bv

Perform a boolean not operation on `bv`

bv.not! → self

Perform a boolean not operation on `bv` in-place

bv1 | bv2 → ored_bv
bv1.or(bv2) → ored_bv

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

bv1.or!(bv2) → self

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

bv.reset_scan → 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.

bv.set(i) → self

Set the bit at i to on (`true`)

bv.to_a

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

bv.unset(i) → self

Set the bit at i to off (`false`)

bv1 ^ bv2 → xored_bv
bv1.xor(bv2) → xored_bv

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

bv1.xor!(bv2) → self

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

bv1 | bv2 → ored_bv
bv1.or(bv2) → ored_bv

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

~bv → bv
bv.not → bv

Perform a boolean not operation on `bv`

[Validate]