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

Contact

- Akinori MUSHA <[email protected]> (current maintainer)

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.



68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/set.rb', line 68

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.



59
60
61
 
# File 'lib/set.rb', line 59

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.



297
298
299
300
301
302
 
# File 'lib/set.rb', line 297

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.



289
290
291
292
 
# File 'lib/set.rb', line 289

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?.



317
318
319
320
321
322
323
324
 
# File 'lib/set.rb', line 317

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)).



308
309
310
311
312
313
 
# File 'lib/set.rb', line 308

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.



201
202
203
204
 
# File 'lib/set.rb', line 201

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:

  • (Boolean) 


209
210
211
212
213
214
215
 
# File 'lib/set.rb', line 209

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"}>}



348
349
350
351
352
353
354
355
356
357
 
# File 'lib/set.rb', line 348

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.



97
98
99
100
 
# File 'lib/set.rb', line 97

def clear
  @hash.clear
  self
end

#collect! ⇒ Object Also known as: map!

Do collect() destructively.



242
243
244
245
246
 
# File 'lib/set.rb', line 242

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.



219
220
221
222
 
# File 'lib/set.rb', line 219

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:

  • (Boolean) 


226
227
228
229
230
231
232
 
# File 'lib/set.rb', line 226

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.



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

def delete_if
  to_a.each { |o| @hash.delete(o) if 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}>}>



375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
 
# File 'lib/set.rb', line 375

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. Returns an enumerator if no block is given.



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

def each
  block_given? or return enum_for(__method__)
  @hash.each_key { |o| yield(o) }
  self
end

#empty? ⇒ Boolean

Returns true if the set contains no elements.

Returns:

  • (Boolean) 


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

def empty?
  @hash.empty?
end

#eql?(o) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


330
331
332
333
 
# File 'lib/set.rb', line 330

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.



142
143
144
 
# File 'lib/set.rb', line 142

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.



148
149
150
151
152
153
154
 
# File 'lib/set.rb', line 148

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

#hash ⇒ Object

:nodoc:



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

def hash	# :nodoc:
  @hash.hash
end

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

Returns true if the set contains the given object.

Returns:

  • (Boolean) 


157
158
159
 
# File 'lib/set.rb', line 157

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

#initialize_copy(orig) ⇒ Object

Copy internal hash.



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

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, ...>")



407
408
409
410
411
412
413
414
415
416
417
418
419
420
 
# File 'lib/set.rb', line 407

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.



259
260
261
262
263
264
265
266
267
268
 
# File 'lib/set.rb', line 259

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:



422
423
424
425
426
427
428
429
430
 
# File 'lib/set.rb', line 422

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:



432
433
434
 
# File 'lib/set.rb', line 432

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:

  • (Boolean) 


184
185
186
187
188
 
# File 'lib/set.rb', line 184

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:

  • (Boolean) 


170
171
172
173
174
 
# File 'lib/set.rb', line 170

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.



251
252
253
254
255
 
# File 'lib/set.rb', line 251

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.



104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/set.rb', line 104

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.



86
87
88
 
# File 'lib/set.rb', line 86

def size
  @hash.size
end

#subset?(set) ⇒ Boolean

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

Returns:

  • (Boolean) 


177
178
179
180
181
 
# File 'lib/set.rb', line 177

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.



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

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:

  • (Boolean) 


163
164
165
166
167
 
# File 'lib/set.rb', line 163

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.



117
118
119
 
# File 'lib/set.rb', line 117

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.



280
281
282
283
 
# File 'lib/set.rb', line 280

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