Functions that work on sets of small integers >= 0.

UintSet is an alternative set type in Elixir emulating the MapSet interface as closely as possible. Many of the UintSet doctests and unit tests were adapted from MapSet. UintSet illustrates the construction of a functional data structure from scratch, implementing the Inspect, Enumerable, and Collectable protocols.

An UintSet can contain only non-negative integers. By definition, sets contain unique elements. Trying to insert a duplicate is a no-op:

  iex> uint_set = UintSet.new()
  #UintSet<[]>
  iex> uint_set = UintSet.put(uint_set, 3)
  #UintSet<[3]>
  iex> uint_set |> UintSet.put(2) |> UintSet.put(2)
  #UintSet<[2, 3]>

UintSet.new/1 accepts an enumerable of elements:

  iex> UintSet.new(1..5)
  #UintSet<[1, 2, 3, 4, 5]>

An UintSet is represented internally using the %UintSet{} struct. This struct can be used whenever there's a need to pattern match on something being an UintSet:

  iex> match?(%UintSet{}, UintSet.new())
  true

The %UintSet{} struct contains a single field—bits— an integer which is used as a bit vector where each bit set to 1 represents a number present in the set.

An empty set is stored as bits = 0:

  iex> empty = UintSet.new()
  iex> empty.bits
  0
  iex> UintSet.member?(empty, 0)
  false

A set containing just a 0 is stored as bits = 1, because the bit at 0 is set, so the element 0 is present:

  iex> set_with_zero = UintSet.new([0])
  iex> set_with_zero.bits
  1
  iex> UintSet.member?(set_with_zero, 0)
  true

A set with a 2 is stored as bits = 4, because the bit at 2 is set, so the element 2 is present:

  iex> set_with_two = UintSet.new([2])
  iex> set_with_two.bits
  4
  iex> UintSet.member?(set_with_two, 2)
  true

A set with the elements 0 and 1 is stored as bits = 3, because 3 is 0b11, so the bits at 0 and 1 are set:

  iex> set_with_zero_and_one = UintSet.new([0, 1])
  #UintSet<[0, 1]>
  iex> set_with_zero_and_one.bits
  3

The UintSet.new/1 function also accepts a keyword argument setting the initial value of the bits field:

  iex> UintSet.new(bits: 13)
  #UintSet<[0, 2, 3]>

This is easier to understand using base 2 notation for the argument:

  iex> UintSet.new(bits: 0b1101)
  #UintSet<[0, 2, 3]>

UintSets can also be constructed starting from other collection-type data structures: for example, see UintSet.new/1 or Enum.into/2.

All the content of an UintSet is represented by a single integer, which in Elixir is limited only by available memory. Using an integer as a bit vector allows set operations like union and intersection to be implemented using fast bitwise operators. See the source code of UintSet.union and UintSet.intersection.

A bit vector is efficient only for storing sets of small integers, or high-density sets where a large percentage of the possible elements are present. The memory usage is proportional only to the largest element stored, not to the number of elements present. If the largest element in a set is 1_000_000, the raw bits will take 125_000 bytes (⅛), regardless of the number of elements in the set.

This package was inspired by the intset example from chapter 6 of The Go Programming Language, by Alan. A. A. Donovan and Brian W. Kernighan.