Class: Cantor::RelativeSet

Inherits:
AbstractSet show all
Includes:
Enumerable
Defined in:
lib/cantor/relative_set.rb

Overview

This data type encodes a set of unique values that belong to an infinite universe of possible values (aka domain). Set operations generally perform worse than AbsoluteSet, as they operate on Hash values and require iterating the underlying Hash of at least one of the two sets in ‘O(n)` time.

This is suitable for sets that don’t have an inherently restricted domain (eg sets of arbitrary String values), including those where the domain is significantly large compared to the typical size of sets built from those values. RelativeSet also requires only a single step to execute #include?, while AbsoluteSet requires two.

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(hash) ⇒ RelativeSet

Returns a new instance of RelativeSet.



21
22
23
 
# File 'lib/cantor/relative_set.rb', line 21

def initialize(hash)
  @hash = hash
end

Class Method Details

.build(object) ⇒ RelativeSet

Returns:



247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
 
# File 'lib/cantor/relative_set.rb', line 247

def build(object)
  if object.is_a?(RelativeSet)
    object
  elsif object.is_a?(Enumerable)
    if object.empty?
      NullSet.build
    elsif object.is_a?(Hash)
      new(object)
    else
      new(object.inject({}){|h,o| h[o] = true; h })
    end
  else
    raise TypeError
  end
end

Instance Method Details

#==(other) ⇒ Object 



201
202
203
204
205
 
# File 'lib/cantor/relative_set.rb', line 201

def ==(other)
  eql?(other) or
    (other.is_a?(Enumerable) and
     @hash.keys == other.to_a)
end

#complement ⇒ RelativeComplement

Returns:



95
96
97
 
# File 'lib/cantor/relative_set.rb', line 95

def complement
  RelativeComplement.new(self)
end

#difference(other) ⇒ Object 



153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/cantor/relative_set.rb', line 153

def difference(other)
  if other.is_a?(RelativeComplement)
    # A ∖ ¬B = A ∩ B
    intersection(other.complement)
  elsif other.is_a?(AbstractSet)
    if other.empty?
      self
    else
      # A ∖ B = A ∩ ¬B
      hash = @hash.clone.delete_if{|o,_| other.include?(o) }

      if hash.empty?
        NullSet.build
      else
        RelativeSet.new(hash)
      end
    end
  else
    difference(Cantor.build(other))
  end
end

#each ⇒ void

This method returns an undefined value.

Yields each element in the set to the implicit block argument.



28
29
30
 
# File 'lib/cantor/relative_set.rb', line 28

def each
  @hash.keys.each{|o| yield o }
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @hash.empty?
end

#finite? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) —

    true



47
48
49
 
# File 'lib/cantor/relative_set.rb', line 47

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.



53
54
55
 
# File 'lib/cantor/relative_set.rb', line 53

def first
  @hash.keys.first
end

#include?(object) ⇒ Boolean

Returns:

  • (Boolean) 


40
41
42
 
# File 'lib/cantor/relative_set.rb', line 40

def include?(object)
  @hash.include?(object)
end

#inspect ⇒ String

Returns:

  • (String) 


234
235
236
 
# File 'lib/cantor/relative_set.rb', line 234

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

#intersection(other) ⇒ Object 



100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/cantor/relative_set.rb', line 100

def intersection(other)
  if other.is_a?(RelativeComplement)
    # A ∩ ¬B = ¬B ∩ A
    other.intersection(self)
  elsif other.is_a?(AbstractSet)
    if other.is_a?(RelativeSet) and size > other.size
      # For efficiency, iterate the smaller of the two sets: A ∩ B = B ∩ A
      other.intersection(self)
    elsif other.empty?
      # A ∩ ∅ = ∅
      NullSet.build
    else
      hash = @hash.clone.delete_if{|o,_| not other.include?(o) }

      if hash.empty?
        NullSet.build
      else
        RelativeSet.new(hash)
      end
    end
  else
    intersection(Cantor.build(other))
  end
end

#map ⇒ RelativeSet

Returns:



76
77
78
79
80
81
 
# File 'lib/cantor/relative_set.rb', line 76

def map
  RelativeSet.new(@hash.keys.inject({}) do |hash, key|
    hash[yield(key)] = true
    hash
  end)
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/cantor/relative_set.rb', line 211

def pretty_print(q)
  q.text("RelativeSet[#{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 ⇒ RelativeSet

Returns:



89
90
91
 
# File 'lib/cantor/relative_set.rb', line 89

def reject
  RelativeSet.new(@hash.clone.delete_if{|o,_| yield(o) })
end

#replace(other) ⇒ Object 



58
59
60
 
# File 'lib/cantor/relative_set.rb', line 58

def replace(other)
  Cantor.build(other)
end

#select ⇒ RelativeSet

Returns:



84
85
86
 
# File 'lib/cantor/relative_set.rb', line 84

def select
  RelativeSet.new(@hash.clone.delete_if{|o,_| not yield(o) })
end

#size ⇒ Object 



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

def size
  @hash.size
end

#symmetric_difference(other) ⇒ Object 



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/cantor/relative_set.rb', line 176

def symmetric_difference(other)
  if other.is_a?(RelativeComplement)
    # A ⊖ ~B = (A ∖ ¬B) | (¬B ∖ A)
    #        = (A ∩ B)  | (¬B ∩ ¬A)
    #        = (B ∖ ¬A) | (¬A ∖ B)
    #        = ~A ⊖ B
    intersection(other.complement).
      union(other.intersection(complement))
  else
    # A ⊖ B = (A ∖ B) | (B ∖ A)
    #       = (A ∪ B) - (A ∩ B)
    other = Cantor.build(other)

    if other.empty?
      self
    else
      union(other).difference(intersection(other))
    end
  end
end

#to_a ⇒ Array

Returns an Array containing each element in this set

Returns:

  • (Array) 


35
36
37
 
# File 'lib/cantor/relative_set.rb', line 35

def to_a
  @hash.keys
end

#union(other) ⇒ Object 



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/cantor/relative_set.rb', line 126

def union(other)
  if other.is_a?(RelativeComplement)
    # A ∪ ¬B = ¬B ∪ A
    other.union(self)
  elsif other.is_a?(AbstractSet)
    unless other.is_a?(RelativeSet) and size < other.size
      hash = other.inject(@hash.clone){|h,o| h[o] = true; h }

      if hash.empty?
        NullSet.build
      else
        RelativeSet.new(hash)
      end
    else
      # For efficiency, iterate the smaller of the two sets: A ∪ B = B ∪ A
      if other.empty?
        self
      else
        other.union(self)
      end
    end
  else
    union(Cantor.build(other))
  end
end