Class: Set

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

Overview

Set implements a collection of unordered values with no duplicates. This is a hybrid of Array’s intuitive inter-operation facilities and Hash’s fast lookup.

Several methods accept any Enumerable object (implementing each) for greater flexibility: new, replace, merge, subtract, |, &, -, ^.

The equality of each couple of elements is determined according to Object#eql? and Object#hash, since Set uses Hash as storage.

Finally, if you are using class Set, you can also use Enumerable#to_set for convenience.

Example

require 'set'
s1 = Set.new [1, 2]                   # -> #<Set: {1, 2}>
s2 = [1, 2].to_set                    # -> #<Set: {1, 2}>
s1 == s2                              # -> true
s1.add("foo")                         # -> #<Set: {1, 2, "foo"}>
s1.merge([2, 6])                      # -> #<Set: {6, 1, 2, "foo"}>
s1.subset? s2                         # -> false
s2.subset? s1                         # -> true

Direct Known Subclasses

SortedSet

Constant Summary collapse

InspectKey =

:nodoc:

:__inspect_key__

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#to_set

Constructor Details

#initialize(enum = nil, &block) ⇒ Set

Creates a new set containing the elements of the given enumerable object.

If a block is given, the elements of enum are preprocessed by the given block.



64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/set.rb', line 64

def initialize(enum = nil, &block) # :yields: o
  @hash ||= Hash.new

  enum.nil? and return

  if block
    enum.each { |o| add(block[o]) }
  else
    merge(enum)
  end
end

Class Method Details

.[](*ary) ⇒ Object

Creates a new set containing the given objects.



55
56
57
 
# File 'lib/set.rb', line 55

def self.[](*ary)
  new(ary)
end

Instance Method Details

#&(enum) ⇒ Object Also known as: intersection

Returns a new set containing elements common to the set and the given enumerable object.



291
292
293
294
295
296
 
# File 'lib/set.rb', line 291

def &(enum)
  enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
  n = self.class.new
  enum.each { |o| n.add(o) if include?(o) }
  n
end

#-(enum) ⇒ Object Also known as: difference

Returns a new set built by duplicating the set, removing every element that appears in the given enumerable object.



283
284
285
286
 
# File 'lib/set.rb', line 283

def -(enum)
  enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
  dup.subtract(enum)
end

#==(set) ⇒ Object

Returns true if two sets are equal. The equality of each couple of elements is defined according to Object#eql?.



311
312
313
314
315
316
317
318
 
# File 'lib/set.rb', line 311

def ==(set)
  equal?(set) and return true

  set.is_a?(Set) && size == set.size or return false

  hash = @hash.dup
  set.all? { |o| hash.include?(o) }
end

#^(enum) ⇒ Object

Returns a new set containing elements exclusive between the set and the given enumerable object. (set ^ enum) is equivalent to ((set | enum) - (set & enum)).



302
303
304
305
306
307
 
# File 'lib/set.rb', line 302

def ^(enum)
  enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
  n = Set.new(enum)
  each { |o| if n.include?(o) then n.delete(o) else n.add(o) end }
  n
end

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

Adds the given object to the set and returns self. Use merge to add several elements at once.



195
196
197
198
 
# File 'lib/set.rb', line 195

def add(o)
  @hash[o] = true
  self
end

#add?(o) ⇒ Boolean

Adds the given object to the set and returns self. If the object is already in the set, returns nil.

Returns:



203
204
205
206
207
208
209
 
# File 'lib/set.rb', line 203

def add?(o)
  if include?(o)
    nil
  else
    add(o)
  end
end

#classify ⇒ Object

Classifies the set by the return value of the given block and returns a hash of => set of elements pairs. The block is called once for each element of the set, passing the element as parameter.

e.g.:

require 'set'
files = Set.new(Dir.glob("*.rb"))
hash = files.classify { |f| File.mtime(f).year }
p hash    # => {2000=>#<Set: {"a.rb", "b.rb"}>,
          #     2001=>#<Set: {"c.rb", "d.rb", "e.rb"}>,
          #     2002=>#<Set: {"f.rb"}>}



342
343
344
345
346
347
348
349
350
351
 
# File 'lib/set.rb', line 342

def classify # :yields: o
  h = {}

  each { |i|
    x = yield(i)
    (h[x] ||= self.class.new).add(i)
  }

  h
end

#clear ⇒ Object

Removes all elements and returns self.



93
94
95
96
 
# File 'lib/set.rb', line 93

def clear
  @hash.clear
  self
end

#collect! ⇒ Object Also known as: map!

Do collect() destructively.



236
237
238
239
240
 
# File 'lib/set.rb', line 236

def collect!
  set = self.class.new
  each { |o| set << yield(o) }
  replace(set)
end

#delete(o) ⇒ Object

Deletes the given object from the set and returns self. Use subtract to delete several items at once.



213
214
215
216
 
# File 'lib/set.rb', line 213

def delete(o)
  @hash.delete(o)
  self
end

#delete?(o) ⇒ Boolean

Deletes the given object from the set and returns self. If the object is not in the set, returns nil.

Returns:



220
221
222
223
224
225
226
 
# File 'lib/set.rb', line 220

def delete?(o)
  if include?(o)
    delete(o)
  else
    nil
  end
end

#delete_if ⇒ Object

Deletes every element of the set for which block evaluates to true, and returns self.



230
231
232
233
 
# File 'lib/set.rb', line 230

def delete_if
  @hash.delete_if { |o,| yield(o) }
  self
end

#divide(&func) ⇒ Object

Divides the set into a set of subsets according to the commonality defined by the given block.

If the arity of the block is 2, elements o1 and o2 are in common if block.call(o1, o2) is true. Otherwise, elements o1 and o2 are in common if block.call(o1) == block.call(o2).

e.g.:

require 'set'
numbers = Set[1, 3, 4, 6, 9, 10, 11]
set = numbers.divide { |i,j| (i - j).abs == 1 }
p set     # => #<Set: {#<Set: {1}>,
          #            #<Set: {11, 9, 10}>,
          #            #<Set: {3, 4}>,
          #            #<Set: {6}>}>



369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
 
# File 'lib/set.rb', line 369

def divide(&func)
  if func.arity == 2
    require 'tsort'

    class << dig = {}   # :nodoc:
  include TSort

  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
 fetch(node).each(&block)
  end
    end

    each { |u|
  dig[u] = a = []
  each{ |v| func.call(u, v) and a << v }
    }

    set = Set.new()
    dig.each_strongly_connected_component { |css|
  set.add(self.class.new(css))
    }
    set
  else
    Set.new(classify(&func).values)
  end
end

#each ⇒ Object

Calls the given block once for each element in the set, passing the element as parameter.



188
189
190
191
 
# File 'lib/set.rb', line 188

def each
  @hash.each_key { |o| yield(o) }
  self
end

#empty? ⇒ Boolean

Returns true if the set contains no elements.

Returns:



88
89
90
 
# File 'lib/set.rb', line 88

def empty?
  @hash.empty?
end

#eql?(o) ⇒ Boolean

:nodoc:

Returns:



324
325
326
327
 
# File 'lib/set.rb', line 324

def eql?(o) # :nodoc:
  return false unless o.is_a?(Set)
  @hash.eql?(o.instance_eval{@hash})
end

#flatten ⇒ Object

Returns a new set that is a copy of the set, flattening each containing set recursively.



138
139
140
 
# File 'lib/set.rb', line 138

def flatten
  self.class.new.flatten_merge(self)
end

#flatten! ⇒ Object

Equivalent to Set#flatten, but replaces the receiver with the result in place. Returns nil if no modifications were made.



144
145
146
147
148
149
150
 
# File 'lib/set.rb', line 144

def flatten!
  if detect { |e| e.is_a?(Set) }
    replace(flatten())
  else
    nil
  end
end

#hash ⇒ Object

:nodoc:



320
321
322
 
# File 'lib/set.rb', line 320

def hash  # :nodoc:
  @hash.hash
end

#include?(o) ⇒ Boolean Also known as: member?

Returns true if the set contains the given object.

Returns:



153
154
155
 
# File 'lib/set.rb', line 153

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

#initialize_copy(orig) ⇒ Object

Copy internal hash.



77
78
79
 
# File 'lib/set.rb', line 77

def initialize_copy(orig)
  @hash = orig.instance_eval{@hash}.dup
end

#inspect ⇒ Object

Returns a string containing a human-readable representation of the set. (“#<Set: element2, …>”)



401
402
403
404
405
406
407
408
409
410
411
412
413
414
 
# File 'lib/set.rb', line 401

def inspect
  ids = (Thread.current[InspectKey] ||= [])

  if ids.include?(object_id)
    return sprintf('#<%s: {...}>', self.class.name)
  end

  begin
    ids << object_id
    return sprintf('#<%s: {%s}>', self.class, to_a.inspect[1..-2])
  ensure
    ids.pop
  end
end

#merge(enum) ⇒ Object

Merges the elements of the given enumerable object to the set and returns self.



253
254
255
256
257
258
259
260
261
262
 
# File 'lib/set.rb', line 253

def merge(enum)
  if enum.is_a?(Set)
    @hash.update(enum.instance_eval { @hash })
  else
    enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
    enum.each { |o| add(o) }
  end

  self
end

#pretty_print(pp) ⇒ Object

:nodoc:



416
417
418
419
420
421
422
423
424
 
# File 'lib/set.rb', line 416

def pretty_print(pp)  # :nodoc:
  pp.text sprintf('#<%s: {', self.class.name)
  pp.nest(1) {
    pp.seplist(self) { |o|
  pp.pp o
    }
  }
  pp.text "}>"
end

#pretty_print_cycle(pp) ⇒ Object

:nodoc:



426
427
428
 
# File 'lib/set.rb', line 426

def pretty_print_cycle(pp)  # :nodoc:
  pp.text sprintf('#<%s: {%s}>', self.class.name, empty? ? '' : '...')
end

#proper_subset?(set) ⇒ Boolean

Returns true if the set is a proper subset of the given set.

Returns:



180
181
182
183
184
 
# File 'lib/set.rb', line 180

def proper_subset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if set.size <= size
  all? { |o| set.include?(o) }
end

#proper_superset?(set) ⇒ Boolean

Returns true if the set is a proper superset of the given set.

Returns:



166
167
168
169
170
 
# File 'lib/set.rb', line 166

def proper_superset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if size <= set.size
  set.all? { |o| include?(o) }
end

#reject! ⇒ Object

Equivalent to Set#delete_if, but returns nil if no changes were made.



245
246
247
248
249
 
# File 'lib/set.rb', line 245

def reject!
  n = size
  delete_if { |o| yield(o) }
  size == n ? nil : self
end

#replace(enum) ⇒ Object

Replaces the contents of the set with the contents of the given enumerable object and returns self.



100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/set.rb', line 100

def replace(enum)
  if enum.class == self.class
    @hash.replace(enum.instance_eval { @hash })
  else
    enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
    clear
    enum.each { |o| add(o) }
  end

  self
end

#size ⇒ Object Also known as: length

Returns the number of elements.



82
83
84
 
# File 'lib/set.rb', line 82

def size
  @hash.size
end

#subset?(set) ⇒ Boolean

Returns true if the set is a subset of the given set.

Returns:



173
174
175
176
177
 
# File 'lib/set.rb', line 173

def subset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if set.size < size
  all? { |o| set.include?(o) }
end

#subtract(enum) ⇒ Object

Deletes every element that appears in the given enumerable object and returns self.



266
267
268
269
270
 
# File 'lib/set.rb', line 266

def subtract(enum)
  enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
  enum.each { |o| delete(o) }
  self
end

#superset?(set) ⇒ Boolean

Returns true if the set is a superset of the given set.

Returns:



159
160
161
162
163
 
# File 'lib/set.rb', line 159

def superset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if size < set.size
  set.all? { |o| include?(o) }
end

#to_a ⇒ Object

Converts the set to an array. The order of elements is uncertain.



113
114
115
 
# File 'lib/set.rb', line 113

def to_a
  @hash.keys
end

#|(enum) ⇒ Object Also known as: +, union

Returns a new set built by merging the set and the elements of the given enumerable object.



274
275
276
277
 
# File 'lib/set.rb', line 274

def |(enum)
  enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
  dup.merge(enum)
end