bitset.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

# Test functionality of BitSet

using Random

@testset "Construction, collect" begin
    data_in = (1,5,100)
    s = BitSet(data_in)
    data_out = collect(s)
    @test all(map(in(data_out), data_in))
    @test length(data_out) === length(data_in)
end

@testset "eltype, empty" begin
    @test eltype(BitSet()) === Int
    @test eltype(BitSet) === Int
    @test isequal(empty(BitSet([1,2,3])), BitSet())
end

@testset "show" begin
    @test sprint(show, BitSet()) == "BitSet([])"
    @test sprint(show, BitSet([1,2,3])) == "BitSet([1, 2, 3])"
    show(IOBuffer(), BitSet())
end

@testset "in, hashing" begin
    s = BitSet([1,2,10,20,200,300,1000,10000,10002])
    @test last(s) === 10002
    @test first(s) === 1
    @test length(s) === 9
    @test pop!(s) === 10002
    @test_throws KeyError pop!(s, -1)
    @test length(s) === 8
    @test popfirst!(s) === 1
    @test length(s) === 7
    @test !in(0,s)
    @test !in(1,s)
    @test in(2,s)
    @test !in(10002,s)
    @test in(UInt128(10000),s)
    @test in(Int32(10000),s)
    @test in(10000.0,s)
    @test !in(10002.0,s)
    @test !in(typemax(UInt), s)
    @test !in(typemin(Int)-Int128(14), s)
    @test_throws ArgumentError first(BitSet())
    @test_throws ArgumentError last(BitSet())
    t = copy(s)
    sizehint!(t, 20000) #check that hash does not depend on size of internal storage
    @test hash(s) === hash(t)
    push!(t, 20000)
    @test 20000 in t
    sizehint!(t, 200) # ensure that sizehint!'ing a small amount isn't destructive
    @test 20000 in t
    @test pop!(t, 20000) === 20000
    @test hash(s) === hash(t)
    # Ensure empty chunks don't affect hash
    @test hash(BitSet([1])) != hash(BitSet([17]))
    @test hash(BitSet([1])) != hash(BitSet([33]))
    @test hash(BitSet([1])) != hash(BitSet([65]))
    @test hash(BitSet([1])) != hash(BitSet([129]))
    # test with a different internal structure
    s = BitSet([129])
    pop!(push!(s, 65), 65)
    @test hash(BitSet([1])) != hash(s)

    @test !(-1 in BitSet(1:10))
end

@testset "issue #8570" begin
    let s
        @test 400 > @allocated s = BitSet(typemax(Int32))
        @test length(s) === 1
        @test only(s) == typemax(Int32)
    end
end

@testset "union!, symdiff!" begin
    i = BitSet([1, 2, 3])
    union!(i, [1, 2])
    @test length(i) === 3
    union!(i, [3, 4, 5])
    @test length(i) === 5

    @test_throws KeyError pop!(i, 10)

    empty!(i)
    @test length(i) === 0

    @test symdiff!(i, -3) == BitSet([-3])
    @test symdiff!(i, -3) == BitSet([])

    @test symdiff!(i, 3) == BitSet([3])
    @test symdiff!(i, 257) == BitSet([3, 257])
    @test symdiff!(i, [3, 6]) == BitSet([6, 257])

    i = BitSet(1:6)
    @test symdiff!(i, BitSet([6, 513])) == BitSet([1:5; 513])

    @test 0 ∈ symdiff!(BitSet(rand(1:100, 30)), 0)
    @test BitSet(0:2:4) ⊆ symdiff!(BitSet(rand(5:100, 30)), [0, 2, 4])

    # issue #23557 :
    @test_throws MethodError symdiff!(BitSet([1]), ['a']) # should no stack-overflow
    @test_throws MethodError symdiff!(BitSet([1, 2]),  [[1]]) # should not return BitSet([2])
end

@testset "copy, copy!, empty" begin
    s1 = BitSet([1,2,3])
    s2 = empty(s1)
    copy!(s2, s1)
    s3 = copy(s2)
    @test s3 == s2 == s1
    @test collect(s3) == collect(s2) == [1,2,3]
end

@testset "push!, union" begin
    i = BitSet([1, 2, 3])
    j = union(i)
    @test j == i
    @test !(j === i)

    j = BitSet([4, 5, 6])
    @test union(i, j) == BitSet(1:6)

    k = BitSet([7, 8, 9])
    @test union(i, j, k) == BitSet(1:9)
    i = BitSet([1, 2, 3])
    j = union(i)
    @test j == i
    @test !(j === i)

    j = BitSet([4, 5, 6])
    @test union(i, j) == BitSet(1:6)

    k = BitSet([7, 8, 9])
    @test union(i, j, k) == BitSet(1:9)

    s1 = BitSet()
    @test push!(s1, -1) == BitSet([-1])
    push!(s1, -10, 1, 10, 100, 1000)
    @test collect(s1) == [-10, -1, 1, 10, 100, 1000]
    push!(s1, 606)
    @test collect(s1) == [-10, -1, 1, 10, 100, 606, 1000]

    s2 = BitSet()
    @test s2 === union!(s2, s1)
    s3 = BitSet([-1, 1, 10, 100])
    union!(s3, [-10, 1, 606, 1000])
    s4 = union(BitSet([-1, 1, 100, 1000]), BitSet([-10, 10, 100, 606]))
    @test s1 == s2 == s3 == s4
end

@testset "pop!, delete!" begin
    s = BitSet(1:2:10)
    # deleting non-positive values should be no-op
    # (Issue #23179 : delete!(s, 0) should not crash)
    len = length(s)
    for n in -20:0
        @test length(delete!(s, n)) == len
    end
    @test length(delete!(s, typemax(UInt))) == len
    @test pop!(s, 1) === 1
    @test !(1 in s)
    @test_throws KeyError pop!(s, 1)
    @test_throws KeyError pop!(s, -1)
    @test pop!(s, -1, 1) === 1
    @test pop!(s, 1, 0) === 0
    @test 5 in s
    @test s === delete!(s, 1) === delete!(s, Int8(5))
    @test !(5 in s)
    for i in s; pop!(s, i); end
    @test isempty(s)
    push!(s, 100)
    @test pop!(s, 100) == 100
    push!(s, 1:2:10...)
    @test pop!(s) === 9
    @test pop!(s) === 7
    @test popfirst!(s) === 1
    @test popfirst!(s) === 3
    @test collect(s) == [5]
    empty!(s)
    @test isempty(s)
end

@testset "intersect" begin
    i = BitSet([1, 2, 3])
    j = BitSet([4, 5, 6])

    @test intersect(i) == i
    @test !(intersect(i) === i)
    @test intersect(i, j) == BitSet([])
    push!(j, 257)
    @test intersect(i, j) == BitSet([])
    push!(j, 2, 3, 17)
    @test intersect(i, j) == BitSet([2, 3])
    k = BitSet([1, 2, 3, 4, 5, 6, 7])
    @test intersect(i, j, k) == BitSet([2, 3])

    @test isempty(intersect(BitSet()))
    @test isempty(intersect(BitSet(1:10), BitSet()))
    @test isempty(intersect(BitSet(), BitSet(1:10)))

    @test intersect(BitSet([1,2,3])) == BitSet([1,2,3])
    @test intersect(BitSet(1:7), BitSet(3:10)) ==
          intersect(BitSet(3:10), BitSet(1:7)) == BitSet(3:7)
    @test intersect(BitSet(1:10), BitSet(1:4), 1:5, [2,3,10]) == BitSet([2,3])
end

@testset "setdiff, symdiff" begin
    @test setdiff(BitSet([1, 2, 3, 4]), BitSet([2, 4, 5, 6])) == BitSet([1, 3])
    @test symdiff(BitSet([1, 2, 3, 4]), BitSet([2, 4, 5, 6])) == BitSet([1, 3, 5, 6])

    s2 = BitSet([1, 2, 3, 4])
    setdiff!(s2, BitSet([2, 4, 5, 6]))
    @test s2 == BitSet([1, 3])

    s1 = BitSet(1:100)
    setdiff!(s1, BitSet(1:2:100))
    s2 = setdiff(BitSet(1:100), BitSet(1:2:100))
    @test s1 == s2 == BitSet(2:2:100)
    @test collect(s1) == collect(2:2:100)

    # issue #23191 : these tests should not segfault
    @test setdiff(s1, 0) == s1
    @test setdiff(s1, -9:0) == s1

    @test symdiff(BitSet([1, 2, 3, 4]), BitSet([2, 4, 5, 6])) ==
          symdiff(BitSet([2, 4, 5, 6]), BitSet([1, 2, 3, 4])) ==
          symdiff(BitSet([1, 2, 3, 4]), [2, 4, 5, 6]) ==
          symdiff(BitSet([2, 4, 5, 6]), [1, 2, 3, 4]) == BitSet([1, 3, 5, 6])
end

@testset "subsets, equality" begin
    i = BitSet([1, 2, 3])
    k = BitSet([4, 5])
    copy!(k, i)
    @test k == i
    @test !(k === i)
    copy!(k, k)
    @test k == i

    i = BitSet([1, 2, 3])
    j = BitSet([1, 2, 4])
    @test i != j

    push!(j, 257)
    pop!(j, 257)
    @test i != j
    @test j != i

    @test issubset(BitSet([1, 2, 4]), BitSet(1:10))
    @test issubset(BitSet([]), BitSet([]))
    @test issubset(BitSet([0]), BitSet([-1,0]))
    @test !issubset(BitSet([-1]), BitSet([]))
    @test !issubset(BitSet([65]), BitSet([]))
    @test BitSet([1, 2, 4]) < BitSet(1:10)
    @test !(BitSet([]) < BitSet([]))
    @test BitSet([1, 2, 4]) <= BitSet(1:10)
    @test BitSet([1, 2, 4]) <= BitSet([1, 2, 4])
    @test BitSet([]) <= BitSet([])

    @test BitSet(2:2:10) < BitSet(1:10)
    @test !(BitSet(2:2:10) < BitSet(2:2:10))
    @test BitSet(2:2:10) <= BitSet(2:10)
    @test BitSet(2:2:10) <= BitSet(2:2:10)

    # == with last-bit set (groups.google.com/forum/#!topic/julia-users/vZNjiIEG_sY)
    s = BitSet(255)
    @test s == s
end

@testset "setlike" begin
    p = BitSet([1,2,5,6])
    q = BitSet([1,3,5,7])
    a = Set(p)
    b = Set(q)
    for f in (union, intersect, setdiff, symdiff)
        @test collect(f(p, p)) == sort(collect(f(a, a)))
        @test collect(f(q, q)) == sort(collect(f(b, b)))
        @test collect(f(p, q)) == sort(collect(f(a, b)))
        @test collect(f(q, p)) == sort(collect(f(b, a)))
    end
end

@testset "misc" begin
    s = BitSet()
    push!(s, 1, 2, 100)
    @test !(0 in s)
    @test 1 in s
    @test 2 in s
    @test !(3 in s)
    @test 100 in s
    @test !(101 in s)
    @test !(1000 in s)
    @test first(s) === 1
    @test last(s) === 100
    @test s == BitSet([1, 2, 100])
    push!(s, 1000)
    @test [i for i in s] == [1, 2, 100, 1000]
    @test pop!(s) === 1000
    @test s == BitSet([1, 2, 100])
    @test hash(s) === hash(BitSet([1, 2, 100]))

    b = 1:1000
    s = BitSet(b)
    @test collect(s) == collect(b)
    @test length(s) === length(b)
    @test pop!(s, 100) === 100
    @test collect(s) == [1:99; 101:1000]
    @test_throws KeyError pop!(s, 100)
    @test_throws KeyError pop!(s, 0)
    @test pop!(s, 100, 0) === 0
    @test pop!(s, 99, 0) === 99
end

@testset "unsigned overflow" begin
    @test BitSet(UInt8(2^8-1)) == BitSet(2^8-1)
    @test [x for x in BitSet(UInt8(2^8-1))] == [UInt8(2^8-1)]
    @test BitSet(UInt16(2^16-1)) == BitSet(2^16-1)
    @test [x for x in BitSet(UInt16(2^16-1))] == [UInt16(2^16-1)]
end

@testset "order" begin
    a = rand(1:1000, 100)
    s = BitSet(a)
    m, M = extrema(s)
    @test m == first(s) == minimum(s) == minimum(a)
    @test M == last(s)  == maximum(s) == maximum(a)
    @test issorted(s)
end

@testset "extreme values" begin
    @test pop!(BitSet(typemin(Int))) == typemin(Int)
    @test pop!(BitSet(typemax(Int))) == typemax(Int)
end

@testset "sizehint! returns a BitSet" begin
    # see #25029
    @test sizehint!(BitSet(), 100) isa BitSet
    # TODO: test that we don't delegate sizehint! to the underlying bits
    # field without dividing by 64 (i.e. the 100 above should allocate
    # only 2 UInt64 words
end

@testset "union!(::BitSet, ::AbstractUnitRange) optimization" begin
    # check that using a:b or a:1:b gives equal results
    a, b = minmax(rand(-1000:1000, 2)...)
    x, y = BitSet(a:b), BitSet(a:1:b)
    @test x == y
    a, b = minmax(rand(-1000:1000, 2)...)
    @test union!(x, BitSet(a:b)) == union!(y, BitSet(a:1:b))
    x = BitSet(rand(-1000:1000, 500))
    y = copy(x)
    @test union!(x, BitSet(a:b)) == union!(y, BitSet(a:1:b))
    @test_throws InexactError BitSet(Int128(typemin(Int))-1:typemin(Int))
    @test_throws InexactError BitSet(typemax(Int):Int128(typemax(Int))+1)
    # union! with an empty range doesn't modify the BitSet
    @test union!(x, b:a) == y
end

@testset "union!(::BitSet, ::AbstractUnitRange) when two ranges do not overlap" begin
    # see #45574
    a, b = rand(-10000:-5000), rand(5000:10000)
    c, d = minmax(rand(20000:30000, 2)...)
    @test length(union!(BitSet(a:b), c:d)) == length(a:b) + length(c:d)
    c, d = minmax(rand(-30000:-20000, 2)...)
    @test length(union!(BitSet(a:b), c:d)) == length(a:b) + length(c:d)
end