Class: DumbNumbSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/dumb_numb_set.rb

Overview

### 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`.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DumbNumbSet

Returns a new instance of DumbNumbSet.



38
39
40
41
42
43
44
45
46
47
48
 
# 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

Instance Method Details

#add(num) ⇒ Object Also known as: <<

Add a non-negative integer to the set. Raises an ArgumentError if the number given is not a non-negative integer.

Raises:

  • (ArgumentError) 


52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# 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

#each ⇒ Object 



116
117
118
119
120
121
122
123
124
125
 
# 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) ⇒ Boolean

Returns true if the given number is in the set. Raises an ArgumentError if the number given is not a non-negative integer.

Returns:

  • (Boolean) 


101
102
103
104
105
106
107
108
109
 
# 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

#merge(nums) ⇒ Object

Merge a collection of numbers into the set. Modifes and returns the target set.



72
73
74
75
76
77
78
 
# File 'lib/dumb_numb_set.rb', line 72

def merge nums
  nums.each do |num|
    self.add num
  end

  self
end

#remove(num) ⇒ Object Also known as: delete

Remove number from set.



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# 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

#size ⇒ Object

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



112
113
114
 
# File 'lib/dumb_numb_set.rb', line 112

def size
  @bitsets.length
end