A.RBSet (Aja v0.4.3) View Source

A Red-Black tree implementation of a set. It keeps elements sorted in ascending order.

It works as a drop-in replacement for the built-in MapSet. Unlike MapSet which does not keep keys in any particular order, A.RBSet stores keys in ascending order.

Erlang's :gb_sets offer similar functionalities and performance. However A.RBSet:

Examples

A.RBSet offers the same API as MapSet:

iex> rb_set = A.RBSet.new([6, 6, 7, 7, 4, 1, 2, 3, 1.0, 5])
#A.RBSet<[1.0, 2, 3, 4, 5, 6, 7]>
iex> A.RBSet.member?(rb_set, 2)
true
iex> A.RBSet.member?(rb_set, 8)
false
iex> A.RBSet.put(rb_set, 4.25)
#A.RBSet<[1.0, 2, 3, 4, 4.25, 5, 6, 7]>
iex> A.RBSet.delete(rb_set, 1)
#A.RBSet<[2, 3, 4, 5, 6, 7]>
iex> A.RBSet.union(rb_set, A.RBSet.new([0, 2, 4, 6, 8]))
#A.RBSet<[0, 1.0, 2, 3, 4, 5, 6, 7, 8]>
iex> A.RBSet.intersection(rb_set, A.RBSet.new([0, 2, 4, 6, 8]))
#A.RBSet<[2, 4, 6]>
iex> A.RBSet.difference(rb_set, A.RBSet.new([0, 2, 4, 6, 8]))
#A.RBSet<[1.0, 3, 5, 7]>
iex> Enum.to_list(rb_set)
[1.0, 2, 3, 4, 5, 6, 7]
iex> [0, 1, 1.1, 2.2, 3.3] |> Enum.into(rb_set)
#A.RBSet<[0, 1, 1.1, 2, 2.2, 3, 3.3, 4, 5, 6, 7]>

Like for MapSets, elements in a set don't have to be of the same type:

iex> A.RBSet.new([1, :two, {"three"}])
#A.RBSet<[1, :two, {"three"}]>

Tree-specific functions

Due to its sorted nature, A.RBSet also offers some extra methods not present in MapSet, like:

  • first/1 and last/1 to efficiently retrieve the first (smallest) / last (largest) element
  • pop_first/1 and pop_last/1 to efficiently pop the first (smallest) / last (largest) element
  • foldl/3 and foldr/3 to efficiently fold (reduce) from left-to-right or right-to-left

Examples:

iex> rb_set = A.RBSet.new([8, 6, 0, 4, 2, 2, 2])
iex> A.RBSet.last(rb_set)
8
iex> {0, updated} = A.RBSet.pop_first(rb_set)
iex> updated
#A.RBSet<[2, 4, 6, 8]>
iex> A.RBSet.foldr(rb_set, [], fn value, acc -> [value + 1 | acc] end)
[1, 3, 5, 7, 9]

With Jason

iex> A.RBSet.new([6, 6, 7, 7, 4, 1, 2, 3, 1.0, 5]) |> Jason.encode!()
"[1.0,2,3,4,5,6,7]"

It also preserves the element order.

Limitations: equality

Like :gb_sets, A.RBSet comparisons based on ==/2, ===/2 or the pin operator ^ are UNRELIABLE.

In Elixir, pattern-matching and equality for structs work based on their internal representation. While this is a pragmatic design choice that simplifies the language, it means that we cannot rededine how they work for custom data structures.

Tree-based sets that are semantically equal (same elements in the same order) might be considered non-equal when comparing their internals, because there is not a unique way of representing one same set.

A.RBSet.equal?/2 should be used instead:

iex> rb_set1 = A.RBSet.new([1, 2])
#A.RBSet<[1, 2]>
iex> rb_set2 = A.RBSet.new([2, 1])
#A.RBSet<[1, 2]>
iex> rb_set1 == rb_set2
false
iex> A.RBSet.equal?(rb_set1, rb_set2)
true
iex> match?(^rb_set1, rb_set2)
false

Pattern-matching and opaque type

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

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

Note, however, than A.RBSet is an opaque type: its struct internal fields must not be accessed directly.

Use the functions in this module to perform operations on A.RBSets, or the Enum module.

Note about numbers

Unlike MapSets, A.RBSets only uses ordering for element comparisons, not strict comparisons. Integers and floats are indistiguinshable as elements.

iex> MapSet.new([1, 2, 3]) |> MapSet.member?(2.0)
false
iex> A.RBSet.new([1, 2, 3]) |> A.RBSet.member?(2.0)
true

Erlang's :gb_sets module works the same.

Memory overhead

A.RBSet takes roughly 1.2x more memory than a MapSet depending on the type of data:

iex> elements = Enum.map(1..100, fn i -> <<i>> end)
iex> map_set_size = MapSet.new(elements) |> :erts_debug.size()
684
iex> rb_set_size = A.RBSet.new(elements) |> :erts_debug.size()
810
iex> elements |> Enum.sort() |> :gb_sets.from_ordset() |> :erts_debug.size()
703
iex> div(100 * rb_set_size, map_set_size)
118

Underlying Red-Black Tree implementation

The underlying red-black tree implementation is available in A.RBTree.Set. The algorithm detail is described in its documentation.

Link to this section Summary

Functions

Deletes value from rb_set.

Returns a set that is rb_set1 without the members of rb_set2.

Checks if rb_set1 and rb_set2 have no members in common.

Checks if two sets are equal.

Finds the smallest element in the set. Returns nil for empty sets.

Folds (reduces) the given rb_set from the left with the function fun. Requires an accumulator acc.

Folds (reduces) the given rb_set from the right with the function fun. Requires an accumulator acc.

Returns a set containing only members that rb_set1 and rb_set2 have in common.

Finds the largest element in the set. Returns nil for empty sets.

Checks if rb_set contains value.

Returns a new empty set.

Creates a set from an enumerable.

Creates a set from an enumerable via the transformation function.

Removes and returns the smallest element in the set.

Removes and returns the largest element in the set.

Inserts value into rb_set if rb_set doesn't already contain it.

Returns the number of elements in rb_set.

Checks if rb_set1's members are all contained in rb_set2.

Converts rb_set to a list.

Returns a set containing all members of rb_set1 and rb_set2.

Link to this section Types

Specs

t() :: t(term())

Specs

t(value)

Specs

value() :: term()

Link to this section Functions

Specs

delete(t(val1), val2) :: t(val1) when val1: value(), val2: value()

Deletes value from rb_set.

Returns a new set which is a copy of rb_set but without value.

Examples

iex> rb_set = A.RBSet.new([1, 2, 3])
iex> A.RBSet.delete(rb_set, 4)
#A.RBSet<[1, 2, 3]>
iex> A.RBSet.delete(rb_set, 2)
#A.RBSet<[1, 3]>
Link to this function

difference(rb_set1, rb_set2)

View Source

Specs

difference(t(val), t(val)) :: t(val) when val: value()

Returns a set that is rb_set1 without the members of rb_set2.

Examples

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

disjoint?(rb_set1, rb_set2)

View Source

Specs

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

Checks if rb_set1 and rb_set2 have no members in common.

Examples

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

equal?(rb_set1, rb_set2)

View Source

Specs

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

Checks if two sets are equal.

The comparison between elements is done using ==/2, not strict equality ===/2.

Examples

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

first(rb_set, default \\ nil)

View Source

Specs

first(t(val), val | nil) :: val | nil when val: value()

Finds the smallest element in the set. Returns nil for empty sets.

This is very efficient and can be done in O(log(n)). It should be preferred over Enum.min/3.

Examples

iex> A.RBSet.new([4, 2, 3]) |> A.RBSet.first()
2
iex> A.RBSet.new() |> A.RBSet.first()
nil
iex> A.RBSet.new() |> A.RBSet.first(0)
0

Folds (reduces) the given rb_set from the left with the function fun. Requires an accumulator acc.

Examples

iex> A.RBSet.new([22, 11, 33]) |> A.RBSet.foldl(0, &+/2)
66
iex> A.RBSet.new([22, 11, 33]) |> A.RBSet.foldl([], &([2 * &1 | &2]))
[66, 44, 22]

Folds (reduces) the given rb_set from the right with the function fun. Requires an accumulator acc.

Unlike linked lists, this is as efficient as foldl/3. This can typically save a call to Enum.reverse/1 on the result when building a list.

Examples

iex> A.RBSet.new([22, 11, 33]) |> A.RBSet.foldr(0, &+/2)
66
iex> A.RBSet.new([22, 11, 33]) |> A.RBSet.foldr([], &([2 * &1 | &2]))
[22, 44, 66]
Link to this function

intersection(rb_set1, rb_set2)

View Source

Specs

intersection(t(val), t(val)) :: t(val) when val: value()

Returns a set containing only members that rb_set1 and rb_set2 have in common.

Examples

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

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

last(rb_set, default \\ nil)

View Source

Specs

last(t(val), val | nil) :: val | nil when val: value()

Finds the largest element in the set. Returns nil for empty sets.

This is very efficient and can be done in O(log(n)). It should be preferred over Enum.max/3.

Examples

iex> A.RBSet.new([4, 2, 3]) |> A.RBSet.last()
4
iex> A.RBSet.new() |> A.RBSet.last()
nil
iex> A.RBSet.new() |> A.RBSet.last(0)
0

Specs

member?(t(), value()) :: boolean()

Checks if rb_set contains value.

Examples

iex> A.RBSet.member?(A.RBSet.new([1, 2, 3]), 2)
true
iex> A.RBSet.member?(A.RBSet.new([1, 2, 3]), 4)
false

Specs

new() :: t()

Returns a new empty set.

Examples

iex> A.RBSet.new()
#A.RBSet<[]>

Specs

new(Enum.t()) :: t()

Creates a set from an enumerable.

Examples

iex> A.RBSet.new([:b, :a, 3])
#A.RBSet<[3, :a, :b]>
iex> A.RBSet.new([3, 3, 3, 2, 2, 1])
#A.RBSet<[1, 2, 3]>
Link to this function

new(enumerable, transform)

View Source

Specs

new(Enum.t(), (term() -> val)) :: t(val) when val: value()

Creates a set from an enumerable via the transformation function.

Examples

iex> A.RBSet.new([1, 2, 1], fn x -> 2 * x end)
#A.RBSet<[2, 4]>

Specs

pop_first(t(val)) :: {val, t(val)} | nil when val: value()

Removes and returns the smallest element in the set.

Returns a {value, new_rb_set} tuple when non-empty, or nil for empty sets.

Examples

iex> rb_set = A.RBSet.new([4, 2, 5, 3])
iex> {2, updated} = A.RBSet.pop_first(rb_set)
iex> updated
#A.RBSet<[3, 4, 5]>
iex> A.RBSet.new() |> A.RBSet.pop_first()
nil

Specs

pop_last(t(val)) :: {val, t(val)} | nil when val: value()

Removes and returns the largest element in the set.

Returns a {value, new_rb_set} tuple when non-empty, or nil for empty sets.

Examples

iex> rb_set = A.RBSet.new([4, 2, 5, 3])
iex> {5, updated} = A.RBSet.pop_last(rb_set)
iex> updated
#A.RBSet<[2, 3, 4]>
iex> A.RBSet.new() |> A.RBSet.pop_last()
nil

Specs

put(t(val), new_val) :: t(val | new_val) when val: value(), new_val: value()

Inserts value into rb_set if rb_set doesn't already contain it.

Examples

iex> A.RBSet.put(A.RBSet.new([1, 2, 3]), 3)
#A.RBSet<[1, 2, 3]>
iex> A.RBSet.put(A.RBSet.new([1, 2, 3]), 4)
#A.RBSet<[1, 2, 3, 4]>

Specs

size(t()) :: non_neg_integer()

Returns the number of elements in rb_set.

Examples

iex> A.RBSet.size(A.RBSet.new([1, 2, 3]))
3
iex> A.RBSet.size(A.RBSet.new([1, 1, 1.0]))
1
Link to this function

subset?(rb_set1, rb_set2)

View Source

Specs

subset?(t(), t()) :: boolean()

Checks if rb_set1's members are all contained in rb_set2.

This function checks if rb_set1 is a subset of rb_set2.

Examples

iex> A.RBSet.subset?(A.RBSet.new([1, 2]), A.RBSet.new([1, 2, 3]))
true
iex> A.RBSet.subset?(A.RBSet.new([1, 2, 3]), A.RBSet.new([1, 2]))
false

Specs

to_list(t(val)) :: [val] when val: value()

Converts rb_set to a list.

Examples

iex> A.RBSet.to_list(A.RBSet.new([1, 2, 3]))
[1, 2, 3]

Specs

union(t(val1), t(val2)) :: t(val1 | val2) when val1: value(), val2: value()

Returns a set containing all members of rb_set1 and rb_set2.

Examples

iex> A.RBSet.union(A.RBSet.new([2, 1]), A.RBSet.new([4, 2, 3]))
#A.RBSet<[1, 2, 3, 4]>