class DumbNumbSet
### DumbNumbSet
A DumbNumbSet
is a data structure for a very specific purpose: compactly storing a set of mostly consecutive positive integers that may begin at any number.
In Ruby, a Set is actually stored as a Hash with `true` as values. So the fairest comparison for DumbNumbSet
is the same Hash a Set would use.
#### Usage
The API for DumbNumbSet
is very simple. Numbers can be added, removed, and their presence in the set can be queried.
dns = DumbNumbSet.new dns.add 1 dns.include? 1 #=> true dns.remove 1 dns.include? 1 #=> false
#### Implementation
DumbNumbSet
is backed by a Hash of integers. Each key represents a multiple of the native integer length, and each value is a bit field. Each bit in the value represents the presence or absence of an integer.
#### Performance
Performance is nearly the same as a Hash, except when inserting many non-consecutive values.
#### Size
For consecutive values, DumbNumbSet
is typically ~95% smaller than a Hash when comparing serialized size with `Marshal.dump`.
Public Class Methods
# File lib/dumb_numb_set.rb, line 38 def initialize @bitsets = {} # Set divisor so that bit-wise operations are always performed # with Integers. if 1.size == 4 @div = 29 else @div = 61 end end
Public Instance Methods
Add a non-negative integer to the set. Raises an ArgumentError if the number given is not a non-negative integer.
# File lib/dumb_numb_set.rb, line 52 def add num raise ArgumentError, "Argument must be positive integer" unless num.is_a? Integer and num.integer? and num >= 0 index = num / @div bitset = @bitsets[index] if bitset @bitsets[index] = (bitset | (1 << (num % @div))) else @bitsets[index] = (1 << (num % @div)) end self end
# File lib/dumb_numb_set.rb, line 116 def each @bitsets.each do |index, bitset| offset = index * @div (0..@div-1).each do |bit| if bitset & (1 << bit) != 0 yield offset + bit end end end end
Returns true if the given number is in the set. Raises an ArgumentError if the number given is not a non-negative integer.
# File lib/dumb_numb_set.rb, line 101 def include? num index = num / @div bitset = @bitsets[index] return false unless bitset bitset & (1 << (num % @div)) != 0 end
# File lib/dumb_numb_set.rb, line 135 def marshal_dump MessagePack.pack({:div => @div, :bitsets => @bitsets}) end
# File lib/dumb_numb_set.rb, line 139 def marshal_load str info = MessagePack.unpack(str) @div = info["div"] @bitsets = info["bitsets"] end
Merge a collection of numbers into the set. Modifes and returns the target set.
# File lib/dumb_numb_set.rb, line 72 def merge nums nums.each do |num| self.add num end self end
Remove number from set.
# File lib/dumb_numb_set.rb, line 81 def remove num index = num / @div bitset = @bitsets[index] return false unless bitset @bitsets[index] = (bitset ^ (1 << (num % @div))) if @bitsets[index] == 0 @bitsets.delete index end num end
Returns number of keys in set (not number of values).
# File lib/dumb_numb_set.rb, line 112 def size @bitsets.length end