Class: HashTable::SparseBitArray Abstract

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/hashtable/sparse_bit_array.rb

Overview

This class is abstract.

SparseBitArray is an implementation of a bitmap that is sparse by only storing the elements that have non-zero bits set.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SparseBitArray

Returns a new instance of SparseBitArray.



168
169
170
171
 
# File 'lib/hashtable/sparse_bit_array.rb', line 168

def initialize
  @elements = []
  @current_index = -1
end

Instance Attribute Details

#current_index ⇒ Integer (readonly)

This has no visible effect on the external state of a SparseBitArray It’s just used to improve performance in the common case of testing/modifying bits with similar indices.

Returns:

  • (Integer) —

    Pointer to our current Element.



166
167
168
 
# File 'lib/hashtable/sparse_bit_array.rb', line 166

def current_index
  @current_index
end

#elements ⇒ Array<SparseBitArrayElement> (readonly)

Returns The list of Elements.

Returns:



162
163
164
 
# File 'lib/hashtable/sparse_bit_array.rb', line 162

def elements
  @elements
end

Instance Method Details

#clear ⇒ Object 



231
232
233
 
# File 'lib/hashtable/sparse_bit_array.rb', line 231

def clear
  @elements.clear
end

#count ⇒ Object 



227
228
229
 
# File 'lib/hashtable/sparse_bit_array.rb', line 227

def count
  @elements.inject(0) { |c, e| c + e.count }
end

#each(&block) ⇒ Object 



259
260
261
 
# File 'lib/hashtable/sparse_bit_array.rb', line 259

def each(&block)
  @elements.each { |element| element.each(&block) }
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


253
254
255
 
# File 'lib/hashtable/sparse_bit_array.rb', line 253

def empty?
  elements.empty?
end

#first ⇒ Integer

Return -1 if no bits are set.

Returns:

  • (Integer) —

    the first set bit in the bitmap.



237
238
239
240
241
242
 
# File 'lib/hashtable/sparse_bit_array.rb', line 237

def first
  return -1 if elements.empty?

  first = elements.first
  first.index * ELEMENT_SIZE + first.first
end

#last ⇒ Integer

Return -1 if no bits are set.

Returns:

  • (Integer) —

    the last set bit in the bitmap.



246
247
248
249
250
251
 
# File 'lib/hashtable/sparse_bit_array.rb', line 246

def last
  return -1 if elements.empty?

  last = elements.last
  last.index * ELEMENT_SIZE + last.last
end

#reset(index) ⇒ Void

Returns Reset a bit in the bitmap.

Parameters:

  • bit (Integer)

Returns:

  • (Void) —

    Reset a bit in the bitmap



188
189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/hashtable/sparse_bit_array.rb', line 188

def reset(index)
  return if @elements.empty?

  e_index = index / ELEMENT_SIZE
  element_i = lower_bound(e_index)
  element = elements[element_i]
  return if element_i == elements.length || element.index != e_index

  element.reset(index % ELEMENT_SIZE)
  return unless element.empty?

  @elements.delete_at(element_i)
end

#set(index) ⇒ Void

Returns Set a bit in the bitmap.

Parameters:

  • bit (Integer)

Returns:

  • (Void) —

    Set a bit in the bitmap



204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/hashtable/sparse_bit_array.rb', line 204

def set(index)
  e_index = index / ELEMENT_SIZE
  element_i = lower_bound(e_index)
  new_e = elements[element_i]
  unless new_e.nil?
    element_i += 1 if new_e.index < e_index
    new_e = nil if new_e.index != e_index
  end
  @current_index = element_i
  @elements.insert(@current_index, SparseBitArrayElement.new(e_index)) if new_e.nil?
  @elements[@current_index].set(index % ELEMENT_SIZE)
end

#test?(index) ⇒ Boolean

Returns Test a bit in the bitmap.

Parameters:

  • bit (Integer)

Returns:

  • (Boolean) —

    Test a bit in the bitmap



175
176
177
178
179
180
181
182
183
184
 
# File 'lib/hashtable/sparse_bit_array.rb', line 175

def test?(index)
  return false if elements.empty?

  e_index = index / ELEMENT_SIZE
  element_i = lower_bound(e_index)
  last = elements.length
  return false if element_i == last || elements[element_i].index != e_index

  elements[element_i].test?(index % ELEMENT_SIZE)
end

#test_and_set?(index) ⇒ Void

Returns Test, Set a bit in the bitmap.

Parameters:

  • bit (Integer)

Returns:

  • (Void) —

    Test, Set a bit in the bitmap



219
220
221
222
223
224
225
 
# File 'lib/hashtable/sparse_bit_array.rb', line 219

def test_and_set?(index)
  unless test?(index)
    set(Idx)
    return true
  end
  false
end