https://github.com/JuliaLang/julia
Tip revision: 67e6911aefee5e100c36d51d58cadd7e05ac8c43 authored by Shuhei Kadowaki on 16 July 2022, 00:58:11 UTC
type stable `instanceof_tfunc`
type stable `instanceof_tfunc`
Tip revision: 67e6911
abstractarray.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
## Basic functions ##
"""
AbstractArray{T,N}
Supertype for `N`-dimensional arrays (or array-like types) with elements of type `T`.
[`Array`](@ref) and other types are subtypes of this. See the manual section on the
[`AbstractArray` interface](@ref man-interface-array).
See also: [`AbstractVector`](@ref), [`AbstractMatrix`](@ref), [`eltype`](@ref), [`ndims`](@ref).
"""
AbstractArray
convert(::Type{T}, a::T) where {T<:AbstractArray} = a
convert(::Type{AbstractArray{T}}, a::AbstractArray) where {T} = AbstractArray{T}(a)::AbstractArray{T}
convert(::Type{AbstractArray{T,N}}, a::AbstractArray{<:Any,N}) where {T,N} = AbstractArray{T,N}(a)::AbstractArray{T,N}
"""
size(A::AbstractArray, [dim])
Return a tuple containing the dimensions of `A`. Optionally you can specify a
dimension to just get the length of that dimension.
Note that `size` may not be defined for arrays with non-standard indices, in which case [`axes`](@ref)
may be useful. See the manual chapter on [arrays with custom indices](@ref man-custom-indices).
See also: [`length`](@ref), [`ndims`](@ref), [`eachindex`](@ref), [`sizeof`](@ref).
# Examples
```jldoctest
julia> A = fill(1, (2,3,4));
julia> size(A)
(2, 3, 4)
julia> size(A, 2)
3
```
"""
size(t::AbstractArray{T,N}, d) where {T,N} = d::Integer <= N ? size(t)[d] : 1
"""
axes(A, d)
Return the valid range of indices for array `A` along dimension `d`.
See also [`size`](@ref), and the manual chapter on [arrays with custom indices](@ref man-custom-indices).
# Examples
```jldoctest
julia> A = fill(1, (5,6,7));
julia> axes(A, 2)
Base.OneTo(6)
julia> axes(A, 4) == 1:1 # all dimensions d > ndims(A) have size 1
true
```
# Usage note
Each of the indices has to be an `AbstractUnitRange{<:Integer}`, but at the same time can be
a type that uses custom indices. So, for example, if you need a subset, use generalized
indexing constructs like `begin`/`end` or [`firstindex`](@ref)/[`lastindex`](@ref):
```julia
ix = axes(v, 1)
ix[2:end] # will work for eg Vector, but may fail in general
ix[(begin+1):end] # works for generalized indexes
```
"""
function axes(A::AbstractArray{T,N}, d) where {T,N}
@inline
d::Integer <= N ? axes(A)[d] : OneTo(1)
end
"""
axes(A)
Return the tuple of valid indices for array `A`.
See also: [`size`](@ref), [`keys`](@ref), [`eachindex`](@ref).
# Examples
```jldoctest
julia> A = fill(1, (5,6,7));
julia> axes(A)
(Base.OneTo(5), Base.OneTo(6), Base.OneTo(7))
```
"""
function axes(A)
@inline
map(unchecked_oneto, size(A))
end
"""
has_offset_axes(A)
has_offset_axes(A, B, ...)
Return `true` if the indices of `A` start with something other than 1 along any axis.
If multiple arguments are passed, equivalent to `has_offset_axes(A) || has_offset_axes(B) || ...`.
See also [`require_one_based_indexing`](@ref).
"""
has_offset_axes() = false
has_offset_axes(A) = _any_tuple(x->Int(first(x))::Int != 1, false, axes(A)...)
has_offset_axes(A::AbstractVector) = Int(firstindex(A))::Int != 1 # improve performance of a common case (ranges)
has_offset_axes(::Colon) = false
has_offset_axes(::Array) = false
# note: this could call `any` directly if the compiler can infer it. We don't use _any_tuple
# here because it stops full elision in some cases (#49332) and we don't need handling of
# `missing` (has_offset_axes(A) always returns a Bool)
has_offset_axes(A, As...) = has_offset_axes(A) || has_offset_axes(As...)
"""
require_one_based_indexing(A::AbstractArray)
require_one_based_indexing(A,B...)
Throw an `ArgumentError` if the indices of any argument start with something other than `1` along any axis.
See also [`has_offset_axes`](@ref).
!!! compat "Julia 1.2"
This function requires at least Julia 1.2.
"""
require_one_based_indexing(A...) = !has_offset_axes(A...) || throw(ArgumentError("offset arrays are not supported but got an array with index other than 1"))
# Performance optimization: get rid of a branch on `d` in `axes(A, d)`
# for d=1. 1d arrays are heavily used, and the first dimension comes up
# in other applications.
axes1(A::AbstractArray{<:Any,0}) = OneTo(1)
axes1(A::AbstractArray) = (@inline; axes(A)[1])
axes1(iter) = oneto(length(iter))
"""
keys(a::AbstractArray)
Return an efficient array describing all valid indices for `a` arranged in the shape of `a` itself.
The keys of 1-dimensional arrays (vectors) are integers, whereas all other N-dimensional
arrays use [`CartesianIndex`](@ref) to describe their locations. Often the special array
types [`LinearIndices`](@ref) and [`CartesianIndices`](@ref) are used to efficiently
represent these arrays of integers and `CartesianIndex`es, respectively.
Note that the `keys` of an array might not be the most efficient index type; for maximum
performance use [`eachindex`](@ref) instead.
# Examples
```jldoctest
julia> keys([4, 5, 6])
3-element LinearIndices{1, Tuple{Base.OneTo{Int64}}}:
1
2
3
julia> keys([4 5; 6 7])
CartesianIndices((2, 2))
```
"""
keys(a::AbstractArray) = CartesianIndices(axes(a))
keys(a::AbstractVector) = LinearIndices(a)
"""
keytype(T::Type{<:AbstractArray})
keytype(A::AbstractArray)
Return the key type of an array. This is equal to the
[`eltype`](@ref) of the result of `keys(...)`, and is provided
mainly for compatibility with the dictionary interface.
# Examples
```jldoctest
julia> keytype([1, 2, 3]) == Int
true
julia> keytype([1 2; 3 4])
CartesianIndex{2}
```
!!! compat "Julia 1.2"
For arrays, this function requires at least Julia 1.2.
"""
keytype(a::AbstractArray) = keytype(typeof(a))
keytype(::Type{Union{}}, slurp...) = eltype(Union{})
keytype(A::Type{<:AbstractArray}) = CartesianIndex{ndims(A)}
keytype(A::Type{<:AbstractVector}) = Int
valtype(a::AbstractArray) = valtype(typeof(a))
valtype(::Type{Union{}}, slurp...) = eltype(Union{})
"""
valtype(T::Type{<:AbstractArray})
valtype(A::AbstractArray)
Return the value type of an array. This is identical to [`eltype`](@ref) and is
provided mainly for compatibility with the dictionary interface.
# Examples
```jldoctest
julia> valtype(["one", "two", "three"])
String
```
!!! compat "Julia 1.2"
For arrays, this function requires at least Julia 1.2.
"""
valtype(A::Type{<:AbstractArray}) = eltype(A)
prevind(::AbstractArray, i::Integer) = Int(i)-1
nextind(::AbstractArray, i::Integer) = Int(i)+1
"""
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.
See also: [`keytype`](@ref), [`typeof`](@ref).
# Examples
```jldoctest
julia> eltype(fill(1f0, (2,2)))
Float32
julia> eltype(fill(0x1, (2,2)))
UInt8
```
"""
eltype(::Type) = Any
eltype(::Type{Bottom}, slurp...) = throw(ArgumentError("Union{} does not have elements"))
eltype(x) = eltype(typeof(x))
eltype(::Type{<:AbstractArray{E}}) where {E} = @isdefined(E) ? E : Any
"""
elsize(type)
Compute the memory stride in bytes between consecutive elements of [`eltype`](@ref)
stored inside the given `type`, if the array elements are stored densely with a
uniform linear stride.
# Examples
```jldoctest
julia> Base.elsize(rand(Float32, 10))
4
```
"""
elsize(A::AbstractArray) = elsize(typeof(A))
"""
ndims(A::AbstractArray) -> Integer
Return the number of dimensions of `A`.
See also: [`size`](@ref), [`axes`](@ref).
# Examples
```jldoctest
julia> A = fill(1, (3,4,5));
julia> ndims(A)
3
```
"""
ndims(::AbstractArray{T,N}) where {T,N} = N::Int
ndims(::Type{<:AbstractArray{<:Any,N}}) where {N} = N::Int
ndims(::Type{Union{}}, slurp...) = throw(ArgumentError("Union{} does not have elements"))
"""
length(collection) -> Integer
Return the number of elements in the collection.
Use [`lastindex`](@ref) to get the last valid index of an indexable collection.
See also: [`size`](@ref), [`ndims`](@ref), [`eachindex`](@ref).
# Examples
```jldoctest
julia> length(1:5)
5
julia> length([1, 2, 3, 4])
4
julia> length([1 2; 3 4])
4
```
"""
length
"""
length(A::AbstractArray)
Return the number of elements in the array, defaults to `prod(size(A))`.
# Examples
```jldoctest
julia> length([1, 2, 3, 4])
4
julia> length([1 2; 3 4])
4
```
"""
length(t::AbstractArray) = (@inline; prod(size(t)))
# `eachindex` is mostly an optimization of `keys`
eachindex(itrs...) = keys(itrs...)
# eachindex iterates over all indices. IndexCartesian definitions are later.
eachindex(A::AbstractVector) = (@inline(); axes1(A))
@noinline function throw_eachindex_mismatch_indices(::IndexLinear, inds...)
throw(DimensionMismatch("all inputs to eachindex must have the same indices, got $(join(inds, ", ", " and "))"))
end
@noinline function throw_eachindex_mismatch_indices(::IndexCartesian, inds...)
throw(DimensionMismatch("all inputs to eachindex must have the same axes, got $(join(inds, ", ", " and "))"))
end
"""
eachindex(A...)
eachindex(::IndexStyle, A::AbstractArray...)
Create an iterable object for visiting each index of an `AbstractArray` `A` in an efficient
manner. For array types that have opted into fast linear indexing (like `Array`), this is
simply the range `1:length(A)` if they use 1-based indexing.
For array types that have not opted into fast linear indexing, a specialized Cartesian
range is typically returned to efficiently index into the array with indices specified
for every dimension.
In general `eachindex` accepts arbitrary iterables, including strings and dictionaries, and returns
an iterator object supporting arbitrary index types (e.g. unevenly spaced or non-integer indices).
If `A` is `AbstractArray` it is possible to explicitly specify the style of the indices that
should be returned by `eachindex` by passing a value having `IndexStyle` type as its first argument
(typically `IndexLinear()` if linear indices are required or `IndexCartesian()` if Cartesian
range is wanted).
If you supply more than one `AbstractArray` argument, `eachindex` will create an
iterable object that is fast for all arguments (typically a [`UnitRange`](@ref)
if all inputs have fast linear indexing, a [`CartesianIndices`](@ref) otherwise).
If the arrays have different sizes and/or dimensionalities, a `DimensionMismatch` exception
will be thrown.
See also [`pairs`](@ref)`(A)` to iterate over indices and values together,
and [`axes`](@ref)`(A, 2)` for valid indices along one dimension.
# Examples
```jldoctest
julia> A = [10 20; 30 40];
julia> for i in eachindex(A) # linear indexing
println("A[", i, "] == ", A[i])
end
A[1] == 10
A[2] == 30
A[3] == 20
A[4] == 40
julia> for i in eachindex(view(A, 1:2, 1:1)) # Cartesian indexing
println(i)
end
CartesianIndex(1, 1)
CartesianIndex(2, 1)
```
"""
eachindex(A::AbstractArray) = (@inline(); eachindex(IndexStyle(A), A))
function eachindex(A::AbstractArray, B::AbstractArray)
@inline
eachindex(IndexStyle(A,B), A, B)
end
function eachindex(A::AbstractArray, B::AbstractArray...)
@inline
eachindex(IndexStyle(A,B...), A, B...)
end
eachindex(::IndexLinear, A::AbstractArray) = (@inline; oneto(length(A)))
eachindex(::IndexLinear, A::AbstractVector) = (@inline; axes1(A))
function eachindex(::IndexLinear, A::AbstractArray, B::AbstractArray...)
@inline
indsA = eachindex(IndexLinear(), A)
_all_match_first(X->eachindex(IndexLinear(), X), indsA, B...) ||
throw_eachindex_mismatch_indices(IndexLinear(), eachindex(A), eachindex.(B)...)
indsA
end
function _all_match_first(f::F, inds, A, B...) where F<:Function
@inline
(inds == f(A)) & _all_match_first(f, inds, B...)
end
_all_match_first(f::F, inds) where F<:Function = true
# keys with an IndexStyle
keys(s::IndexStyle, A::AbstractArray, B::AbstractArray...) = eachindex(s, A, B...)
"""
lastindex(collection) -> Integer
lastindex(collection, d) -> Integer
Return the last index of `collection`. If `d` is given, return the last index of `collection` along dimension `d`.
The syntaxes `A[end]` and `A[end, end]` lower to `A[lastindex(A)]` and
`A[lastindex(A, 1), lastindex(A, 2)]`, respectively.
See also: [`axes`](@ref), [`firstindex`](@ref), [`eachindex`](@ref), [`prevind`](@ref).
# Examples
```jldoctest
julia> lastindex([1,2,4])
3
julia> lastindex(rand(3,4,5), 2)
4
```
"""
lastindex(a::AbstractArray) = (@inline; last(eachindex(IndexLinear(), a)))
lastindex(a, d) = (@inline; last(axes(a, d)))
"""
firstindex(collection) -> Integer
firstindex(collection, d) -> Integer
Return the first index of `collection`. If `d` is given, return the first index of `collection` along dimension `d`.
The syntaxes `A[begin]` and `A[1, begin]` lower to `A[firstindex(A)]` and
`A[1, firstindex(A, 2)]`, respectively.
See also: [`first`](@ref), [`axes`](@ref), [`lastindex`](@ref), [`nextind`](@ref).
# Examples
```jldoctest
julia> firstindex([1,2,4])
1
julia> firstindex(rand(3,4,5), 2)
1
```
"""
firstindex(a::AbstractArray) = (@inline; first(eachindex(IndexLinear(), a)))
firstindex(a, d) = (@inline; first(axes(a, d)))
@propagate_inbounds first(a::AbstractArray) = a[first(eachindex(a))]
"""
first(coll)
Get the first element of an iterable collection. Return the start point of an
[`AbstractRange`](@ref) even if it is empty.
See also: [`only`](@ref), [`firstindex`](@ref), [`last`](@ref).
# Examples
```jldoctest
julia> first(2:2:10)
2
julia> first([1; 2; 3; 4])
1
```
"""
function first(itr)
x = iterate(itr)
x === nothing && throw(ArgumentError("collection must be non-empty"))
x[1]
end
"""
first(itr, n::Integer)
Get the first `n` elements of the iterable collection `itr`, or fewer elements if `itr` is not
long enough.
See also: [`startswith`](@ref), [`Iterators.take`](@ref).
!!! compat "Julia 1.6"
This method requires at least Julia 1.6.
# Examples
```jldoctest
julia> first(["foo", "bar", "qux"], 2)
2-element Vector{String}:
"foo"
"bar"
julia> first(1:6, 10)
1:6
julia> first(Bool[], 1)
Bool[]
```
"""
first(itr, n::Integer) = collect(Iterators.take(itr, n))
# Faster method for vectors
function first(v::AbstractVector, n::Integer)
n < 0 && throw(ArgumentError("Number of elements must be non-negative"))
v[range(begin, length=min(n, checked_length(v)))]
end
"""
last(coll)
Get the last element of an ordered collection, if it can be computed in O(1) time. This is
accomplished by calling [`lastindex`](@ref) to get the last index. Return the end
point of an [`AbstractRange`](@ref) even if it is empty.
See also [`first`](@ref), [`endswith`](@ref).
# Examples
```jldoctest
julia> last(1:2:10)
9
julia> last([1; 2; 3; 4])
4
```
"""
last(a) = a[end]
"""
last(itr, n::Integer)
Get the last `n` elements of the iterable collection `itr`, or fewer elements if `itr` is not
long enough.
!!! compat "Julia 1.6"
This method requires at least Julia 1.6.
# Examples
```jldoctest
julia> last(["foo", "bar", "qux"], 2)
2-element Vector{String}:
"bar"
"qux"
julia> last(1:6, 10)
1:6
julia> last(Float64[], 1)
Float64[]
```
"""
last(itr, n::Integer) = reverse!(collect(Iterators.take(Iterators.reverse(itr), n)))
# Faster method for arrays
function last(v::AbstractVector, n::Integer)
n < 0 && throw(ArgumentError("Number of elements must be non-negative"))
v[range(stop=lastindex(v), length=min(n, checked_length(v)))]
end
"""
strides(A)
Return a tuple of the memory strides in each dimension.
See also: [`stride`](@ref).
# Examples
```jldoctest
julia> A = fill(1, (3,4,5));
julia> strides(A)
(1, 3, 12)
```
"""
function strides end
"""
stride(A, k::Integer)
Return the distance in memory (in number of elements) between adjacent elements in dimension `k`.
See also: [`strides`](@ref).
# Examples
```jldoctest
julia> A = fill(1, (3,4,5));
julia> stride(A,2)
3
julia> stride(A,3)
12
```
"""
function stride(A::AbstractArray, k::Integer)
st = strides(A)
k ≤ ndims(A) && return st[k]
ndims(A) == 0 && return 1
sz = size(A)
s = st[1] * sz[1]
for i in 2:ndims(A)
s += st[i] * sz[i]
end
return s
end
@inline size_to_strides(s, d, sz...) = (s, size_to_strides(s * d, sz...)...)
size_to_strides(s, d) = (s,)
size_to_strides(s) = ()
function isstored(A::AbstractArray{<:Any,N}, I::Vararg{Integer,N}) where {N}
@boundscheck checkbounds(A, I...)
return true
end
# used to compute "end" for last index
function trailingsize(A, n)
s = 1
for i=n:ndims(A)
s *= size(A,i)
end
return s
end
function trailingsize(inds::Indices, n)
s = 1
for i=n:length(inds)
s *= length(inds[i])
end
return s
end
# This version is type-stable even if inds is heterogeneous
function trailingsize(inds::Indices)
@inline
prod(map(length, inds))
end
## Bounds checking ##
# The overall hierarchy is
# `checkbounds(A, I...)` ->
# `checkbounds(Bool, A, I...)` ->
# `checkbounds_indices(Bool, IA, I)`, which recursively calls
# `checkindex` for each dimension
#
# See the "boundscheck" devdocs for more information.
#
# Note this hierarchy has been designed to reduce the likelihood of
# method ambiguities. We try to make `checkbounds` the place to
# specialize on array type, and try to avoid specializations on index
# types; conversely, `checkindex` is intended to be specialized only
# on index type (especially, its last argument).
"""
checkbounds(Bool, A, I...)
Return `true` if the specified indices `I` are in bounds for the given
array `A`. Subtypes of `AbstractArray` should specialize this method
if they need to provide custom bounds checking behaviors; however, in
many cases one can rely on `A`'s indices and [`checkindex`](@ref).
See also [`checkindex`](@ref).
# Examples
```jldoctest
julia> A = rand(3, 3);
julia> checkbounds(Bool, A, 2)
true
julia> checkbounds(Bool, A, 3, 4)
false
julia> checkbounds(Bool, A, 1:3)
true
julia> checkbounds(Bool, A, 1:3, 2:4)
false
```
"""
function checkbounds(::Type{Bool}, A::AbstractArray, I...)
@inline
checkbounds_indices(Bool, axes(A), I)
end
# Linear indexing is explicitly allowed when there is only one (non-cartesian) index;
# indices that do not allow linear indexing (e.g., logical arrays, cartesian indices, etc)
# must add specialized methods to implement their restrictions
function checkbounds(::Type{Bool}, A::AbstractArray, i)
@inline
return checkindex(Bool, eachindex(IndexLinear(), A), i)
end
"""
checkbounds(A, I...)
Throw an error if the specified indices `I` are not in bounds for the given array `A`.
"""
function checkbounds(A::AbstractArray, I...)
@inline
checkbounds(Bool, A, I...) || throw_boundserror(A, I)
nothing
end
"""
checkbounds_indices(Bool, IA, I)
Return `true` if the "requested" indices in the tuple `I` fall within
the bounds of the "permitted" indices specified by the tuple
`IA`. This function recursively consumes elements of these tuples,
usually in a 1-for-1 fashion,
checkbounds_indices(Bool, (IA1, IA...), (I1, I...)) = checkindex(Bool, IA1, I1) &
checkbounds_indices(Bool, IA, I)
Note that [`checkindex`](@ref) is being used to perform the actual
bounds-check for a single dimension of the array.
There are two important exceptions to the 1-1 rule: linear indexing and
CartesianIndex{N}, both of which may "consume" more than one element
of `IA`.
See also [`checkbounds`](@ref).
"""
function checkbounds_indices(::Type{Bool}, inds::Tuple, I::Tuple{Any, Vararg})
@inline
return checkindex(Bool, get(inds, 1, OneTo(1)), I[1])::Bool &
checkbounds_indices(Bool, safe_tail(inds), tail(I))
end
checkbounds_indices(::Type{Bool}, inds::Tuple, ::Tuple{}) = (@inline; all(x->length(x)==1, inds))
# check along a single dimension
"""
checkindex(Bool, inds::AbstractUnitRange, index)
Return `true` if the given `index` is within the bounds of
`inds`. Custom types that would like to behave as indices for all
arrays can extend this method in order to provide a specialized bounds
checking implementation.
See also [`checkbounds`](@ref).
# Examples
```jldoctest
julia> checkindex(Bool, 1:20, 8)
true
julia> checkindex(Bool, 1:20, 21)
false
```
"""
checkindex(::Type{Bool}, inds, i) = throw(ArgumentError("unable to check bounds for indices of type $(typeof(i))"))
checkindex(::Type{Bool}, inds::AbstractUnitRange, i::Real) = (first(inds) <= i) & (i <= last(inds))
checkindex(::Type{Bool}, inds::IdentityUnitRange, i::Real) = checkindex(Bool, inds.indices, i)
checkindex(::Type{Bool}, inds::OneTo{T}, i::T) where {T<:BitInteger} = unsigned(i - one(i)) < unsigned(last(inds))
checkindex(::Type{Bool}, inds::AbstractUnitRange, ::Colon) = true
checkindex(::Type{Bool}, inds::AbstractUnitRange, ::Slice) = true
checkindex(::Type{Bool}, inds::AbstractUnitRange, i::AbstractRange) =
isempty(i) | (checkindex(Bool, inds, first(i)) & checkindex(Bool, inds, last(i)))
# range like indices with cheap `extrema`
checkindex(::Type{Bool}, inds::AbstractUnitRange, i::LinearIndices) =
isempty(i) | (checkindex(Bool, inds, first(i)) & checkindex(Bool, inds, last(i)))
function checkindex(::Type{Bool}, inds, I::AbstractArray)
@inline
b = true
for i in I
b &= checkindex(Bool, inds, i)
end
b
end
# See also specializations in multidimensional
## Constructors ##
# default arguments to similar()
"""
similar(array, [element_type=eltype(array)], [dims=size(array)])
Create an uninitialized mutable array with the given element type and size, based upon the
given source array. The second and third arguments are both optional, defaulting to the
given array's `eltype` and `size`. The dimensions may be specified either as a single tuple
argument or as a series of integer arguments.
Custom AbstractArray subtypes may choose which specific array type is best-suited to return
for the given element type and dimensionality. If they do not specialize this method, the
default is an `Array{element_type}(undef, dims...)`.
For example, `similar(1:10, 1, 4)` returns an uninitialized `Array{Int,2}` since ranges are
neither mutable nor support 2 dimensions:
```julia-repl
julia> similar(1:10, 1, 4)
1×4 Matrix{Int64}:
4419743872 4374413872 4419743888 0
```
Conversely, `similar(trues(10,10), 2)` returns an uninitialized `BitVector` with two
elements since `BitArray`s are both mutable and can support 1-dimensional arrays:
```julia-repl
julia> similar(trues(10,10), 2)
2-element BitVector:
0
0
```
Since `BitArray`s can only store elements of type [`Bool`](@ref), however, if you request a
different element type it will create a regular `Array` instead:
```julia-repl
julia> similar(falses(10), Float64, 2, 4)
2×4 Matrix{Float64}:
2.18425e-314 2.18425e-314 2.18425e-314 2.18425e-314
2.18425e-314 2.18425e-314 2.18425e-314 2.18425e-314
```
See also: [`undef`](@ref), [`isassigned`](@ref).
"""
similar(a::AbstractArray{T}) where {T} = similar(a, T)
similar(a::AbstractArray, ::Type{T}) where {T} = similar(a, T, to_shape(axes(a)))
similar(a::AbstractArray{T}, dims::Tuple) where {T} = similar(a, T, to_shape(dims))
similar(a::AbstractArray{T}, dims::DimOrInd...) where {T} = similar(a, T, to_shape(dims))
similar(a::AbstractArray, ::Type{T}, dims::DimOrInd...) where {T} = similar(a, T, to_shape(dims))
# Similar supports specifying dims as either Integers or AbstractUnitRanges or any mixed combination
# thereof. Ideally, we'd just convert Integers to OneTos and then call a canonical method with the axes,
# but we don't want to require all AbstractArray subtypes to dispatch on Base.OneTo. So instead we
# define this method to convert supported axes to Ints, with the expectation that an offset array
# package will define a method with dims::Tuple{Union{Integer, UnitRange}, Vararg{Union{Integer, UnitRange}}}
similar(a::AbstractArray, ::Type{T}, dims::Tuple{Union{Integer, OneTo}, Vararg{Union{Integer, OneTo}}}) where {T} = similar(a, T, to_shape(dims))
similar(a::AbstractArray, ::Type{T}, dims::Tuple{Integer, Vararg{Integer}}) where {T} = similar(a, T, to_shape(dims))
# similar creates an Array by default
similar(a::AbstractArray, ::Type{T}, dims::Dims{N}) where {T,N} = Array{T,N}(undef, dims)
to_shape(::Tuple{}) = ()
to_shape(dims::Dims) = dims
to_shape(dims::DimsOrInds) = map(to_shape, dims)::DimsOrInds
# each dimension
to_shape(i::Int) = i
to_shape(i::Integer) = Int(i)
to_shape(r::OneTo) = Int(last(r))
to_shape(r::AbstractUnitRange) = r
"""
similar(storagetype, axes)
Create an uninitialized mutable array analogous to that specified by
`storagetype`, but with `axes` specified by the last
argument.
**Examples**:
similar(Array{Int}, axes(A))
creates an array that "acts like" an `Array{Int}` (and might indeed be
backed by one), but which is indexed identically to `A`. If `A` has
conventional indexing, this will be identical to
`Array{Int}(undef, size(A))`, but if `A` has unconventional indexing then the
indices of the result will match `A`.
similar(BitArray, (axes(A, 2),))
would create a 1-dimensional logical array whose indices match those
of the columns of `A`.
"""
similar(::Type{T}, dims::DimOrInd...) where {T<:AbstractArray} = similar(T, dims)
similar(::Type{T}, shape::Tuple{Union{Integer, OneTo}, Vararg{Union{Integer, OneTo}}}) where {T<:AbstractArray} = similar(T, to_shape(shape))
similar(::Type{T}, dims::Dims) where {T<:AbstractArray} = T(undef, dims)
"""
empty(v::AbstractVector, [eltype])
Create an empty vector similar to `v`, optionally changing the `eltype`.
See also: [`empty!`](@ref), [`isempty`](@ref), [`isassigned`](@ref).
# Examples
```jldoctest
julia> empty([1.0, 2.0, 3.0])
Float64[]
julia> empty([1.0, 2.0, 3.0], String)
String[]
```
"""
empty(a::AbstractVector{T}, ::Type{U}=T) where {T,U} = similar(a, U, 0)
# like empty, but should return a mutable collection, a Vector by default
emptymutable(a::AbstractVector{T}, ::Type{U}=T) where {T,U} = Vector{U}()
emptymutable(itr, ::Type{U}) where {U} = Vector{U}()
"""
copy!(dst, src) -> dst
In-place [`copy`](@ref) of `src` into `dst`, discarding any pre-existing
elements in `dst`.
If `dst` and `src` are of the same type, `dst == src` should hold after
the call. If `dst` and `src` are multidimensional arrays, they must have
equal [`axes`](@ref).
$(_DOCS_ALIASING_WARNING)
See also [`copyto!`](@ref).
!!! compat "Julia 1.1"
This method requires at least Julia 1.1. In Julia 1.0 this method
is available from the `Future` standard library as `Future.copy!`.
"""
function copy!(dst::AbstractVector, src::AbstractVector)
firstindex(dst) == firstindex(src) || throw(ArgumentError(
"vectors must have the same offset for copy! (consider using `copyto!`)"))
if length(dst) != length(src)
resize!(dst, length(src))
end
copyto!(dst, src)
end
function copy!(dst::AbstractArray, src::AbstractArray)
axes(dst) == axes(src) || throw(ArgumentError(
"arrays must have the same axes for copy! (consider using `copyto!`)"))
copyto!(dst, src)
end
## from general iterable to any array
# This is `Experimental.@max_methods 1 function copyto! end`, which is not
# defined at this point in bootstrap.
typeof(function copyto! end).name.max_methods = UInt8(1)
function copyto!(dest::AbstractArray, src)
destiter = eachindex(dest)
y = iterate(destiter)
for x in src
y === nothing &&
throw(ArgumentError("destination has fewer elements than required"))
dest[y[1]] = x
y = iterate(destiter, y[2])
end
return dest
end
function copyto!(dest::AbstractArray, dstart::Integer, src)
i = Int(dstart)
if haslength(src) && length(dest) > 0
@boundscheck checkbounds(dest, i:(i + length(src) - 1))
for x in src
@inbounds dest[i] = x
i += 1
end
else
for x in src
dest[i] = x
i += 1
end
end
return dest
end
# copy from an some iterable object into an AbstractArray
function copyto!(dest::AbstractArray, dstart::Integer, src, sstart::Integer)
if (sstart < 1)
throw(ArgumentError(LazyString("source start offset (",sstart,") is < 1")))
end
y = iterate(src)
for j = 1:(sstart-1)
if y === nothing
throw(ArgumentError(LazyString(
"source has fewer elements than required, ",
"expected at least ", sstart,", got ", j-1)))
end
y = iterate(src, y[2])
end
if y === nothing
throw(ArgumentError(LazyString(
"source has fewer elements than required, ",
"expected at least ",sstart," got ", sstart-1)))
end
i = Int(dstart)
while y !== nothing
val, st = y
dest[i] = val
i += 1
y = iterate(src, st)
end
return dest
end
# this method must be separate from the above since src might not have a length
function copyto!(dest::AbstractArray, dstart::Integer, src, sstart::Integer, n::Integer)
n < 0 && throw(ArgumentError(LazyString("tried to copy n=",n,
", elements, but n should be non-negative")))
n == 0 && return dest
dmax = dstart + n - 1
inds = LinearIndices(dest)
if (dstart ∉ inds || dmax ∉ inds) | (sstart < 1)
sstart < 1 && throw(ArgumentError(LazyString("source start offset (",
sstart,") is < 1")))
throw(BoundsError(dest, dstart:dmax))
end
y = iterate(src)
for j = 1:(sstart-1)
if y === nothing
throw(ArgumentError(LazyString(
"source has fewer elements than required, ",
"expected at least ",sstart,", got ",j-1)))
end
y = iterate(src, y[2])
end
i = Int(dstart)
while i <= dmax && y !== nothing
val, st = y
@inbounds dest[i] = val
y = iterate(src, st)
i += 1
end
i <= dmax && throw(BoundsError(dest, i))
return dest
end
## copy between abstract arrays - generally more efficient
## since a single index variable can be used.
"""
copyto!(dest::AbstractArray, src) -> dest
Copy all elements from collection `src` to array `dest`, whose length must be greater than
or equal to the length `n` of `src`. The first `n` elements of `dest` are overwritten,
the other elements are left untouched.
See also [`copy!`](@ref Base.copy!), [`copy`](@ref).
$(_DOCS_ALIASING_WARNING)
# Examples
```jldoctest
julia> x = [1., 0., 3., 0., 5.];
julia> y = zeros(7);
julia> copyto!(y, x);
julia> y
7-element Vector{Float64}:
1.0
0.0
3.0
0.0
5.0
0.0
0.0
```
"""
function copyto!(dest::AbstractArray, src::AbstractArray)
isempty(src) && return dest
if dest isa BitArray
# avoid ambiguities with other copyto!(::AbstractArray, ::SourceArray) methods
return _copyto_bitarray!(dest, src)
end
src′ = unalias(dest, src)
copyto_unaliased!(IndexStyle(dest), dest, IndexStyle(src′), src′)
end
function copyto!(deststyle::IndexStyle, dest::AbstractArray, srcstyle::IndexStyle, src::AbstractArray)
isempty(src) && return dest
src′ = unalias(dest, src)
copyto_unaliased!(deststyle, dest, srcstyle, src′)
end
function copyto_unaliased!(deststyle::IndexStyle, dest::AbstractArray, srcstyle::IndexStyle, src::AbstractArray)
isempty(src) && return dest
destinds, srcinds = LinearIndices(dest), LinearIndices(src)
idf, isf = first(destinds), first(srcinds)
Δi = idf - isf
(checkbounds(Bool, destinds, isf+Δi) & checkbounds(Bool, destinds, last(srcinds)+Δi)) ||
throw(BoundsError(dest, srcinds))
if deststyle isa IndexLinear
if srcstyle isa IndexLinear
# Single-index implementation
@inbounds for i in srcinds
if isassigned(src, i)
dest[i + Δi] = src[i]
else
_unsetindex!(dest, i + Δi)
end
end
else
# Dual-index implementation
i = idf - 1
@inbounds for a in eachindex(src)
i += 1
if isassigned(src, a)
dest[i] = src[a]
else
_unsetindex!(dest, i)
end
end
end
else
iterdest, itersrc = eachindex(dest), eachindex(src)
if iterdest == itersrc
# Shared-iterator implementation
@inbounds for I in iterdest
if isassigned(src, I)
dest[I] = src[I]
else
_unsetindex!(dest, I)
end
end
else
# Dual-iterator implementation
ret = iterate(iterdest)
@inbounds for a in itersrc
idx, state = ret::NTuple{2,Any}
if isassigned(src, a)
dest[idx] = src[a]
else
_unsetindex!(dest, idx)
end
ret = iterate(iterdest, state)
end
end
end
return dest
end
function copyto!(dest::AbstractArray, dstart::Integer, src::AbstractArray)
copyto!(dest, dstart, src, first(LinearIndices(src)), length(src))
end
function copyto!(dest::AbstractArray, dstart::Integer, src::AbstractArray, sstart::Integer)
srcinds = LinearIndices(src)
checkbounds(Bool, srcinds, sstart) || throw(BoundsError(src, sstart))
copyto!(dest, dstart, src, sstart, last(srcinds)-sstart+1)
end
function copyto!(dest::AbstractArray, dstart::Integer,
src::AbstractArray, sstart::Integer,
n::Integer)
n == 0 && return dest
n < 0 && throw(ArgumentError(LazyString("tried to copy n=",
n," elements, but n should be non-negative")))
destinds, srcinds = LinearIndices(dest), LinearIndices(src)
(checkbounds(Bool, destinds, dstart) && checkbounds(Bool, destinds, dstart+n-1)) || throw(BoundsError(dest, dstart:dstart+n-1))
(checkbounds(Bool, srcinds, sstart) && checkbounds(Bool, srcinds, sstart+n-1)) || throw(BoundsError(src, sstart:sstart+n-1))
src′ = unalias(dest, src)
@inbounds for i = 0:n-1
if isassigned(src′, sstart+i)
dest[dstart+i] = src′[sstart+i]
else
_unsetindex!(dest, dstart+i)
end
end
return dest
end
function copy(a::AbstractArray)
@_propagate_inbounds_meta
copymutable(a)
end
function copyto!(B::AbstractVecOrMat{R}, ir_dest::AbstractRange{Int}, jr_dest::AbstractRange{Int},
A::AbstractVecOrMat{S}, ir_src::AbstractRange{Int}, jr_src::AbstractRange{Int}) where {R,S}
if length(ir_dest) != length(ir_src)
throw(ArgumentError(LazyString("source and destination must have same size (got ",
length(ir_src)," and ",length(ir_dest),")")))
end
if length(jr_dest) != length(jr_src)
throw(ArgumentError(LazyString("source and destination must have same size (got ",
length(jr_src)," and ",length(jr_dest),")")))
end
@boundscheck checkbounds(B, ir_dest, jr_dest)
@boundscheck checkbounds(A, ir_src, jr_src)
A′ = unalias(B, A)
jdest = first(jr_dest)
for jsrc in jr_src
idest = first(ir_dest)
for isrc in ir_src
@inbounds B[idest,jdest] = A′[isrc,jsrc]
idest += step(ir_dest)
end
jdest += step(jr_dest)
end
return B
end
@noinline _checkaxs(axd, axs) = axd == axs || throw(DimensionMismatch("axes must agree, got $axd and $axs"))
function copyto_axcheck!(dest, src)
_checkaxs(axes(dest), axes(src))
copyto!(dest, src)
end
"""
copymutable(a)
Make a mutable copy of an array or iterable `a`. For `a::Array`,
this is equivalent to `copy(a)`, but for other array types it may
differ depending on the type of `similar(a)`. For generic iterables
this is equivalent to `collect(a)`.
# Examples
```jldoctest
julia> tup = (1, 2, 3)
(1, 2, 3)
julia> Base.copymutable(tup)
3-element Vector{Int64}:
1
2
3
```
"""
function copymutable(a::AbstractArray)
@_propagate_inbounds_meta
copyto!(similar(a), a)
end
copymutable(itr) = collect(itr)
zero(x::AbstractArray{T}) where {T<:Number} = fill!(similar(x, typeof(zero(T))), zero(T))
zero(x::AbstractArray) = map(zero, x)
## iteration support for arrays by iterating over `eachindex` in the array ##
# Allows fast iteration by default for both IndexLinear and IndexCartesian arrays
# While the definitions for IndexLinear are all simple enough to inline on their
# own, IndexCartesian's CartesianIndices is more complicated and requires explicit
# inlining.
function iterate(A::AbstractArray, state=(eachindex(A),))
y = iterate(state...)
y === nothing && return nothing
A[y[1]], (state[1], tail(y)...)
end
isempty(a::AbstractArray) = (length(a) == 0)
## range conversions ##
map(::Type{T}, r::StepRange) where {T<:Real} = T(r.start):T(r.step):T(last(r))
map(::Type{T}, r::UnitRange) where {T<:Real} = T(r.start):T(last(r))
map(::Type{T}, r::StepRangeLen) where {T<:AbstractFloat} = convert(StepRangeLen{T}, r)
function map(::Type{T}, r::LinRange) where T<:AbstractFloat
LinRange(T(r.start), T(r.stop), length(r))
end
## unsafe/pointer conversions ##
# note: the following type definitions don't mean any AbstractArray is convertible to
# a data Ref. they just map the array element type to the pointer type for
# convenience in cases that work.
pointer(x::AbstractArray{T}) where {T} = unsafe_convert(Ptr{T}, cconvert(Ptr{T}, x))
function pointer(x::AbstractArray{T}, i::Integer) where T
@inline
pointer(x) + Int(_memory_offset(x, i))::Int
end
# The distance from pointer(x) to the element at x[I...] in bytes
_memory_offset(x::DenseArray, I::Vararg{Any,N}) where {N} = (_to_linear_index(x, I...) - first(LinearIndices(x)))*elsize(x)
function _memory_offset(x::AbstractArray, I::Vararg{Any,N}) where {N}
J = _to_subscript_indices(x, I...)
return sum(map((i, s, o)->s*(i-o), J, strides(x), Tuple(first(CartesianIndices(x)))))*elsize(x)
end
## Approach:
# We only define one fallback method on getindex for all argument types.
# That dispatches to an (inlined) internal _getindex function, where the goal is
# to transform the indices such that we can call the only getindex method that
# we require the type A{T,N} <: AbstractArray{T,N} to define; either:
# getindex(::A, ::Int) # if IndexStyle(A) == IndexLinear() OR
# getindex(::A{T,N}, ::Vararg{Int, N}) where {T,N} # if IndexCartesian()
# If the subtype hasn't defined the required method, it falls back to the
# _getindex function again where an error is thrown to prevent stack overflows.
"""
getindex(A, inds...)
Return a subset of array `A` as selected by the indices `inds`.
Each index may be any [supported index type](@ref man-supported-index-types), such
as an [`Integer`](@ref), [`CartesianIndex`](@ref), [range](@ref Base.AbstractRange), or [array](@ref man-multi-dim-arrays) of supported indices.
A [:](@ref Base.Colon) may be used to select all elements along a specific dimension, and a boolean array (e.g. an `Array{Bool}` or a [`BitArray`](@ref)) may be used to filter for elements where the corresponding index is `true`.
When `inds` selects multiple elements, this function returns a newly
allocated array. To index multiple elements without making a copy,
use [`view`](@ref) instead.
See the manual section on [array indexing](@ref man-array-indexing) for details.
# Examples
```jldoctest
julia> A = [1 2; 3 4]
2×2 Matrix{Int64}:
1 2
3 4
julia> getindex(A, 1)
1
julia> getindex(A, [2, 1])
2-element Vector{Int64}:
3
1
julia> getindex(A, 2:4)
3-element Vector{Int64}:
3
2
4
julia> getindex(A, 2, 1)
3
julia> getindex(A, CartesianIndex(2, 1))
3
julia> getindex(A, :, 2)
2-element Vector{Int64}:
2
4
julia> getindex(A, 2, :)
2-element Vector{Int64}:
3
4
julia> getindex(A, A .> 2)
2-element Vector{Int64}:
3
4
```
"""
function getindex(A::AbstractArray, I...)
@_propagate_inbounds_meta
error_if_canonical_getindex(IndexStyle(A), A, I...)
_getindex(IndexStyle(A), A, to_indices(A, I)...)
end
# To avoid invalidations from multidimensional.jl: getindex(A::Array, i1::Union{Integer, CartesianIndex}, I::Union{Integer, CartesianIndex}...)
@propagate_inbounds getindex(A::Array, i1::Integer, I::Integer...) = A[to_indices(A, (i1, I...))...]
@inline unsafe_getindex(A::AbstractArray, I...) = @inbounds getindex(A, I...)
struct CanonicalIndexError <: Exception
func::String
type::Any
CanonicalIndexError(func::String, @nospecialize(type)) = new(func, type)
end
error_if_canonical_getindex(::IndexLinear, A::AbstractArray, ::Int) =
throw(CanonicalIndexError("getindex", typeof(A)))
error_if_canonical_getindex(::IndexCartesian, A::AbstractArray{T,N}, ::Vararg{Int,N}) where {T,N} =
throw(CanonicalIndexError("getindex", typeof(A)))
error_if_canonical_getindex(::IndexStyle, ::AbstractArray, ::Any...) = nothing
## Internal definitions
_getindex(::IndexStyle, A::AbstractArray, I...) =
error("getindex for $(typeof(A)) with types $(typeof(I)) is not supported")
## IndexLinear Scalar indexing: canonical method is one Int
_getindex(::IndexLinear, A::AbstractVector, i::Int) = (@_propagate_inbounds_meta; getindex(A, i)) # ambiguity resolution in case packages specialize this (to be avoided if at all possible, but see Interpolations.jl)
_getindex(::IndexLinear, A::AbstractArray, i::Int) = (@_propagate_inbounds_meta; getindex(A, i))
function _getindex(::IndexLinear, A::AbstractArray, I::Vararg{Int,M}) where M
@inline
@boundscheck checkbounds(A, I...) # generally _to_linear_index requires bounds checking
@inbounds r = getindex(A, _to_linear_index(A, I...))
r
end
_to_linear_index(A::AbstractArray, i::Integer) = i
_to_linear_index(A::AbstractVector, i::Integer, I::Integer...) = i
_to_linear_index(A::AbstractArray) = first(LinearIndices(A))
_to_linear_index(A::AbstractArray, I::Integer...) = (@inline; _sub2ind(A, I...))
## IndexCartesian Scalar indexing: Canonical method is full dimensionality of Ints
function _getindex(::IndexCartesian, A::AbstractArray, I::Vararg{Int,M}) where M
@inline
@boundscheck checkbounds(A, I...) # generally _to_subscript_indices requires bounds checking
@inbounds r = getindex(A, _to_subscript_indices(A, I...)...)
r
end
function _getindex(::IndexCartesian, A::AbstractArray{T,N}, I::Vararg{Int, N}) where {T,N}
@_propagate_inbounds_meta
getindex(A, I...)
end
_to_subscript_indices(A::AbstractArray, i::Integer) = (@inline; _unsafe_ind2sub(A, i))
_to_subscript_indices(A::AbstractArray{T,N}) where {T,N} = (@inline; fill_to_length((), 1, Val(N)))
_to_subscript_indices(A::AbstractArray{T,0}) where {T} = ()
_to_subscript_indices(A::AbstractArray{T,0}, i::Integer) where {T} = ()
_to_subscript_indices(A::AbstractArray{T,0}, I::Integer...) where {T} = ()
function _to_subscript_indices(A::AbstractArray{T,N}, I::Integer...) where {T,N}
@inline
J, Jrem = IteratorsMD.split(I, Val(N))
_to_subscript_indices(A, J, Jrem)
end
_to_subscript_indices(A::AbstractArray, J::Tuple, Jrem::Tuple{}) =
__to_subscript_indices(A, axes(A), J, Jrem)
function __to_subscript_indices(A::AbstractArray,
::Tuple{AbstractUnitRange,Vararg{AbstractUnitRange}}, J::Tuple, Jrem::Tuple{})
@inline
(J..., map(first, tail(_remaining_size(J, axes(A))))...)
end
_to_subscript_indices(A, J::Tuple, Jrem::Tuple) = J # already bounds-checked, safe to drop
_to_subscript_indices(A::AbstractArray{T,N}, I::Vararg{Int,N}) where {T,N} = I
_remaining_size(::Tuple{Any}, t::Tuple) = t
_remaining_size(h::Tuple, t::Tuple) = (@inline; _remaining_size(tail(h), tail(t)))
_unsafe_ind2sub(::Tuple{}, i) = () # _ind2sub may throw(BoundsError()) in this case
_unsafe_ind2sub(sz, i) = (@inline; _ind2sub(sz, i))
## Setindex! is defined similarly. We first dispatch to an internal _setindex!
# function that allows dispatch on array storage
"""
setindex!(A, X, inds...)
A[inds...] = X
Store values from array `X` within some subset of `A` as specified by `inds`.
The syntax `A[inds...] = X` is equivalent to `(setindex!(A, X, inds...); X)`.
$(_DOCS_ALIASING_WARNING)
# Examples
```jldoctest
julia> A = zeros(2,2);
julia> setindex!(A, [10, 20], [1, 2]);
julia> A[[3, 4]] = [30, 40];
julia> A
2×2 Matrix{Float64}:
10.0 30.0
20.0 40.0
```
"""
function setindex!(A::AbstractArray, v, I...)
@_propagate_inbounds_meta
error_if_canonical_setindex(IndexStyle(A), A, I...)
_setindex!(IndexStyle(A), A, v, to_indices(A, I)...)
end
function unsafe_setindex!(A::AbstractArray, v, I...)
@inline
@inbounds r = setindex!(A, v, I...)
r
end
error_if_canonical_setindex(::IndexLinear, A::AbstractArray, ::Int) =
throw(CanonicalIndexError("setindex!", typeof(A)))
error_if_canonical_setindex(::IndexCartesian, A::AbstractArray{T,N}, ::Vararg{Int,N}) where {T,N} =
throw(CanonicalIndexError("setindex!", typeof(A)))
error_if_canonical_setindex(::IndexStyle, ::AbstractArray, ::Any...) = nothing
## Internal definitions
_setindex!(::IndexStyle, A::AbstractArray, v, I...) =
error("setindex! for $(typeof(A)) with types $(typeof(I)) is not supported")
## IndexLinear Scalar indexing
_setindex!(::IndexLinear, A::AbstractArray, v, i::Int) = (@_propagate_inbounds_meta; setindex!(A, v, i))
function _setindex!(::IndexLinear, A::AbstractArray, v, I::Vararg{Int,M}) where M
@inline
@boundscheck checkbounds(A, I...)
@inbounds r = setindex!(A, v, _to_linear_index(A, I...))
r
end
# IndexCartesian Scalar indexing
function _setindex!(::IndexCartesian, A::AbstractArray{T,N}, v, I::Vararg{Int, N}) where {T,N}
@_propagate_inbounds_meta
setindex!(A, v, I...)
end
function _setindex!(::IndexCartesian, A::AbstractArray, v, I::Vararg{Int,M}) where M
@inline
@boundscheck checkbounds(A, I...)
@inbounds r = setindex!(A, v, _to_subscript_indices(A, I...)...)
r
end
function _unsetindex!(A::AbstractArray, i::Integer...)
@_propagate_inbounds_meta
_unsetindex!(A, map(to_index, i)...)
end
function _unsetindex!(A::AbstractArray{T}, i::Int...) where T
# this provides a fallback method which is a no-op if the element is already unassigned
# such that copying into an uninitialized object generally always will work,
# even if the specific custom array type has not implemented `_unsetindex!`
@inline
@boundscheck checkbounds(A, i...)
allocatedinline(T) || @inbounds(!isassigned(A, i...)) || throw(MethodError(_unsetindex!, (A, i...)))
return A
end
"""
parent(A)
Return the underlying parent object of the view. This parent of objects of types `SubArray`, `SubString`, `ReshapedArray`
or `LinearAlgebra.Transpose` is what was passed as an argument to `view`, `reshape`, `transpose`, etc.
during object creation. If the input is not a wrapped object, return the input itself. If the input is
wrapped multiple times, only the outermost wrapper will be removed.
# Examples
```jldoctest
julia> A = [1 2; 3 4]
2×2 Matrix{Int64}:
1 2
3 4
julia> V = view(A, 1:2, :)
2×2 view(::Matrix{Int64}, 1:2, :) with eltype Int64:
1 2
3 4
julia> parent(V)
2×2 Matrix{Int64}:
1 2
3 4
```
"""
function parent end
parent(a::AbstractArray) = a
## rudimentary aliasing detection ##
"""
Base.unalias(dest, A)
Return either `A` or a copy of `A` in a rough effort to prevent modifications to `dest` from
affecting the returned object. No guarantees are provided.
Custom arrays that wrap or use fields containing arrays that might alias against other
external objects should provide a [`Base.dataids`](@ref) implementation.
This function must return an object of exactly the same type as `A` for performance and type
stability. Mutable custom arrays for which [`copy(A)`](@ref) is not `typeof(A)` should
provide a [`Base.unaliascopy`](@ref) implementation.
See also [`Base.mightalias`](@ref).
"""
unalias(dest, A::AbstractArray) = mightalias(dest, A) ? unaliascopy(A) : A
unalias(dest, A::AbstractRange) = A
unalias(dest, A) = A
"""
Base.unaliascopy(A)
Make a preventative copy of `A` in an operation where `A` [`Base.mightalias`](@ref) against
another array in order to preserve consistent semantics as that other array is mutated.
This must return an object of the same type as `A` to preserve optimal performance in the
much more common case where aliasing does not occur. By default,
`unaliascopy(A::AbstractArray)` will attempt to use [`copy(A)`](@ref), but in cases where
`copy(A)` is not a `typeof(A)`, then the array should provide a custom implementation of
`Base.unaliascopy(A)`.
"""
unaliascopy(A::Array) = copy(A)
unaliascopy(A::AbstractArray)::typeof(A) = (@noinline; _unaliascopy(A, copy(A)))
_unaliascopy(A::T, C::T) where {T} = C
_unaliascopy(A, C) = throw(ArgumentError("""
an array of type `$(typename(typeof(A)).wrapper)` shares memory with another argument
and must make a preventative copy of itself in order to maintain consistent semantics,
but `copy(::$(typeof(A)))` returns a new array of type `$(typeof(C))`.
To fix, implement:
`Base.unaliascopy(A::$(typename(typeof(A)).wrapper))::typeof(A)`"""))
unaliascopy(A) = A
"""
Base.mightalias(A::AbstractArray, B::AbstractArray)
Perform a conservative test to check if arrays `A` and `B` might share the same memory.
By default, this simply checks if either of the arrays reference the same memory
regions, as identified by their [`Base.dataids`](@ref).
"""
mightalias(A::AbstractArray, B::AbstractArray) = !isbits(A) && !isbits(B) && !isempty(A) && !isempty(B) && !_isdisjoint(dataids(A), dataids(B))
mightalias(x, y) = false
_isdisjoint(as::Tuple{}, bs::Tuple{}) = true
_isdisjoint(as::Tuple{}, bs::Tuple{UInt}) = true
_isdisjoint(as::Tuple{}, bs::Tuple) = true
_isdisjoint(as::Tuple{UInt}, bs::Tuple{}) = true
_isdisjoint(as::Tuple{UInt}, bs::Tuple{UInt}) = as[1] != bs[1]
_isdisjoint(as::Tuple{UInt}, bs::Tuple) = !(as[1] in bs)
_isdisjoint(as::Tuple, bs::Tuple{}) = true
_isdisjoint(as::Tuple, bs::Tuple{UInt}) = !(bs[1] in as)
_isdisjoint(as::Tuple, bs::Tuple) = !(as[1] in bs) && _isdisjoint(tail(as), bs)
"""
Base.dataids(A::AbstractArray)
Return a tuple of `UInt`s that represent the mutable data segments of an array.
Custom arrays that would like to opt-in to aliasing detection of their component
parts can specialize this method to return the concatenation of the `dataids` of
their component parts. A typical definition for an array that wraps a parent is
`Base.dataids(C::CustomArray) = dataids(C.parent)`.
"""
dataids(A::AbstractArray) = (UInt(objectid(A)),)
dataids(A::Memory) = (B = ccall(:jl_genericmemory_owner, Any, (Any,), A); (UInt(pointer(B isa typeof(A) ? B : A)),))
dataids(A::Array) = dataids(A.ref.mem)
dataids(::AbstractRange) = ()
dataids(x) = ()
## get (getindex with a default value) ##
RangeVecIntList{A<:AbstractVector{Int}} = Union{Tuple{Vararg{Union{AbstractRange, AbstractVector{Int}}}},
AbstractVector{UnitRange{Int}}, AbstractVector{AbstractRange{Int}}, AbstractVector{A}}
get(A::AbstractArray, i::Integer, default) = checkbounds(Bool, A, i) ? A[i] : default
get(A::AbstractArray, I::Tuple{}, default) = checkbounds(Bool, A) ? A[] : default
get(A::AbstractArray, I::Dims, default) = checkbounds(Bool, A, I...) ? A[I...] : default
get(f::Callable, A::AbstractArray, i::Integer) = checkbounds(Bool, A, i) ? A[i] : f()
get(f::Callable, A::AbstractArray, I::Tuple{}) = checkbounds(Bool, A) ? A[] : f()
get(f::Callable, A::AbstractArray, I::Dims) = checkbounds(Bool, A, I...) ? A[I...] : f()
function get!(X::AbstractVector{T}, A::AbstractVector, I::Union{AbstractRange,AbstractVector{Int}}, default::T) where T
# 1d is not linear indexing
ind = findall(in(axes1(A)), I)
X[ind] = A[I[ind]]
Xind = axes1(X)
X[first(Xind):first(ind)-1] = default
X[last(ind)+1:last(Xind)] = default
X
end
function get!(X::AbstractArray{T}, A::AbstractArray, I::Union{AbstractRange,AbstractVector{Int}}, default::T) where T
# Linear indexing
ind = findall(in(1:length(A)), I)
X[ind] = A[I[ind]]
fill!(view(X, 1:first(ind)-1), default)
fill!(view(X, last(ind)+1:length(X)), default)
X
end
get(A::AbstractArray, I::AbstractRange, default) = get!(similar(A, typeof(default), index_shape(I)), A, I, default)
function get!(X::AbstractArray{T}, A::AbstractArray, I::RangeVecIntList, default::T) where T
fill!(X, default)
dst, src = indcopy(size(A), I)
X[dst...] = A[src...]
X
end
get(A::AbstractArray, I::RangeVecIntList, default) =
get!(similar(A, typeof(default), index_shape(I...)), A, I, default)
## structured matrix methods ##
replace_in_print_matrix(A::AbstractMatrix,i::Integer,j::Integer,s::AbstractString) = s
replace_in_print_matrix(A::AbstractVector,i::Integer,j::Integer,s::AbstractString) = s
## Concatenation ##
eltypeof(x) = typeof(x)
eltypeof(x::AbstractArray) = eltype(x)
promote_eltypeof() = error()
promote_eltypeof(v1) = eltypeof(v1)
promote_eltypeof(v1, vs...) = promote_type(eltypeof(v1), promote_eltypeof(vs...))
promote_eltypeof(v1::T, vs::T...) where {T} = eltypeof(v1)
promote_eltypeof(v1::AbstractArray{T}, vs::AbstractArray{T}...) where {T} = T
promote_eltype() = error()
promote_eltype(v1) = eltype(v1)
promote_eltype(v1, vs...) = promote_type(eltype(v1), promote_eltype(vs...))
promote_eltype(v1::T, vs::T...) where {T} = eltype(T)
promote_eltype(v1::AbstractArray{T}, vs::AbstractArray{T}...) where {T} = T
#TODO: ERROR CHECK
_cat(catdim::Int) = Vector{Any}()
typed_vcat(::Type{T}) where {T} = Vector{T}()
typed_hcat(::Type{T}) where {T} = Vector{T}()
## cat: special cases
vcat(X::T...) where {T} = T[ X[i] for i=1:length(X) ]
vcat(X::T...) where {T<:Number} = T[ X[i] for i=1:length(X) ]
hcat(X::T...) where {T} = T[ X[j] for i=1:1, j=1:length(X) ]
hcat(X::T...) where {T<:Number} = T[ X[j] for i=1:1, j=1:length(X) ]
vcat(X::Number...) = hvcat_fill!(Vector{promote_typeof(X...)}(undef, length(X)), X)
hcat(X::Number...) = hvcat_fill!(Matrix{promote_typeof(X...)}(undef, 1,length(X)), X)
typed_vcat(::Type{T}, X::Number...) where {T} = hvcat_fill!(Vector{T}(undef, length(X)), X)
typed_hcat(::Type{T}, X::Number...) where {T} = hvcat_fill!(Matrix{T}(undef, 1,length(X)), X)
vcat(V::AbstractVector...) = typed_vcat(promote_eltype(V...), V...)
vcat(V::AbstractVector{T}...) where {T} = typed_vcat(T, V...)
# FIXME: this alias would better be Union{AbstractVector{T}, Tuple{Vararg{T}}}
# and method signatures should do AbstractVecOrTuple{<:T} when they want covariance,
# but that solution currently fails (see #27188 and #27224)
AbstractVecOrTuple{T} = Union{AbstractVector{<:T}, Tuple{Vararg{T}}}
_typed_vcat_similar(V, ::Type{T}, n) where T = similar(V[1], T, n)
_typed_vcat(::Type{T}, V::AbstractVecOrTuple{AbstractVector}) where T =
_typed_vcat!(_typed_vcat_similar(V, T, sum(map(length, V))), V)
function _typed_vcat!(a::AbstractVector{T}, V::AbstractVecOrTuple{AbstractVector}) where T
pos = 1
for k=1:Int(length(V))::Int
Vk = V[k]
p1 = pos + Int(length(Vk))::Int - 1
a[pos:p1] = Vk
pos = p1+1
end
a
end
typed_hcat(::Type{T}, A::AbstractVecOrMat...) where {T} = _typed_hcat(T, A)
# Catch indexing errors like v[i +1] (instead of v[i+1] or v[i + 1]), where indexing is
# interpreted as a typed concatenation. (issue #49676)
typed_hcat(::AbstractArray, other...) = throw(ArgumentError("It is unclear whether you \
intend to perform an indexing operation or typed concatenation. If you intend to \
perform indexing (v[1 + 2]), adjust spacing or insert missing operator to clarify. \
If you intend to perform typed concatenation (T[1 2]), ensure that T is a type."))
hcat(A::AbstractVecOrMat...) = typed_hcat(promote_eltype(A...), A...)
hcat(A::AbstractVecOrMat{T}...) where {T} = typed_hcat(T, A...)
function _typed_hcat(::Type{T}, A::AbstractVecOrTuple{AbstractVecOrMat}) where T
nargs = length(A)
nrows = size(A[1], 1)
ncols = 0
dense = true
for j = 1:nargs
Aj = A[j]
if size(Aj, 1) != nrows
throw(DimensionMismatch("number of rows of each array must match (got $(map(x->size(x,1), A)))"))
end
dense &= isa(Aj,Array)
nd = ndims(Aj)
ncols += (nd==2 ? size(Aj,2) : 1)
end
B = similar(A[1], T, nrows, ncols)
pos = 1
if dense
for k=1:nargs
Ak = A[k]
n = length(Ak)
copyto!(B, pos, Ak, 1, n)
pos += n
end
else
for k=1:nargs
Ak = A[k]
p1 = pos+(isa(Ak,AbstractMatrix) ? size(Ak, 2) : 1)-1
B[:, pos:p1] = Ak
pos = p1+1
end
end
return B
end
vcat(A::AbstractVecOrMat...) = typed_vcat(promote_eltype(A...), A...)
vcat(A::AbstractVecOrMat{T}...) where {T} = typed_vcat(T, A...)
function _typed_vcat(::Type{T}, A::AbstractVecOrTuple{AbstractVecOrMat}) where T
nargs = length(A)
nrows = sum(a->size(a, 1), A)::Int
ncols = size(A[1], 2)
for j = 2:nargs
if size(A[j], 2) != ncols
throw(DimensionMismatch("number of columns of each array must match (got $(map(x->size(x,2), A)))"))
end
end
B = similar(A[1], T, nrows, ncols)
pos = 1
for k=1:nargs
Ak = A[k]
p1 = pos+size(Ak,1)::Int-1
B[pos:p1, :] = Ak
pos = p1+1
end
return B
end
typed_vcat(::Type{T}, A::AbstractVecOrMat...) where {T} = _typed_vcat(T, A)
reduce(::typeof(vcat), A::AbstractVector{<:AbstractVecOrMat}) =
_typed_vcat(mapreduce(eltype, promote_type, A), A)
reduce(::typeof(hcat), A::AbstractVector{<:AbstractVecOrMat}) =
_typed_hcat(mapreduce(eltype, promote_type, A), A)
## cat: general case
# helper functions
cat_size(A) = (1,)
cat_size(A::AbstractArray) = size(A)
cat_size(A, d) = 1
cat_size(A::AbstractArray, d) = size(A, d)
cat_length(::Any) = 1
cat_length(a::AbstractArray) = length(a)
cat_ndims(a) = 0
cat_ndims(a::AbstractArray) = ndims(a)
cat_indices(A, d) = OneTo(1)
cat_indices(A::AbstractArray, d) = axes(A, d)
cat_similar(A, ::Type{T}, shape::Tuple) where T = Array{T}(undef, shape)
cat_similar(A, ::Type{T}, shape::Vector) where T = Array{T}(undef, shape...)
cat_similar(A::Array, ::Type{T}, shape::Tuple) where T = Array{T}(undef, shape)
cat_similar(A::Array, ::Type{T}, shape::Vector) where T = Array{T}(undef, shape...)
cat_similar(A::AbstractArray, T::Type, shape::Tuple) = similar(A, T, shape)
cat_similar(A::AbstractArray, T::Type, shape::Vector) = similar(A, T, shape...)
# These are for backwards compatibility (even though internal)
cat_shape(dims, shape::Tuple{Vararg{Int}}) = shape
function cat_shape(dims, shapes::Tuple)
out_shape = ()
for s in shapes
out_shape = _cshp(1, dims, out_shape, s)
end
return out_shape
end
# The new way to compute the shape (more inferable than combining cat_size & cat_shape, due to Varargs + issue#36454)
cat_size_shape(dims) = ntuple(zero, Val(length(dims)))
@inline cat_size_shape(dims, X, tail...) = _cat_size_shape(dims, _cshp(1, dims, (), cat_size(X)), tail...)
_cat_size_shape(dims, shape) = shape
@inline _cat_size_shape(dims, shape, X, tail...) = _cat_size_shape(dims, _cshp(1, dims, shape, cat_size(X)), tail...)
_cshp(ndim::Int, ::Tuple{}, ::Tuple{}, ::Tuple{}) = ()
_cshp(ndim::Int, ::Tuple{}, ::Tuple{}, nshape) = nshape
_cshp(ndim::Int, dims, ::Tuple{}, ::Tuple{}) = ntuple(Returns(1), Val(length(dims)))
@inline _cshp(ndim::Int, dims, shape, ::Tuple{}) =
(shape[1] + dims[1], _cshp(ndim + 1, tail(dims), tail(shape), ())...)
@inline _cshp(ndim::Int, dims, ::Tuple{}, nshape) =
(nshape[1], _cshp(ndim + 1, tail(dims), (), tail(nshape))...)
@inline function _cshp(ndim::Int, ::Tuple{}, shape, ::Tuple{})
_cs(ndim, shape[1], 1)
(1, _cshp(ndim + 1, (), tail(shape), ())...)
end
@inline function _cshp(ndim::Int, ::Tuple{}, shape, nshape)
next = _cs(ndim, shape[1], nshape[1])
(next, _cshp(ndim + 1, (), tail(shape), tail(nshape))...)
end
@inline function _cshp(ndim::Int, dims, shape, nshape)
a = shape[1]
b = nshape[1]
next = dims[1] ? a + b : _cs(ndim, a, b)
(next, _cshp(ndim + 1, tail(dims), tail(shape), tail(nshape))...)
end
_cs(d, a, b) = (a == b ? a : throw(DimensionMismatch(
"mismatch in dimension $d (expected $a got $b)")))
dims2cat(::Val{dims}) where dims = dims2cat(dims)
function dims2cat(dims)
if any(≤(0), dims)
throw(ArgumentError("All cat dimensions must be positive integers, but got $dims"))
end
ntuple(in(dims), maximum(dims))
end
_cat(dims, X...) = _cat_t(dims, promote_eltypeof(X...), X...)
@inline function _cat_t(dims, ::Type{T}, X...) where {T}
catdims = dims2cat(dims)
shape = cat_size_shape(catdims, X...)
A = cat_similar(X[1], T, shape)
if count(!iszero, catdims)::Int > 1
fill!(A, zero(T))
end
return __cat(A, shape, catdims, X...)
end
# this version of `cat_t` is not very kind for inference and so its usage should be avoided,
# nevertheless it is here just for compat after https://github.com/JuliaLang/julia/pull/45028
@inline cat_t(::Type{T}, X...; dims) where {T} = _cat_t(dims, T, X...)
# Why isn't this called `__cat!`?
__cat(A, shape, catdims, X...) = __cat_offset!(A, shape, catdims, ntuple(zero, length(shape)), X...)
function __cat_offset!(A, shape, catdims, offsets, x, X...)
# splitting the "work" on x from X... may reduce latency (fewer costly specializations)
newoffsets = __cat_offset1!(A, shape, catdims, offsets, x)
return __cat_offset!(A, shape, catdims, newoffsets, X...)
end
__cat_offset!(A, shape, catdims, offsets) = A
function __cat_offset1!(A, shape, catdims, offsets, x)
inds = ntuple(length(offsets)) do i
(i <= length(catdims) && catdims[i]) ? offsets[i] .+ cat_indices(x, i) : 1:shape[i]
end
_copy_or_fill!(A, inds, x)
newoffsets = ntuple(length(offsets)) do i
(i <= length(catdims) && catdims[i]) ? offsets[i] + cat_size(x, i) : offsets[i]
end
return newoffsets
end
_copy_or_fill!(A, inds, x) = fill!(view(A, inds...), x)
_copy_or_fill!(A, inds, x::AbstractArray) = (A[inds...] = x)
"""
vcat(A...)
Concatenate arrays or numbers vertically. Equivalent to [`cat`](@ref)`(A...; dims=1)`,
and to the syntax `[a; b; c]`.
To concatenate a large vector of arrays, `reduce(vcat, A)` calls an efficient method
when `A isa AbstractVector{<:AbstractVecOrMat}`, rather than working pairwise.
See also [`hcat`](@ref), [`Iterators.flatten`](@ref), [`stack`](@ref).
# Examples
```jldoctest
julia> v = vcat([1,2], [3,4])
4-element Vector{Int64}:
1
2
3
4
julia> v == vcat(1, 2, [3,4]) # accepts numbers
true
julia> v == [1; 2; [3,4]] # syntax for the same operation
true
julia> summary(ComplexF64[1; 2; [3,4]]) # syntax for supplying the element type
"4-element Vector{ComplexF64}"
julia> vcat(range(1, 2, length=3)) # collects lazy ranges
3-element Vector{Float64}:
1.0
1.5
2.0
julia> two = ([10, 20, 30]', Float64[4 5 6; 7 8 9]) # row vector and a matrix
([10 20 30], [4.0 5.0 6.0; 7.0 8.0 9.0])
julia> vcat(two...)
3×3 Matrix{Float64}:
10.0 20.0 30.0
4.0 5.0 6.0
7.0 8.0 9.0
julia> vs = [[1, 2], [3, 4], [5, 6]];
julia> reduce(vcat, vs) # more efficient than vcat(vs...)
6-element Vector{Int64}:
1
2
3
4
5
6
julia> ans == collect(Iterators.flatten(vs))
true
```
"""
vcat(X...) = cat(X...; dims=Val(1))
"""
hcat(A...)
Concatenate arrays or numbers horizontally. Equivalent to [`cat`](@ref)`(A...; dims=2)`,
and to the syntax `[a b c]` or `[a;; b;; c]`.
For a large vector of arrays, `reduce(hcat, A)` calls an efficient method
when `A isa AbstractVector{<:AbstractVecOrMat}`.
For a vector of vectors, this can also be written [`stack`](@ref)`(A)`.
See also [`vcat`](@ref), [`hvcat`](@ref).
# Examples
```jldoctest
julia> hcat([1,2], [3,4], [5,6])
2×3 Matrix{Int64}:
1 3 5
2 4 6
julia> hcat(1, 2, [30 40], [5, 6, 7]') # accepts numbers
1×7 Matrix{Int64}:
1 2 30 40 5 6 7
julia> ans == [1 2 [30 40] [5, 6, 7]'] # syntax for the same operation
true
julia> Float32[1 2 [30 40] [5, 6, 7]'] # syntax for supplying the eltype
1×7 Matrix{Float32}:
1.0 2.0 30.0 40.0 5.0 6.0 7.0
julia> ms = [zeros(2,2), [1 2; 3 4], [50 60; 70 80]];
julia> reduce(hcat, ms) # more efficient than hcat(ms...)
2×6 Matrix{Float64}:
0.0 0.0 1.0 2.0 50.0 60.0
0.0 0.0 3.0 4.0 70.0 80.0
julia> stack(ms) |> summary # disagrees on a vector of matrices
"2×2×3 Array{Float64, 3}"
julia> hcat(Int[], Int[], Int[]) # empty vectors, each of size (0,)
0×3 Matrix{Int64}
julia> hcat([1.1, 9.9], Matrix(undef, 2, 0)) # hcat with empty 2×0 Matrix
2×1 Matrix{Any}:
1.1
9.9
```
"""
hcat(X...) = cat(X...; dims=Val(2))
typed_vcat(::Type{T}, X...) where T = _cat_t(Val(1), T, X...)
typed_hcat(::Type{T}, X...) where T = _cat_t(Val(2), T, X...)
"""
cat(A...; dims)
Concatenate the input arrays along the dimensions specified in `dims`.
Along a dimension `d in dims`, the size of the output array is `sum(size(a,d) for
a in A)`.
Along other dimensions, all input arrays should have the same size,
which will also be the size of the output array along those dimensions.
If `dims` is a single number, the different arrays are tightly packed along that dimension.
If `dims` is an iterable containing several dimensions, the positions along these dimensions
are increased simultaneously for each input array, filling with zero elsewhere.
This allows one to construct block-diagonal matrices as `cat(matrices...; dims=(1,2))`,
and their higher-dimensional analogues.
The special case `dims=1` is [`vcat`](@ref), and `dims=2` is [`hcat`](@ref).
See also [`hvcat`](@ref), [`hvncat`](@ref), [`stack`](@ref), [`repeat`](@ref).
The keyword also accepts `Val(dims)`.
!!! compat "Julia 1.8"
For multiple dimensions `dims = Val(::Tuple)` was added in Julia 1.8.
# Examples
Concatenate two arrays in different dimensions:
```jldoctest
julia> a = [1 2 3]
1×3 Matrix{Int64}:
1 2 3
julia> b = [4 5 6]
1×3 Matrix{Int64}:
4 5 6
julia> cat(a, b; dims=1)
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> cat(a, b; dims=2)
1×6 Matrix{Int64}:
1 2 3 4 5 6
julia> cat(a, b; dims=(1, 2))
2×6 Matrix{Int64}:
1 2 3 0 0 0
0 0 0 4 5 6
```
# Extended Help
Concatenate 3D arrays:
```jldoctest
julia> a = ones(2, 2, 3);
julia> b = ones(2, 2, 4);
julia> c = cat(a, b; dims=3);
julia> size(c) == (2, 2, 7)
true
```
Concatenate arrays of different sizes:
```jldoctest
julia> cat([1 2; 3 4], [pi, pi], fill(10, 2,3,1); dims=2) # same as hcat
2×6×1 Array{Float64, 3}:
[:, :, 1] =
1.0 2.0 3.14159 10.0 10.0 10.0
3.0 4.0 3.14159 10.0 10.0 10.0
```
Construct a block diagonal matrix:
```
julia> cat(true, trues(2,2), trues(4)', dims=(1,2)) # block-diagonal
4×7 Matrix{Bool}:
1 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 1 0 0 0 0
0 0 0 1 1 1 1
```
```
julia> cat(1, [2], [3;;]; dims=Val(2))
1×3 Matrix{Int64}:
1 2 3
```
!!! note
`cat` does not join two strings, you may want to use `*`.
```jldoctest
julia> a = "aaa";
julia> b = "bbb";
julia> cat(a, b; dims=1)
2-element Vector{String}:
"aaa"
"bbb"
julia> cat(a, b; dims=2)
1×2 Matrix{String}:
"aaa" "bbb"
julia> a * b
"aaabbb"
```
"""
@inline cat(A...; dims) = _cat(dims, A...)
# `@constprop :aggressive` allows `catdims` to be propagated as constant improving return type inference
@constprop :aggressive _cat(catdims, A::AbstractArray{T}...) where {T} = _cat_t(catdims, T, A...)
# The specializations for 1 and 2 inputs are important
# especially when running with --inline=no, see #11158
vcat(A::AbstractArray) = cat(A; dims=Val(1))
vcat(A::AbstractArray, B::AbstractArray) = cat(A, B; dims=Val(1))
vcat(A::AbstractArray...) = cat(A...; dims=Val(1))
vcat(A::Union{AbstractArray,Number}...) = cat(A...; dims=Val(1))
hcat(A::AbstractArray) = cat(A; dims=Val(2))
hcat(A::AbstractArray, B::AbstractArray) = cat(A, B; dims=Val(2))
hcat(A::AbstractArray...) = cat(A...; dims=Val(2))
hcat(A::Union{AbstractArray,Number}...) = cat(A...; dims=Val(2))
typed_vcat(T::Type, A::AbstractArray) = _cat_t(Val(1), T, A)
typed_vcat(T::Type, A::AbstractArray, B::AbstractArray) = _cat_t(Val(1), T, A, B)
typed_vcat(T::Type, A::AbstractArray...) = _cat_t(Val(1), T, A...)
typed_hcat(T::Type, A::AbstractArray) = _cat_t(Val(2), T, A)
typed_hcat(T::Type, A::AbstractArray, B::AbstractArray) = _cat_t(Val(2), T, A, B)
typed_hcat(T::Type, A::AbstractArray...) = _cat_t(Val(2), T, A...)
# 2d horizontal and vertical concatenation
# these are produced in lowering if splatting occurs inside hvcat
hvcat_rows(rows::Tuple...) = hvcat(map(length, rows), (rows...)...)
typed_hvcat_rows(T::Type, rows::Tuple...) = typed_hvcat(T, map(length, rows), (rows...)...)
function hvcat(nbc::Int, as...)
# nbc = # of block columns
n = length(as)
mod(n,nbc) != 0 &&
throw(ArgumentError("number of arrays $n is not a multiple of the requested number of block columns $nbc"))
nbr = div(n,nbc)
hvcat(ntuple(Returns(nbc), nbr), as...)
end
"""
hvcat(blocks_per_row::Union{Tuple{Vararg{Int}}, Int}, values...)
Horizontal and vertical concatenation in one call. This function is called for block matrix
syntax. The first argument specifies the number of arguments to concatenate in each block
row. If the first argument is a single integer `n`, then all block rows are assumed to have `n`
block columns.
# Examples
```jldoctest
julia> a, b, c, d, e, f = 1, 2, 3, 4, 5, 6
(1, 2, 3, 4, 5, 6)
julia> [a b c; d e f]
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> hvcat((3,3), a,b,c,d,e,f)
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> [a b; c d; e f]
3×2 Matrix{Int64}:
1 2
3 4
5 6
julia> hvcat((2,2,2), a,b,c,d,e,f)
3×2 Matrix{Int64}:
1 2
3 4
5 6
julia> hvcat((2,2,2), a,b,c,d,e,f) == hvcat(2, a,b,c,d,e,f)
true
```
"""
hvcat(rows::Tuple{Vararg{Int}}, xs::AbstractArray...) = typed_hvcat(promote_eltype(xs...), rows, xs...)
hvcat(rows::Tuple{Vararg{Int}}, xs::AbstractArray{T}...) where {T} = typed_hvcat(T, rows, xs...)
function typed_hvcat(::Type{T}, rows::Tuple{Vararg{Int}}, as::AbstractVecOrMat...) where T
nbr = length(rows) # number of block rows
nc = 0
for i=1:rows[1]
nc += size(as[i],2)
end
nr = 0
a = 1
for i = 1:nbr
nr += size(as[a],1)
a += rows[i]
end
out = similar(as[1], T, nr, nc)
a = 1
r = 1
for i = 1:nbr
c = 1
szi = size(as[a],1)
for j = 1:rows[i]
Aj = as[a+j-1]
szj = size(Aj,2)
if size(Aj,1) != szi
throw(DimensionMismatch("mismatched height in block row $(i) (expected $szi, got $(size(Aj,1)))"))
end
if c-1+szj > nc
throw(DimensionMismatch("block row $(i) has mismatched number of columns (expected $nc, got $(c-1+szj))"))
end
out[r:r-1+szi, c:c-1+szj] = Aj
c += szj
end
if c != nc+1
throw(DimensionMismatch("block row $(i) has mismatched number of columns (expected $nc, got $(c-1))"))
end
r += szi
a += rows[i]
end
out
end
hvcat(rows::Tuple{Vararg{Int}}) = []
typed_hvcat(::Type{T}, rows::Tuple{Vararg{Int}}) where {T} = Vector{T}()
function hvcat(rows::Tuple{Vararg{Int}}, xs::T...) where T<:Number
nr = length(rows)
nc = rows[1]
a = Matrix{T}(undef, nr, nc)
if length(a) != length(xs)
throw(ArgumentError("argument count does not match specified shape (expected $(length(a)), got $(length(xs)))"))
end
k = 1
@inbounds for i=1:nr
if nc != rows[i]
throw(DimensionMismatch("row $(i) has mismatched number of columns (expected $nc, got $(rows[i]))"))
end
for j=1:nc
a[i,j] = xs[k]
k += 1
end
end
a
end
function hvcat_fill!(a::Array, xs::Tuple)
nr, nc = size(a,1), size(a,2)
len = length(xs)
if nr*nc != len
throw(ArgumentError("argument count $(len) does not match specified shape $((nr,nc))"))
end
k = 1
for i=1:nr
@inbounds for j=1:nc
a[i,j] = xs[k]
k += 1
end
end
a
end
hvcat(rows::Tuple{Vararg{Int}}, xs::Number...) = typed_hvcat(promote_typeof(xs...), rows, xs...)
hvcat(rows::Tuple{Vararg{Int}}, xs...) = typed_hvcat(promote_eltypeof(xs...), rows, xs...)
# the following method is needed to provide a more specific one compared to LinearAlgebra/uniformscaling.jl
hvcat(rows::Tuple{Vararg{Int}}, xs::Union{AbstractArray,Number}...) = typed_hvcat(promote_eltypeof(xs...), rows, xs...)
function typed_hvcat(::Type{T}, rows::Tuple{Vararg{Int}}, xs::Number...) where T
nr = length(rows)
nc = rows[1]
for i = 2:nr
if nc != rows[i]
throw(DimensionMismatch("row $(i) has mismatched number of columns (expected $nc, got $(rows[i]))"))
end
end
hvcat_fill!(Matrix{T}(undef, nr, nc), xs)
end
function typed_hvcat(::Type{T}, rows::Tuple{Vararg{Int}}, as...) where T
nbr = length(rows) # number of block rows
rs = Vector{Any}(undef, nbr)
a = 1
for i = 1:nbr
rs[i] = typed_hcat(T, as[a:a-1+rows[i]]...)
a += rows[i]
end
T[rs...;]
end
## N-dimensional concatenation ##
"""
hvncat(dim::Int, row_first, values...)
hvncat(dims::Tuple{Vararg{Int}}, row_first, values...)
hvncat(shape::Tuple{Vararg{Tuple}}, row_first, values...)
Horizontal, vertical, and n-dimensional concatenation of many `values` in one call.
This function is called for block matrix syntax. The first argument either specifies the
shape of the concatenation, similar to `hvcat`, as a tuple of tuples, or the dimensions that
specify the key number of elements along each axis, and is used to determine the output
dimensions. The `dims` form is more performant, and is used by default when the concatenation
operation has the same number of elements along each axis (e.g., [a b; c d;;; e f ; g h]).
The `shape` form is used when the number of elements along each axis is unbalanced
(e.g., [a b ; c]). Unbalanced syntax needs additional validation overhead. The `dim` form
is an optimization for concatenation along just one dimension. `row_first` indicates how
`values` are ordered. The meaning of the first and second elements of `shape` are also
swapped based on `row_first`.
# Examples
```jldoctest
julia> a, b, c, d, e, f = 1, 2, 3, 4, 5, 6
(1, 2, 3, 4, 5, 6)
julia> [a b c;;; d e f]
1×3×2 Array{Int64, 3}:
[:, :, 1] =
1 2 3
[:, :, 2] =
4 5 6
julia> hvncat((2,1,3), false, a,b,c,d,e,f)
2×1×3 Array{Int64, 3}:
[:, :, 1] =
1
2
[:, :, 2] =
3
4
[:, :, 3] =
5
6
julia> [a b;;; c d;;; e f]
1×2×3 Array{Int64, 3}:
[:, :, 1] =
1 2
[:, :, 2] =
3 4
[:, :, 3] =
5 6
julia> hvncat(((3, 3), (3, 3), (6,)), true, a, b, c, d, e, f)
1×3×2 Array{Int64, 3}:
[:, :, 1] =
1 2 3
[:, :, 2] =
4 5 6
```
# Examples for construction of the arguments
```
[a b c ; d e f ;;;
g h i ; j k l ;;;
m n o ; p q r ;;;
s t u ; v w x]
⇒ dims = (2, 3, 4)
[a b ; c ;;; d ;;;;]
___ _ _
2 1 1 = elements in each row (2, 1, 1)
_______ _
3 1 = elements in each column (3, 1)
_____________
4 = elements in each 3d slice (4,)
_____________
4 = elements in each 4d slice (4,)
⇒ shape = ((2, 1, 1), (3, 1), (4,), (4,)) with `row_first` = true
```
"""
hvncat(dimsshape::Tuple, row_first::Bool, xs...) = _hvncat(dimsshape, row_first, xs...)
hvncat(dim::Int, xs...) = _hvncat(dim, true, xs...)
_hvncat(dimsshape::Union{Tuple, Int}, row_first::Bool) = _typed_hvncat(Any, dimsshape, row_first)
_hvncat(dimsshape::Union{Tuple, Int}, row_first::Bool, xs...) = _typed_hvncat(promote_eltypeof(xs...), dimsshape, row_first, xs...)
_hvncat(dimsshape::Union{Tuple, Int}, row_first::Bool, xs::T...) where T<:Number = _typed_hvncat(T, dimsshape, row_first, xs...)
_hvncat(dimsshape::Union{Tuple, Int}, row_first::Bool, xs::Number...) = _typed_hvncat(promote_typeof(xs...), dimsshape, row_first, xs...)
_hvncat(dimsshape::Union{Tuple, Int}, row_first::Bool, xs::AbstractArray...) = _typed_hvncat(promote_eltype(xs...), dimsshape, row_first, xs...)
_hvncat(dimsshape::Union{Tuple, Int}, row_first::Bool, xs::AbstractArray{T}...) where T = _typed_hvncat(T, dimsshape, row_first, xs...)
typed_hvncat(T::Type, dimsshape::Tuple, row_first::Bool, xs...) = _typed_hvncat(T, dimsshape, row_first, xs...)
typed_hvncat(T::Type, dim::Int, xs...) = _typed_hvncat(T, Val(dim), xs...)
# 1-dimensional hvncat methods
_typed_hvncat(::Type, ::Val{0}) = _typed_hvncat_0d_only_one()
_typed_hvncat(T::Type, ::Val{0}, x) = fill(convert(T, x))
_typed_hvncat(T::Type, ::Val{0}, x::Number) = fill(convert(T, x))
_typed_hvncat(T::Type, ::Val{0}, x::AbstractArray) = convert.(T, x)
_typed_hvncat(::Type, ::Val{0}, ::Any...) = _typed_hvncat_0d_only_one()
_typed_hvncat(::Type, ::Val{0}, ::Number...) = _typed_hvncat_0d_only_one()
_typed_hvncat(::Type, ::Val{0}, ::AbstractArray...) = _typed_hvncat_0d_only_one()
_typed_hvncat_0d_only_one() =
throw(ArgumentError("a 0-dimensional array may only contain exactly one element"))
# `@constprop :aggressive` here to form constant `Val(dim)` type to get type stability
@constprop :aggressive _typed_hvncat(T::Type, dim::Int, ::Bool, xs...) = _typed_hvncat(T, Val(dim), xs...) # catches from _hvncat type promoters
function _typed_hvncat(::Type{T}, ::Val{N}) where {T, N}
N < 0 &&
throw(ArgumentError("concatenation dimension must be non-negative"))
return Array{T, N}(undef, ntuple(x -> 0, Val(N)))
end
function _typed_hvncat(T::Type, ::Val{N}, xs::Number...) where N
N < 0 &&
throw(ArgumentError("concatenation dimension must be non-negative"))
A = cat_similar(xs[1], T, (ntuple(x -> 1, Val(N - 1))..., length(xs)))
hvncat_fill!(A, false, xs)
return A
end
function _typed_hvncat(::Type{T}, ::Val{N}, as::AbstractArray...) where {T, N}
# optimization for arrays that can be concatenated by copying them linearly into the destination
# conditions: the elements must all have 1-length dimensions above N
length(as) > 0 ||
throw(ArgumentError("must have at least one element"))
N < 0 &&
throw(ArgumentError("concatenation dimension must be non-negative"))
for a ∈ as
ndims(a) <= N || all(x -> size(a, x) == 1, (N + 1):ndims(a)) ||
return _typed_hvncat(T, (ntuple(x -> 1, Val(N - 1))..., length(as), 1), false, as...)
# the extra 1 is to avoid an infinite cycle
end
nd = N
Ndim = 0
for i ∈ eachindex(as)
Ndim += cat_size(as[i], N)
nd = max(nd, cat_ndims(as[i]))
for d ∈ 1:N - 1
cat_size(as[1], d) == cat_size(as[i], d) || throw(DimensionMismatch("mismatched size along axis $d in element $i"))
end
end
A = cat_similar(as[1], T, (ntuple(d -> size(as[1], d), N - 1)..., Ndim, ntuple(x -> 1, nd - N)...))
k = 1
for a ∈ as
for i ∈ eachindex(a)
A[k] = a[i]
k += 1
end
end
return A
end
function _typed_hvncat(::Type{T}, ::Val{N}, as...) where {T, N}
length(as) > 0 ||
throw(ArgumentError("must have at least one element"))
N < 0 &&
throw(ArgumentError("concatenation dimension must be non-negative"))
nd = N
Ndim = 0
for i ∈ eachindex(as)
Ndim += cat_size(as[i], N)
nd = max(nd, cat_ndims(as[i]))
for d ∈ 1:N-1
cat_size(as[i], d) == 1 ||
throw(DimensionMismatch("all dimensions of element $i other than $N must be of length 1"))
end
end
A = Array{T, nd}(undef, ntuple(x -> 1, Val(N - 1))..., Ndim, ntuple(x -> 1, nd - N)...)
k = 1
for a ∈ as
if a isa AbstractArray
lena = length(a)
copyto!(A, k, a, 1, lena)
k += lena
else
A[k] = a
k += 1
end
end
return A
end
# 0-dimensional cases for balanced and unbalanced hvncat method
_typed_hvncat(T::Type, ::Tuple{}, ::Bool, x...) = _typed_hvncat(T, Val(0), x...)
_typed_hvncat(T::Type, ::Tuple{}, ::Bool, x::Number...) = _typed_hvncat(T, Val(0), x...)
# balanced dimensions hvncat methods
_typed_hvncat(T::Type, dims::Tuple{Int}, ::Bool, as...) = _typed_hvncat_1d(T, dims[1], Val(false), as...)
_typed_hvncat(T::Type, dims::Tuple{Int}, ::Bool, as::Number...) = _typed_hvncat_1d(T, dims[1], Val(false), as...)
function _typed_hvncat_1d(::Type{T}, ds::Int, ::Val{row_first}, as...) where {T, row_first}
lengthas = length(as)
ds > 0 ||
throw(ArgumentError("`dimsshape` argument must consist of positive integers"))
lengthas == ds ||
throw(ArgumentError("number of elements does not match `dimshape` argument; expected $ds, got $lengthas"))
if row_first
return _typed_hvncat(T, Val(2), as...)
else
return _typed_hvncat(T, Val(1), as...)
end
end
function _typed_hvncat(::Type{T}, dims::NTuple{N, Int}, row_first::Bool, xs::Number...) where {T, N}
all(>(0), dims) ||
throw(ArgumentError("`dims` argument must contain positive integers"))
A = Array{T, N}(undef, dims...)
lengtha = length(A) # Necessary to store result because throw blocks are being deoptimized right now, which leads to excessive allocations
lengthx = length(xs) # Cuts from 3 allocations to 1.
if lengtha != lengthx
throw(ArgumentError("argument count does not match specified shape (expected $lengtha, got $lengthx)"))
end
hvncat_fill!(A, row_first, xs)
return A
end
function hvncat_fill!(A::Array, row_first::Bool, xs::Tuple)
nr, nc = size(A, 1), size(A, 2)
na = prod(size(A)[3:end])
len = length(xs)
nrc = nr * nc
if nrc * na != len
throw(ArgumentError("argument count $(len) does not match specified shape $(size(A))"))
end
# putting these in separate functions leads to unnecessary allocations
if row_first
k = 1
for d ∈ 1:na
dd = nrc * (d - 1)
for i ∈ 1:nr
Ai = dd + i
for j ∈ 1:nc
@inbounds A[Ai] = xs[k]
k += 1
Ai += nr
end
end
end
else
for k ∈ eachindex(xs)
@inbounds A[k] = xs[k]
end
end
end
function _typed_hvncat(T::Type, dims::NTuple{N, Int}, row_first::Bool, as...) where {N}
# function barrier after calculating the max is necessary for high performance
nd = max(maximum(cat_ndims(a) for a ∈ as), N)
return _typed_hvncat_dims(T, (dims..., ntuple(x -> 1, nd - N)...), row_first, as)
end
function _typed_hvncat_dims(::Type{T}, dims::NTuple{N, Int}, row_first::Bool, as::Tuple) where {T, N}
length(as) > 0 ||
throw(ArgumentError("must have at least one element"))
all(>(0), dims) ||
throw(ArgumentError("`dims` argument must contain positive integers"))
d1 = row_first ? 2 : 1
d2 = row_first ? 1 : 2
outdims = zeros(Int, N)
# validate shapes for lowest level of concatenation
d = findfirst(>(1), dims)
if d !== nothing # all dims are 1
if row_first && d < 3
d = d == 1 ? 2 : 1
end
nblocks = length(as) ÷ dims[d]
for b ∈ 1:nblocks
offset = ((b - 1) * dims[d])
startelementi = offset + 1
for i ∈ offset .+ (2:dims[d])
for dd ∈ 1:N
dd == d && continue
if cat_size(as[startelementi], dd) != cat_size(as[i], dd)
throw(DimensionMismatch("incompatible shape in element $i"))
end
end
end
end
end
# discover number of rows or columns
for i ∈ 1:dims[d1]
outdims[d1] += cat_size(as[i], d1)
end
currentdims = zeros(Int, N)
blockcount = 0
elementcount = 0
for i ∈ eachindex(as)
elementcount += cat_length(as[i])
currentdims[d1] += cat_size(as[i], d1)
if currentdims[d1] == outdims[d1]
currentdims[d1] = 0
for d ∈ (d2, 3:N...)
currentdims[d] += cat_size(as[i], d)
if outdims[d] == 0 # unfixed dimension
blockcount += 1
if blockcount == dims[d]
outdims[d] = currentdims[d]
currentdims[d] = 0
blockcount = 0
else
break
end
else # fixed dimension
if currentdims[d] == outdims[d] # end of dimension
currentdims[d] = 0
elseif currentdims[d] < outdims[d] # dimension in progress
break
else # exceeded dimension
throw(DimensionMismatch("argument $i has too many elements along axis $d"))
end
end
end
elseif currentdims[d1] > outdims[d1] # exceeded dimension
throw(DimensionMismatch("argument $i has too many elements along axis $d1"))
end
end
outlen = prod(outdims)
elementcount == outlen ||
throw(DimensionMismatch("mismatched number of elements; expected $(outlen), got $(elementcount)"))
# copy into final array
A = cat_similar(as[1], T, outdims)
# @assert all(==(0), currentdims)
outdims .= 0
hvncat_fill!(A, currentdims, outdims, d1, d2, as)
return A
end
# unbalanced dimensions hvncat methods
function _typed_hvncat(T::Type, shape::Tuple{Tuple}, row_first::Bool, xs...)
length(shape[1]) > 0 ||
throw(ArgumentError("each level of `shape` argument must have at least one value"))
return _typed_hvncat_1d(T, shape[1][1], Val(row_first), xs...)
end
function _typed_hvncat(T::Type, shape::NTuple{N, Tuple}, row_first::Bool, as...) where {N}
# function barrier after calculating the max is necessary for high performance
nd = max(maximum(cat_ndims(a) for a ∈ as), N)
return _typed_hvncat_shape(T, (shape..., ntuple(x -> shape[end], nd - N)...), row_first, as)
end
function _typed_hvncat_shape(::Type{T}, shape::NTuple{N, Tuple}, row_first, as::Tuple) where {T, N}
length(as) > 0 ||
throw(ArgumentError("must have at least one element"))
all(>(0), tuple((shape...)...)) ||
throw(ArgumentError("`shape` argument must consist of positive integers"))
d1 = row_first ? 2 : 1
d2 = row_first ? 1 : 2
shapev = collect(shape) # saves allocations later
all(!isempty, shapev) ||
throw(ArgumentError("each level of `shape` argument must have at least one value"))
length(shapev[end]) == 1 ||
throw(ArgumentError("last level of shape must contain only one integer"))
shapelength = shapev[end][1]
lengthas = length(as)
shapelength == lengthas || throw(ArgumentError("number of elements does not match shape; expected $(shapelength), got $lengthas)"))
# discover dimensions
nd = max(N, cat_ndims(as[1]))
outdims = fill(-1, nd)
currentdims = zeros(Int, nd)
blockcounts = zeros(Int, nd)
shapepos = ones(Int, nd)
elementcount = 0
for i ∈ eachindex(as)
elementcount += cat_length(as[i])
wasstartblock = false
for d ∈ 1:N
ad = (d < 3 && row_first) ? (d == 1 ? 2 : 1) : d
dsize = cat_size(as[i], ad)
blockcounts[d] += 1
if d == 1 || i == 1 || wasstartblock
currentdims[d] += dsize
elseif dsize != cat_size(as[i - 1], ad)
throw(DimensionMismatch("argument $i has a mismatched number of elements along axis $ad; \
expected $(cat_size(as[i - 1], ad)), got $dsize"))
end
wasstartblock = blockcounts[d] == 1 # remember for next dimension
isendblock = blockcounts[d] == shapev[d][shapepos[d]]
if isendblock
if outdims[d] == -1
outdims[d] = currentdims[d]
elseif outdims[d] != currentdims[d]
throw(DimensionMismatch("argument $i has a mismatched number of elements along axis $ad; \
expected $(abs(outdims[d] - (currentdims[d] - dsize))), got $dsize"))
end
currentdims[d] = 0
blockcounts[d] = 0
shapepos[d] += 1
d > 1 && (blockcounts[d - 1] == 0 ||
throw(DimensionMismatch("shape in level $d is inconsistent; level counts must nest \
evenly into each other")))
end
end
end
outlen = prod(outdims)
elementcount == outlen ||
throw(ArgumentError("mismatched number of elements; expected $(outlen), got $(elementcount)"))
if row_first
outdims[1], outdims[2] = outdims[2], outdims[1]
end
# @assert all(==(0), currentdims)
# @assert all(==(0), blockcounts)
# copy into final array
A = cat_similar(as[1], T, outdims)
hvncat_fill!(A, currentdims, blockcounts, d1, d2, as)
return A
end
function hvncat_fill!(A::AbstractArray{T, N}, scratch1::Vector{Int}, scratch2::Vector{Int},
d1::Int, d2::Int, as::Tuple) where {T, N}
N > 1 || throw(ArgumentError("dimensions of the destination array must be at least 2"))
length(scratch1) == length(scratch2) == N ||
throw(ArgumentError("scratch vectors must have as many elements as the destination array has dimensions"))
0 < d1 < 3 &&
0 < d2 < 3 &&
d1 != d2 ||
throw(ArgumentError("d1 and d2 must be either 1 or 2, exclusive."))
outdims = size(A)
offsets = scratch1
inneroffsets = scratch2
for a ∈ as
if isa(a, AbstractArray)
for ai ∈ a
@inbounds Ai = hvncat_calcindex(offsets, inneroffsets, outdims, N)
A[Ai] = ai
@inbounds for j ∈ 1:N
inneroffsets[j] += 1
inneroffsets[j] < cat_size(a, j) && break
inneroffsets[j] = 0
end
end
else
@inbounds Ai = hvncat_calcindex(offsets, inneroffsets, outdims, N)
A[Ai] = a
end
@inbounds for j ∈ (d1, d2, 3:N...)
offsets[j] += cat_size(a, j)
offsets[j] < outdims[j] && break
offsets[j] = 0
end
end
end
@propagate_inbounds function hvncat_calcindex(offsets::Vector{Int}, inneroffsets::Vector{Int},
outdims::Tuple{Vararg{Int}}, nd::Int)
Ai = inneroffsets[1] + offsets[1] + 1
for j ∈ 2:nd
increment = inneroffsets[j] + offsets[j]
for k ∈ 1:j-1
increment *= outdims[k]
end
Ai += increment
end
Ai
end
"""
stack(iter; [dims])
Combine a collection of arrays (or other iterable objects) of equal size
into one larger array, by arranging them along one or more new dimensions.
By default the axes of the elements are placed first,
giving `size(result) = (size(first(iter))..., size(iter)...)`.
This has the same order of elements as [`Iterators.flatten`](@ref)`(iter)`.
With keyword `dims::Integer`, instead the `i`th element of `iter` becomes the slice
[`selectdim`](@ref)`(result, dims, i)`, so that `size(result, dims) == length(iter)`.
In this case `stack` reverses the action of [`eachslice`](@ref) with the same `dims`.
The various [`cat`](@ref) functions also combine arrays. However, these all
extend the arrays' existing (possibly trivial) dimensions, rather than placing
the arrays along new dimensions.
They also accept arrays as separate arguments, rather than a single collection.
!!! compat "Julia 1.9"
This function requires at least Julia 1.9.
# Examples
```jldoctest
julia> vecs = (1:2, [30, 40], Float32[500, 600]);
julia> mat = stack(vecs)
2×3 Matrix{Float32}:
1.0 30.0 500.0
2.0 40.0 600.0
julia> mat == hcat(vecs...) == reduce(hcat, collect(vecs))
true
julia> vec(mat) == vcat(vecs...) == reduce(vcat, collect(vecs))
true
julia> stack(zip(1:4, 10:99)) # accepts any iterators of iterators
2×4 Matrix{Int64}:
1 2 3 4
10 11 12 13
julia> vec(ans) == collect(Iterators.flatten(zip(1:4, 10:99)))
true
julia> stack(vecs; dims=1) # unlike any cat function, 1st axis of vecs[1] is 2nd axis of result
3×2 Matrix{Float32}:
1.0 2.0
30.0 40.0
500.0 600.0
julia> x = rand(3,4);
julia> x == stack(eachcol(x)) == stack(eachrow(x), dims=1) # inverse of eachslice
true
```
Higher-dimensional examples:
```jldoctest
julia> A = rand(5, 7, 11);
julia> E = eachslice(A, dims=2); # a vector of matrices
julia> (element = size(first(E)), container = size(E))
(element = (5, 11), container = (7,))
julia> stack(E) |> size
(5, 11, 7)
julia> stack(E) == stack(E; dims=3) == cat(E...; dims=3)
true
julia> A == stack(E; dims=2)
true
julia> M = (fill(10i+j, 2, 3) for i in 1:5, j in 1:7);
julia> (element = size(first(M)), container = size(M))
(element = (2, 3), container = (5, 7))
julia> stack(M) |> size # keeps all dimensions
(2, 3, 5, 7)
julia> stack(M; dims=1) |> size # vec(container) along dims=1
(35, 2, 3)
julia> hvcat(5, M...) |> size # hvcat puts matrices next to each other
(14, 15)
```
"""
stack(iter; dims=:) = _stack(dims, iter)
"""
stack(f, args...; [dims])
Apply a function to each element of a collection, and `stack` the result.
Or to several collections, [`zip`](@ref)ped together.
The function should return arrays (or tuples, or other iterators) all of the same size.
These become slices of the result, each separated along `dims` (if given) or by default
along the last dimensions.
See also [`mapslices`](@ref), [`eachcol`](@ref).
# Examples
```jldoctest
julia> stack(c -> (c, c-32), "julia")
2×5 Matrix{Char}:
'j' 'u' 'l' 'i' 'a'
'J' 'U' 'L' 'I' 'A'
julia> stack(eachrow([1 2 3; 4 5 6]), (10, 100); dims=1) do row, n
vcat(row, row .* n, row ./ n)
end
2×9 Matrix{Float64}:
1.0 2.0 3.0 10.0 20.0 30.0 0.1 0.2 0.3
4.0 5.0 6.0 400.0 500.0 600.0 0.04 0.05 0.06
```
"""
stack(f, iter; dims=:) = _stack(dims, f(x) for x in iter)
stack(f, xs, yzs...; dims=:) = _stack(dims, f(xy...) for xy in zip(xs, yzs...))
_stack(dims::Union{Integer, Colon}, iter) = _stack(dims, IteratorSize(iter), iter)
_stack(dims, ::IteratorSize, iter) = _stack(dims, collect(iter))
function _stack(dims, ::Union{HasShape, HasLength}, iter)
S = @default_eltype iter
T = S != Union{} ? eltype(S) : Any # Union{} occurs for e.g. stack(1,2), postpone the error
if isconcretetype(T)
_typed_stack(dims, T, S, iter)
else # Need to look inside, but shouldn't run an expensive iterator twice:
array = iter isa Union{Tuple, AbstractArray} ? iter : collect(iter)
isempty(array) && return _empty_stack(dims, T, S, iter)
T2 = mapreduce(eltype, promote_type, array)
_typed_stack(dims, T2, eltype(array), array)
end
end
function _typed_stack(::Colon, ::Type{T}, ::Type{S}, A, Aax=_iterator_axes(A)) where {T, S}
xit = iterate(A)
nothing === xit && return _empty_stack(:, T, S, A)
x1, _ = xit
ax1 = _iterator_axes(x1)
B = similar(_ensure_array(x1), T, ax1..., Aax...)
off = firstindex(B)
len = length(x1)
while xit !== nothing
x, state = xit
_stack_size_check(x, ax1)
copyto!(B, off, x)
off += len
xit = iterate(A, state)
end
B
end
_iterator_axes(x) = _iterator_axes(x, IteratorSize(x))
_iterator_axes(x, ::HasLength) = (OneTo(length(x)),)
_iterator_axes(x, ::IteratorSize) = axes(x)
# For some dims values, stack(A; dims) == stack(vec(A)), and the : path will be faster
_typed_stack(dims::Integer, ::Type{T}, ::Type{S}, A) where {T,S} =
_typed_stack(dims, T, S, IteratorSize(S), A)
_typed_stack(dims::Integer, ::Type{T}, ::Type{S}, ::HasLength, A) where {T,S} =
_typed_stack(dims, T, S, HasShape{1}(), A)
function _typed_stack(dims::Integer, ::Type{T}, ::Type{S}, ::HasShape{N}, A) where {T,S,N}
if dims == N+1
_typed_stack(:, T, S, A, (_vec_axis(A),))
else
_dim_stack(dims, T, S, A)
end
end
_typed_stack(dims::Integer, ::Type{T}, ::Type{S}, ::IteratorSize, A) where {T,S} =
_dim_stack(dims, T, S, A)
_vec_axis(A, ax=_iterator_axes(A)) = length(ax) == 1 ? only(ax) : OneTo(prod(length, ax; init=1))
@constprop :aggressive function _dim_stack(dims::Integer, ::Type{T}, ::Type{S}, A) where {T,S}
xit = Iterators.peel(A)
nothing === xit && return _empty_stack(dims, T, S, A)
x1, xrest = xit
ax1 = _iterator_axes(x1)
N1 = length(ax1)+1
dims in 1:N1 || throw(ArgumentError(LazyString("cannot stack slices ndims(x) = ", N1-1, " along dims = ", dims)))
newaxis = _vec_axis(A)
outax = ntuple(d -> d==dims ? newaxis : ax1[d - (d>dims)], N1)
B = similar(_ensure_array(x1), T, outax...)
if dims == 1
_dim_stack!(Val(1), B, x1, xrest)
elseif dims == 2
_dim_stack!(Val(2), B, x1, xrest)
else
_dim_stack!(Val(dims), B, x1, xrest)
end
B
end
function _dim_stack!(::Val{dims}, B::AbstractArray, x1, xrest) where {dims}
before = ntuple(d -> Colon(), dims - 1)
after = ntuple(d -> Colon(), ndims(B) - dims)
i = firstindex(B, dims)
copyto!(view(B, before..., i, after...), x1)
for x in xrest
_stack_size_check(x, _iterator_axes(x1))
i += 1
@inbounds copyto!(view(B, before..., i, after...), x)
end
end
@inline function _stack_size_check(x, ax1::Tuple)
if _iterator_axes(x) != ax1
uax1 = map(UnitRange, ax1)
uaxN = map(UnitRange, axes(x))
throw(DimensionMismatch(
LazyString("stack expects uniform slices, got axes(x) == ", uaxN, " while first had ", uax1)))
end
end
_ensure_array(x::AbstractArray) = x
_ensure_array(x) = 1:0 # passed to similar, makes stack's output an Array
_empty_stack(_...) = throw(ArgumentError("`stack` on an empty collection is not allowed"))
## Reductions and accumulates ##
function isequal(A::AbstractArray, B::AbstractArray)
if A === B return true end
if axes(A) != axes(B)
return false
end
for (a, b) in zip(A, B)
if !isequal(a, b)
return false
end
end
return true
end
function cmp(A::AbstractVector, B::AbstractVector)
for (a, b) in zip(A, B)
if !isequal(a, b)
return isless(a, b) ? -1 : 1
end
end
return cmp(length(A), length(B))
end
"""
isless(A::AbstractVector, B::AbstractVector)
Return `true` when `A` is less than `B` in lexicographic order.
"""
isless(A::AbstractVector, B::AbstractVector) = cmp(A, B) < 0
function (==)(A::AbstractArray, B::AbstractArray)
if axes(A) != axes(B)
return false
end
anymissing = false
for (a, b) in zip(A, B)
eq = (a == b)
if ismissing(eq)
anymissing = true
elseif !eq
return false
end
end
return anymissing ? missing : true
end
# _sub2ind and _ind2sub
# fallbacks
function _sub2ind(A::AbstractArray, I...)
@inline
_sub2ind(axes(A), I...)
end
function _ind2sub(A::AbstractArray, ind)
@inline
_ind2sub(axes(A), ind)
end
# 0-dimensional arrays and indexing with []
_sub2ind(::Tuple{}) = 1
_sub2ind(::DimsInteger) = 1
_sub2ind(::Indices) = 1
_sub2ind(::Tuple{}, I::Integer...) = (@inline; _sub2ind_recurse((), 1, 1, I...))
# Generic cases
_sub2ind(dims::DimsInteger, I::Integer...) = (@inline; _sub2ind_recurse(dims, 1, 1, I...))
_sub2ind(inds::Indices, I::Integer...) = (@inline; _sub2ind_recurse(inds, 1, 1, I...))
# In 1d, there's a question of whether we're doing cartesian indexing
# or linear indexing. Support only the former.
_sub2ind(inds::Indices{1}, I::Integer...) =
throw(ArgumentError("Linear indexing is not defined for one-dimensional arrays"))
_sub2ind(inds::Tuple{OneTo}, I::Integer...) = (@inline; _sub2ind_recurse(inds, 1, 1, I...)) # only OneTo is safe
_sub2ind(inds::Tuple{OneTo}, i::Integer) = i
_sub2ind_recurse(::Any, L, ind) = ind
function _sub2ind_recurse(::Tuple{}, L, ind, i::Integer, I::Integer...)
@inline
_sub2ind_recurse((), L, ind+(i-1)*L, I...)
end
function _sub2ind_recurse(inds, L, ind, i::Integer, I::Integer...)
@inline
r1 = inds[1]
_sub2ind_recurse(tail(inds), nextL(L, r1), ind+offsetin(i, r1)*L, I...)
end
nextL(L, l::Integer) = L*l
nextL(L, r::AbstractUnitRange) = L*length(r)
nextL(L, r::Slice) = L*length(r.indices)
offsetin(i, l::Integer) = i-1
offsetin(i, r::AbstractUnitRange) = i-first(r)
_ind2sub(::Tuple{}, ind::Integer) = (@inline; ind == 1 ? () : throw(BoundsError()))
_ind2sub(dims::DimsInteger, ind::Integer) = (@inline; _ind2sub_recurse(dims, ind-1))
_ind2sub(inds::Indices, ind::Integer) = (@inline; _ind2sub_recurse(inds, ind-1))
_ind2sub(inds::Indices{1}, ind::Integer) =
throw(ArgumentError("Linear indexing is not defined for one-dimensional arrays"))
_ind2sub(inds::Tuple{OneTo}, ind::Integer) = (ind,)
_ind2sub_recurse(::Tuple{}, ind) = (ind+1,)
function _ind2sub_recurse(indslast::NTuple{1}, ind)
@inline
(_lookup(ind, indslast[1]),)
end
function _ind2sub_recurse(inds, ind)
@inline
r1 = inds[1]
indnext, f, l = _div(ind, r1)
(ind-l*indnext+f, _ind2sub_recurse(tail(inds), indnext)...)
end
_lookup(ind, d::Integer) = ind+1
_lookup(ind, r::AbstractUnitRange) = ind+first(r)
_div(ind, d::Integer) = div(ind, d), 1, d
_div(ind, r::AbstractUnitRange) = (d = length(r); (div(ind, d), first(r), d))
# Vectorized forms
function _sub2ind(inds::Indices{1}, I1::AbstractVector{T}, I::AbstractVector{T}...) where T<:Integer
throw(ArgumentError("Linear indexing is not defined for one-dimensional arrays"))
end
_sub2ind(inds::Tuple{OneTo}, I1::AbstractVector{T}, I::AbstractVector{T}...) where {T<:Integer} =
_sub2ind_vecs(inds, I1, I...)
_sub2ind(inds::Union{DimsInteger,Indices}, I1::AbstractVector{T}, I::AbstractVector{T}...) where {T<:Integer} =
_sub2ind_vecs(inds, I1, I...)
function _sub2ind_vecs(inds, I::AbstractVector...)
I1 = I[1]
Iinds = axes1(I1)
for j = 2:length(I)
axes1(I[j]) == Iinds || throw(DimensionMismatch("indices of I[1] ($(Iinds)) does not match indices of I[$j] ($(axes1(I[j])))"))
end
Iout = similar(I1)
_sub2ind!(Iout, inds, Iinds, I)
Iout
end
function _sub2ind!(Iout, inds, Iinds, I)
@noinline
for i in Iinds
# Iout[i] = _sub2ind(inds, map(Ij -> Ij[i], I)...)
Iout[i] = sub2ind_vec(inds, i, I)
end
Iout
end
sub2ind_vec(inds, i, I) = (@inline; _sub2ind(inds, _sub2ind_vec(i, I...)...))
_sub2ind_vec(i, I1, I...) = (@inline; (I1[i], _sub2ind_vec(i, I...)...))
_sub2ind_vec(i) = ()
function _ind2sub(inds::Union{DimsInteger{N},Indices{N}}, ind::AbstractVector{<:Integer}) where N
M = length(ind)
t = ntuple(n->similar(ind),Val(N))
for (i,idx) in pairs(IndexLinear(), ind)
sub = _ind2sub(inds, idx)
for j = 1:N
t[j][i] = sub[j]
end
end
t
end
## iteration utilities ##
"""
foreach(f, c...) -> Nothing
Call function `f` on each element of iterable `c`.
For multiple iterable arguments, `f` is called elementwise, and iteration stops when
any iterator is finished.
`foreach` should be used instead of [`map`](@ref) when the results of `f` are not
needed, for example in `foreach(println, array)`.
# Examples
```jldoctest
julia> tri = 1:3:7; res = Int[];
julia> foreach(x -> push!(res, x^2), tri)
julia> res
3-element Vector{$(Int)}:
1
16
49
julia> foreach((x, y) -> println(x, " with ", y), tri, 'a':'z')
1 with a
4 with b
7 with c
```
"""
foreach(f, itr) = (for x in itr; f(x); end; nothing)
foreach(f, itr, itrs...) = (for z in zip(itr, itrs...); f(z...); end; nothing)
## map over arrays ##
## transform any set of dimensions
## dims specifies which dimensions will be transformed. for example
## dims==1:2 will call f on all slices A[:,:,...]
"""
mapslices(f, A; dims)
Transform the given dimensions of array `A` by applying a function `f` on each slice
of the form `A[..., :, ..., :, ...]`, with a colon at each `d` in `dims`. The results are
concatenated along the remaining dimensions.
For example, if `dims = [1,2]` and `A` is 4-dimensional, then `f` is called on `x = A[:,:,i,j]`
for all `i` and `j`, and `f(x)` becomes `R[:,:,i,j]` in the result `R`.
See also [`eachcol`](@ref) or [`eachslice`](@ref), used with [`map`](@ref) or [`stack`](@ref).
# Examples
```jldoctest
julia> A = reshape(1:30,(2,5,3))
2×5×3 reshape(::UnitRange{$Int}, 2, 5, 3) with eltype $Int:
[:, :, 1] =
1 3 5 7 9
2 4 6 8 10
[:, :, 2] =
11 13 15 17 19
12 14 16 18 20
[:, :, 3] =
21 23 25 27 29
22 24 26 28 30
julia> f(x::Matrix) = fill(x[1,1], 1,4); # returns a 1×4 matrix
julia> B = mapslices(f, A, dims=(1,2))
1×4×3 Array{$Int, 3}:
[:, :, 1] =
1 1 1 1
[:, :, 2] =
11 11 11 11
[:, :, 3] =
21 21 21 21
julia> f2(x::AbstractMatrix) = fill(x[1,1], 1,4);
julia> B == stack(f2, eachslice(A, dims=3))
true
julia> g(x) = x[begin] // x[end-1]; # returns a number
julia> mapslices(g, A, dims=[1,3])
1×5×1 Array{Rational{$Int}, 3}:
[:, :, 1] =
1//21 3//23 1//5 7//27 9//29
julia> map(g, eachslice(A, dims=2))
5-element Vector{Rational{$Int}}:
1//21
3//23
1//5
7//27
9//29
julia> mapslices(sum, A; dims=(1,3)) == sum(A; dims=(1,3))
true
```
Notice that in `eachslice(A; dims=2)`, the specified dimension is the
one *without* a colon in the slice. This is `view(A,:,i,:)`, whereas
`mapslices(f, A; dims=(1,3))` uses `A[:,i,:]`. The function `f` may mutate
values in the slice without affecting `A`.
"""
function mapslices(f, A::AbstractArray; dims)
isempty(dims) && return map(f, A)
for d in dims
d isa Integer || throw(ArgumentError("mapslices: dimension must be an integer, got $d"))
d >= 1 || throw(ArgumentError("mapslices: dimension must be ≥ 1, got $d"))
# Indexing a matrix M[:,1,:] produces a 1-column matrix, but dims=(1,3) here
# would otherwise ignore 3, and slice M[:,i]. Previously this gave error:
# BoundsError: attempt to access 2-element Vector{Any} at index [3]
d > ndims(A) && throw(ArgumentError("mapslices does not accept dimensions > ndims(A) = $(ndims(A)), got $d"))
end
dim_mask = ntuple(d -> d in dims, ndims(A))
# Apply the function to the first slice in order to determine the next steps
idx1 = ntuple(d -> d in dims ? (:) : firstindex(A,d), ndims(A))
Aslice = A[idx1...]
r1 = f(Aslice)
res1 = if r1 isa AbstractArray && ndims(r1) > 0
n = sum(dim_mask)
if ndims(r1) > n && any(ntuple(d -> size(r1,d+n)>1, ndims(r1)-n))
s = size(r1)[1:n]
throw(DimensionMismatch("mapslices cannot assign slice f(x) of size $(size(r1)) into output of size $s"))
end
r1
else
# If the result of f on a single slice is a scalar then we add singleton
# dimensions. When adding the dimensions, we have to respect the
# index type of the input array (e.g. in the case of OffsetArrays)
_res1 = similar(Aslice, typeof(r1), reduced_indices(Aslice, 1:ndims(Aslice)))
_res1[begin] = r1
_res1
end
# Determine result size and allocate. We always pad ndims(res1) out to length(dims):
din = Ref(0)
Rsize = ntuple(ndims(A)) do d
if d in dims
axes(res1, din[] += 1)
else
axes(A,d)
end
end
R = similar(res1, Rsize)
# Determine iteration space. It will be convenient in the loop to mask N-dimensional
# CartesianIndices, with some trivial dimensions:
itershape = ntuple(d -> d in dims ? Base.OneTo(1) : axes(A,d), ndims(A))
indices = Iterators.drop(CartesianIndices(itershape), 1)
# That skips the first element, which we already have:
ridx = ntuple(d -> d in dims ? Slice(axes(R,d)) : firstindex(A,d), ndims(A))
concatenate_setindex!(R, res1, ridx...)
# In some cases, we can re-use the first slice for a dramatic performance
# increase. The slice itself must be mutable and the result cannot contain
# any mutable containers. The following errs on the side of being overly
# strict (#18570 & #21123).
safe_for_reuse = isa(Aslice, StridedArray) &&
(isa(r1, Number) || (isa(r1, AbstractArray) && eltype(r1) <: Number))
_inner_mapslices!(R, indices, f, A, dim_mask, Aslice, safe_for_reuse)
return R
end
@noinline function _inner_mapslices!(R, indices, f, A, dim_mask, Aslice, safe_for_reuse)
must_extend = any(dim_mask .& size(R) .> 1)
if safe_for_reuse
# when f returns an array, R[ridx...] = f(Aslice) line copies elements,
# so we can reuse Aslice
for I in indices
idx = ifelse.(dim_mask, Slice.(axes(A)), Tuple(I))
_unsafe_getindex!(Aslice, A, idx...)
r = f(Aslice)
if r isa AbstractArray || must_extend
ridx = ifelse.(dim_mask, Slice.(axes(R)), Tuple(I))
R[ridx...] = r
else
ridx = ifelse.(dim_mask, first.(axes(R)), Tuple(I))
R[ridx...] = r
end
end
else
# we can't guarantee safety (#18524), so allocate new storage for each slice
for I in indices
idx = ifelse.(dim_mask, Slice.(axes(A)), Tuple(I))
ridx = ifelse.(dim_mask, Slice.(axes(R)), Tuple(I))
concatenate_setindex!(R, f(A[idx...]), ridx...)
end
end
end
concatenate_setindex!(R, v, I...) = (R[I...] .= (v,); R)
concatenate_setindex!(R, X::AbstractArray, I...) = (R[I...] = X)
## 1 argument
function map!(f::F, dest::AbstractArray, A::AbstractArray) where F
for (i,j) in zip(eachindex(dest),eachindex(A))
val = f(@inbounds A[j])
@inbounds dest[i] = val
end
return dest
end
# map on collections
map(f, A::AbstractArray) = collect_similar(A, Generator(f,A))
mapany(f, A::AbstractArray) = map!(f, Vector{Any}(undef, length(A)), A)
mapany(f, itr) = Any[f(x) for x in itr]
"""
map(f, c...) -> collection
Transform collection `c` by applying `f` to each element. For multiple collection arguments,
apply `f` elementwise, and stop when any of them is exhausted.
See also [`map!`](@ref), [`foreach`](@ref), [`mapreduce`](@ref), [`mapslices`](@ref), [`zip`](@ref), [`Iterators.map`](@ref).
# Examples
```jldoctest
julia> map(x -> x * 2, [1, 2, 3])
3-element Vector{Int64}:
2
4
6
julia> map(+, [1, 2, 3], [10, 20, 30, 400, 5000])
3-element Vector{Int64}:
11
22
33
```
"""
map(f, A) = collect(Generator(f,A)) # default to returning an Array for `map` on general iterators
map(f, ::AbstractDict) = error("map is not defined on dictionaries")
map(f, ::AbstractSet) = error("map is not defined on sets")
## 2 argument
function map!(f::F, dest::AbstractArray, A::AbstractArray, B::AbstractArray) where F
for (i, j, k) in zip(eachindex(dest), eachindex(A), eachindex(B))
@inbounds a, b = A[j], B[k]
val = f(a, b)
@inbounds dest[i] = val
end
return dest
end
## N argument
@inline ith_all(i, ::Tuple{}) = ()
function ith_all(i, as)
@_propagate_inbounds_meta
return (as[1][i], ith_all(i, tail(as))...)
end
function map_n!(f::F, dest::AbstractArray, As) where F
idxs1 = LinearIndices(As[1])
@boundscheck LinearIndices(dest) == idxs1 && all(x -> LinearIndices(x) == idxs1, As)
for i = idxs1
@inbounds I = ith_all(i, As)
val = f(I...)
@inbounds dest[i] = val
end
return dest
end
"""
map!(function, destination, collection...)
Like [`map`](@ref), but stores the result in `destination` rather than a new
collection. `destination` must be at least as large as the smallest collection.
$(_DOCS_ALIASING_WARNING)
See also: [`map`](@ref), [`foreach`](@ref), [`zip`](@ref), [`copyto!`](@ref).
# Examples
```jldoctest
julia> a = zeros(3);
julia> map!(x -> x * 2, a, [1, 2, 3]);
julia> a
3-element Vector{Float64}:
2.0
4.0
6.0
julia> map!(+, zeros(Int, 5), 100:999, 1:3)
5-element Vector{$(Int)}:
101
103
105
0
0
```
"""
function map!(f::F, dest::AbstractArray, As::AbstractArray...) where {F}
isempty(As) && throw(ArgumentError(
"""map! requires at least one "source" argument"""))
map_n!(f, dest, As)
end
"""
map(f, A::AbstractArray...) -> N-array
When acting on multi-dimensional arrays of the same [`ndims`](@ref),
they must all have the same [`axes`](@ref), and the answer will too.
See also [`broadcast`](@ref), which allows mismatched sizes.
# Examples
```
julia> map(//, [1 2; 3 4], [4 3; 2 1])
2×2 Matrix{Rational{$Int}}:
1//4 2//3
3//2 4//1
julia> map(+, [1 2; 3 4], zeros(2,1))
ERROR: DimensionMismatch
julia> map(+, [1 2; 3 4], [1,10,100,1000], zeros(3,1)) # iterates until 3rd is exhausted
3-element Vector{Float64}:
2.0
13.0
102.0
```
"""
map(f, it, iters...) = collect(Generator(f, it, iters...))
# multi-item push!, pushfirst! (built on top of type-specific 1-item version)
# (note: must not cause a dispatch loop when 1-item case is not defined)
push!(A, a, b) = push!(push!(A, a), b)
push!(A, a, b, c...) = push!(push!(A, a, b), c...)
pushfirst!(A, a, b) = pushfirst!(pushfirst!(A, b), a)
pushfirst!(A, a, b, c...) = pushfirst!(pushfirst!(A, c...), a, b)
## hashing AbstractArray ##
const hash_abstractarray_seed = UInt === UInt64 ? 0x7e2d6fb6448beb77 : 0xd4514ce5
function hash(A::AbstractArray, h::UInt)
h += hash_abstractarray_seed
# Axes are themselves AbstractArrays, so hashing them directly would stack overflow
# Instead hash the tuple of firsts and lasts along each dimension
h = hash(map(first, axes(A)), h)
h = hash(map(last, axes(A)), h)
# For short arrays, it's not worth doing anything complicated
if length(A) < 8192
for x in A
h = hash(x, h)
end
return h
end
# Goal: Hash approximately log(N) entries with a higher density of hashed elements
# weighted towards the end and special consideration for repeated values. Colliding
# hashes will often subsequently be compared by equality -- and equality between arrays
# works elementwise forwards and is short-circuiting. This means that a collision
# between arrays that differ by elements at the beginning is cheaper than one where the
# difference is towards the end. Furthermore, choosing `log(N)` arbitrary entries from a
# sparse array will likely only choose the same element repeatedly (zero in this case).
# To achieve this, we work backwards, starting by hashing the last element of the
# array. After hashing each element, we skip `fibskip` elements, where `fibskip`
# is pulled from the Fibonacci sequence -- Fibonacci was chosen as a simple
# ~O(log(N)) algorithm that ensures we don't hit a common divisor of a dimension
# and only end up hashing one slice of the array (as might happen with powers of
# two). Finally, we find the next distinct value from the one we just hashed.
# This is a little tricky since skipping an integer number of values inherently works
# with linear indices, but `findprev` uses `keys`. Hoist out the conversion "maps":
ks = keys(A)
key_to_linear = LinearIndices(ks) # Index into this map to compute the linear index
linear_to_key = vec(ks) # And vice-versa
# Start at the last index
keyidx = last(ks)
linidx = key_to_linear[keyidx]
fibskip = prevfibskip = oneunit(linidx)
first_linear = first(LinearIndices(linear_to_key))
n = 0
while true
n += 1
# Hash the element
elt = A[keyidx]
h = hash(keyidx=>elt, h)
# Skip backwards a Fibonacci number of indices -- this is a linear index operation
linidx = key_to_linear[keyidx]
linidx < fibskip + first_linear && break
linidx -= fibskip
keyidx = linear_to_key[linidx]
# Only increase the Fibonacci skip once every N iterations. This was chosen
# to be big enough that all elements of small arrays get hashed while
# obscenely large arrays are still tractable. With a choice of N=4096, an
# entirely-distinct 8000-element array will have ~75% of its elements hashed,
# with every other element hashed in the first half of the array. At the same
# time, hashing a `typemax(Int64)`-length Float64 range takes about a second.
if rem(n, 4096) == 0
fibskip, prevfibskip = fibskip + prevfibskip, fibskip
end
# Find a key index with a value distinct from `elt` -- might be `keyidx` itself
keyidx = findprev(!isequal(elt), A, keyidx)
keyidx === nothing && break
end
return h
end
# The semantics of `collect` are weird. Better to write our own
function rest(a::AbstractArray{T}, state...) where {T}
v = Vector{T}(undef, 0)
# assume only very few items are taken from the front
sizehint!(v, length(a))
return foldl(push!, Iterators.rest(a, state...), init=v)
end
## keepat! ##
# NOTE: since these use `@inbounds`, they are actually only intended for Vector and BitVector
function _keepat!(a::AbstractVector, inds)
local prev
i = firstindex(a)
for k in inds
if @isdefined(prev)
prev < k || throw(ArgumentError("indices must be unique and sorted"))
end
ak = a[k] # must happen even when i==k for bounds checking
if i != k
@inbounds a[i] = ak # k > i, so a[i] is inbounds
end
prev = k
i = nextind(a, i)
end
deleteat!(a, i:lastindex(a))
return a
end
function _keepat!(a::AbstractVector, m::AbstractVector{Bool})
length(m) == length(a) || throw(BoundsError(a, m))
j = firstindex(a)
for i in eachindex(a, m)
@inbounds begin
if m[i]
i == j || (a[j] = a[i])
j = nextind(a, j)
end
end
end
deleteat!(a, j:lastindex(a))
end
## 1-d circshift ##
function circshift!(a::AbstractVector, shift::Integer)
n = length(a)
n == 0 && return
shift = mod(shift, n)
shift == 0 && return
l = lastindex(a)
reverse!(a, firstindex(a), l-shift)
reverse!(a, l-shift+1, lastindex(a))
reverse!(a)
return a
end
