class My::Bitmap

使用 ruby 字符串实现的 bitmap,并不比 set 快多少,但是很节约内存(数字比较小的情况)

Attributes

count[R]
max_value[R]

Public Class Methods

new(max_value) click to toggle source
# File lib/my/bitmap.rb, line 7
def initialize(max_value)
  @max_value = max_value
  @bitmap = "\0".b * (max_value/8 + 1)
  @count = 0
end

Public Instance Methods

<<(value) click to toggle source
# File lib/my/bitmap.rb, line 13
def <<(value)
  raise IndexError, 'out of range' if value > max_value || value < 1
  bytes, bits = value.divmod(8)
  if bits > 0
    mask = 1 << (8 - bits)
  else
    bytes -= 1
    mask = 1
  end
  int = @bitmap[bytes].ord
  return value if int & mask > 0 # 已经存在
  @count += 1
  @bitmap[bytes] = (int | mask).chr
  value
end
to_s() click to toggle source
# File lib/my/bitmap.rb, line 29
def to_s
  @bitmap.chars.map{|c| c.ord.to_s(2).rjust(8, '0') }.join[0...max_value]
end