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