GitHub

Small bit sets

SmallCollections.SmallBitSet — Type
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. The argument iter can be any iterator giving such values. If U is omitted, then UInt is taken. Called without an argument, the constructor returns an empty set.

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

Examples

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

julia> s = SmallBitSet{UInt8}(2*k for k in 1:3)
SmallBitSet{UInt8} with 3 elements:
  2
  4
  6

julia> first(s), last(s)
(2, 6)

julia> 4.0 in s
true

julia> SmallBitSet{UInt32}(s)
SmallBitSet{UInt32} with 3 elements:
  2
  4
  6
source
Base.convert — Method
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
source
SmallCollections.capacity — Method
capacity(::Type{<:SmallBitSet}) -> Int
capacity(s::SmallBitSet) -> Int

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

source
SmallCollections.smallbitsettype — Function
smallbitsettype(::Val{N}) where N -> Type{<:SmallBitSet}

Returns a type SmallBitSet{U} where U <: Unsigned has at least N bits.

Examples

julia> smallbitsettype(Val(30))
SmallBitSet{UInt32}

julia> smallbitsettype(Val(200))
SmallBitSet{BitIntegers.UInt256}
source
SmallCollections.fasthash — Method
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
source
Base.empty — Method
empty(s::S) where S <: SmallBitSet -> S

Return an empty SmallBitSet of the same type as s.

source
SmallCollections.first_as_set — Function
first_as_set(s::S) where S <: SmallBitSet -> S

Returns the smallest element of s as a singleton. If s is empty, then an empty set is returned.

See also Base.first.

Examples

julia> s = SmallBitSet{UInt8}(3:5);

julia> first_as_set(s)
SmallBitSet{UInt8} with 1 element:
  3

julia> first_as_set(empty(s))
SmallBitSet{UInt8}([])
source
SmallCollections.pop — Method
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!!.

source
SmallCollections.pop — Method
pop(s::S, x) where S <: SmallBitSet -> Tuple{S, Int}

Return the pair (t, Int(x)) where t is the set s with x deleted. The set s must contain x.

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

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

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

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

source
SmallCollections.exchange — Function
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
source
Base.any — Method
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.

source
Base.checkbounds — Function
checkbounds(::Type{Bool}, v::Union{AbstractFixedVector, AbstractSmallVector, PackedVector}, s::SmallBitSet) -> Bool

Returns true if all elements of s are inbounds for v.

See alse Base.checkbounds.

Examples

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

julia> s = SmallBitSet{UInt8}((1, 4))
SmallBitSet{UInt8} with 2 elements:
  1
  4

julia> checkbounds(Bool, v, s)
false

julia> checkbounds(v, s)
ERROR: BoundsError: attempt to access 3-element SmallVector{8, Int8} at index [SmallBitSet{UInt8}([1, 4])]
source

Orderings

The following orderings are available to compare one SmallBitSet to another.

Base.isless — Method
isless(s::SmallBitSet, t::SmallBitSet) -> Bool

Compares s and t in the colexicographic ordering.

Currently, sorting with the default ordering given by isless is significantly faster than specifiying one of the other orderings (including Colex).

See also SmallCollections.Colex.

source