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