Class: My::Bitmap

Inherits:
Object
  • Object
show all
Defined in:
lib/my/bitmap.rb

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_value) ⇒ Bitmap

Returns a new instance of Bitmap.



7
8
9
10
11
 
# 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

Instance Attribute Details

#count ⇒ Object (readonly)

Returns the value of attribute count.



5
6
7
 
# File 'lib/my/bitmap.rb', line 5

def count
  @count
end

#max_value ⇒ Object (readonly)

Returns the value of attribute max_value.



5
6
7
 
# File 'lib/my/bitmap.rb', line 5

def max_value
  @max_value
end

Instance Method Details

#<<(value) ⇒ Object

Raises:

  • (IndexError) 


13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# 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 ⇒ Object 



29
30
31
 
# 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