Small bit sets

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!!.

exchange(s::S, i::Integer, j::Integer) where S <: SmallBitSet -> S

Return the set s with the element i, if present, replaced by j and vice versa. If i equals j, then the set is not modified.

This function is faster than the equivalent replace(s, i => j, j => i).

See also Base.replace.

Examples

julia> s = SmallBitSet((1, 2)); exchange(s, 1, 2)
SmallBitSet{UInt64} with 2 elements:
  1
  2

julia> s = SmallBitSet((1, 2)); exchange(s, 2, 3)
SmallBitSet{UInt64} with 2 elements:
  1
  3

julia> s = SmallBitSet((1, 2)); exchange(s, 3, 4)
SmallBitSet{UInt64} with 2 elements:
  1
  2

julia> s = SmallBitSet((1, 2)); exchange(s, 1, 1)
SmallBitSet{UInt64} with 2 elements:
  1
  2

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)