This documentation is automatically generated by online-judge-tools/verification-helper
spec/datastructure/multi_set_spec.cr
- View this file on GitHub
- Last update: 2022-04-14 15:58:09+09:00
Depends on
Code
require "spec"
require "../../src/datastructure/multi_set"
describe MultiSet do
it "#initialize" do
MultiSet(Int32).new.to_s.should eq "MultiSet{}"
MultiSet.new([0, 1, 2, 2]).to_s.should eq "MultiSet{0, 1, 2, 2}"
MultiSet{0, 1, 2, 2}.to_s.should eq "MultiSet{0, 1, 2, 2}"
end
it ".from_counts" do
MultiSet.from_counts([{0, 1}]).should eq MultiSet{0}
MultiSet.from_counts([{0, 3}]).should eq MultiSet{0, 0, 0}
MultiSet.from_counts([{1, 1}, {2, 2}, {3, 3}]).should eq MultiSet{1, 2, 2, 3, 3, 3}
expect_raises(ArgumentError) { MultiSet.from_counts [{1, 1}, {2, 2}, {1, 3}] }
expect_raises(ArgumentError) { MultiSet.from_counts [{0, -1}] }
end
it "#size" do
MultiSet{0, 0, 0, 1, 1, 2}.size.should eq 6
MultiSet(Int32).new.size.should eq 0
end
it "#kind_count" do
MultiSet{0, 0, 1, 2}.kind_count.should eq 3
MultiSet(Int32).new.kind_count.should eq 0
end
it "#==" do
a = MultiSet{1, 2, 2}
(a == MultiSet{1, 2, 2}).should be_true
(a == MultiSet{1, 2}).should be_false
(a == MultiSet{1i64, 2i64, 2i64}).should be_true
end
it "#add, #<<" do
a = MultiSet(Int32).new
a.add(1).should be a
a.add(2) << 1
a.should eq MultiSet{1, 1, 2}
a.add(3, 5).should be a
a.add 2, 3
a.should eq MultiSet.from_counts [{1, 2}, {2, 4}, {3, 5}]
end
it "#delete" do
a = MultiSet{1, 1, 1, 1, 1, 2, 2, 3}
a.delete(2).should be_true
a.should eq MultiSet{1, 1, 1, 1, 1, 2, 3}
a.delete(1, 3).should be_true
a.should eq MultiSet{1, 1, 2, 3}
a.delete(3, 128).should be_true
a.should eq MultiSet{1, 1, 2}
a.delete(3).should be_false
a.should eq MultiSet{1, 1, 2}
expect_raises(ArgumentError) { a.delete 1, -1 }
end
it "#concat" do
a = MultiSet{1, 1, 1, 1, 1, 2, 2, 3}
a.concat a
a.should eq MultiSet.from_counts [{1, 10}, {2, 4}, {3, 2}]
a.concat({0, 0, 0, 1, 2, 3})
a.should eq MultiSet.from_counts [{1, 11}, {2, 5}, {3, 3}, {0, 3}]
end
it "#clear" do
a = MultiSet{0, 0, 1, 1}
a.clear.should be a
a.should eq MultiSet(Int32).new
end
it "#count" do
a = MultiSet{0, 0, 0, 1, 1, 2}
a.count(0).should eq 3
a.count(1).should eq 2
a.count(2).should eq 1
a.count(3).should eq 0
end
it "#includes?, #===" do
a = MultiSet{0, 0, 0, 1, 1, 2}
4.times do |i|
a.includes?(i).should eq i < 3
(a === i).should eq i < 3
end
end
it "#empty?" do
MultiSet{0}.should_not be_empty
MultiSet(Int32).new.should be_empty
end
it "#intersects?" do
a = MultiSet{0, 0, 0, 1, 1, 2}
b = MultiSet{2, 3}
c = MultiSet{3, 3, 3, 4, 4, 5}
a.intersects?(b).should be_true
b.intersects?(c).should be_true
a.intersects?(c).should be_false
end
it "#subset_of?" do
a = MultiSet{0, 0, 0, 1, 1, 2}
b = MultiSet{0, 1, 0}
c = MultiSet{-1, 0, 0, 1}
a.subset_of?(b).should be_false
b.subset_of?(a).should be_true
c.subset_of?(a).should be_false
end
it "#superset_of?" do
a = MultiSet{0, 0, 0, 1, 1, 2}
b = MultiSet{0, 1, 0}
c = MultiSet{-1, 0, 0, 1}
a.superset_of?(b).should be_true
b.superset_of?(a).should be_false
c.superset_of?(a).should be_false
end
it "#each" do
a = MultiSet{0, 0, 0, 1, 1, 2}
a.each.to_a.should eq [0, 0, 0, 1, 1, 2]
a.each.max.should eq 2
end
it "#each(&)" do
a = [] of Int32
MultiSet{0, 0, 0, 1, 1, 2}.each do |elem|
a << elem
end
a.should eq [0, 0, 0, 1, 1, 2]
end
it "#each_count" do
MultiSet{0, 0, 0, 1, 1, 2}.each_count.max.should eq({2, 1})
end
it "#each_count(&)" do
a = [] of {Int32, Int32}
MultiSet{0, 0, 0, 1, 1, 2}.each_count do |elem, cnt|
a << {elem, cnt}
end
a.should eq [{0, 3}, {1, 2}, {2, 1}]
end
it "#&" do
a = MultiSet{0, 0, 0, 1, 1, 2, 3}
b = MultiSet{0, 1, 1, 2, 2, 2}
(a & b).should eq MultiSet{0, 1, 1, 2}
a = MultiSet{1, 2, 2, 3, 3, 3}
b = MultiSet{2, 3, 3, 4}
(a & b).should eq MultiSet{2, 3, 3}
end
it "#|, #+" do
a = MultiSet{0, 0, 0, 1, 1, 2, 3}
b = MultiSet{0, 1, 1, 2, 2, 2}
c = MultiSet{0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3}
(a | b).should eq c
(a + b).should eq c
end
it "#-" do
a = MultiSet{0, 1, 2, 2, 3, 3}
b = MultiSet{1, 2, 3, 3, 3, 4}
(a - b).should eq MultiSet{0, 2}
(a - b.to_a).should eq MultiSet{0, 2}
end
it "#*" do
a = MultiSet{1, 2, 2}
(a * 10).should eq MultiSet.from_counts [{1, 10}, {2, 20}]
(a * 0).should be_empty
expect_raises(ArgumentError) { a * -1 }
end
it "#subtract" do
a = MultiSet{1, 2, 2, 3}
a.subtract(MultiSet{1, 1, 2}).should be a
a.should eq MultiSet{2, 3}
a = MultiSet{1, 2, 2, 3}
a.subtract([1, 1, 2]).should be a
a.should eq MultiSet{2, 3}
end
it "#dup" do
a = MultiSet{1, 2, 2, 3}
b = a.dup
b.should eq a
b.should_not be a
end
it "#clone" do
a = MultiSet{[1, 2, 3]}
b = a.clone
b.should eq a
b.should_not be a
a.to_a[0].should_not be b.to_a[0]
end
it "#to_s" do
MultiSet{0, 0, 0, 1, 1, 2}.to_s.should eq "MultiSet{0, 0, 0, 1, 1, 2}"
end
it "#inspect" do
MultiSet{0, 0, 0, 1, 1, 2}.inspect.should eq "{0(3), 1(2), 2(1)}"
MultiSet{0, 1, 2, 0, 1, 0}.inspect.should eq "{0(3), 1(2), 2(1)}"
end
it "includes Iterable" do
MultiSet{0, 0, 0, 1, 1, 2}.each_slice(3).to_a.should eq [[0, 0, 0], [1, 1, 2]]
MultiSet{0, 0, 0, 1, 1, 2}.each_cons(2).select { |(i, j)| i != j }.to_a.should eq [[0, 1], [1, 2]]
end
it "includes Enumeratable" do
a = MultiSet{0, 0, 0, 1, 1, 2}
a.all?(&.even?).should be_false
a.all? { |i| i >= 0 }.should be_true
a.max.should eq 2
MultiSet{"a", "ab", "abc", "abcd"}.max_by(&.size).should eq "abcd"
a.first.should eq 0
a.index(1).should eq 3
a.join.should eq "000112"
end
endrequire "spec"
# require "../../src/datastructure/multi_set"
class MultiSet(T)
include Iterable(T)
include Enumerable(T)
@count = Hash(T, Int32).new(0)
@size = 0
# Returns the additive identity of this type.
#
# This is an empty multiset
def self.additive_identify : self
new
end
# Creates a new, empty multiset.
def initialize(initial_capacity = nil)
@count = Hash(T, Int32).new(0, initial_capacity: initial_capacity)
end
# Creates a new multiset from the elements in *elements*.
def initialize(elements : Enumerable(T))
@count = Hash(T, Int32).new(0)
concat elements
end
# Creates a new multiset from the enumerable of {element, count}.
def self.from_counts(counts : Enumerable({T, Int32})) : MultiSet(T)
counts.each_with_object(MultiSet(T).new) do |(elem, cnt), set|
raise ArgumentError.new "Duplicate element: #{elem}" if set.includes?(elem)
raise ArgumentError.new "Negative count: #{cnt}" if cnt < 0
set.@count[elem] += cnt
end
end
protected def initialize(*, @count : Hash(T, Int32), @size : Int32)
end
# Returns the number of elements in the set.
def size : Int32
@size
end
# Returns the number of kinds in the multiset.
def kind_count : Int32
@count.size
end
# Returns `true` if the multiset is empty.
def empty? : Bool
size == 0
end
# Compares with *other*.
def ==(other : MultiSet) : Bool
@count == other.@count
end
# Returns `true` if *object* exists in the multiset.
def includes?(object : T) : Bool
@count[object] > 0
end
# :ditto:
def ===(object : T) : Bool
includes?(object)
end
# Returns the number of times that the *object* is present in the multiset.
def count(object : T)
@count[object]
end
# Adds *object* to the multiset and returns `self`.
def add(object : T) : self
@count[object] += 1
@size += 1
self
end
# :ditto:
def <<(object : T) : self
add object
end
# Adds *object* to the multiset *count* times and returns `self`.
def add(object : T, count : Int32) : self
raise ArgumentError.new unless count >= 0
@count[object] += count
@size += count
self
end
# Removes the *object* from the multiset and returns `true` if it was present, otherwise returns `false`.
def delete(object : T) : Bool
if flag = @count[object] > 0
@count[object] -= 1
@count.delete(object) if @count[object] == 0
end
flag
end
# Removes the *object* from the multiset at most *count* times and returns `true`
# if it was present, otherwise returns `false`.
def delete(object : T, count : Int32) : Bool
raise ArgumentError.new unless count >= 0
if flag = @count[object] > 0
@count[object] = {0, @count[object] - count}.max
@count.delete(object) if @count[object] == 0
end
flag
end
# Adds `each` element of *elems* to the multisetset and returns `self`.
def concat(elems) : self
elems.each { |elem| self << elem }
self
end
# Removes all elements in the multiset and returns `self`.
def clear : self
@count.clear
@size = 0
self
end
private class MultiSetIterator(T)
include Iterator(T)
include IteratorWrapper
@iterator : Iterator({T, Int32})
@value : Tuple(T?, Int32)
def initialize(count : Hash(T, Int32))
@iterator = count.each
@value = {nil, 0}
end
def next
until @value[1] > 0
@value = wrapped_next
end
@value = {@value[0], @value[1] - 1}
@value[0].not_nil!
end
end
# Returns an iterator for each element of the multiset.
def each
MultiSetIterator(T).new(@count)
end
# Yields each element of the multiset, and returns `nil`.
def each(&) : Nil
@count.each do |(elem, cnt)|
cnt.times { yield elem }
end
end
# Returns `true` if the multiset and the given multiset have at least one element in common.
def intersects?(other : self) : Bool
if kind_count < other.kind_count
any? { |o| other.includes?(o) }
else
other.any? { |o| includes?(o) }
end
end
# Returns `true` if the multiset is a subset of the given multiset.
def subset_of?(other : self) : Bool
return false if other.size < size
all? { |o| other.includes?(o) }
end
# Returns true if the multiset is a superset of the given multiset.
def superset_of?(other : self) : Bool
other.subset_of?(self)
end
# Returns an iterator for each tuple of element and count of the multiset
def each_count
@count.each
end
# Yields each pair of element and count of the multiset, and returns `nil`.
def each_count(&) : Nil
@count.each do |(elem, cnt)|
yield(elem, cnt)
end
end
# Intersection.
#
# ```
# MultiSet{1, 2, 2, 3} & MultiSet{2, 3, 3, 4} # => MultiSet{2, 3}
# ```
def &(other : MultiSet(T)) : self
small, large = self, other
if large.kind_count < small.kind_count
small, large = large, small
end
result = MultiSet(T).new
small.each_count do |elem, small_cnt|
large_cnt = large.count(elem)
result.add elem, Math.min(small_cnt, large_cnt) if large_cnt > 0
end
result
end
# Union.
#
# ```
# MultiSet{1, 2, 2} | MultiSet{2, 3} # => MultiSet{1, 2, 2, 3}
# ```
def |(other : MultiSet(U)) : MultiSet(T | U) forall U
result = MultiSet(T | U).new
each_count { |elem, cnt| result.add elem, cnt }
other.each_count { |elem, cnt| result.add elem, cnt }
result
end
# Addition. Same as `#|`.
def +(other : MultiSet(U)) : MultiSet(T | U) forall U
self | other
end
# Difference.
#
# ```
# MultiSet{1, 2, 2, 3} - MultiSet{1, 2} # => MultiSet{2, 3}
# MultiSet{1, 2, 2, 3} - [1, 2] # => MultiSet{2, 3}
# ```
def -(other : MultiSet) : self
dup.subtract other
end
# :ditto:
def -(other : Enumerable) : self
dup.subtract other
end
# Repetition
#
# ```
# MultiSet{1, 2, 2} * 2 # => MultiSet{1, 1, 2, 2, 2, 2}
# ```
def *(times : Int) : self
if times == 0 || empty?
MultiSet(T).new
elsif times == 1
dup
else
set = MultiSet(T).new(@count.size)
each_count do |elem, cnt|
set.add elem, cnt * times
end
set
end
end
# Returns `self` after removing *other* elements.
#
# ```
# MultiSet{1, 2, 2, 3}.subtract MultiSet{1, 2} # => MultiSet{2, 3}
# MultiSet{1, 2, 2, 3}.subtract [1, 2] # => MultiSet{2, 3}
# ```
def subtract(other : MultiSet(U)) : self forall U
other.each_count do |elem, cnt|
delete elem, cnt
end
self
end
# :ditto:
def subtract(other : Enumerable) : self forall U
other.each do |elem|
delete elem
end
self
end
# Returns a new multiset with all of the same elements.
def dup : self
MultiSet(T).new count: @count.dup, size: @size
end
# Returns a new multiset with all of the elements cloned.
def clone : self
set = MultiSet(T).new(@count.size)
each_count do |elem, cnt|
set.add elem.clone, cnt
end
set
end
# Writes a string representation of the multiset to *io*.
#
# ```
# set = MultiSet{3, 1, 4, 1, 5}
# set.to_s # => "MultiSet{3, 1, 1, 4, 5}"
# ```
def to_s(io : IO) : Nil
io << "MultiSet{"
each.join(", ", io)
io << '}'
end
# Writes a string representation of the multiset to *io*.
#
# ```
# set = MultiSet{3, 1, 4, 1, 5}
# set.inspect # => "{3(1), 1(2), 4(1), 5(1)}"
# ```
def inspect(io : IO) : Nil
io << '{'
each_count.join(", ", io) do |(elem, count), io|
io << elem << '(' << count << ')'
end
io << '}'
end
end
describe MultiSet do
it "#initialize" do
MultiSet(Int32).new.to_s.should eq "MultiSet{}"
MultiSet.new([0, 1, 2, 2]).to_s.should eq "MultiSet{0, 1, 2, 2}"
MultiSet{0, 1, 2, 2}.to_s.should eq "MultiSet{0, 1, 2, 2}"
end
it ".from_counts" do
MultiSet.from_counts([{0, 1}]).should eq MultiSet{0}
MultiSet.from_counts([{0, 3}]).should eq MultiSet{0, 0, 0}
MultiSet.from_counts([{1, 1}, {2, 2}, {3, 3}]).should eq MultiSet{1, 2, 2, 3, 3, 3}
expect_raises(ArgumentError) { MultiSet.from_counts [{1, 1}, {2, 2}, {1, 3}] }
expect_raises(ArgumentError) { MultiSet.from_counts [{0, -1}] }
end
it "#size" do
MultiSet{0, 0, 0, 1, 1, 2}.size.should eq 6
MultiSet(Int32).new.size.should eq 0
end
it "#kind_count" do
MultiSet{0, 0, 1, 2}.kind_count.should eq 3
MultiSet(Int32).new.kind_count.should eq 0
end
it "#==" do
a = MultiSet{1, 2, 2}
(a == MultiSet{1, 2, 2}).should be_true
(a == MultiSet{1, 2}).should be_false
(a == MultiSet{1i64, 2i64, 2i64}).should be_true
end
it "#add, #<<" do
a = MultiSet(Int32).new
a.add(1).should be a
a.add(2) << 1
a.should eq MultiSet{1, 1, 2}
a.add(3, 5).should be a
a.add 2, 3
a.should eq MultiSet.from_counts [{1, 2}, {2, 4}, {3, 5}]
end
it "#delete" do
a = MultiSet{1, 1, 1, 1, 1, 2, 2, 3}
a.delete(2).should be_true
a.should eq MultiSet{1, 1, 1, 1, 1, 2, 3}
a.delete(1, 3).should be_true
a.should eq MultiSet{1, 1, 2, 3}
a.delete(3, 128).should be_true
a.should eq MultiSet{1, 1, 2}
a.delete(3).should be_false
a.should eq MultiSet{1, 1, 2}
expect_raises(ArgumentError) { a.delete 1, -1 }
end
it "#concat" do
a = MultiSet{1, 1, 1, 1, 1, 2, 2, 3}
a.concat a
a.should eq MultiSet.from_counts [{1, 10}, {2, 4}, {3, 2}]
a.concat({0, 0, 0, 1, 2, 3})
a.should eq MultiSet.from_counts [{1, 11}, {2, 5}, {3, 3}, {0, 3}]
end
it "#clear" do
a = MultiSet{0, 0, 1, 1}
a.clear.should be a
a.should eq MultiSet(Int32).new
end
it "#count" do
a = MultiSet{0, 0, 0, 1, 1, 2}
a.count(0).should eq 3
a.count(1).should eq 2
a.count(2).should eq 1
a.count(3).should eq 0
end
it "#includes?, #===" do
a = MultiSet{0, 0, 0, 1, 1, 2}
4.times do |i|
a.includes?(i).should eq i < 3
(a === i).should eq i < 3
end
end
it "#empty?" do
MultiSet{0}.should_not be_empty
MultiSet(Int32).new.should be_empty
end
it "#intersects?" do
a = MultiSet{0, 0, 0, 1, 1, 2}
b = MultiSet{2, 3}
c = MultiSet{3, 3, 3, 4, 4, 5}
a.intersects?(b).should be_true
b.intersects?(c).should be_true
a.intersects?(c).should be_false
end
it "#subset_of?" do
a = MultiSet{0, 0, 0, 1, 1, 2}
b = MultiSet{0, 1, 0}
c = MultiSet{-1, 0, 0, 1}
a.subset_of?(b).should be_false
b.subset_of?(a).should be_true
c.subset_of?(a).should be_false
end
it "#superset_of?" do
a = MultiSet{0, 0, 0, 1, 1, 2}
b = MultiSet{0, 1, 0}
c = MultiSet{-1, 0, 0, 1}
a.superset_of?(b).should be_true
b.superset_of?(a).should be_false
c.superset_of?(a).should be_false
end
it "#each" do
a = MultiSet{0, 0, 0, 1, 1, 2}
a.each.to_a.should eq [0, 0, 0, 1, 1, 2]
a.each.max.should eq 2
end
it "#each(&)" do
a = [] of Int32
MultiSet{0, 0, 0, 1, 1, 2}.each do |elem|
a << elem
end
a.should eq [0, 0, 0, 1, 1, 2]
end
it "#each_count" do
MultiSet{0, 0, 0, 1, 1, 2}.each_count.max.should eq({2, 1})
end
it "#each_count(&)" do
a = [] of {Int32, Int32}
MultiSet{0, 0, 0, 1, 1, 2}.each_count do |elem, cnt|
a << {elem, cnt}
end
a.should eq [{0, 3}, {1, 2}, {2, 1}]
end
it "#&" do
a = MultiSet{0, 0, 0, 1, 1, 2, 3}
b = MultiSet{0, 1, 1, 2, 2, 2}
(a & b).should eq MultiSet{0, 1, 1, 2}
a = MultiSet{1, 2, 2, 3, 3, 3}
b = MultiSet{2, 3, 3, 4}
(a & b).should eq MultiSet{2, 3, 3}
end
it "#|, #+" do
a = MultiSet{0, 0, 0, 1, 1, 2, 3}
b = MultiSet{0, 1, 1, 2, 2, 2}
c = MultiSet{0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3}
(a | b).should eq c
(a + b).should eq c
end
it "#-" do
a = MultiSet{0, 1, 2, 2, 3, 3}
b = MultiSet{1, 2, 3, 3, 3, 4}
(a - b).should eq MultiSet{0, 2}
(a - b.to_a).should eq MultiSet{0, 2}
end
it "#*" do
a = MultiSet{1, 2, 2}
(a * 10).should eq MultiSet.from_counts [{1, 10}, {2, 20}]
(a * 0).should be_empty
expect_raises(ArgumentError) { a * -1 }
end
it "#subtract" do
a = MultiSet{1, 2, 2, 3}
a.subtract(MultiSet{1, 1, 2}).should be a
a.should eq MultiSet{2, 3}
a = MultiSet{1, 2, 2, 3}
a.subtract([1, 1, 2]).should be a
a.should eq MultiSet{2, 3}
end
it "#dup" do
a = MultiSet{1, 2, 2, 3}
b = a.dup
b.should eq a
b.should_not be a
end
it "#clone" do
a = MultiSet{[1, 2, 3]}
b = a.clone
b.should eq a
b.should_not be a
a.to_a[0].should_not be b.to_a[0]
end
it "#to_s" do
MultiSet{0, 0, 0, 1, 1, 2}.to_s.should eq "MultiSet{0, 0, 0, 1, 1, 2}"
end
it "#inspect" do
MultiSet{0, 0, 0, 1, 1, 2}.inspect.should eq "{0(3), 1(2), 2(1)}"
MultiSet{0, 1, 2, 0, 1, 0}.inspect.should eq "{0(3), 1(2), 2(1)}"
end
it "includes Iterable" do
MultiSet{0, 0, 0, 1, 1, 2}.each_slice(3).to_a.should eq [[0, 0, 0], [1, 1, 2]]
MultiSet{0, 0, 0, 1, 1, 2}.each_cons(2).select { |(i, j)| i != j }.to_a.should eq [[0, 1], [1, 2]]
end
it "includes Enumeratable" do
a = MultiSet{0, 0, 0, 1, 1, 2}
a.all?(&.even?).should be_false
a.all? { |i| i >= 0 }.should be_true
a.max.should eq 2
MultiSet{"a", "ab", "abc", "abcd"}.max_by(&.size).should eq "abcd"
a.first.should eq 0
a.index(1).should eq 3
a.join.should eq "000112"
end
end