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

new() click to toggle source

# 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

<<(num)

Alias for: add

add(num) click to toggle source

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

Also aliased as: <<

delete(num)

Alias for: remove

each() { |offset| ... } click to toggle source

# 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

include?(num) click to toggle source

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

marshal_dump() click to toggle source

# File lib/dumb_numb_set.rb, line 135
def marshal_dump
  MessagePack.pack({:div => @div, :bitsets => @bitsets})
end

marshal_load(str) click to toggle source

# File lib/dumb_numb_set.rb, line 139
def marshal_load str
  info = MessagePack.unpack(str)
  @div = info["div"]
  @bitsets = info["bitsets"]
end

merge(nums) click to toggle source

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(num) click to toggle source

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

Also aliased as: delete

size() click to toggle source

Returns number of keys in set (not number of values).

# File lib/dumb_numb_set.rb, line 112
def size
  @bitsets.length
end