Class: Bitz::Set

Inherits:
Object
  • Object
show all
Defined in:
lib/bitz/set.rb

Overview

A dynamic bitset implementation with efficient bit manipulation operations. Supports automatic buffer resizing and both mutating and non-mutating operations.

Instance Method Summary collapse

Constructor Details

#initialize(bits = 64, fill: false) ⇒ Set

Creates a new bitset with the specified capacity.

Parameters:

  • bits (Integer) (defaults to: 64) —

    the initial capacity in bits (default: 64)

  • fill (Boolean) (defaults to: false) —

    whether to initialize with all bits set (default: false)



11
12
13
14
15
16
17
 
# File 'lib/bitz/set.rb', line 11

def initialize bits = 64, fill: false
  # round up to the nearest 8 then get byte count
  bytes = ((bits + 7) & -8) / 8
  @fill = fill
  @buffer = "".b
  resize bytes, @fill
end

Instance Method Details

#&(other) ⇒ Bitz::Set

Returns a new bitset containing the intersection of this bitset and another. Neither original bitset is modified.

Parameters:

  • other (Bitz::Set) —

    the bitset to intersect with

Returns:

  • (Bitz::Set) —

    a new bitset with the intersection result

Raises:

  • (ArgumentError) —

    if the bitsets have different capacities



153
154
155
 
# File 'lib/bitz/set.rb', line 153

def & other
  dup.set_intersection other
end

#==(other) ⇒ Boolean Also known as: eql?

Compares this bitset with another for equality. Returns false if the bitsets have different capacities. Otherwise compares all bytes for exact equality.

Parameters:

  • other (Object) —

    the object to compare with

Returns:

  • (Boolean) —

    true if bitsets are equal, false otherwise



309
310
311
312
313
314
 
# File 'lib/bitz/set.rb', line 309

def == other
  return false unless other.is_a?(self.class)
  return false unless other.capacity == capacity

  @buffer == other.buffer
end

#capacity ⇒ Integer

Returns the current capacity of the bitset in bits.

Returns:

  • (Integer) —

    the total number of bits this bitset can hold



85
86
87
 
# File 'lib/bitz/set.rb', line 85

def capacity
  @buffer.bytesize * 8
end

#count ⇒ Integer

Returns the number of bits set to 1 in this bitset. Uses efficient popcount algorithm for fast bit counting.

Returns:

  • (Integer) —

    the number of set bits



78
79
80
 
# File 'lib/bitz/set.rb', line 78

def count
  @buffer.each_byte.sum { |byte| popcount(byte) }
end

#each_bit {|Integer| ... } ⇒ Enumerator, self

Iterates over each set bit in the bitset, yielding the bit position. Only bits that are set to 1 are yielded. Bits are yielded in ascending order. Returns an Enumerator if no block is given.

Examples:

bitset = Bitz::Set.new
bitset.set(2)
bitset.set(5)
bitset.set(10)
bitset.each_bit { |bit| puts bit }  # prints 2, 5, 10
bitset.each_bit.to_a                # => [2, 5, 10]

Yields:

  • (Integer) —

    the position of each set bit (0-indexed)

Returns:

  • (Enumerator, self) —

    returns Enumerator if no block given, otherwise self



201
202
203
204
205
206
207
208
209
210
211
212
213
214
 
# File 'lib/bitz/set.rb', line 201

def each_bit
  return enum_for(__method__) unless block_given?

  byte = 0
  @buffer.each_byte { |b|
    8.times { |bit|
      if b & 0x1 == 0x1
        yield byte + bit
      end
      b >>= 1
    }
    byte += 8
  }
end

#hash ⇒ Object 



318
319
320
 
# File 'lib/bitz/set.rb', line 318

def hash
  @buffer.hash
end

#initialize_copy(_) ⇒ void

This method returns an undefined value.

Creates a deep copy of the bitset.

Parameters:

  • _ (Object) —

    unused parameter (required by Ruby’s dup mechanism)



69
70
71
72
 
# File 'lib/bitz/set.rb', line 69

def initialize_copy _
  super
  @buffer = @buffer.dup
end

#pretty_print(pp) ⇒ void

This method returns an undefined value.

Ruby’s pp library integration. Called by pp when pretty printing this object.

Parameters:

  • pp (PP) —

    the pretty printer object



299
300
301
 
# File 'lib/bitz/set.rb', line 299

def pretty_print pp
  pp.text(to_ascii(width: 32))
end

#set(bit) ⇒ void

This method returns an undefined value.

Sets the bit at the specified position to 1. Automatically resizes the buffer if necessary.

Parameters:

  • bit (Integer) —

    the bit position to set (0-indexed)



24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/bitz/set.rb', line 24

def set bit
  byte = bit / 8
  while true
    if val = @buffer.getbyte(byte)
      @buffer.setbyte(byte, val | (1 << (bit % 8)))
      break
    else
      resize(@buffer.bytesize * 2, @fill)
    end
  end
end

#set?(bit) ⇒ Boolean?

Checks if the bit at the specified position is set.

Parameters:

  • bit (Integer) —

    the bit position to check (0-indexed)

Returns:

  • (Boolean, nil) —

    true if bit is set, false if unset, nil if position doesn’t exist



57
58
59
60
61
62
63
 
# File 'lib/bitz/set.rb', line 57

def set? bit
  if val = @buffer.getbyte(bit / 8)
    0 != val & (1 << (bit % 8))
  else
    nil
  end
end

#set_all ⇒ void

This method returns an undefined value.

Sets all bits in the bitset to 1.



92
93
94
 
# File 'lib/bitz/set.rb', line 92

def set_all
  @buffer.bytesize.times { |index| @buffer.setbyte(index, 0xFF) }
end

#set_intersection(other) ⇒ self

Performs an in-place intersection with another bitset. This bitset will contain only bits that are set in both bitsets.

Parameters:

  • other (Bitz::Set) —

    the bitset to intersect with

Returns:

  • (self) —

    returns self for method chaining

Raises:

  • (ArgumentError) —

    if the bitsets have different capacities



131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/bitz/set.rb', line 131

def set_intersection other
  # Raise exception if capacities don't match
  if other.capacity != capacity
    raise ArgumentError, "Cannot intersect bitsets with different capacities: #{capacity} != #{other.capacity}"
  end

  # Perform bitwise AND with each byte
  other_buffer = other.buffer
  other_buffer.each_byte.with_index do |byte, index|
    current = @buffer.getbyte(index)
    @buffer.setbyte(index, current & byte)
  end

  self
end

#set_union(other) ⇒ self

Performs an in-place union with another bitset. This bitset will contain all bits that are set in either bitset.

Parameters:

  • other (Bitz::Set) —

    the bitset to union with

Returns:

  • (self) —

    returns self for method chaining

Raises:

  • (ArgumentError) —

    if the bitsets have different capacities



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/bitz/set.rb', line 109

def set_union other
  # Raise exception if capacities don't match
  if other.capacity != capacity
    raise ArgumentError, "Cannot union bitsets with different capacities: #{capacity} != #{other.capacity}"
  end

  # Perform bitwise OR with each byte
  other_buffer = other.buffer
  other_buffer.each_byte.with_index do |byte, index|
    current = @buffer.getbyte(index)
    @buffer.setbyte(index, current | byte)
  end

  self
end

#to_ascii(width: 64, start: 0) ⇒ String

Returns an ASCII art representation of the bitset. Displays bit indices (in hexadecimal) on top and bit values on bottom in a table format. Groups bits by bytes (8 bits) with visual separators.

Examples:

bitset = Bitz::Set.new(16)
bitset.set(1)
bitset.set(5)
bitset.set(10)
puts bitset.to_ascii(width: 16)
# Output:
# Bit Index: |  0  1  2  3  4  5  6  7 |  8  9  a  b  c  d  e  f |
# Bit Value: |  0  1  0  0  0  1  0  0 |  0  0  1  0  0  0  0  0 |
#            +------------------------+------------------------+

Parameters:

  • width (Integer) (defaults to: 64) —

    number of bits to display per row (default: 64)

  • start (Integer) (defaults to: 0) —

    starting bit position to display (default: 0)

Returns:

  • (String) —

    formatted ASCII art table



233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
 
# File 'lib/bitz/set.rb', line 233

def to_ascii width: 64, start: 0
  lines = []
  end_bit = [start + width, capacity].min
  total_bits = end_bit - start

  return "Empty bitset\n" if total_bits <= 0

  # Calculate number of byte groups
  byte_groups = (total_bits + 7) / 8

  # Build index line
  index_line = "Bit Index: "
  value_line = "Bit Value: "
  border_line = "           "

  byte_groups.times do |group|
    group_start = start + (group * 8)
    group_end = [group_start + 8, end_bit].min

    index_line += "|"
    value_line += "|"
    border_line += "+"

    (group_start...group_end).each do |bit_pos|
      index_line += sprintf("%3x", bit_pos)
      value_line += sprintf("%3d", set?(bit_pos) ? 1 : 0)
      border_line += "---"
    end

    # Pad incomplete byte groups
    if group_end - group_start < 8
      padding = 8 - (group_end - group_start)
      index_line += "   " * padding
      value_line += "   " * padding
      border_line += "---" * padding
    end

    index_line += " "
    value_line += " "
    border_line += "-"
  end

  index_line += "|\n"
  value_line += "|\n"
  border_line += "+\n"

  lines << index_line
  lines << value_line
  lines << border_line

  # Handle multi-row output for large bitsets
  if end_bit < capacity && width < capacity
    remaining = capacity - end_bit
    if remaining > 0
      lines << to_ascii(width: width, start: end_bit)
    end
  end

  lines.join
end

#toggle_all ⇒ self

Flips all bits in the bitset (complement/NOT operation). All 0 bits become 1, and all 1 bits become 0.

Returns:

  • (self) —

    returns self for method chaining



179
180
181
182
183
184
185
186
 
# File 'lib/bitz/set.rb', line 179

def toggle_all
  idx = 0
  @buffer.each_byte do |byte|
    @buffer.setbyte(idx, ~byte & 0xFF)
    idx += 1
  end
  self
end

#unset(bit) ⇒ void

This method returns an undefined value.

Sets the bit at the specified position to 0. Automatically resizes the buffer if necessary.

Parameters:

  • bit (Integer) —

    the bit position to unset (0-indexed)



41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/bitz/set.rb', line 41

def unset bit
  byte = bit / 8
  while true
    if val = @buffer.getbyte(byte)
      @buffer.setbyte(byte, val & ~(1 << (bit % 8)))
      break
    else
      resize(@buffer.bytesize * 2, @fill)
    end
  end
end

#unset_all ⇒ void

This method returns an undefined value.

Sets all bits in the bitset to 0.



99
100
101
 
# File 'lib/bitz/set.rb', line 99

def unset_all
  @buffer.bytesize.times { |index| @buffer.setbyte(index, 0x00) }
end

#|(other) ⇒ Bitz::Set

Returns a new bitset containing the union of this bitset and another. Neither original bitset is modified.

Parameters:

  • other (Bitz::Set) —

    the bitset to union with

Returns:

  • (Bitz::Set) —

    a new bitset with the union result

Raises:

  • (ArgumentError) —

    if the bitsets have different capacities



163
164
165
 
# File 'lib/bitz/set.rb', line 163

def | other
  dup.set_union other
end

#~ ⇒ Bitz::Set

Returns a new bitset with all bits flipped (complement/NOT operation). The original bitset is not modified.

Returns:

  • (Bitz::Set) —

    a new bitset with all bits flipped



171
172
173
 
# File 'lib/bitz/set.rb', line 171

def ~
  dup.toggle_all
end