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 bitvectors 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 yeilding each one in order

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

Compares two bit vectors and returns true if both bitvectors 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-vecter. 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]