https://github.com/JuliaLang/julia
Tip revision: bd4464b61b1fdd8688dfc53f646970d27c3bb25c authored by Jameson Nash on 29 February 2024, 22:18:08 UTC
codegen: add a pass for late conversion of known modify ops to call atomicrmw
codegen: add a pass for late conversion of known modify ops to call atomicrmw
Tip revision: bd4464b
sets.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
# Set tests
isdefined(Main, :OffsetArrays) || @eval Main include("testhelpers/OffsetArrays.jl")
using .Main.OffsetArrays
using Dates
@testset "Construction, collect" begin
@test Set([1,2,3]) isa Set{Int}
@test Set{Int}([3]) isa Set{Int}
data_in = (1,"banana", ())
s = Set(data_in)
data_out = collect(s)
@test s isa Set{Any}
@test data_out isa Array{Any,1}
@test all(map(in(data_out), data_in))
@test length(data_out) == length(data_in)
let f17741 = x -> x < 0 ? false : 1
@test isa(Set(x for x = 1:3), Set{Int})
@test isa(Set(x for x = 1:3 for j = 1:1), Set{Int})
@test isa(Set(sin(x) for x = 1:3), Set{Float64})
@test isa(Set(f17741(x) for x = 1:3), Set{Int})
@test isa(Set(f17741(x) for x = -1:1), Set{Integer})
@test isa(Set(f17741(x) for x = 1:0), Set{Integer})
end
let s1 = Set(["foo", "bar"]), s2 = Set(s1)
@test s1 == s2
x = pop!(s1)
@test s1 != s2
@test !(x in s1)
@test x in s2
push!(s1, "baz")
push!(s2, "baz2")
@test "baz" in s1
@test !("baz" in s2)
@test !("baz2" in s1)
@test "baz2" in s2
end
end
@testset "hash" begin
s1 = Set(["bar", "foo"])
s2 = Set(["foo", "bar"])
s3 = Set(["baz"])
@test hash(s1) == hash(s2)
@test hash(s1) != hash(s3)
d1 = Dict(Set([3]) => 33, Set([2]) => 22)
d2 = Dict(Set([2]) => 33, Set([3]) => 22)
@test hash(d1) != hash(d2)
end
@testset "equality" for eq in (isequal, ==)
@test eq(Set(), Set())
@test !eq(Set(), Set([1]))
@test eq(Set{Any}(Any[1,2]), Set{Int}([1,2]))
@test !eq(Set{Any}(Any[1,2]), Set{Int}([1,2,3]))
# Comparison of unrelated types
@test eq(Set{Int}(), Set{AbstractString}())
@test !eq(Set{Int}(), Set{AbstractString}([""]))
@test !eq(Set{AbstractString}(), Set{Int}([0]))
@test !eq(Set{Int}([1]), Set{AbstractString}())
@test eq(Set{Any}([1,2,3]), Set{Int}([1,2,3]))
@test eq(Set{Int}([1,2,3]), Set{Any}([1,2,3]))
@test !eq(Set{Any}([1,2,3]), Set{Int}([1,2,3,4]))
@test !eq(Set{Int}([1,2,3]), Set{Any}([1,2,3,4]))
@test !eq(Set{Any}([1,2,3,4]), Set{Int}([1,2,3]))
@test !eq(Set{Int}([1,2,3,4]), Set{Any}([1,2,3]))
# Special cases
@test eq(Set([-0.0]), Set([-0.0]))
@test !eq(Set([0.0]), Set([-0.0]))
@test eq(Set([NaN]), Set([NaN]))
@test !eq(Set([NaN]), Set([1.0]))
@test eq(Set([missing]), Set([missing]))
@test !eq(Set([missing]), Set([1]))
end
@testset "hash and == for Set/BitSet" begin
for s = (Set([1]), Set(1:10), Set(-100:7:100))
b = BitSet(s)
@test hash(s) == hash(b)
@test s == b
end
end
@testset "eltype, empty" begin
s1 = empty(Set([1,"hello"]))
@test isequal(s1, Set())
@test ===(eltype(s1), Any)
s2 = empty(Set{Float32}([2.0f0,3.0f0,4.0f0]))
@test isequal(s2, Set())
@test ===(eltype(s2), Float32)
s3 = empty(Set([1,"hello"]),Float32)
@test isequal(s3, Set())
@test ===(eltype(s3), Float32)
end
@testset "show" begin
@test sprint(show, Set()) == "Set{Any}()"
@test repr([Set(),Set()]) == "Set{Any}[Set(), Set()]"
@test sprint(show, Set(['a'])) == "Set(['a'])"
end
@testset "isempty, length, in, push, pop, delete" begin
# also test for no duplicates
s = Set(); push!(s,1); push!(s,2); push!(s,3)
@test !isempty(s)
@test in(1,s)
@test in(2,s)
@test length(s) == 3
push!(s,1); push!(s,2); push!(s,3)
@test length(s) == 3
@test pop!(s,1) == 1
@test !in(1,s)
@test in(2,s)
@test length(s) == 2
@test_throws KeyError pop!(s,1)
@test pop!(s,1,:foo) === :foo
@test length(delete!(s,2)) == 1
@test !in(1,s)
@test !in(2,s)
@test pop!(s) == 3
@test length(s) == 0
@test isempty(s)
@test_throws ArgumentError pop!(s)
@test length(Set(['x',120])) == 2
# Test that pop! returns the element in the set, not the query
s = Set{Any}(Any[0x01, UInt(2), 3, 4.0])
@test pop!(s, 1) === 0x01
@test pop!(s, 2) === UInt(2)
@test pop!(s, 3) === 3
@test pop!(s, 4) === 4.0
@test_throws KeyError pop!(s, 5)
end
@testset "in!" begin
s = Set()
@test !(in!(0x01, s))
@test !(in!(Int32(2), s))
@test in!(1, s)
@test in!(2.0, s)
(a, b, c...) = sort!(collect(s))
@test a === 0x01
@test b === Int32(2)
@test isempty(c)
# in! will convert to the right type automatically
s = Set{Int32}()
@test !(in!(1, s))
@test only(s) === Int32(1)
@test_throws Exception in!("hello", s)
# Other set types
s = BitSet()
@test !(in!(13, s))
@test in!(UInt16(13), s)
@test only(s) === 13
end
@testset "copy" begin
data_in = (1,2,9,8,4)
s = Set(data_in)
c = copy(s)
@test isequal(s,c)
v = pop!(s)
@test !in(v,s)
@test in(v,c)
push!(s,100)
push!(c,200)
@test !in(100,c)
@test !in(200,s)
end
@testset "copy(::KeySet) (issue #41537)" begin
@test union(keys(Dict(1=>2, 3=>4))) == copy(keys(Dict(1=>2, 3=>4))) == Set([1,3])
end
@testset "copy!" begin
for S = (Set, BitSet)
s = S([1, 2])
for a = ([1], UInt[1], [3, 4, 5], UInt[3, 4, 5])
@test s === copy!(s, Set(a)) == S(a)
@test s === copy!(s, BitSet(a)) == S(a)
end
end
s = Set([1, 2])
s2 = copy(s)
@test copy!(s, s) == s2
end
@testset "sizehint, empty" begin
s = Set([1])
@test isequal(sizehint!(s, 10), Set([1]))
@test isequal(empty!(s), Set())
s2 = GenericSet(s)
sizehint!(s2, 10)
@test s2 == GenericSet(s)
end
@testset "shrinking" begin # Similar test as for the underlying Dict
d = Set(i for i = 1:1000)
filter!(x -> x < 10, d)
sizehint!(d, 10)
@test length(d.dict.slots) < 100
sizehint!(d, 1000)
sizehint!(d, 1; shrink = false)
@test length(d.dict.slots) >= 1000
sizehint!(d, 1; shrink = true)
@test length(d.dict.slots) < 1000
end
@testset "rehash!" begin
# Use a pointer type to have defined behavior for uninitialized
# array element
s = Set(["a", "b", "c"])
Base.rehash!(s)
k = s.dict.keys
Base.rehash!(s)
@test length(k) == length(s.dict.keys)
for i in 1:length(k)
if isassigned(k, i)
@test k[i] == s.dict.keys[i]
else
@test !isassigned(s.dict.keys, i)
end
end
@test s == Set(["a", "b", "c"])
end
@testset "start, done, next" begin
for data_in in ((7, 8, 4, 5),
("hello", 23, 2.7, (), [], (1, 8)))
local data_in, s, t
s = Set(data_in)
s_new = Set()
for el in s
push!(s_new, el)
end
@test isequal(s, s_new)
t = tuple(s...)
@test length(t) == length(s)
for e in t
@test in(e,s)
end
end
end
@testset "union" begin
for S in (Set, BitSet, Vector)
s = ∪(S([1,2]), S([3,4]))
@test s == S([1,2,3,4])
s = union(S([5,6,7,8]), S([7,8,9]))
@test s == S([5,6,7,8,9])
s = S([1,3,5,7])
union!(s, (2,3,4,5))
@test s == S([1,3,5,7,2,4]) # order matters for Vector
let s1 = S([1, 2, 3])
@test s1 !== union(s1) == s1
@test s1 !== union(s1, 2:4) == S([1,2,3,4])
@test s1 !== union(s1, [2,3,4]) == S([1,2,3,4])
@test s1 !== union(s1, [2,3,4], S([5])) == S([1,2,3,4,5])
@test s1 === union!(s1, [2,3,4], S([5])) == S([1,2,3,4,5])
end
end
@test union(Set([1]), BitSet()) isa Set{Int}
@test union(BitSet([1]), Set()) isa BitSet
@test union([1], BitSet()) isa Vector{Int}
# union must uniquify
@test union([1, 2, 1]) == union!([1, 2, 1]) == [1, 2]
@test union([1, 2, 1], [2, 2]) == union!([1, 2, 1], [2, 2]) == [1, 2]
s2 = Set([nothing])
union!(s2, [nothing])
@test s2 == Set([nothing])
@testset "promotion" begin
ints = [1:5, [1, 2], Set([1, 2])]
floats = [2:0.1:3, [2.0, 3.5], Set([2.0, 3.5])]
for a in ints, b in floats
@test eltype(union(a, b)) == Float64
@test eltype(union(b, a)) == Float64
end
end
end
@testset "intersect" begin
for S in (Set, BitSet, Vector)
s = S([1,2]) ∩ S([3,4])
@test s == S()
s = intersect(S([5,6,7,8]), S([7,8,9]))
slong = S(collect(3:63))
# test #36339 length/order short-cut
@test intersect(S([5,6,7,8]), slong) == intersect(slong, S([5,6,7,8]))
@test s == S([7,8])
@test intersect(S([2,3,1]), S([4,2,3]), S([5,4,3,2])) == S([2,3])
let s1 = S([1,2,3])
@test s1 !== intersect(s1) == s1
@test s1 !== intersect(s1, 2:10) == S([2,3])
@test s1 !== intersect(s1, [2,3,4]) == S([2,3])
@test s1 !== intersect(s1, [2,3,4], 3:4) == S([3])
@test s1 === intersect!(s1, [2,3,4], 3:4) == S([3])
end
end
@test intersect(Set([1]), BitSet()) isa Set{Int}
@test intersect(BitSet([1]), Set()) isa Set{Any}
@test intersect(BitSet([1]), Set([1])) isa BitSet
@test intersect(BitSet([1]), Set([1]), Set([1])) isa BitSet
@test intersect([1], BitSet()) isa Vector{Int}
# intersect must uniquify
@test intersect([1, 2, 1]) == intersect!([1, 2, 1]) == [1, 2]
@test intersect([1, 2, 1], [2, 2]) == intersect!([1, 2, 1], [2, 2]) == [2]
# issue #25801
x = () ∩ (:something,)
y = () ∩ (42,)
@test isempty(x)
@test isempty(y)
# Discussed in PR#41769
@testset "promotion" begin
ints = [1:5, [1, 2], Set([1, 2])]
floats = [2:0.1:3, [2.0, 3.5], Set([2.0, 3.5])]
for a in ints, b in floats
@test eltype(intersect(a, b)) == Float64
@test eltype(intersect(b, a)) == Float64
@test eltype(intersect(a, a, b)) == Float64
end
end
# 3-argument version is correctly covered
@test intersect(Set([1,2]), Set([2]), Set([1,2,3])) == Set([2])
@test intersect(Set([1,2]), Set([2]), Set([1.,2,3])) == Set([2.])
end
@testset "setdiff" begin
for S in (Set, BitSet, Vector)
@test setdiff(S([1,2,3]), S()) == S([1,2,3])
@test setdiff(S([1,2,3]), S([1])) == S([2,3])
@test setdiff(S([1,2,3]), S([1,2])) == S([3])
@test setdiff(S([1,2,3]), S([1,2,3])) == S()
@test setdiff(S([1,2,3]), S([4])) == S([1,2,3])
@test setdiff(S([1,2,3]), S([4,1])) == S([2,3])
let s1 = S([1, 2, 3])
@test s1 !== setdiff(s1) == s1
@test s1 !== setdiff(s1, 2:10) == S([1])
@test s1 !== setdiff(s1, [2,3,4]) == S([1])
@test s1 !== setdiff(s1, S([2,3,4]), S([1])) == S()
@test s1 === setdiff!(s1, S([2,3,4]), S([1])) == S()
end
end
@test setdiff(Set([1]), BitSet()) isa Set{Int}
@test setdiff(BitSet([1]), Set()) isa BitSet
@test setdiff([1], BitSet()) isa Vector{Int}
# setdiff must uniquify
@test setdiff([1, 2, 1]) == setdiff!([1, 2, 1]) == [1, 2]
@test setdiff([1, 2, 1], [2, 2]) == setdiff!([1, 2, 1], [2, 2]) == [1]
s = Set([1,3,5,7])
setdiff!(s,(3,5))
@test isequal(s,Set([1,7]))
s = Set([1,2,3,4])
setdiff!(s, Set([2,4,5,6]))
@test isequal(s,Set([1,3]))
# setdiff iterates the shorter set - make sure this algorithm works
sa, sb = Set([1,2,3,4,5,6,7]), Set([2,3,9])
@test Set([1,4,5,6,7]) == setdiff(sa, sb) !== sa
@test Set([1,4,5,6,7]) == setdiff!(sa, sb) === sa
sa, sb = Set([1,2,3,4,5,6,7]), Set([2,3,9])
@test Set([9]) == setdiff(sb, sa) !== sb
@test Set([9]) == setdiff!(sb, sa) === sb
end
@testset "ordering" begin
@test Set() < Set([1])
@test Set([1]) < Set([1,2])
@test !(Set([3]) < Set([1,2]))
@test !(Set([3]) > Set([1,2]))
@test Set([1,2,3]) > Set([1,2])
@test !(Set([3]) <= Set([1,2]))
@test !(Set([3]) >= Set([1,2]))
@test Set([1]) <= Set([1,2])
@test Set([1,2]) <= Set([1,2])
@test Set([1,2]) >= Set([1,2])
@test Set([1,2,3]) >= Set([1,2])
@test !(Set([1,2,3]) >= Set([1,2,4]))
@test !(Set([1,2,3]) <= Set([1,2,4]))
end
@testset "issubset, symdiff, isdisjoint" begin
for S in (Set, BitSet, Vector)
for (l,r) in ((S([1,2]), S([3,4])),
(S([5,6,7,8]), S([7,8,9])),
(S([1,2]), S([3,4])),
(S([5,6,7,8]), S([7,8,9])),
(S([1,2,3]), S()),
(S(), S()),
(S(), S([1,2,3])),
(S([1,2,3]), S([1])),
(S([1,2,3]), S([1,2])),
(S([1,2,3]), S([1,2,3])),
(S([1,2,3]), S([4])),
(S([1,2,3]), S([4,1])))
@test issubset(intersect(l,r), l)
@test issubset(intersect(l,r), r)
@test issubset(l, union(l,r))
@test issubset(r, union(l,r))
@test issubset(union(l,r))(r)
@test isdisjoint(l,l) == isempty(l)
@test isdisjoint(l)(l) == isempty(l)
@test isdisjoint(l,r) == isempty(intersect(l,r))
if S === Vector
@test sort(union(intersect(l,r),symdiff(l,r))) == sort(union(l,r))
else
@test union(intersect(l,r),symdiff(l,r)) == union(l,r)
end
end
if S !== Vector
@test ⊆(S([1]), S([1,2]))
@test ⊊(S([1]), S([1,2]))
@test !⊊(S([1]), S([1]))
@test ⊈(S([1]), S([2]))
@test ⊇(S([1,2]), S([1]))
@test ⊋(S([1,2]), S([1]))
@test !⊋(S([1]), S([1]))
@test ⊉(S([1]), S([2]))
@test ⊆(S([1,2]))(S([1]))
@test ⊊(S([1,2]))(S([1]))
@test !⊊(S([1]))(S([1]))
@test ⊈(S([2]))(S([1]))
@test ⊇(S([1]))(S([1,2]))
@test ⊋(S([1]))(S([1,2]))
@test !⊋(S([1]))(S([1]))
@test ⊉(S([2]))(S([1]))
end
let s1 = S([1,2,3,4])
@test s1 !== symdiff(s1) == s1
@test s1 !== symdiff(s1, S([2,4,5,6])) == S([1,3,5,6])
@test s1 !== symdiff(s1, S([2,4,5,6]), [1,6,7]) == S([3,5,7])
@test s1 === symdiff!(s1, S([2,4,5,6]), [1,6,7]) == S([3,5,7])
end
end
@test symdiff(Set([1,2,3,4]), Set([2,4,5,6])) == Set([1,3,5,6])
@test symdiff(Set([1]), BitSet()) isa Set{Int}
@test symdiff(BitSet([1]), Set{Int}()) isa BitSet
@test symdiff([1], BitSet()) isa Vector{Int}
#symdiff does uniquify
@test symdiff([1, 2, 1]) == symdiff!([1, 2, 1]) == [1,2]
@test symdiff([1, 2, 1], [2, 2]) == symdiff!([1, 2, 1], [2, 2]) == [1]
@test symdiff([1, 2, 1], [2, 2]) == symdiff!([1, 2, 1], [2, 2]) == [1]
# Base.hasfastin
@test all(Base.hasfastin, Any[Dict(1=>2), Set(1), BitSet(1), 1:9, 1:2:9,
Dict, Set, BitSet, UnitRange, StepRange])
@test !any(Base.hasfastin, Any[[1, 2, 3], "123",
Array, String])
# tests for Dict
d1 = Dict(1=>nothing, 2=>nothing)
d2 = Dict(1=>nothing, 3=>nothing)
d3 = Dict(1=>nothing, 2=>nothing, 3=>nothing)
@test d3 == merge(d1, d2)
@test !issubset(d1, d2)
@test !issubset(d2, d1)
@test !issubset(d3, d1)
@test !issubset(d3, d2)
@test issubset(d1, d3)
@test issubset(d2, d3)
# no fast in, long enough container
@test issubset(Set(Bool[]), rand(Bool, 100)) == true
# neither has a fast in, right doesn't have a length
@test isdisjoint([1, 3, 5, 7, 9], Iterators.filter(iseven, 1:10))
# range fast-path
for (truth, a, b) in (
# Integers
(true, 1:10, 11:20), # not overlapping
(false, 1:10, 5:20), # partial overlap
(false, 5:9, 1:10), # complete overlap
# complete overlap, unequal steps
(false, 3:6:60, 9:9:60),
(true, 4:6:60, 9:9:60),
(true, 0:6:12, 9:9:60),
(false, 6:6:18, 9:9:60),
(false, 12:6:18, 9:9:60),
(false, 18:6:18, 9:9:60),
(true, 1:2:3, 2:3:5),
(true, 1:4:5, 2:1:4),
(false, 4:12:124, 1:1:8),
# potential overflow
(false, 0x1:0x3:0x4, 0x4:0x3:0x4),
(true, 0x3:0x3:0x6, 0x4:0x3:0x4),
(false, typemax(Int8):Int8(3):typemax(Int8), typemin(Int8):Int8(3):typemax(Int8)),
# Chars
(true, 'a':'l', 'o':'p'), # not overlapping
(false, 'a':'l', 'h':'p'), # partial overlap
(false, 'a':'l', 'c':'e'), # complete overlap
# Floats
(true, 1.:10., 11.:20.), # not overlapping
(false, 1.:10., 5.:20.), # partial overlap
(false, 5.:9., 1.:10.), # complete overlap
# Inputs that may hang
(false, -6011687643038262928:3545293653953105048, -6446834672754204848:3271267329311042532),
)
@test isdisjoint(a, b) == truth
@test isdisjoint(b, a) == truth
@test isdisjoint(a, reverse(b)) == truth
@test isdisjoint(reverse(a), b) == truth
@test isdisjoint(b, reverse(a)) == truth
@test isdisjoint(reverse(b), a) == truth
end
@test isdisjoint(10:9, 1:10) # empty range
@test !isdisjoint(1e-100:.1:1, 0:.1:1)
@test !isdisjoint(eps()/4:.1:.71, 0:.1:1)
end
@testset "unique" begin
u = @inferred(unique([1, 1, 2]))
@test in(1, u)
@test in(2, u)
@test length(u) == 2
@test unique(iseven, []) == []
# type promotion
@test unique(x -> x^2, [1, 3.]) == [1, 3.]
@test @inferred(unique(iseven, [5, 1, 8, 9, 3, 4, 10, 7, 2, 6])) == [5, 8]
@test @inferred(unique(x->x^2, Integer[3, -4, 5, 4])) == Integer[3, -4, 5]
@test @inferred(unique(iseven, Integer[3, -4, 5, 4]; seen=Set{Bool}())) == Integer[3, -4]
@test @inferred(unique(n -> n % 3, [5, 1, 8, 9, 3, 4, 10, 7, 2, 6])) == [5, 1, 9]
for r = (Base.OneTo(-1), Base.OneTo(0), Base.OneTo(1), Base.OneTo(5),
1:0, 1:1, 1:2, 1:10, 1:.5:.5, 1:.5:1, 1:.5:10, 3:-2:5, 3:-2:3, 3:-2:1,
StepRangeLen(1.0, 2.0, 0), StepRangeLen(1.0, 2.0, 2), StepRangeLen(1.0, 2.0, 3),
StepRangeLen(1.0, 0.0, 0), StepRangeLen(1.0, -0.0, 1), StepRangeLen(1.0, 0.0, 2),
LinRange(1, 2, 3), LinRange(1, 1, 0), LinRange(1, 1, 1), LinRange(1, 1, 10))
@test @inferred(unique(r)) == invoke(unique, Tuple{Any}, r)
end
end
@testset "issue 20105" begin
@test @inferred(unique(x for x in 1:1)) == [1]
@test unique(x for x in Any[1, 1.0])::Vector{Real} == [1]
@test unique(x for x in Real[1, 1.0])::Vector{Real} == [1]
@test @inferred(unique(Integer[1, 1, 2]))::Vector{Integer} == [1, 2]
@test unique(x for x in []) isa Vector{Any}
end
@testset "unique!" begin
u = []
@test unique!(u) === u
u = [1,1,3,2,1]
@inferred(unique!(u))
@test u == [1,3,2]
@test @inferred(unique!([])) == []
@test @inferred(unique!(Float64[])) == Float64[]
u = [1,2,2,3,5,5]
@test unique!(u) === u
@test u == [1,2,3,5]
u = [6,5,5,3,3,2,1]
@test unique!(u) === u
@test u == [6,5,3,2,1]
u = OffsetArray([1,2,2,3,5,5], -1)
@test unique!(u) === u
@test u == OffsetArray([1,2,3,5], -1)
u = OffsetArray([5,5,4,4,2,2,0,-1,-1], -1)
@test unique!(u) === u
@test u == OffsetArray([5,4,2,0,-1], -1)
u = OffsetArray(["w","we","w",5,"r",5,5], -1)
@test unique!(u) === u
@test u == OffsetArray(["w","we",5,"r"], -1)
u = [0.0,-0.0,1.0,2]
@test unique!(u) === u
@test u == [0.0,-0.0,1.0,2.0]
u = [1,NaN,NaN,3]
@test unique!(u) === u
@test u[1] == 1
@test isnan(u[2])
@test u[3] == 3
u = [5,"w","we","w","r",5,"w"]
unique!(u)
@test u == [5,"w","we","r"]
u = [1,2,5,1,3,2]
@test unique!(x -> x ^ 2, [1, -1, 3, -3, 5, -5]) == [1, 3, 5]
@test unique!(n -> n % 3, [5, 1, 8, 9, 3, 4, 10, 7, 2, 6]) == [5, 1, 9]
@test @inferred(unique!(iseven, [2, 3, 5, 7, 9])) == [2, 3]
@test @inferred(unique!(x -> x % 2 == 0 ? :even : :odd, [1, 2, 3, 4, 2, 2, 1])) == [1, 2]
@test @inferred(unique!(x -> x % 2 == 0 ? :even : "odd", [1, 2, 3, 4, 2, 2, 1]; seen=Set{Union{Symbol,String}}())) == [1, 2]
@test isempty(unique!(Union{}[]))
@test eltype(unique!([i for i in ["1"] if i isa Int])) <: Union{}
end
@testset "allunique" begin
@test allunique([])
@test allunique(Set())
@test allunique([1,2,3])
@test allunique([1 2; 3 4])
@test allunique([:a,:b,:c])
@test allunique(Set([1,2,3]))
@test !allunique([1,1,2])
@test !allunique([:a,:b,:c,:a])
@test allunique(unique(randn(100))) # longer than 32
@test allunique(collect(1:100)) # sorted/unique && longer than 32
@test allunique(collect(100:-1:1)) # sorted/unique && longer than 32
@test !allunique(fill(1,100)) # sorted/repeating && longer than 32
@test allunique(collect('A':'z')) # 58-element Vector{Char}
@test !allunique(repeat(1:99, 1, 2))
@test !allunique(vcat(pi, randn(1998), pi)) # longer than 1000
@test allunique(eachrow(hcat(1:10, 1:10)))
@test allunique(x for x in 'A':'Z' if randn()>0)
@test !allunique(x for x in repeat(1:2000, 3) if true)
@test allunique([0.0, -0.0])
@test allunique(x for x in [0.0, -0.0] if true)
@test !allunique([NaN, NaN])
@test !allunique(x for x in [NaN, NaN] if true)
# ranges
@test allunique(4:7)
@test allunique(1:1)
@test allunique(4.0:0.3:7.0)
@test allunique(4:-1:5) # empty range
@test allunique(7:-1:1) # negative step
@test allunique(Date(2018, 8, 7):Day(1):Date(2018, 8, 11)) # JuliaCon 2018
@test allunique(DateTime(2018, 8, 7):Hour(1):DateTime(2018, 8, 11))
@test allunique(('a':1:'c')[1:2]) == true
@test allunique(collect(1:1001))
for r = (Base.OneTo(-1), Base.OneTo(0), Base.OneTo(1), Base.OneTo(5),
1:0, 1:1, 1:2, 1:10, 1:.5:.5, 1:.5:1, 1:.5:10, 3:-2:5, 3:-2:3, 3:-2:1,
StepRangeLen(1.0, 2.0, 0), StepRangeLen(1.0, 2.0, 2), StepRangeLen(1.0, 2.0, 3),
StepRangeLen(1.0, 0.0, 0), StepRangeLen(1.0, -0.0, 1), StepRangeLen(1.0, 0.0, 2),
LinRange(1, 2, 3), LinRange(1, 1, 0), LinRange(1, 1, 1), LinRange(1, 1, 10))
@test allunique(r) == invoke(allunique, Tuple{Any}, r)
end
# tuples
@test allunique(())
@test allunique((1,2,3))
@test allunique(ntuple(identity, 40))
@test !allunique((1,2,3,4,3))
@test allunique((0.0, -0.0))
@test !allunique((NaN, NaN))
# Known length 1, need not evaluate:
@test allunique(error(x) for x in [1])
end
@testset "allunique(f, xs)" begin
@test allunique(sin, 1:3)
@test !allunique(sin, [1,2,3,1])
@test allunique(sin, (1, 2, pi, im)) # eltype Any
@test allunique(abs2, 1:100)
@test !allunique(abs, -10:10)
@test allunique(abs2, Vector{Any}(1:100))
# These cases don't call the function at all:
@test allunique(error, [])
@test allunique(error, [1])
end
@testset "allequal" begin
# sets & dictionaries
@test allequal(Set())
@test allequal(Set(1))
@test !allequal(Set([1, 2]))
@test allequal(Dict())
@test allequal(Dict(:a => 1))
@test !allequal(Dict(:a => 1, :b => 2))
# vectors
@test allequal([])
@test allequal([1])
@test allequal([1, 1])
@test !allequal([1, 1, 2])
@test allequal([:a, :a])
@test !allequal([:a, :b])
# ranges
@test !allequal(1:2)
@test allequal(1:1)
@test !allequal(4.0:0.3:7.0)
@test allequal(4:-1:5) # empty range
@test !allequal(7:-1:1) # negative step
@test !allequal(Date(2018, 8, 7):Day(1):Date(2018, 8, 11)) # JuliaCon 2018
@test !allequal(DateTime(2018, 8, 7):Hour(1):DateTime(2018, 8, 11))
@test allequal(StepRangeLen(1.0, 0.0, 2))
@test !allequal(StepRangeLen(1.0, 1.0, 2))
@test allequal(LinRange(1, 1, 0))
@test allequal(LinRange(1, 1, 1))
@test allequal(LinRange(1, 1, 2))
@test !allequal(LinRange(1, 2, 2))
# Known length 1, need not evaluate:
@test allequal(error(x) for x in [1])
# Empty, but !haslength:
@test allequal(error(x) for x in 1:3 if false)
end
@testset "allequal(f, xs)" begin
@test allequal(abs2, [3, -3])
@test allequal(x -> 1, rand(3))
@test !allequal(x -> rand(), [1,1,1])
# tuples
@test allequal(abs2, (3, -3))
@test allequal(x -> 1, Tuple(rand(3)))
@test !allequal(x -> rand(), (1,1,1))
# These cases don't call the function at all:
@test allequal(error, [])
@test allequal(error, ())
@test allequal(error, (x for x in 1:3 if false))
@test allequal(error, [1])
@test allequal(error, (1,))
end
@testset "filter(f, ::$S)" for S = (Set, BitSet)
s = S([1,2,3,4])
@test s !== filter( isodd, s) == S([1,3])
@test s === filter!(isodd, s) == S([1,3])
end
@testset "first" begin
@test_throws ArgumentError first(Set())
@test first(Set(2)) == 2
end
@testset "pop!" begin
s = Set(1:5)
@test 2 in s
@test pop!(s, 2) == 2
@test !(2 in s)
@test_throws KeyError pop!(s, 2)
@test pop!(s, 2, ()) == ()
@test 3 in s
@test pop!(s, 3, ()) == 3
@test !(3 in s)
@test pop!(Set(1:2), 2, nothing) == 2
end
@testset "convert" begin
iset = Set([17, 4711])
cfset = convert(Set{Float64}, iset)
@test typeof(cfset) == Set{Float64}
@test cfset == iset
fset = Set([17.0, 4711.0])
ciset = convert(Set{Int}, fset)
@test typeof(ciset) == Set{Int}
@test ciset == fset
ssset = Set(split("foo bar"))
cssset = convert(Set{String}, ssset)
@test typeof(cssset) == Set{String}
@test cssset == Set(["foo", "bar"])
end
@testset "fuzzy testing Set & BitSet" begin
b1, b2 = rand(-1000:1000, 2)
e1 = rand(b1-9:1000) # -9 to have an empty list sometimes
e2 = rand(b2-9:1000)
l1, l2 = rand(1:1000, 2)
a1 = b1 <= e1 ? rand(b1:e1, l1) : Int[]
a2 = b2 <= e2 ? rand(b2:e2, l2) : Int[]
s1, s2 = Set(a1), Set(a2)
t1, t2 = BitSet(a1), BitSet(a2)
for (s, t) = ((s1, t1), (s2, t2))
@test length(s) == length(t)
@test issubset(s, t)
@test issubset(t, s)
@test isempty(s) == isempty(t)
isempty(s) && continue
@test maximum(s) == maximum(t)
@test minimum(s) == minimum(t)
@test extrema(s) == extrema(t)
rs, rt = rand(s), rand(t)
@test rs in s
@test rt in s
@test rs in t
@test rt in t
for y in (rs, rt)
ss = copy(s)
tt = copy(t)
pop!(ss, y)
pop!(tt, y)
@test BitSet(ss) == tt
@test Set(tt) == ss
z = rand(1001:1100) # z ∉ s or t
push!(ss, z)
push!(tt, z)
@test BitSet(ss) == tt
@test Set(tt) == ss
end
end
res = Dict{String,Union{Bool,Vector{Int}}}()
function check(desc, val)
n = val isa Bool ? val : sort!(collect(val))
r = get!(res, desc, n)
if n isa Bool || r !== n
@test r == n
end
end
asbitset(x) = x isa BitSet ? x : BitSet(x)
asset(x) = x isa Set ? x : Set(x)
for x1 = (s1, t1), x2 = (s2, t2)
check("union", union(x1, x2))
check("intersect", intersect(x1, x2))
check("symdiff", symdiff(x1, x2))
check("setdiff", setdiff(x1, x2))
check("== as Bitset", asbitset(x1) == asbitset(x2))
check("== as Set", asset(x1) == asset(x2))
check("issubset", issubset(x1, x2))
if typeof(x1) == typeof(x2)
check("<", x1 < x2)
check("<=", x1 > x2)
check("union!", union!(copy(x1), x2))
check("setdiff!", setdiff!(copy(x1), x2))
x1 isa Set && continue
check("intersect!", intersect!(copy(x1), x2))
check("symdiff!", symdiff!(copy(x1), x2))
end
end
end
@testset "replace! & replace" begin
a = [1, 2, 3, 1]
@test replace(x -> iseven(x) ? 2x : x, a) == [1, 4, 3, 1]
@test replace(x -> iseven(x) ? 2x : x, Tuple(a)) === (1, 4, 3, 1)
@test replace!(x -> iseven(x) ? 2x : x, a) === a
@test a == [1, 4, 3, 1]
@test replace(a, 1=>0) == [0, 4, 3, 0]
@test replace(Tuple(a), 1=>0) === (0, 4, 3, 0)
for count = (1, 0x1, big(1))
@test replace(a, 1=>0, count=count) == [0, 4, 3, 1]
@test replace(Tuple(a), 1=>0, count=count) === (0, 4, 3, 1)
end
@test replace!(a, 1=>2) === a
@test a == [2, 4, 3, 2]
@test replace!(x->2x, a, count=0x2) == [4, 8, 3, 2]
d = Dict(1=>2, 3=>4)
@test replace!(x -> x.first > 2 ? x.first=>2*x.second : x, d) === d
@test d == Dict(1=>2, 3=>8)
@test replace(d, (3=>8)=>(0=>0)) == Dict(1=>2, 0=>0)
@test replace!(d, (3=>8)=>(2=>2)) === d
@test d == Dict(1=>2, 2=>2)
s = Set([1, 2, 3])
@test replace(x -> x > 1 ? 2x : x, s) == Set([1, 4, 6])
for count = (1, 0x1, big(1))
@test replace(x -> x > 1 ? 2x : x, s, count=count) in [Set([1, 4, 3]), Set([1, 2, 6])]
end
@test replace(s, 1=>4) == Set([2, 3, 4])
@test replace!(s, 1=>2) === s
@test s == Set([2, 3])
@test replace!(x->2x, s, count=0x1) in [Set([4, 3]), Set([2, 6])]
for count = (0, 0x0, big(0)) # count == 0 --> no replacements
@test replace([1, 2], 1=>0, 2=>0; count) == [1, 2]
@test replace((1, 2), 1=>0, 2=>0; count) === (1, 2)
for dict = (Dict(1=>2, 2=>3), IdDict(1=>2, 2=>3))
@test replace(dict, (1=>2) => (1=>3); count) == dict
end
@test replace(Set([1, 2]), 2=>-1; count) == Set([1, 2])
end
# test collisions with AbstractSet/AbstractDict
@test replace!(x->2x, Set([3, 6])) == Set([6, 12])
@test replace!(x->2x, Set([1:20;])) == Set([2:2:40;])
@test replace!(kv -> (2kv[1] => kv[2]), Dict(1=>2, 2=>4, 4=>8, 8=>16)) == Dict(2=>2, 4=>4, 8=>8, 16=>16)
# avoid recursive call issue #25384
@test_throws MethodError replace!("")
# test eltype promotion
x = @inferred replace([1, 2], 2=>2.5)
@test x == [1, 2.5] && x isa Vector{Float64}
x = @inferred replace([1, 2], 2=>missing)
@test isequal(x, [1, missing]) && x isa Vector{Union{Int, Missing}}
x = @inferred replace([1, missing], missing=>2)
@test x == [1, 2] && x isa Vector{Int}
x = @inferred replace([1, missing], missing=>2, count=1)
@test x == [1, 2] && x isa Vector{Union{Int, Missing}}
x = @inferred replace([1, missing], missing=>missing)
@test isequal(x, [1, missing]) && x isa Vector{Union{Int, Missing}}
x = @inferred replace([1, missing], missing=>2, 1=>missing)
@test isequal(x, [missing, 2]) && x isa Vector{Union{Int, Missing}}
# eltype promotion for dicts
d = Dict(1=>2, 3=>4)
f = replace(d, (1=>2) => (1=>nothing))
@test f == Dict(3=>4, 1=>nothing)
@test eltype(f) == Pair{Int, Union{Nothing, Int}}
f = replace(d, (1=>2) => (1=>missing), (3=>4)=>(3=>missing))
@test valtype(f) == Union{Missing,Int}
f = replace(d, (1=>2) => (1=>'a'), (3=>4)=>(3=>'b'))
@test valtype(f) == Any
@test f == Dict(3=>'b', 1=>'a')
# eltype promotion for sets
s = Set([1, 2, 3])
f = replace(s, 2=>missing, 3=>nothing)
@test f == Set([1, missing, nothing])
@test eltype(f) == Union{Int,Missing,Nothing}
f = replace(s, 2=>'a')
@test eltype(f) == Any
@test f == Set([1, 3, 'a'])
# test that isequal is used
@test replace([NaN, 1.0], NaN=>0.0) == [0.0, 1.0]
@test replace((NaN, 1.0), NaN=>0.0) === (0.0, 1.0)
@test replace([1, missing], missing=>0) == [1, 0]
@test replace((1, missing), missing=>0) === (1, 0)
# test that MethodError is thrown for pairs
@test_throws MethodError replace(identity, 1=>2)
@test_throws MethodError replace(identity, 1=>2, 3=>4)
@test_throws MethodError replace!(identity, 1=>2)
@test_throws MethodError replace!(identity, 1=>2, 3=>4)
# test replace and friends for AbstractDicts
d1 = GenericDict(Dict(1=>2, 3=>4))
d2 = replace(d1, (1=>2) => (1=>"a"))
@test d2 == Dict(1=>"a", 3=>4)
@test d2 isa Dict{Int, Any}
@test d1 === replace!(d1, (1=>2) => (1=>-2))
@test d1 == Dict(1=>-2, 3=>4)
dd = Dict(1=>2, 3=>1, 5=>1, 7=>1)
for d1 in (dd, GenericDict(dd))
@test replace(d1, (1=>2) => (1=>"a"), count=0) == d1
d2 = replace(kv->(kv[2] == 1 ? kv[1]=>2 : kv), d1, count=2)
@test count(==(2), values(d2)) == 3
@test count(==(1), values(d2)) == 1
end
end
@testset "⊆, ⊊, ⊈, ⊇, ⊋, ⊉, <, <=, issetequal" begin
a = [2, 1, 2]
b = [2, 3, 1, 3]
ua = unique(a)
ub = unique(b)
for TA in (Tuple, identity, Set, BitSet, IdSet{Int}),
TB in (Tuple, identity, Set, BitSet, IdSet{Int}),
uA = false:true,
uB = false:true
A = TA(uA ? ua : a)
B = TB(uB ? ub : b)
@test A ⊆ B
@test A ⊊ B
@test !(A ⊈ B)
@test !(A ⊇ B)
@test !(A ⊋ B)
@test A ⊉ B
@test !(B ⊆ A)
@test !(B ⊊ A)
@test B ⊈ A
@test B ⊇ A
@test B ⊋ A
@test !(B ⊉ A)
@test !issetequal(A, B)
@test !issetequal(B, A)
@test !issetequal(B)(A)
@test !issetequal(A)(B)
for T = (Tuple, identity, Set, BitSet, IdSet{Int})
@test issetequal(A, T(A))
@test issetequal(B, T(B))
end
if A isa AbstractSet && B isa AbstractSet
@test A <= B
@test A < B
@test !(A >= B)
@test !(A > B)
@test !(B <= A)
@test !(B < A)
@test B >= A
@test B > A
end
end
# first doesn't have length
@test issetequal(Iterators.filter(iseven, 1:10), [2, 4, 6, 8, 10])
# both don't have length
@test issetequal(Iterators.filter(iseven, 1:10), Iterators.filter(iseven, 1:10))
end
@testset "optimized union! with max_values" begin
# issue #30315
T = Union{Nothing, Bool}
@test Base.max_values(T) == 3
d = Set{T}()
union!(d, (nothing, true, false))
@test length(d) == 3
@test d == Set((nothing, true, false))
@test nothing in d
@test true in d
@test false in d
for X = (Int8, Int16, Int32, Int64)
@test Base.max_values(Union{Nothing, X}) == (sizeof(X) < sizeof(Int) ?
2^(8*sizeof(X)) + 1 :
typemax(Int))
end
# this does not account for non-empty intersections of the unioned types
@test Base.max_values(Union{Int8,Int16}) == 2^8 + 2^16
end
struct OpenInterval{T}
lower::T
upper::T
end
Base.in(x, i::OpenInterval) = i.lower < x < i.upper
Base.IteratorSize(::Type{<:OpenInterval}) = Base.SizeUnknown()
@testset "Continuous sets" begin
i = OpenInterval(2, 4)
@test 3 ∈ i
@test issubset(3, i)
end
@testset "IdSet" begin
a = [1]
b = [2]
c = [3]
d = [4]
e = [5]
A = IdSet{Vector{Int}}([a, b, c, d])
@test !isempty(A)
B = copy(A)
@test A ⊆ B
@test B ⊆ A
A = filter!(x->isodd(x[1]), A)
@test A ⊆ B
@test !(B ⊆ A)
@test !isempty(A)
a_ = pop!(A, a)
@test a_ === a
@test !isempty(A)
e_ = pop!(A, a, e)
@test e_ === e
@test !isempty(A)
A = empty!(A)
@test isempty(A)
end
@testset "⊊, ⊋" begin
@test !((1, 2) ⊊ (1, 2, 2))
@test !((1, 2, 2) ⊋ (1, 2))
end
@testset "AbstractSet & Fallback" begin
mutable struct TestSet{T} <: AbstractSet{T}
set::Set{T}
function TestSet{T}() where T
new{T}(Set{T}())
end
end
set = TestSet{Any}()
@test sizehint!(set, 1) === set
@test sizehint!(set, 1; shrink = true) === set
@test sizehint!(set, 1; shrink = false) === set
end