### Home Classes Methods

### In Files

- ext/r_utils.c

### Parent

Object

### Methods

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

### Files

- MIT-LICENSE
- README
- TODO
- TUTORIAL

### Class/Module Index

Quicksearch

- Ferret
- Ferret::Analysis
- Ferret::Analysis::Analyzer
- Ferret::Analysis::AsciiLetterAnalyzer
- Ferret::Analysis::AsciiLetterTokenizer
- Ferret::Analysis::AsciiLowerCaseFilter
- Ferret::Analysis::AsciiStandardAnalyzer
- Ferret::Analysis::AsciiStandardTokenizer
- Ferret::Analysis::AsciiWhiteSpaceAnalyzer
- Ferret::Analysis::AsciiWhiteSpaceTokenizer
- Ferret::Analysis::HyphenFilter
- Ferret::Analysis::LetterAnalyzer
- Ferret::Analysis::LetterTokenizer
- Ferret::Analysis::LowerCaseFilter
- Ferret::Analysis::MappingFilter
- Ferret::Analysis::PerFieldAnalyzer
- Ferret::Analysis::RegExpAnalyzer
- Ferret::Analysis::RegExpTokenizer
- Ferret::Analysis::StandardAnalyzer
- Ferret::Analysis::StandardTokenizer
- Ferret::Analysis::StemFilter
- Ferret::Analysis::StopFilter
- Ferret::Analysis::Token
- Ferret::Analysis::TokenStream
- Ferret::Analysis::WhiteSpaceAnalyzer
- Ferret::Analysis::WhiteSpaceTokenizer
- Ferret::BlankSlate
- Ferret::BoostMixin
- Ferret::Browser
- Ferret::Browser::Controller
- Ferret::Browser::Delegator
- Ferret::Browser::DocumentController
- Ferret::Browser::ErrorController
- Ferret::Browser::HelpController
- Ferret::Browser::HomeController
- Ferret::Browser::TermController
- Ferret::Browser::TermVectorController
- Ferret::Browser::ViewHelper
- Ferret::Document
- Ferret::Field
- Ferret::FieldSymbol
- Ferret::FieldSymbolMethods
- Ferret::FileNotFoundError
- Ferret::Index
- Ferret::Index::FieldInfo
- Ferret::Index::FieldInfos
- Ferret::Index::Index
- Ferret::Index::IndexReader
- Ferret::Index::IndexWriter
- Ferret::Index::LazyDoc
- Ferret::Index::LazyDoc::LazyDocData
- Ferret::Index::TermDocEnum
- Ferret::Index::TermEnum
- Ferret::Index::TermVector
- Ferret::Index::TermVector::TVOffsets
- Ferret::Index::TermVector::TVTerm
- Ferret::ParseError
- Ferret::QueryParser
- Ferret::QueryParser::QueryParseException
- Ferret::Search
- Ferret::Search::BooleanQuery
- Ferret::Search::BooleanQuery::BooleanClause
- Ferret::Search::ConstantScoreQuery
- Ferret::Search::Explanation
- Ferret::Search::Filter
- Ferret::Search::FilteredQuery
- Ferret::Search::FuzzyQuery
- Ferret::Search::Hit
- Ferret::Search::MatchAllQuery
- Ferret::Search::MultiSearcher
- Ferret::Search::MultiTermQuery
- Ferret::Search::PhraseQuery
- Ferret::Search::PrefixQuery
- Ferret::Search::Query
- Ferret::Search::QueryFilter
- Ferret::Search::RangeFilter
- Ferret::Search::RangeQuery
- Ferret::Search::Searcher
- Ferret::Search::Sort
- Ferret::Search::SortField
- Ferret::Search::Spans
- Ferret::Search::Spans::SpanFirstQuery
- Ferret::Search::Spans::SpanMultiTermQuery
- Ferret::Search::Spans::SpanNearQuery
- Ferret::Search::Spans::SpanNotQuery
- Ferret::Search::Spans::SpanOrQuery
- Ferret::Search::Spans::SpanPrefixQuery
- Ferret::Search::Spans::SpanTermQuery
- Ferret::Search::TermQuery
- Ferret::Search::TopDocs
- Ferret::Search::TypedRangeFilter
- Ferret::Search::TypedRangeQuery
- Ferret::Search::WildcardQuery
- Ferret::StateError
- Ferret::Store
- Ferret::Store::Directory
- Ferret::Store::FSDirectory
- Ferret::Store::Lock
- Ferret::Store::Lock::LockError
- Ferret::Store::RAMDirectory
- Ferret::Utils
- Ferret::Utils::BitVector
- Ferret::Utils::MultiMapper
- Ferret::Utils::PriorityQueue
- WEBrick
- WEBrick::FerretBrowserHandler
- Date
- DateTime
- FileUtils
- Float
- Integer
- String
- Symbol
- Time

No matching classes.

# Ferret::Utils::BitVector

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

### Public Class Methods

new() → new_bit_vector click to toggle source

Returns a new empty bit vector object

    static VALUE
    frb_bv_init(VALUE self)
    {
        return self;
    }

### Public Instance Methods

bv1 & bv2 → anded_bv click to toggle source
and(bv2) → anded_bv

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

bv1 == bv2 → bool click to toggle source
bv1 != bv2 → bool
eql(bv2) → bool

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(i) → bool click to toggle source
bv[i] → bool

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

bv[i] = bool → bool click to toggle source

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

bv1 ^ bv2 → xored_bv click to toggle source
xor(bv2) → xored_bv

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

bv1 & bv2 → anded_bv click to toggle source
and(bv2) → anded_bv

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

and!(bv2) → self click to toggle source

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

clear → self click to toggle source

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 → bit_count click to toggle source

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

each { |bit_num| } click to toggle source

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

bv1 == bv2 → bool click to toggle source
bv1 != bv2 → bool
eql(bv2) → bool

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(i) → bool click to toggle source
bv[i] → bool

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

hash → int click to toggle source

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

next → bit_num click to toggle source

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

next_from(from) → bit_num click to toggle source

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

next_unset → bit_num click to toggle source

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

next_unset_from(from) → bit_num click to toggle source

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

~bv → bv click to toggle source
not → bv

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

not! → self click to toggle source

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

bv1 | bv2 → ored_bv click to toggle source
or(bv2) → ored_bv

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

or!(bv2) → self click to toggle source

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

reset_scan → self click to toggle source

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(i) → self click to toggle source

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

to_a click to toggle source

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

unset(i) → self click to toggle source

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

bv1 ^ bv2 → xored_bv click to toggle source
xor(bv2) → xored_bv

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

xor!(bv2) → self click to toggle source

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

bv1 | bv2 → ored_bv click to toggle source
or(bv2) → ored_bv

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

~bv → bv click to toggle source
not → bv

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

[Validate]

Generated with the Darkfish Rdoc Generator 2.