Small and packed vectors

SmallCollections.AbstractCapacityVector — Type

AbstractCapacityVector{T} <: AbstractVector{T}

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

source

SmallCollections.capacity — Method

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

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

source

Base.empty — Method

empty(v::V) where V <: AbstractCapacityVector -> V

Return an empty AbstractCapacityVector of the same type as v.

source

Base.zeros — Function

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

Return an AbstractCapacityVector of type V containing n zeros.

Small vectors

SmallCollections.AbstractSmallVector — Type

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

AbstractSmallVector{N,T} is the supertype of SmallVector{N,T} and MutableSmallVector{N,T}.

source

SmallCollections.SmallVector — Type

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

SmallVector{N,T}()
SmallVector{N,T}(iter)
SmallVector{N}(iter)
SmallVector(v::PackedVector{T})
SmallVector(v::AbstractSmallVector)

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 iterator that has an element type, for example from an AbstractVector or 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 an AbstractSmallVector or 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 MutableSmallVector, capacity, SmallCollections.default, Base.IteratorEltype, 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

source

SmallCollections.MutableSmallVector — Type

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

MutableSmallVector{N,T}()
MutableSmallVector{N,T}(iter)
MutableSmallVector{N}(iter)
MutableSmallVector(v::PackedVector{T})
MutableSmallVector(v::AbstractSmallVector)

MutableSmallVector{N,T}(undef, n::Integer)

MutableSmallVector{N,T} is a mutable vector type that can hold up to N elements of type T. It is the mutable analog of SmallVector{N,T}.

Note that setting individual vector elements (via setindex!) is only supported for isbits element types.

The special form MutableSmallVector{N,T}(undef, n) returns a non-initialized vector of length n.

See also SmallVector, Base.isbitstype.

source

Base.empty — Method

empty(v::AbstractSmallVector{N}, S::Type) where {N,S} -> AbstractSmallVector{N,S}

Return an empty AbstractSmallVector with the same capacity as v and element type U. The resulting vector is mutable if and only if v is so.

source

SmallCollections.fasthash — Method

fasthash(v::AbstractSmallVector [, 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 AbstractSmallVectors of the same element type, but it may not be compatible with hash or with fasthash for a AbstractSmallVector 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 fasthash(::PackedVector, ::UInt), 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

source

SmallCollections.sum_fast — Method

sum_fast(v::AbstractSmallVector{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).

Packed vectors

SmallCollections.PackedVector — Type

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

PackedVector{U,M,T}()
PackedVector{U,M,T}(iter)
PackedVector{U,M}(v::AbstractVector{T})
PackedVector{U,M}(t::Tuple)
PackedVector(v::AbstractSmallVector{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 AbstractSmallVector 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.

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

source

SmallCollections.bits — Method

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

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

source

Base.empty — Method

empty(v::PackedVector{U,M}, S::Type) where {U,M,S} -> PackedVector{U,M,S}

Return an empty PackedVector with the same bit mask type and same bit size as v, but element type S.

source

SmallCollections.fasthash — Method

fasthash(v::PackedVector [, 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 PackedVector{U,M,T} of the same internal bit size M, but it may not be compatible with hash or with fasthash for a PackedVector having a different bit size. However, using fasthash for two PackedVectors with the same M, but both signed and unsigned element types T may lead to hash collisions.

See also fasthash(::AbstractSmallVector, ::UInt), Base.hash.

Examples

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

julia> fasthash(v)
0x11e89b9d8f3daac6

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

julia> w = PackedVector{UInt128,5,Int8}(v); fasthash(v) == fasthash(w)
true

julia> w = PackedVector{UInt64,4,Int8}(v); fasthash(v) == fasthash(w)
false

julia> w = PackedVector{UInt64,5,UInt8}(v); fasthash(v) == fasthash(w)
true

source

SmallCollections.unsafe_add — Function

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.

Permutations

SmallCollections.permutations — Function

permutations(n::Integer)

Return an iterator that yields all permutations of the integers from 1 to n.

The argument n must be between 0 and 16. The identity permutation is returned first. Each permutation is of type SmallVector{16,Int8}, but this may change in the future.

Examples

julia> collect(permutations(3))
6-element Vector{SmallVector{16, Int8}}:
 [1, 2, 3]
 [2, 1, 3]
 [3, 1, 2]
 [1, 3, 2]
 [2, 3, 1]
 [3, 2, 1]

julia> collect(permutations(0))
1-element Vector{SmallVector{16, Int8}}:
 0-element SmallVector{16, Int8}

source

SmallCollections.permutations_sign_transposition — Function

permutations_sign_transposition(n::Integer)

Return an iterator that yields all permutations p of the integers from 1 to n together with some extra data. The first element of the tuple returned is the permutation p. The second element is the sign of p (+1 for even and -1 for odd permutations). The third element is a pair (i, j) that indicates the transposition t by which p differs from the previously returned permutation q. (More precisely, the new permutations p is obtained by first applying t and then q.)

The argument n must be between 0 and 16. The iterator returns the identity permutation first; in this case the transposition pair is set to (0, 0). The true transpositions (i, j) satisfy i < j. Each permutation is of type SmallVector{16,Int8}, but this may change in the future.

See also permutations, Base.signbit.

Examples

julia> collect(permutations_sign_transposition(3))
6-element Vector{Tuple{SmallVector{16, Int8}, Int64, Tuple{Int64, Int64}}}:
 ([1, 2, 3], 1, (0, 0))
 ([2, 1, 3], -1, (1, 2))
 ([3, 1, 2], 1, (1, 3))
 ([1, 3, 2], -1, (1, 2))
 ([2, 3, 1], 1, (1, 3))
 ([3, 2, 1], -1, (1, 2))

julia> collect(SmallCollections.permutations_sign_transposition(0))
1-element Vector{Tuple{SmallVector{16, Int8}, Int64, Tuple{Int64, Int64}}}:
 ([], 1, (0, 0))

source