Class: Set
Relationships & Source Files | |
Extension / Inclusion / Inheritance Descendants | |
Subclasses:
|
|
Super Chains via Extension / Inclusion / Inheritance | |
Instance Chain:
self,
::Enumerable
|
|
Inherits: | Object |
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 <knu@iDaemons.org> (current maintainer)
Constant Summary
-
InspectKey =
Internal use only
# File 'lib/set.rb', line 618:__inspect_key__
Class Method Summary
-
.[](*ary)
Creates a new set containing the given objects.
-
.new(enum = nil, &block) ⇒ Set
constructor
Creates a new set containing the elements of the given enumerable object.
Instance Attribute Summary
-
#compare_by_identity
readonly
Makes the set compare its elements by their identity and returns self.
-
#compare_by_identity? ⇒ Boolean
readonly
Returns true if the set will compare its elements by their identity.
-
#empty? ⇒ Boolean
readonly
Returns true if the set contains no elements.
Instance Method Summary
-
#&(enum)
(also: #intersection)
Returns a new set containing elements common to the set and the given enumerable object.
-
#+(enum)
Alias for #|.
-
#-(enum)
(also: #difference)
Returns a new set built by duplicating the set, removing every element that appears in the given enumerable object.
-
#<(set)
Alias for #proper_subset?.
-
#<<(o)
Alias for #add.
-
#<=(set)
Alias for #subset?.
-
#==(other)
Returns true if two sets are equal.
-
#===(o)
Alias for #include?.
-
#>(set)
Alias for #proper_superset?.
-
#>=(set)
Alias for #superset?.
-
#^(enum)
Returns a new set containing elements exclusive between the set and the given enumerable object.
-
#add(o)
(also: #<<)
Adds the given object to the set and returns self.
-
#add?(o) ⇒ Boolean
Adds the given object to the set and returns self.
-
#classify
Classifies the set by the return value of the given block and returns a hash of
=> set of elements
pairs. -
#clear
Removes all elements and returns self.
-
#collect!
(also: #map!)
Replaces the elements with ones returned by collect().
-
#delete(o)
Deletes the given object from the set and returns self.
-
#delete?(o) ⇒ Boolean
Deletes the given object from the set and returns self.
-
#delete_if
Deletes every element of the set for which block evaluates to true, and returns self.
-
#difference(enum)
Alias for #-.
-
#disjoint?(set) ⇒ Boolean
Returns true if the set and the given set have no element in common.
-
#divide(&func)
Divides the set into a set of subsets according to the commonality defined by the given block.
-
#each(&block)
Calls the given block once for each element in the set, passing the element as parameter.
-
#filter!(&block)
Alias for #select!.
-
#flatten
Returns a new set that is a copy of the set, flattening each containing set recursively.
-
#flatten!
Equivalent to #flatten, but replaces the receiver with the result in place.
-
#include?(o) ⇒ Boolean
(also: #member?, #===)
Returns true if the set contains the given object.
-
#initialize_clone(orig)
Clone internal hash.
-
#initialize_dup(orig)
Dup internal hash.
-
#inspect
(also: #to_s)
Returns a string containing a human-readable representation of the set (“#<Set:
element2, …
>”). -
#intersect?(set) ⇒ Boolean
Returns true if the set and the given set have at least one element in common.
-
#intersection(enum)
Alias for #&.
-
#keep_if
Deletes every element of the set for which block evaluates to false, and returns self.
-
#length
Alias for #size.
-
#map!
Alias for #collect!.
-
#member?(o)
Alias for #include?.
-
#merge(enum)
Merges the elements of the given enumerable object to the set and returns self.
-
#proper_subset?(set) ⇒ Boolean
(also: #<)
Returns true if the set is a proper subset of the given set.
-
#proper_superset?(set) ⇒ Boolean
(also: #>)
Returns true if the set is a proper superset of the given set.
-
#reject!(&block)
Equivalent to #delete_if, but returns nil if no changes were made.
-
#replace(enum)
Replaces the contents of the set with the contents of the given enumerable object and returns self.
-
#reset
Resets the internal state after modification to existing elements and returns self.
-
#select!(&block)
(also: #filter!)
Equivalent to #keep_if, but returns nil if no changes were made.
-
#size
(also: #length)
Returns the number of elements.
-
#subset?(set) ⇒ Boolean
(also: #<=)
Returns true if the set is a subset of the given set.
-
#subtract(enum)
Deletes every element that appears in the given enumerable object and returns self.
-
#superset?(set) ⇒ Boolean
(also: #>=)
Returns true if the set is a superset of the given set.
-
#to_a
Converts the set to an array.
-
#to_s
Alias for #inspect.
-
#to_set(klass = Set, *args, &block)
Returns self if no arguments are given.
-
#union(enum)
Alias for #|.
-
#|(enum)
(also: #+, #union)
Returns a new set built by merging the set and the elements of the given enumerable object.
- #eql?(o) ⇒ Boolean Internal use only
- #freeze Internal use only
- #hash Internal use only
- #pretty_print(pp) Internal use only
- #pretty_print_cycle(pp) Internal use only
- #flatten_merge(set, seen = Set.new) protected Internal use only
- #do_with_enum(enum, &block) private Internal use only
::Enumerable
- Included
#to_set | Makes a set from the enumerable object with given arguments. |
Constructor Details
.new(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}>
# 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)
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}>
# File 'lib/set.rb', line 78
def self.[](*ary) new(ary) end
Instance Attribute Details
#compare_by_identity (readonly)
Makes the set compare its elements by their identity and returns self. This method may not be supported by all subclasses of Set
.
# 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
(readonly)
Returns true if the set will compare its elements by their identity. Also see #compare_by_identity.
# File 'lib/set.rb', line 118
def compare_by_identity? @hash.respond_to?(:compare_by_identity?) && @hash.compare_by_identity? end
#empty? ⇒ Boolean
(readonly)
Returns true if the set contains no elements.
# File 'lib/set.rb', line 157
def empty? @hash.empty? end
Instance Method Details
#&(enum) 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"}>
# File 'lib/set.rb', line 465
def &(enum) n = self.class.new do_with_enum(enum) { |o| n.add(o) if include?(o) } n end
#+(enum)
Alias for #|.
# File 'lib/set.rb', line 447
alias + |
#-(enum) 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"}>
# File 'lib/set.rb', line 455
def -(enum) dup.subtract(enum) end
#<(set)
Alias for #proper_subset?.
# File 'lib/set.rb', line 298
alias < proper_subset?
#<<(o)
Alias for #add.
# File 'lib/set.rb', line 342
alias << add
#<=(set)
Alias for #subset?.
# File 'lib/set.rb', line 285
alias <= subset?
#==(other)
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
#===(o)
Alias for #include?.
# File 'lib/set.rb', line 545
alias === include?
#>(set)
Alias for #proper_superset?.
# File 'lib/set.rb', line 272
alias > proper_superset?
#>=(set)
Alias for #superset?.
# File 'lib/set.rb', line 259
alias >= superset?
#^(enum)
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"}>
#add(o) 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}>
# 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
#classify
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.
#clear
Removes all elements and returns self.
set = Set[1, 'c', :s] #=> #<Set: {1, "c", :s}>
set.clear #=> #<Set: {}>
set #=> #<Set: {}>
# File 'lib/set.rb', line 166
def clear @hash.clear self end
#collect! Also known as: #map!
Replaces the elements with ones returned by collect(). Returns an enumerator if no block is given.
#delete(o)
Deletes the given object from the set and returns self. Use #subtract to delete many items at once.
# 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.
#delete_if
Deletes every element of the set for which block evaluates to true, and returns self. Returns an enumerator if no block is given.
#difference(enum)
Alias for #-.
# File 'lib/set.rb', line 458
alias difference -
#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
# File 'lib/set.rb', line 319
def disjoint?(set) !intersect?(set) end
#divide(&func)
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.
# File 'lib/set.rb', line 588
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
#do_with_enum(enum, &block) (private)
#each(&block)
Calls the given block once for each element in the set, passing the element as parameter. Returns an enumerator if no block is given.
# File 'lib/set.rb', line 326
def each(&block) block or return enum_for(__method__) { size } @hash.each_key(&block) self end
#eql?(o) ⇒ Boolean
# File 'lib/set.rb', line 507
def eql?(o) # :nodoc: return false unless o.is_a?(Set) @hash.eql?(o.instance_variable_get(:@hash)) end
#filter!(&block)
Alias for #select!.
# File 'lib/set.rb', line 418
alias filter! select!
#flatten
Returns a new set that is a copy of the set, flattening each containing set recursively.
# File 'lib/set.rb', line 227
def flatten self.class.new.flatten_merge(self) end
#flatten!
Equivalent to #flatten, but replaces the receiver with the result in place. Returns nil if no modifications were made.
#flatten_merge(set, seen = Set.new) (protected)
#freeze
# File 'lib/set.rb', line 145
def freeze # :nodoc: @hash.freeze super end
#hash
# File 'lib/set.rb', line 503
def hash # :nodoc: @hash.hash end
#include?(o) ⇒ Boolean
Also known as: #member?, #===
# File 'lib/set.rb', line 243
def include?(o) @hash[o] end
#initialize_clone(orig)
Clone internal hash.
# File 'lib/set.rb', line 140
def initialize_clone(orig) super @hash = orig.instance_variable_get(:@hash).clone end
#initialize_dup(orig)
Dup internal hash.
# File 'lib/set.rb', line 134
def initialize_dup(orig) super @hash = orig.instance_variable_get(:@hash).dup end
#inspect Also known as: #to_s
Returns a string containing a human-readable representation of the set (“#<Set: element2, …
>”).
# File 'lib/set.rb', line 622
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
#intersection(enum)
Alias for #&.
# File 'lib/set.rb', line 470
alias intersection &
#keep_if
Deletes every element of the set for which block evaluates to false, and returns self. Returns an enumerator if no block is given.
#length
Alias for #size.
# File 'lib/set.rb', line 154
alias length size
#map!
Alias for #collect!.
# File 'lib/set.rb', line 397
alias map! collect!
#member?(o)
Alias for #include?.
# File 'lib/set.rb', line 246
alias member? include?
#merge(enum)
Merges the elements of the given enumerable object to the set and returns self.
# 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)
# File 'lib/set.rb', line 639
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)
# File 'lib/set.rb', line 649
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.
#proper_superset?(set) ⇒ Boolean
Also known as: #>
Returns true if the set is a proper superset of the given set.
#reject!(&block)
Equivalent to #delete_if, but returns nil if no changes were made. Returns an enumerator if no block is given.
#replace(enum)
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}>
# 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
Resets the internal state after modification to existing elements and returns self.
Elements will be reindexed and deduplicated.
# File 'lib/set.rb', line 516
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) Also known as: #filter!
Equivalent to #keep_if, but returns nil if no changes were made. Returns an enumerator if no block is given.
#size Also known as: #length
Returns the number of elements.
# 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.
#subtract(enum)
Deletes every element that appears in the given enumerable object and returns self.
# 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.
#to_a
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]
# File 'lib/set.rb', line 192
def to_a @hash.keys end
#to_s
Alias for #inspect.
# File 'lib/set.rb', line 637
alias to_s inspect
#to_set(klass = Set, *args, &block)
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.
#union(enum)
Alias for #|.
# File 'lib/set.rb', line 448
alias union |
#|(enum) 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}>
# File 'lib/set.rb', line 444
def |(enum) dup.merge(enum) end