Class: Bloombroom::BitBucketField

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

Constant Summary collapse

ELEMENT_WIDTH = 
32

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(bits, size) ⇒ BitBucketField

new BitBucketField

Parameters:

  • bits (Fixnum) —

    number of bits per bucket

  • size (Fixnum) —

    number of buckets in field



23
24
25
26
27
28
29
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 23

def initialize(bits, size)
  @size = size
  @bits = bits
  @buckets_per_element = ELEMENT_WIDTH / bits
  @field = Array.new(((size - 1) / @buckets_per_element) + 1, 0)
  @bucket_mask = (2 ** @bits) - 1
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



15
16
17
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 15

def size
  @size
end

Instance Method Details

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

read a bucket

Parameters:

  • position (Fixnum) —

    bucket position

Returns:

  • (Fixnum) —

    bucket value



48
49
50
51
52
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 48

def [](position)
  element, offset = position.divmod(@buckets_per_element)
  shift_bits = (position % @buckets_per_element) * @bits
  (@field[element] & (@bucket_mask << shift_bits)) >> shift_bits
end

#[]=(position, value) ⇒ Object Also known as: set

set a bucket

Parameters:

  • position (Fixnum) —

    bucket position

  • value (Fixnum) —

    bucket value



34
35
36
37
38
39
40
41
42
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 34

def []=(position, value)
  element, offset = position.divmod(@buckets_per_element)
  shift_bits = offset * @bits
  if value == 0
    @field[element] &= ~(@bucket_mask << shift_bits)
  else
    @field[element] = (@field[element] & ~(@bucket_mask << shift_bits)) | value << shift_bits
  end
end

#dec(position) ⇒ Object 



64
65
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 64

def dec(position)
end

#each(&block) ⇒ Object

iterate over each bucket



68
69
70
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 68

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

#inc(position) ⇒ Object 



61
62
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 61

def inc(position)
end

#to_s(base = 2) ⇒ Object

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



73
74
75
76
77
78
79
80
81
82
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 73

def to_s(base = 2)
  case base 
  when 2
    inject("") { |a, b| a + "%0#{@bits}b " % b }.strip
  when 10
    self.inject("") { |a, b| a + "%1d " % b }.strip
  else
    raise(ArgumentError, "unsupported base")
  end
end

#total_set ⇒ Object

returns the total number of non zero buckets



85
86
87
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 85

def total_set
  self.inject(0) { |a, bucket| a += bucket.zero? ? 0 : 1; a }
end

#zero?(position) ⇒ Boolean

Returns:

  • (Boolean) 


55
56
57
58
59
 
# File 'lib/bloombroom/bits/bit_bucket_field.rb', line 55

def zero?(position)
  element, offset = position.divmod(@buckets_per_element)
  shift_bits = (position % @buckets_per_element) * @bits
  (@field[element] & (@bucket_mask << shift_bits)) == 0
end