Class: Stupidedi::Sets::AbsoluteSet

Inherits:
AbstractSet show all
Includes:
Enumerable
Defined in:
lib/stupidedi/sets/absolute_set.rb

Overview

AbsoluteSet is a subset of a finite, fully-enumerated universe set. This means every possible value that can belong to the AbsoluteSet must already belong to the universe set, which is a finite collection.

This implementation is fairly efficient when computing set operations on two sets from the same universe, especially compared to RelativeSet. Efficiency is achieved by encoding each element in the universe’s membership to the specific subset as a bitmask. Operations can then be performed using bitwise operations, instead of using operations on a Hash.

This data type is not suitable for sets whose elements belong to an huge universe of possible values, as each set requires ‘2**|U|` bits of storage where `|U|` is the size of the universe. Operations on sets that belong to different universes do not currently attempt to merge the two universe sets, as this probably a better use case for RelativeSet.

Instance Attribute Summary collapse

Set Operations collapse

Set Ordering collapse

Pretty Printing collapse

Constructors collapse

Instance Method Summary collapse

Methods included from Enumerable

#blank?, #count, #present?, #sum

Methods inherited from AbstractSet

#&, #+, #-, #<, #<=, #>, #>=, #^, #disjoint?, #exclude?, #infinite?, #proper_subset?, #proper_superset?, #subset?, #superset?, #|, #~

Constructor Details

#initialize(mask, universe) ⇒ AbsoluteSet

Returns a new instance of AbsoluteSet.



30
31
32
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 30

def initialize(mask, universe)
  @mask, @universe = mask, universe.freeze
end

Instance Attribute Details

#mask ⇒ Integer (readonly)

Returns:



25
26
27
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 25

def mask
  @mask
end

#universe ⇒ Hash (readonly)

Returns:



28
29
30
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 28

def universe
  @universe
end

Class Method Details

.build(values) ⇒ AbsoluteSet

Returns:



285
286
287
288
289
290
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 285

def build(values)
  count    = -1
  universe = values.inject({}){|hash, v| hash.update(v => (count += 1)) }

  new((1 << (count + 1)) - 1, universe)
end

Instance Method Details

#==(other) ⇒ Object 



197
198
199
200
201
202
203
204
205
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 197

def ==(other)
  if other.is_a?(AbsoluteSet) and other.universe.eql?(@universe)
    @mask == other.mask
  elsif other.is_a?(AbstractSet) and other.infinite?
    false
  elsif other.is_a?(Enumerable)
    @mask == as_mask(other, false) and size == other.size
  end
end

#complement ⇒ Object 



145
146
147
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 145

def complement
  copy(:mask => ~@mask & ((1 << @universe.size) - 1))
end

#copy(changes = {}) ⇒ AbsoluteSet

Returns:



36
37
38
39
40
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 36

def copy(changes = {})
  AbsoluteSet.new \
    changes.fetch(:mask, @mask),
    changes.fetch(:universe, @universe)
end

#difference(other) ⇒ Object 



172
173
174
175
176
177
178
179
180
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 172

def difference(other)
  if other.is_a?(AbsoluteSet) and other.universe.eql?(@universe)
    copy(:mask => @mask & ~other.mask)
  elsif other.is_a?(AbstractSet) and other.infinite?
    intersection(other.complement)
  else
    copy(:mask => @mask & ~as_mask(other, false))
  end
end

#each ⇒ void

This method returns an undefined value.

Yields each element in the set to the implicit block argument



55
56
57
58
59
60
61
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 55

def each
  @universe.each do |value, n|
    unless @mask[n].zero?
      yield(value)
    end
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


69
70
71
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 69

def empty?
  @mask.zero?
end

#finite? ⇒ Boolean

Returns:

  • (Boolean) 


64
65
66
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 64

def finite?
  true
end

#first ⇒ Object

Returns a single element from the set, with no guarantees about which element. If the set is #empty?, the return value is undefined.



44
45
46
47
48
49
50
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 44

def first
  @universe.each do |value, n|
    unless @mask[n].zero?
      return value
    end
  end
end

#include?(element) ⇒ Boolean

Returns:

  • (Boolean) 


88
89
90
91
92
93
94
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 88

def include?(element)
  if n = @universe.at(element)
    # Same as (@mask & (1 << n)).zero? but potentially eliminates
    # converting the intermediate computation to a Ruby value
    not @mask[n].zero?
  end
end

#inspect ⇒ String

Returns:



234
235
236
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 234

def inspect
  "AbsoluteSet(#{to_a.map(&:inspect).join(', ')})"
end

#intersection(other) ⇒ Object 



161
162
163
164
165
166
167
168
169
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 161

def intersection(other)
  if other.is_a?(AbsoluteSet) and other.universe.eql?(@universe)
    copy(:mask => @mask & other.mask)
  elsif other.is_a?(AbstractSet) and other.infinite?
    other.intersection(self)
  else
    copy(:mask => @mask & as_mask(other, false))
  end
end

#map ⇒ AbsoluteSet

Returns:



100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 100

def map
  mask = 0

  @universe.each do |value, n|
    unless @mask[n].zero?
      value = yield(value)

      if m = @universe.at(value)
        mask |= (1 << m)
      else
        raise "universe does not contain element #{value.inspect}"
      end
    end
  end

  copy(:mask => mask)
end

#pretty_print(q) ⇒ void

This method returns an undefined value.



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 211

def pretty_print(q)
  q.text("AbsoluteSet[#{size}/#{@universe.size}]")
  q.group(2, "(", ")") do
    q.breakable ""

    elements = to_a
    elements.take(5).each do |e|
      unless q.current_group.first?
        q.text ","
        q.breakable
      end
      q.pp e
    end

    if elements.length > 5
      q.text ","
      q.breakable
      q.text "..."
    end
  end
end

#reject ⇒ AbsoluteSet

Returns:



132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 132

def reject
  mask = 0

  @universe.each do |value, n|
    unless @mask[n].zero? or yield(value)
      mask |= (1 << n)
    end
  end

  copy(:mask => mask)
end

#replace(other) ⇒ AbstractSet

Returns the ‘other` set, converting it to an Stupidedi::Sets::AbstractSet if it isn’t already.

Returns:



79
80
81
82
83
84
85
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 79

def replace(other)
  if other.is_a?(AbstractSet)
    other
  else
    copy(:mask => as_mask(other, true))
  end
end

#select ⇒ AbsoluteSet

Returns:



119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 119

def select
  mask = 0

  @universe.each do |value, n|
    unless @mask[n].zero? or not yield(value)
      mask |= (1 << n)
    end
  end

  copy(:mask => mask)
end

#size ⇒ Numeric

Returns the number of elements in the set

Returns:

  • (Numeric) 


74
75
76
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 74

def size
  @universe.inject(0){|size, (value, n)| size + @mask[n] }
end

#symmetric_difference(other) ⇒ Object 



183
184
185
186
187
188
189
190
191
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 183

def symmetric_difference(other)
  if other.is_a?(AbsoluteSet) and other.universe.eql?(@universe)
    copy(:mask => @mask ^ other.mask)
  elsif other.is_a?(AbstractSet) and other.infinite?
    other.symmetric_difference(self)
  else
    copy(:mask => @mask ^ as_mask(other, true))
  end
end

#union(other) ⇒ Object 



150
151
152
153
154
155
156
157
158
 
# File 'lib/stupidedi/sets/absolute_set.rb', line 150

def union(other)
  if other.is_a?(AbsoluteSet) and other.universe.eql?(@universe)
    copy(:mask => @mask | other.mask)
  elsif other.is_a?(AbstractSet) and other.infinite?
    other.union(self)
  else
    copy(:mask => @mask | as_mask(other, true))
  end
end