Report index
StatProfilerHTML.jl report
Generated on Mon, 01 Apr 2024 21:01:18
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 ## array.jl: Dense arrays
4
5 """
6 DimensionMismatch([msg])
7
8 The objects called do not have matching dimensionality. Optional argument `msg` is a
9 descriptive error string.
10 """
11 struct DimensionMismatch <: Exception
12 msg::AbstractString
13 end
14 DimensionMismatch() = DimensionMismatch("")
15
16 ## Type aliases for convenience ##
17 """
18 AbstractVector{T}
19
20 Supertype for one-dimensional arrays (or array-like types) with
21 elements of type `T`. Alias for [`AbstractArray{T,1}`](@ref).
22 """
23 const AbstractVector{T} = AbstractArray{T,1}
24
25 """
26 AbstractMatrix{T}
27
28 Supertype for two-dimensional arrays (or array-like types) with
29 elements of type `T`. Alias for [`AbstractArray{T,2}`](@ref).
30 """
31 const AbstractMatrix{T} = AbstractArray{T,2}
32
33 """
34 AbstractVecOrMat{T}
35
36 Union type of [`AbstractVector{T}`](@ref) and [`AbstractMatrix{T}`](@ref).
37 """
38 const AbstractVecOrMat{T} = Union{AbstractVector{T}, AbstractMatrix{T}}
39 const RangeIndex = Union{<:BitInteger, AbstractRange{<:BitInteger}}
40 const DimOrInd = Union{Integer, AbstractUnitRange}
41 const IntOrInd = Union{Int, AbstractUnitRange}
42 const DimsOrInds{N} = NTuple{N,DimOrInd}
43 const NeedsShaping = Union{Tuple{Integer,Vararg{Integer}}, Tuple{OneTo,Vararg{OneTo}}}
44
45 """
46 Array{T,N} <: AbstractArray{T,N}
47
48 `N`-dimensional dense array with elements of type `T`.
49 """
50 Array
51
52 """
53 Vector{T} <: AbstractVector{T}
54
55 One-dimensional dense array with elements of type `T`, often used to represent
56 a mathematical vector. Alias for [`Array{T,1}`](@ref).
57
58 See also [`empty`](@ref), [`similar`](@ref) and [`zero`](@ref) for creating vectors.
59 """
60 const Vector{T} = Array{T,1}
61
62 """
63 Matrix{T} <: AbstractMatrix{T}
64
65 Two-dimensional dense array with elements of type `T`, often used to represent
66 a mathematical matrix. Alias for [`Array{T,2}`](@ref).
67
68 See also [`fill`](@ref), [`zeros`](@ref), [`undef`](@ref) and [`similar`](@ref)
69 for creating matrices.
70 """
71 const Matrix{T} = Array{T,2}
72
73 """
74 VecOrMat{T}
75
76 Union type of [`Vector{T}`](@ref) and [`Matrix{T}`](@ref) which allows functions to accept either a Matrix or a Vector.
77
78 # Examples
79 ```jldoctest
80 julia> Vector{Float64} <: VecOrMat{Float64}
81 true
82
83 julia> Matrix{Float64} <: VecOrMat{Float64}
84 true
85
86 julia> Array{Float64, 3} <: VecOrMat{Float64}
87 false
88 ```
89 """
90 const VecOrMat{T} = Union{Vector{T}, Matrix{T}}
91
92 """
93 DenseArray{T, N} <: AbstractArray{T,N}
94
95 `N`-dimensional dense array with elements of type `T`.
96 The elements of a dense array are stored contiguously in memory.
97 """
98 DenseArray
99
100 """
101 DenseVector{T}
102
103 One-dimensional [`DenseArray`](@ref) with elements of type `T`. Alias for `DenseArray{T,1}`.
104 """
105 const DenseVector{T} = DenseArray{T,1}
106
107 """
108 DenseMatrix{T}
109
110 Two-dimensional [`DenseArray`](@ref) with elements of type `T`. Alias for `DenseArray{T,2}`.
111 """
112 const DenseMatrix{T} = DenseArray{T,2}
113
114 """
115 DenseVecOrMat{T}
116
117 Union type of [`DenseVector{T}`](@ref) and [`DenseMatrix{T}`](@ref).
118 """
119 const DenseVecOrMat{T} = Union{DenseVector{T}, DenseMatrix{T}}
120
121 ## Basic functions ##
122
123 using Core: arraysize, arrayset, const_arrayref
124
125 """
126 @_safeindex
127
128 This internal macro converts:
129 - `getindex(xs::Tuple, )` -> `__inbounds_getindex(args...)`
130 - `setindex!(xs::Vector, args...)` -> `__inbounds_setindex!(xs, args...)`
131 to tell the compiler that indexing operations within the applied expression are always
132 inbounds and do not need to taint `:consistent` and `:nothrow`.
133 """
134 macro _safeindex(ex)
135 return esc(_safeindex(__module__, ex))
136 end
137 function _safeindex(__module__, ex)
138 isa(ex, Expr) || return ex
139 if ex.head === :(=)
140 lhs = arrayref(true, ex.args, 1)
141 if isa(lhs, Expr) && lhs.head === :ref # xs[i] = x
142 rhs = arrayref(true, ex.args, 2)
143 xs = arrayref(true, lhs.args, 1)
144 args = Vector{Any}(undef, length(lhs.args)-1)
145 for i = 2:length(lhs.args)
146 arrayset(true, args, _safeindex(__module__, arrayref(true, lhs.args, i)), i-1)
147 end
148 return Expr(:call, GlobalRef(__module__, :__inbounds_setindex!), xs, _safeindex(__module__, rhs), args...)
149 end
150 elseif ex.head === :ref # xs[i]
151 return Expr(:call, GlobalRef(__module__, :__inbounds_getindex), ex.args...)
152 end
153 args = Vector{Any}(undef, length(ex.args))
154 for i = 1:length(ex.args)
155 arrayset(true, args, _safeindex(__module__, arrayref(true, ex.args, i)), i)
156 end
157 return Expr(ex.head, args...)
158 end
159
160 vect() = Vector{Any}()
161 function vect(X::T...) where T
162 @_terminates_locally_meta
163 vec = Vector{T}(undef, length(X))
164 @_safeindex for i = 1:length(X)
165 vec[i] = X[i]
166 end
167 return vec
168 end
169
170 """
171 vect(X...)
172
173 Create a [`Vector`](@ref) with element type computed from the `promote_typeof` of the argument,
174 containing the argument list.
175
176 # Examples
177 ```jldoctest
178 julia> a = Base.vect(UInt8(1), 2.5, 1//2)
179 3-element Vector{Float64}:
180 1.0
181 2.5
182 0.5
183 ```
184 """
185 function vect(X...)
186 T = promote_typeof(X...)
187 return T[X...]
188 end
189
190 size(a::Array, d::Integer) = arraysize(a, d isa Int ? d : convert(Int, d))
191 size(a::Vector) = (arraysize(a,1),)
192 size(a::Matrix) = (arraysize(a,1), arraysize(a,2))
193 size(a::Array{<:Any,N}) where {N} = (@inline; ntuple(M -> size(a, M), Val(N))::Dims)
194
195 asize_from(a::Array, n) = n > ndims(a) ? () : (arraysize(a,n), asize_from(a, n+1)...)
196
197 allocatedinline(@nospecialize T::Type) = (@_total_meta; ccall(:jl_stored_inline, Cint, (Any,), T) != Cint(0))
198
199 """
200 Base.isbitsunion(::Type{T})
201
202 Return whether a type is an "is-bits" Union type, meaning each type included in a Union is [`isbitstype`](@ref).
203
204 # Examples
205 ```jldoctest
206 julia> Base.isbitsunion(Union{Float64, UInt8})
207 true
208
209 julia> Base.isbitsunion(Union{Float64, String})
210 false
211 ```
212 """
213 isbitsunion(u::Union) = allocatedinline(u)
214 isbitsunion(x) = false
215
216 function _unsetindex!(A::Array{T}, i::Int) where {T}
217 @inline
218 @boundscheck checkbounds(A, i)
219 t = @_gc_preserve_begin A
220 p = Ptr{Ptr{Cvoid}}(pointer(A, i))
221 if !allocatedinline(T)
222 Intrinsics.atomic_pointerset(p, C_NULL, :monotonic)
223 elseif T isa DataType
224 if !datatype_pointerfree(T)
225 for j = 1:Core.sizeof(Ptr{Cvoid}):Core.sizeof(T)
226 Intrinsics.atomic_pointerset(p + j - 1, C_NULL, :monotonic)
227 end
228 end
229 end
230 @_gc_preserve_end t
231 return A
232 end
233
234
235 """
236 Base.bitsunionsize(U::Union) -> Int
237
238 For a `Union` of [`isbitstype`](@ref) types, return the size of the largest type; assumes `Base.isbitsunion(U) == true`.
239
240 # Examples
241 ```jldoctest
242 julia> Base.bitsunionsize(Union{Float64, UInt8})
243 8
244
245 julia> Base.bitsunionsize(Union{Float64, UInt8, Int128})
246 16
247 ```
248 """
249 function bitsunionsize(u::Union)
250 isinline, sz, _ = uniontype_layout(u)
251 @assert isinline
252 return sz
253 end
254
255 elsize(@nospecialize _::Type{A}) where {T,A<:Array{T}} = aligned_sizeof(T)
256 function elsize(::Type{Ptr{T}}) where T
257 # this only must return something valid for values which satisfy is_valid_intrinsic_elptr(T),
258 # which includes Any and most concrete datatypes
259 T === Any && return sizeof(Ptr{Any})
260 T isa DataType || sizeof(Any) # throws
261 return LLT_ALIGN(Core.sizeof(T), datatype_alignment(T))
262 end
263 elsize(::Type{Union{}}, slurp...) = 0
264 sizeof(a::Array) = Core.sizeof(a)
265
266 function isassigned(a::Array, i::Int...)
267 @inline
268 @boundscheck checkbounds(Bool, a, i...) || return false
269 ii = (_sub2ind(size(a), i...) % UInt) - 1
270 ccall(:jl_array_isassigned, Cint, (Any, UInt), a, ii) == 1
271 end
272
273 ## copy ##
274
275 """
276 unsafe_copyto!(dest::Ptr{T}, src::Ptr{T}, N)
277
278 Copy `N` elements from a source pointer to a destination, with no checking. The size of an
279 element is determined by the type of the pointers.
280
281 The `unsafe` prefix on this function indicates that no validation is performed on the
282 pointers `dest` and `src` to ensure that they are valid. Incorrect usage may corrupt or
283 segfault your program, in the same manner as C.
284 """
285 function unsafe_copyto!(dest::Ptr{T}, src::Ptr{T}, n) where T
286 # Do not use this to copy data between pointer arrays.
287 # It can't be made safe no matter how carefully you checked.
288 memmove(dest, src, n * aligned_sizeof(T))
289 return dest
290 end
291
292
293 function _unsafe_copyto!(dest, doffs, src, soffs, n)
294 destp = pointer(dest, doffs)
295 srcp = pointer(src, soffs)
296 @inbounds if destp < srcp || destp > srcp + n
297 for i = 1:n
298 if isassigned(src, soffs + i - 1)
299 dest[doffs + i - 1] = src[soffs + i - 1]
300 else
301 _unsetindex!(dest, doffs + i - 1)
302 end
303 end
304 else
305 for i = n:-1:1
306 if isassigned(src, soffs + i - 1)
307 dest[doffs + i - 1] = src[soffs + i - 1]
308 else
309 _unsetindex!(dest, doffs + i - 1)
310 end
311 end
312 end
313 return dest
314 end
315
316 """
317 unsafe_copyto!(dest::Array, do, src::Array, so, N)
318
319 Copy `N` elements from a source array to a destination, starting at the linear index `so` in the
320 source and `do` in the destination (1-indexed).
321
322 The `unsafe` prefix on this function indicates that no validation is performed to ensure
323 that N is inbounds on either array. Incorrect usage may corrupt or segfault your program, in
324 the same manner as C.
325
326 $(_DOCS_ALIASING_WARNING)
327 """
328 function unsafe_copyto!(dest::Array{T}, doffs, src::Array{T}, soffs, n) where T
329 t1 = @_gc_preserve_begin dest
330 t2 = @_gc_preserve_begin src
331 destp = pointer(dest, doffs)
332 srcp = pointer(src, soffs)
333 if !allocatedinline(T)
334 ccall(:jl_array_ptr_copy, Cvoid, (Any, Ptr{Cvoid}, Any, Ptr{Cvoid}, Int),
335 dest, destp, src, srcp, n)
336 elseif isbitstype(T)
337 memmove(destp, srcp, n * aligned_sizeof(T))
338 elseif isbitsunion(T)
339 memmove(destp, srcp, n * aligned_sizeof(T))
340 # copy selector bytes
341 memmove(
342 ccall(:jl_array_typetagdata, Ptr{UInt8}, (Any,), dest) + doffs - 1,
343 ccall(:jl_array_typetagdata, Ptr{UInt8}, (Any,), src) + soffs - 1,
344 n)
345 else
346 _unsafe_copyto!(dest, doffs, src, soffs, n)
347 end
348 @_gc_preserve_end t2
349 @_gc_preserve_end t1
350 return dest
351 end
352
353 unsafe_copyto!(dest::Array, doffs, src::Array, soffs, n) =
354 _unsafe_copyto!(dest, doffs, src, soffs, n)
355
356 """
357 copyto!(dest, do, src, so, N)
358
359 Copy `N` elements from collection `src` starting at the linear index `so`, to array `dest` starting at
360 the index `do`. Return `dest`.
361 """
362 function copyto!(dest::Array, doffs::Integer, src::Array, soffs::Integer, n::Integer)
363 return _copyto_impl!(dest, doffs, src, soffs, n)
364 end
365
366 # this is only needed to avoid possible ambiguities with methods added in some packages
367 function copyto!(dest::Array{T}, doffs::Integer, src::Array{T}, soffs::Integer, n::Integer) where T
368 return _copyto_impl!(dest, doffs, src, soffs, n)
369 end
370
371 function _copyto_impl!(dest::Array, doffs::Integer, src::Array, soffs::Integer, n::Integer)
372 n == 0 && return dest
373 n > 0 || _throw_argerror("Number of elements to copy must be nonnegative.")
374 @boundscheck checkbounds(dest, doffs:doffs+n-1)
375 @boundscheck checkbounds(src, soffs:soffs+n-1)
376 unsafe_copyto!(dest, doffs, src, soffs, n)
377 return dest
378 end
379
380 # Outlining this because otherwise a catastrophic inference slowdown
381 # occurs, see discussion in #27874.
382 # It is also mitigated by using a constant string.
383 _throw_argerror(s) = (@noinline; throw(ArgumentError(s)))
384
385 copyto!(dest::Array, src::Array) = copyto!(dest, 1, src, 1, length(src))
386
387 # also to avoid ambiguities in packages
388 copyto!(dest::Array{T}, src::Array{T}) where {T} = copyto!(dest, 1, src, 1, length(src))
389
390 # N.B: The generic definition in multidimensional.jl covers, this, this is just here
391 # for bootstrapping purposes.
392 function fill!(dest::Array{T}, x) where T
393 xT = x isa T ? x : convert(T, x)::T
394 for i in eachindex(dest)
395 @inbounds dest[i] = xT
396 end
397 return dest
398 end
399
400 """
401 copy(x)
402
403 Create a shallow copy of `x`: the outer structure is copied, but not all internal values.
404 For example, copying an array produces a new array with identically-same elements as the
405 original.
406
407 See also [`copy!`](@ref Base.copy!), [`copyto!`](@ref), [`deepcopy`](@ref).
408 """
409 copy
410
411 copy(a::T) where {T<:Array} = ccall(:jl_array_copy, Ref{T}, (Any,), a)
412
413 ## Constructors ##
414
415 similar(a::Array{T,1}) where {T} = Vector{T}(undef, size(a,1))
416 similar(a::Array{T,2}) where {T} = Matrix{T}(undef, size(a,1), size(a,2))
417 similar(a::Array{T,1}, S::Type) where {T} = Vector{S}(undef, size(a,1))
418 similar(a::Array{T,2}, S::Type) where {T} = Matrix{S}(undef, size(a,1), size(a,2))
419 similar(a::Array{T}, m::Int) where {T} = Vector{T}(undef, m)
420 similar(a::Array, T::Type, dims::Dims{N}) where {N} = Array{T,N}(undef, dims)
421 similar(a::Array{T}, dims::Dims{N}) where {T,N} = Array{T,N}(undef, dims)
422
423 # T[x...] constructs Array{T,1}
424 """
425 getindex(type[, elements...])
426
427 Construct a 1-d array of the specified type. This is usually called with the syntax
428 `Type[]`. Element values can be specified using `Type[a,b,c,...]`.
429
430 # Examples
431 ```jldoctest
432 julia> Int8[1, 2, 3]
433 3-element Vector{Int8}:
434 1
435 2
436 3
437
438 julia> getindex(Int8, 1, 2, 3)
439 3-element Vector{Int8}:
440 1
441 2
442 3
443 ```
444 """
445 function getindex(::Type{T}, vals...) where T
446 @inline
447 @_effect_free_terminates_locally_meta
448 a = Vector{T}(undef, length(vals))
449 if vals isa NTuple
450 @_safeindex for i in 1:length(vals)
451 a[i] = vals[i]
452 end
453 else
454 # use afoldl to avoid type instability inside loop
455 afoldl(1, vals...) do i, v
456 @inbounds a[i] = v
457 return i + 1
458 end
459 end
460 return a
461 end
462
463 function getindex(::Type{Any}, @nospecialize vals...)
464 @_effect_free_terminates_locally_meta
465 a = Vector{Any}(undef, length(vals))
466 @_safeindex for i = 1:length(vals)
467 a[i] = vals[i]
468 end
469 return a
470 end
471 getindex(::Type{Any}) = Vector{Any}()
472
473 function fill!(a::Union{Array{UInt8}, Array{Int8}}, x::Integer)
474 t = @_gc_preserve_begin a
475 p = unsafe_convert(Ptr{Cvoid}, a)
476 memset(p, x isa eltype(a) ? x : convert(eltype(a), x), length(a))
477 @_gc_preserve_end t
478 return a
479 end
480
481 to_dim(d::Integer) = d
482 to_dim(d::OneTo) = last(d)
483
484 """
485 fill(value, dims::Tuple)
486 fill(value, dims...)
487
488 Create an array of size `dims` with every location set to `value`.
489
490 For example, `fill(1.0, (5,5))` returns a 5×5 array of floats,
491 with `1.0` in every location of the array.
492
493 The dimension lengths `dims` may be specified as either a tuple or a sequence of arguments.
494 An `N`-length tuple or `N` arguments following the `value` specify an `N`-dimensional
495 array. Thus, a common idiom for creating a zero-dimensional array with its only location
496 set to `x` is `fill(x)`.
497
498 Every location of the returned array is set to (and is thus [`===`](@ref) to)
499 the `value` that was passed; this means that if the `value` is itself modified,
500 all elements of the `fill`ed array will reflect that modification because they're
501 _still_ that very `value`. This is of no concern with `fill(1.0, (5,5))` as the
502 `value` `1.0` is immutable and cannot itself be modified, but can be unexpected
503 with mutable values like — most commonly — arrays. For example, `fill([], 3)`
504 places _the very same_ empty array in all three locations of the returned vector:
505
506 ```jldoctest
507 julia> v = fill([], 3)
508 3-element Vector{Vector{Any}}:
509 []
510 []
511 []
512
513 julia> v[1] === v[2] === v[3]
514 true
515
516 julia> value = v[1]
517 Any[]
518
519 julia> push!(value, 867_5309)
520 1-element Vector{Any}:
521 8675309
522
523 julia> v
524 3-element Vector{Vector{Any}}:
525 [8675309]
526 [8675309]
527 [8675309]
528 ```
529
530 To create an array of many independent inner arrays, use a [comprehension](@ref man-comprehensions) instead.
531 This creates a new and distinct array on each iteration of the loop:
532
533 ```jldoctest
534 julia> v2 = [[] for _ in 1:3]
535 3-element Vector{Vector{Any}}:
536 []
537 []
538 []
539
540 julia> v2[1] === v2[2] === v2[3]
541 false
542
543 julia> push!(v2[1], 8675309)
544 1-element Vector{Any}:
545 8675309
546
547 julia> v2
548 3-element Vector{Vector{Any}}:
549 [8675309]
550 []
551 []
552 ```
553
554 See also: [`fill!`](@ref), [`zeros`](@ref), [`ones`](@ref), [`similar`](@ref).
555
556 # Examples
557 ```jldoctest
558 julia> fill(1.0, (2,3))
559 2×3 Matrix{Float64}:
560 1.0 1.0 1.0
561 1.0 1.0 1.0
562
563 julia> fill(42)
564 0-dimensional Array{Int64, 0}:
565 42
566
567 julia> A = fill(zeros(2), 2) # sets both elements to the same [0.0, 0.0] vector
568 2-element Vector{Vector{Float64}}:
569 [0.0, 0.0]
570 [0.0, 0.0]
571
572 julia> A[1][1] = 42; # modifies the filled value to be [42.0, 0.0]
573
574 julia> A # both A[1] and A[2] are the very same vector
575 2-element Vector{Vector{Float64}}:
576 [42.0, 0.0]
577 [42.0, 0.0]
578 ```
579 """
580 function fill end
581
582 fill(v, dims::DimOrInd...) = fill(v, dims)
583 fill(v, dims::NTuple{N, Union{Integer, OneTo}}) where {N} = fill(v, map(to_dim, dims))
584 fill(v, dims::NTuple{N, Integer}) where {N} = (a=Array{typeof(v),N}(undef, dims); fill!(a, v); a)
585 fill(v, dims::Tuple{}) = (a=Array{typeof(v),0}(undef, dims); fill!(a, v); a)
586
587 """
588 zeros([T=Float64,] dims::Tuple)
589 zeros([T=Float64,] dims...)
590
591 Create an `Array`, with element type `T`, of all zeros with size specified by `dims`.
592 See also [`fill`](@ref), [`ones`](@ref), [`zero`](@ref).
593
594 # Examples
595 ```jldoctest
596 julia> zeros(1)
597 1-element Vector{Float64}:
598 0.0
599
600 julia> zeros(Int8, 2, 3)
601 2×3 Matrix{Int8}:
602 0 0 0
603 0 0 0
604 ```
605 """
606 function zeros end
607
608 """
609 ones([T=Float64,] dims::Tuple)
610 ones([T=Float64,] dims...)
611
612 Create an `Array`, with element type `T`, of all ones with size specified by `dims`.
613 See also [`fill`](@ref), [`zeros`](@ref).
614
615 # Examples
616 ```jldoctest
617 julia> ones(1,2)
618 1×2 Matrix{Float64}:
619 1.0 1.0
620
621 julia> ones(ComplexF64, 2, 3)
622 2×3 Matrix{ComplexF64}:
623 1.0+0.0im 1.0+0.0im 1.0+0.0im
624 1.0+0.0im 1.0+0.0im 1.0+0.0im
625 ```
626 """
627 function ones end
628
629 for (fname, felt) in ((:zeros, :zero), (:ones, :one))
630 @eval begin
631 $fname(dims::DimOrInd...) = $fname(dims)
632 $fname(::Type{T}, dims::DimOrInd...) where {T} = $fname(T, dims)
633 $fname(dims::Tuple{Vararg{DimOrInd}}) = $fname(Float64, dims)
634 $fname(::Type{T}, dims::NTuple{N, Union{Integer, OneTo}}) where {T,N} = $fname(T, map(to_dim, dims))
635 function $fname(::Type{T}, dims::NTuple{N, Integer}) where {T,N}
636 a = Array{T,N}(undef, dims)
637 fill!(a, $felt(T))
638 return a
639 end
640 function $fname(::Type{T}, dims::Tuple{}) where {T}
641 a = Array{T}(undef)
642 fill!(a, $felt(T))
643 return a
644 end
645 end
646 end
647
648 function _one(unit::T, x::AbstractMatrix) where T
649 require_one_based_indexing(x)
650 m,n = size(x)
651 m==n || throw(DimensionMismatch("multiplicative identity defined only for square matrices"))
652 # Matrix{T}(I, m, m)
653 I = zeros(T, m, m)
654 for i in 1:m
655 I[i,i] = unit
656 end
657 I
658 end
659
660 one(x::AbstractMatrix{T}) where {T} = _one(one(T), x)
661 oneunit(x::AbstractMatrix{T}) where {T} = _one(oneunit(T), x)
662
663 ## Conversions ##
664
665 convert(::Type{T}, a::AbstractArray) where {T<:Array} = a isa T ? a : T(a)::T
666
667 promote_rule(a::Type{Array{T,n}}, b::Type{Array{S,n}}) where {T,n,S} = el_same(promote_type(T,S), a, b)
668
669 ## Constructors ##
670
671 if nameof(@__MODULE__) === :Base # avoid method overwrite
672 # constructors should make copies
673 Array{T,N}(x::AbstractArray{S,N}) where {T,N,S} = copyto_axcheck!(Array{T,N}(undef, size(x)), x)
674 AbstractArray{T,N}(A::AbstractArray{S,N}) where {T,N,S} = copyto_axcheck!(similar(A,T), A)
675 end
676
677 ## copying iterators to containers
678
679 """
680 collect(element_type, collection)
681
682 Return an `Array` with the given element type of all items in a collection or iterable.
683 The result has the same shape and number of dimensions as `collection`.
684
685 # Examples
686 ```jldoctest
687 julia> collect(Float64, 1:2:5)
688 3-element Vector{Float64}:
689 1.0
690 3.0
691 5.0
692 ```
693 """
694 collect(::Type{T}, itr) where {T} = _collect(T, itr, IteratorSize(itr))
695
696 _collect(::Type{T}, itr, isz::Union{HasLength,HasShape}) where {T} =
697 copyto!(_array_for(T, isz, _similar_shape(itr, isz)), itr)
698 function _collect(::Type{T}, itr, isz::SizeUnknown) where T
699 a = Vector{T}()
700 for x in itr
701 push!(a, x)
702 end
703 return a
704 end
705
706 # make a collection similar to `c` and appropriate for collecting `itr`
707 _similar_for(c, ::Type{T}, itr, isz, shp) where {T} = similar(c, T)
708
709 _similar_shape(itr, ::SizeUnknown) = nothing
710 _similar_shape(itr, ::HasLength) = length(itr)::Integer
711 _similar_shape(itr, ::HasShape) = axes(itr)
712
713 _similar_for(c::AbstractArray, ::Type{T}, itr, ::SizeUnknown, ::Nothing) where {T} =
714 similar(c, T, 0)
715 _similar_for(c::AbstractArray, ::Type{T}, itr, ::HasLength, len::Integer) where {T} =
716 similar(c, T, len)
717 _similar_for(c::AbstractArray, ::Type{T}, itr, ::HasShape, axs) where {T} =
718 similar(c, T, axs)
719
720 # make a collection appropriate for collecting `itr::Generator`
721 _array_for(::Type{T}, ::SizeUnknown, ::Nothing) where {T} = Vector{T}(undef, 0)
722 _array_for(::Type{T}, ::HasLength, len::Integer) where {T} = Vector{T}(undef, Int(len))
723 _array_for(::Type{T}, ::HasShape{N}, axs) where {T,N} = similar(Array{T,N}, axs)
724
725 # used by syntax lowering for simple typed comprehensions
726 _array_for(::Type{T}, itr, isz) where {T} = _array_for(T, isz, _similar_shape(itr, isz))
727
728
729 """
730 collect(collection)
731
732 Return an `Array` of all items in a collection or iterator. For dictionaries, returns
733 `Vector{Pair{KeyType, ValType}}`. If the argument is array-like or is an iterator with the
734 [`HasShape`](@ref IteratorSize) trait, the result will have the same shape
735 and number of dimensions as the argument.
736
737 Used by comprehensions to turn a generator into an `Array`.
738
739 # Examples
740 ```jldoctest
741 julia> collect(1:2:13)
742 7-element Vector{Int64}:
743 1
744 3
745 5
746 7
747 9
748 11
749 13
750
751 julia> [x^2 for x in 1:8 if isodd(x)]
752 4-element Vector{Int64}:
753 1
754 9
755 25
756 49
757 ```
758 """
759 collect(itr) = _collect(1:1 #= Array =#, itr, IteratorEltype(itr), IteratorSize(itr))
760
761 collect(A::AbstractArray) = _collect_indices(axes(A), A)
762
763 collect_similar(cont, itr) = _collect(cont, itr, IteratorEltype(itr), IteratorSize(itr))
764
765 _collect(cont, itr, ::HasEltype, isz::Union{HasLength,HasShape}) =
766 copyto!(_similar_for(cont, eltype(itr), itr, isz, _similar_shape(itr, isz)), itr)
767
768 function _collect(cont, itr, ::HasEltype, isz::SizeUnknown)
769 a = _similar_for(cont, eltype(itr), itr, isz, nothing)
770 for x in itr
771 push!(a,x)
772 end
773 return a
774 end
775
776 _collect_indices(::Tuple{}, A) = copyto!(Array{eltype(A),0}(undef), A)
777 _collect_indices(indsA::Tuple{Vararg{OneTo}}, A) =
778 copyto!(Array{eltype(A)}(undef, length.(indsA)), A)
779 function _collect_indices(indsA, A)
780 B = Array{eltype(A)}(undef, length.(indsA))
781 copyto!(B, CartesianIndices(axes(B)), A, CartesianIndices(indsA))
782 end
783
784 # NOTE: this function is not meant to be called, only inferred, for the
785 # purpose of bounding the types of values generated by an iterator.
786 function _iterator_upper_bound(itr)
787 x = iterate(itr)
788 while x !== nothing
789 val = getfield(x, 1)
790 if inferencebarrier(nothing)
791 return val
792 end
793 x = iterate(itr, getfield(x, 2))
794 end
795 throw(nothing)
796 end
797
798 # define this as a macro so that the call to Core.Compiler
799 # gets inlined into the caller before recursion detection
800 # gets a chance to see it, so that recursive calls to the caller
801 # don't trigger the inference limiter
802 if isdefined(Core, :Compiler)
803 macro default_eltype(itr)
804 I = esc(itr)
805 return quote
806 if $I isa Generator && ($I).f isa Type
807 T = ($I).f
808 else
809 T = Core.Compiler.return_type(_iterator_upper_bound, Tuple{typeof($I)})
810 end
811 promote_typejoin_union(T)
812 end
813 end
814 else
815 macro default_eltype(itr)
816 I = esc(itr)
817 return quote
818 if $I isa Generator && ($I).f isa Type
819 promote_typejoin_union($I.f)
820 else
821 Any
822 end
823 end
824 end
825 end
826
827 function collect(itr::Generator)
828 isz = IteratorSize(itr.iter)
829 et = @default_eltype(itr)
830 if isa(isz, SizeUnknown)
831 return grow_to!(Vector{et}(), itr)
832 else
833 shp = _similar_shape(itr, isz)
834 y = iterate(itr)
835 if y === nothing
836 return _array_for(et, isz, shp)
837 end
838 v1, st = y
839 dest = _array_for(typeof(v1), isz, shp)
840 # The typeassert gives inference a helping hand on the element type and dimensionality
841 # (work-around for #28382)
842 et′ = et <: Type ? Type : et
843 RT = dest isa AbstractArray ? AbstractArray{<:et′, ndims(dest)} : Any
844 collect_to_with_first!(dest, v1, itr, st)::RT
845 end
846 end
847
848 _collect(c, itr, ::EltypeUnknown, isz::SizeUnknown) =
849 grow_to!(_similar_for(c, @default_eltype(itr), itr, isz, nothing), itr)
850
851 function _collect(c, itr, ::EltypeUnknown, isz::Union{HasLength,HasShape})
852 et = @default_eltype(itr)
853 shp = _similar_shape(itr, isz)
854 y = iterate(itr)
855 if y === nothing
856 return _similar_for(c, et, itr, isz, shp)
857 end
858 v1, st = y
859 dest = _similar_for(c, typeof(v1), itr, isz, shp)
860 # The typeassert gives inference a helping hand on the element type and dimensionality
861 # (work-around for #28382)
862 et′ = et <: Type ? Type : et
863 RT = dest isa AbstractArray ? AbstractArray{<:et′, ndims(dest)} : Any
864 collect_to_with_first!(dest, v1, itr, st)::RT
865 end
866
867 function collect_to_with_first!(dest::AbstractArray, v1, itr, st)
868 i1 = first(LinearIndices(dest))
869 dest[i1] = v1
870 return collect_to!(dest, itr, i1+1, st)
871 end
872
873 function collect_to_with_first!(dest, v1, itr, st)
874 push!(dest, v1)
875 return grow_to!(dest, itr, st)
876 end
877
878 function setindex_widen_up_to(dest::AbstractArray{T}, el, i) where T
879 @inline
880 new = similar(dest, promote_typejoin(T, typeof(el)))
881 f = first(LinearIndices(dest))
882 copyto!(new, first(LinearIndices(new)), dest, f, i-f)
883 @inbounds new[i] = el
884 return new
885 end
886
887 function collect_to!(dest::AbstractArray{T}, itr, offs, st) where T
888 # collect to dest array, checking the type of each result. if a result does not
889 # match, widen the result type and re-dispatch.
890 i = offs
891 while true
892 y = iterate(itr, st)
893 y === nothing && break
894 el, st = y
895 if el isa T
896 @inbounds dest[i] = el
897 i += 1
898 else
899 new = setindex_widen_up_to(dest, el, i)
900 return collect_to!(new, itr, i+1, st)
901 end
902 end
903 return dest
904 end
905
906 function grow_to!(dest, itr)
907 y = iterate(itr)
908 y === nothing && return dest
909 dest2 = empty(dest, typeof(y[1]))
910 push!(dest2, y[1])
911 grow_to!(dest2, itr, y[2])
912 end
913
914 function push_widen(dest, el)
915 @inline
916 new = sizehint!(empty(dest, promote_typejoin(eltype(dest), typeof(el))), length(dest))
917 if new isa AbstractSet
918 # TODO: merge back these two branches when copy! is re-enabled for sets/vectors
919 union!(new, dest)
920 else
921 append!(new, dest)
922 end
923 push!(new, el)
924 return new
925 end
926
927 function grow_to!(dest, itr, st)
928 T = eltype(dest)
929 y = iterate(itr, st)
930 while y !== nothing
931 el, st = y
932 if el isa T
933 push!(dest, el)
934 else
935 new = push_widen(dest, el)
936 return grow_to!(new, itr, st)
937 end
938 y = iterate(itr, st)
939 end
940 return dest
941 end
942
943 ## Iteration ##
944
945 iterate(A::Array, i=1) = (@inline; (i % UInt) - 1 < length(A) ? (@inbounds A[i], i + 1) : nothing)
946
947 ## Indexing: getindex ##
948
949 """
950 getindex(collection, key...)
951
952 Retrieve the value(s) stored at the given key or index within a collection. The syntax
953 `a[i,j,...]` is converted by the compiler to `getindex(a, i, j, ...)`.
954
955 See also [`get`](@ref), [`keys`](@ref), [`eachindex`](@ref).
956
957 # Examples
958 ```jldoctest
959 julia> A = Dict("a" => 1, "b" => 2)
960 Dict{String, Int64} with 2 entries:
961 "b" => 2
962 "a" => 1
963
964 julia> getindex(A, "a")
965 1
966 ```
967 """
968 function getindex end
969
970 # Faster contiguous indexing using copyto! for AbstractUnitRange and Colon
971 function getindex(A::Array, I::AbstractUnitRange{<:Integer})
972 @inline
973 @boundscheck checkbounds(A, I)
974 lI = length(I)
975 X = similar(A, axes(I))
976 if lI > 0
977 copyto!(X, firstindex(X), A, first(I), lI)
978 end
979 return X
980 end
981
982 # getindex for carrying out logical indexing for AbstractUnitRange{Bool} as Bool <: Integer
983 getindex(a::Array, r::AbstractUnitRange{Bool}) = getindex(a, to_index(r))
984
985 function getindex(A::Array, c::Colon)
986 lI = length(A)
987 X = similar(A, lI)
988 if lI > 0
989 unsafe_copyto!(X, 1, A, 1, lI)
990 end
991 return X
992 end
993
994 # This is redundant with the abstract fallbacks, but needed for bootstrap
995 function getindex(A::Array{S}, I::AbstractRange{Int}) where S
996 return S[ A[i] for i in I ]
997 end
998
999 ## Indexing: setindex! ##
1000
1001 """
1002 setindex!(collection, value, key...)
1003
1004 Store the given value at the given key or index within a collection. The syntax `a[i,j,...] =
1005 x` is converted by the compiler to `(setindex!(a, x, i, j, ...); x)`.
1006
1007 # Examples
1008 ```jldoctest
1009 julia> a = Dict("a"=>1)
1010 Dict{String, Int64} with 1 entry:
1011 "a" => 1
1012
1013 julia> setindex!(a, 2, "b")
1014 Dict{String, Int64} with 2 entries:
1015 "b" => 2
1016 "a" => 1
1017 ```
1018 """
1019 function setindex! end
1020
1021 1 (2 %) 1 (2 %)
1 (2 %) samples spent in setindex!
1 (100 %) (ex.), 1 (100 %) (incl.) when called from residual! line 437
@eval setindex!(A::Array{T}, x, i1::Int) where {T} =
1022 arrayset($(Expr(:boundscheck)), A, x isa T ? x : convert(T,x)::T, i1)
1023 @eval setindex!(A::Array{T}, x, i1::Int, i2::Int, I::Int...) where {T} =
1024 (@inline; arrayset($(Expr(:boundscheck)), A, x isa T ? x : convert(T,x)::T, i1, i2, I...))
1025
1026 __inbounds_setindex!(A::Array{T}, x, i1::Int) where {T} =
1027 arrayset(false, A, convert(T,x)::T, i1)
1028 __inbounds_setindex!(A::Array{T}, x, i1::Int, i2::Int, I::Int...) where {T} =
1029 (@inline; arrayset(false, A, convert(T,x)::T, i1, i2, I...))
1030
1031 # This is redundant with the abstract fallbacks but needed and helpful for bootstrap
1032 function setindex!(A::Array, X::AbstractArray, I::AbstractVector{Int})
1033 @_propagate_inbounds_meta
1034 @boundscheck setindex_shape_check(X, length(I))
1035 require_one_based_indexing(X)
1036 X′ = unalias(A, X)
1037 I′ = unalias(A, I)
1038 count = 1
1039 for i in I′
1040 @inbounds x = X′[count]
1041 A[i] = x
1042 count += 1
1043 end
1044 return A
1045 end
1046
1047 # Faster contiguous setindex! with copyto!
1048 function setindex!(A::Array{T}, X::Array{T}, I::AbstractUnitRange{Int}) where T
1049 @inline
1050 @boundscheck checkbounds(A, I)
1051 lI = length(I)
1052 @boundscheck setindex_shape_check(X, lI)
1053 if lI > 0
1054 unsafe_copyto!(A, first(I), X, 1, lI)
1055 end
1056 return A
1057 end
1058 function setindex!(A::Array{T}, X::Array{T}, c::Colon) where T
1059 @inline
1060 lI = length(A)
1061 @boundscheck setindex_shape_check(X, lI)
1062 if lI > 0
1063 unsafe_copyto!(A, 1, X, 1, lI)
1064 end
1065 return A
1066 end
1067
1068 # efficiently grow an array
1069
1070 _growbeg!(a::Vector, delta::Integer) =
1071 ccall(:jl_array_grow_beg, Cvoid, (Any, UInt), a, delta)
1072 _growend!(a::Vector, delta::Integer) =
1073 ccall(:jl_array_grow_end, Cvoid, (Any, UInt), a, delta)
1074 _growat!(a::Vector, i::Integer, delta::Integer) =
1075 ccall(:jl_array_grow_at, Cvoid, (Any, Int, UInt), a, i - 1, delta)
1076
1077 # efficiently delete part of an array
1078
1079 _deletebeg!(a::Vector, delta::Integer) =
1080 ccall(:jl_array_del_beg, Cvoid, (Any, UInt), a, delta)
1081 _deleteend!(a::Vector, delta::Integer) =
1082 ccall(:jl_array_del_end, Cvoid, (Any, UInt), a, delta)
1083 _deleteat!(a::Vector, i::Integer, delta::Integer) =
1084 ccall(:jl_array_del_at, Cvoid, (Any, Int, UInt), a, i - 1, delta)
1085
1086 ## Dequeue functionality ##
1087
1088 """
1089 push!(collection, items...) -> collection
1090
1091 Insert one or more `items` in `collection`. If `collection` is an ordered container,
1092 the items are inserted at the end (in the given order).
1093
1094 # Examples
1095 ```jldoctest
1096 julia> push!([1, 2, 3], 4, 5, 6)
1097 6-element Vector{Int64}:
1098 1
1099 2
1100 3
1101 4
1102 5
1103 6
1104 ```
1105
1106 If `collection` is ordered, use [`append!`](@ref) to add all the elements of another
1107 collection to it. The result of the preceding example is equivalent to `append!([1, 2, 3], [4,
1108 5, 6])`. For `AbstractSet` objects, [`union!`](@ref) can be used instead.
1109
1110 See [`sizehint!`](@ref) for notes about the performance model.
1111
1112 See also [`pushfirst!`](@ref).
1113 """
1114 function push! end
1115
1116 function push!(a::Vector{T}, item) where T
1117 # convert first so we don't grow the array if the assignment won't work
1118 itemT = item isa T ? item : convert(T, item)::T
1119 _growend!(a, 1)
1120 @_safeindex a[length(a)] = itemT
1121 return a
1122 end
1123
1124 # specialize and optimize the single argument case
1125 function push!(a::Vector{Any}, @nospecialize x)
1126 _growend!(a, 1)
1127 @_safeindex a[length(a)] = x
1128 return a
1129 end
1130 function push!(a::Vector{Any}, @nospecialize x...)
1131 @_terminates_locally_meta
1132 na = length(a)
1133 nx = length(x)
1134 _growend!(a, nx)
1135 @_safeindex for i = 1:nx
1136 a[na+i] = x[i]
1137 end
1138 return a
1139 end
1140
1141 """
1142 append!(collection, collections...) -> collection.
1143
1144 For an ordered container `collection`, add the elements of each `collections`
1145 to the end of it.
1146
1147 !!! compat "Julia 1.6"
1148 Specifying multiple collections to be appended requires at least Julia 1.6.
1149
1150 # Examples
1151 ```jldoctest
1152 julia> append!([1], [2, 3])
1153 3-element Vector{Int64}:
1154 1
1155 2
1156 3
1157
1158 julia> append!([1, 2, 3], [4, 5], [6])
1159 6-element Vector{Int64}:
1160 1
1161 2
1162 3
1163 4
1164 5
1165 6
1166 ```
1167
1168 Use [`push!`](@ref) to add individual items to `collection` which are not already
1169 themselves in another collection. The result of the preceding example is equivalent to
1170 `push!([1, 2, 3], 4, 5, 6)`.
1171
1172 See [`sizehint!`](@ref) for notes about the performance model.
1173
1174 See also [`vcat`](@ref) for vectors, [`union!`](@ref) for sets,
1175 and [`prepend!`](@ref) and [`pushfirst!`](@ref) for the opposite order.
1176 """
1177 function append! end
1178
1179 function append!(a::Vector, items::AbstractVector)
1180 itemindices = eachindex(items)
1181 n = length(itemindices)
1182 _growend!(a, n)
1183 copyto!(a, length(a)-n+1, items, first(itemindices), n)
1184 return a
1185 end
1186
1187 append!(a::AbstractVector, iter) = _append!(a, IteratorSize(iter), iter)
1188 push!(a::AbstractVector, iter...) = append!(a, iter)
1189
1190 append!(a::AbstractVector, iter...) = foldl(append!, iter, init=a)
1191
1192 function _append!(a::AbstractVector, ::Union{HasLength,HasShape}, iter)
1193 @_terminates_locally_meta
1194 n = length(a)
1195 i = lastindex(a)
1196 resize!(a, n+Int(length(iter))::Int)
1197 for (i, item) in zip(i+1:lastindex(a), iter)
1198 if isa(a, Vector) # give better effects for builtin vectors
1199 @_safeindex a[i] = item
1200 else
1201 a[i] = item
1202 end
1203 end
1204 a
1205 end
1206 function _append!(a::AbstractVector, ::IteratorSize, iter)
1207 for item in iter
1208 push!(a, item)
1209 end
1210 a
1211 end
1212
1213 """
1214 prepend!(a::Vector, collections...) -> collection
1215
1216 Insert the elements of each `collections` to the beginning of `a`.
1217
1218 When `collections` specifies multiple collections, order is maintained:
1219 elements of `collections[1]` will appear leftmost in `a`, and so on.
1220
1221 !!! compat "Julia 1.6"
1222 Specifying multiple collections to be prepended requires at least Julia 1.6.
1223
1224 # Examples
1225 ```jldoctest
1226 julia> prepend!([3], [1, 2])
1227 3-element Vector{Int64}:
1228 1
1229 2
1230 3
1231
1232 julia> prepend!([6], [1, 2], [3, 4, 5])
1233 6-element Vector{Int64}:
1234 1
1235 2
1236 3
1237 4
1238 5
1239 6
1240 ```
1241 """
1242 function prepend! end
1243
1244 function prepend!(a::Vector, items::AbstractVector)
1245 itemindices = eachindex(items)
1246 n = length(itemindices)
1247 _growbeg!(a, n)
1248 if a === items
1249 copyto!(a, 1, items, n+1, n)
1250 else
1251 copyto!(a, 1, items, first(itemindices), n)
1252 end
1253 return a
1254 end
1255
1256 prepend!(a::Vector, iter) = _prepend!(a, IteratorSize(iter), iter)
1257 pushfirst!(a::Vector, iter...) = prepend!(a, iter)
1258
1259 prepend!(a::AbstractVector, iter...) = foldr((v, a) -> prepend!(a, v), iter, init=a)
1260
1261 function _prepend!(a::Vector, ::Union{HasLength,HasShape}, iter)
1262 @_terminates_locally_meta
1263 require_one_based_indexing(a)
1264 n = length(iter)
1265 _growbeg!(a, n)
1266 i = 0
1267 for item in iter
1268 @_safeindex a[i += 1] = item
1269 end
1270 a
1271 end
1272 function _prepend!(a::Vector, ::IteratorSize, iter)
1273 n = 0
1274 for item in iter
1275 n += 1
1276 pushfirst!(a, item)
1277 end
1278 reverse!(a, 1, n)
1279 a
1280 end
1281
1282 """
1283 resize!(a::Vector, n::Integer) -> Vector
1284
1285 Resize `a` to contain `n` elements. If `n` is smaller than the current collection
1286 length, the first `n` elements will be retained. If `n` is larger, the new elements are not
1287 guaranteed to be initialized.
1288
1289 # Examples
1290 ```jldoctest
1291 julia> resize!([6, 5, 4, 3, 2, 1], 3)
1292 3-element Vector{Int64}:
1293 6
1294 5
1295 4
1296
1297 julia> a = resize!([6, 5, 4, 3, 2, 1], 8);
1298
1299 julia> length(a)
1300 8
1301
1302 julia> a[1:6]
1303 6-element Vector{Int64}:
1304 6
1305 5
1306 4
1307 3
1308 2
1309 1
1310 ```
1311 """
1312 function resize!(a::Vector, nl::Integer)
1313 l = length(a)
1314 if nl > l
1315 _growend!(a, nl-l)
1316 elseif nl != l
1317 if nl < 0
1318 _throw_argerror("new length must be ≥ 0")
1319 end
1320 _deleteend!(a, l-nl)
1321 end
1322 return a
1323 end
1324
1325 """
1326 sizehint!(s, n) -> s
1327
1328 Suggest that collection `s` reserve capacity for at least `n` elements. That is, if
1329 you expect that you're going to have to push a lot of values onto `s`, you can avoid
1330 the cost of incremental reallocation by doing it once up front; this can improve
1331 performance.
1332
1333 See also [`resize!`](@ref).
1334
1335 # Notes on the performance model
1336
1337 For types that support `sizehint!`,
1338
1339 1. `push!` and `append!` methods generally may (but are not required to) preallocate extra
1340 storage. For types implemented in `Base`, they typically do, using a heuristic optimized for
1341 a general use case.
1342
1343 2. `sizehint!` may control this preallocation. Again, it typically does this for types in
1344 `Base`.
1345
1346 3. `empty!` is nearly costless (and O(1)) for types that support this kind of preallocation.
1347 """
1348 function sizehint! end
1349
1350 function sizehint!(a::Vector, sz::Integer)
1351 ccall(:jl_array_sizehint, Cvoid, (Any, UInt), a, sz)
1352 a
1353 end
1354
1355 """
1356 pop!(collection) -> item
1357
1358 Remove an item in `collection` and return it. If `collection` is an
1359 ordered container, the last item is returned; for unordered containers,
1360 an arbitrary element is returned.
1361
1362 See also: [`popfirst!`](@ref), [`popat!`](@ref), [`delete!`](@ref), [`deleteat!`](@ref), [`splice!`](@ref), and [`push!`](@ref).
1363
1364 # Examples
1365 ```jldoctest
1366 julia> A=[1, 2, 3]
1367 3-element Vector{Int64}:
1368 1
1369 2
1370 3
1371
1372 julia> pop!(A)
1373 3
1374
1375 julia> A
1376 2-element Vector{Int64}:
1377 1
1378 2
1379
1380 julia> S = Set([1, 2])
1381 Set{Int64} with 2 elements:
1382 2
1383 1
1384
1385 julia> pop!(S)
1386 2
1387
1388 julia> S
1389 Set{Int64} with 1 element:
1390 1
1391
1392 julia> pop!(Dict(1=>2))
1393 1 => 2
1394 ```
1395 """
1396 function pop!(a::Vector)
1397 if isempty(a)
1398 _throw_argerror("array must be non-empty")
1399 end
1400 item = a[end]
1401 _deleteend!(a, 1)
1402 return item
1403 end
1404
1405 """
1406 popat!(a::Vector, i::Integer, [default])
1407
1408 Remove the item at the given `i` and return it. Subsequent items
1409 are shifted to fill the resulting gap.
1410 When `i` is not a valid index for `a`, return `default`, or throw an error if
1411 `default` is not specified.
1412
1413 See also: [`pop!`](@ref), [`popfirst!`](@ref), [`deleteat!`](@ref), [`splice!`](@ref).
1414
1415 !!! compat "Julia 1.5"
1416 This function is available as of Julia 1.5.
1417
1418 # Examples
1419 ```jldoctest
1420 julia> a = [4, 3, 2, 1]; popat!(a, 2)
1421 3
1422
1423 julia> a
1424 3-element Vector{Int64}:
1425 4
1426 2
1427 1
1428
1429 julia> popat!(a, 4, missing)
1430 missing
1431
1432 julia> popat!(a, 4)
1433 ERROR: BoundsError: attempt to access 3-element Vector{Int64} at index [4]
1434 [...]
1435 ```
1436 """
1437 function popat!(a::Vector, i::Integer)
1438 x = a[i]
1439 _deleteat!(a, i, 1)
1440 x
1441 end
1442
1443 function popat!(a::Vector, i::Integer, default)
1444 if 1 <= i <= length(a)
1445 x = @inbounds a[i]
1446 _deleteat!(a, i, 1)
1447 x
1448 else
1449 default
1450 end
1451 end
1452
1453 """
1454 pushfirst!(collection, items...) -> collection
1455
1456 Insert one or more `items` at the beginning of `collection`.
1457
1458 This function is called `unshift` in many other programming languages.
1459
1460 # Examples
1461 ```jldoctest
1462 julia> pushfirst!([1, 2, 3, 4], 5, 6)
1463 6-element Vector{Int64}:
1464 5
1465 6
1466 1
1467 2
1468 3
1469 4
1470 ```
1471 """
1472 function pushfirst!(a::Vector{T}, item) where T
1473 item = item isa T ? item : convert(T, item)::T
1474 _growbeg!(a, 1)
1475 @_safeindex a[1] = item
1476 return a
1477 end
1478
1479 # specialize and optimize the single argument case
1480 function pushfirst!(a::Vector{Any}, @nospecialize x)
1481 _growbeg!(a, 1)
1482 @_safeindex a[1] = x
1483 return a
1484 end
1485 function pushfirst!(a::Vector{Any}, @nospecialize x...)
1486 @_terminates_locally_meta
1487 na = length(a)
1488 nx = length(x)
1489 _growbeg!(a, nx)
1490 @_safeindex for i = 1:nx
1491 a[i] = x[i]
1492 end
1493 return a
1494 end
1495
1496 """
1497 popfirst!(collection) -> item
1498
1499 Remove the first `item` from `collection`.
1500
1501 This function is called `shift` in many other programming languages.
1502
1503 See also: [`pop!`](@ref), [`popat!`](@ref), [`delete!`](@ref).
1504
1505 # Examples
1506 ```jldoctest
1507 julia> A = [1, 2, 3, 4, 5, 6]
1508 6-element Vector{Int64}:
1509 1
1510 2
1511 3
1512 4
1513 5
1514 6
1515
1516 julia> popfirst!(A)
1517 1
1518
1519 julia> A
1520 5-element Vector{Int64}:
1521 2
1522 3
1523 4
1524 5
1525 6
1526 ```
1527 """
1528 function popfirst!(a::Vector)
1529 if isempty(a)
1530 _throw_argerror("array must be non-empty")
1531 end
1532 item = a[1]
1533 _deletebeg!(a, 1)
1534 return item
1535 end
1536
1537 """
1538 insert!(a::Vector, index::Integer, item)
1539
1540 Insert an `item` into `a` at the given `index`. `index` is the index of `item` in
1541 the resulting `a`.
1542
1543 See also: [`push!`](@ref), [`replace`](@ref), [`popat!`](@ref), [`splice!`](@ref).
1544
1545 # Examples
1546 ```jldoctest
1547 julia> insert!(Any[1:6;], 3, "here")
1548 7-element Vector{Any}:
1549 1
1550 2
1551 "here"
1552 3
1553 4
1554 5
1555 6
1556 ```
1557 """
1558 function insert!(a::Array{T,1}, i::Integer, item) where T
1559 # Throw convert error before changing the shape of the array
1560 _item = item isa T ? item : convert(T, item)::T
1561 _growat!(a, i, 1)
1562 # _growat! already did bound check
1563 @inbounds a[i] = _item
1564 return a
1565 end
1566
1567 """
1568 deleteat!(a::Vector, i::Integer)
1569
1570 Remove the item at the given `i` and return the modified `a`. Subsequent items
1571 are shifted to fill the resulting gap.
1572
1573 See also: [`keepat!`](@ref), [`delete!`](@ref), [`popat!`](@ref), [`splice!`](@ref).
1574
1575 # Examples
1576 ```jldoctest
1577 julia> deleteat!([6, 5, 4, 3, 2, 1], 2)
1578 5-element Vector{Int64}:
1579 6
1580 4
1581 3
1582 2
1583 1
1584 ```
1585 """
1586 function deleteat!(a::Vector, i::Integer)
1587 i isa Bool && depwarn("passing Bool as an index is deprecated", :deleteat!)
1588 _deleteat!(a, i, 1)
1589 return a
1590 end
1591
1592 function deleteat!(a::Vector, r::AbstractUnitRange{<:Integer})
1593 if eltype(r) === Bool
1594 return invoke(deleteat!, Tuple{Vector, AbstractVector{Bool}}, a, r)
1595 else
1596 n = length(a)
1597 f = first(r)
1598 f isa Bool && depwarn("passing Bool as an index is deprecated", :deleteat!)
1599 isempty(r) || _deleteat!(a, f, length(r))
1600 return a
1601 end
1602 end
1603
1604 """
1605 deleteat!(a::Vector, inds)
1606
1607 Remove the items at the indices given by `inds`, and return the modified `a`.
1608 Subsequent items are shifted to fill the resulting gap.
1609
1610 `inds` can be either an iterator or a collection of sorted and unique integer indices,
1611 or a boolean vector of the same length as `a` with `true` indicating entries to delete.
1612
1613 # Examples
1614 ```jldoctest
1615 julia> deleteat!([6, 5, 4, 3, 2, 1], 1:2:5)
1616 3-element Vector{Int64}:
1617 5
1618 3
1619 1
1620
1621 julia> deleteat!([6, 5, 4, 3, 2, 1], [true, false, true, false, true, false])
1622 3-element Vector{Int64}:
1623 5
1624 3
1625 1
1626
1627 julia> deleteat!([6, 5, 4, 3, 2, 1], (2, 2))
1628 ERROR: ArgumentError: indices must be unique and sorted
1629 Stacktrace:
1630 [...]
1631 ```
1632 """
1633 deleteat!(a::Vector, inds) = _deleteat!(a, inds)
1634 deleteat!(a::Vector, inds::AbstractVector) = _deleteat!(a, to_indices(a, (inds,))[1])
1635
1636 struct Nowhere; end
1637 push!(::Nowhere, _) = nothing
1638 _growend!(::Nowhere, _) = nothing
1639
1640 @inline function _push_deleted!(dltd, a::Vector, ind)
1641 if @inbounds isassigned(a, ind)
1642 push!(dltd, @inbounds a[ind])
1643 else
1644 _growend!(dltd, 1)
1645 end
1646 end
1647
1648 @inline function _copy_item!(a::Vector, p, q)
1649 if @inbounds isassigned(a, q)
1650 @inbounds a[p] = a[q]
1651 else
1652 _unsetindex!(a, p)
1653 end
1654 end
1655
1656 function _deleteat!(a::Vector, inds, dltd=Nowhere())
1657 n = length(a)
1658 y = iterate(inds)
1659 y === nothing && return a
1660 (p, s) = y
1661 checkbounds(a, p)
1662 _push_deleted!(dltd, a, p)
1663 q = p+1
1664 while true
1665 y = iterate(inds, s)
1666 y === nothing && break
1667 (i,s) = y
1668 if !(q <= i <= n)
1669 if i < q
1670 _throw_argerror("indices must be unique and sorted")
1671 else
1672 throw(BoundsError())
1673 end
1674 end
1675 while q < i
1676 _copy_item!(a, p, q)
1677 p += 1; q += 1
1678 end
1679 _push_deleted!(dltd, a, i)
1680 q = i+1
1681 end
1682 while q <= n
1683 _copy_item!(a, p, q)
1684 p += 1; q += 1
1685 end
1686 _deleteend!(a, n-p+1)
1687 return a
1688 end
1689
1690 # Simpler and more efficient version for logical indexing
1691 function deleteat!(a::Vector, inds::AbstractVector{Bool})
1692 n = length(a)
1693 length(inds) == n || throw(BoundsError(a, inds))
1694 p = 1
1695 for (q, i) in enumerate(inds)
1696 _copy_item!(a, p, q)
1697 p += !i
1698 end
1699 _deleteend!(a, n-p+1)
1700 return a
1701 end
1702
1703 const _default_splice = []
1704
1705 """
1706 splice!(a::Vector, index::Integer, [replacement]) -> item
1707
1708 Remove the item at the given index, and return the removed item.
1709 Subsequent items are shifted left to fill the resulting gap.
1710 If specified, replacement values from an ordered
1711 collection will be spliced in place of the removed item.
1712
1713 See also: [`replace`](@ref), [`delete!`](@ref), [`deleteat!`](@ref), [`pop!`](@ref), [`popat!`](@ref).
1714
1715 # Examples
1716 ```jldoctest
1717 julia> A = [6, 5, 4, 3, 2, 1]; splice!(A, 5)
1718 2
1719
1720 julia> A
1721 5-element Vector{Int64}:
1722 6
1723 5
1724 4
1725 3
1726 1
1727
1728 julia> splice!(A, 5, -1)
1729 1
1730
1731 julia> A
1732 5-element Vector{Int64}:
1733 6
1734 5
1735 4
1736 3
1737 -1
1738
1739 julia> splice!(A, 1, [-1, -2, -3])
1740 6
1741
1742 julia> A
1743 7-element Vector{Int64}:
1744 -1
1745 -2
1746 -3
1747 5
1748 4
1749 3
1750 -1
1751 ```
1752
1753 To insert `replacement` before an index `n` without removing any items, use
1754 `splice!(collection, n:n-1, replacement)`.
1755 """
1756 function splice!(a::Vector, i::Integer, ins=_default_splice)
1757 v = a[i]
1758 m = length(ins)
1759 if m == 0
1760 _deleteat!(a, i, 1)
1761 elseif m == 1
1762 a[i] = ins[1]
1763 else
1764 _growat!(a, i, m-1)
1765 k = 1
1766 for x in ins
1767 a[i+k-1] = x
1768 k += 1
1769 end
1770 end
1771 return v
1772 end
1773
1774 """
1775 splice!(a::Vector, indices, [replacement]) -> items
1776
1777 Remove items at specified indices, and return a collection containing
1778 the removed items.
1779 Subsequent items are shifted left to fill the resulting gaps.
1780 If specified, replacement values from an ordered collection will be spliced in
1781 place of the removed items; in this case, `indices` must be a `AbstractUnitRange`.
1782
1783 To insert `replacement` before an index `n` without removing any items, use
1784 `splice!(collection, n:n-1, replacement)`.
1785
1786 $(_DOCS_ALIASING_WARNING)
1787
1788 !!! compat "Julia 1.5"
1789 Prior to Julia 1.5, `indices` must always be a `UnitRange`.
1790
1791 !!! compat "Julia 1.8"
1792 Prior to Julia 1.8, `indices` must be a `UnitRange` if splicing in replacement values.
1793
1794 # Examples
1795 ```jldoctest
1796 julia> A = [-1, -2, -3, 5, 4, 3, -1]; splice!(A, 4:3, 2)
1797 Int64[]
1798
1799 julia> A
1800 8-element Vector{Int64}:
1801 -1
1802 -2
1803 -3
1804 2
1805 5
1806 4
1807 3
1808 -1
1809 ```
1810 """
1811 function splice!(a::Vector, r::AbstractUnitRange{<:Integer}, ins=_default_splice)
1812 v = a[r]
1813 m = length(ins)
1814 if m == 0
1815 deleteat!(a, r)
1816 return v
1817 end
1818
1819 n = length(a)
1820 f = first(r)
1821 l = last(r)
1822 d = length(r)
1823
1824 if m < d
1825 delta = d - m
1826 _deleteat!(a, (f - 1 < n - l) ? f : (l - delta + 1), delta)
1827 elseif m > d
1828 _growat!(a, (f - 1 < n - l) ? f : (l + 1), m - d)
1829 end
1830
1831 k = 1
1832 for x in ins
1833 a[f+k-1] = x
1834 k += 1
1835 end
1836 return v
1837 end
1838
1839 splice!(a::Vector, inds) = (dltds = eltype(a)[]; _deleteat!(a, inds, dltds); dltds)
1840
1841 function empty!(a::Vector)
1842 _deleteend!(a, length(a))
1843 return a
1844 end
1845
1846 # use memcmp for cmp on byte arrays
1847 function cmp(a::Array{UInt8,1}, b::Array{UInt8,1})
1848 ta = @_gc_preserve_begin a
1849 tb = @_gc_preserve_begin b
1850 pa = unsafe_convert(Ptr{Cvoid}, a)
1851 pb = unsafe_convert(Ptr{Cvoid}, b)
1852 c = memcmp(pa, pb, min(length(a),length(b)))
1853 @_gc_preserve_end ta
1854 @_gc_preserve_end tb
1855 return c < 0 ? -1 : c > 0 ? +1 : cmp(length(a),length(b))
1856 end
1857
1858 const BitIntegerArray{N} = Union{map(T->Array{T,N}, BitInteger_types)...} where N
1859 # use memcmp for == on bit integer types
1860 function ==(a::Arr, b::Arr) where {Arr <: BitIntegerArray}
1861 if size(a) == size(b)
1862 ta = @_gc_preserve_begin a
1863 tb = @_gc_preserve_begin b
1864 pa = unsafe_convert(Ptr{Cvoid}, a)
1865 pb = unsafe_convert(Ptr{Cvoid}, b)
1866 c = memcmp(pa, pb, sizeof(eltype(Arr)) * length(a))
1867 @_gc_preserve_end ta
1868 @_gc_preserve_end tb
1869 return c == 0
1870 else
1871 return false
1872 end
1873 end
1874
1875 function ==(a::Arr, b::Arr) where Arr <: BitIntegerArray{1}
1876 len = length(a)
1877 if len == length(b)
1878 ta = @_gc_preserve_begin a
1879 tb = @_gc_preserve_begin b
1880 T = eltype(Arr)
1881 pa = unsafe_convert(Ptr{T}, a)
1882 pb = unsafe_convert(Ptr{T}, b)
1883 c = memcmp(pa, pb, sizeof(T) * len)
1884 @_gc_preserve_end ta
1885 @_gc_preserve_end tb
1886 return c == 0
1887 else
1888 return false
1889 end
1890 end
1891
1892 """
1893 reverse(v [, start=firstindex(v) [, stop=lastindex(v) ]] )
1894
1895 Return a copy of `v` reversed from start to stop. See also [`Iterators.reverse`](@ref)
1896 for reverse-order iteration without making a copy, and in-place [`reverse!`](@ref).
1897
1898 # Examples
1899 ```jldoctest
1900 julia> A = Vector(1:5)
1901 5-element Vector{Int64}:
1902 1
1903 2
1904 3
1905 4
1906 5
1907
1908 julia> reverse(A)
1909 5-element Vector{Int64}:
1910 5
1911 4
1912 3
1913 2
1914 1
1915
1916 julia> reverse(A, 1, 4)
1917 5-element Vector{Int64}:
1918 4
1919 3
1920 2
1921 1
1922 5
1923
1924 julia> reverse(A, 3, 5)
1925 5-element Vector{Int64}:
1926 1
1927 2
1928 5
1929 4
1930 3
1931 ```
1932 """
1933 function reverse(A::AbstractVector, start::Integer, stop::Integer=lastindex(A))
1934 s, n = Int(start), Int(stop)
1935 B = similar(A)
1936 for i = firstindex(A):s-1
1937 B[i] = A[i]
1938 end
1939 for i = s:n
1940 B[i] = A[n+s-i]
1941 end
1942 for i = n+1:lastindex(A)
1943 B[i] = A[i]
1944 end
1945 return B
1946 end
1947
1948 # 1d special cases of reverse(A; dims) and reverse!(A; dims):
1949 for (f,_f) in ((:reverse,:_reverse), (:reverse!,:_reverse!))
1950 @eval begin
1951 $f(A::AbstractVector; dims=:) = $_f(A, dims)
1952 $_f(A::AbstractVector, ::Colon) = $f(A, firstindex(A), lastindex(A))
1953 $_f(A::AbstractVector, dim::Tuple{Integer}) = $_f(A, first(dim))
1954 function $_f(A::AbstractVector, dim::Integer)
1955 dim == 1 || _throw_argerror(LazyString("invalid dimension ", dim, " ≠ 1"))
1956 return $_f(A, :)
1957 end
1958 end
1959 end
1960
1961 function reverseind(a::AbstractVector, i::Integer)
1962 li = LinearIndices(a)
1963 first(li) + last(li) - i
1964 end
1965
1966 # This implementation of `midpoint` is performance-optimized but safe
1967 # only if `lo <= hi`.
1968 midpoint(lo::T, hi::T) where T<:Integer = lo + ((hi - lo) >>> 0x01)
1969 midpoint(lo::Integer, hi::Integer) = midpoint(promote(lo, hi)...)
1970
1971 """
1972 reverse!(v [, start=firstindex(v) [, stop=lastindex(v) ]]) -> v
1973
1974 In-place version of [`reverse`](@ref).
1975
1976 # Examples
1977 ```jldoctest
1978 julia> A = Vector(1:5)
1979 5-element Vector{Int64}:
1980 1
1981 2
1982 3
1983 4
1984 5
1985
1986 julia> reverse!(A);
1987
1988 julia> A
1989 5-element Vector{Int64}:
1990 5
1991 4
1992 3
1993 2
1994 1
1995 ```
1996 """
1997 function reverse!(v::AbstractVector, start::Integer, stop::Integer=lastindex(v))
1998 s, n = Int(start), Int(stop)
1999 if n > s # non-empty and non-trivial
2000 liv = LinearIndices(v)
2001 if !(first(liv) ≤ s ≤ last(liv))
2002 throw(BoundsError(v, s))
2003 elseif !(first(liv) ≤ n ≤ last(liv))
2004 throw(BoundsError(v, n))
2005 end
2006 r = n
2007 @inbounds for i in s:midpoint(s, n-1)
2008 v[i], v[r] = v[r], v[i]
2009 r -= 1
2010 end
2011 end
2012 return v
2013 end
2014
2015 # concatenations of (in)homogeneous combinations of vectors, horizontal and vertical
2016
2017 vcat() = Vector{Any}()
2018 hcat() = Vector{Any}()
2019
2020 function hcat(V::Vector{T}...) where T
2021 height = length(V[1])
2022 for j = 2:length(V)
2023 if length(V[j]) != height
2024 throw(DimensionMismatch("vectors must have same lengths"))
2025 end
2026 end
2027 return [ V[j][i]::T for i=1:length(V[1]), j=1:length(V) ]
2028 end
2029 hcat(A::Vector...) = cat(A...; dims=Val(2)) # more special than SparseArrays's hcat
2030
2031 function vcat(arrays::Vector{T}...) where T
2032 n = 0
2033 for a in arrays
2034 n += length(a)
2035 end
2036 arr = Vector{T}(undef, n)
2037 nd = 1
2038 for a in arrays
2039 na = length(a)
2040 @assert nd + na <= 1 + length(arr) # Concurrent modification of arrays?
2041 unsafe_copyto!(arr, nd, a, 1, na)
2042 nd += na
2043 end
2044 return arr
2045 end
2046 vcat(A::Vector...) = cat(A...; dims=Val(1)) # more special than SparseArrays's vcat
2047
2048 _cat(n::Integer, x::Integer...) = reshape([x...], (ntuple(Returns(1), n-1)..., length(x)))
2049
2050 ## find ##
2051
2052 """
2053 findnext(A, i)
2054
2055 Find the next index after or including `i` of a `true` element of `A`,
2056 or `nothing` if not found.
2057
2058 Indices are of the same type as those returned by [`keys(A)`](@ref)
2059 and [`pairs(A)`](@ref).
2060
2061 # Examples
2062 ```jldoctest
2063 julia> A = [false, false, true, false]
2064 4-element Vector{Bool}:
2065 0
2066 0
2067 1
2068 0
2069
2070 julia> findnext(A, 1)
2071 3
2072
2073 julia> findnext(A, 4) # returns nothing, but not printed in the REPL
2074
2075 julia> A = [false false; true false]
2076 2×2 Matrix{Bool}:
2077 0 0
2078 1 0
2079
2080 julia> findnext(A, CartesianIndex(1, 1))
2081 CartesianIndex(2, 1)
2082 ```
2083 """
2084 findnext(A, start) = findnext(identity, A, start)
2085
2086 """
2087 findfirst(A)
2088
2089 Return the index or key of the first `true` value in `A`.
2090 Return `nothing` if no such value is found.
2091 To search for other kinds of values, pass a predicate as the first argument.
2092
2093 Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
2094 and [`pairs(A)`](@ref).
2095
2096 See also: [`findall`](@ref), [`findnext`](@ref), [`findlast`](@ref), [`searchsortedfirst`](@ref).
2097
2098 # Examples
2099 ```jldoctest
2100 julia> A = [false, false, true, false]
2101 4-element Vector{Bool}:
2102 0
2103 0
2104 1
2105 0
2106
2107 julia> findfirst(A)
2108 3
2109
2110 julia> findfirst(falses(3)) # returns nothing, but not printed in the REPL
2111
2112 julia> A = [false false; true false]
2113 2×2 Matrix{Bool}:
2114 0 0
2115 1 0
2116
2117 julia> findfirst(A)
2118 CartesianIndex(2, 1)
2119 ```
2120 """
2121 findfirst(A) = findfirst(identity, A)
2122
2123 # Needed for bootstrap, and allows defining only an optimized findnext method
2124 findfirst(A::AbstractArray) = findnext(A, first(keys(A)))
2125
2126 """
2127 findnext(predicate::Function, A, i)
2128
2129 Find the next index after or including `i` of an element of `A`
2130 for which `predicate` returns `true`, or `nothing` if not found.
2131
2132 Indices are of the same type as those returned by [`keys(A)`](@ref)
2133 and [`pairs(A)`](@ref).
2134
2135 # Examples
2136 ```jldoctest
2137 julia> A = [1, 4, 2, 2];
2138
2139 julia> findnext(isodd, A, 1)
2140 1
2141
2142 julia> findnext(isodd, A, 2) # returns nothing, but not printed in the REPL
2143
2144 julia> A = [1 4; 2 2];
2145
2146 julia> findnext(isodd, A, CartesianIndex(1, 1))
2147 CartesianIndex(1, 1)
2148 ```
2149 """
2150 function findnext(testf::Function, A, start)
2151 i = oftype(first(keys(A)), start)
2152 l = last(keys(A))
2153 i > l && return nothing
2154 while true
2155 testf(A[i]) && return i
2156 i == l && break
2157 # nextind(A, l) can throw/overflow
2158 i = nextind(A, i)
2159 end
2160 return nothing
2161 end
2162
2163 """
2164 findfirst(predicate::Function, A)
2165
2166 Return the index or key of the first element of `A` for which `predicate` returns `true`.
2167 Return `nothing` if there is no such element.
2168
2169 Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
2170 and [`pairs(A)`](@ref).
2171
2172 # Examples
2173 ```jldoctest
2174 julia> A = [1, 4, 2, 2]
2175 4-element Vector{Int64}:
2176 1
2177 4
2178 2
2179 2
2180
2181 julia> findfirst(iseven, A)
2182 2
2183
2184 julia> findfirst(x -> x>10, A) # returns nothing, but not printed in the REPL
2185
2186 julia> findfirst(isequal(4), A)
2187 2
2188
2189 julia> A = [1 4; 2 2]
2190 2×2 Matrix{Int64}:
2191 1 4
2192 2 2
2193
2194 julia> findfirst(iseven, A)
2195 CartesianIndex(2, 1)
2196 ```
2197 """
2198 function findfirst(testf::Function, A)
2199 for (i, a) in pairs(A)
2200 testf(a) && return i
2201 end
2202 return nothing
2203 end
2204
2205 # Needed for bootstrap, and allows defining only an optimized findnext method
2206 findfirst(testf::Function, A::Union{AbstractArray, AbstractString}) =
2207 findnext(testf, A, first(keys(A)))
2208
2209 findfirst(p::Union{Fix2{typeof(isequal),Int},Fix2{typeof(==),Int}}, r::OneTo{Int}) =
2210 1 <= p.x <= r.stop ? p.x : nothing
2211
2212 findfirst(p::Union{Fix2{typeof(isequal),T},Fix2{typeof(==),T}}, r::AbstractUnitRange) where {T<:Integer} =
2213 first(r) <= p.x <= last(r) ? firstindex(r) + Int(p.x - first(r)) : nothing
2214
2215 function findfirst(p::Union{Fix2{typeof(isequal),T},Fix2{typeof(==),T}}, r::StepRange{T,S}) where {T,S}
2216 isempty(r) && return nothing
2217 minimum(r) <= p.x <= maximum(r) || return nothing
2218 d = convert(S, p.x - first(r))::S
2219 iszero(d % step(r)) || return nothing
2220 return d ÷ step(r) + 1
2221 end
2222
2223 """
2224 findprev(A, i)
2225
2226 Find the previous index before or including `i` of a `true` element of `A`,
2227 or `nothing` if not found.
2228
2229 Indices are of the same type as those returned by [`keys(A)`](@ref)
2230 and [`pairs(A)`](@ref).
2231
2232 See also: [`findnext`](@ref), [`findfirst`](@ref), [`findall`](@ref).
2233
2234 # Examples
2235 ```jldoctest
2236 julia> A = [false, false, true, true]
2237 4-element Vector{Bool}:
2238 0
2239 0
2240 1
2241 1
2242
2243 julia> findprev(A, 3)
2244 3
2245
2246 julia> findprev(A, 1) # returns nothing, but not printed in the REPL
2247
2248 julia> A = [false false; true true]
2249 2×2 Matrix{Bool}:
2250 0 0
2251 1 1
2252
2253 julia> findprev(A, CartesianIndex(2, 1))
2254 CartesianIndex(2, 1)
2255 ```
2256 """
2257 findprev(A, start) = findprev(identity, A, start)
2258
2259 """
2260 findlast(A)
2261
2262 Return the index or key of the last `true` value in `A`.
2263 Return `nothing` if there is no `true` value in `A`.
2264
2265 Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
2266 and [`pairs(A)`](@ref).
2267
2268 See also: [`findfirst`](@ref), [`findprev`](@ref), [`findall`](@ref).
2269
2270 # Examples
2271 ```jldoctest
2272 julia> A = [true, false, true, false]
2273 4-element Vector{Bool}:
2274 1
2275 0
2276 1
2277 0
2278
2279 julia> findlast(A)
2280 3
2281
2282 julia> A = falses(2,2);
2283
2284 julia> findlast(A) # returns nothing, but not printed in the REPL
2285
2286 julia> A = [true false; true false]
2287 2×2 Matrix{Bool}:
2288 1 0
2289 1 0
2290
2291 julia> findlast(A)
2292 CartesianIndex(2, 1)
2293 ```
2294 """
2295 findlast(A) = findlast(identity, A)
2296
2297 # Needed for bootstrap, and allows defining only an optimized findprev method
2298 findlast(A::AbstractArray) = findprev(A, last(keys(A)))
2299
2300 """
2301 findprev(predicate::Function, A, i)
2302
2303 Find the previous index before or including `i` of an element of `A`
2304 for which `predicate` returns `true`, or `nothing` if not found.
2305
2306 Indices are of the same type as those returned by [`keys(A)`](@ref)
2307 and [`pairs(A)`](@ref).
2308
2309 # Examples
2310 ```jldoctest
2311 julia> A = [4, 6, 1, 2]
2312 4-element Vector{Int64}:
2313 4
2314 6
2315 1
2316 2
2317
2318 julia> findprev(isodd, A, 1) # returns nothing, but not printed in the REPL
2319
2320 julia> findprev(isodd, A, 3)
2321 3
2322
2323 julia> A = [4 6; 1 2]
2324 2×2 Matrix{Int64}:
2325 4 6
2326 1 2
2327
2328 julia> findprev(isodd, A, CartesianIndex(1, 2))
2329 CartesianIndex(2, 1)
2330 ```
2331 """
2332 function findprev(testf::Function, A, start)
2333 f = first(keys(A))
2334 i = oftype(f, start)
2335 i < f && return nothing
2336 while true
2337 testf(A[i]) && return i
2338 i == f && break
2339 # prevind(A, f) can throw/underflow
2340 i = prevind(A, i)
2341 end
2342 return nothing
2343 end
2344
2345 """
2346 findlast(predicate::Function, A)
2347
2348 Return the index or key of the last element of `A` for which `predicate` returns `true`.
2349 Return `nothing` if there is no such element.
2350
2351 Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
2352 and [`pairs(A)`](@ref).
2353
2354 # Examples
2355 ```jldoctest
2356 julia> A = [1, 2, 3, 4]
2357 4-element Vector{Int64}:
2358 1
2359 2
2360 3
2361 4
2362
2363 julia> findlast(isodd, A)
2364 3
2365
2366 julia> findlast(x -> x > 5, A) # returns nothing, but not printed in the REPL
2367
2368 julia> A = [1 2; 3 4]
2369 2×2 Matrix{Int64}:
2370 1 2
2371 3 4
2372
2373 julia> findlast(isodd, A)
2374 CartesianIndex(2, 1)
2375 ```
2376 """
2377 function findlast(testf::Function, A)
2378 for (i, a) in Iterators.reverse(pairs(A))
2379 testf(a) && return i
2380 end
2381 return nothing
2382 end
2383
2384 # Needed for bootstrap, and allows defining only an optimized findprev method
2385 findlast(testf::Function, A::Union{AbstractArray, AbstractString}) =
2386 findprev(testf, A, last(keys(A)))
2387
2388 """
2389 findall(f::Function, A)
2390
2391 Return a vector `I` of the indices or keys of `A` where `f(A[I])` returns `true`.
2392 If there are no such elements of `A`, return an empty array.
2393
2394 Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
2395 and [`pairs(A)`](@ref).
2396
2397 # Examples
2398 ```jldoctest
2399 julia> x = [1, 3, 4]
2400 3-element Vector{Int64}:
2401 1
2402 3
2403 4
2404
2405 julia> findall(isodd, x)
2406 2-element Vector{Int64}:
2407 1
2408 2
2409
2410 julia> A = [1 2 0; 3 4 0]
2411 2×3 Matrix{Int64}:
2412 1 2 0
2413 3 4 0
2414 julia> findall(isodd, A)
2415 2-element Vector{CartesianIndex{2}}:
2416 CartesianIndex(1, 1)
2417 CartesianIndex(2, 1)
2418
2419 julia> findall(!iszero, A)
2420 4-element Vector{CartesianIndex{2}}:
2421 CartesianIndex(1, 1)
2422 CartesianIndex(2, 1)
2423 CartesianIndex(1, 2)
2424 CartesianIndex(2, 2)
2425
2426 julia> d = Dict(:A => 10, :B => -1, :C => 0)
2427 Dict{Symbol, Int64} with 3 entries:
2428 :A => 10
2429 :B => -1
2430 :C => 0
2431
2432 julia> findall(x -> x >= 0, d)
2433 2-element Vector{Symbol}:
2434 :A
2435 :C
2436
2437 ```
2438 """
2439 function findall(testf::Function, A)
2440 T = eltype(keys(A))
2441 gen = (first(p) for p in pairs(A) if testf(last(p)))
2442 isconcretetype(T) ? collect(T, gen) : collect(gen)
2443 end
2444
2445 # Broadcasting is much faster for small testf, and computing
2446 # integer indices from logical index using findall has a negligible cost
2447 findall(testf::F, A::AbstractArray) where {F<:Function} = findall(testf.(A))
2448
2449 """
2450 findall(A)
2451
2452 Return a vector `I` of the `true` indices or keys of `A`.
2453 If there are no such elements of `A`, return an empty array.
2454 To search for other kinds of values, pass a predicate as the first argument.
2455
2456 Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
2457 and [`pairs(A)`](@ref).
2458
2459 See also: [`findfirst`](@ref), [`searchsorted`](@ref).
2460
2461 # Examples
2462 ```jldoctest
2463 julia> A = [true, false, false, true]
2464 4-element Vector{Bool}:
2465 1
2466 0
2467 0
2468 1
2469
2470 julia> findall(A)
2471 2-element Vector{Int64}:
2472 1
2473 4
2474
2475 julia> A = [true false; false true]
2476 2×2 Matrix{Bool}:
2477 1 0
2478 0 1
2479
2480 julia> findall(A)
2481 2-element Vector{CartesianIndex{2}}:
2482 CartesianIndex(1, 1)
2483 CartesianIndex(2, 2)
2484
2485 julia> findall(falses(3))
2486 Int64[]
2487 ```
2488 """
2489 function findall(A)
2490 collect(first(p) for p in pairs(A) if last(p))
2491 end
2492
2493 # Allocating result upfront is faster (possible only when collection can be iterated twice)
2494 function findall(A::AbstractArray{Bool})
2495 n = count(A)
2496 I = Vector{eltype(keys(A))}(undef, n)
2497 cnt = 1
2498 for (i,a) in pairs(A)
2499 if a
2500 I[cnt] = i
2501 cnt += 1
2502 end
2503 end
2504 I
2505 end
2506
2507 findall(x::Bool) = x ? [1] : Vector{Int}()
2508 findall(testf::Function, x::Number) = testf(x) ? [1] : Vector{Int}()
2509 findall(p::Fix2{typeof(in)}, x::Number) = x in p.x ? [1] : Vector{Int}()
2510
2511 # similar to Matlab's ismember
2512 """
2513 indexin(a, b)
2514
2515 Return an array containing the first index in `b` for
2516 each value in `a` that is a member of `b`. The output
2517 array contains `nothing` wherever `a` is not a member of `b`.
2518
2519 See also: [`sortperm`](@ref), [`findfirst`](@ref).
2520
2521 # Examples
2522 ```jldoctest
2523 julia> a = ['a', 'b', 'c', 'b', 'd', 'a'];
2524
2525 julia> b = ['a', 'b', 'c'];
2526
2527 julia> indexin(a, b)
2528 6-element Vector{Union{Nothing, Int64}}:
2529 1
2530 2
2531 3
2532 2
2533 nothing
2534 1
2535
2536 julia> indexin(b, a)
2537 3-element Vector{Union{Nothing, Int64}}:
2538 1
2539 2
2540 3
2541 ```
2542 """
2543 function indexin(a, b::AbstractArray)
2544 inds = keys(b)
2545 bdict = Dict{eltype(b),eltype(inds)}()
2546 for (val, ind) in zip(b, inds)
2547 get!(bdict, val, ind)
2548 end
2549 return Union{eltype(inds), Nothing}[
2550 get(bdict, i, nothing) for i in a
2551 ]
2552 end
2553
2554 function _findin(a::Union{AbstractArray, Tuple}, b)
2555 ind = Vector{eltype(keys(a))}()
2556 bset = Set(b)
2557 @inbounds for (i,ai) in pairs(a)
2558 ai in bset && push!(ind, i)
2559 end
2560 ind
2561 end
2562
2563 # If two collections are already sorted, _findin can be computed with
2564 # a single traversal of the two collections. This is much faster than
2565 # using a hash table (although it has the same complexity).
2566 function _sortedfindin(v::Union{AbstractArray, Tuple}, w)
2567 viter, witer = keys(v), eachindex(w)
2568 out = eltype(viter)[]
2569 vy, wy = iterate(viter), iterate(witer)
2570 if vy === nothing || wy === nothing
2571 return out
2572 end
2573 viteri, i = vy
2574 witerj, j = wy
2575 @inbounds begin
2576 vi, wj = v[viteri], w[witerj]
2577 while true
2578 if isless(vi, wj)
2579 vy = iterate(viter, i)
2580 if vy === nothing
2581 break
2582 end
2583 viteri, i = vy
2584 vi = v[viteri]
2585 elseif isless(wj, vi)
2586 wy = iterate(witer, j)
2587 if wy === nothing
2588 break
2589 end
2590 witerj, j = wy
2591 wj = w[witerj]
2592 else
2593 push!(out, viteri)
2594 vy = iterate(viter, i)
2595 if vy === nothing
2596 break
2597 end
2598 # We only increment the v iterator because v can have
2599 # repeated matches to a single value in w
2600 viteri, i = vy
2601 vi = v[viteri]
2602 end
2603 end
2604 end
2605 return out
2606 end
2607
2608 function findall(pred::Fix2{typeof(in),<:Union{Array{<:Real},Real}}, x::Array{<:Real})
2609 if issorted(x, Sort.Forward) && issorted(pred.x, Sort.Forward)
2610 return _sortedfindin(x, pred.x)
2611 else
2612 return _findin(x, pred.x)
2613 end
2614 end
2615 # issorted fails for some element types so the method above has to be restricted
2616 # to element with isless/< defined.
2617 findall(pred::Fix2{typeof(in)}, x::AbstractArray) = _findin(x, pred.x)
2618 findall(pred::Fix2{typeof(in)}, x::Tuple) = _findin(x, pred.x)
2619
2620 # Copying subregions
2621 function indcopy(sz::Dims, I::Vector)
2622 n = length(I)
2623 s = sz[n]
2624 for i = n+1:length(sz)
2625 s *= sz[i]
2626 end
2627 dst = eltype(I)[_findin(I[i], i < n ? (1:sz[i]) : (1:s)) for i = 1:n]
2628 src = eltype(I)[I[i][_findin(I[i], i < n ? (1:sz[i]) : (1:s))] for i = 1:n]
2629 dst, src
2630 end
2631
2632 function indcopy(sz::Dims, I::Tuple{Vararg{RangeIndex}})
2633 n = length(I)
2634 s = sz[n]
2635 for i = n+1:length(sz)
2636 s *= sz[i]
2637 end
2638 dst::typeof(I) = ntuple(i-> _findin(I[i], i < n ? (1:sz[i]) : (1:s)), n)::typeof(I)
2639 src::typeof(I) = ntuple(i-> I[i][_findin(I[i], i < n ? (1:sz[i]) : (1:s))], n)::typeof(I)
2640 dst, src
2641 end
2642
2643 ## Filter ##
2644
2645 """
2646 filter(f, a)
2647
2648 Return a copy of collection `a`, removing elements for which `f` is `false`.
2649 The function `f` is passed one argument.
2650
2651 !!! compat "Julia 1.4"
2652 Support for `a` as a tuple requires at least Julia 1.4.
2653
2654 See also: [`filter!`](@ref), [`Iterators.filter`](@ref).
2655
2656 # Examples
2657 ```jldoctest
2658 julia> a = 1:10
2659 1:10
2660
2661 julia> filter(isodd, a)
2662 5-element Vector{Int64}:
2663 1
2664 3
2665 5
2666 7
2667 9
2668 ```
2669 """
2670 function filter(f, a::Array{T, N}) where {T, N}
2671 j = 1
2672 b = Vector{T}(undef, length(a))
2673 for ai in a
2674 @inbounds b[j] = ai
2675 j = ifelse(f(ai)::Bool, j+1, j)
2676 end
2677 resize!(b, j-1)
2678 sizehint!(b, length(b))
2679 b
2680 end
2681
2682 function filter(f, a::AbstractArray)
2683 (IndexStyle(a) != IndexLinear()) && return a[map(f, a)::AbstractArray{Bool}]
2684
2685 j = 1
2686 idxs = Vector{Int}(undef, length(a))
2687 for idx in eachindex(a)
2688 @inbounds idxs[j] = idx
2689 ai = @inbounds a[idx]
2690 j = ifelse(f(ai)::Bool, j+1, j)
2691 end
2692 resize!(idxs, j-1)
2693 res = a[idxs]
2694 empty!(idxs)
2695 sizehint!(idxs, 0)
2696 return res
2697 end
2698
2699 """
2700 filter!(f, a)
2701
2702 Update collection `a`, removing elements for which `f` is `false`.
2703 The function `f` is passed one argument.
2704
2705 # Examples
2706 ```jldoctest
2707 julia> filter!(isodd, Vector(1:10))
2708 5-element Vector{Int64}:
2709 1
2710 3
2711 5
2712 7
2713 9
2714 ```
2715 """
2716 function filter!(f, a::AbstractVector)
2717 j = firstindex(a)
2718 for ai in a
2719 @inbounds a[j] = ai
2720 j = ifelse(f(ai)::Bool, nextind(a, j), j)
2721 end
2722 j > lastindex(a) && return a
2723 if a isa Vector
2724 resize!(a, j-1)
2725 sizehint!(a, j-1)
2726 else
2727 deleteat!(a, j:lastindex(a))
2728 end
2729 return a
2730 end
2731
2732 """
2733 filter(f)
2734
2735 Create a function that filters its arguments with function `f` using [`filter`](@ref), i.e.
2736 a function equivalent to `x -> filter(f, x)`.
2737
2738 The returned function is of type `Base.Fix1{typeof(filter)}`, which can be
2739 used to implement specialized methods.
2740
2741 # Examples
2742 ```jldoctest
2743 julia> (1, 2, Inf, 4, NaN, 6) |> filter(isfinite)
2744 (1, 2, 4, 6)
2745
2746 julia> map(filter(iseven), [1:3, 2:4, 3:5])
2747 3-element Vector{Vector{Int64}}:
2748 [2]
2749 [2, 4]
2750 [4]
2751 ```
2752 !!! compat "Julia 1.9"
2753 This method requires at least Julia 1.9.
2754 """
2755 function filter(f)
2756 Fix1(filter, f)
2757 end
2758
2759 """
2760 keepat!(a::Vector, inds)
2761 keepat!(a::BitVector, inds)
2762
2763 Remove the items at all the indices which are not given by `inds`,
2764 and return the modified `a`.
2765 Items which are kept are shifted to fill the resulting gaps.
2766
2767 $(_DOCS_ALIASING_WARNING)
2768
2769 `inds` must be an iterator of sorted and unique integer indices.
2770 See also [`deleteat!`](@ref).
2771
2772 !!! compat "Julia 1.7"
2773 This function is available as of Julia 1.7.
2774
2775 # Examples
2776 ```jldoctest
2777 julia> keepat!([6, 5, 4, 3, 2, 1], 1:2:5)
2778 3-element Vector{Int64}:
2779 6
2780 4
2781 2
2782 ```
2783 """
2784 keepat!(a::Vector, inds) = _keepat!(a, inds)
2785
2786 """
2787 keepat!(a::Vector, m::AbstractVector{Bool})
2788 keepat!(a::BitVector, m::AbstractVector{Bool})
2789
2790 The in-place version of logical indexing `a = a[m]`. That is, `keepat!(a, m)` on
2791 vectors of equal length `a` and `m` will remove all elements from `a` for which
2792 `m` at the corresponding index is `false`.
2793
2794 # Examples
2795 ```jldoctest
2796 julia> a = [:a, :b, :c];
2797
2798 julia> keepat!(a, [true, false, true])
2799 2-element Vector{Symbol}:
2800 :a
2801 :c
2802
2803 julia> a
2804 2-element Vector{Symbol}:
2805 :a
2806 :c
2807 ```
2808 """
2809 keepat!(a::Vector, m::AbstractVector{Bool}) = _keepat!(a, m)
2810
2811 # set-like operators for vectors
2812 # These are moderately efficient, preserve order, and remove dupes.
2813
2814 _unique_filter!(pred::P, update!::U, state) where {P,U} = function (x)
2815 # P, U force specialization
2816 if pred(x, state)
2817 update!(state, x)
2818 true
2819 else
2820 false
2821 end
2822 end
2823
2824 _grow_filter!(seen) = _unique_filter!(∉, push!, seen)
2825 _shrink_filter!(keep) = _unique_filter!(∈, pop!, keep)
2826
2827 function _grow!(pred!, v::AbstractVector, itrs)
2828 filter!(pred!, v) # uniquify v
2829 for itr in itrs
2830 mapfilter(pred!, push!, itr, v)
2831 end
2832 return v
2833 end
2834
2835 union!(v::AbstractVector{T}, itrs...) where {T} =
2836 _grow!(_grow_filter!(sizehint!(Set{T}(), length(v))), v, itrs)
2837
2838 symdiff!(v::AbstractVector{T}, itrs...) where {T} =
2839 _grow!(_shrink_filter!(symdiff!(Set{T}(), v, itrs...)), v, itrs)
2840
2841 function _shrink!(shrinker!::F, v::AbstractVector, itrs) where F
2842 seen = Set{eltype(v)}()
2843 filter!(_grow_filter!(seen), v)
2844 shrinker!(seen, itrs...)
2845 filter!(in(seen), v)
2846 end
2847
2848 intersect!(v::AbstractVector, itrs...) = _shrink!(intersect!, v, itrs)
2849 setdiff!( v::AbstractVector, itrs...) = _shrink!(setdiff!, v, itrs)
2850
2851 vectorfilter(T::Type, f, v) = T[x for x in v if f(x)]
2852
2853 function _shrink(shrinker!::F, itr, itrs) where F
2854 T = promote_eltype(itr, itrs...)
2855 keep = shrinker!(Set{T}(itr), itrs...)
2856 vectorfilter(T, _shrink_filter!(keep), itr)
2857 end
2858
2859 intersect(itr, itrs...) = _shrink(intersect!, itr, itrs)
2860 setdiff( itr, itrs...) = _shrink(setdiff!, itr, itrs)
2861
2862 function intersect(v::AbstractVector, r::AbstractRange)
2863 T = promote_eltype(v, r)
2864 common = Iterators.filter(in(r), v)
2865 seen = Set{T}(common)
2866 return vectorfilter(T, _shrink_filter!(seen), common)
2867 end
2868 intersect(r::AbstractRange, v::AbstractVector) = intersect(v, r)