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.



186
187
188
189
 
# File 'lib/hashtable/sparse_bit_array.rb', line 186

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. attr_reader :current_index

Returns:

  • (Integer) —

    Pointer to our current Element.



184
185
186
 
# File 'lib/hashtable/sparse_bit_array.rb', line 184

def current_index
  @current_index
end

#elements ⇒ Array<SparseBitArrayElement> (readonly)

Returns The list of Elements.

Returns:



179
180
181
 
# File 'lib/hashtable/sparse_bit_array.rb', line 179

def elements
  @elements
end

Instance Method Details

#clear ⇒ Object 



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

def clear
  @elements.clear
end

#count ⇒ Object 



245
246
247
 
# File 'lib/hashtable/sparse_bit_array.rb', line 245

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

#each(&block) ⇒ Object 



277
278
279
 
# File 'lib/hashtable/sparse_bit_array.rb', line 277

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


271
272
273
 
# File 'lib/hashtable/sparse_bit_array.rb', line 271

def empty?
  elements.empty?
end

#first ⇒ Integer

Return -1 if no bits are set.

Returns:

  • (Integer) —

    the first set bit in the bitmap.



255
256
257
258
259
260
 
# File 'lib/hashtable/sparse_bit_array.rb', line 255

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.



264
265
266
267
268
269
 
# File 'lib/hashtable/sparse_bit_array.rb', line 264

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



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

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



221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/hashtable/sparse_bit_array.rb', line 221

def set(index)
  e_index = index / ELEMENT_SIZE
  element_i = lower_bound(e_index)
  new_e = elements[element_i]
  eql = new_e.index <=> e_index unless new_e.nil?
  if eql.nil? || eql != 0
    element_i += 1 if eql == -1
    new_e = SparseBitArrayElement.new(e_index)
    @elements.insert(element_i, new_e)
  end
  @current_index = element_i
  new_e.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



193
194
195
196
197
198
199
200
201
 
# File 'lib/hashtable/sparse_bit_array.rb', line 193

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

  e_index = index / ELEMENT_SIZE
  element_i = lower_bound(e_index)
  return false if element_i == elements.length || 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



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

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