Class: SplitIoClient::Cache::Filter::BloomFilter

Inherits:
Object
  • Object
show all
Defined in:
lib/splitclient-rb/cache/filter/bloom_filter.rb

Instance Method Summary collapse

Constructor Details

#initialize(capacity, false_positive_probability = 0.001) ⇒ BloomFilter

Returns a new instance of BloomFilter.



9
10
11
12
13
14
 
# File 'lib/splitclient-rb/cache/filter/bloom_filter.rb', line 9

def initialize(capacity, false_positive_probability = 0.001)
  @capacity = capacity.round
  m = best_m(capacity, false_positive_probability)
  @ba = BitArray.new(m.round)
  @k = best_k(capacity)
end

Instance Method Details

#add(string) ⇒ Object 



16
17
18
19
20
21
22
23
24
 
# File 'lib/splitclient-rb/cache/filter/bloom_filter.rb', line 16

def add(string)
  return false if contains?(string)

  positions = hashes(string)
  
  positions.each { |position| @ba[position] = 1 }

  true
end

#clear ⇒ Object 



30
31
32
 
# File 'lib/splitclient-rb/cache/filter/bloom_filter.rb', line 30

def clear
  @ba.size.times { |i| @ba[i] = 0 }
end

#contains?(string) ⇒ Boolean

Returns:

  • (Boolean) 


26
27
28
 
# File 'lib/splitclient-rb/cache/filter/bloom_filter.rb', line 26

def contains?(string)
  !hashes(string).any? { |ea| @ba[ea] == 0 }
end