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)

Constant Summary

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

#fieldObject

Returns the value of attribute field



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

def field
  @field
end

#sizeObject (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_sObject

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_setObject

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