SmallCollections.jl

SmallCollections

This packages provides several immutable collections that don't allocate and are therefore faster than the usual types. The number of elements that these collections can hold is necessarily limited. At present SmallBitSet and subtypes of AbstractSmallVector are defined.

If the package BangBang.jl is loaded, then many functions defined by this package are also available in !!-form. For example, setindex!! with a SmallVector as first argument calls setindex.

Bounds checking can be skipped for the functions defined in this package by using the @inbounds macro.

See SmallBitSet, AbstractSmallVector, Base.@inbounds, Section "BangBang support".

AbstractSmallVector{T} <: AbstractVector{T}

AbstractSmallVector is the supertype of the vector types provided by this module. At present, these are SmallVector and PackedVector. Both are read-only ans can hold a variable number of elements up to a predefined maximal capacity. If the element type T is concrete, then these vector types do not allocate.

See also SmallVector, PackedVector.

capacity(::Type{<:AbstractSmallVector}) -> Int
capacity(v::AbstractSmallVector) -> Int

Return the largest number of elements this vector type can hold.

zeros(::Type{V}, n::Integer) where V <: AbstractSmallVector -> V

Return an AbstractSmallVector of type V containing n zeros.

See also ones.

ones(::Type{V}, n::Integer) where V <: AbstractSmallVector -> V

Return a AbstractSmallVector of type V containing n ones.

See also zeros.

setindex(v::V, x, i::Integer) where V <: AbstractSmallVector -> V

Substitute x for the i-th component of v and return the new vector.

See also Base.setindex, addindex.

addindex(v::V, x, i::Integer) where V <: AbstractSmallVector -> V

Add x to the i-th component of v and return the new vector.

See also setindex.

push(v::V, xs...) where V <: AbstractSmallVector -> V

Return the AbstractSmallVector obtained from v by appending the arguments xs.

See also Base.push!, BangBang.push!!.

pop(v::V) where {T, V <: AbstractSmallVector{T}} -> Tuple{V,T}

Return the tuple (w, x) where x is the last element of v and w obtained from v by dropping this element. The vector v must not be empty.

See also Base.pop!, BangBang.pop!!.

pushfirst((v::V, xs...) where V <: AbstractSmallVector -> V

Return the AbstractSmallVector obtained from v by prepending the arguments xs.

See also Base.pushfirst!, BangBang.pushfirst!!.

popfirst(v::V) where {T, V <: AbstractSmallVector{T}} -> Tuple{V,T}

Return the tuple (w, x) where x is the first element of v and w obtained from v by dropping this element. The vector v must not be empty.

See also Base.popfirst!, BangBang.popfirst!!.

insert(v::V, i::Integer, x) where V <: AbstractSmallVector{T} -> V

Return the AbstractSmallVector obtained from v by inserting x at position i. The position i must be between 1 and length(v)+1.

This is the non-mutating analog of Base.insert!.

See also duplicate.

duplicate(v::V, i::Integer, x) where V <: AbstractSmallVector{T} -> V

Duplicate the i-th entry of v by inserting it at position i+1 and return the new vector.

See also insert.

Example

julia> v = SmallVector{8,Int8}(1:3)
3-element SmallVector{8, Int8}:
 1
 2
 3

julia> duplicate(v, 2)
4-element SmallVector{8, Int8}:
 1
 2
 2
 3

deleteat(v::V, i::Integer) where V <: AbstractSmallVector -> V

Return the AbstractSmallVector obtained from v by deleting the element at position i. The latter must be between 1 and length(v).

See also Base.deleteat!, BangBang.deleteat!!.

popat(v::V, i::Integer) where {T, V <: AbstractSmallVector{T}} -> Tuple{V,T}

Return the tuple (w, x) where w obtained from v by deleting the element x at position i. The latter must be between 1 and length(v).

See also Base.popat!, BangBang.popat!!.

append(v::V, ws...) where V <: AbstractSmallVector -> V

Append all elements of the collections ws to v and return the new vector. Note that the resulting AbstractSmallVector has the same capacity as v.

See also Base.append!, BangBang.append!!.

prepend(v::V, ws...) where V <: AbstractSmallVector -> V

Prepend all elements of the collections ws to v and return the new vector. Note that the resulting AbstractSmallVector has the same capacity as v.

See also Base.prepend!.

support(v::AbstractSmallVector) -> SmallBitSet

Return the SmallBitSet with the indices of the non-zero elements of v.

See also SmallBitSet.

Example

julia> v = SmallVector{8,Int8}([1, 0, 2, 0, 0, 3]);

julia> support(v)
SmallBitSet{UInt64} with 3 elements:
  1
  3
  6

SmallVector{N,T} <: AbstractSmallVector{T}

SmallVector{N,T}()
SmallVector{N,T}(iter)
SmallVector{N}(v::AbstractVector{T})
SmallVector{N}(t::Tuple)
SmallVector(v::PackedVector{T})

SmallVector{N,T} is an immutable vector type that can hold up to N elements of type T. Here N can be any (small) positive integer. However, at least for bit integer and hardware float types, one usually takes N to be a power of 2.

The element type T can be omitted when creating the SmallVector from an AbstractVector or from a tuple. In the latter case, T is determined by promoting the element types of the tuple. If no argument is given, then an empty vector is returned. If the SmallVector is created from a PackedVector v and the parameter N is omitted, then it is set to capacity of v.

The unused elements of a SmallVector{N,T} are filled with the value default(T), which is predefined for several types including Number. Default values for other types must be defined explicitly.

Addition and subtraction of two SmallVectors is possible even if the vectors have different capacity. (Of course, their lengths must agree.) The capacity of the result is the smaller of the arguments' capacities in this case.

See also capacity, SmallCollections.default, promote_type.

Examples

julia> v = SmallVector{8,Int8}(2*x for x in 1:3)
3-element SmallVector{8, Int8}:
 2
 4
 6

julia> w = SmallVector{9}((1, 2.5, 4))
3-element SmallVector{9, Float64}:
 1.0
 2.5
 4.0

julia> v+w
3-element SmallVector{8, Float64}:
  3.0
  6.5
 10.0

empty(v::V) where V <: SmallVector -> V
empty(v::SmallVector{N}, U::Type) where {N,U} -> SmallVector{N,U}

Called with one argument, return an empty SmallVector of the same type as v. Called with two arguments, return an empty SmallVector with the same capacity as v and element type U.

fasthash(v::SmallVector [, h0::UInt]) -> UInt

Return a hash for v that may be computed faster than the standard hash for vectors. This new hash is consistent across all SmallVectorss of the same element type, but it may not be compatible with hash or with fasthash for a SmallVector having a different element type.

Currently, fasthash differs from hash only if the element type of v is a bit integer type with at most 32 bits, Bool or Char.

See also Base.hash.

Examples

julia> v = SmallVector{8,Int8}([1, 5, 6]);

julia> fasthash(v)
0x6466067ab41d0916

julia> fasthash(v) == hash(v)
false

julia> w = SmallVector{16,Int8}(v); fasthash(v) == fasthash(w)
true

julia> w = SmallVector{8,Int16}(v); fasthash(v) == fasthash(w)
false

sum_fast(v::SmallVector{N,T}) where {N,T}

Return the sum of the elements of v using @fastmath arithmetic if T is Float32 or Float64. Otherwise return sum(v).

See also Base.@fastmath.

Example

julia> v = SmallVector{4}([-0.0, -0.0])
2-element SmallVector{4, Float64}:
 -0.0
 -0.0

julia> sum(v), sum_fast(v)
(-0.0, 0.0)

map(f, v::SmallVector...) -> SmallVector

Apply f to the argument vectors elementwise and stop when one of them is exhausted. Note that the capacity of the resulting SmallVector is the minimum of the argument vectors' capacities.

See also capacity, Base.map(f, v::AbstractVector...), Section "Broadcasting".

Examples

julia> v = SmallVector{8}(1:3); w = SmallVector{4}(2.0:4.0); map(*, v, w)
3-element SmallVector{4, Float64}:
  2.0
  6.0
 12.0

julia> v = SmallVector{8}('a':'e'); w = SmallVector{4}('x':'z'); map(*, v, w)
3-element SmallVector{4, String}:
 "ax"
 "by"
 "cz"

PackedVector{U<:Unsigned,M,T<:Union{Base.BitInteger,Bool}} <: AbstractSmallVector{T}

PackedVector{U,M,T}()
PackedVector{U,M,T}(iter)
PackedVector{U,M}(v::AbstractVector{T})
PackedVector{U,M}(t::Tuple)
PackedVector(v::SmallVector{M,T})

This type of immutable vector stores the elements in a common bit mask of type U with M bits for each entry. The range of allowed values is -2^(M-1):2^(M-1)-1 if T <: Signed, 0:2^M-1 if T <: Unsigned and false:true if T == Bool. Apart from that, the official element type T is only used when retrieving an entry. The capacity, that is, the number of elements that can be stored, is given by bitsize(U)÷M.

The element type T can be omitted when creating the PackedVector from an AbstractVector or from a tuple. In the latter case, T is determined by promoting the element types of the tuple. If no argument is given, then an empty vector is returned. If the PackedVector is created from a SmallVector v and the parameters U and M are omitted, then M is set to bitsize(T) and U is chosen such that the capacity of the resulting vector is at least the capacity of v.

Overflow or underflow during addition or subtraction of vectors do not throw an error. The same applies to multiplication by a scalar of type T. Scalar multiplication by other types returns a Vector.

Compared to a SmallVector, a PackedVector may have faster insert and delete operations. Arithmetic operations are usually slower unless M is the size of a hardware integer.

See also capacity, SmallCollections.bitsize.

Examples

julia> v = PackedVector{UInt64,5,Int8}(-5:5:10)
4-element PackedVector{UInt64, 5, Int8}:
 -5
  0
  5
 10

julia> capacity(v)
12

julia> w = PackedVector{UInt64,5,Int8}([1, 2, 3, 4])
4-element PackedVector{UInt64, 5, Int8}:
 1
 2
 3
 4

julia> v+w
4-element PackedVector{UInt64, 5, Int8}:
 -4
  2
  8
 14

julia> Int8(2)*v
4-element PackedVector{UInt64, 5, Int8}:
 -10
   0
  10
 -12

bits(v::PackedVector{U}) where U -> U

Return the bit mask used internally to store the elements of the vector v.

SmallCollections.unsafe_add(v::V, w::V) where V <: PackedVector -> V

Add v and w and return the result. It is not checked that v and w have the same length. No overflow or underflow is allowed in any component, nor are sign changes in the case of signed integers.

This function is much faster than regular addition.

See also unsafe_sub.

SmallCollections.unsafe_sub(v::V, w::V) where V <: PackedVector -> V

Subtract w from v and return the result. It is not checked that v and w have the same length. No overflow or underflow is allowed in any component, nor are sign changes in the case of signed integers.

This function is much faster than regular addition.

See also unsafe_add.

SmallBitSet{U<:Unsigned} <: AbstractSet{Int}

SmallBitSet{U}([iter])
SmallBitSet([iter])

SmallBitSet{U} is an immutable set that can hold integers between 1 and the bit length of U. Called without an argument, it returns an empty set. If U is omitted, then UInt is taken.

All non-mutating functions for sets are supported. The non-mutating analogs push, pop and delete of the corresponding !-functions are also provided.

bits(s::SmallBitSet{U}) where U -> U

Return the bit mask used internally to store the elements of the set s.

See also convert(::Type{SmallBitSet}, ::Integer).

convert(::Type{SmallBitSet{U}}, mask::Integer) where U -> SmallBitSet{U}
convert(::Type{SmallBitSet}, mask::Integer) -> SmallBitSet{UInt}

Convert a bit mask to a SmallBitSet of the given type. This is the inverse operation to bits.

See also bits.

Examples

julia> s = SmallBitSet{UInt16}([1, 5, 6]);

julia> u = bits(s)
0x0031

julia> convert(SmallBitSet, u)
SmallBitSet{UInt64} with 3 elements:
  1
  5
  6

capacity(::Type{<:SmallBitSet}) -> Int
capacity(s::SmallBitSet) -> Int

Return the largest number that the given set or SmallBitSet type can store.

fasthash(s::SmallBitSet [, h0::UInt]) -> UInt

Return a hash for s that can be computed fast. This hash is consistent across all SmallBitSets, but it is not compatible with the hash used for sets.

See also Base.hash.

Examples

julia> s = SmallBitSet(1:3);

julia> fasthash(s)
0x828a4cc485149963

julia> fasthash(s) == hash(s)
false

julia> t = SmallBitSet{UInt16}(s);

julia> fasthash(s) == fasthash(t)
true

empty(s::S) where S <: SmallBitSet -> S

Return an empty SmallBitSet of the same type as s.

push(s::S, xs...) where S <: SmallBitSet -> S

Return the SmallBitSet obtained from s by adding the other arguments xs.

See also Base.push!, BangBang.push!!.

pop(s::S) where S <: SmallBitSet -> Tuple{S, Int}

Return the pair (t, x) where x is the smallest element from s and t is the set s with x deleted. The set s must be non-empty.

See also Base.pop!, BangBang.pop!!.

pop(s::S, x) where S <: SmallBitSet -> Tuple{S, Int}

Return the pair (t, x) where t is the set s with x deleted. The set s must be non-empty.

See also Base.pop!, BangBang.pop!!.

pop(s::S, x, default::T) where S <: SmallBitSet -> Tuple{S, Union{Int,T}}

If s contains x, return the pair (t, x) where t is the set s with x deleted. Otherwise return (s, default)

See also Base.pop!, BangBang.pop!!.

delete(s::S, x) where S <: SmallBitSet -> S

If s contains x, return the set obtained by deleting that element. Otherwise return s.

See also Base.delete!, BangBang.delete!!.

subsets(s::S) where S <: SmallBitSet -> AbstractVector{S}
subsets(n::Integer) -> AbstractVector{SmallBitSet{UInt}}

In the first form, return a vector of length 2^length(s) whose elements are the subsets of the set s.

In the second form the set s is taken to be SmallBitSet(1:n).

See also subsets(::Integer, ::Integer).

Examples

julia> collect(subsets(SmallBitSet{UInt8}([3, 5])))
4-element Vector{SmallBitSet{UInt8}}:
 SmallBitSet([])
 SmallBitSet([3])
 SmallBitSet([5])
 SmallBitSet([3, 5])

julia> collect(subsets(2))
4-element Vector{SmallBitSet{UInt64}}:
 SmallBitSet([])
 SmallBitSet([1])
 SmallBitSet([2])
 SmallBitSet([1, 2])

julia> subsets(2)[2]
SmallBitSet{UInt64} with 1 element:
  1

subsets(s::SmallBitSet, k::Integer)
subsets(n::Integer, k::Integer)

In the first form, return an iterator that yields all k-element subsets of the set s. The element type is the type of s. If k is negative or larger than length(s), then the iterator is empty.

In the second form the set s is taken to be SmallBitSet(1:n).

See also subsets(::Integer), shuffles.

Example

julia> collect(subsets(SmallBitSet{UInt8}(2:2:8), 3))
4-element Vector{SmallBitSet{UInt8}}:
 SmallBitSet([2, 4, 6])
 SmallBitSet([2, 4, 8])
 SmallBitSet([2, 6, 8])
 SmallBitSet([4, 6, 8])

julia> collect(subsets(3, 2))
3-element Vector{SmallBitSet{UInt64}}:
 SmallBitSet([1, 2])
 SmallBitSet([1, 3])
 SmallBitSet([2, 3])

julia> collect(subsets(3, 4))
SmallBitSet{UInt64}[]

compositions(s::S, ks::Vararg{Integer,N}) where {S <: SmallBitSet, N}
compositions(ks::Vararg{Integer,N}) where N

In the first form, return an iterator that yields all ks-compositions of the set s, that is, all ordered partitions of s into N sets of size ks[1] to ks[N], respectively. The element type is NTuple{N, S}. The partition sizes in ks must be non-negative and add up to length(s).

In the second form the set s is taken to be SmallBitSet(1:sum(ks)). This gives an iterator over all set compositions of the integer sum(ks).

See also subsets, shuffles.

Examples

julia> collect(compositions(SmallBitSet([2, 4, 5]), 1, 2))
3-element Vector{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}}}:
 (SmallBitSet([2]), SmallBitSet([4, 5]))
 (SmallBitSet([4]), SmallBitSet([2, 5]))
 (SmallBitSet([5]), SmallBitSet([2, 4]))

julia> collect(compositions(1, 1, 1))
6-element Vector{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}, SmallBitSet{UInt64}}}:
 (SmallBitSet([1]), SmallBitSet([2]), SmallBitSet([3]))
 (SmallBitSet([2]), SmallBitSet([1]), SmallBitSet([3]))
 (SmallBitSet([1]), SmallBitSet([3]), SmallBitSet([2]))
 (SmallBitSet([3]), SmallBitSet([1]), SmallBitSet([2]))
 (SmallBitSet([2]), SmallBitSet([3]), SmallBitSet([1]))
 (SmallBitSet([3]), SmallBitSet([2]), SmallBitSet([1]))

julia> collect(compositions(SmallBitSet([2, 4, 5]), 1, 0, 2))
3-element Vector{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}, SmallBitSet{UInt64}}}:
 (SmallBitSet([2]), SmallBitSet([]), SmallBitSet([4, 5]))
 (SmallBitSet([4]), SmallBitSet([]), SmallBitSet([2, 5]))
 (SmallBitSet([5]), SmallBitSet([]), SmallBitSet([2, 4]))

julia> collect(compositions(SmallBitSet()))
1-element Vector{Tuple{}}:
 ()

shuffles(s::S, ks::Vararg{Integer,N}) where {S <: SmallBitSet, N}
shuffles(ks::Vararg{Integer,N}) where N

In the first form, return an iterator that yields all ks-compositions of the set s together with the sign of the permutation that puts the elements back into an increasing order. See compositions and shuffle_signbit for details. The iterator returns tuples (t, s), where t is of type NTuple{N, S} and the sign bit s is of type Bool where false means +1 and true means -1. The partition sizes in ks must be non-negative and add up to length(s).

In the second form the set s is taken to be SmallBitSet(1:sum(ks)).

See also compositions, shuffle_signbit.

Examples

julia> collect(shuffles(SmallBitSet([2, 4, 5]), 1, 2))
3-element Vector{Tuple{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}}, Bool}}:
 ((SmallBitSet([2]), SmallBitSet([4, 5])), 0)
 ((SmallBitSet([4]), SmallBitSet([2, 5])), 1)
 ((SmallBitSet([5]), SmallBitSet([2, 4])), 0)

julia> all(s == shuffle_signbit(a, b) for ((a, b), s) in shuffles(1, 2))
true

shuffle_signbit(ss::SmallBitSet...) -> Bool

Return true if an odd number of transpositions is needed to transform the elements of the sets ss into an increasing sequence, and false otherwise. The sets are considered as increasing sequences and assumed to be disjoint.

See also shuffles.

Examples

julia> s, t, u = SmallBitSet([2, 3, 8]), SmallBitSet([1, 4, 6]), SmallBitSet([5, 7]);

julia> shuffle_signbit(s, t), shuffle_signbit(s, t, u)
(true, false)

SmallCollections.bitsize(T::Type) -> Int
SmallCollections.bitsize(x::T) where T -> Int

Return the size of the internal binary representation of T in bits. For Bool the function returns 1.

See also Base.sizeof.

SmallCollections.default(::Type{T}) where T -> T
SmallCollections.default(::T) where T -> T

Return the default value of type T used for filling unused elements of a SmallVector. This must be defined as zero(T) if T supports algebraic operations. Otherwise it can be any value of type T.

This function has methods for number types, bits types (including Char, SmallVector and SmallBitSet types), String and Symbol. Methods for other types must be defined explicitly.

See also Base.isbitstype.

SmallCollections.SmallVectorStyle <: Broadcast.AbstractArrayStyle{1}

The broadcasting style used for SmallVector.

See also SmallVector, Broadcast.AbstractArrayStyle.

SmallCollections.AbstractBitInteger

This type is the union of Base.BitInteger, BitIntegers.AbstractBitSigned and BitIntegers.AbstractBitUnsigned.

SmallCollections.top_set_bit(x::AbstractBitInteger) -> Int

Return the position of the highest set bit in x (counting from 1), or return 0 if x is 0.

This function is analogous to Julia's internal function Base.top_set_bit, but it is also fast and correct for bit integers defined by BitIntegers.jl.

See also Base.top_set_bit, SmallCollections.AbstractBitInteger.

SmallCollections.unsafe_shl(x::U, i::Integer) where U <: AbstractBitInteger -> U

This is a fast, but unsafe version of the left bit shift operator x << i. The shift i is assumed to be between 0 and bitsize(x)-1.

See also SmallCollections.bitsize, SmallCollections.AbstractBitInteger.

SmallCollections.unsafe_lshr(x::U, i::Integer) where U <: AbstractBitInteger -> U

This is a fast, but unsafe version of the logical (or unsigned) right bit shift operator x >>> i. The shift i is assumed to be between 0 and bitsize(x)-1.

See also SmallCollections.bitsize, SmallCollections.AbstractBitInteger.

SmallCollections.pdep(x::Unsigned, y::U) where U <: Unsigned -> U

Assume that y has exactly m 1-bits. Then pdep(x, y) replaces these bits by the m lowest bits of x (in order) and returns the result. The remaining bits of x are ignored.

On x86_64 and i686 machines, this function uses the corresponding instruction from the BMI2 instruction set if possible. Without hardware support it is much slower.