bitarray.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
## BitArray
# notes: bits are stored in contiguous chunks
# unused bits must always be set to 0
"""
BitArray{N} <: AbstractArray{Bool, N}
Space-efficient `N`-dimensional boolean array, using just one bit for each boolean value.
`BitArray`s pack up to 64 values into every 8 bytes, resulting in an 8x space efficiency
over `Array{Bool, N}` and allowing some operations to work on 64 values at once.
By default, Julia returns `BitArrays` from [broadcasting](@ref Broadcasting) operations
that generate boolean elements (including dotted-comparisons like `.==`) as well as from
the functions [`trues`](@ref) and [`falses`](@ref).
!!! note
Due to its packed storage format, concurrent access to the elements of a `BitArray`
where at least one of them is a write is not thread-safe.
"""
mutable struct BitArray{N} <: AbstractArray{Bool, N}
chunks::Vector{UInt64}
len::Int
dims::NTuple{N,Int}
function BitArray{N}(::UndefInitializer, dims::Vararg{Int,N}) where N
n = 1
i = 1
for d in dims
d >= 0 || throw(ArgumentError("dimension size must be ≥ 0, got $d for dimension $i"))
n *= d
i += 1
end
nc = num_bit_chunks(n)
chunks = Vector{UInt64}(undef, nc)
nc > 0 && (chunks[end] = UInt64(0))
b = new(chunks, n)
N != 1 && (b.dims = dims)
return b
end
end
# note: the docs for the two signatures are unified, but only
# the first one is recognized by the help system; it would be nice
# to fix this.
"""
BitArray(undef, dims::Integer...)
BitArray{N}(undef, dims::NTuple{N,Int})
Construct an undef [`BitArray`](@ref) with the given dimensions.
Behaves identically to the [`Array`](@ref) constructor. See [`undef`](@ref).
# Examples
```julia-repl
julia> BitArray(undef, 2, 2)
2×2 BitMatrix:
0 0
0 0
julia> BitArray(undef, (3, 1))
3×1 BitMatrix:
0
0
0
```
"""
BitArray(::UndefInitializer, dims::Integer...) = BitArray(undef, map(Int,dims))
BitArray{N}(::UndefInitializer, dims::Integer...) where {N} = BitArray{N}(undef, map(Int,dims))::BitArray{N}
BitArray(::UndefInitializer, dims::NTuple{N,Integer}) where {N} = BitArray{N}(undef, map(Int, dims)...)
BitArray{N}(::UndefInitializer, dims::NTuple{N,Integer}) where {N} = BitArray{N}(undef, map(Int, dims)...)
const BitVector = BitArray{1}
const BitMatrix = BitArray{2}
BitVector() = BitVector(undef, 0)
"""
BitVector(nt::Tuple{Vararg{Bool}})
Construct a `BitVector` from a tuple of `Bool`.
# Examples
```julia-repl
julia> nt = (true, false, true, false)
(true, false, true, false)
julia> BitVector(nt)
4-element BitVector:
1
0
1
0
```
"""
function BitVector(nt::Tuple{Vararg{Bool}})
bv = BitVector(undef, length(nt))
bv .= nt
end
## utility functions ##
length(B::BitArray) = B.len
size(B::BitVector) = (B.len,)
size(B::BitArray) = B.dims
@inline function size(B::BitVector, d::Integer)
d < 1 && throw_boundserror(size(B), d)
ifelse(d == 1, B.len, 1)
end
isassigned(B::BitArray, i::Int) = 1 <= i <= length(B)
IndexStyle(::Type{<:BitArray}) = IndexLinear()
## aux functions ##
const _msk64 = ~UInt64(0)
@inline _div64(l) = l >> 6
@inline _mod64(l) = l & 63
@inline _blsr(x)= x & (x-1) #zeros the last set bit. Has native instruction on many archs. needed in multidimensional.jl
@inline _msk_end(l::Int) = _msk64 >>> _mod64(-l)
@inline _msk_end(B::BitArray) = _msk_end(length(B))
num_bit_chunks(n::Int) = _div64(n+63)
@inline get_chunks_id(i::Int) = _div64(i-1)+1, _mod64(i-1)
function glue_src_bitchunks(src::Vector{UInt64}, k::Int, ks1::Int, msk_s0::UInt64, ls0::Int)
@inbounds begin
chunk = ((src[k] & msk_s0) >>> ls0)
if ks1 > k && ls0 > 0
chunk_n = (src[k + 1] & ~msk_s0)
chunk |= (chunk_n << (64 - ls0))
end
end
return chunk
end
function copy_chunks!(dest::Vector{UInt64}, pos_d::Int, src::Vector{UInt64}, pos_s::Int, numbits::Int)
numbits == 0 && return
if dest === src && pos_d > pos_s
return copy_chunks_rtol!(dest, pos_d, pos_s, numbits)
end
kd0, ld0 = get_chunks_id(pos_d)
kd1, ld1 = get_chunks_id(pos_d + numbits - 1)
ks0, ls0 = get_chunks_id(pos_s)
ks1, ls1 = get_chunks_id(pos_s + numbits - 1)
delta_kd = kd1 - kd0
delta_ks = ks1 - ks0
u = _msk64
if delta_kd == 0
msk_d0 = ~(u << ld0) | (u << (ld1+1))
else
msk_d0 = ~(u << ld0)
msk_d1 = (u << (ld1+1))
end
if delta_ks == 0
msk_s0 = (u << ls0) & ~(u << (ls1+1))
else
msk_s0 = (u << ls0)
end
chunk_s0 = glue_src_bitchunks(src, ks0, ks1, msk_s0, ls0)
dest[kd0] = (dest[kd0] & msk_d0) | ((chunk_s0 << ld0) & ~msk_d0)
delta_kd == 0 && return
for i = 1 : kd1 - kd0 - 1
chunk_s1 = glue_src_bitchunks(src, ks0 + i, ks1, msk_s0, ls0)
chunk_s = (chunk_s0 >>> (64 - ld0)) | (chunk_s1 << ld0)
dest[kd0 + i] = chunk_s
chunk_s0 = chunk_s1
end
if ks1 >= ks0 + delta_kd
chunk_s1 = glue_src_bitchunks(src, ks0 + delta_kd, ks1, msk_s0, ls0)
else
chunk_s1 = UInt64(0)
end
chunk_s = (chunk_s0 >>> (64 - ld0)) | (chunk_s1 << ld0)
dest[kd1] = (dest[kd1] & msk_d1) | (chunk_s & ~msk_d1)
return
end
function copy_chunks_rtol!(chunks::Vector{UInt64}, pos_d::Int, pos_s::Int, numbits::Int)
pos_d == pos_s && return
pos_d < pos_s && return copy_chunks!(chunks, pos_d, chunks, pos_s, numbits)
left = numbits
s = min(left, 64)
b = left - s
ps = pos_s + b
pd = pos_d + b
u = _msk64
while left > 0
kd0, ld0 = get_chunks_id(pd)
kd1, ld1 = get_chunks_id(pd + s - 1)
ks0, ls0 = get_chunks_id(ps)
ks1, ls1 = get_chunks_id(ps + s - 1)
delta_kd = kd1 - kd0
delta_ks = ks1 - ks0
if delta_kd == 0
msk_d0 = ~(u << ld0) | (u << (ld1+1))
else
msk_d0 = ~(u << ld0)
msk_d1 = (u << (ld1+1))
end
if delta_ks == 0
msk_s0 = (u << ls0) & ~(u << (ls1+1))
else
msk_s0 = (u << ls0)
end
chunk_s0 = glue_src_bitchunks(chunks, ks0, ks1, msk_s0, ls0) & ~(u << s)
chunks[kd0] = (chunks[kd0] & msk_d0) | ((chunk_s0 << ld0) & ~msk_d0)
if delta_kd != 0
chunk_s = (chunk_s0 >>> (64 - ld0))
chunks[kd1] = (chunks[kd1] & msk_d1) | (chunk_s & ~msk_d1)
end
left -= s
s = min(left, 64)
b = left - s
ps = pos_s + b
pd = pos_d + b
end
end
function fill_chunks!(Bc::Array{UInt64}, x::Bool, pos::Int, numbits::Int)
numbits <= 0 && return
k0, l0 = get_chunks_id(pos)
k1, l1 = get_chunks_id(pos+numbits-1)
u = _msk64
if k1 == k0
msk0 = (u << l0) & ~(u << (l1+1))
else
msk0 = (u << l0)
msk1 = ~(u << (l1+1))
end
@inbounds if x
Bc[k0] |= msk0
for k = k0+1:k1-1
Bc[k] = u
end
k1 > k0 && (Bc[k1] |= msk1)
else
Bc[k0] &= ~msk0
for k = k0+1:k1-1
Bc[k] = 0
end
k1 > k0 && (Bc[k1] &= ~msk1)
end
end
copy_to_bitarray_chunks!(dest::Vector{UInt64}, pos_d::Int, src::BitArray, pos_s::Int, numbits::Int) =
copy_chunks!(dest, pos_d, src.chunks, pos_s, numbits)
# pack 8 Bools encoded as one contiguous UIn64 into a single byte, e.g.:
# 0000001:0000001:00000000:00000000:00000001:00000000:00000000:00000001 → 11001001 → 0xc9
function pack8bools(z::UInt64)
z |= z >>> 7
z |= z >>> 14
z |= z >>> 28
z &= 0xFF
return z
end
function copy_to_bitarray_chunks!(Bc::Vector{UInt64}, pos_d::Int, C::Array{Bool}, pos_s::Int, numbits::Int)
kd0, ld0 = get_chunks_id(pos_d)
kd1, ld1 = get_chunks_id(pos_d + numbits - 1)
delta_kd = kd1 - kd0
u = _msk64
if delta_kd == 0
msk_d0 = msk_d1 = ~(u << ld0) | (u << (ld1+1))
lt0 = ld1
else
msk_d0 = ~(u << ld0)
msk_d1 = (u << (ld1+1))
lt0 = 63
end
bind = kd0
ind = pos_s
@inbounds if ld0 > 0
c = UInt64(0)
for j = ld0:lt0
c |= (UInt64(C[ind]) << j)
ind += 1
end
Bc[kd0] = (Bc[kd0] & msk_d0) | (c & ~msk_d0)
bind += 1
end
nc = _div64(numbits - ind + pos_s)
nc8 = (nc >>> 3) << 3
if nc8 > 0
ind8 = 1
P8 = Ptr{UInt64}(pointer(C, ind)) # unaligned i64 pointer
@inbounds for i = 1:nc8
c = UInt64(0)
for j = 0:7
# unaligned load
c |= (pack8bools(unsafe_load(P8, ind8)) << (j<<3))
ind8 += 1
end
Bc[bind] = c
bind += 1
end
ind += (ind8-1) << 3
end
@inbounds for i = (nc8+1):nc
c = UInt64(0)
for j = 0:63
c |= (UInt64(C[ind]) << j)
ind += 1
end
Bc[bind] = c
bind += 1
end
@inbounds if bind ≤ kd1
@assert bind == kd1
c = UInt64(0)
for j = 0:ld1
c |= (UInt64(C[ind]) << j)
ind += 1
end
Bc[kd1] = (Bc[kd1] & msk_d1) | (c & ~msk_d1)
end
end
## More definitions in multidimensional.jl
# auxiliary definitions used when filling a BitArray via a Vector{Bool} cache
# (e.g. when constructing from an iterable, or in broadcast!)
const bitcache_chunks = 64 # this can be changed
const bitcache_size = 64 * bitcache_chunks # do not change this
dumpbitcache(Bc::Vector{UInt64}, bind::Int, C::Vector{Bool}) =
copy_to_bitarray_chunks!(Bc, ((bind - 1) << 6) + 1, C, 1, min(bitcache_size, (length(Bc)-bind+1) << 6))
## custom iterator ##
function iterate(B::BitArray, i::Int=0)
i >= length(B) && return nothing
(B.chunks[_div64(i)+1] & (UInt64(1)<<_mod64(i)) != 0, i+1)
end
## similar, fill!, copy! etc ##
similar(B::BitArray) = BitArray(undef, size(B))
similar(B::BitArray, dims::Int...) = BitArray(undef, dims)
similar(B::BitArray, dims::Dims) = BitArray(undef, dims...)
similar(B::BitArray, T::Type{Bool}, dims::Dims) = BitArray(undef, dims)
# changing type to a non-Bool returns an Array
# (this triggers conversions like float(bitvector) etc.)
similar(B::BitArray, T::Type, dims::Dims) = Array{T}(undef, dims)
function fill!(B::BitArray, x)
y = convert(Bool, x)
isempty(B) && return B
Bc = B.chunks
if !y
fill!(Bc, 0)
else
fill!(Bc, _msk64)
Bc[end] &= _msk_end(B)
end
return B
end
"""
falses(dims)
Create a `BitArray` with all values set to `false`.
# Examples
```jldoctest
julia> falses(2,3)
2×3 BitMatrix:
0 0 0
0 0 0
```
"""
falses(dims::DimOrInd...) = falses(dims)
falses(dims::NTuple{N, Union{Integer, OneTo}}) where {N} = falses(map(to_dim, dims))
falses(dims::NTuple{N, Integer}) where {N} = fill!(BitArray(undef, dims), false)
falses(dims::Tuple{}) = fill!(BitArray(undef, dims), false)
falses(dims::NTuple{N, DimOrInd}) where {N} = fill!(similar(BitArray, dims), false)
"""
trues(dims)
Create a `BitArray` with all values set to `true`.
# Examples
```jldoctest
julia> trues(2,3)
2×3 BitMatrix:
1 1 1
1 1 1
```
"""
trues(dims::DimOrInd...) = trues(dims)
trues(dims::NTuple{N, Union{Integer, OneTo}}) where {N} = trues(map(to_dim, dims))
trues(dims::NTuple{N, Integer}) where {N} = fill!(BitArray(undef, dims), true)
trues(dims::Tuple{}) = fill!(BitArray(undef, dims), true)
trues(dims::NTuple{N, DimOrInd}) where {N} = fill!(similar(BitArray, dims), true)
function one(x::BitMatrix)
m, n = size(x)
m == n || throw(DimensionMismatch("multiplicative identity defined only for square matrices"))
a = falses(n, n)
for i = 1:n
a[i,i] = true
end
return a
end
function copyto!(dest::BitArray, src::BitArray)
length(src) > length(dest) && throw(BoundsError(dest, length(dest)+1))
destc = dest.chunks; srcc = src.chunks
nc = min(length(destc), length(srcc))
nc == 0 && return dest
@inbounds begin
for i = 1 : nc - 1
destc[i] = srcc[i]
end
if length(src) == length(dest)
destc[nc] = srcc[nc]
else
msk_s = _msk_end(src)
msk_d = ~msk_s
destc[nc] = (msk_d & destc[nc]) | (msk_s & srcc[nc])
end
end
return dest
end
function unsafe_copyto!(dest::BitArray, doffs::Integer, src::Union{BitArray,Array}, soffs::Integer, n::Integer)
copy_to_bitarray_chunks!(dest.chunks, Int(doffs), src, Int(soffs), Int(n))
return dest
end
copyto!(dest::BitArray, doffs::Integer, src::Union{BitArray,Array}, soffs::Integer, n::Integer) =
_copyto_int!(dest, Int(doffs), src, Int(soffs), Int(n))
function _copyto_int!(dest::BitArray, doffs::Int, src::Union{BitArray,Array}, soffs::Int, n::Int)
n == 0 && return dest
n < 0 && throw(ArgumentError("Number of elements to copy must be non-negative."))
soffs < 1 && throw(BoundsError(src, soffs))
doffs < 1 && throw(BoundsError(dest, doffs))
soffs+n-1 > length(src) && throw(BoundsError(src, length(src)+1))
doffs+n-1 > length(dest) && throw(BoundsError(dest, length(dest)+1))
return unsafe_copyto!(dest, doffs, src, soffs, n)
end
function copyto!(dest::BitArray, src::Array)
length(src) > length(dest) && throw(BoundsError(dest, length(dest)+1))
length(src) == 0 && return dest
return unsafe_copyto!(dest, 1, src, 1, length(src))
end
function reshape(B::BitArray{N}, dims::NTuple{N,Int}) where N
return dims == size(B) ? B : _bitreshape(B, dims)
end
reshape(B::BitArray, dims::Tuple{Vararg{Int}}) = _bitreshape(B, dims)
function _bitreshape(B::BitArray, dims::NTuple{N,Int}) where N
prod(dims) == length(B) ||
throw(DimensionMismatch("new dimensions $(dims) must be consistent with array length $(length(B))"))
Br = BitArray{N}(undef, ntuple(i->0,Val(N))...)
Br.chunks = B.chunks
Br.len = prod(dims)
N != 1 && (Br.dims = dims)
return Br
end
## Constructors ##
function Array{T,N}(B::BitArray{N}) where {T,N}
A = Array{T,N}(undef, size(B))
Bc = B.chunks
@inbounds for i = 1:length(A)
A[i] = unsafe_bitgetindex(Bc, i)
end
return A
end
BitArray(A::AbstractArray{<:Any,N}) where {N} = BitArray{N}(A)
function BitArray{N}(A::AbstractArray{T,N}) where N where T
B = BitArray(undef, convert(Dims{N}, size(A)::Dims{N}))
_checkaxs(axes(B), axes(A))
_copyto_bitarray!(B, A)
return B::BitArray{N}
end
function _copyto_bitarray!(B::BitArray, A::AbstractArray)
l = length(A)
l == 0 && return B
l > length(B) && throw(BoundsError(B, length(B)+1))
Bc = B.chunks
nc = num_bit_chunks(l)
Ai = first(eachindex(A))
@inbounds begin
for i = 1:nc-1
c = UInt64(0)
for j = 0:63
c |= (UInt64(convert(Bool, A[Ai])::Bool) << j)
Ai = nextind(A, Ai)
end
Bc[i] = c
end
c = UInt64(0)
tail = _mod64(l - 1) + 1
for j = 0:tail-1
c |= (UInt64(convert(Bool, A[Ai])::Bool) << j)
Ai = nextind(A, Ai)
end
msk = _msk_end(tail)
Bc[nc] = (c & msk) | (Bc[nc] & ~msk)
end
return B
end
reinterpret(::Type{Bool}, B::BitArray, dims::NTuple{N,Int}) where {N} = reinterpret(B, dims)
reinterpret(B::BitArray, dims::NTuple{N,Int}) where {N} = reshape(B, dims)
if nameof(@__MODULE__) === :Base # avoid method overwrite
(::Type{T})(x::T) where {T<:BitArray} = copy(x)::T
BitArray(x::BitArray) = copy(x)
end
"""
BitArray(itr)
Construct a [`BitArray`](@ref) generated by the given iterable object.
The shape is inferred from the `itr` object.
# Examples
```jldoctest
julia> BitArray([1 0; 0 1])
2×2 BitMatrix:
1 0
0 1
julia> BitArray(x+y == 3 for x = 1:2, y = 1:3)
2×3 BitMatrix:
0 1 0
1 0 0
julia> BitArray(x+y == 3 for x = 1:2 for y = 1:3)
6-element BitVector:
0
1
0
1
0
0
```
"""
BitArray(itr) = gen_bitarray(IteratorSize(itr), itr)
BitArray{N}(itr) where N = gen_bitarrayN(BitArray{N}, IteratorSize(itr), itr)
convert(::Type{T}, a::AbstractArray) where {T<:BitArray} = a isa T ? a : T(a)::T
# generic constructor from an iterable without compile-time info
# (we pass start(itr) explicitly to avoid a type-instability with filters)
gen_bitarray(isz::IteratorSize, itr) = gen_bitarray_from_itr(itr)
# generic iterable with known shape
function gen_bitarray(::HasShape, itr)
B = BitArray(undef, size(itr))
for (I,x) in zip(CartesianIndices(axes(itr)), itr)
B[I] = x
end
return B
end
# generator with known shape or length
function gen_bitarray(::HasShape, itr::Generator)
B = BitArray(undef, size(itr))
return fill_bitarray_from_itr!(B, itr)
end
function gen_bitarray(::HasLength, itr)
b = BitVector(undef, length(itr))
return fill_bitarray_from_itr!(b, itr)
end
gen_bitarray(::IsInfinite, itr) = throw(ArgumentError("infinite-size iterable used in BitArray constructor"))
gen_bitarrayN(::Type{BitVector}, itsz, itr) = gen_bitarray(itsz, itr)
gen_bitarrayN(::Type{BitVector}, itsz::HasShape{1}, itr) = gen_bitarray(itsz, itr)
gen_bitarrayN(::Type{BitArray{N}}, itsz::HasShape{N}, itr) where N = gen_bitarray(itsz, itr)
# The first of these is just for ambiguity resolution
gen_bitarrayN(::Type{BitVector}, itsz::HasShape{N}, itr) where N = throw(DimensionMismatch("cannot create a BitVector from a $N-dimensional iterator"))
gen_bitarrayN(@nospecialize(T::Type), itsz::HasShape{N}, itr) where N = throw(DimensionMismatch("cannot create a $T from a $N-dimensional iterator"))
gen_bitarrayN(@nospecialize(T::Type), itsz, itr) = throw(DimensionMismatch("cannot create a $T from a generic iterator"))
# The aux functions gen_bitarray_from_itr and fill_bitarray_from_itr! both
# use a Vector{Bool} cache for performance reasons
function gen_bitarray_from_itr(itr)
B = empty!(BitVector(undef, bitcache_size))
C = Vector{Bool}(undef, bitcache_size)
Bc = B.chunks
ind = 1
cind = 1
y = iterate(itr)
while y !== nothing
x, st = y
@inbounds C[ind] = x
ind += 1
if ind > bitcache_size
resize!(B, length(B) + bitcache_size)
dumpbitcache(Bc, cind, C)
cind += bitcache_chunks
ind = 1
end
y = iterate(itr, st)
end
if ind > 1
@inbounds C[ind:bitcache_size] .= false
resize!(B, length(B) + ind - 1)
dumpbitcache(Bc, cind, C)
end
return B
end
function fill_bitarray_from_itr!(B::BitArray, itr)
n = length(B)
C = Vector{Bool}(undef, bitcache_size)
Bc = B.chunks
ind = 1
cind = 1
y = iterate(itr)
while y !== nothing
x, st = y
@inbounds C[ind] = x
ind += 1
if ind > bitcache_size
dumpbitcache(Bc, cind, C)
cind += bitcache_chunks
ind = 1
end
y = iterate(itr, st)
end
if ind > 1
@inbounds C[ind:bitcache_size] .= false
dumpbitcache(Bc, cind, C)
end
return B
end
## Indexing: getindex ##
@inline function unsafe_bitgetindex(Bc::Vector{UInt64}, i::Int)
i1, i2 = get_chunks_id(i)
u = UInt64(1) << i2
@inbounds r = (Bc[i1] & u) != 0
return r
end
@inline function getindex(B::BitArray, i::Int)
@boundscheck checkbounds(B, i)
unsafe_bitgetindex(B.chunks, i)
end
## Indexing: setindex! ##
@inline function unsafe_bitsetindex!(Bc::Array{UInt64}, x::Bool, i::Int)
i1, i2 = get_chunks_id(i)
_unsafe_bitsetindex!(Bc, x, i1, i2)
end
@inline function _unsafe_bitsetindex!(Bc::Array{UInt64}, x::Bool, i1::Int, i2::Int)
u = UInt64(1) << i2
@inbounds begin
c = Bc[i1]
Bc[i1] = ifelse(x, c | u, c & ~u)
end
end
@inline function setindex!(B::BitArray, x, i::Int)
@boundscheck checkbounds(B, i)
unsafe_bitsetindex!(B.chunks, convert(Bool, x), i)
return B
end
indexoffset(i) = first(i)-1
indexoffset(::Colon) = 0
@propagate_inbounds function setindex!(B::BitArray, X::AbstractArray, J0::Union{Colon,AbstractUnitRange{Int}})
_setindex!(IndexStyle(B), B, X, to_indices(B, (J0,))[1])
end
# Assigning an array of bools is more complicated, but we can still do some
# work on chunks by combining X and I 64 bits at a time to improve perf by ~40%
@inline function setindex!(B::BitArray, X::AbstractArray, I::BitArray)
@boundscheck checkbounds(B, I)
_unsafe_setindex!(B, X, I)
end
function _unsafe_setindex!(B::BitArray, X::AbstractArray, I::BitArray)
Bc = B.chunks
Ic = I.chunks
length(Bc) == length(Ic) || throw_boundserror(B, I)
lc = length(Bc)
lx = length(X)
last_chunk_len = _mod64(length(B)-1)+1
Xi = first(eachindex(X))
lastXi = last(eachindex(X))
for i = 1:lc
@inbounds Imsk = Ic[i]
@inbounds C = Bc[i]
u = UInt64(1)
for j = 1:(i < lc ? 64 : last_chunk_len)
if Imsk & u != 0
Xi > lastXi && throw_setindex_mismatch(X, count(I))
@inbounds x = convert(Bool, X[Xi])
C = ifelse(x, C | u, C & ~u)
Xi = nextind(X, Xi)
end
u <<= 1
end
@inbounds Bc[i] = C
end
if Xi != nextind(X, lastXi)
throw_setindex_mismatch(X, count(I))
end
return B
end
## Dequeue functionality ##
function push!(B::BitVector, item)
# convert first so we don't grow the bitarray if the assignment won't work
item = convert(Bool, item)
Bc = B.chunks
l = _mod64(length(B))
if l == 0
_growend!(Bc, 1)
Bc[end] = UInt64(0)
end
B.len += 1
if item
B[end] = true
end
return B
end
function append!(B::BitVector, items::BitVector)
n0 = length(B)
n1 = length(items)
n1 == 0 && return B
Bc = B.chunks
k0 = length(Bc)
k1 = num_bit_chunks(n0 + n1)
if k1 > k0
_growend!(Bc, k1 - k0)
Bc[end] = UInt64(0)
end
B.len += n1
copy_chunks!(Bc, n0+1, items.chunks, 1, n1)
return B
end
append!(B::BitVector, items) = append!(B, BitVector(items))
append!(A::Vector{Bool}, items::BitVector) = append!(A, Array(items))
function prepend!(B::BitVector, items::BitVector)
n0 = length(B)
n1 = length(items)
n1 == 0 && return B
Bc = B.chunks
k0 = length(Bc)
k1 = num_bit_chunks(n0 + n1)
if k1 > k0
_growend!(Bc, k1 - k0)
Bc[end] = UInt64(0)
end
B.len += n1
copy_chunks!(Bc, 1 + n1, Bc, 1, n0)
copy_chunks!(Bc, 1, items.chunks, 1, n1)
return B
end
prepend!(B::BitVector, items) = prepend!(B, BitArray(items))
prepend!(A::Vector{Bool}, items::BitVector) = prepend!(A, Array(items))
function sizehint!(B::BitVector, sz::Integer)
sizehint!(B.chunks, num_bit_chunks(sz))
return B
end
resize!(B::BitVector, n::Integer) = _resize_int!(B, Int(n))
function _resize_int!(B::BitVector, n::Int)
n0 = length(B)
n == n0 && return B
n >= 0 || throw(BoundsError(B, n))
if n < n0
deleteat!(B, n+1:n0)
return B
end
Bc = B.chunks
k0 = length(Bc)
k1 = num_bit_chunks(n)
if k1 > k0
_growend!(Bc, k1 - k0)
Bc[end] = UInt64(0)
end
B.len = n
return B
end
function pop!(B::BitVector)
isempty(B) && throw(ArgumentError("argument must not be empty"))
item = B[end]
B[end] = false
l = _mod64(length(B))
l == 1 && _deleteend!(B.chunks, 1)
B.len -= 1
return item
end
function pushfirst!(B::BitVector, item)
item = convert(Bool, item)
Bc = B.chunks
l = _mod64(length(B))
if l == 0
_growend!(Bc, 1)
Bc[end] = UInt64(0)
end
B.len += 1
if B.len == 1
Bc[1] = item
return B
end
for i = length(Bc) : -1 : 2
Bc[i] = (Bc[i] << 1) | (Bc[i-1] >>> 63)
end
Bc[1] = UInt64(item) | (Bc[1] << 1)
return B
end
function popfirst!(B::BitVector)
isempty(B) && throw(ArgumentError("argument must not be empty"))
@inbounds begin
item = B[1]
Bc = B.chunks
for i = 1 : length(Bc) - 1
Bc[i] = (Bc[i] >>> 1) | (Bc[i+1] << 63)
end
l = _mod64(length(B))
if l == 1
_deleteend!(Bc, 1)
else
Bc[end] >>>= 1
end
B.len -= 1
end
return item
end
insert!(B::BitVector, i::Integer, item) = _insert_int!(B, Int(i), item)
function _insert_int!(B::BitVector, i::Int, item)
i = Int(i)
n = length(B)
1 <= i <= n+1 || throw(BoundsError(B, i))
item = convert(Bool, item)
Bc = B.chunks
k, j = get_chunks_id(i)
l = _mod64(length(B))
if l == 0
_growend!(Bc, 1)
Bc[end] = UInt64(0)
end
B.len += 1
for t = length(Bc) : -1 : k + 1
Bc[t] = (Bc[t] << 1) | (Bc[t - 1] >>> 63)
end
msk_aft = (_msk64 << j)
msk_bef = ~msk_aft
Bc[k] = (msk_bef & Bc[k]) | ((msk_aft & Bc[k]) << 1)
B[i] = item
B
end
function _deleteat!(B::BitVector, i::Int)
k, j = get_chunks_id(i)
msk_bef = _msk64 >>> (63 - j)
msk_aft = ~msk_bef
msk_bef >>>= 1
Bc = B.chunks
@inbounds begin
Bc[k] = (msk_bef & Bc[k]) | ((msk_aft & Bc[k]) >> 1)
if length(Bc) > k
Bc[k] |= (Bc[k + 1] << 63)
end
for t = k + 1 : length(Bc) - 1
Bc[t] = (Bc[t] >>> 1) | (Bc[t + 1] << 63)
end
l = _mod64(length(B))
if l == 1
_deleteend!(Bc, 1)
elseif length(Bc) > k
Bc[end] >>>= 1
end
end
B.len -= 1
return B
end
function deleteat!(B::BitVector, i::Integer)
i isa Bool && depwarn("passing Bool as an index is deprecated", :deleteat!)
i = Int(i)
n = length(B)
1 <= i <= n || throw(BoundsError(B, i))
return _deleteat!(B, i)
end
function deleteat!(B::BitVector, r::AbstractUnitRange{Int})
n = length(B)
i_f = first(r)
i_l = last(r)
1 <= i_f || throw(BoundsError(B, i_f))
i_l <= n || throw(BoundsError(B, n+1))
Bc = B.chunks
new_l = length(B) - length(r)
delta_k = num_bit_chunks(new_l) - length(Bc)
copy_chunks!(Bc, i_f, Bc, i_l+1, n-i_l)
delta_k < 0 && _deleteend!(Bc, -delta_k)
B.len = new_l
if new_l > 0
Bc[end] &= _msk_end(new_l)
end
return B
end
function deleteat!(B::BitVector, inds)
n = new_l = length(B)
y = iterate(inds)
y === nothing && return B
Bc = B.chunks
(p, s) = y
checkbounds(B, p)
p isa Bool && throw(ArgumentError("invalid index $p of type Bool"))
q = p+1
new_l -= 1
y = iterate(inds, s)
while y !== nothing
(i, s) = y
if !(q <= i <= n)
i isa Bool && throw(ArgumentError("invalid index $i of type Bool"))
i < q && throw(ArgumentError("indices must be unique and sorted"))
throw(BoundsError(B, i))
end
new_l -= 1
if i > q
copy_chunks!(Bc, Int(p), Bc, Int(q), Int(i-q))
p += i-q
end
q = i+1
y = iterate(inds, s)
end
q <= n && copy_chunks!(Bc, Int(p), Bc, Int(q), Int(n-q+1))
delta_k = num_bit_chunks(new_l) - length(Bc)
delta_k < 0 && _deleteend!(Bc, -delta_k)
B.len = new_l
if new_l > 0
Bc[end] &= _msk_end(new_l)
end
return B
end
function deleteat!(B::BitVector, inds::AbstractVector{Bool})
length(inds) == length(B) || throw(BoundsError(B, inds))
n = new_l = length(B)
y = findfirst(inds)
y === nothing && return B
Bc = B.chunks
p = y
s = y + 1
checkbounds(B, p)
q = p + 1
new_l -= 1
y = findnext(inds, s)
while y !== nothing
i = y
s = y + 1
new_l -= 1
if i > q
copy_chunks!(Bc, Int(p), Bc, Int(q), Int(i-q))
p += i - q
end
q = i + 1
y = findnext(inds, s)
end
q <= n && copy_chunks!(Bc, Int(p), Bc, Int(q), Int(n - q + 1))
delta_k = num_bit_chunks(new_l) - length(Bc)
delta_k < 0 && _deleteend!(Bc, -delta_k)
B.len = new_l
if new_l > 0
Bc[end] &= _msk_end(new_l)
end
return B
end
keepat!(B::BitVector, inds) = _keepat!(B, inds)
keepat!(B::BitVector, inds::AbstractVector{Bool}) = _keepat!(B, inds)
function splice!(B::BitVector, i::Integer)
# TODO: after deprecation remove the four lines below
# as v = B[i] is enough to do both bounds checking
# and Bool check then just pass Int(i) to _deleteat!
i isa Bool && depwarn("passing Bool as an index is deprecated", :splice!)
i = Int(i)
n = length(B)
1 <= i <= n || throw(BoundsError(B, i))
v = B[i] # TODO: change to a copy if/when subscripting becomes an ArrayView
_deleteat!(B, i)
return v
end
const _default_bit_splice = BitVector()
function splice!(B::BitVector, r::Union{AbstractUnitRange{Int}, Integer}, ins::AbstractArray = _default_bit_splice)
r isa Bool && depwarn("passing Bool as an index is deprecated", :splice!)
_splice_int!(B, isa(r, AbstractUnitRange{Int}) ? r : Int(r), ins)
end
function _splice_int!(B::BitVector, r, ins)
n = length(B)
i_f, i_l = first(r), last(r)
1 <= i_f <= n+1 || throw(BoundsError(B, i_f))
i_l <= n || throw(BoundsError(B, n+1))
Bins = convert(BitArray, ins)
if (i_f > n)
append!(B, Bins)
return BitVector()
end
v = B[r] # TODO: change to a copy if/when subscripting becomes an ArrayView
Bc = B.chunks
lins = length(Bins)
ldel = length(r)
new_l = length(B) + lins - ldel
delta_k = num_bit_chunks(new_l) - length(Bc)
delta_k > 0 && _growend!(Bc, delta_k)
copy_chunks!(Bc, i_f+lins, Bc, i_l+1, n-i_l)
copy_chunks!(Bc, i_f, Bins.chunks, 1, lins)
delta_k < 0 && _deleteend!(Bc, -delta_k)
B.len = new_l
if new_l > 0
Bc[end] &= _msk_end(new_l)
end
return v
end
function splice!(B::BitVector, r::Union{AbstractUnitRange{Int}, Integer}, ins)
Bins = BitVector(undef, length(ins))
i = 1
for x in ins
Bins[i] = Bool(x)
i += 1
end
return splice!(B, r, Bins)
end
function empty!(B::BitVector)
_deleteend!(B.chunks, length(B.chunks))
B.len = 0
return B
end
## Unary operators ##
function (-)(B::BitArray)
A = zeros(Int, size(B))
l = length(B)
l == 0 && return A
Bc = B.chunks
ind = 1
for i = 1:length(Bc)-1
u = UInt64(1)
c = Bc[i]
for j = 1:64
if c & u != 0
A[ind] = -1
end
ind += 1
u <<= 1
end
end
u = UInt64(1)
c = Bc[end]
for j = 0:_mod64(l-1)
if c & u != 0
A[ind] = -1
end
ind += 1
u <<= 1
end
return A
end
## Binary arithmetic operators ##
for f in (:+, :-)
@eval function ($f)(A::BitArray, B::BitArray)
r = Array{Int}(undef, promote_shape(size(A), size(B)))
ay, by = iterate(A), iterate(B)
ri = 1
# promote_shape guarantees that A and B have the
# same iteration space
while ay !== nothing
@inbounds r[ri] = ($f)(ay[1], by[1])
ri += 1
ay, by = iterate(A, ay[2]), iterate(B, by[2])
end
return r
end
end
for f in (:/, :\)
@eval begin
($f)(A::Union{BitMatrix,BitVector}, B::Union{BitMatrix,BitVector}) = ($f)(Array(A), Array(B))
end
end
(/)(B::BitArray, x::Number) = (/)(Array(B), x)
(/)(x::Number, B::BitArray) = (/)(x, Array(B))
## promotion to complex ##
# TODO?
## comparison operators ##
function (==)(A::BitArray, B::BitArray)
size(A) != size(B) && return false
return A.chunks == B.chunks
end
## Data movement ##
# TODO some of this could be optimized
_reverse(A::BitArray, d::Tuple{Integer}) = _reverse(A, d[1])
function _reverse(A::BitArray, d::Int)
nd = ndims(A)
1 ≤ d ≤ nd || throw(ArgumentError("dimension $d is not 1 ≤ $d ≤ $nd"))
sd = size(A, d)
sd == 1 && return copy(A)
B = similar(A)
nnd = 0
for i = 1:nd
nnd += size(A,i)==1 || i==d
end
if nnd == nd
# reverse along the only non-singleton dimension
for i = 1:sd
B[i] = A[sd+1-i]
end
return B
end
d_in = size(A)
leading = d_in[1:(d-1)]
M = prod(leading)
N = length(A)
stride = M * sd
if M == 1
for j = 0:stride:(N-stride)
for i = 1:sd
ri = sd+1-i
B[j + ri] = A[j + i]
end
end
else
for i = 1:sd
ri = sd+1-i
for j=0:stride:(N-stride)
offs = j + 1 + (i-1)*M
boffs = j + 1 + (ri-1)*M
copy_chunks!(B.chunks, boffs, A.chunks, offs, M)
end
end
end
return B
end
function _reverse!(B::BitVector, ::Colon)
# Basic idea: each chunk is divided into two blocks of size k = n % 64, and
# h = 64 - k. Walk from either end (with indices i and j) reversing chunks
# and separately ORing their two blocks into place.
#
# chunk 3 chunk 2 chunk 1
# ┌───────────────┬───────┐┌───────────────┬───────┐┌───────────────┬───────┐
# │000000000000000│ E ││ D │ C ││ B │ A │
# └───────────────┴───────┘└───────────────┴───────┘└───────────────┴───────┘
# k h k h k
# yielding;
# ┌───────────────┬───────┐┌───────────────┬───────┐┌───────────────┬───────┐
# │000000000000000│ A' ││ B' │ C' ││ D' │ E' │
# └───────────────┴───────┘└───────────────┴───────┘└───────────────┴───────┘
n = length(B)
n == 0 && return B
k = _mod64(n+63) + 1
h = 64 - k
i, j = 0, length(B.chunks)
u = UInt64(0)
v = bitreverse(B.chunks[j])
B.chunks[j] = 0
@inbounds while true
i += 1
if i == j
break
end
u = bitreverse(B.chunks[i])
B.chunks[i] = 0
B.chunks[j] |= u >>> h
B.chunks[i] |= v >>> h
j -= 1
if i == j
break
end
v = bitreverse(B.chunks[j])
B.chunks[j] = 0
B.chunks[i] |= v << k
B.chunks[j] |= u << k
end
if isodd(length(B.chunks))
B.chunks[i] |= v >>> h
else
B.chunks[i] |= u << k
end
return B
end
function (<<)(B::BitVector, i::UInt)
n = length(B)
i == 0 && return copy(B)
A = falses(n)
i < n && copy_chunks!(A.chunks, 1, B.chunks, Int(i+1), Int(n-i))
return A
end
function (>>>)(B::BitVector, i::UInt)
n = length(B)
i == 0 && return copy(B)
A = falses(n)
i < n && copy_chunks!(A.chunks, Int(i+1), B.chunks, 1, Int(n-i))
return A
end
"""
>>(B::BitVector, n) -> BitVector
Right bit shift operator, `B >> n`. For `n >= 0`, the result is `B`
with elements shifted `n` positions forward, filling with `false`
values. If `n < 0`, elements are shifted backwards. Equivalent to
`B << -n`.
# Examples
```jldoctest
julia> B = BitVector([true, false, true, false, false])
5-element BitVector:
1
0
1
0
0
julia> B >> 1
5-element BitVector:
0
1
0
1
0
julia> B >> -1
5-element BitVector:
0
1
0
0
0
```
"""
(>>)(B::BitVector, i::Union{Int, UInt}) = B >>> i
# signed integer version of shift operators with handling of negative values
"""
<<(B::BitVector, n) -> BitVector
Left bit shift operator, `B << n`. For `n >= 0`, the result is `B`
with elements shifted `n` positions backwards, filling with `false`
values. If `n < 0`, elements are shifted forwards. Equivalent to
`B >> -n`.
# Examples
```jldoctest
julia> B = BitVector([true, false, true, false, false])
5-element BitVector:
1
0
1
0
0
julia> B << 1
5-element BitVector:
0
1
0
0
0
julia> B << -1
5-element BitVector:
0
1
0
1
0
```
"""
(<<)(B::BitVector, i::Int) = (i >=0 ? B << unsigned(i) : B >> unsigned(-i))
"""
>>>(B::BitVector, n) -> BitVector
Unsigned right bitshift operator, `B >>> n`. Equivalent to `B >> n`. See [`>>`](@ref) for
details and examples.
"""
(>>>)(B::BitVector, i::Int) = (i >=0 ? B >> unsigned(i) : B << unsigned(-i))
circshift!(dest::BitVector, src::BitVector, i::Integer) = _circshift_int!(dest, src, Int(i))
function _circshift_int!(dest::BitVector, src::BitVector, i::Int)
i = Int(i)
length(dest) == length(src) || throw(ArgumentError("destination and source should be of same size"))
n = length(dest)
i %= n
i == 0 && return (src === dest ? src : copyto!(dest, src))
Bc = (src === dest ? copy(src.chunks) : src.chunks)
if i > 0 # right
copy_chunks!(dest.chunks, i+1, Bc, 1, n-i)
copy_chunks!(dest.chunks, 1, Bc, n-i+1, i)
else # left
i = -i
copy_chunks!(dest.chunks, 1, Bc, i+1, n-i)
copy_chunks!(dest.chunks, n-i+1, Bc, 1, i)
end
return dest
end
circshift!(B::BitVector, i::Integer) = circshift!(B, B, i)
## count & find ##
function bitcount(Bc::Vector{UInt64}; init::T=0) where {T}
n::T = init
@inbounds for i = 1:length(Bc)
n = (n + count_ones(Bc[i])) % T
end
return n
end
_count(::typeof(identity), B::BitArray, ::Colon, init) = bitcount(B.chunks; init)
function unsafe_bitfindnext(Bc::Vector{UInt64}, start::Int)
chunk_start = _div64(start-1)+1
within_chunk_start = _mod64(start-1)
mask = _msk64 << within_chunk_start
@inbounds begin
if Bc[chunk_start] & mask != 0
return (chunk_start-1) << 6 + trailing_zeros(Bc[chunk_start] & mask) + 1
end
for i = chunk_start+1:length(Bc)
if Bc[i] != 0
return (i-1) << 6 + trailing_zeros(Bc[i]) + 1
end
end
end
return nothing
end
# returns the index of the next true element, or nothing if all false
function findnext(B::BitArray, start::Integer)
start = Int(start)
start > 0 || throw(BoundsError(B, start))
start > length(B) && return nothing
unsafe_bitfindnext(B.chunks, start)
end
#findfirst(B::BitArray) = findnext(B, 1) ## defined in array.jl
# aux function: same as findnext(~B, start), but performed without temporaries
function findnextnot(B::BitArray, start::Int)
start > 0 || throw(BoundsError(B, start))
start > length(B) && return nothing
Bc = B.chunks
l = length(Bc)
l == 0 && return nothing
chunk_start = _div64(start-1)+1
within_chunk_start = _mod64(start-1)
mask = ~(_msk64 << within_chunk_start)
@inbounds if chunk_start < l
if Bc[chunk_start] | mask != _msk64
return (chunk_start-1) << 6 + trailing_ones(Bc[chunk_start] | mask) + 1
end
for i = chunk_start+1:l-1
if Bc[i] != _msk64
return (i-1) << 6 + trailing_ones(Bc[i]) + 1
end
end
if Bc[l] != _msk_end(B)
return (l-1) << 6 + trailing_ones(Bc[l]) + 1
end
elseif Bc[l] | mask != _msk_end(B)
return (l-1) << 6 + trailing_ones(Bc[l] | mask) + 1
end
return nothing
end
findfirstnot(B::BitArray) = findnextnot(B,1)
# returns the index of the first matching element
function findnext(pred::Fix2{<:Union{typeof(isequal),typeof(==)},Bool},
B::BitArray, start::Integer)
v = pred.x
v == false && return findnextnot(B, Int(start))
v == true && return findnext(B, start)
return nothing
end
#findfirst(B::BitArray, v) = findnext(B, 1, v) ## defined in array.jl
# returns the index of the first element for which the function returns true
findnext(testf::Function, B::BitArray, start::Integer) = _findnext_int(testf, B, Int(start))
function _findnext_int(testf::Function, B::BitArray, start::Int)
f0::Bool = testf(false)
f1::Bool = testf(true)
!f0 && f1 && return findnext(B, start)
f0 && !f1 && return findnextnot(B, start)
start > 0 || throw(BoundsError(B, start))
start > length(B) && return nothing
f0 && f1 && return start
return nothing # last case: !f0 && !f1
end
#findfirst(testf::Function, B::BitArray) = findnext(testf, B, 1) ## defined in array.jl
function unsafe_bitfindprev(Bc::Vector{UInt64}, start::Int)
chunk_start = _div64(start-1)+1
mask = _msk_end(start)
@inbounds begin
if Bc[chunk_start] & mask != 0
return (chunk_start-1) << 6 + (top_set_bit(Bc[chunk_start] & mask))
end
for i = (chunk_start-1):-1:1
if Bc[i] != 0
return (i-1) << 6 + (top_set_bit(Bc[i]))
end
end
end
return nothing
end
# returns the index of the previous true element, or nothing if all false
function findprev(B::BitArray, start::Integer)
start = Int(start)
start > 0 || return nothing
start > length(B) && throw(BoundsError(B, start))
unsafe_bitfindprev(B.chunks, start)
end
function findprevnot(B::BitArray, start::Int)
start = Int(start)
start > 0 || return nothing
start > length(B) && throw(BoundsError(B, start))
Bc = B.chunks
chunk_start = _div64(start-1)+1
mask = ~_msk_end(start)
@inbounds begin
if Bc[chunk_start] | mask != _msk64
return (chunk_start-1) << 6 + (64 - leading_ones(Bc[chunk_start] | mask))
end
for i = chunk_start-1:-1:1
if Bc[i] != _msk64
return (i-1) << 6 + (64 - leading_ones(Bc[i]))
end
end
end
return nothing
end
findlastnot(B::BitArray) = findprevnot(B, length(B))
# returns the index of the previous matching element
function findprev(pred::Fix2{<:Union{typeof(isequal),typeof(==)},Bool},
B::BitArray, start::Integer)
v = pred.x
v == false && return findprevnot(B, Int(start))
v == true && return findprev(B, start)
return nothing
end
#findlast(B::BitArray, v) = findprev(B, 1, v) ## defined in array.jl
# returns the index of the previous element for which the function returns true
findprev(testf::Function, B::BitArray, start::Integer) = _findprev_int(testf, B, Int(start))
function _findprev_int(testf::Function, B::BitArray, start::Int)
f0::Bool = testf(false)
f1::Bool = testf(true)
!f0 && f1 && return findprev(B, start)
f0 && !f1 && return findprevnot(B, start)
start > 0 || return nothing
start > length(B) && throw(BoundsError(B, start))
f0 && f1 && return start
return nothing # last case: !f0 && !f1
end
#findlast(testf::Function, B::BitArray) = findprev(testf, B, 1) ## defined in array.jl
function findmax(a::BitArray)
isempty(a) && throw(ArgumentError("BitArray must be non-empty"))
m, mi = false, 1
ti = 1
ac = a.chunks
for i = 1:length(ac)
@inbounds k = trailing_zeros(ac[i])
ti += k
k == 64 || return (true, @inbounds keys(a)[ti])
end
return m, @inbounds keys(a)[mi]
end
function findmin(a::BitArray)
isempty(a) && throw(ArgumentError("BitArray must be non-empty"))
m, mi = true, 1
ti = 1
ac = a.chunks
for i = 1:length(ac)-1
@inbounds k = trailing_ones(ac[i])
ti += k
k == 64 || return (false, @inbounds keys(a)[ti])
end
l = Base._mod64(length(a)-1) + 1
@inbounds k = trailing_ones(ac[end] & Base._msk_end(l))
ti += k
k == l || return (false, @inbounds keys(a)[ti])
return (m, @inbounds keys(a)[mi])
end
# findall helper functions
# Generic case (>2 dimensions)
function allindices!(I, B::BitArray)
ind = first(keys(B))
for k = 1:length(B)
I[k] = ind
ind = nextind(B, ind)
end
end
# Optimized case for vector
function allindices!(I, B::BitVector)
I[:] .= 1:length(B)
end
# Optimized case for matrix
function allindices!(I, B::BitMatrix)
k = 1
for c = 1:size(B,2), r = 1:size(B,1)
I[k] = CartesianIndex(r, c)
k += 1
end
end
@inline _overflowind(i1, irest::Tuple{}, size) = (i1, irest)
@inline function _overflowind(i1, irest, size)
i2 = irest[1]
while i1 > size[1]
i1 -= size[1]
i2 += 1
end
i2, irest = _overflowind(i2, tail(irest), tail(size))
return (i1, (i2, irest...))
end
@inline _toind(i1, irest::Tuple{}) = i1
@inline _toind(i1, irest) = CartesianIndex(i1, irest...)
function findall(B::BitArray)
nnzB = count(B)
I = Vector{eltype(keys(B))}(undef, nnzB)
nnzB == 0 && return I
nnzB == length(B) && (allindices!(I, B); return I)
Bc = B.chunks
Bs = size(B)
Bi = i1 = i = 1
irest = ntuple(one, ndims(B) - 1)
c = Bc[1]
@inbounds while true
while c == 0
Bi == length(Bc) && return I
i1 += 64
Bi += 1
c = Bc[Bi]
end
tz = trailing_zeros(c)
c = _blsr(c)
i1, irest = _overflowind(i1 + tz, irest, Bs)
I[i] = _toind(i1, irest)
i += 1
i1 -= tz
end
end
# For performance
findall(::typeof(!iszero), B::BitArray) = findall(B)
## Reductions ##
_sum(A::BitArray, dims) = reduce(+, A, dims=dims)
_sum(B::BitArray, ::Colon) = count(B)
function all(B::BitArray)
isempty(B) && return true
Bc = B.chunks
@inbounds begin
for i = 1:length(Bc)-1
Bc[i] == _msk64 || return false
end
Bc[end] == _msk_end(B) || return false
end
return true
end
function any(B::BitArray)
isempty(B) && return false
Bc = B.chunks
@inbounds begin
for i = 1:length(Bc)
Bc[i] == 0 || return true
end
end
return false
end
minimum(B::BitArray) = isempty(B) ? throw(ArgumentError("argument must be non-empty")) : all(B)
maximum(B::BitArray) = isempty(B) ? throw(ArgumentError("argument must be non-empty")) : any(B)
## map over bitarrays ##
# Specializing map is even more important for bitarrays than it is for generic
# arrays since there can be a 64x speedup by working at the level of Int64
# instead of looping bit-by-bit.
map(::Union{typeof(~), typeof(!)}, A::BitArray) = bit_map!(~, similar(A), A)
map(::typeof(zero), A::BitArray) = fill!(similar(A), false)
map(::typeof(one), A::BitArray) = fill!(similar(A), true)
map(::typeof(identity), A::BitArray) = copy(A)
map!(::Union{typeof(~), typeof(!)}, dest::BitArray, A::BitArray) = bit_map!(~, dest, A)
map!(::typeof(zero), dest::BitArray, A::BitArray) = fill!(dest, false)
map!(::typeof(one), dest::BitArray, A::BitArray) = fill!(dest, true)
map!(::typeof(identity), dest::BitArray, A::BitArray) = copyto!(dest, A)
for (T, f) in ((:(Union{typeof(&), typeof(*), typeof(min)}), :(&)),
(:(Union{typeof(|), typeof(max)}), :(|)),
(:(Union{typeof(xor), typeof(!=)}), :xor),
(:(typeof(nand)), :nand),
(:(typeof(nor)), :nor),
(:(Union{typeof(>=), typeof(^)}), :((p, q) -> p | ~q)),
(:(typeof(<=)), :((p, q) -> ~p | q)),
(:(typeof(==)), :((p, q) -> ~xor(p, q))),
(:(typeof(<)), :((p, q) -> ~p & q)),
(:(typeof(>)), :((p, q) -> p & ~q)))
@eval map(::$T, A::BitArray, B::BitArray) = bit_map!($f, similar(A), A, B)
@eval map!(::$T, dest::BitArray, A::BitArray, B::BitArray) = bit_map!($f, dest, A, B)
end
# If we were able to specialize the function to a known bitwise operation,
# map across the chunks. Otherwise, fall-back to the AbstractArray method that
# iterates bit-by-bit.
function bit_map!(f::F, dest::BitArray, A::BitArray) where F
length(A) <= length(dest) || throw(DimensionMismatch("length of destination must be >= length of collection"))
isempty(A) && return dest
destc = dest.chunks
Ac = A.chunks
len_Ac = length(Ac)
for i = 1:(len_Ac-1)
destc[i] = f(Ac[i])
end
# the last effected UInt64's original content
dest_last = destc[len_Ac]
_msk = _msk_end(A)
# first zero out the bits mask is going to change
# then update bits by `or`ing with a masked RHS
# DO NOT SEPARATE ONTO TO LINES.
# Otherwise there will be bugs when Ac aliases destc
destc[len_Ac] = (dest_last & (~_msk)) | f(Ac[len_Ac]) & _msk
dest
end
function bit_map!(f::F, dest::BitArray, A::BitArray, B::BitArray) where F
min_bitlen = min(length(A), length(B))
min_bitlen <= length(dest) || throw(DimensionMismatch("length of destination must be >= length of smallest input collection"))
isempty(A) && return dest
isempty(B) && return dest
destc = dest.chunks
Ac = A.chunks
Bc = B.chunks
len_Ac = min(length(Ac), length(Bc))
for i = 1:len_Ac-1
destc[i] = f(Ac[i], Bc[i])
end
# the last effected UInt64's original content
dest_last = destc[len_Ac]
_msk = _msk_end(min_bitlen)
# first zero out the bits mask is going to change
# then update bits by `or`ing with a masked RHS
# DO NOT SEPARATE ONTO TO LINES.
# Otherwise there will be bugs when Ac or Bc aliases destc
destc[len_Ac] = (dest_last & ~(_msk)) | f(Ac[end], Bc[end]) & _msk
dest
end
## Filter ##
function filter(f, Bs::BitArray)
boolmap::Array{Bool} = map(f, Bs)
Bs[boolmap]
end
## Concatenation ##
function hcat(B::BitVector...)
height = length(B[1])
for j = 2:length(B)
length(B[j]) == height ||
throw(DimensionMismatch("dimensions must match: $j-th argument has length $(length(B[j])), should have $height"))
end
M = BitMatrix(undef, height, length(B))
for j = 1:length(B)
copy_chunks!(M.chunks, (height*(j-1))+1, B[j].chunks, 1, height)
end
return M
end
function vcat(V::BitVector...)
n = 0
for Vk in V
n += length(Vk)
end
B = BitVector(undef, n)
j = 1
for Vk in V
copy_chunks!(B.chunks, j, Vk.chunks, 1, length(Vk))
j += length(Vk)
end
return B
end
function hcat(A::Union{BitMatrix,BitVector}...)
nargs = length(A)
nrows = size(A[1], 1)
ncols = 0
dense = true
for j = 1:nargs
Aj = A[j]
nd = ndims(Aj)
ncols += (nd==2 ? size(Aj,2) : 1)
size(Aj, 1) == nrows ||
throw(DimensionMismatch("row lengths must match: $j-th element has first dim $(size(Aj, 1)), should have $nrows"))
end
B = BitMatrix(undef, nrows, ncols)
pos = 1
for k = 1:nargs
Ak = A[k]
n = length(Ak)
copy_chunks!(B.chunks, pos, Ak.chunks, 1, n)
pos += n
end
return B
end
function vcat(A::BitMatrix...)
nargs = length(A)
nrows, nrowsA = 0, sizehint!(Int[], nargs)
for a in A
sz1 = size(a, 1)
nrows += sz1
push!(nrowsA, sz1)
end
ncols = size(A[1], 2)
for j = 2:nargs
size(A[j], 2) == ncols ||
throw(DimensionMismatch("column lengths must match: $j-th element has second dim $(size(A[j], 2)), should have $ncols"))
end
B = BitMatrix(undef, nrows, ncols)
Bc = B.chunks
pos_d = 1
pos_s = fill(1, nargs)
for j = 1:ncols, k = 1:nargs
copy_chunks!(Bc, pos_d, A[k].chunks, pos_s[k], nrowsA[k])
pos_s[k] += nrowsA[k]
pos_d += nrowsA[k]
end
return B
end
# general case, specialized for BitArrays and Integers
_cat(dims::Integer, X::Union{BitArray, Bool}...) = _cat(Int(dims)::Int, X...)
function _cat(dims::Int, X::Union{BitArray, Bool}...)
dims = Int(dims)
catdims = dims2cat(dims)
shape = cat_shape(catdims, map(cat_size, X))
A = falses(shape)
return __cat(A, shape, catdims, X...)
end
# hvcat -> use fallbacks in abstractarray.jl
# BitArray I/O
write(s::IO, B::BitArray) = write(s, B.chunks)
function read!(s::IO, B::BitArray)
n = length(B)
Bc = B.chunks
nc = length(read!(s, Bc))
if length(Bc) > 0 && Bc[end] & _msk_end(n) ≠ Bc[end]
Bc[end] &= _msk_end(n) # ensure that the BitArray is not broken
throw(DimensionMismatch("read mismatch, found non-zero bits after BitArray length"))
end
return B
end
sizeof(B::BitArray) = sizeof(B.chunks)
function _split_rest(a::Union{Vector, BitVector}, n::Int)
_check_length_split_rest(length(a), n)
last_n = a[end-n+1:end]
resize!(a, length(a) - n)
return a, last_n
end