класс Set
Эта библиотека предоставляет класс Set, который реализует коллекцию неупорядоченных значений без дубликатов. Это гибрид интуитивных возможностей взаимодействия массива (Array) и быстрого поиска хеша (Hash).
Метод to_set добавлен в Enumerable для удобства.
Set легко использовать с объектами Enumerable (реализующими each). Большинство методов инициализации и бинарных операторов принимают обобщённые объекты Enumerable помимо множеств и массивов. Объект Enumerable может быть преобразован в Set с помощью метода to_set.
Set использует Hash в качестве хранилища, поэтому необходимо учесть следующие моменты:
-
Равенство элементов определяется в соответствии с
Object#eql?иObject#hash. ИспользуйтеSet#compare_by_identity, чтобы множество сравнивало элементы по их идентичности. -
Setпредполагает, что идентичность каждого элемента не изменяется во время его хранения. Изменение элемента множества сделает множество ненадежным. -
Когда строка должна быть сохранена, вместо неё сохраняется замороженная копия строки, если только исходная строка не является замороженной.
Сравнение
Операторы сравнения <, >, <=, и >= реализованы как сокращения для методов {proper_,}{subset?,superset?} . Оператор <=> отражает этот порядок или возвращает nil для множеств, которые оба имеют уникальные элементы ({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
Контакты
-
Акинори Муша <knu@iDaemons.org> (текущий основной разработчик)
Что здесь
Сначала, что где-то ещё. Класс Set:
-
Наследуется от класса Object.
-
Включает модуль Enumerable, который предоставляет десятки дополнительных методов.
В частности, класс Set не имеет многих собственных методов для извлечения или итерации. Вместо этого он полагается на методы в Enumerable.
Здесь класс Set предоставляет методы, полезные для:
Методы для создания множества
-
::[]: Возвращает новое множество, содержащее заданные объекты. -
::new: Возвращает новое множество, содержащее заданные объекты (если блок не задан) или возвращаемые значения вызываемого блока (если блок задан).
Методы для операций над множествами
-
| (алиас
unionи+): Возвращает новое множество, содержащее все элементы изselfи все элементы из заданного перечисляемого (без дубликатов). -
& (алиас
intersection): Возвращает новое множество, содержащее все элементы, общие дляselfи заданного перечисляемого. -
- (алиас
difference): Возвращает копиюselfсо всеми элементами из заданного перечисляемого, удалёнными. -
^: Возвращает новое множество, содержащее все элементы из
selfи заданного перечисляемого, кроме тех, которые общие для обоих.
Методы для сравнения
-
<=>: Возвращает -1, 0 или 1, в зависимости от того,
selfменьше, равно или больше заданного объекта. -
==: Возвращает true, если
selfи заданный перечисляемый равны, как определяетсяObject#eql?. -
compare_by_identity?: Возвращает true, если множество учитывает только идентичность при сравнении элементов.
Методы для запросов
-
empty?: Возвращает true, если множество пусто. -
include?(алиасыmember?и===): Возвращает true, если заданный объект является элементом множества. -
subset?(алиас <=): Возвращает true, если заданный объект является подмножеством множества. -
proper_subset?(алиас <): Возвращает true, если заданный перечисляемый является собственным подмножеством множества. -
superset?(алиас >=): Возвращает true, если заданный перечисляемый является надмножеством множества. -
proper_superset?(алиас >): Возвращает true, если заданный перечисляемый является собственным надмножеством множества. -
disjoint?: Возвращает true, если множество и заданный перечисляемый не имеют общих элементов,falseв противном случае. -
intersect?: Возвращает true, если множество и заданный перечисляемый имеют общие элементы,falseв противном случае. -
compare_by_identity?: Возвращает true, если множество учитывает только идентичность при сравнении элементов.
Методы для присваивания
-
add(алиас<<): Добавляет заданный объект в множество; возвращаетself. -
add?: Если заданный объект не является элементом множества, добавляет его и возвращаетself; в противном случае, возвращаетnil. -
merge: Объединяет элементы каждого заданного перечисляемого объекта в множество; возвращаетself. -
replace: Заменяет содержимое множества содержимым заданного перечисляемого.
Методы для удаления
-
clear: Удаляет все элементы из множества; возвращаетself. -
delete: Удаляет заданный объект из множества; возвращаетself. -
delete?: Если заданный объект является элементом множества, удаляет его и возвращаетself; в противном случае, возвращаетnil. -
subtract: Удаляет каждый заданный объект из множества; возвращаетself. -
delete_if- Удаляет элементы, указанные заданным блоком. -
select!(алиасfilter!): Удаляет элементы, не указанные заданным блоком. -
keep_if: Удаляет элементы, не указанные заданным блоком. -
reject!Удаляет элементы, указанные заданным блоком.
Методы для преобразования
-
classify: Возвращает хеш, который классифицирует элементы, как определено заданным блоком. -
collect!(алиасmap!): Заменяет каждый элемент значением, возвращаемым блоком. -
divide: Возвращает хеш, который классифицирует элементы, как определено заданным блоком; отличается отclassifyтем, что блок может принимать либо один, либо два аргумента. -
flatten: Возвращает новое множество, которое является рекурсивным уплощениемself.flatten!: Заменяет каждое вложенное множество вselfэлементами из этого множества. -
inspect(алиасto_s): Возвращает строку, отображающую элементы. -
join: Возвращает строку, содержащую все элементы, преобразованные в строки по мере необходимости, и соединённые заданным разделителем строк. -
to_a: Возвращает массив, содержащий все элементы множества. -
to_set: Возвращаетself, если не заданы аргументы и блок; если задан блок, возвращает новое множество, состоящее из возвращаемых значений блока.
Методы для итерации
-
each: Вызывает блок для каждого последующего элемента; возвращаетself.
Другие методы
-
reset: Сбрасывает внутреннее состояние; полезно, если объект был изменён, пока элемент находился в наборе.
Константы
- VERSION
Методы класса
# File lib/set.rb, line 228 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 ext/json/lib/json/add/set.rb, line 9 def self.json_create(object) new object['a'] end
См. as_json.
# File lib/set.rb, line 243
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 640
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 Возвращает новый набор, содержащий элементы, общие для набора и заданного перечислимого объекта.
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 630 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 453 def <=>(set) return unless set.is_a?(Set) case size <=> set.size when -1 then -1 if proper_subset?(set) when +1 then +1 if proper_superset?(set) else 0 if self.==(set) end end
Возвращает 0, если наборы равны, -1 / +1, если набор является собственным подмножеством / надмножеством заданного набора, или nil, если оба имеют уникальные элементы.
# File lib/set.rb, line 674
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 661
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 511 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 523 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 ext/json/lib/json/add/set.rb, line 28
def as_json(*)
{
JSON.create_id => self.class.name,
'a' => to_a,
}
end Методы Set#as_json и Set.json_create могут использоваться для сериализации и десериализации объекта Set; см. Marshal.
Метод Set#as_json сериализует self, возвращая хэш из 2 элементов, представляющий self:
require 'json/add/set'
x = Set.new(%w/foo bar baz/).as_json
# => {"json_class"=>"Set", "a"=>["foo", "bar", "baz"]}
Метод JSON.create десериализует такой хэш, возвращая объект Set:
Set.json_create(x) # => #<Set: {"foo", "bar", "baz"}>
# File lib/set.rb, line 743
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 316 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 564
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 257
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 268 def compare_by_identity? @hash.respond_to?(:compare_by_identity?) && @hash.compare_by_identity? end
Возвращает true, если набор будет сравнивать свои элементы по их идентификаторам. Также см. Set#compare_by_identity.
# File lib/set.rb, line 529 def delete(o) @hash.delete(o) self end
Удаляет заданный объект из набора и возвращает self. Используйте subtract для удаления сразу нескольких элементов.
# File lib/set.rb, line 536 def delete?(o) delete(o) if include?(o) end
Удаляет заданный объект из набора и возвращает self. Если объект не находится в наборе, возвращает nil.
# File lib/set.rb, line 543
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 492 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 Set[1, 2, 3].disjoint? [3, 4] #=> false Set[1, 2, 3].disjoint? 4..5 #=> true
# File lib/set.rb, line 771
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) истинно. В противном случае, элементы 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 499
def each(&block)
block_given? or return enum_for(__method__) { size }
@hash.each_key(&block)
self
end Вызывает заданный блок один раз для каждого элемента в множестве, передавая элемент в качестве параметра. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 307 def empty? @hash.empty? end
Возвращает true, если множество не содержит элементов.
# File lib/set.rb, line 377 def flatten self.class.new.flatten_merge(self) end
Возвращает новое множество, являющееся копией множества, рекурсивно раскрывающего каждое содержащее множество.
# File lib/set.rb, line 383 def flatten! replace(flatten()) if any?(Set) end
Эквивалентно Set#flatten, но заменяет получатель результат на месте. Возвращает nil, если никаких изменений не было.
# File lib/set.rb, line 393 def include?(o) @hash[o] end
Возвращает true, если множество содержит заданный объект.
Обратите внимание, что include? и member? не проверяют равенство членов, используя ==, как это делают другие перечисляемые объекты.
См. также Enumerable#include?
# File lib/set.rb, line 290 def initialize_clone(orig, **options) super @hash = orig.instance_variable_get(:@hash).clone(**options) end
Клонирование внутреннего хэша.
# File lib/set.rb, line 284 def initialize_dup(orig) super @hash = orig.instance_variable_get(:@hash).dup end
Дублирование внутреннего хэша.
# File lib/set.rb, line 811
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 Возвращает строку, содержащую удобочитаемое представление множества (“#<Множество: {элемент1, элемент2, …}>”).
# File lib/set.rb, line 470
def intersect?(set)
case set
when Set
if size < set.size
any?(set)
else
set.any?(self)
end
when Enumerable
set.any?(self)
else
raise ArgumentError, "value must be enumerable"
end
end Возвращает true, если множество и заданный перечисляемый объект имеют хотя бы один общий элемент.
Set[1, 2, 3].intersect? Set[4, 5] #=> false Set[1, 2, 3].intersect? Set[3, 4] #=> true Set[1, 2, 3].intersect? 4..5 #=> false Set[1, 2, 3].intersect? [3, 4] #=> true
# File lib/set.rb, line 803 def join(separator=nil) to_a.join(separator) end
Возвращает строку, созданную путём преобразования каждого элемента множества в строку. См. также: Array#join
# File lib/set.rb, line 554
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 595
def merge(*enums, **nil)
enums.each do |enum|
if enum.instance_of?(self.class)
@hash.update(enum.instance_variable_get(:@hash))
else
do_with_enum(enum) { |o| add(o) }
end
end
self
end Объединяет элементы заданных перечисляемых объектов в множество и возвращает self.
# File lib/set.rb, line 438
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?(set)
else
raise ArgumentError, "value must be a set"
end
end Возвращает true, если множество является собственным подмножеством заданного множества.
# File lib/set.rb, line 412
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?(self)
else
raise ArgumentError, "value must be a set"
end
end Возвращает true, если множество является собственным надмножеством заданного множества.
# File lib/set.rb, line 574
def reject!(&block)
block_given? or return enum_for(__method__) { size }
n = size
delete_if(&block)
self if size != n
end Эквивалентно Set#delete_if, но возвращает nil, если изменений не было. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 327
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 699
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 Сбрасывает внутреннее состояние после изменения существующих элементов и возвращает self.
Элементы будут переиндексированы и дубликаты удалены.
# File lib/set.rb, line 583
def select!(&block)
block_given? or return enum_for(__method__) { size }
n = size
keep_if(&block)
self if size != n
end Эквивалентно Set#keep_if, но возвращает nil, если изменений не было. Возвращает перечислитель, если блок не задан.
# File lib/set.rb, line 301 def size @hash.size end
Возвращает количество элементов.
# File lib/set.rb, line 425
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?(set)
else
raise ArgumentError, "value must be a set"
end
end Возвращает true, если множество является подмножеством заданного множества.
# File lib/set.rb, line 609
def subtract(enum)
do_with_enum(enum) { |o| delete(o) }
self
end Удаляет каждый элемент, который встречается в заданном перечислимом объекте, и возвращает self.
# File lib/set.rb, line 399
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?(self)
else
raise ArgumentError, "value must be a set"
end
end Возвращает true, если множество является надмножеством заданного множества.
# File lib/set.rb, line 342 def to_a @hash.keys end
Преобразует множество в массив. Порядок элементов неопределён.
Set[1, 2].to_a #=> [1, 2] Set[1, 'c', :s].to_a #=> [1, "c", :s]
# File ext/json/lib/json/add/set.rb, line 44 def to_json(*args) as_json.to_json(*args) end
Возвращает строку JSON, представляющую self:
require 'json/add/set' puts Set.new(%w/foo bar baz/).to_json
Вывод:
{"json_class":"Set","a":["foo","bar","baz"]}
# File lib/set.rb, line 351 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 619 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–2022 Yukihiro Matsumoto
Licensed under the Ruby License.
Ruby Standard Library © contributors
Licensed under their own licenses.
