класс Set
Множество реализует коллекцию неупорядоченных значений без дубликатов. Это гибрид интуитивно понятных возможностей работы с массивами и быстрого поиска хэшей.
Множество легко использовать с объектами Enumerable (реализующими each). Большинство методов инициализации и бинарных операторов принимают универсальные объекты Enumerable, помимо множеств и массивов. Объект Enumerable можно преобразовать в Множество с помощью метода to_set.
Множество использует Хэш-таблицу в качестве хранилища, поэтому вы должны учитывать следующие моменты:
-
Равенство элементов определяется по Object#eql? и Object#hash. Используйте #compare_by_identity, чтобы множества сравнивали элементы по их идентификатору.
-
Множество предполагает, что идентификатор каждого элемента не изменяется во время его хранения. Изменение элемента множества сделает состояние множества ненадёжным.
-
Если строка должна храниться, вместо неё хранится замороженная копия строки, если только исходная строка уже не заморожена.
Сравнение
Операторы сравнения <, >, <=, и >= реализованы в качестве сокращений для методов {proper_,}{subset?,superset?}. Однако оператор <=> намеренно опущен, поскольку не все пары множеств сравнимы (например, {x, y} и {x, z}).
Пример
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
Контакты
- Akinori MUSHA <knu@iDaemons.org> (current maintainer)
Открытые методы класса
# File lib/set.rb, line 78 def self.[](*ary) new(ary) end
Создаёт новое множество, содержащее указанные объекты.
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 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 Создаёт новое множество, содержащее элементы заданного объекта перечисления.
Если задан блок, элементы enum предварительно обрабатываются с помощью данного блока.
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 472
def &(enum)
n = self.class.new
do_with_enum(enum) { |o| n.add(o) if include?(o) }
n
end Возвращает новый набор, содержащий элементы, общие для набора и заданного перечислимого объекта.
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 462 def -(enum) dup.subtract(enum) end
Возвращает новый набор, созданный путем дублирования набора, удаляя каждый элемент, который появляется в заданном перечислимом объекте.
Set[1, 3, 5] - Set[1, 5] #=> #<Set: {3}>
Set['a', 'b', 'z'] - ['a', 'c'] #=> #<Set: {"b", "z"}>
# File lib/set.rb, line 498
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 Возвращает true, если два набора равны. Равенство каждой пары элементов определяется в соответствии с 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
Возвращает true, если заданный объект является членом набора, и false в противном случае.
Используется в операторах case:
require 'set' case :apple when Set[:potato, :carrot] "vegetable" when Set[:apple, :banana] "fruit" end # => "fruit"
Или самостоятельно:
Set[1, 2, 3] === 2 #=> true Set[1, 2, 3] === 4 #=> false
# File lib/set.rb, line 485
def ^(enum)
n = Set.new(enum)
each { |o| n.add(o) unless n.delete?(o) }
n
end Возвращает новый набор, содержащий элементы, уникальные для набора и заданного перечислимого объекта. (set ^ enum) эквивалентно ((set | enum) - (set & enum)).
Set[1, 2] ^ Set[2, 3] #=> #<Set: {3, 1}>
Set[1, 'b', 'c'] ^ ['b', 'd'] #=> #<Set: {"d", 1, "c"}>
# File lib/set.rb, line 348 def add(o) @hash[o] = true self end
Добавляет заданный объект в набор и возвращает self. Используйте merge для добавления сразу нескольких элементов.
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 360 def add?(o) add(o) unless include?(o) end
Добавляет заданный объект в набор и возвращает self. Если объект уже присутствует в наборе, возвращает 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
# File lib/set.rb, line 567
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 Классифицирует набор по возвращаемому значению заданного блока и возвращает хеш пар {значение => множество элементов}. Блок вызывается один раз для каждого элемента набора, передавая элемент в качестве параметра.
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"}>}
Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 176 def clear @hash.clear self end
Удаляет все элементы и возвращает self.
set = Set[1, 'c', :s] #=> #<Set: {1, "c", :s}>
set.clear #=> #<Set: {}>
set #=> #<Set: {}>
# File lib/set.rb, line 401
def collect!
block_given? or return enum_for(__method__) { size }
set = self.class.new
each { |o| set << yield(o) }
replace(set)
end Заменяет элементы теми, которые возвращены collect(). Возвращает перечислитель, если блок не задан.
# 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 Принуждает набор сравнивать свои элементы по их идентичности и возвращает self. Этот метод может быть не поддерживается всеми подклассами Set.
# File lib/set.rb, line 118 def compare_by_identity? @hash.respond_to?(:compare_by_identity?) && @hash.compare_by_identity? end
Возвращает true, если набор будет сравнивать свои элементы по их идентичности. Также см. #compare_by_identity.
# File lib/set.rb, line 366 def delete(o) @hash.delete(o) self end
Удаляет заданный объект из набора и возвращает self. Используйте subtract для удаления сразу нескольких элементов.
# File lib/set.rb, line 373 def delete?(o) delete(o) if include?(o) end
Удаляет заданный объект из набора и возвращает self. Если объект не присутствует в наборе, возвращает nil.
# File lib/set.rb, line 380
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 Удаляет каждый элемент набора, для которого блок возвращает true, и возвращает self. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 329 def disjoint?(set) !intersect?(set) end
Возвращает true, если у набора и заданного набора нет общих элементов. Этот метод является противоположностью intersect?.
Set[1, 2, 3].disjoint? Set[3, 4] #=> false Set[1, 2, 3].disjoint? Set[4, 5] #=> true
# File lib/set.rb, line 595
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 Разделяет набор на множество подмножеств в соответствии с общностью, определенной заданным блоком.
Если арность блока равна 2, элементы o1 и o2 являются общими, если block.call(o1, o2) равно true. В противном случае, элементы o1 и o2 являются общими, если 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}>}>
Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 336
def each(&block)
block or return enum_for(__method__) { size }
@hash.each_key(&block)
self
end Вызывает заданный блок один раз для каждого элемента в наборе, передавая элемент в качестве параметра. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 167 def empty? @hash.empty? end
Возвращает true, если набор не содержит элементов.
# File lib/set.rb, line 237 def flatten self.class.new.flatten_merge(self) end
Возвращает новый набор, являющийся копией набора, рекурсивно раскрывающим каждый содержащий набор.
# File lib/set.rb, line 243
def flatten!
replace(flatten()) if any? { |e| e.is_a?(Set) }
end Эквивалентно #flatten, но заменяет получатель результат на месте. Возвращает nil, если изменения не были внесены.
# File lib/set.rb, line 253 def include?(o) @hash[o] end
Возвращает true, если набор содержит заданный объект.
Обратите внимание, что include? и member? не проверяют равенство членов с помощью ==, как и другие Enumerables.
См. также Enumerable#include?
# File lib/set.rb, line 140 def initialize_clone(orig) super @hash = orig.instance_variable_get(:@hash).clone end
Клонирование внутренней хеш-таблицы.
# File lib/set.rb, line 134 def initialize_dup(orig) super @hash = orig.instance_variable_get(:@hash).dup end
Дублирование внутренней хеш-таблицы.
# File lib/set.rb, line 629
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 Возвращает строку, содержащую удобочитаемое представление набора («#<Set: {элемент1, элемент2, …}>»).
# File lib/set.rb, line 315
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 Возвращает true, если у набора и заданного набора есть хотя бы один общий элемент.
Set[1, 2, 3].intersect? Set[4, 5] #=> false Set[1, 2, 3].intersect? Set[3, 4] #=> true
# File lib/set.rb, line 391
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 Удаляет каждый элемент набора, для которого блок возвращает false, и возвращает self. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 429
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 Объединяет элементы заданного перечислимого объекта в набор и возвращает self.
# File lib/set.rb, line 298
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 Возвращает true, если набор является собственным подмножеством заданного набора.
# File lib/set.rb, line 272
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 Возвращает true, если набор является собственным надмножеством заданного набора.
# File lib/set.rb, line 411
def reject!(&block)
block or return enum_for(__method__) { size }
n = size
delete_if(&block)
self if size != n
end Эквивалентно #delete_if, но возвращает nil, если изменений не было. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 187
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 Заменяет содержимое набора содержимым заданного перечислимого объекта и возвращает 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 523
def reset
if @hash.respond_to?(:rehash)
@hash.rehash # This should perform frozenness check.
else
raise "can't modify frozen #{self.class.name}" if frozen?
end
self
end Сбрасывает внутреннее состояние после изменения существующих элементов и возвращает self.
Элементы будут переиндексированы и дубликаты будут удалены.
# File lib/set.rb, line 420
def select!(&block)
block or return enum_for(__method__) { size }
n = size
keep_if(&block)
self if size != n
end Эквивалентно #keep_if, но возвращает nil, если изменений не было. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 161 def size @hash.size end
Возвращает количество элементов.
# File lib/set.rb, line 285
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 Возвращает true, если набор является подмножеством заданного набора.
# File lib/set.rb, line 441
def subtract(enum)
do_with_enum(enum) { |o| delete(o) }
self
end Удаляет каждый элемент, который встречается в заданном перечислимом объекте, и возвращает self.
# File lib/set.rb, line 259
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 Возвращает true, если набор является надмножеством заданного набора.
# File lib/set.rb, line 202 def to_a @hash.keys end
Преобразует набор в массив. Порядок элементов не определён.
Set[1, 2].to_a #=> [1, 2] Set[1, 'c', :s].to_a #=> [1, "c", :s]
# File lib/set.rb, line 211 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
Возвращает self, если аргументов нет. В противном случае преобразует множество в другое с помощью klass.new(self, *args, &block).
В подклассах возвращает klass.new(self, *args, &block), если не переопределено.
# File lib/set.rb, line 451 def |(enum) dup.merge(enum) end
Возвращает новое множество, созданное путём объединения множества и элементов заданного перечислимого объекта.
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}>
Ruby Core © 1993–2017 Yukihiro Matsumoto
Licensed under the Ruby License.
Ruby Standard Library © contributors
Licensed under their own licenses.
