View Source IntSet (IntSet v2.0.0)

Efficiently store and index a set of non-negative integers.

A set can be constructed using IntSet.new/0:

iex> IntSet.new()
IntSet.new([])

An IntSet obeys the same set semantics as MapSet, and provides constant-time operations for insertion, deletion, and membership checking. Use Enum.member?/2 to check for membership.

iex> IntSet.new(3) |> Enum.member?(3)
true

Sets also implement Collectable, so it can collect values in any context that a list can:

iex> Enum.into([1, 2, 3], IntSet.new())
IntSet.new([1, 2, 3])

Working with applications that use bitstrings becomes way easier, because IntSet.new/1 accepts a bitstring, and IntSet.bitstring/2 can return one.

iex> IntSet.new(5) |> IntSet.bitstring()
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1, 0::1, 0::1>>

iex> IntSet.new(<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1>>)
IntSet.new([5])

performance

Performance

An IntSet is significantly faster than Elixir's MapSet at set operations (union, intersection, difference, equality), but slower at everything else. The case for memory usage is similar: better than MapSet for set operations, worse for everything else.

OpMapSetIntSetComparison
new4.8K2.46K1.95x slower
member?6.78M2.93M2.31x slower
put4.19M1.15M3.66x slower
union156.4K944.31K6.04x faster
difference48.09891.27K18.53x faster
intersection14.03K905.70K64.54x faster
equal?0.26M2.41M9.25x faster

There is a benchmark checked into the project repo at perf/performance_test.exs. You can run it with mix run to see some results for yourself.

serialization

Serialization

With the use of IntSet.bitstring/2, and IntSet.new/1, you can serialize this collection very efficiently.

iex> IntSet.new([4, 8, 15, 16, 23, 42]) |> IntSet.bitstring() |> Base.encode16()
"088181000020"
iex> Base.decode16!("088181000020") |> IntSet.new()
IntSet.new([4, 8, 15, 16, 23, 42])

Link to this section Summary

Functions

Get a bitstring representing the members of a set.

Remove a number from the int set.

Returns a set that is int_set1 without the members of int_set2.

Checks if int_set and int_set2 have no members in common.

Checks if two sets are equal

Find all elements that are in both int_set1 and int_set2.

Returns a set of size n with all members not in the given IntSet.

Create an empty int set.

Create an int set with some starting value.

Add a value to the int set.

Create a new set that contains all of the elements of both x and y.

Link to this section Types

Link to this opaque

t()

View Source (opaque) (since 1.0.0)
@opaque t()

Link to this section Functions

Link to this function

bitstring(int_set)

View Source (since 1.1.0)
@spec bitstring(t()) :: bitstring()

Get a bitstring representing the members of a set.

examples

Examples

iex> IntSet.new(0) |> IntSet.bitstring()
<<128>>

iex> IntSet.new(5) |> IntSet.bitstring()
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1, 0::1, 0::1>>

iex> IntSet.new() |> IntSet.bitstring()
<<>>
Link to this function

delete(set, x)

View Source (since 1.0.0)
@spec delete(t(), non_neg_integer()) :: t()

Remove a number from the int set.

examples

Examples

iex> set = IntSet.new(5)
IntSet.new([5])
iex> IntSet.delete(set, 5)
IntSet.new([])
Link to this function

difference(int_set1, int_set2)

View Source (since 1.2.0)
@spec difference(t(), t()) :: t()

Returns a set that is int_set1 without the members of int_set2.

examples

Examples

iex> IntSet.difference(IntSet.new([1, 2]), IntSet.new([2, 3, 4]))
IntSet.new([1])
Link to this function

disjoint?(int_set1, int_set2)

View Source (since 1.2.0)
@spec disjoint?(t(), t()) :: boolean()

Checks if int_set and int_set2 have no members in common.

examples

Examples

iex> IntSet.disjoint?(IntSet.new([1, 2]), IntSet.new([3, 4]))
true

iex> IntSet.disjoint?(IntSet.new([1, 2]), IntSet.new([2, 3]))
false
Link to this function

equal?(int_set1, int_set2)

View Source (since 1.3.0)
@spec equal?(t(), t()) :: boolean()

Checks if two sets are equal

examples

Examples

iex> IntSet.equal?(IntSet.new([1, 2]), IntSet.new([2, 1, 1]))
true
iex> IntSet.equal?(IntSet.new([1, 2]), IntSet.new([3, 4]))
false
Link to this function

intersection(int_set1, int_set2)

View Source (since 1.3.0)
@spec intersection(t(), t()) :: t()

Find all elements that are in both int_set1 and int_set2.

examples

Examples

iex> IntSet.intersection(IntSet.new([1, 2]), IntSet.new([2, 3, 4]))
IntSet.new([2])

iex> IntSet.intersection(IntSet.new([1, 2]), IntSet.new([3, 4]))
IntSet.new([])
Link to this function

inverse(int_set, n)

View Source (since 1.4.0)
@spec inverse(t(), non_neg_integer()) :: t()

Returns a set of size n with all members not in the given IntSet.

You can visualize this operation as calling IntSet.difference/2 with the first argument being a full IntSet of size n.

examples

Examples

iex> IntSet.new(0) |> IntSet.inverse(1)
IntSet.new([])

iex> IntSet.new(0) |> IntSet.inverse(8)
IntSet.new([1, 2, 3, 4, 5, 6, 7])

iex> IntSet.new() |> IntSet.inverse(3)
IntSet.new([0, 1, 2])

iex> IntSet.new() |> IntSet.inverse(9)
IntSet.new([0, 1, 2, 3, 4, 5, 6, 7, 8])
@spec new() :: t()

Create an empty int set.

examples

Examples

iex> IntSet.new
IntSet.new([])
Link to this function

new(members)

View Source (since 1.0.0)
@spec new(non_neg_integer() | Enum.t() | bitstring()) :: t()

Create an int set with some starting value.

examples

Examples

You can create a set with a single starting value.

iex> IntSet.new(0)
IntSet.new([0])

You can also provide an enumerable of integers to start with.

iex> IntSet.new([1, 2, 3])
IntSet.new([1, 2, 3])

Lastly, you can initialize the set with a bit string. Binary strings are interpreted as little-endian, with the very first bit of the string representing the number zero.

iex> IntSet.new(<<1 :: 1>>)
IntSet.new([0])

iex> IntSet.new(<<0b1000_1000>>)
IntSet.new([0, 4])

iex> IntSet.new(<<0 :: 1>>)
IntSet.new([])
Link to this function

put(int_set, x)

View Source (since 1.0.0)
@spec put(t(), non_neg_integer()) :: t()

Add a value to the int set.

examples

Examples

iex> set = IntSet.new()
IntSet.new([])
iex> IntSet.put(set, 0)
IntSet.new([0])
Link to this function

union(x, y)

View Source (since 1.0.0)
@spec union(t(), t()) :: t()

Create a new set that contains all of the elements of both x and y.

examples

Examples

iex> a = IntSet.new(7)
iex> b = IntSet.new(4)
iex> IntSet.union(a, b)
IntSet.new([4, 7])