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

#! ⇒ 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

#&(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



222
223
224
225
226
227
 
# File 'lib/bitz/set.rb', line 222

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 



231
232
233
 
# File 'lib/bitz/set.rb', line 231

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

#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

#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