StatProfilerHTML.jl report
Generated on tor 10 okt 2019 11:38:33
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 ## array.jl: Dense arrays
4
5 """
6 DimensionMismatch([msg])
7
8 The objects called do not have matching dimensionality. Optional argument `msg` is a
9 descriptive error string.
10 """
11 struct DimensionMismatch <: Exception
12 msg::AbstractString
13 end
14 DimensionMismatch() = DimensionMismatch("")
15
16 ## Type aliases for convenience ##
17 """
18 AbstractVector{T}
19
20 Supertype for one-dimensional arrays (or array-like types) with
21 elements of type `T`. Alias for [`AbstractArray{T,1}`](@ref).
22 """
23 const AbstractVector{T} = AbstractArray{T,1}
24
25 """
26 AbstractMatrix{T}
27
28 Supertype for two-dimensional arrays (or array-like types) with
29 elements of type `T`. Alias for [`AbstractArray{T,2}`](@ref).
30 """
31 const AbstractMatrix{T} = AbstractArray{T,2}
32
33 """
34 AbstractVecOrMat{T}
35
36 Union type of [`AbstractVector{T}`](@ref) and [`AbstractMatrix{T}`](@ref).
37 """
38 const AbstractVecOrMat{T} = Union{AbstractVector{T}, AbstractMatrix{T}}
39 const RangeIndex = Union{Int, AbstractRange{Int}, AbstractUnitRange{Int}}
40 const DimOrInd = Union{Integer, AbstractUnitRange}
41 const IntOrInd = Union{Int, AbstractUnitRange}
42 const DimsOrInds{N} = NTuple{N,DimOrInd}
43 const NeedsShaping = Union{Tuple{Integer,Vararg{Integer}}, Tuple{OneTo,Vararg{OneTo}}}
44
45 """
46 Array{T,N} <: AbstractArray{T,N}
47
48 `N`-dimensional dense array with elements of type `T`.
49 """
50 Array
51
52 """
53 Vector{T} <: AbstractVector{T}
54
55 One-dimensional dense array with elements of type `T`, often used to represent
56 a mathematical vector. Alias for [`Array{T,1}`](@ref).
57 """
58 const Vector{T} = Array{T,1}
59
60 """
61 Matrix{T} <: AbstractMatrix{T}
62
63 Two-dimensional dense array with elements of type `T`, often used to represent
64 a mathematical matrix. Alias for [`Array{T,2}`](@ref).
65 """
66 const Matrix{T} = Array{T,2}
67 """
68 VecOrMat{T}
69
70 Union type of [`Vector{T}`](@ref) and [`Matrix{T}`](@ref).
71 """
72 const VecOrMat{T} = Union{Vector{T}, Matrix{T}}
73
74 """
75 DenseArray{T, N} <: AbstractArray{T,N}
76
77 `N`-dimensional dense array with elements of type `T`.
78 The elements of a dense array are stored contiguously in memory.
79 """
80 DenseArray
81
82 """
83 DenseVector{T}
84
85 One-dimensional [`DenseArray`](@ref) with elements of type `T`. Alias for `DenseArray{T,1}`.
86 """
87 const DenseVector{T} = DenseArray{T,1}
88
89 """
90 DenseMatrix{T}
91
92 Two-dimensional [`DenseArray`](@ref) with elements of type `T`. Alias for `DenseArray{T,2}`.
93 """
94 const DenseMatrix{T} = DenseArray{T,2}
95
96 """
97 DenseVecOrMat{T}
98
99 Union type of [`DenseVector{T}`](@ref) and [`DenseMatrix{T}`](@ref).
100 """
101 const DenseVecOrMat{T} = Union{DenseVector{T}, DenseMatrix{T}}
102
103 ## Basic functions ##
104
105 """
106 eltype(type)
107
108 Determine the type of the elements generated by iterating a collection of the given `type`.
109 For dictionary types, this will be a `Pair{KeyType,ValType}`. The definition
110 `eltype(x) = eltype(typeof(x))` is provided for convenience so that instances can be passed
111 instead of types. However the form that accepts a type argument should be defined for new
112 types.
113
114 # Examples
115 ```jldoctest
116 julia> eltype(fill(1f0, (2,2)))
117 Float32
118
119 julia> eltype(fill(0x1, (2,2)))
120 UInt8
121 ```
122 """
123 eltype(::Type) = Any
124 eltype(::Type{Bottom}) = throw(ArgumentError("Union{} does not have elements"))
125 eltype(x) = eltype(typeof(x))
126
127 import Core: arraysize, arrayset, arrayref
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!
1 (100.00%) (ex.), 1 (100.00%) (incl.) when called from resize! line 1011
_deleteend!(a::Vector, delta::Integer) =
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)