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. Use Set#compare_by_identity to make a set compare its elements by their identity.

  • 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 (y vs. z for example).

Example

require 'set'
s1 = Set[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.

Set.new([1, 2])                       #=> #<Set: {1, 2}>
Set.new([1, 2, 1])                    #=> #<Set: {1, 2}>
Set.new([1, 'c', :s])                 #=> #<Set: {1, "c", :s}>
Set.new(1..5)                         #=> #<Set: {1, 2, 3, 4, 5}>
Set.new([1, 2, 3]) { |x| x * x }      #=> #<Set: {1, 4, 9}>



93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/set.rb', line 93

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

  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.

Set[1, 2]                   # => #<Set: {1, 2}>
Set[1, 2, 1]                # => #<Set: {1, 2}>
Set[1, 'c', :s]             # => #<Set: {1, "c", :s}>



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

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.

Set[1, 3, 5] & Set[3, 2, 1]             #=> #<Set: {3, 1}>
Set['a', 'b', 'z'] & ['a', 'b', 'c']    #=> #<Set: {"a", "b"}>



465
466
467
468
469
470
471
472
473
474
475
476
477
 
# File 'lib/set.rb', line 465

def &(enum)
  n = self.class.new
  if enum.is_a?(Set)
    if enum.size > size
      each { |o| n.add(o) if enum.include?(o) }
    else
      enum.each { |o| n.add(o) if include?(o) }
    end
  else
    do_with_enum(enum) { |o| n.add(o) if include?(o) }
  end
  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.

Set[1, 3, 5] - Set[1, 5]                #=> #<Set: {3}>
Set['a', 'b', 'z'] - ['a', 'c']         #=> #<Set: {"b", "z"}>



455
456
457
 
# File 'lib/set.rb', line 455

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

Set[1, 2] == Set[2, 1]                       #=> true
Set[1, 3, 5] == Set[1, 5]                    #=> false
Set['a', 'b', 'c'] == Set['a', 'c', 'b']     #=> true
Set['a', 'b', 'c'] == ['a', 'c', 'b']        #=> false



499
500
501
502
503
504
505
506
507
508
509
 
# File 'lib/set.rb', line 499

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

Set[1, 2] ^ Set[2, 3]                   #=> #<Set: {3, 1}>
Set[1, 'b', 'c'] ^ ['b', 'd']           #=> #<Set: {"d", 1, "c"}>



486
487
488
489
490
 
# File 'lib/set.rb', line 486

def ^(enum)
  n = Set.new(enum)
  each { |o| n.add(o) unless n.delete?(o) }
  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.

Set[1, 2].add(3)                    #=> #<Set: {1, 2, 3}>
Set[1, 2].add([3, 4])               #=> #<Set: {1, 2, [3, 4]}>
Set[1, 2].add(2)                    #=> #<Set: {1, 2}>



338
339
340
341
 
# File 'lib/set.rb', line 338

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.

Set[1, 2].add?(3)                    #=> #<Set: {1, 2, 3}>
Set[1, 2].add?([3, 4])               #=> #<Set: {1, 2, [3, 4]}>
Set[1, 2].add?(2)                    #=> nil

Returns:

  • (Boolean) 


350
351
352
 
# File 'lib/set.rb', line 350

def add?(o)
  add(o) unless include?(o)
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.

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

Returns an enumerator if no block is given.



568
569
570
571
572
573
574
575
576
577
578
 
# File 'lib/set.rb', line 568

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

  h = {}

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

  h
end

#clear ⇒ Object

Removes all elements and returns self.

set = Set[1, 'c', :s]             #=> #<Set: {1, "c", :s}>
set.clear                         #=> #<Set: {}>
set                               #=> #<Set: {}>



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

def clear
  @hash.clear
  self
end

#collect! ⇒ Object Also known as: map!

Replaces the elements with ones returned by collect(). Returns an enumerator if no block is given.



391
392
393
394
395
396
 
# File 'lib/set.rb', line 391

def collect!
  block_given? or return enum_for(__method__) { size }
  set = self.class.new
  each { |o| set << yield(o) }
  replace(set)
end

#compare_by_identity ⇒ Object

Makes the set compare its elements by their identity and returns self. This method may not be supported by all subclasses of Set.



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

def compare_by_identity
  if @hash.respond_to?(:compare_by_identity)
    @hash.compare_by_identity
    self
  else
    raise NotImplementedError, "#{self.class.name}\##{__method__} is not implemented"
  end
end

#compare_by_identity? ⇒ Boolean

Returns true if the set will compare its elements by their identity. Also see Set#compare_by_identity.

Returns:

  • (Boolean) 


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

def compare_by_identity?
  @hash.respond_to?(:compare_by_identity?) && @hash.compare_by_identity?
end

#delete(o) ⇒ Object

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



356
357
358
359
 
# File 'lib/set.rb', line 356

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) 


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

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

#delete_if ⇒ Object

Deletes every element of the set for which block evaluates to true, and returns self. Returns an enumerator if no block is given.



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

def delete_if
  block_given? or return enum_for(__method__) { size }
  # @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?.

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

Returns:

  • (Boolean) 


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

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

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

Returns an enumerator if no block is given.



596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
 
# File 'lib/set.rb', line 596

def divide(&func)
  func or return enum_for(__method__) { size }

  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.



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

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

#empty? ⇒ Boolean

Returns true if the set contains no elements.

Returns:

  • (Boolean) 


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

def empty?
  @hash.empty?
end

#eql?(o) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


515
516
517
518
 
# File 'lib/set.rb', line 515

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.



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

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.



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

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

#freeze ⇒ Object

:nodoc:



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

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

#hash ⇒ Object

:nodoc:



511
512
513
 
# File 'lib/set.rb', line 511

def hash      # :nodoc:
  @hash.hash
end

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

Returns true if the set contains the given object.

Note that include? and member? do not test member equality using == as do other Enumerables.

See also Enumerable#include?

Returns:

  • (Boolean) 


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

def include?(o)
  @hash[o]
end

#initialize_clone(orig) ⇒ Object

Clone internal hash.



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

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

#initialize_dup(orig) ⇒ Object

Dup internal hash.



134
135
136
137
 
# File 'lib/set.rb', line 134

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

#inspect ⇒ Object Also known as: to_s

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



630
631
632
633
634
635
636
637
638
639
640
641
642
643
 
# File 'lib/set.rb', line 630

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

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

  ids << object_id
  begin
    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.

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

Returns:

  • (Boolean) 


305
306
307
308
309
310
311
312
 
# File 'lib/set.rb', line 305

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



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

def keep_if
  block_given? or return enum_for(__method__) { size }
  # @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.



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

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:



647
648
649
650
651
652
653
654
655
 
# File 'lib/set.rb', line 647

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:



657
658
659
 
# File 'lib/set.rb', line 657

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) 


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

def proper_subset?(set)
  case
  when set.instance_of?(self.class) && @hash.respond_to?(:<)
    @hash < set.instance_variable_get(:@hash)
  when set.is_a?(Set)
    size < set.size && all? { |o| set.include?(o) }
  else
    raise ArgumentError, "value must be a set"
  end
end

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

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

Returns:

  • (Boolean) 


262
263
264
265
266
267
268
269
270
271
 
# File 'lib/set.rb', line 262

def proper_superset?(set)
  case
  when set.instance_of?(self.class) && @hash.respond_to?(:>)
    @hash > set.instance_variable_get(:@hash)
  when set.is_a?(Set)
    size > set.size && set.all? { |o| include?(o) }
  else
    raise ArgumentError, "value must be a set"
  end
end

#reject!(&block) ⇒ Object

Equivalent to Set#delete_if, but returns nil if no changes were made. Returns an enumerator if no block is given.



401
402
403
404
405
406
 
# File 'lib/set.rb', line 401

def reject!(&block)
  block or return enum_for(__method__) { size }
  n = size
  delete_if(&block)
  self if size != n
end

#replace(enum) ⇒ Object

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

set = Set[1, 'c', :s]             #=> #<Set: {1, "c", :s}>
set.replace([1, 2])               #=> #<Set: {1, 2}>
set                               #=> #<Set: {1, 2}>



177
178
179
180
181
182
183
184
185
186
 
# File 'lib/set.rb', line 177

def replace(enum)
  if enum.instance_of?(self.class)
    @hash.replace(enum.instance_variable_get(:@hash))
    self
  else
    do_with_enum(enum)  # make sure enum is enumerable before calling clear
    clear
    merge(enum)
  end
end

#reset ⇒ Object

Resets the internal state after modification to existing elements and returns self.

Elements will be reindexed and deduplicated.



524
525
526
527
528
529
530
531
 
# File 'lib/set.rb', line 524

def reset
  if @hash.respond_to?(:rehash)
    @hash.rehash # This should perform frozenness check.
  else
    raise FrozenError, "can't modify frozen #{self.class.name}" if frozen?
  end
  self
end

#select!(&block) ⇒ Object Also known as: filter!

Equivalent to Set#keep_if, but returns nil if no changes were made. Returns an enumerator if no block is given.



410
411
412
413
414
415
 
# File 'lib/set.rb', line 410

def select!(&block)
  block or return enum_for(__method__) { size }
  n = size
  keep_if(&block)
  self if size != n
end

#size ⇒ Object Also known as: length

Returns the number of elements.



151
152
153
 
# File 'lib/set.rb', line 151

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) 


275
276
277
278
279
280
281
282
283
284
 
# File 'lib/set.rb', line 275

def subset?(set)
  case
  when set.instance_of?(self.class) && @hash.respond_to?(:<=)
    @hash <= set.instance_variable_get(:@hash)
  when set.is_a?(Set)
    size <= set.size && all? { |o| set.include?(o) }
  else
    raise ArgumentError, "value must be a set"
  end
end

#subtract(enum) ⇒ Object

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



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

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) 


249
250
251
252
253
254
255
256
257
258
 
# File 'lib/set.rb', line 249

def superset?(set)
  case
  when set.instance_of?(self.class) && @hash.respond_to?(:>=)
    @hash >= set.instance_variable_get(:@hash)
  when set.is_a?(Set)
    size >= set.size && set.all? { |o| include?(o) }
  else
    raise ArgumentError, "value must be a set"
  end
end

#to_a ⇒ Object

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

Set[1, 2].to_a                    #=> [1, 2]
Set[1, 'c', :s].to_a              #=> [1, "c", :s]



192
193
194
 
# File 'lib/set.rb', line 192

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.



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

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

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

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

Set[1, 2, 3] | Set[2, 4, 5]         #=> #<Set: {1, 2, 3, 4, 5}>
Set[1, 5, 'z'] | (1..6)             #=> #<Set: {1, 5, "z", 2, 3, 4, 6}>



444
445
446
 
# File 'lib/set.rb', line 444

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