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.

Set is easy to use with Enumerable objects (implementing each). Most of the initializer methods and binary operators accept generic Enumerable objects besides sets and arrays. An Enumerable object can be converted to Set using the to_set method.

Set uses Hash as storage, so you must note the following points:

  • Equality of elements is determined according to Object#eql? and Object#hash.

  • Set assumes that the identity of each element does not change while it is stored. Modifying an element of a set will render the set to an unreliable state.

  • When a string is to be stored, a frozen copy of the string is stored instead unless the original string is already frozen.

Comparison

The comparison operators <, >, <= and >= are implemented as shorthand for the proper_,subset?,superset? methods. However, the <=> operator is intentionally left out because not every pair of sets is comparable. (x,y vs. x,z for example)

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: {1, 2, "foo", 6}>
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

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.



80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/set.rb', line 80

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

  enum.nil? and return

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

Class Method Details

.[](*ary) ⇒ Object

Creates a new set containing the given objects.



71
72
73
 
# File 'lib/set.rb', line 71

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.



405
406
407
408
409
 
# File 'lib/set.rb', line 405

def &(enum)
  n = self.class.new
  do_with_enum(enum) { |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.



398
399
400
 
# File 'lib/set.rb', line 398

def -(enum)
  dup.subtract(enum)
end

#==(other) ⇒ Object

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



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

def ==(other)
  if self.equal?(other)
    true
  elsif other.instance_of?(self.class)
    @hash == other.instance_variable_get(:@hash)
  elsif other.is_a?(Set) && self.size == other.size
    other.all? { |o| @hash.include?(o) }
  else
    false
  end
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)).



415
416
417
418
419
 
# File 'lib/set.rb', line 415

def ^(enum)
  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 many elements at once.



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

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) 


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

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



457
458
459
460
461
462
463
464
465
466
467
468
 
# File 'lib/set.rb', line 457

def classify # :yields: o
  block_given? or return enum_for(__method__)

  h = {}

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

  h
end

#clear ⇒ Object

Removes all elements and returns self.



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

def clear
  @hash.clear
  self
end

#collect! ⇒ Object Also known as: map!

Replaces the elements with ones returned by collect().



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

def collect!
  block_given? or return enum_for(__method__)
  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 many items at once.



307
308
309
310
 
# File 'lib/set.rb', line 307

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) 


314
315
316
317
318
319
320
 
# File 'lib/set.rb', line 314

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.



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

def delete_if
  block_given? or return enum_for(__method__)
  # @hash.delete_if should be faster, but using it breaks the order
  # of enumeration in subclasses.
  select { |o| yield o }.each { |o| @hash.delete(o) }
  self
end

#disjoint?(set) ⇒ Boolean

Returns true if the set and the given set have no element in common. This method is the opposite of intersect?.

e.g.:

require 'set'
Set[1, 2, 3].disjoint? Set[3, 4] # => false
Set[1, 2, 3].disjoint? Set[4, 5] # => true

Returns:

  • (Boolean) 


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

def disjoint?(set)
  !intersect?(set)
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}>}>



486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
 
# File 'lib/set.rb', line 486

def divide(&func)
  func or return enum_for(__method__)

  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(&block) ⇒ 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.



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

def each(&block)
  block or return enum_for(__method__)
  @hash.each_key(&block)
  self
end

#empty? ⇒ Boolean

Returns true if the set contains no elements.

Returns:

  • (Boolean) 


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

def empty?
  @hash.empty?
end

#eql?(o) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


439
440
441
442
 
# File 'lib/set.rb', line 439

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

#flatten ⇒ Object

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



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

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.



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

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

#freeze ⇒ Object

:nodoc:



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

def freeze    # :nodoc:
  @hash.freeze
  super
end

#hash ⇒ Object

:nodoc:



435
436
437
 
# File 'lib/set.rb', line 435

def hash      # :nodoc:
  @hash.hash
end

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

Returns true if the set contains the given object.

Returns:

  • (Boolean) 


211
212
213
 
# File 'lib/set.rb', line 211

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

#initialize_clone(orig) ⇒ Object

Clone internal hash.



110
111
112
113
 
# File 'lib/set.rb', line 110

def initialize_clone(orig)
  super
  @hash = orig.instance_variable_get(:@hash).clone
end

#initialize_dup(orig) ⇒ Object

Dup internal hash.



104
105
106
107
 
# File 'lib/set.rb', line 104

def initialize_dup(orig)
  super
  @hash = orig.instance_variable_get(:@hash).dup
end

#inspect ⇒ Object

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



520
521
522
523
524
525
526
527
528
529
530
531
532
533
 
# File 'lib/set.rb', line 520

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

#intersect?(set) ⇒ Boolean

Returns true if the set and the given set have at least one element in common.

e.g.:

require 'set'
Set[1, 2, 3].intersect? Set[4, 5] # => false
Set[1, 2, 3].intersect? Set[3, 4] # => true

Returns:

  • (Boolean) 


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

def intersect?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  if size < set.size
    any? { |o| set.include?(o) }
  else
    set.any? { |o| include?(o) }
  end
end

#keep_if ⇒ Object

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



334
335
336
337
338
339
340
 
# File 'lib/set.rb', line 334

def keep_if
  block_given? or return enum_for(__method__)
  # @hash.keep_if should be faster, but using it breaks the order of
  # enumeration in subclasses.
  reject { |o| yield o }.each { |o| @hash.delete(o) }
  self
end

#merge(enum) ⇒ Object

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



371
372
373
374
375
376
377
378
379
 
# File 'lib/set.rb', line 371

def merge(enum)
  if enum.instance_of?(self.class)
    @hash.update(enum.instance_variable_get(:@hash))
  else
    do_with_enum(enum) { |o| add(o) }
  end

  self
end

#pretty_print(pp) ⇒ Object

:nodoc:



535
536
537
538
539
540
541
542
543
 
# File 'lib/set.rb', line 535

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:



545
546
547
 
# File 'lib/set.rb', line 545

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

#proper_subset?(set) ⇒ Boolean Also known as: <

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

Returns:

  • (Boolean) 


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

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 Also known as: >

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

Returns:

  • (Boolean) 


225
226
227
228
229
 
# File 'lib/set.rb', line 225

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!(&block) ⇒ Object

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



353
354
355
356
357
358
 
# File 'lib/set.rb', line 353

def reject!(&block)
  block or return enum_for(__method__)
  n = size
  delete_if(&block)
  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.



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

def replace(enum)
  if enum.instance_of?(self.class)
    @hash.replace(enum.instance_variable_get(:@hash))
    self
  else
    do_with_enum(enum)
    clear
    merge(enum)
  end
end

#select!(&block) ⇒ Object

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



362
363
364
365
366
367
 
# File 'lib/set.rb', line 362

def select!(&block)
  block or return enum_for(__method__)
  n = size
  keep_if(&block)
  size == n ? nil : self
end

#size ⇒ Object Also known as: length

Returns the number of elements.



131
132
133
 
# File 'lib/set.rb', line 131

def size
  @hash.size
end

#subset?(set) ⇒ Boolean Also known as: <=

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

Returns:

  • (Boolean) 


233
234
235
236
237
 
# File 'lib/set.rb', line 233

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.



383
384
385
386
 
# File 'lib/set.rb', line 383

def subtract(enum)
  do_with_enum(enum) { |o| delete(o) }
  self
end

#superset?(set) ⇒ Boolean Also known as: >=

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

Returns:

  • (Boolean) 


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

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

#taint ⇒ Object

:nodoc:



120
121
122
123
 
# File 'lib/set.rb', line 120

def taint     # :nodoc:
  @hash.taint
  super
end

#to_a ⇒ Object

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



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

def to_a
  @hash.keys
end

#to_set(klass = Set, *args, &block) ⇒ Object

Returns self if no arguments are given. Otherwise, converts the set to another with klass.new(self, *args, &block).

In subclasses, returns klass.new(self, *args, &block) unless overridden.



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

def to_set(klass = Set, *args, &block)
  return self if instance_of?(Set) && klass == Set && block.nil? && args.empty?
  klass.new(self, *args, &block)
end

#untaint ⇒ Object

:nodoc:



125
126
127
128
 
# File 'lib/set.rb', line 125

def untaint   # :nodoc:
  @hash.untaint
  super
end

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

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



390
391
392
 
# File 'lib/set.rb', line 390

def |(enum)
  dup.merge(enum)
end