Class: Bloombroom::BitField

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/bloombroom/bits/bit_field.rb

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.



21
22
23
24
 
# File 'lib/bloombroom/bits/bit_field.rb', line 21

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

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



16
17
18
 
# File 'lib/bloombroom/bits/bit_field.rb', line 16

def size
  @size
end

Instance Method Details

#[](position) ⇒ Fixnum Also known as: get

read a bit

Parameters:

  • position (Fixnum) —

    bit position

Returns:

  • (Fixnum) —

    bit value 0/1



40
41
42
 
# File 'lib/bloombroom/bits/bit_field.rb', line 40

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

#[]=(position, value) ⇒ Object

set a bit

Parameters:

  • position (Fixnum) —

    bit position

  • value (Fixnum) —

    bit value 0/1



29
30
31
32
33
34
35
 
# File 'lib/bloombroom/bits/bit_field.rb', line 29

def []=(position, value)
  if value == 0
    @field[position / ELEMENT_WIDTH] &= ~(1 << (position % ELEMENT_WIDTH))
  else
    @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH)
  end
end

#each(&block) ⇒ Object

iterate over each bit



75
76
77
 
# File 'lib/bloombroom/bits/bit_field.rb', line 75

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

#include?(position) ⇒ Boolean

check if bit is set

Parameters:

  • position (Fixnum) —

    bit position

Returns:

  • (Boolean) —

    true if bit is set



62
63
64
 
# File 'lib/bloombroom/bits/bit_field.rb', line 62

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

#set(position) ⇒ Object

set a bit to 1

Parameters:

  • position (Fixnum) —

    bit position



47
48
49
50
 
# File 'lib/bloombroom/bits/bit_field.rb', line 47

def set(position)
  # duplicated code to avoid a method call
  @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH)
end

#to_s ⇒ Object

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



80
81
82
 
# File 'lib/bloombroom/bits/bit_field.rb', line 80

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)



86
87
88
 
# File 'lib/bloombroom/bits/bit_field.rb', line 86

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

#unset(position) ⇒ Object

set a bit to 0

Parameters:

  • position (Fixnum) —

    bit position



54
55
56
57
 
# File 'lib/bloombroom/bits/bit_field.rb', line 54

def unset(position)
  # duplicated code to avoid a method call
  @field[position / ELEMENT_WIDTH] &= ~(1 << (position % ELEMENT_WIDTH))
end

#zero?(position) ⇒ Boolean

check if bit is not set

Parameters:

  • position (Fixnum) —

    bit position

Returns:

  • (Boolean) —

    true if bit is not set



69
70
71
72
 
# File 'lib/bloombroom/bits/bit_field.rb', line 69

def zero?(position)
  # duplicated code to avoid a method call
  @field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) == 0
end