IntSet (IntSet v1.5.1) View Source

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

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

iex> IntSet.new
#IntSet<[]>

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<[1, 2, 3]>

The inspect/1 implementation for IntSet sorts the members, which makes it way easier to write doctests:

iex> IntSet.new([3, 1, 2])
#IntSet<[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>>

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

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

With the use of IntSet.bitstring/2, and IntSet.new/1, you can serialize this collection very efficiently. Remember to pass the byte_align: true option into IntSet.bitstring/2 when you do this; most encoding schemes like byte-aligned data.

iex> IntSet.new([4, 8, 15, 16, 23, 42]) |> IntSet.bitstring(byte_align: true) |> Base.encode16()
"088181000020"
iex> Base.decode16!("088181000020") |> IntSet.new()
#IntSet<[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 section Functions

Link to this function

bitstring(int_set, opts \\ [])

View Source (since 1.1.0)

Get a bitstring representing the members of a set.

Examples

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

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

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

You can also provide a :byte_align option, which will pad the end of the binary with zeroes until you're at a nice round n-byte size. By default this options is false.

iex> IntSet.new(5) |> IntSet.bitstring(byte_align: true)
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1, 0::1, 0::1>>
Link to this function

delete(set, x)

View Source (since 1.0.0)

Specs

delete(t(), non_neg_integer()) :: t()

Remove a number from the int set.

Examples

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

difference(int_set1, int_set2)

View Source (since 1.2.0)

Specs

difference(t(), t()) :: t()

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

Examples

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

disjoint?(int_set1, int_set2)

View Source (since 1.2.0)

Specs

disjoint?(t(), t()) :: boolean()

Checks if int_set and int_set2 have no members in common.

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)

Specs

equal?(t(), t()) :: boolean()

Checks if two sets are equal

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)

Specs

intersection(t(), t()) :: t()

Find all elements that are in both int_set1 and int_set2.

Examples

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

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

inverse(int_set, n)

View Source (since 1.4.0)

Specs

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

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

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

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

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

Specs

new() :: t()

Create an empty int set.

Examples

iex> IntSet.new
#IntSet<[]>
Link to this function

new(members)

View Source (since 1.0.0)

Specs

new(non_neg_integer() | Enum.t() | bitstring()) :: t()

Create an int set with some starting value.

Examples

You can create a set with a single starting value.

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

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

iex> IntSet.new([1, 2, 3])
#IntSet<[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<[0]>

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

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

Specs

put(t(), non_neg_integer()) :: t()

Add a value to the int set.

Examples

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

union(x, y)

View Source (since 1.0.0)

Specs

union(t(), t()) :: t()

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

Examples

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