Revision b9cb073637ed17f7c31244c6e6d4a4c7fdc4c916 authored by Kristoffer Carlsson on 17 January 2018, 03:54:14 UTC, committed by Jeff Bezanson on 17 January 2018, 03:54:14 UTC
1 parent cb23538
sets.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
# Set tests
isdefined(Main, :TestHelpers) || @eval Main include("TestHelpers.jl")
using Main.TestHelpers.OAs
@testset "Construction, collect" begin
@test ===(typeof(Set([1,2,3])), Set{Int})
@test ===(typeof(Set{Int}([3])), Set{Int})
data_in = (1,"banana", ())
s = Set(data_in)
data_out = collect(s)
@test ===(typeof(data_out), Array{Any,1})
@test all(map(occursin(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(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})
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 "isequal" begin
@test isequal(Set(), Set())
@test !isequal(Set(), Set([1]))
@test isequal(Set{Any}(Any[1,2]), Set{Int}([1,2]))
@test !isequal(Set{Any}(Any[1,2]), Set{Int}([1,2,3]))
# Comparison of unrelated types seems rather inconsistent
@test isequal(Set{Int}(), Set{AbstractString}())
@test !isequal(Set{Int}(), Set{AbstractString}([""]))
@test !isequal(Set{AbstractString}(), Set{Int}([0]))
@test !isequal(Set{Int}([1]), Set{AbstractString}())
@test isequal(Set{Any}([1,2,3]), Set{Int}([1,2,3]))
@test isequal(Set{Int}([1,2,3]), Set{Any}([1,2,3]))
@test !isequal(Set{Any}([1,2,3]), Set{Int}([1,2,3,4]))
@test !isequal(Set{Int}([1,2,3]), Set{Any}([1,2,3,4]))
@test !isequal(Set{Any}([1,2,3,4]), Set{Int}([1,2,3]))
@test !isequal(Set{Int}([1,2,3,4]), Set{Any}([1,2,3]))
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 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
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 "sizehint, empty" begin
s = Set([1])
@test isequal(sizehint!(s, 10), Set([1]))
@test isequal(empty!(s), Set())
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]
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]))
@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 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]
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]))
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" 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([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))
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]))
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 must NOT uniquify
@test symdiff([1, 2, 1]) == symdiff!([1, 2, 1]) == [2]
@test symdiff([1, 2, 1], [2, 2]) == symdiff!([1, 2, 1], [2, 2]) == [2]
end
@testset "unique" begin
u = unique([1, 1, 2])
@test in(1, u)
@test in(2, u)
@test length(u) == 2
@test unique(iseven, [5, 1, 8, 9, 3, 4, 10, 7, 2, 6]) == [5, 8]
@test unique(n -> n % 3, [5, 1, 8, 9, 3, 4, 10, 7, 2, 6]) == [5, 1, 9]
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 unique(Integer[1, 1, 2])::Vector{Integer} == [1, 2]
end
@testset "unique!" begin
u = [1,1,3,2,1]
unique!(u)
@test u == [1,3,2]
@test unique!([]) == []
@test 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]
end
@testset "allunique" begin
@test allunique([])
@test allunique(Set())
@test allunique([1,2,3])
@test allunique([:a,:b,:c])
@test allunique(Set([1,2,3]))
@test !allunique([1,1,2])
@test !allunique([:a,:b,:c,:a])
@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
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
maybe1(v, p) = if p Some(v) end
maybe2(v, p) = if p v end
for maybe = (maybe1, maybe2)
a = [1, 2, 3, 1]
@test replace(x->maybe(2x, iseven(x)), a) == [1, 4, 3, 1]
@test replace!(x->maybe(2x, iseven(x)), a) === a
@test a == [1, 4, 3, 1]
@test replace(a, 1=>0) == [0, 4, 3, 0]
for count = (1, 0x1, big(1))
@test replace(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, d, 0=>0) == Dict(1=>2, 0=>0)
@test replace!(x->maybe(x.first=>2*x.second, x.first > 2), 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)
for count = (1, 0x1, big(1))
@test replace(x->x.second == 2, d, 0=>0, count=count) in [Dict(1=>2, 0=>0),
Dict(2=>2, 0=>0)]
end
s = Set([1, 2, 3])
@test replace(x->maybe(2x, x>1), s) == Set([1, 4, 6])
for count = (1, 0x1, big(1))
@test replace(x->maybe(2x, x>1), 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))
@test replace([1, 2], 1=>0, 2=>0, count=count) == [1, 2] # count=0 --> no replacements
end
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)
# test Some(nothing)
a = [1, 2, nothing, 4]
@test replace(x -> x === nothing ? 0 : Some(nothing), a) == [nothing, nothing, 0, nothing]
@test replace(x -> x === nothing ? 0 : nothing, a) == [1, 2, 0, 4]
@test replace!(x -> x !== nothing ? Some(nothing) : nothing, a) == [nothing, nothing, nothing, nothing]
@test replace(iseven, Any[1, 2, 3, 4], nothing) == [1, nothing, 3, nothing]
@test replace(Any[1, 2, 3, 4], 1=>nothing, 3=>nothing) == [nothing, 2, nothing, 4]
s = Set([1, 2, nothing, 4])
@test replace(x -> x === nothing ? 0 : Some(nothing), s) == Set([0, nothing])
@test replace(x -> x === nothing ? 0 : nothing, s) == Set([1, 2, 0, 4])
@test replace(x -> x !== nothing ? Some(nothing) : nothing, s) == Set([nothing])
@test replace(iseven, Set(Any[1, 2, 3, 4]), nothing) == Set([1, nothing, 3, nothing])
@test replace(Set(Any[1, 2, 3, 4]), 1=>nothing, 3=>nothing) == Set([nothing, 2, nothing, 4])
# avoid recursive call issue #25384
@test_throws MethodError replace!("")
end
@testset "⊆, ⊊, ⊈, ⊇, ⊋, ⊉, <, <=, issetequal" begin
a = [1, 2]
b = [2, 1, 3]
for C = (Tuple, identity, Set, BitSet)
A = C(a)
B = C(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)
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
for D = (Tuple, identity, Set, BitSet)
@test issetequal(A, D(A))
@test !issetequal(A, D(B))
end
end
end
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...