Class: Ferret::Utils::BitVector

Inherits:
Object
  • Object
show all
Defined in:
lib/ferret/utils/bit_vector.rb

Overview

Optimized implementation of a vector of bits.

* a count() method, which efficiently computes the number of one bits
* optimized read from and write to disk
* inlinable get() method

Constant Summary collapse

BYTE_COUNTS =

table of bits/byte

[ # table of bits/byte
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
]

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ BitVector

Returns a new instance of BitVector.



11
12
13
14
 
# File 'lib/ferret/utils/bit_vector.rb', line 11

def initialize
  @bits = 0
  @count = -1
end

Instance Attribute Details

#bits ⇒ Object

Returns the value of attribute bits.



9
10
11
 
# File 'lib/ferret/utils/bit_vector.rb', line 9

def bits
  @bits
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



8
9
10
 
# File 'lib/ferret/utils/bit_vector.rb', line 8

def size
  @size
end

Class Method Details

.bignum_to_string(num) ⇒ Object

converts a BigNum into a string



106
107
108
109
110
111
112
113
 
# File 'lib/ferret/utils/bit_vector.rb', line 106

def BitVector.bignum_to_string(num)
  str = []
  while (num > 0)
    str << (num & 0xff)
    num >>= 8
  end
  return str.pack("C*")
end

.read(d, name) ⇒ Object

Constructs a bit vector from the file name in Directory d, as written by the @link #writeendmethod.



85
86
87
88
89
90
91
92
93
94
 
# File 'lib/ferret/utils/bit_vector.rb', line 85

def BitVector.read(d, name)
  bv = BitVector.new
  input = d.open_input(name)
  begin 
    bv.bits = string_to_bignum(input.read_string())
  ensure 
    input.close()
  end
  return bv
end

.string_to_bignum(str) ⇒ Object

converts a string into a bignum



116
117
118
119
120
121
 
# File 'lib/ferret/utils/bit_vector.rb', line 116

def BitVector.string_to_bignum(str)
  str = str.unpack("C*") 
  num = 0
  str.reverse.each {|c| num = ((num << 8) | c) }
  return num
end

Instance Method Details

#clear(bit) ⇒ Object

Sets the value of bit to zero.



23
24
25
26
 
# File 'lib/ferret/utils/bit_vector.rb', line 23

def clear(bit) 
  @bits &= ~(1 << bit)
  @count = -1
end

#count ⇒ Object

Returns the total number of one bits in this vector. This is efficiently computed and cached, so that, if the vector is not changed, no recomputation is done for repeated calls.



38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/ferret/utils/bit_vector.rb', line 38

def count() 
  # if the vector has been modified
  if (@count == -1) 
    c = 0
    tmp = @bits
    while tmp > 0
      c += BYTE_COUNTS[tmp & 0xFF] # sum bits per byte
      tmp >>= 8
    end
    @count = c
  end
  return @count
end

#get(bit) ⇒ Object Also known as: []

Returns true if bit is one and false if it is zero.



30
31
32
 
# File 'lib/ferret/utils/bit_vector.rb', line 30

def get(bit) 
  return (@bits & (1 << bit)) != 0
end

#set(bit) ⇒ Object

Sets the value of bit to one.



17
18
19
20
 
# File 'lib/ferret/utils/bit_vector.rb', line 17

def set(bit) 
  @bits |= 1 << bit
  @count = -1
end

#to_s ⇒ Object 



96
97
98
99
100
101
102
103
 
# File 'lib/ferret/utils/bit_vector.rb', line 96

def to_s
  i = @bits
  while i > 0
    print(i&1)
    i >>= 1
  end
  puts ""
end

#write(d, name) ⇒ Object

Writes this vector to the file name in Directory d, in a format that can be read by the constructor



74
75
76
77
78
79
80
81
 
# File 'lib/ferret/utils/bit_vector.rb', line 74

def write(d, name)
  output = d.create_output(name)
  begin 
    output.write_string(self.class.bignum_to_string(@bits))
  ensure 
    output.close()
  end
end