https://github.com/JuliaLang/julia
Tip revision: 80516ca20297a67b996caa08c38786332379b6a5 authored by Alex Arslan on 21 January 2019, 21:24:18 UTC
Set VERSION to 1.1.0 (#30786)
Set VERSION to 1.1.0 (#30786)
Tip revision: 80516ca
array.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
## array.jl: Dense arrays
"""
DimensionMismatch([msg])
The objects called do not have matching dimensionality. Optional argument `msg` is a
descriptive error string.
"""
struct DimensionMismatch <: Exception
msg::AbstractString
end
DimensionMismatch() = DimensionMismatch("")
## Type aliases for convenience ##
"""
AbstractVector{T}
Supertype for one-dimensional arrays (or array-like types) with
elements of type `T`. Alias for [`AbstractArray{T,1}`](@ref).
"""
const AbstractVector{T} = AbstractArray{T,1}
"""
AbstractMatrix{T}
Supertype for two-dimensional arrays (or array-like types) with
elements of type `T`. Alias for [`AbstractArray{T,2}`](@ref).
"""
const AbstractMatrix{T} = AbstractArray{T,2}
"""
AbstractVecOrMat{T}
Union type of [`AbstractVector{T}`](@ref) and [`AbstractMatrix{T}`](@ref).
"""
const AbstractVecOrMat{T} = Union{AbstractVector{T}, AbstractMatrix{T}}
const RangeIndex = Union{Int, AbstractRange{Int}, AbstractUnitRange{Int}}
const DimOrInd = Union{Integer, AbstractUnitRange}
const IntOrInd = Union{Int, AbstractUnitRange}
const DimsOrInds{N} = NTuple{N,DimOrInd}
const NeedsShaping = Union{Tuple{Integer,Vararg{Integer}}, Tuple{OneTo,Vararg{OneTo}}}
"""
Array{T,N} <: AbstractArray{T,N}
`N`-dimensional dense array with elements of type `T`.
"""
Array
"""
Vector{T} <: AbstractVector{T}
One-dimensional dense array with elements of type `T`, often used to represent
a mathematical vector. Alias for [`Array{T,1}`](@ref).
"""
const Vector{T} = Array{T,1}
"""
Matrix{T} <: AbstractMatrix{T}
Two-dimensional dense array with elements of type `T`, often used to represent
a mathematical matrix. Alias for [`Array{T,2}`](@ref).
"""
const Matrix{T} = Array{T,2}
"""
VecOrMat{T}
Union type of [`Vector{T}`](@ref) and [`Matrix{T}`](@ref).
"""
const VecOrMat{T} = Union{Vector{T}, Matrix{T}}
"""
DenseArray{T, N} <: AbstractArray{T,N}
`N`-dimensional dense array with elements of type `T`.
The elements of a dense array are stored contiguously in memory.
"""
DenseArray
"""
DenseVector{T}
One-dimensional [`DenseArray`](@ref) with elements of type `T`. Alias for `DenseArray{T,1}`.
"""
const DenseVector{T} = DenseArray{T,1}
"""
DenseMatrix{T}
Two-dimensional [`DenseArray`](@ref) with elements of type `T`. Alias for `DenseArray{T,2}`.
"""
const DenseMatrix{T} = DenseArray{T,2}
"""
DenseVecOrMat{T}
Union type of [`DenseVector{T}`](@ref) and [`DenseMatrix{T}`](@ref).
"""
const DenseVecOrMat{T} = Union{DenseVector{T}, DenseMatrix{T}}
## Basic functions ##
"""
eltype(type)
Determine the type of the elements generated by iterating a collection of the given `type`.
For dictionary types, this will be a `Pair{KeyType,ValType}`. The definition
`eltype(x) = eltype(typeof(x))` is provided for convenience so that instances can be passed
instead of types. However the form that accepts a type argument should be defined for new
types.
# Examples
```jldoctest
julia> eltype(fill(1f0, (2,2)))
Float32
julia> eltype(fill(0x1, (2,2)))
UInt8
```
"""
eltype(::Type) = Any
eltype(::Type{Bottom}) = throw(ArgumentError("Union{} does not have elements"))
eltype(x) = eltype(typeof(x))
import Core: arraysize, arrayset, arrayref
vect() = Vector{Any}()
vect(X::T...) where {T} = T[ X[i] for i = 1:length(X) ]
"""
vect(X...)
Create a [`Vector`](@ref) with element type computed from the `promote_typeof` of the argument,
containing the argument list.
# Examples
```jldoctest
julia> a = Base.vect(UInt8(1), 2.5, 1//2)
3-element Array{Float64,1}:
1.0
2.5
0.5
```
"""
function vect(X...)
T = promote_typeof(X...)
#T[ X[i] for i=1:length(X) ]
# TODO: this is currently much faster. should figure out why. not clear.
return copyto!(Vector{T}(undef, length(X)), X)
end
size(a::Array, d) = arraysize(a, d)
size(a::Vector) = (arraysize(a,1),)
size(a::Matrix) = (arraysize(a,1), arraysize(a,2))
size(a::Array{<:Any,N}) where {N} = (@_inline_meta; ntuple(M -> size(a, M), Val(N)))
asize_from(a::Array, n) = n > ndims(a) ? () : (arraysize(a,n), asize_from(a, n+1)...)
"""
Base.isbitsunion(::Type{T})
Return whether a type is an "is-bits" Union type, meaning each type included in a Union is [`isbitstype`](@ref).
# Examples
```jldoctest
julia> Base.isbitsunion(Union{Float64, UInt8})
true
julia> Base.isbitsunion(Union{Float64, String})
false
```
"""
isbitsunion(u::Union) = (@_pure_meta; ccall(:jl_array_store_unboxed, Cint, (Any,), u) != Cint(0))
isbitsunion(x) = false
"""
Base.bitsunionsize(U::Union)
For a `Union` of [`isbitstype`](@ref) types, return the size of the largest type; assumes `Base.isbitsunion(U) == true`.
# Examples
```jldoctest
julia> Base.bitsunionsize(Union{Float64, UInt8})
0x0000000000000008
julia> Base.bitsunionsize(Union{Float64, UInt8, Int128})
0x0000000000000010
```
"""
function bitsunionsize(u::Union)
sz = Ref{Csize_t}(0)
algn = Ref{Csize_t}(0)
@assert ccall(:jl_islayout_inline, Cint, (Any, Ptr{Csize_t}, Ptr{Csize_t}), u, sz, algn) != Cint(0)
return sz[]
end
length(a::Array) = arraylen(a)
elsize(::Type{<:Array{T}}) where {T} = isbitstype(T) ? sizeof(T) : (isbitsunion(T) ? bitsunionsize(T) : sizeof(Ptr))
sizeof(a::Array) = Core.sizeof(a)
function isassigned(a::Array, i::Int...)
@_inline_meta
ii = (_sub2ind(size(a), i...) % UInt) - 1
@boundscheck ii < length(a) % UInt || return false
ccall(:jl_array_isassigned, Cint, (Any, UInt), a, ii) == 1
end
## copy ##
"""
unsafe_copyto!(dest::Ptr{T}, src::Ptr{T}, N)
Copy `N` elements from a source pointer to a destination, with no checking. The size of an
element is determined by the type of the pointers.
The `unsafe` prefix on this function indicates that no validation is performed on the
pointers `dest` and `src` to ensure that they are valid. Incorrect usage may corrupt or
segfault your program, in the same manner as C.
"""
function unsafe_copyto!(dest::Ptr{T}, src::Ptr{T}, n) where T
# Do not use this to copy data between pointer arrays.
# It can't be made safe no matter how carefully you checked.
ccall(:memmove, Ptr{Cvoid}, (Ptr{Cvoid}, Ptr{Cvoid}, UInt),
dest, src, n*sizeof(T))
return dest
end
"""
unsafe_copyto!(dest::Array, do, src::Array, so, N)
Copy `N` elements from a source array to a destination, starting at offset `so` in the
source and `do` in the destination (1-indexed).
The `unsafe` prefix on this function indicates that no validation is performed to ensure
that N is inbounds on either array. Incorrect usage may corrupt or segfault your program, in
the same manner as C.
"""
function unsafe_copyto!(dest::Array{T}, doffs, src::Array{T}, soffs, n) where T
t1 = @_gc_preserve_begin dest
t2 = @_gc_preserve_begin src
if isbitstype(T)
unsafe_copyto!(pointer(dest, doffs), pointer(src, soffs), n)
elseif isbitsunion(T)
ccall(:memmove, Ptr{Cvoid}, (Ptr{Cvoid}, Ptr{Cvoid}, UInt),
pointer(dest, doffs), pointer(src, soffs), n * Base.bitsunionsize(T))
# copy selector bytes
ccall(:memmove, Ptr{Cvoid}, (Ptr{Cvoid}, Ptr{Cvoid}, UInt),
ccall(:jl_array_typetagdata, Ptr{UInt8}, (Any,), dest) + doffs - 1,
ccall(:jl_array_typetagdata, Ptr{UInt8}, (Any,), src) + soffs - 1,
n)
else
ccall(:jl_array_ptr_copy, Cvoid, (Any, Ptr{Cvoid}, Any, Ptr{Cvoid}, Int),
dest, pointer(dest, doffs), src, pointer(src, soffs), n)
end
@_gc_preserve_end t2
@_gc_preserve_end t1
return dest
end
"""
copyto!(dest, do, src, so, N)
Copy `N` elements from collection `src` starting at offset `so`, to array `dest` starting at
offset `do`. Return `dest`.
"""
function copyto!(dest::Array{T}, doffs::Integer, src::Array{T}, soffs::Integer, n::Integer) where T
n == 0 && return dest
n > 0 || _throw_argerror()
if soffs < 1 || doffs < 1 || soffs+n-1 > length(src) || doffs+n-1 > length(dest)
throw(BoundsError())
end
unsafe_copyto!(dest, doffs, src, soffs, n)
return dest
end
# Outlining this because otherwise a catastrophic inference slowdown
# occurs, see discussion in #27874.
# It is also mitigated by using a constant string.
function _throw_argerror()
@_noinline_meta
throw(ArgumentError("Number of elements to copy must be nonnegative."))
end
copyto!(dest::Array{T}, src::Array{T}) where {T} = copyto!(dest, 1, src, 1, length(src))
# N.B: The generic definition in multidimensional.jl covers, this, this is just here
# for bootstrapping purposes.
function fill!(dest::Array{T}, x) where T
@_noinline_meta
xT = convert(T, x)
for i in 1:length(dest)
@inbounds dest[i] = xT
end
return dest
end
"""
copy(x)
Create a shallow copy of `x`: the outer structure is copied, but not all internal values.
For example, copying an array produces a new array with identically-same elements as the
original.
"""
copy
copy(a::T) where {T<:Array} = ccall(:jl_array_copy, Ref{T}, (Any,), a)
## Constructors ##
similar(a::Array{T,1}) where {T} = Vector{T}(undef, size(a,1))
similar(a::Array{T,2}) where {T} = Matrix{T}(undef, size(a,1), size(a,2))
similar(a::Array{T,1}, S::Type) where {T} = Vector{S}(undef, size(a,1))
similar(a::Array{T,2}, S::Type) where {T} = Matrix{S}(undef, size(a,1), size(a,2))
similar(a::Array{T}, m::Int) where {T} = Vector{T}(undef, m)
similar(a::Array, T::Type, dims::Dims{N}) where {N} = Array{T,N}(undef, dims)
similar(a::Array{T}, dims::Dims{N}) where {T,N} = Array{T,N}(undef, dims)
# T[x...] constructs Array{T,1}
"""
getindex(type[, elements...])
Construct a 1-d array of the specified type. This is usually called with the syntax
`Type[]`. Element values can be specified using `Type[a,b,c,...]`.
# Examples
```jldoctest
julia> Int8[1, 2, 3]
3-element Array{Int8,1}:
1
2
3
julia> getindex(Int8, 1, 2, 3)
3-element Array{Int8,1}:
1
2
3
```
"""
function getindex(::Type{T}, vals...) where T
a = Vector{T}(undef, length(vals))
@inbounds for i = 1:length(vals)
a[i] = vals[i]
end
return a
end
getindex(::Type{T}) where {T} = (@_inline_meta; Vector{T}())
getindex(::Type{T}, x) where {T} = (@_inline_meta; a = Vector{T}(undef, 1); @inbounds a[1] = x; a)
getindex(::Type{T}, x, y) where {T} = (@_inline_meta; a = Vector{T}(undef, 2); @inbounds (a[1] = x; a[2] = y); a)
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)
function getindex(::Type{Any}, @nospecialize vals...)
a = Vector{Any}(undef, length(vals))
@inbounds for i = 1:length(vals)
a[i] = vals[i]
end
return a
end
getindex(::Type{Any}) = Vector{Any}()
function fill!(a::Union{Array{UInt8}, Array{Int8}}, x::Integer)
ccall(:memset, Ptr{Cvoid}, (Ptr{Cvoid}, Cint, Csize_t), a, x, length(a))
return a
end
function fill!(a::Array{T}, x) where T<:Union{Integer,AbstractFloat}
@_noinline_meta
xT = convert(T, x)
for i in eachindex(a)
@inbounds a[i] = xT
end
return a
end
to_dim(d::Integer) = d
to_dim(d::OneTo) = last(d)
"""
fill(x, dims)
Create an array filled with the value `x`. For example, `fill(1.0, (5,5))` returns a 5×5
array of floats, with each element initialized to `1.0`.
# Examples
```jldoctest
julia> fill(1.0, (5,5))
5×5 Array{Float64,2}:
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
```
If `x` is an object reference, all elements will refer to the same object. `fill(Foo(),
dims)` will return an array filled with the result of evaluating `Foo()` once.
"""
fill(v, dims::DimOrInd...) = fill(v, dims)
fill(v, dims::NTuple{N, Union{Integer, OneTo}}) where {N} = fill(v, map(to_dim, dims))
fill(v, dims::NTuple{N, Integer}) where {N} = fill!(Array{typeof(v),N}(undef, dims), v)
fill(v, dims::Tuple{}) = fill!(Array{typeof(v),0}(undef, dims), v)
"""
zeros([T=Float64,] dims...)
Create an `Array`, with element type `T`, of all zeros with size specified by `dims`.
See also [`fill`](@ref), [`ones`](@ref).
# Examples
```jldoctest
julia> zeros(1)
1-element Array{Float64,1}:
0.0
julia> zeros(Int8, 2, 3)
2×3 Array{Int8,2}:
0 0 0
0 0 0
```
"""
function zeros end
"""
ones([T=Float64,] dims...)
Create an `Array`, with element type `T`, of all ones with size specified by `dims`.
See also: [`fill`](@ref), [`zeros`](@ref).
# Examples
```jldoctest
julia> ones(1,2)
1×2 Array{Float64,2}:
1.0 1.0
julia> ones(ComplexF64, 2, 3)
2×3 Array{Complex{Float64},2}:
1.0+0.0im 1.0+0.0im 1.0+0.0im
1.0+0.0im 1.0+0.0im 1.0+0.0im
```
"""
function ones end
for (fname, felt) in ((:zeros, :zero), (:ones, :one))
@eval begin
$fname(dims::DimOrInd...) = $fname(dims)
$fname(::Type{T}, dims::DimOrInd...) where {T} = $fname(T, dims)
$fname(dims::Tuple{Vararg{DimOrInd}}) = $fname(Float64, dims)
$fname(::Type{T}, dims::NTuple{N, Union{Integer, OneTo}}) where {T,N} = $fname(T, map(to_dim, dims))
$fname(::Type{T}, dims::NTuple{N, Integer}) where {T,N} = fill!(Array{T,N}(undef, map(to_dim, dims)), $felt(T))
$fname(::Type{T}, dims::Tuple{}) where {T} = fill!(Array{T}(undef), $felt(T))
end
end
function _one(unit::T, x::AbstractMatrix) where T
@assert !has_offset_axes(x)
m,n = size(x)
m==n || throw(DimensionMismatch("multiplicative identity defined only for square matrices"))
# Matrix{T}(I, m, m)
I = zeros(T, m, m)
for i in 1:m
I[i,i] = unit
end
I
end
one(x::AbstractMatrix{T}) where {T} = _one(one(T), x)
oneunit(x::AbstractMatrix{T}) where {T} = _one(oneunit(T), x)
## Conversions ##
convert(::Type{T}, a::AbstractArray) where {T<:Array} = a isa T ? a : T(a)
promote_rule(a::Type{Array{T,n}}, b::Type{Array{S,n}}) where {T,n,S} = el_same(promote_type(T,S), a, b)
## Constructors ##
if nameof(@__MODULE__) === :Base # avoid method overwrite
# constructors should make copies
Array{T,N}(x::AbstractArray{S,N}) where {T,N,S} = copyto!(Array{T,N}(undef, size(x)), x)
AbstractArray{T,N}(A::AbstractArray{S,N}) where {T,N,S} = copyto!(similar(A,T), A)
end
## copying iterators to containers
"""
collect(element_type, collection)
Return an `Array` with the given element type of all items in a collection or iterable.
The result has the same shape and number of dimensions as `collection`.
# Examples
```jldoctest
julia> collect(Float64, 1:2:5)
3-element Array{Float64,1}:
1.0
3.0
5.0
```
"""
collect(::Type{T}, itr) where {T} = _collect(T, itr, IteratorSize(itr))
_collect(::Type{T}, itr, isz::HasLength) where {T} = copyto!(Vector{T}(undef, Int(length(itr)::Integer)), itr)
_collect(::Type{T}, itr, isz::HasShape) where {T} = copyto!(similar(Array{T}, axes(itr)), itr)
function _collect(::Type{T}, itr, isz::SizeUnknown) where T
a = Vector{T}()
for x in itr
push!(a,x)
end
return a
end
# make a collection similar to `c` and appropriate for collecting `itr`
_similar_for(c::AbstractArray, ::Type{T}, itr, ::SizeUnknown) where {T} = similar(c, T, 0)
_similar_for(c::AbstractArray, ::Type{T}, itr, ::HasLength) where {T} =
similar(c, T, Int(length(itr)::Integer))
_similar_for(c::AbstractArray, ::Type{T}, itr, ::HasShape) where {T} =
similar(c, T, axes(itr))
_similar_for(c, ::Type{T}, itr, isz) where {T} = similar(c, T)
"""
collect(collection)
Return an `Array` of all items in a collection or iterator. For dictionaries, returns
`Pair{KeyType, ValType}`. If the argument is array-like or is an iterator with the
[`HasShape`](@ref IteratorSize) trait, the result will have the same shape
and number of dimensions as the argument.
# Examples
```jldoctest
julia> collect(1:2:13)
7-element Array{Int64,1}:
1
3
5
7
9
11
13
```
"""
collect(itr) = _collect(1:1 #= Array =#, itr, IteratorEltype(itr), IteratorSize(itr))
collect(A::AbstractArray) = _collect_indices(axes(A), A)
collect_similar(cont, itr) = _collect(cont, itr, IteratorEltype(itr), IteratorSize(itr))
_collect(cont, itr, ::HasEltype, isz::Union{HasLength,HasShape}) =
copyto!(_similar_for(cont, eltype(itr), itr, isz), itr)
function _collect(cont, itr, ::HasEltype, isz::SizeUnknown)
a = _similar_for(cont, eltype(itr), itr, isz)
for x in itr
push!(a,x)
end
return a
end
_collect_indices(::Tuple{}, A) = copyto!(Array{eltype(A),0}(undef), A)
_collect_indices(indsA::Tuple{Vararg{OneTo}}, A) =
copyto!(Array{eltype(A)}(undef, length.(indsA)), A)
function _collect_indices(indsA, A)
B = Array{eltype(A)}(undef, length.(indsA))
copyto!(B, CartesianIndices(axes(B)), A, CartesianIndices(indsA))
end
# define this as a macro so that the call to Core.Compiler
# gets inlined into the caller before recursion detection
# gets a chance to see it, so that recursive calls to the caller
# don't trigger the inference limiter
if isdefined(Core, :Compiler)
macro default_eltype(itr)
I = esc(itr)
return quote
if $I isa Generator && ($I).f isa Type
($I).f
else
Core.Compiler.return_type(first, Tuple{typeof($I)})
end
end
end
else
macro default_eltype(itr)
I = esc(itr)
return quote
if $I isa Generator && ($I).f isa Type
($I).f
else
Any
end
end
end
end
_array_for(::Type{T}, itr, ::HasLength) where {T} = Vector{T}(undef, Int(length(itr)::Integer))
_array_for(::Type{T}, itr, ::HasShape{N}) where {T,N} = similar(Array{T,N}, axes(itr))
function collect(itr::Generator)
isz = IteratorSize(itr.iter)
et = @default_eltype(itr)
if isa(isz, SizeUnknown)
return grow_to!(Vector{et}(), itr)
else
y = iterate(itr)
if y === nothing
return _array_for(et, itr.iter, isz)
end
v1, st = y
collect_to_with_first!(_array_for(typeof(v1), itr.iter, isz), v1, itr, st)
end
end
_collect(c, itr, ::EltypeUnknown, isz::SizeUnknown) =
grow_to!(_similar_for(c, @default_eltype(itr), itr, isz), itr)
function _collect(c, itr, ::EltypeUnknown, isz::Union{HasLength,HasShape})
y = iterate(itr)
if y === nothing
return _similar_for(c, @default_eltype(itr), itr, isz)
end
v1, st = y
collect_to_with_first!(_similar_for(c, typeof(v1), itr, isz), v1, itr, st)
end
function collect_to_with_first!(dest::AbstractArray, v1, itr, st)
i1 = first(LinearIndices(dest))
dest[i1] = v1
return collect_to!(dest, itr, i1+1, st)
end
function collect_to_with_first!(dest, v1, itr, st)
push!(dest, v1)
return grow_to!(dest, itr, st)
end
function setindex_widen_up_to(dest::AbstractArray{T}, el, i) where T
@_inline_meta
new = similar(dest, promote_typejoin(T, typeof(el)))
copyto!(new, firstindex(new), dest, firstindex(dest), i-1)
@inbounds new[i] = el
return new
end
function collect_to!(dest::AbstractArray{T}, itr, offs, st) where T
# collect to dest array, checking the type of each result. if a result does not
# match, widen the result type and re-dispatch.
i = offs
while true
y = iterate(itr, st)
y === nothing && break
el, st = y
if el isa T || typeof(el) === T
@inbounds dest[i] = el::T
i += 1
else
new = setindex_widen_up_to(dest, el, i)
return collect_to!(new, itr, i+1, st)
end
end
return dest
end
function grow_to!(dest, itr)
y = iterate(itr)
y === nothing && return dest
dest2 = empty(dest, typeof(y[1]))
push!(dest2, y[1])
grow_to!(dest2, itr, y[2])
end
function push_widen(dest, el)
@_inline_meta
new = sizehint!(empty(dest, promote_typejoin(eltype(dest), typeof(el))), length(dest))
if new isa AbstractSet
# TODO: merge back these two branches when copy! is re-enabled for sets/vectors
union!(new, dest)
else
append!(new, dest)
end
push!(new, el)
return new
end
function grow_to!(dest, itr, st)
T = eltype(dest)
y = iterate(itr, st)
while y !== nothing
el, st = y
S = typeof(el)
if S === T || S <: T
push!(dest, el::T)
else
new = push_widen(dest, el)
return grow_to!(new, itr, st)
end
y = iterate(itr, st)
end
return dest
end
## Iteration ##
iterate(A::Array, i=1) = (@_inline_meta; (i % UInt) - 1 < length(A) ? (@inbounds A[i], i + 1) : nothing)
## Indexing: getindex ##
"""
getindex(collection, key...)
Retrieve the value(s) stored at the given key or index within a collection. The syntax
`a[i,j,...]` is converted by the compiler to `getindex(a, i, j, ...)`.
# Examples
```jldoctest
julia> A = Dict("a" => 1, "b" => 2)
Dict{String,Int64} with 2 entries:
"b" => 2
"a" => 1
julia> getindex(A, "a")
1
```
"""
function getindex end
# This is more complicated than it needs to be in order to get Win64 through bootstrap
@eval getindex(A::Array, i1::Int) = arrayref($(Expr(:boundscheck)), A, i1)
@eval getindex(A::Array, i1::Int, i2::Int, I::Int...) = (@_inline_meta; arrayref($(Expr(:boundscheck)), A, i1, i2, I...))
# Faster contiguous indexing using copyto! for UnitRange and Colon
function getindex(A::Array, I::UnitRange{Int})
@_inline_meta
@boundscheck checkbounds(A, I)
lI = length(I)
X = similar(A, lI)
if lI > 0
unsafe_copyto!(X, 1, A, first(I), lI)
end
return X
end
function getindex(A::Array, c::Colon)
lI = length(A)
X = similar(A, lI)
if lI > 0
unsafe_copyto!(X, 1, A, 1, lI)
end
return X
end
# This is redundant with the abstract fallbacks, but needed for bootstrap
function getindex(A::Array{S}, I::AbstractRange{Int}) where S
return S[ A[i] for i in I ]
end
## Indexing: setindex! ##
"""
setindex!(collection, value, key...)
Store the given value at the given key or index within a collection. The syntax `a[i,j,...] =
x` is converted by the compiler to `(setindex!(a, x, i, j, ...); x)`.
"""
function setindex! end
@eval setindex!(A::Array{T}, x, i1::Int) where {T} = arrayset($(Expr(:boundscheck)), A, convert(T,x)::T, i1)
@eval setindex!(A::Array{T}, x, i1::Int, i2::Int, I::Int...) where {T} =
(@_inline_meta; arrayset($(Expr(:boundscheck)), A, convert(T,x)::T, i1, i2, I...))
# This is redundant with the abstract fallbacks but needed and helpful for bootstrap
function setindex!(A::Array, X::AbstractArray, I::AbstractVector{Int})
@_propagate_inbounds_meta
@boundscheck setindex_shape_check(X, length(I))
@assert !has_offset_axes(X)
X′ = unalias(A, X)
I′ = unalias(A, I)
count = 1
for i in I′
@inbounds x = X′[count]
A[i] = x
count += 1
end
return A
end
# Faster contiguous setindex! with copyto!
function setindex!(A::Array{T}, X::Array{T}, I::UnitRange{Int}) where T
@_inline_meta
@boundscheck checkbounds(A, I)
lI = length(I)
@boundscheck setindex_shape_check(X, lI)
if lI > 0
unsafe_copyto!(A, first(I), X, 1, lI)
end
return A
end
function setindex!(A::Array{T}, X::Array{T}, c::Colon) where T
@_inline_meta
lI = length(A)
@boundscheck setindex_shape_check(X, lI)
if lI > 0
unsafe_copyto!(A, 1, X, 1, lI)
end
return A
end
# efficiently grow an array
_growbeg!(a::Vector, delta::Integer) =
ccall(:jl_array_grow_beg, Cvoid, (Any, UInt), a, delta)
_growend!(a::Vector, delta::Integer) =
ccall(:jl_array_grow_end, Cvoid, (Any, UInt), a, delta)
_growat!(a::Vector, i::Integer, delta::Integer) =
ccall(:jl_array_grow_at, Cvoid, (Any, Int, UInt), a, i - 1, delta)
# efficiently delete part of an array
_deletebeg!(a::Vector, delta::Integer) =
ccall(:jl_array_del_beg, Cvoid, (Any, UInt), a, delta)
_deleteend!(a::Vector, delta::Integer) =
ccall(:jl_array_del_end, Cvoid, (Any, UInt), a, delta)
_deleteat!(a::Vector, i::Integer, delta::Integer) =
ccall(:jl_array_del_at, Cvoid, (Any, Int, UInt), a, i - 1, delta)
## Dequeue functionality ##
"""
push!(collection, items...) -> collection
Insert one or more `items` at the end of `collection`.
# Examples
```jldoctest
julia> push!([1, 2, 3], 4, 5, 6)
6-element Array{Int64,1}:
1
2
3
4
5
6
```
Use [`append!`](@ref) to add all the elements of another collection to
`collection`. The result of the preceding example is equivalent to `append!([1, 2, 3], [4,
5, 6])`.
"""
function push! end
function push!(a::Array{T,1}, item) where T
# convert first so we don't grow the array if the assignment won't work
itemT = convert(T, item)
_growend!(a, 1)
a[end] = itemT
return a
end
function push!(a::Array{Any,1}, @nospecialize item)
_growend!(a, 1)
arrayset(true, a, item, length(a))
return a
end
"""
append!(collection, collection2) -> collection.
Add the elements of `collection2` to the end of `collection`.
# Examples
```jldoctest
julia> append!([1],[2,3])
3-element Array{Int64,1}:
1
2
3
julia> append!([1, 2, 3], [4, 5, 6])
6-element Array{Int64,1}:
1
2
3
4
5
6
```
Use [`push!`](@ref) to add individual items to `collection` which are not already
themselves in another collection. The result of the preceding example is equivalent to
`push!([1, 2, 3], 4, 5, 6)`.
"""
function append!(a::Array{<:Any,1}, items::AbstractVector)
itemindices = eachindex(items)
n = length(itemindices)
_growend!(a, n)
copyto!(a, length(a)-n+1, items, first(itemindices), n)
return a
end
append!(a::Vector, iter) = _append!(a, IteratorSize(iter), iter)
push!(a::Vector, iter...) = append!(a, iter)
function _append!(a, ::Union{HasLength,HasShape}, iter)
@assert !has_offset_axes(a)
n = length(a)
resize!(a, n+length(iter))
@inbounds for (i,item) in zip(n+1:length(a), iter)
a[i] = item
end
a
end
function _append!(a, ::IteratorSize, iter)
for item in iter
push!(a, item)
end
a
end
"""
prepend!(a::Vector, items) -> collection
Insert the elements of `items` to the beginning of `a`.
# Examples
```jldoctest
julia> prepend!([3],[1,2])
3-element Array{Int64,1}:
1
2
3
```
"""
function prepend! end
function prepend!(a::Array{<:Any,1}, items::AbstractVector)
itemindices = eachindex(items)
n = length(itemindices)
_growbeg!(a, n)
if a === items
copyto!(a, 1, items, n+1, n)
else
copyto!(a, 1, items, first(itemindices), n)
end
return a
end
prepend!(a::Vector, iter) = _prepend!(a, IteratorSize(iter), iter)
pushfirst!(a::Vector, iter...) = prepend!(a, iter)
function _prepend!(a, ::Union{HasLength,HasShape}, iter)
@assert !has_offset_axes(a)
n = length(iter)
_growbeg!(a, n)
i = 0
for item in iter
@inbounds a[i += 1] = item
end
a
end
function _prepend!(a, ::IteratorSize, iter)
n = 0
for item in iter
n += 1
pushfirst!(a, item)
end
reverse!(a, 1, n)
a
end
"""
resize!(a::Vector, n::Integer) -> Vector
Resize `a` to contain `n` elements. If `n` is smaller than the current collection
length, the first `n` elements will be retained. If `n` is larger, the new elements are not
guaranteed to be initialized.
# Examples
```jldoctest
julia> resize!([6, 5, 4, 3, 2, 1], 3)
3-element Array{Int64,1}:
6
5
4
julia> a = resize!([6, 5, 4, 3, 2, 1], 8);
julia> length(a)
8
julia> a[1:6]
6-element Array{Int64,1}:
6
5
4
3
2
1
```
"""
function resize!(a::Vector, nl::Integer)
l = length(a)
if nl > l
_growend!(a, nl-l)
elseif nl != l
if nl < 0
throw(ArgumentError("new length must be ≥ 0"))
end
_deleteend!(a, l-nl)
end
return a
end
"""
sizehint!(s, n)
Suggest that collection `s` reserve capacity for at least `n` elements. This can improve performance.
"""
function sizehint! end
function sizehint!(a::Vector, sz::Integer)
ccall(:jl_array_sizehint, Cvoid, (Any, UInt), a, sz)
a
end
"""
pop!(collection) -> item
Remove an item in `collection` and return it. If `collection` is an
ordered container, the last item is returned.
# Examples
```jldoctest
julia> A=[1, 2, 3]
3-element Array{Int64,1}:
1
2
3
julia> pop!(A)
3
julia> A
2-element Array{Int64,1}:
1
2
julia> S = Set([1, 2])
Set([2, 1])
julia> pop!(S)
2
julia> S
Set([1])
julia> pop!(Dict(1=>2))
1 => 2
```
"""
function pop!(a::Vector)
if isempty(a)
throw(ArgumentError("array must be non-empty"))
end
item = a[end]
_deleteend!(a, 1)
return item
end
"""
pushfirst!(collection, items...) -> collection
Insert one or more `items` at the beginning of `collection`.
# Examples
```jldoctest
julia> pushfirst!([1, 2, 3, 4], 5, 6)
6-element Array{Int64,1}:
5
6
1
2
3
4
```
"""
function pushfirst!(a::Array{T,1}, item) where T
item = convert(T, item)
_growbeg!(a, 1)
a[1] = item
return a
end
"""
popfirst!(collection) -> item
Remove the first `item` from `collection`.
# Examples
```jldoctest
julia> A = [1, 2, 3, 4, 5, 6]
6-element Array{Int64,1}:
1
2
3
4
5
6
julia> popfirst!(A)
1
julia> A
5-element Array{Int64,1}:
2
3
4
5
6
```
"""
function popfirst!(a::Vector)
if isempty(a)
throw(ArgumentError("array must be non-empty"))
end
item = a[1]
_deletebeg!(a, 1)
return item
end
"""
insert!(a::Vector, index::Integer, item)
Insert an `item` into `a` at the given `index`. `index` is the index of `item` in
the resulting `a`.
# Examples
```jldoctest
julia> insert!([6, 5, 4, 2, 1], 4, 3)
6-element Array{Int64,1}:
6
5
4
3
2
1
```
"""
function insert!(a::Array{T,1}, i::Integer, item) where T
# Throw convert error before changing the shape of the array
_item = convert(T, item)
_growat!(a, i, 1)
# _growat! already did bound check
@inbounds a[i] = _item
return a
end
"""
deleteat!(a::Vector, i::Integer)
Remove the item at the given `i` and return the modified `a`. Subsequent items
are shifted to fill the resulting gap.
# Examples
```jldoctest
julia> deleteat!([6, 5, 4, 3, 2, 1], 2)
5-element Array{Int64,1}:
6
4
3
2
1
```
"""
deleteat!(a::Vector, i::Integer) = (_deleteat!(a, i, 1); a)
function deleteat!(a::Vector, r::UnitRange{<:Integer})
n = length(a)
isempty(r) || _deleteat!(a, first(r), length(r))
return a
end
"""
deleteat!(a::Vector, inds)
Remove the items at the indices given by `inds`, and return the modified `a`.
Subsequent items are shifted to fill the resulting gap.
`inds` can be either an iterator or a collection of sorted and unique integer indices,
or a boolean vector of the same length as `a` with `true` indicating entries to delete.
# Examples
```jldoctest
julia> deleteat!([6, 5, 4, 3, 2, 1], 1:2:5)
3-element Array{Int64,1}:
5
3
1
julia> deleteat!([6, 5, 4, 3, 2, 1], [true, false, true, false, true, false])
3-element Array{Int64,1}:
5
3
1
julia> deleteat!([6, 5, 4, 3, 2, 1], (2, 2))
ERROR: ArgumentError: indices must be unique and sorted
Stacktrace:
[...]
```
"""
deleteat!(a::Vector, inds) = _deleteat!(a, inds)
deleteat!(a::Vector, inds::AbstractVector) = _deleteat!(a, to_indices(a, (inds,))[1])
function _deleteat!(a::Vector, inds)
n = length(a)
y = iterate(inds)
y === nothing && return a
n == 0 && throw(BoundsError(a, inds))
(p, s) = y
q = p+1
while true
y = iterate(inds, s)
y === nothing && break
(i,s) = y
if !(q <= i <= n)
if i < q
throw(ArgumentError("indices must be unique and sorted"))
else
throw(BoundsError())
end
end
while q < i
@inbounds a[p] = a[q]
p += 1; q += 1
end
q = i+1
end
while q <= n
@inbounds a[p] = a[q]
p += 1; q += 1
end
_deleteend!(a, n-p+1)
return a
end
# Simpler and more efficient version for logical indexing
function deleteat!(a::Vector, inds::AbstractVector{Bool})
n = length(a)
length(inds) == n || throw(BoundsError(a, inds))
p = 1
for (q, i) in enumerate(inds)
@inbounds a[p] = a[q]
p += !i
end
_deleteend!(a, n-p+1)
return a
end
const _default_splice = []
"""
splice!(a::Vector, index::Integer, [replacement]) -> item
Remove the item at the given index, and return the removed item.
Subsequent items are shifted left to fill the resulting gap.
If specified, replacement values from an ordered
collection will be spliced in place of the removed item.
# Examples
```jldoctest splice!
julia> A = [6, 5, 4, 3, 2, 1]; splice!(A, 5)
2
julia> A
5-element Array{Int64,1}:
6
5
4
3
1
julia> splice!(A, 5, -1)
1
julia> A
5-element Array{Int64,1}:
6
5
4
3
-1
julia> splice!(A, 1, [-1, -2, -3])
6
julia> A
7-element Array{Int64,1}:
-1
-2
-3
5
4
3
-1
```
To insert `replacement` before an index `n` without removing any items, use
`splice!(collection, n:n-1, replacement)`.
"""
function splice!(a::Vector, i::Integer, ins=_default_splice)
v = a[i]
m = length(ins)
if m == 0
_deleteat!(a, i, 1)
elseif m == 1
a[i] = ins[1]
else
_growat!(a, i, m-1)
k = 1
for x in ins
a[i+k-1] = x
k += 1
end
end
return v
end
"""
splice!(a::Vector, range, [replacement]) -> items
Remove items in the specified index range, and return a collection containing
the removed items.
Subsequent items are shifted left to fill the resulting gap.
If specified, replacement values from an ordered collection will be spliced in
place of the removed items.
To insert `replacement` before an index `n` without removing any items, use
`splice!(collection, n:n-1, replacement)`.
# Examples
```jldoctest splice!
julia> splice!(A, 4:3, 2)
0-element Array{Int64,1}
julia> A
8-element Array{Int64,1}:
-1
-2
-3
2
5
4
3
-1
```
"""
function splice!(a::Vector, r::UnitRange{<:Integer}, ins=_default_splice)
v = a[r]
m = length(ins)
if m == 0
deleteat!(a, r)
return v
end
n = length(a)
f = first(r)
l = last(r)
d = length(r)
if m < d
delta = d - m
_deleteat!(a, (f - 1 < n - l) ? f : (l - delta + 1), delta)
elseif m > d
_growat!(a, (f - 1 < n - l) ? f : (l + 1), m - d)
end
k = 1
for x in ins
a[f+k-1] = x
k += 1
end
return v
end
function empty!(a::Vector)
_deleteend!(a, length(a))
return a
end
_memcmp(a, b, len) = ccall(:memcmp, Int32, (Ptr{Cvoid}, Ptr{Cvoid}, Csize_t), a, b, len) % Int
# use memcmp for cmp on byte arrays
function cmp(a::Array{UInt8,1}, b::Array{UInt8,1})
c = _memcmp(a, b, min(length(a),length(b)))
return c < 0 ? -1 : c > 0 ? +1 : cmp(length(a),length(b))
end
const BitIntegerArray{N} = Union{map(T->Array{T,N}, BitInteger_types)...} where N
# use memcmp for == on bit integer types
==(a::Arr, b::Arr) where {Arr <: BitIntegerArray} =
size(a) == size(b) && 0 == _memcmp(a, b, sizeof(eltype(Arr)) * length(a))
# this is ~20% faster than the generic implementation above for very small arrays
function ==(a::Arr, b::Arr) where Arr <: BitIntegerArray{1}
len = length(a)
len == length(b) && 0 == _memcmp(a, b, sizeof(eltype(Arr)) * len)
end
"""
reverse(v [, start=1 [, stop=length(v) ]] )
Return a copy of `v` reversed from start to stop. See also [`Iterators.reverse`](@ref)
for reverse-order iteration without making a copy.
# Examples
```jldoctest
julia> A = Vector(1:5)
5-element Array{Int64,1}:
1
2
3
4
5
julia> reverse(A)
5-element Array{Int64,1}:
5
4
3
2
1
julia> reverse(A, 1, 4)
5-element Array{Int64,1}:
4
3
2
1
5
julia> reverse(A, 3, 5)
5-element Array{Int64,1}:
1
2
5
4
3
```
"""
function reverse(A::AbstractVector, s=first(LinearIndices(A)), n=last(LinearIndices(A)))
B = similar(A)
for i = first(LinearIndices(A)):s-1
B[i] = A[i]
end
for i = s:n
B[i] = A[n+s-i]
end
for i = n+1:last(LinearIndices(A))
B[i] = A[i]
end
return B
end
# to resolve ambiguity with reverse(A; dims)
reverse(A::Vector) = invoke(reverse, Tuple{AbstractVector}, A)
function reverseind(a::AbstractVector, i::Integer)
li = LinearIndices(a)
first(li) + last(li) - i
end
"""
reverse!(v [, start=1 [, stop=length(v) ]]) -> v
In-place version of [`reverse`](@ref).
# Examples
```jldoctest
julia> A = Vector(1:5)
5-element Array{Int64,1}:
1
2
3
4
5
julia> reverse!(A);
julia> A
5-element Array{Int64,1}:
5
4
3
2
1
```
"""
function reverse!(v::AbstractVector, s=first(LinearIndices(v)), n=last(LinearIndices(v)))
liv = LinearIndices(v)
if n <= s # empty case; ok
elseif !(first(liv) ≤ s ≤ last(liv))
throw(BoundsError(v, s))
elseif !(first(liv) ≤ n ≤ last(liv))
throw(BoundsError(v, n))
end
r = n
@inbounds for i in s:div(s+n-1, 2)
v[i], v[r] = v[r], v[i]
r -= 1
end
return v
end
# concatenations of homogeneous combinations of vectors, horizontal and vertical
vcat() = Vector{Any}()
hcat() = Vector{Any}()
function hcat(V::Vector{T}...) where T
height = length(V[1])
for j = 2:length(V)
if length(V[j]) != height
throw(DimensionMismatch("vectors must have same lengths"))
end
end
return [ V[j][i]::T for i=1:length(V[1]), j=1:length(V) ]
end
function vcat(arrays::Vector{T}...) where T
n = 0
for a in arrays
n += length(a)
end
arr = Vector{T}(undef, n)
ptr = pointer(arr)
if isbitstype(T)
elsz = Core.sizeof(T)
elseif isbitsunion(T)
elsz = bitsunionsize(T)
selptr = ccall(:jl_array_typetagdata, Ptr{UInt8}, (Any,), arr)
else
elsz = Core.sizeof(Ptr{Cvoid})
end
t = @_gc_preserve_begin arr
for a in arrays
na = length(a)
nba = na * elsz
if isbitstype(T)
ccall(:memcpy, Ptr{Cvoid}, (Ptr{Cvoid}, Ptr{Cvoid}, UInt),
ptr, a, nba)
elseif isbitsunion(T)
ccall(:memcpy, Ptr{Cvoid}, (Ptr{Cvoid}, Ptr{Cvoid}, UInt),
ptr, a, nba)
# copy selector bytes
ccall(:memcpy, Ptr{Cvoid}, (Ptr{Cvoid}, Ptr{Cvoid}, UInt),
selptr, ccall(:jl_array_typetagdata, Ptr{UInt8}, (Any,), a), na)
selptr += na
else
ccall(:jl_array_ptr_copy, Cvoid, (Any, Ptr{Cvoid}, Any, Ptr{Cvoid}, Int),
arr, ptr, a, pointer(a), na)
end
ptr += nba
end
@_gc_preserve_end t
return arr
end
_cat(n::Integer, x::Integer...) = reshape([x...], (ntuple(x->1, n-1)..., length(x)))
## find ##
"""
findnext(A, i)
Find the next index after or including `i` of a `true` element of `A`,
or `nothing` if not found.
Indices are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [false, false, true, false]
4-element Array{Bool,1}:
false
false
true
false
julia> findnext(A, 1)
3
julia> findnext(A, 4) # returns nothing, but not printed in the REPL
julia> A = [false false; true false]
2×2 Array{Bool,2}:
false false
true false
julia> findnext(A, CartesianIndex(1, 1))
CartesianIndex(2, 1)
```
"""
function findnext(A, start)
l = last(keys(A))
i = start
while i <= l
if A[i]
return i
end
i = nextind(A, i)
end
return nothing
end
"""
findfirst(A)
Return the index or key of the first `true` value in `A`.
Return `nothing` if no such value is found.
To search for other kinds of values, pass a predicate as the first argument.
Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [false, false, true, false]
4-element Array{Bool,1}:
false
false
true
false
julia> findfirst(A)
3
julia> findfirst(falses(3)) # returns nothing, but not printed in the REPL
julia> A = [false false; true false]
2×2 Array{Bool,2}:
false false
true false
julia> findfirst(A)
CartesianIndex(2, 1)
```
"""
function findfirst(A)
for (i, a) in pairs(A)
if a
return i
end
end
return nothing
end
# Needed for bootstrap, and allows defining only an optimized findnext method
findfirst(A::Union{AbstractArray, AbstractString}) = findnext(A, first(keys(A)))
"""
findnext(predicate::Function, A, i)
Find the next index after or including `i` of an element of `A`
for which `predicate` returns `true`, or `nothing` if not found.
Indices are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [1, 4, 2, 2];
julia> findnext(isodd, A, 1)
1
julia> findnext(isodd, A, 2) # returns nothing, but not printed in the REPL
julia> A = [1 4; 2 2];
julia> findnext(isodd, A, CartesianIndex(1, 1))
CartesianIndex(1, 1)
```
"""
function findnext(testf::Function, A, start)
l = last(keys(A))
i = start
while i <= l
if testf(A[i])
return i
end
i = nextind(A, i)
end
return nothing
end
"""
findfirst(predicate::Function, A)
Return the index or key of the first element of `A` for which `predicate` returns `true`.
Return `nothing` if there is no such element.
Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [1, 4, 2, 2]
4-element Array{Int64,1}:
1
4
2
2
julia> findfirst(iseven, A)
2
julia> findfirst(x -> x>10, A) # returns nothing, but not printed in the REPL
julia> findfirst(isequal(4), A)
2
julia> A = [1 4; 2 2]
2×2 Array{Int64,2}:
1 4
2 2
julia> findfirst(iseven, A)
CartesianIndex(2, 1)
```
"""
function findfirst(testf::Function, A)
for (i, a) in pairs(A)
testf(a) && return i
end
return nothing
end
# Needed for bootstrap, and allows defining only an optimized findnext method
findfirst(testf::Function, A::Union{AbstractArray, AbstractString}) =
findnext(testf, A, first(keys(A)))
"""
findprev(A, i)
Find the previous index before or including `i` of a `true` element of `A`,
or `nothing` if not found.
Indices are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [false, false, true, true]
4-element Array{Bool,1}:
false
false
true
true
julia> findprev(A, 3)
3
julia> findprev(A, 1) # returns nothing, but not printed in the REPL
julia> A = [false false; true true]
2×2 Array{Bool,2}:
false false
true true
julia> findprev(A, CartesianIndex(2, 1))
CartesianIndex(2, 1)
```
"""
function findprev(A, start)
i = start
while i >= first(keys(A))
A[i] && return i
i = prevind(A, i)
end
return nothing
end
"""
findlast(A)
Return the index or key of the last `true` value in `A`.
Return `nothing` if there is no `true` value in `A`.
Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [true, false, true, false]
4-element Array{Bool,1}:
true
false
true
false
julia> findlast(A)
3
julia> A = falses(2,2);
julia> findlast(A) # returns nothing, but not printed in the REPL
julia> A = [true false; true false]
2×2 Array{Bool,2}:
true false
true false
julia> findlast(A)
CartesianIndex(2, 1)
```
"""
function findlast(A)
for (i, a) in Iterators.reverse(pairs(A))
if a
return i
end
end
return nothing
end
# Needed for bootstrap, and allows defining only an optimized findprev method
findlast(A::Union{AbstractArray, AbstractString}) = findprev(A, last(keys(A)))
"""
findprev(predicate::Function, A, i)
Find the previous index before or including `i` of an element of `A`
for which `predicate` returns `true`, or `nothing` if not found.
Indices are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [4, 6, 1, 2]
4-element Array{Int64,1}:
4
6
1
2
julia> findprev(isodd, A, 1) # returns nothing, but not printed in the REPL
julia> findprev(isodd, A, 3)
3
julia> A = [4 6; 1 2]
2×2 Array{Int64,2}:
4 6
1 2
julia> findprev(isodd, A, CartesianIndex(1, 2))
CartesianIndex(2, 1)
```
"""
function findprev(testf::Function, A, start)
i = start
while i >= first(keys(A))
testf(A[i]) && return i
i = prevind(A, i)
end
return nothing
end
"""
findlast(predicate::Function, A)
Return the index or key of the last element of `A` for which `predicate` returns `true`.
Return `nothing` if there is no such element.
Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [1, 2, 3, 4]
4-element Array{Int64,1}:
1
2
3
4
julia> findlast(isodd, A)
3
julia> findlast(x -> x > 5, A) # returns nothing, but not printed in the REPL
julia> A = [1 2; 3 4]
2×2 Array{Int64,2}:
1 2
3 4
julia> findlast(isodd, A)
CartesianIndex(2, 1)
```
"""
function findlast(testf::Function, A)
for (i, a) in Iterators.reverse(pairs(A))
testf(a) && return i
end
return nothing
end
# Needed for bootstrap, and allows defining only an optimized findprev method
findlast(testf::Function, A::Union{AbstractArray, AbstractString}) =
findprev(testf, A, last(keys(A)))
"""
findall(f::Function, A)
Return a vector `I` of the indices or keys of `A` where `f(A[I])` returns `true`.
If there are no such elements of `A`, return an empty array.
Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> x = [1, 3, 4]
3-element Array{Int64,1}:
1
3
4
julia> findall(isodd, x)
2-element Array{Int64,1}:
1
2
julia> A = [1 2 0; 3 4 0]
2×3 Array{Int64,2}:
1 2 0
3 4 0
julia> findall(isodd, A)
2-element Array{CartesianIndex{2},1}:
CartesianIndex(1, 1)
CartesianIndex(2, 1)
julia> findall(!iszero, A)
4-element Array{CartesianIndex{2},1}:
CartesianIndex(1, 1)
CartesianIndex(2, 1)
CartesianIndex(1, 2)
CartesianIndex(2, 2)
julia> d = Dict(:A => 10, :B => -1, :C => 0)
Dict{Symbol,Int64} with 3 entries:
:A => 10
:B => -1
:C => 0
julia> findall(x -> x >= 0, d)
2-element Array{Symbol,1}:
:A
:C
```
"""
findall(testf::Function, A) = collect(first(p) for p in pairs(A) if testf(last(p)))
"""
findall(A)
Return a vector `I` of the `true` indices or keys of `A`.
If there are no such elements of `A`, return an empty array.
To search for other kinds of values, pass a predicate as the first argument.
Indices or keys are of the same type as those returned by [`keys(A)`](@ref)
and [`pairs(A)`](@ref).
# Examples
```jldoctest
julia> A = [true, false, false, true]
4-element Array{Bool,1}:
true
false
false
true
julia> findall(A)
2-element Array{Int64,1}:
1
4
julia> A = [true false; false true]
2×2 Array{Bool,2}:
true false
false true
julia> findall(A)
2-element Array{CartesianIndex{2},1}:
CartesianIndex(1, 1)
CartesianIndex(2, 2)
julia> findall(falses(3))
0-element Array{Int64,1}
```
"""
function findall(A)
collect(first(p) for p in pairs(A) if last(p))
end
# Allocating result upfront is faster (possible only when collection can be iterated twice)
function findall(A::AbstractArray{Bool})
n = count(A)
I = Vector{eltype(keys(A))}(undef, n)
cnt = 1
for (i,a) in pairs(A)
if a
I[cnt] = i
cnt += 1
end
end
I
end
findall(x::Bool) = x ? [1] : Vector{Int}()
findall(testf::Function, x::Number) = testf(x) ? [1] : Vector{Int}()
findall(p::Fix2{typeof(in)}, x::Number) = x in p.x ? [1] : Vector{Int}()
"""
findmax(itr) -> (x, index)
Return the maximum element of the collection `itr` and its index. If there are multiple
maximal elements, then the first one will be returned.
If any data element is `NaN`, this element is returned.
The result is in line with `max`.
The collection must not be empty.
# Examples
```jldoctest
julia> findmax([8,0.1,-9,pi])
(8.0, 1)
julia> findmax([1,7,7,6])
(7, 2)
julia> findmax([1,7,7,NaN])
(NaN, 4)
```
"""
findmax(a) = _findmax(a, :)
function _findmax(a, ::Colon)
p = pairs(a)
y = iterate(p)
if y === nothing
throw(ArgumentError("collection must be non-empty"))
end
(mi, m), s = y
i = mi
while true
y = iterate(p, s)
y === nothing && break
m != m && break
(i, ai), s = y
if ai != ai || isless(m, ai)
m = ai
mi = i
end
end
return (m, mi)
end
"""
findmin(itr) -> (x, index)
Return the minimum element of the collection `itr` and its index. If there are multiple
minimal elements, then the first one will be returned.
If any data element is `NaN`, this element is returned.
The result is in line with `min`.
The collection must not be empty.
# Examples
```jldoctest
julia> findmin([8,0.1,-9,pi])
(-9.0, 3)
julia> findmin([7,1,1,6])
(1, 2)
julia> findmin([7,1,1,NaN])
(NaN, 4)
```
"""
findmin(a) = _findmin(a, :)
function _findmin(a, ::Colon)
p = pairs(a)
y = iterate(p)
if y === nothing
throw(ArgumentError("collection must be non-empty"))
end
(mi, m), s = y
i = mi
while true
y = iterate(p, s)
y === nothing && break
m != m && break
(i, ai), s = y
if ai != ai || isless(ai, m)
m = ai
mi = i
end
end
return (m, mi)
end
"""
argmax(itr) -> Integer
Return the index of the maximum element in a collection. If there are multiple maximal
elements, then the first one will be returned.
The collection must not be empty.
# Examples
```jldoctest
julia> argmax([8,0.1,-9,pi])
1
julia> argmax([1,7,7,6])
2
julia> argmax([1,7,7,NaN])
4
```
"""
argmax(a) = findmax(a)[2]
"""
argmin(itr) -> Integer
Return the index of the minimum element in a collection. If there are multiple minimal
elements, then the first one will be returned.
The collection must not be empty.
# Examples
```jldoctest
julia> argmin([8,0.1,-9,pi])
3
julia> argmin([7,1,1,6])
2
julia> argmin([7,1,1,NaN])
4
```
"""
argmin(a) = findmin(a)[2]
# similar to Matlab's ismember
"""
indexin(a, b)
Return an array containing the first index in `b` for
each value in `a` that is a member of `b`. The output
array contains `nothing` wherever `a` is not a member of `b`.
# Examples
```jldoctest
julia> a = ['a', 'b', 'c', 'b', 'd', 'a'];
julia> b = ['a', 'b', 'c'];
julia> indexin(a, b)
6-element Array{Union{Nothing, Int64},1}:
1
2
3
2
nothing
1
julia> indexin(b, a)
3-element Array{Union{Nothing, Int64},1}:
1
2
3
```
"""
function indexin(a, b::AbstractArray)
inds = keys(b)
bdict = Dict{eltype(b),eltype(inds)}()
for (val, ind) in zip(b, inds)
get!(bdict, val, ind)
end
return Union{eltype(inds), Nothing}[
get(bdict, i, nothing) for i in a
]
end
function _findin(a::Union{AbstractArray, Tuple}, b)
ind = Vector{eltype(keys(a))}()
bset = Set(b)
@inbounds for (i,ai) in pairs(a)
ai in bset && push!(ind, i)
end
ind
end
# If two collections are already sorted, _findin can be computed with
# a single traversal of the two collections. This is much faster than
# using a hash table (although it has the same complexity).
function _sortedfindin(v::Union{AbstractArray, Tuple}, w)
viter, witer = keys(v), eachindex(w)
out = eltype(viter)[]
vy, wy = iterate(viter), iterate(witer)
if vy === nothing || wy === nothing
return out
end
viteri, i = vy
witerj, j = wy
@inbounds begin
vi, wj = v[viteri], w[witerj]
while true
if isless(vi, wj)
vy = iterate(viter, i)
if vy === nothing
break
end
viteri, i = vy
vi = v[viteri]
elseif isless(wj, vi)
wy = iterate(witer, j)
if wy === nothing
break
end
witerj, j = wy
wj = w[witerj]
else
push!(out, viteri)
vy = iterate(viter, i)
if vy === nothing
break
end
# We only increment the v iterator because v can have
# repeated matches to a single value in w
viteri, i = vy
vi = v[viteri]
end
end
end
return out
end
function findall(pred::Fix2{typeof(in),<:Union{Array{<:Real},Real}}, x::Array{<:Real})
if issorted(x, Sort.Forward) && issorted(pred.x, Sort.Forward)
return _sortedfindin(x, pred.x)
else
return _findin(x, pred.x)
end
end
# issorted fails for some element types so the method above has to be restricted
# to element with isless/< defined.
findall(pred::Fix2{typeof(in)}, x::Union{AbstractArray, Tuple}) = _findin(x, pred.x)
# Copying subregions
function indcopy(sz::Dims, I::Vector)
n = length(I)
s = sz[n]
for i = n+1:length(sz)
s *= sz[i]
end
dst = eltype(I)[_findin(I[i], i < n ? (1:sz[i]) : (1:s)) for i = 1:n]
src = eltype(I)[I[i][_findin(I[i], i < n ? (1:sz[i]) : (1:s))] for i = 1:n]
dst, src
end
function indcopy(sz::Dims, I::Tuple{Vararg{RangeIndex}})
n = length(I)
s = sz[n]
for i = n+1:length(sz)
s *= sz[i]
end
dst::typeof(I) = ntuple(i-> _findin(I[i], i < n ? (1:sz[i]) : (1:s)), n)::typeof(I)
src::typeof(I) = ntuple(i-> I[i][_findin(I[i], i < n ? (1:sz[i]) : (1:s))], n)::typeof(I)
dst, src
end
## Filter ##
"""
filter(f, a::AbstractArray)
Return a copy of `a`, removing elements for which `f` is `false`.
The function `f` is passed one argument.
# Examples
```jldoctest
julia> a = 1:10
1:10
julia> filter(isodd, a)
5-element Array{Int64,1}:
1
3
5
7
9
```
"""
filter(f, As::AbstractArray) = As[map(f, As)::AbstractArray{Bool}]
"""
filter!(f, a::AbstractVector)
Update `a`, removing elements for which `f` is `false`.
The function `f` is passed one argument.
# Examples
```jldoctest
julia> filter!(isodd, Vector(1:10))
5-element Array{Int64,1}:
1
3
5
7
9
```
"""
function filter!(f, a::AbstractVector)
idx = eachindex(a)
y = iterate(idx)
y === nothing && return a
i, state = y
for acurr in a
if f(acurr)
@inbounds a[i] = acurr
y = iterate(idx, state)
y === nothing && (i += 1; break)
i, state = y
end
end
deleteat!(a, i:last(idx))
return a
end
filter(f, a::Vector) = mapfilter(f, push!, a, empty(a))
# set-like operators for vectors
# These are moderately efficient, preserve order, and remove dupes.
_unique_filter!(pred, update!, state) = function (x)
if pred(x, state)
update!(state, x)
true
else
false
end
end
_grow_filter!(seen) = _unique_filter!(∉, push!, seen)
_shrink_filter!(keep) = _unique_filter!(∈, pop!, keep)
function _grow!(pred!, v::AbstractVector, itrs)
filter!(pred!, v) # uniquify v
for itr in itrs
mapfilter(pred!, push!, itr, v)
end
return v
end
union!(v::AbstractVector{T}, itrs...) where {T} =
_grow!(_grow_filter!(sizehint!(Set{T}(), length(v))), v, itrs)
symdiff!(v::AbstractVector{T}, itrs...) where {T} =
_grow!(_shrink_filter!(symdiff!(Set{T}(), v, itrs...)), v, itrs)
function _shrink!(shrinker!, v::AbstractVector, itrs)
seen = Set{eltype(v)}()
filter!(_grow_filter!(seen), v)
shrinker!(seen, itrs...)
filter!(_in(seen), v)
end
intersect!(v::AbstractVector, itrs...) = _shrink!(intersect!, v, itrs)
setdiff!( v::AbstractVector, itrs...) = _shrink!(setdiff!, v, itrs)
vectorfilter(f, v::AbstractVector) = filter(f, v) # TODO: do we want this special case?
vectorfilter(f, v) = [x for x in v if f(x)]
function _shrink(shrinker!, itr, itrs)
keep = shrinker!(Set(itr), itrs...)
vectorfilter(_shrink_filter!(keep), itr)
end
intersect(itr, itrs...) = _shrink(intersect!, itr, itrs)
setdiff( itr, itrs...) = _shrink(setdiff!, itr, itrs)