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

#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



66
67
68
69
70
71
 
# File 'lib/hashtable/sparse_bit_array.rb', line 66

def count
  (0...BITWORDS_PER_ELEMENT).inject(0) do |nums, i|
    v = @bits[i].digits(2).count(1)
    nums + v
  end
end

#each ⇒ Object 



118
119
120
121
122
123
124
125
126
127
128
129
130
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
 
# File 'lib/hashtable/sparse_bit_array.rb', line 118

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) 


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

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



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

def first
  (0...BITWORDS_PER_ELEMENT).each do |i|
    v = @bits[i]
    next if v.zero?

    count = v.digits(2).index(1)
    return i * BITWORD_SIZE + count
  end
end

#last ⇒ Integer

Returns the index of the last set bit.

Returns:

  • (Integer) —

    the index of the last set bit



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

def last
  (0...BITWORDS_PER_ELEMENT).each do |i|
    index = BITWORDS_PER_ELEMENT - i - 1
    v = @bits[index]
    next unless v != 0

    count = BIT_WORD - v.bit_length
    return index * BITWORD_SIZE + BITWORD_SIZE - count - 1
  end
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) 


98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/hashtable/sparse_bit_array.rb', line 98

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 



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

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

#set(index) ⇒ Object 



40
41
42
 
# File 'lib/hashtable/sparse_bit_array.rb', line 40

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

#test?(index) ⇒ Boolean

Returns:

  • (Boolean) 


44
45
46
 
# File 'lib/hashtable/sparse_bit_array.rb', line 44

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

#test_and_set?(index) ⇒ Boolean

Returns:

  • (Boolean) 


48
49
50
51
52
53
54
 
# File 'lib/hashtable/sparse_bit_array.rb', line 48

def test_and_set?(index)
  unless test(index)
    set(Idx)
    return 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