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 %) | 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 (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
@eval getindex(A::Array, i1::Int) = arrayref($(Expr(:boundscheck)), A, i1)
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 |
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!
@eval setindex!(A::Array{T}, x, i1::Int) where {T} = arrayset($(Expr(:boundscheck)), A, convert(T,x)::T, i1)
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 |
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!
_growend!(a::Vector, delta::Integer) =
86 (100 %) (ex.), 86 (100 %) (incl.) when called from push! line 912 |
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 (100 %)
samples spent calling
_growend!
_growend!(a, 1)
|
|
913 | 46 (6 %) | 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) |