Class: HashTable::SparseBitArrayElement Abstract

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

Overview

This class is abstract.

SparseBitArrayElement

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(index = 0) ⇒ SparseBitArrayElement

Returns a new instance of SparseBitArrayElement.



19
20
21
22
23
 
# File 'lib/hashtable/sparse_bit_array.rb', line 19

def initialize(index = 0)
  @index = index
  # Index of Element in terms of where first bit starts.
  @bits = Array.new(BITWORDS_PER_ELEMENT, 0)
end

Instance Attribute Details

#index ⇒ Integer (readonly)

Returns Index of Element in terms of where first bit starts.

Returns:

  • (Integer) —

    Index of Element in terms of where first bit starts.



17
18
19
 
# File 'lib/hashtable/sparse_bit_array.rb', line 17

def index
  @index
end

Instance Method Details

#==(other) ⇒ Object 



33
34
35
36
37
38
39
 
# File 'lib/hashtable/sparse_bit_array.rb', line 33

def ==(other)
  return false unless index == other.index

  (0...BITWORDS_PER_ELEMENT).each do |i|
    return false unless @bits[i] == other.bits[i]
  end || true
end

#count ⇒ Object

v = @bits v -= ((v >> 1) & 0x5555555555555555) v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333) v = (v + (v >> 4) & 0x0F0F0F0F0F0F0F0F) v = (v * 0x0101010101010101) & UINT_64_MAX v >>= 56



72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/hashtable/sparse_bit_array.rb', line 72

def count
  @bits.inject(0) do |nums, b|
    v = b
    v -= ((v >> 1) & 0x5555555555555555)
    v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333)
    v = (v + (v >> 4) & 0x0F0F0F0F0F0F0F0F)
    v = (v * 0x0101010101010101) & UINT_64_MAX
    v >>= 56
    nums + v
  end
end

#each ⇒ Object 



131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/hashtable/sparse_bit_array.rb', line 131

def each
  return if empty?

  last_i = last
  first_i = first
  bits = 0
  bit_number = 0
  loop do
    while bits.nonzero? && (bits & 1).zero?
      bits >>= 1
      bit_number += 1
    end
    # See if we ran out of Bits in this word.
    if bits.zero?
      next_set_bit_number = self.next(bit_number % ELEMENT_SIZE)
      if next_set_bit_number == -1 || (bit_number % ELEMENT_SIZE).zero?
        next_set_bit_number = first_i
        bit_number = index * ELEMENT_SIZE
        bit_number += next_set_bit_number
        word_number = bit_number % ELEMENT_SIZE / BITWORD_SIZE
        bits = word(word_number)
        bits >>= next_set_bit_number % BITWORD_SIZE
      else
        # Set up for next non-zero word in bitmap
        word_number = next_set_bit_number % ELEMENT_SIZE / BITWORD_SIZE
        bits = word(word_number)
        bits >>= next_set_bit_number % BITWORD_SIZE
        bit_number = index * ELEMENT_SIZE
        bit_number += next_set_bit_number
      end
    end
    yield bit_number
    break if bit_number % ELEMENT_SIZE == last_i

    bit_number += 1
    bits >>= 1
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


41
42
43
44
45
 
# File 'lib/hashtable/sparse_bit_array.rb', line 41

def empty?
  (0...BITWORDS_PER_ELEMENT).each do |i|
    return false unless @bits[i].zero?
  end || true
end

#first ⇒ Integer

Returns the index of the first set bit.

Returns:

  • (Integer) —

    the index of the first set bit

Raises:

  • (ArgumentError) 


85
86
87
88
89
90
91
92
93
94
 
# File 'lib/hashtable/sparse_bit_array.rb', line 85

def first
  (0...BITWORDS_PER_ELEMENT).each do |i|
    v = @bits[i]
    unless v.zero?
      count = v.digits(2).index(1)
      return i * BITWORD_SIZE + count
    end
  end
  raise ArgumentError, 'Illegal empty element'
end

#last ⇒ Integer

Returns the index of the last set bit.

Returns:

  • (Integer) —

    the index of the last set bit

Raises:

  • (ArgumentError) 


97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/hashtable/sparse_bit_array.rb', line 97

def last
  (0...BITWORDS_PER_ELEMENT).each do |i|
    index = BITWORDS_PER_ELEMENT - i - 1
    v = @bits[index]
    unless v.zero?
      count = BIT_WORD - v.bit_length
      return index * BITWORD_SIZE + BITWORD_SIZE - count - 1
    end
  end
  raise ArgumentError, 'Illegal empty element'
end

#next(index) ⇒ Integer

Returns -1 if the next set bit is not found.

Returns:

  • (Integer) —

    the index of the next set bit starting from the “index” bit.

Raises:

  • (ArgumentError) 


111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/hashtable/sparse_bit_array.rb', line 111

def next(index)
  return -1 if index >= BITS_PER_ELEMENT

  word_pos = index / BITWORD_SIZE
  bit_pos = index % BITWORD_SIZE
  copy = @bits[word_pos]
  raise ArgumentError, 'Word Position outside of element' unless word_pos <= BITS_PER_ELEMENT

  copy &= ~0 << bit_pos
  return word_pos * BITWORD_SIZE + copy.digits(2).index(1) unless copy.zero?

  word_pos += 1
  (word_pos...BITWORDS_PER_ELEMENT).each do |i|
    return i * BITWORD_SIZE + @bits[i].digits(2).index(1) unless @bits[i].zero?
  end
  -1
end

#reset(index) ⇒ Object 



62
63
64
 
# File 'lib/hashtable/sparse_bit_array.rb', line 62

def reset(index)
  @bits[index / BITWORD_SIZE] &= ~(1 << (index % BITWORD_SIZE))
end

#set(index) ⇒ Object 



47
48
49
 
# File 'lib/hashtable/sparse_bit_array.rb', line 47

def set(index)
  @bits[index / BITWORD_SIZE] |= 1 << (index % BITWORD_SIZE)
end

#test?(index) ⇒ Boolean

Returns:

  • (Boolean) 


51
52
53
 
# File 'lib/hashtable/sparse_bit_array.rb', line 51

def test?(index)
  @bits[index / BITWORD_SIZE] & (1 << (index % BITWORD_SIZE)) != 0
end

#test_and_set?(index) ⇒ Boolean

Returns:

  • (Boolean) 


55
56
57
58
59
60
 
# File 'lib/hashtable/sparse_bit_array.rb', line 55

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

#word(index) ⇒ Integer

Returns the bits that make up word index in our element.

Parameters:

  • index (Integer)

Returns:

  • (Integer) —

    the bits that make up word index in our element

Raises:

  • (ArgumentError) 


27
28
29
30
31
 
# File 'lib/hashtable/sparse_bit_array.rb', line 27

def word(index)
  raise ArgumentError, 'index error' unless index < BITWORDS_PER_ELEMENT

  @bits[index]
end