Class: Cantor::AbsoluteSet

Inherits:
AbstractSet show all
Includes:
Enumerable
Defined in:
lib/cantor/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 inherited from AbstractSet

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

Constructor Details

#initialize(mask, universe) ⇒ AbsoluteSet

Returns a new instance of AbsoluteSet.



29
30
31
 
# File 'lib/cantor/absolute_set.rb', line 29

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

Instance Attribute Details

#mask ⇒ Integer (readonly)

Returns:

  • (Integer) 


24
25
26
 
# File 'lib/cantor/absolute_set.rb', line 24

def mask
  @mask
end

#universe ⇒ Hash (readonly)

Returns:

  • (Hash) 


27
28
29
 
# File 'lib/cantor/absolute_set.rb', line 27

def universe
  @universe
end

Class Method Details

.build(values) ⇒ AbsoluteSet

Returns:



284
285
286
287
288
289
 
# File 'lib/cantor/absolute_set.rb', line 284

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 



196
197
198
199
200
201
202
203
204
 
# File 'lib/cantor/absolute_set.rb', line 196

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 



144
145
146
 
# File 'lib/cantor/absolute_set.rb', line 144

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

#copy(changes = {}) ⇒ AbsoluteSet

Returns:



35
36
37
38
39
 
# File 'lib/cantor/absolute_set.rb', line 35

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

#difference(other) ⇒ Object 



171
172
173
174
175
176
177
178
179
 
# File 'lib/cantor/absolute_set.rb', line 171

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



54
55
56
57
58
59
60
 
# File 'lib/cantor/absolute_set.rb', line 54

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


68
69
70
 
# File 'lib/cantor/absolute_set.rb', line 68

def empty?
  @mask.zero?
end

#finite? ⇒ Boolean

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/cantor/absolute_set.rb', line 63

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.



43
44
45
46
47
48
49
 
# File 'lib/cantor/absolute_set.rb', line 43

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

#include?(element) ⇒ Boolean

Returns:

  • (Boolean) 


87
88
89
90
91
92
93
 
# File 'lib/cantor/absolute_set.rb', line 87

def include?(element)
  if n = @universe.fetch(element, false)
    # 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:

  • (String) 


233
234
235
 
# File 'lib/cantor/absolute_set.rb', line 233

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

#intersection(other) ⇒ Object 



160
161
162
163
164
165
166
167
168
 
# File 'lib/cantor/absolute_set.rb', line 160

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:



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

def map
  mask = 0

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

      if m = @universe.fetch(value, false)
        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.



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

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:



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

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) ⇒ Object 



78
79
80
81
82
83
84
 
# File 'lib/cantor/absolute_set.rb', line 78

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

#select ⇒ AbsoluteSet

Returns:



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

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 ⇒ Object 



73
74
75
 
# File 'lib/cantor/absolute_set.rb', line 73

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

#symmetric_difference(other) ⇒ Object 



182
183
184
185
186
187
188
189
190
 
# File 'lib/cantor/absolute_set.rb', line 182

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 



149
150
151
152
153
154
155
156
157
 
# File 'lib/cantor/absolute_set.rb', line 149

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