Class: BitField

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/bitfield.rb

Overview

NAME: BitField

   AUTHOR: Peter Cooper
  LICENSE: MIT ( http://www.opensource.org/licenses/mit-license.php )
COPYRIGHT: (c) 2007 Peter Cooper (http://www.petercooper.co.uk/)
  VERSION: v4
  HISTORY: v4 (better support for loading and dumping fields)
           v3 (supports dynamic bitwidths for array elements.. now doing 32 bit widths default)
           v2 (now uses 1 << y, rather than 2 ** y .. it's 21.8 times faster!)
           v1 (first release)

DESCRIPTION: Basic, pure Ruby bit field. Pretty fast (for what it is) and memory efficient.

I've written a pretty intensive test suite for it and it passes great. 
Works well for Bloom filters (the reason I wrote it).

Create a bit field 1000 bits wide
  bf = BitField.new(1000)

Setting and reading bits
  bf[100] = 1
  bf[100]    .. => 1
  bf[100] = 0

More
  bf.to_s = "10101000101010101"  (example)
  bf.total_set         .. => 10  (example - 10 bits are set to "1")

Constant Summary collapse

ELEMENT_WIDTH = 
32

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ BitField

Returns a new instance of BitField.



34
35
36
37
 
# File 'lib/bitfield.rb', line 34

def initialize(size)
  @size = size
  @field = Array.new(((size - 1) / ELEMENT_WIDTH) + 1, 0)
end

Instance Attribute Details

#field ⇒ Object

Returns the value of attribute field.



29
30
31
 
# File 'lib/bitfield.rb', line 29

def field
  @field
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



28
29
30
 
# File 'lib/bitfield.rb', line 28

def size
  @size
end

Instance Method Details

#[](position) ⇒ Object

Read a bit (1/0)



45
46
47
 
# File 'lib/bitfield.rb', line 45

def [](position)
  @field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) > 0 ? 1 : 0
end

#[]=(position, value) ⇒ Object

Set a bit (1/0)



40
41
42
 
# File 'lib/bitfield.rb', line 40

def []=(position, value)
  value == 1 ? @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH) : @field[position / ELEMENT_WIDTH] ^= 1 << (position % ELEMENT_WIDTH)
end

#each(&block) ⇒ Object

Iterate over each bit



50
51
52
 
# File 'lib/bitfield.rb', line 50

def each(&block)
  @size.times { |position| yield self[position] }
end

#to_s ⇒ Object

Returns the field as a string like “0101010100111100,” etc.



55
56
57
 
# File 'lib/bitfield.rb', line 55

def to_s
  inject("") { |a, b| a + b.to_s }
end

#total_set ⇒ Object

Returns the total number of bits that are set (The technique used here is about 6 times faster than using each or inject direct on the bitfield)



61
62
63
 
# File 'lib/bitfield.rb', line 61

def total_set
  @field.inject(0) { |a, byte| a += byte & 1 and byte >>= 1 until byte == 0; a }
end