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

any(f::Function, s::SmallBitSet{U}; [style::MapStyle]) where U
all(f::Function, s::SmallBitSet{U}; [style::MapStyle]) where U
count(f, s::SmallBitSet{U}; init = 0, [style::MapStyle]) where U
filter(f, s::SmallBitSet{U}; [style::MapStyle]) where U

With a SmallBitSet s as second argument, these functions accept the additional keyword argument style. If it equals LazyStyle(), then the function f is only evaluated for elements of s. For any other value of style, f is evaluated on all numbers between 1 and the bit size of U. This is often faster for simple functions.

As discussed under MapStyle, the default value for style is based on a list of known functions.

See also SmallCollections.MapStyle.