A.RBSet (Aja v0.4.6) 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:
- is a better Elixir citizen: pipe-friendliness,
Enum/Inspect/Collectableprotocols - is more convenient and safer to use: no unsafe functions like
:gb_sets.from_ordset/1 - keeps the tree balanced on deletion unlike
:gb_sets - optionally implements the
Jason.Encoderprotocol ifJasonis installed
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/1andlast/1to efficiently retrieve the first (smallest) / last (largest) elementpop_first/1andpop_last/1to efficiently pop the first (smallest) / last (largest) elementfoldl/3andfoldr/3to 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)
falsePattern-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())
trueNote, 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)
trueErlang'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)
118Link 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
Link to this section Functions
Specs
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]>Specs
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]>Specs
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]))
falseSpecs
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]))
falseSpecs
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)
0Folds (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]Specs
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<[]>Specs
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)
0Specs
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)
falseSpecs
new() :: t()
Returns a new empty set.
Examples
iex> A.RBSet.new()
#A.RBSet<[]>Specs
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]>Specs
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
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()
nilSpecs
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()
nilSpecs
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]))
1Specs
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]))
falseSpecs
Converts rb_set to a list.
Examples
iex> A.RBSet.to_list(A.RBSet.new([1, 2, 3]))
[1, 2, 3]Specs
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]>