Class: Stupidedi::Sets::RelativeSet

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

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

Methods inherited from AbstractSet

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

Constructor Details

#initialize(hash) ⇒ RelativeSet

Returns a new instance of RelativeSet.



22
23
24
 
# File 'lib/stupidedi/sets/relative_set.rb', line 22

def initialize(hash)
  @hash = hash
end

Class Method Details

.build(object) ⇒ RelativeSet

Returns:



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

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 



202
203
204
205
206
 
# File 'lib/stupidedi/sets/relative_set.rb', line 202

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

#complement ⇒ RelativeComplement

Returns:



96
97
98
 
# File 'lib/stupidedi/sets/relative_set.rb', line 96

def complement
  RelativeComplement.new(self)
end

#difference(other) ⇒ Object 



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

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(Sets.build(other))
  end
end

#each ⇒ void

This method returns an undefined value.

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



29
30
31
 
# File 'lib/stupidedi/sets/relative_set.rb', line 29

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @hash.empty?
end

#finite? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) —

    true



48
49
50
 
# File 'lib/stupidedi/sets/relative_set.rb', line 48

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.



54
55
56
 
# File 'lib/stupidedi/sets/relative_set.rb', line 54

def first
  @hash.keys.first
end

#include?(object) ⇒ Boolean

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/stupidedi/sets/relative_set.rb', line 41

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

#inspect ⇒ String

Returns:



235
236
237
 
# File 'lib/stupidedi/sets/relative_set.rb', line 235

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

#intersection(other) ⇒ Object 



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

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(Sets.build(other))
  end
end

#map ⇒ RelativeSet

Returns:



77
78
79
80
81
82
 
# File 'lib/stupidedi/sets/relative_set.rb', line 77

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.



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

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:



90
91
92
 
# File 'lib/stupidedi/sets/relative_set.rb', line 90

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

#replace(other) ⇒ AbstractSet

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

Returns:



59
60
61
 
# File 'lib/stupidedi/sets/relative_set.rb', line 59

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

#select ⇒ RelativeSet

Returns:



85
86
87
 
# File 'lib/stupidedi/sets/relative_set.rb', line 85

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

#size ⇒ Numeric

Returns the number of elements in the set

Returns:

  • (Numeric) 


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

def size
  @hash.size
end

#symmetric_difference(other) ⇒ Object 



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

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 = Sets.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:



36
37
38
 
# File 'lib/stupidedi/sets/relative_set.rb', line 36

def to_a
  @hash.keys
end

#union(other) ⇒ Object 



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

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(Sets.build(other))
  end
end