#38182

Committed 15 Aug 2025 03:55AM UTC coverage: 77.87% (-0.4%) from 78.28%

Build # #38182

Build Type

push

local

Committed by

web-flow

Commit Message

🤖 [master] Bump the SparseArrays stdlib from 30201ab to bb5ecc0 (#59263)

Stdlib: SparseArrays
URL: https://github.com/JuliaSparse/SparseArrays.jl.git
Stdlib branch: main
Julia branch: master
Old commit: 30201ab
New commit: bb5ecc0
Julia version: 1.13.0-DEV
SparseArrays version: 1.13.0
Bump invoked by: @ViralBShah
Powered by:
[BumpStdlibs.jl](https://github.com/JuliaLang/BumpStdlibs.jl)

Diff:
https://github.com/JuliaSparse/SparseArrays.jl/compare/30201abcb...bb5ecc091

```
$ git log --oneline 30201ab..bb5ecc0
bb5ecc0 fast quadratic form for dense matrix, sparse vectors (#640)
34ece87 Extend 3-arg `dot` to generic `HermOrSym` sparse matrices (#643)
095b685 Exclude unintended complex symmetric sparse matrices from 3-arg `dot` (#642)
8049287 Fix signature for 2-arg matrix-matrix `dot` (#641)
cff971d Make cond(::SparseMatrix, 1 / Inf) discoverable from 2-norm error (#629)
```

Co-authored-by: ViralBShah <744411+ViralBShah@users.noreply.github.com>

Run Details

48274 of 61993 relevant lines covered (77.87%)

9571166.83 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

64.14

/base/abstractset.jl

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

eltype(::Type{<:AbstractSet{T}}) where {T} = @isdefined(T) ? T : Any
sizehint!(s::AbstractSet, n) = s

function copy!(dst::AbstractSet, src::AbstractSet)
    dst === src && return dst
    union!(empty!(dst), src)
end

## set operations (union, intersection, symmetric difference)

"""
    union(s, itrs...)
    ∪(s, itrs...)

Construct an object containing all distinct elements from all of the arguments.

The first argument controls what kind of container is returned.
If this is an array, it maintains the order in which elements first appear.

Unicode `∪` can be typed by writing `\\cup` then pressing tab in the Julia REPL, and in many editors.
This is an infix operator, allowing `s ∪ itr`.

See also [`unique`](@ref), [`intersect`](@ref), [`isdisjoint`](@ref), [`vcat`](@ref), [`Iterators.flatten`](@ref).

# Examples
```jldoctest; filter = r"^\\s+\\d\$"m
julia> union([1, 2], [3])
3-element Vector{Int64}:
 1
 2
 3

julia> union([4 2 3 4 4], 1:3, 3.0)
4-element Vector{Float64}:
 4.0
 2.0
 3.0
 1.0

julia> (0, 0.0) ∪ (-0.0, NaN)
3-element Vector{Real}:
   0
  -0.0
 NaN

julia> union(Set([1, 2]), 2:3)
Set{Int64} with 3 elements:
  2
  3
  1
```
"""
function union end

union(s, sets...) = union!(emptymutable(s, promote_eltype(s, sets...)), s, sets...)
union(s::AbstractSet) = copy(s)

const ∪ = union

"""
    union!(s::Union{AbstractSet,AbstractVector}, itrs...)

Construct the [`union`](@ref) of passed in sets and overwrite `s` with the result.
Maintain order with arrays.

$(_DOCS_ALIASING_WARNING)

# Examples
```jldoctest; filter = r"^\\s+\\d\$"m
julia> a = Set([3, 4, 5]);

julia> union!(a, 1:2:7);

julia> a
Set{Int64} with 5 elements:
  5
  4
  7
  3
  1
```
"""
function union!(s::AbstractSet, sets...)
    for x in sets
        union!(s, x)
    end
    return s
end

max_values(::Type) = typemax(Int)
max_values(T::Union{map(X -> Type{X}, BitIntegerSmall_types)...}) = 1 << (8*sizeof(T))
# saturated addition to prevent overflow with typemax(Int)
function max_values(T::Union)
    a = max_values(T.a)::Int
    b = max_values(T.b)::Int
    return max(a, b, a + b)
end
max_values(::Type{Bool}) = 2
max_values(::Type{Nothing}) = 1

function union!(s::AbstractSet{T}, itr) where T
    haslength(itr) && sizehint!(s, length(s) + Int(length(itr))::Int; shrink = false)
    for x in itr
        push!(s, x)
        length(s) == max_values(T) && break
    end
    return s
end

"""
    intersect(s, itrs...)
    ∩(s, itrs...)

Construct the set containing those elements which appear in all of the arguments.

The first argument controls what kind of container is returned.
If this is an array, it maintains the order in which elements first appear.

Unicode `∩` can be typed by writing `\\cap` then pressing tab in the Julia REPL, and in many editors.
This is an infix operator, allowing `s ∩ itr`.

See also [`setdiff`](@ref), [`isdisjoint`](@ref), [`issubset`](@ref Base.issubset), [`issetequal`](@ref).

!!! compat "Julia 1.8"
    As of Julia 1.8 intersect returns a result with the eltype of the
    type-promoted eltypes of the two inputs

# Examples
```jldoctest
julia> intersect([1, 2, 3], [3, 4, 5])
1-element Vector{Int64}:
 3

julia> intersect([1, 4, 4, 5, 6], [6, 4, 6, 7, 8])
2-element Vector{Int64}:
 4
 6

julia> intersect(1:16, 7:99)
7:16

julia> (0, 0.0) ∩ (-0.0, 0)
1-element Vector{Real}:
 0

julia> intersect(Set([1, 2]), BitSet([2, 3]), 1.0:10.0)
Set{Float64} with 1 element:
  2.0
```
"""
function intersect(s::AbstractSet, itr, itrs...)
    # heuristics to try to `intersect` with the shortest Set on the left
    if length(s)>50 && haslength(itr) && all(haslength, itrs)
        min_length, min_idx = findmin(length, itrs)
        if length(itr) > min_length
            new_itrs = setindex(itrs, itr, min_idx)
            return intersect(s, itrs[min_idx], new_itrs...)
        end
    end
    T = promote_eltype(s, itr, itrs...)
    if T == promote_eltype(s, itr)
        out = intersect(s, itr)
    else
        out = union!(emptymutable(s, T), s)
        intersect!(out, itr)
    end
    return intersect!(out, itrs...)
end
intersect(s) = union(s)
function intersect(s::AbstractSet, itr)
    if haslength(itr) && hasfastin(itr) && length(s) < length(itr)
        return mapfilter(in(itr), push!, s, emptymutable(s, promote_eltype(s, itr)))
    else
        return mapfilter(in(s), push!, itr, emptymutable(s, promote_eltype(s, itr)))
    end
end

const ∩ = intersect

"""
    intersect!(s::Union{AbstractSet,AbstractVector}, itrs...)

Intersect all passed in sets and overwrite `s` with the result.
Maintain order with arrays.

$(_DOCS_ALIASING_WARNING)
"""
function intersect!(s::AbstractSet, itrs...)
    for x in itrs
        intersect!(s, x)
    end
    return s
end
intersect!(s::AbstractSet, s2::AbstractSet) = filter!(in(s2), s)
intersect!(s::AbstractSet, itr) =
    intersect!(s, union!(emptymutable(s, eltype(itr)), itr))

"""
    setdiff(s, itrs...)

Construct the set of elements in `s` but not in any of the iterables in `itrs`.
Maintain order with arrays.

See also [`setdiff!`](@ref), [`union`](@ref) and [`intersect`](@ref).

# Examples
```jldoctest
julia> setdiff([1,2,3], [3,4,5])
2-element Vector{Int64}:
 1
 2
```
"""
setdiff(s::AbstractSet, itrs...) = setdiff!(copymutable(s), itrs...)
setdiff(s) = union(s)

"""
    setdiff!(s, itrs...)

Remove from set `s` (in-place) each element of each iterable from `itrs`.
Maintain order with arrays.

$(_DOCS_ALIASING_WARNING)

# Examples
```jldoctest
julia> a = Set([1, 3, 4, 5]);

julia> setdiff!(a, 1:2:6);

julia> a
Set{Int64} with 1 element:
  4
```
"""
function setdiff!(s::AbstractSet, itrs...)
    for x in itrs
        setdiff!(s, x)
    end
    return s
end
function setdiff!(s::AbstractSet, itr)
    for x in itr
        delete!(s, x)
    end
    return s
end


"""
    symdiff(s, itrs...)

Construct the symmetric difference of elements in the passed in sets.
When `s` is not an `AbstractSet`, the order is maintained.

See also [`symdiff!`](@ref), [`setdiff`](@ref), [`union`](@ref) and [`intersect`](@ref).

# Examples
```jldoctest
julia> symdiff([1,2,3], [3,4,5], [4,5,6])
3-element Vector{Int64}:
 1
 2
 6

julia> symdiff([1,2,1], [2, 1, 2])
Int64[]
```
"""
symdiff(s, sets...) = symdiff!(emptymutable(s, promote_eltype(s, sets...)), s, sets...)
symdiff(s) = symdiff!(copy(s))

"""
    symdiff!(s::Union{AbstractSet,AbstractVector}, itrs...)

Construct the symmetric difference of the passed in sets, and overwrite `s` with the result.
When `s` is an array, the order is maintained.
Note that in this case the multiplicity of elements matters.

$(_DOCS_ALIASING_WARNING)
"""
function symdiff!(s::AbstractSet, itrs...)
    for x in itrs
        symdiff!(s, x)
    end
    return s
end

symdiff!(s::AbstractSet, itr) = symdiff!(s::AbstractSet, Set(itr))

function symdiff!(s::AbstractSet, itr::AbstractSet)
    for x in itr
        x in s ? delete!(s, x) : push!(s, x)
    end
    return s
end

## non-strict subset comparison

const ⊆ = issubset
function ⊇ end
"""
    issubset(a, b)::Bool
    ⊆(a, b)::Bool
    ⊇(b, a)::Bool

Determine whether every element of `a` is also in `b`, using [`in`](@ref).

See also [`⊊`](@ref), [`⊈`](@ref), [`∩`](@ref intersect), [`∪`](@ref union), [`contains`](@ref).

# Examples
```jldoctest
julia> issubset([1, 2], [1, 2, 3])
true

julia> [1, 2, 3] ⊆ [1, 2]
false

julia> [1, 2, 3] ⊇ [1, 2]
true
```
"""
issubset, ⊆, ⊇

const FASTIN_SET_THRESHOLD = 70

function issubset(a, b)
    if haslength(b) && (isa(a, AbstractSet) || !hasfastin(b))
        blen = length(b) # conditions above make this length computed only when needed
        # check a for too many unique elements
        if isa(a, AbstractSet) && length(a) > blen
            return false
        end
        # when `in` would be too slow and b is big enough, convert it to a Set
        # this threshold was empirically determined (cf. #26198)
        if !hasfastin(b) && blen > FASTIN_SET_THRESHOLD
            return issubset(a, Set(b))
        end
    end
    for elt in a
        elt in b || return false
    end
    return true
end

"""
    Base.hasfastin(T)

Determine whether the computation `x ∈ collection` where `collection::T` can be considered
as a "fast" operation (typically constant or logarithmic complexity).
The definition `hasfastin(x) = hasfastin(typeof(x))` is provided for convenience so that instances
can be passed instead of types.
However the form that accepts a type argument should be defined for new types.

The default for `hasfastin(T)` is `true` for subtypes of
[`AbstractSet`](@ref), [`AbstractDict`](@ref) and [`AbstractRange`](@ref)
and `false` otherwise.
"""
hasfastin(::Type) = false
hasfastin(::Union{Type{<:AbstractSet},Type{<:AbstractDict},Type{<:AbstractRange}}) = true
hasfastin(x) = hasfastin(typeof(x))

⊇(a, b) = b ⊆ a

"""
    issubset(x)

Create a function that compares its argument to `x` using [`issubset`](@ref), i.e.
a function equivalent to `y -> issubset(y, x)`.
The returned function is of type `Base.Fix2{typeof(issubset)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
issubset(a) = Fix2(issubset, a)

"""
    ⊇(x)

Create a function that compares its argument to `x` using [`⊇`](@ref), i.e.
a function equivalent to `y -> y ⊇ x`.
The returned function is of type `Base.Fix2{typeof(⊇)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
⊇(a) = Fix2(⊇, a)
## strict subset comparison

function ⊊ end
function ⊋ end
"""
    ⊊(a, b)::Bool
    ⊋(b, a)::Bool

Determines if `a` is a subset of, but not equal to, `b`.

See also [`issubset`](@ref) (`⊆`), [`⊈`](@ref).

# Examples
```jldoctest
julia> (1, 2) ⊊ (1, 2, 3)
true

julia> (1, 2) ⊊ (1, 2)
false
```
"""
⊊, ⊋

⊊(a::AbstractSet, b::AbstractSet) = length(a) < length(b) && a ⊆ b
⊊(a::AbstractSet, b) = a ⊊ Set(b)
⊊(a, b::AbstractSet) = Set(a) ⊊ b
⊊(a, b) = Set(a) ⊊ Set(b)
⊋(a, b) = b ⊊ a

"""
    ⊋(x)

Create a function that compares its argument to `x` using [`⊋`](@ref), i.e.
a function equivalent to `y -> y ⊋ x`.
The returned function is of type `Base.Fix2{typeof(⊋)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
⊋(a) = Fix2(⊋, a)
"""
    ⊊(x)

Create a function that compares its argument to `x` using [`⊊`](@ref), i.e.
a function equivalent to `y -> y ⊊ x`.
The returned function is of type `Base.Fix2{typeof(⊊)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
⊊(a) = Fix2(⊊, a)

function ⊈ end
function ⊉ end
"""
    ⊈(a, b)::Bool
    ⊉(b, a)::Bool

Negation of `⊆` and `⊇`, i.e. checks that `a` is not a subset of `b`.

See also [`issubset`](@ref) (`⊆`), [`⊊`](@ref).

# Examples
```jldoctest
julia> (1, 2) ⊈ (2, 3)
true

julia> (1, 2) ⊈ (1, 2, 3)
false
```
"""
⊈, ⊉

⊈(a, b) = !⊆(a, b)
⊉(a, b) = b ⊈ a

"""
    ⊉(x)

Create a function that compares its argument to `x` using [`⊉`](@ref), i.e.
a function equivalent to `y -> y ⊉ x`.
The returned function is of type `Base.Fix2{typeof(⊉)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
⊉(a) = Fix2(⊉, a)

"""
    ⊈(x)

Create a function that compares its argument to `x` using [`⊈`](@ref), i.e.
a function equivalent to `y -> y ⊈ x`.
The returned function is of type `Base.Fix2{typeof(⊈)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
⊈(a) = Fix2(⊈, a)

## set equality comparison

"""
    issetequal(a, b)::Bool

Determine whether `a` and `b` have the same elements. Equivalent
to `a ⊆ b && b ⊆ a` but more efficient when possible.

See also: [`isdisjoint`](@ref), [`union`](@ref).

# Examples
```jldoctest
julia> issetequal([1, 2], [1, 2, 3])
false

julia> issetequal([1, 2], [2, 1])
true
```
"""
issetequal(a::AbstractSet, b::AbstractSet) = a == b
issetequal(a::AbstractSet, b) = issetequal(a, Set(b))

function issetequal(a, b::AbstractSet)
    if haslength(a)
        # check b for too many unique elements
        length(a) < length(b) && return false
    end
    return issetequal(Set(a), b)
end

function issetequal(a, b)
    haslength(a) && return issetequal(a, Set(b))
    haslength(b) && return issetequal(b, Set(a))
    return issetequal(Set(a), Set(b))
end

"""
    issetequal(x)

Create a function that compares its argument to `x` using [`issetequal`](@ref), i.e.
a function equivalent to `y -> issetequal(y, x)`.
The returned function is of type `Base.Fix2{typeof(issetequal)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
issetequal(a) = Fix2(issetequal, a)

## set disjoint comparison
"""
    isdisjoint(a, b)::Bool

Determine whether the collections `a` and `b` are disjoint.
Equivalent to `isempty(a ∩ b)` but more efficient when possible.

See also: [`intersect`](@ref), [`isempty`](@ref), [`issetequal`](@ref).

!!! compat "Julia 1.5"
    This function requires at least Julia 1.5.

# Examples
```jldoctest
julia> isdisjoint([1, 2], [2, 3, 4])
false

julia> isdisjoint([3, 1], [2, 4])
true
```
"""
function isdisjoint(a, b)
    function _isdisjoint(a, b)
        hasfastin(b) && return !any(in(b), a)
        hasfastin(a) && return !any(in(a), b)
        haslength(b) && length(b) < FASTIN_SET_THRESHOLD &&
            return !any(in(b), a)
        return !any(in(Set(b)), a)
    end
    if haslength(a) && haslength(b) && length(b) < length(a)
        return _isdisjoint(b, a)
    end
    _isdisjoint(a, b)
end

function isdisjoint(a::AbstractRange{T}, b::AbstractRange{T}) where T
    (isempty(a) || isempty(b)) && return true
    fa, la = extrema(a)
    fb, lb = extrema(b)
    if (la < fb) | (lb < fa)
        return true
    else
        return _overlapping_range_isdisjoint(a, b)
    end
end

"""
    isdisjoint(x)

Create a function that compares its argument to `x` using [`isdisjoint`](@ref), i.e.
a function equivalent to `y -> isdisjoint(y, x)`.
The returned function is of type `Base.Fix2{typeof(isdisjoint)}`, which can be
used to implement specialized methods.

!!! compat "Julia 1.11"
    This functionality requires at least Julia 1.11.
"""
isdisjoint(a) = Fix2(isdisjoint, a)

_overlapping_range_isdisjoint(a::AbstractRange{T}, b::AbstractRange{T}) where T = invoke(isdisjoint, Tuple{Any,Any}, a, b)

function _overlapping_range_isdisjoint(a::AbstractRange{T}, b::AbstractRange{T}) where T<:Integer
    if abs(step(a)) == abs(step(b))
        return mod(minimum(a), step(a)) != mod(minimum(b), step(a))
    else
        return invoke(isdisjoint, Tuple{Any,Any}, a, b)
    end
end

## partial ordering of sets by containment

==(a::AbstractSet, b::AbstractSet) = length(a) == length(b) && a ⊆ b
# convenience functions for AbstractSet
# (if needed, only their synonyms ⊊ and ⊆ must be specialized)
<( a::AbstractSet, b::AbstractSet) = a ⊊ b
<=(a::AbstractSet, b::AbstractSet) = a ⊆ b

## filtering sets

filter(pred, s::AbstractSet) = mapfilter(pred, push!, s, emptymutable(s))

# it must be safe to delete the current element while iterating over s:
unsafe_filter!(pred, s::AbstractSet) = mapfilter(!pred, delete!, s, s)

# TODO: delete mapfilter in favor of comprehensions/foldl/filter when competitive
function mapfilter(pred, f, itr, res)
    for x in itr
        pred(x) && f(res, x)
    end
    res
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	eltype(::Type{<:AbstractSet{T}}) where {T} = @isdefined(T) ? T : Any	32,487✔
4	sizehint!(s::AbstractSet, n) = s	×
5
6	function copy!(dst::AbstractSet, src::AbstractSet)	×
7	dst === src && return dst	×
8	union!(empty!(dst), src)	×
9	end
10
11	## set operations (union, intersection, symmetric difference)
12
13	"""
14	union(s, itrs...)
15	∪(s, itrs...)
16
17	Construct an object containing all distinct elements from all of the arguments.
18
19	The first argument controls what kind of container is returned.
20	If this is an array, it maintains the order in which elements first appear.
21
22	Unicode `∪` can be typed by writing `\\cup` then pressing tab in the Julia REPL, and in many editors.
23	This is an infix operator, allowing `s ∪ itr`.
24
25	See also [`unique`](@ref), [`intersect`](@ref), [`isdisjoint`](@ref), [`vcat`](@ref), [`Iterators.flatten`](@ref).
26
27	# Examples
28	```jldoctest; filter = r"^\\s+\\d\$"m
29	julia> union([1, 2], [3])
30	3-element Vector{Int64}:
31	1
32	2
33	3
34
35	julia> union([4 2 3 4 4], 1:3, 3.0)
36	4-element Vector{Float64}:
37	4.0
38	2.0
39	3.0
40	1.0
41
42	julia> (0, 0.0) ∪ (-0.0, NaN)
43	3-element Vector{Real}:
44	0
45	-0.0
46	NaN
47
48	julia> union(Set([1, 2]), 2:3)
49	Set{Int64} with 3 elements:
50	2
51	3
52	1
53	```
54	"""
55	function union end
56
57	union(s, sets...) = union!(emptymutable(s, promote_eltype(s, sets...)), s, sets...)	191✔
58	union(s::AbstractSet) = copy(s)	×
59
60	const ∪ = union
61
62	"""
63	union!(s::Union{AbstractSet,AbstractVector}, itrs...)
64
65	Construct the [`union`](@ref) of passed in sets and overwrite `s` with the result.
66	Maintain order with arrays.
67
68	$(_DOCS_ALIASING_WARNING)
69
70	# Examples
71	```jldoctest; filter = r"^\\s+\\d\$"m
72	julia> a = Set([3, 4, 5]);
73
74	julia> union!(a, 1:2:7);
75
76	julia> a
77	Set{Int64} with 5 elements:
78	5
79	4
80	7
81	3
82	1
83	```
84	"""
85	function union!(s::AbstractSet, sets...)	2✔
86	for x in sets	19✔
87	union!(s, x)	26✔
88	end	39✔
89	return s	19✔
90	end
91
92	max_values(::Type) = typemax(Int)	509,595✔
93	max_values(T::Union{map(X -> Type{X}, BitIntegerSmall_types)...}) = 1 << (8*sizeof(T))	×
94	# saturated addition to prevent overflow with typemax(Int)
95	function max_values(T::Union)
96	a = max_values(T.a)::Int	286✔
97	b = max_values(T.b)::Int	286✔
98	return max(a, b, a + b)	286✔
99	end
100	max_values(::Type{Bool}) = 2	×
101	max_values(::Type{Nothing}) = 1	×
102
103	function union!(s::AbstractSet{T}, itr) where T	21,126✔
104	haslength(itr) && sizehint!(s, length(s) + Int(length(itr))::Int; shrink = false)	23,921✔
105	for x in itr	28,387✔
106	push!(s, x)	296,212✔
107	length(s) == max_values(T) && break	296,186✔
108	end	296,122✔
109	return s	21,173✔
110	end
111
112	"""
113	intersect(s, itrs...)
114	∩(s, itrs...)
115
116	Construct the set containing those elements which appear in all of the arguments.
117
118	The first argument controls what kind of container is returned.
119	If this is an array, it maintains the order in which elements first appear.
120
121	Unicode `∩` can be typed by writing `\\cap` then pressing tab in the Julia REPL, and in many editors.
122	This is an infix operator, allowing `s ∩ itr`.
123
124	See also [`setdiff`](@ref), [`isdisjoint`](@ref), [`issubset`](@ref Base.issubset), [`issetequal`](@ref).
125
126	!!! compat "Julia 1.8"
127	As of Julia 1.8 intersect returns a result with the eltype of the
128	type-promoted eltypes of the two inputs
129
130	# Examples
131	```jldoctest
132	julia> intersect([1, 2, 3], [3, 4, 5])
133	1-element Vector{Int64}:
134	3
135
136	julia> intersect([1, 4, 4, 5, 6], [6, 4, 6, 7, 8])
137	2-element Vector{Int64}:
138	4
139	6
140
141	julia> intersect(1:16, 7:99)
142	7:16
143
144	julia> (0, 0.0) ∩ (-0.0, 0)
145	1-element Vector{Real}:
146	0
147
148	julia> intersect(Set([1, 2]), BitSet([2, 3]), 1.0:10.0)
149	Set{Float64} with 1 element:
150	2.0
151	```
152	"""
153	function intersect(s::AbstractSet, itr, itrs...)	2✔
154	# heuristics to try to `intersect` with the shortest Set on the left
155	if length(s)>50 && haslength(itr) && all(haslength, itrs)	2✔
156	min_length, min_idx = findmin(length, itrs)	×
157	if length(itr) > min_length	×
158	new_itrs = setindex(itrs, itr, min_idx)	×
159	return intersect(s, itrs[min_idx], new_itrs...)	×
160	end
161	end
162	T = promote_eltype(s, itr, itrs...)	2✔
163	if T == promote_eltype(s, itr)	2✔
164	out = intersect(s, itr)	2✔
165	else
166	out = union!(emptymutable(s, T), s)	×
167	intersect!(out, itr)	×
168	end
169	return intersect!(out, itrs...)	2✔
170	end
171	intersect(s) = union(s)	6✔
172	function intersect(s::AbstractSet, itr)	5✔
173	if haslength(itr) && hasfastin(itr) && length(s) < length(itr)	5✔
174	return mapfilter(in(itr), push!, s, emptymutable(s, promote_eltype(s, itr)))	×
175	else
176	return mapfilter(in(s), push!, itr, emptymutable(s, promote_eltype(s, itr)))	5✔
177	end
178	end
179
180	const ∩ = intersect
181
182	"""
183	intersect!(s::Union{AbstractSet,AbstractVector}, itrs...)
184
185	Intersect all passed in sets and overwrite `s` with the result.
186	Maintain order with arrays.
187
188	$(_DOCS_ALIASING_WARNING)
189	"""
190	function intersect!(s::AbstractSet, itrs...)	1✔
191	for x in itrs	2✔
192	intersect!(s, x)	5✔
193	end	6✔
194	return s	2✔
195	end
196	intersect!(s::AbstractSet, s2::AbstractSet) = filter!(in(s2), s)	326✔
197	intersect!(s::AbstractSet, itr) =	325✔
198	intersect!(s, union!(emptymutable(s, eltype(itr)), itr))
199
200	"""
201	setdiff(s, itrs...)
202
203	Construct the set of elements in `s` but not in any of the iterables in `itrs`.
204	Maintain order with arrays.
205
206	See also [`setdiff!`](@ref), [`union`](@ref) and [`intersect`](@ref).
207
208	# Examples
209	```jldoctest
210	julia> setdiff([1,2,3], [3,4,5])
211	2-element Vector{Int64}:
212	1
213	2
214	```
215	"""
216	setdiff(s::AbstractSet, itrs...) = setdiff!(copymutable(s), itrs...)	104,454✔
217	setdiff(s) = union(s)	×
218
219	"""
220	setdiff!(s, itrs...)
221
222	Remove from set `s` (in-place) each element of each iterable from `itrs`.
223	Maintain order with arrays.
224
225	$(_DOCS_ALIASING_WARNING)
226
227	# Examples
228	```jldoctest
229	julia> a = Set([1, 3, 4, 5]);
230
231	julia> setdiff!(a, 1:2:6);
232
233	julia> a
234	Set{Int64} with 1 element:
235	4
236	```
237	"""
238	function setdiff!(s::AbstractSet, itrs...)	×
239	for x in itrs	×
240	setdiff!(s, x)	×
241	end	×
242	return s	×
243	end
244	function setdiff!(s::AbstractSet, itr)	460✔
245	for x in itr	1,269✔
246	delete!(s, x)	14,129✔
247	end	27,263✔
248	return s	820✔
249	end
250
251
252	"""
253	symdiff(s, itrs...)
254
255	Construct the symmetric difference of elements in the passed in sets.
256	When `s` is not an `AbstractSet`, the order is maintained.
257
258	See also [`symdiff!`](@ref), [`setdiff`](@ref), [`union`](@ref) and [`intersect`](@ref).
259
260	# Examples
261	```jldoctest
262	julia> symdiff([1,2,3], [3,4,5], [4,5,6])
263	3-element Vector{Int64}:
264	1
265	2
266	6
267
268	julia> symdiff([1,2,1], [2, 1, 2])
269	Int64[]
270	```
271	"""
272	symdiff(s, sets...) = symdiff!(emptymutable(s, promote_eltype(s, sets...)), s, sets...)	21✔
273	symdiff(s) = symdiff!(copy(s))	2✔
274
275	"""
276	symdiff!(s::Union{AbstractSet,AbstractVector}, itrs...)
277
278	Construct the symmetric difference of the passed in sets, and overwrite `s` with the result.
279	When `s` is an array, the order is maintained.
280	Note that in this case the multiplicity of elements matters.
281
282	$(_DOCS_ALIASING_WARNING)
283	"""
284	function symdiff!(s::AbstractSet, itrs...)	17✔
285	for x in itrs	21✔
286	symdiff!(s, x)	62✔
287	end	73✔
288	return s	21✔
289	end
290
291	symdiff!(s::AbstractSet, itr) = symdiff!(s::AbstractSet, Set(itr))	28✔
292
293	function symdiff!(s::AbstractSet, itr::AbstractSet)	36✔
294	for x in itr	72✔
295	x in s ? delete!(s, x) : push!(s, x)	130✔
296	end	150✔
297	return s	36✔
298	end
299
300	## non-strict subset comparison
301
302	const ⊆ = issubset
303	function ⊇ end
304	"""
305	issubset(a, b)::Bool
306	⊆(a, b)::Bool
307	⊇(b, a)::Bool
308
309	Determine whether every element of `a` is also in `b`, using [`in`](@ref).
310
311	See also [`⊊`](@ref), [`⊈`](@ref), [`∩`](@ref intersect), [`∪`](@ref union), [`contains`](@ref).
312
313	# Examples
314	```jldoctest
315	julia> issubset([1, 2], [1, 2, 3])
316	true
317
318	julia> [1, 2, 3] ⊆ [1, 2]
319	false
320
321	julia> [1, 2, 3] ⊇ [1, 2]
322	true
323	```
324	"""
325	issubset, ⊆, ⊇
326
327	const FASTIN_SET_THRESHOLD = 70
328
329	function issubset(a, b)	291✔
330	if haslength(b) && (isa(a, AbstractSet) \|\| !hasfastin(b))	442✔
331	blen = length(b) # conditions above make this length computed only when needed	110✔
332	# check a for too many unique elements
333	if isa(a, AbstractSet) && length(a) > blen	110✔
334	return false	8✔
335	end
336	# when `in` would be too slow and b is big enough, convert it to a Set
337	# this threshold was empirically determined (cf. #26198)
338	if !hasfastin(b) && blen > FASTIN_SET_THRESHOLD	102✔
339	return issubset(a, Set(b))	×
340	end
341	end
342	for elt in a	697✔
343	elt in b \|\| return false	8,938✔
344	end	16,715✔
345	return true	320✔
346	end
347
348	"""
349	Base.hasfastin(T)
350
351	Determine whether the computation `x ∈ collection` where `collection::T` can be considered
352	as a "fast" operation (typically constant or logarithmic complexity).
353	The definition `hasfastin(x) = hasfastin(typeof(x))` is provided for convenience so that instances
354	can be passed instead of types.
355	However the form that accepts a type argument should be defined for new types.
356
357	The default for `hasfastin(T)` is `true` for subtypes of
358	[`AbstractSet`](@ref), [`AbstractDict`](@ref) and [`AbstractRange`](@ref)
359	and `false` otherwise.
360	"""
361	hasfastin(::Type) = false	×
362	hasfastin(::Union{Type{<:AbstractSet},Type{<:AbstractDict},Type{<:AbstractRange}}) = true	×
363	hasfastin(x) = hasfastin(typeof(x))	446✔
364
365	⊇(a, b) = b ⊆ a	×
366
367	"""
368	issubset(x)
369
370	Create a function that compares its argument to `x` using [`issubset`](@ref), i.e.
371	a function equivalent to `y -> issubset(y, x)`.
372	The returned function is of type `Base.Fix2{typeof(issubset)}`, which can be
373	used to implement specialized methods.
374
375	!!! compat "Julia 1.11"
376	This functionality requires at least Julia 1.11.
377	"""
378	issubset(a) = Fix2(issubset, a)	×
379
380	"""
381	⊇(x)
382
383	Create a function that compares its argument to `x` using [`⊇`](@ref), i.e.
384	a function equivalent to `y -> y ⊇ x`.
385	The returned function is of type `Base.Fix2{typeof(⊇)}`, which can be
386	used to implement specialized methods.
387
388	!!! compat "Julia 1.11"
389	This functionality requires at least Julia 1.11.
390	"""
391	⊇(a) = Fix2(⊇, a)	×
392	## strict subset comparison
393
394	function ⊊ end
395	function ⊋ end
396	"""
397	⊊(a, b)::Bool
398	⊋(b, a)::Bool
399
400	Determines if `a` is a subset of, but not equal to, `b`.
401
402	See also [`issubset`](@ref) (`⊆`), [`⊈`](@ref).
403
404	# Examples
405	```jldoctest
406	julia> (1, 2) ⊊ (1, 2, 3)
407	true
408
409	julia> (1, 2) ⊊ (1, 2)
410	false
411	```
412	"""
413	⊊, ⊋
414
415	⊊(a::AbstractSet, b::AbstractSet) = length(a) < length(b) && a ⊆ b	60✔
416	⊊(a::AbstractSet, b) = a ⊊ Set(b)	×
417	⊊(a, b::AbstractSet) = Set(a) ⊊ b	×
418	⊊(a, b) = Set(a) ⊊ Set(b)	55✔
419	⊋(a, b) = b ⊊ a	47✔
420
421	"""
422	⊋(x)
423
424	Create a function that compares its argument to `x` using [`⊋`](@ref), i.e.
425	a function equivalent to `y -> y ⊋ x`.
426	The returned function is of type `Base.Fix2{typeof(⊋)}`, which can be
427	used to implement specialized methods.
428
429	!!! compat "Julia 1.11"
430	This functionality requires at least Julia 1.11.
431	"""
432	⊋(a) = Fix2(⊋, a)	×
433	"""
434	⊊(x)
435
436	Create a function that compares its argument to `x` using [`⊊`](@ref), i.e.
437	a function equivalent to `y -> y ⊊ x`.
438	The returned function is of type `Base.Fix2{typeof(⊊)}`, which can be
439	used to implement specialized methods.
440
441	!!! compat "Julia 1.11"
442	This functionality requires at least Julia 1.11.
443	"""
444	⊊(a) = Fix2(⊊, a)	×
445
446	function ⊈ end
447	function ⊉ end
448	"""
449	⊈(a, b)::Bool
450	⊉(b, a)::Bool
451
452	Negation of `⊆` and `⊇`, i.e. checks that `a` is not a subset of `b`.
453
454	See also [`issubset`](@ref) (`⊆`), [`⊊`](@ref).
455
456	# Examples
457	```jldoctest
458	julia> (1, 2) ⊈ (2, 3)
459	true
460
461	julia> (1, 2) ⊈ (1, 2, 3)
462	false
463	```
464	"""
465	⊈, ⊉
466
467	⊈(a, b) = !⊆(a, b)	×
468	⊉(a, b) = b ⊈ a	×
469
470	"""
471	⊉(x)
472
473	Create a function that compares its argument to `x` using [`⊉`](@ref), i.e.
474	a function equivalent to `y -> y ⊉ x`.
475	The returned function is of type `Base.Fix2{typeof(⊉)}`, which can be
476	used to implement specialized methods.
477
478	!!! compat "Julia 1.11"
479	This functionality requires at least Julia 1.11.
480	"""
481	⊉(a) = Fix2(⊉, a)	×
482
483	"""
484	⊈(x)
485
486	Create a function that compares its argument to `x` using [`⊈`](@ref), i.e.
487	a function equivalent to `y -> y ⊈ x`.
488	The returned function is of type `Base.Fix2{typeof(⊈)}`, which can be
489	used to implement specialized methods.
490
491	!!! compat "Julia 1.11"
492	This functionality requires at least Julia 1.11.
493	"""
494	⊈(a) = Fix2(⊈, a)	×
495
496	## set equality comparison
497
498	"""
499	issetequal(a, b)::Bool
500
501	Determine whether `a` and `b` have the same elements. Equivalent
502	to `a ⊆ b && b ⊆ a` but more efficient when possible.
503
504	See also: [`isdisjoint`](@ref), [`union`](@ref).
505
506	# Examples
507	```jldoctest
508	julia> issetequal([1, 2], [1, 2, 3])
509	false
510
511	julia> issetequal([1, 2], [2, 1])
512	true
513	```
514	"""
515	issetequal(a::AbstractSet, b::AbstractSet) = a == b	2✔
516	issetequal(a::AbstractSet, b) = issetequal(a, Set(b))	×
517
518	function issetequal(a, b::AbstractSet)
519	if haslength(a)	2✔
520	# check b for too many unique elements
521	length(a) < length(b) && return false	2✔
522	end
523	return issetequal(Set(a), b)	2✔
524	end
525
526	function issetequal(a, b)	2✔
527	haslength(a) && return issetequal(a, Set(b))	2✔
528	haslength(b) && return issetequal(b, Set(a))	×
529	return issetequal(Set(a), Set(b))	×
530	end
531
532	"""
533	issetequal(x)
534
535	Create a function that compares its argument to `x` using [`issetequal`](@ref), i.e.
536	a function equivalent to `y -> issetequal(y, x)`.
537	The returned function is of type `Base.Fix2{typeof(issetequal)}`, which can be
538	used to implement specialized methods.
539
540	!!! compat "Julia 1.11"
541	This functionality requires at least Julia 1.11.
542	"""
543	issetequal(a) = Fix2(issetequal, a)	×
544
545	## set disjoint comparison
546	"""
547	isdisjoint(a, b)::Bool
548
549	Determine whether the collections `a` and `b` are disjoint.
550	Equivalent to `isempty(a ∩ b)` but more efficient when possible.
551
552	See also: [`intersect`](@ref), [`isempty`](@ref), [`issetequal`](@ref).
553
554	!!! compat "Julia 1.5"
555	This function requires at least Julia 1.5.
556
557	# Examples
558	```jldoctest
559	julia> isdisjoint([1, 2], [2, 3, 4])
560	false
561
562	julia> isdisjoint([3, 1], [2, 4])
563	true
564	```
565	"""
566	function isdisjoint(a, b)	×
567	function _isdisjoint(a, b)	×
568	hasfastin(b) && return !any(in(b), a)	×
569	hasfastin(a) && return !any(in(a), b)	×
570	haslength(b) && length(b) < FASTIN_SET_THRESHOLD &&	×
571	return !any(in(b), a)
572	return !any(in(Set(b)), a)	×
573	end
574	if haslength(a) && haslength(b) && length(b) < length(a)	×
575	return _isdisjoint(b, a)	×
576	end
577	_isdisjoint(a, b)	×
578	end
579
580	function isdisjoint(a::AbstractRange{T}, b::AbstractRange{T}) where T	75✔
581	(isempty(a) \|\| isempty(b)) && return true	75✔
582	fa, la = extrema(a)	75✔
583	fb, lb = extrema(b)	75✔
584	if (la < fb) \| (lb < fa)	75✔
585	return true	12✔
586	else
587	return _overlapping_range_isdisjoint(a, b)	63✔
588	end
589	end
590
591	"""
592	isdisjoint(x)
593
594	Create a function that compares its argument to `x` using [`isdisjoint`](@ref), i.e.
595	a function equivalent to `y -> isdisjoint(y, x)`.
596	The returned function is of type `Base.Fix2{typeof(isdisjoint)}`, which can be
597	used to implement specialized methods.
598
599	!!! compat "Julia 1.11"
600	This functionality requires at least Julia 1.11.
601	"""
602	isdisjoint(a) = Fix2(isdisjoint, a)	×
603
604	_overlapping_range_isdisjoint(a::AbstractRange{T}, b::AbstractRange{T}) where T = invoke(isdisjoint, Tuple{Any,Any}, a, b)	×
605
606	function _overlapping_range_isdisjoint(a::AbstractRange{T}, b::AbstractRange{T}) where T<:Integer	×
607	if abs(step(a)) == abs(step(b))	63✔
608	return mod(minimum(a), step(a)) != mod(minimum(b), step(a))	63✔
609	else
610	return invoke(isdisjoint, Tuple{Any,Any}, a, b)	×
611	end
612	end
613
614	## partial ordering of sets by containment
615
616	==(a::AbstractSet, b::AbstractSet) = length(a) == length(b) && a ⊆ b	52✔
617	# convenience functions for AbstractSet
618	# (if needed, only their synonyms ⊊ and ⊆ must be specialized)
619	<( a::AbstractSet, b::AbstractSet) = a ⊊ b	9✔
620	<=(a::AbstractSet, b::AbstractSet) = a ⊆ b	11✔
621
622	## filtering sets
623
624	filter(pred, s::AbstractSet) = mapfilter(pred, push!, s, emptymutable(s))	39✔
625
626	# it must be safe to delete the current element while iterating over s:
627	unsafe_filter!(pred, s::AbstractSet) = mapfilter(!pred, delete!, s, s)	505✔
628
629	# TODO: delete mapfilter in favor of comprehensions/foldl/filter when competitive
630	function mapfilter(pred, f, itr, res)	948✔
631	for x in itr	1,533✔
632	pred(x) && f(res, x)	245,285✔
633	end	363,846✔
634	res	948✔
635	end

JuliaLang / julia / #38182

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous