xb5_sets (xb5 v1.0.1)

View Source

An ordered set backed by a B-tree of order 5, and a drop-in alternative to gb_sets.

Elements are kept in ascending Erlang term order, and each value appears at most once. Comparisons use == rather than =:= — so 1 and 1.0 are considered the same element.

Conversion to a list via to_list/1 always yields elements in ascending order.

See also

Examples

> S = xb5_sets:from_list([3, 1, 2, 1]).
> xb5_sets:to_list(S).
[1, 2, 3]
> xb5_sets:is_member(2, S).
true
> xb5_sets:largest(S).
3

Summary

Types

iter()

Shorthand for iter(_).

iter(Element)

An iterator over elements of type Element. See iterator/1 and next/1.

set()

Shorthand for set(_).

set(Element)

An ordered set containing elements of type Element.

unwrapped_set(Element)

A plain-map representation of a set, suitable for cross-language serialization (for example, converting to or from an Elixir struct that uses the same underlying node structures).

Functions

add(Element, Set1)

Adds element Element to set Set1, returning a new set Set2. If Element is already a member of Set1, Set1 is returned unchanged.

add_element(Element, Set1)

Equivalent to add/2.

balance(Set1)

Returns Set unchanged.

del_element(Element, Set1)

Equivalent to delete_any/2.

delete(Element, Set1)

Removes element Element from set Set1, returning a new set Set2.

delete_any(Element, Set1)

Removes element Element from set Set1 if present, returning a new set Set2. If Element is not a member, Set1 is returned unchanged.

difference(Set1, Set2)

Returns the elements of Set1 that are not in Set2.

empty()

Equivalent to new/0.

filter(Pred, Set1)

Filters elements of Set1 using predicate function Pred, returning a new set Set2 containing only the elements for which Pred returns true.

filtermap(Fun, Set1)

Filters and maps elements of Set1 using Fun, returning a new set Set2.

fold(Function, Acc0, Set)

Folds Function over every element in Set, returning the final accumulator value. Elements are visited in Erlang term order.

from_list(List)

Returns a set of the elements in List. Duplicate elements are removed.

from_ordset(Ordset)

Returns a set built from the ordered set Ordset.

insert(Element, Set1)

Inserts element Element into set Set1, returning a new set Set2.

intersection(SetList)

Returns the intersection of the non-empty list of sets.

intersection(Set1, Set2)

Returns the intersection of Set1 and Set2.

is_disjoint(Set1, Set2)

Returns true if Set1 and Set2 are disjoint (have no elements in common), otherwise false.

is_element(Element, Set)

Equivalent to is_member/2.

is_empty(Set)

Returns true if Set is empty, otherwise false.

is_equal(Set1, Set2)

Returns true if Set1 and Set2 contain the same elements, otherwise false.

is_member(Element, Set)

Returns true if Element is a member of Set, otherwise false.

is_set(Term)

Returns true if Term appears to be a set, otherwise false.

is_subset(Set1, Set2)

Returns true if every element of Set1 is also a member of Set2, otherwise false.

iterator(Set)

Returns an iterator that can be used for traversing the entries of Set; see next/1. Equivalent to iterator(Set, ordered).

iterator(Set, Order)

Returns an iterator that can be used for traversing the entries of Set in the given Order; see next/1.

iterator_from(Element, Set)

Returns an iterator that can be used for traversing the entries of Set starting from element Element; see next/1. Equivalent to iterator_from(Element, Set, ordered).

iterator_from(Element, Set, Order)

Returns an iterator that can be used for traversing the entries of Set starting from element Element in the given Order; see next/1.

larger(Element1, Set)

Returns {found, Element2} where Element2 is the smallest element in Set that is strictly greater than Element1, or none if no such element exists.

largest(Set)

Returns the largest element in Set. Raises an empty_set error if the set is empty.

map(Fun, Set1)

Maps Fun over all elements of Set1, returning a new set Set2. Duplicates arising from the mapping are removed.

new()

Returns a new empty set.

next(Iter1)

Returns {Element, Iter2} where Element is the next element referred to by iterator Iter1 and Iter2 is the updated iterator, or none if no more elements remain.

singleton(Element)

Returns a set containing only element Element.

size(Set)

Returns the number of elements in Set.

smaller(Element1, Set)

Returns {found, Element2} where Element2 is the largest element in Set that is strictly less than Element1, or none if no such element exists.

smallest(Set)

Returns the smallest element in Set. Raises an empty_set error if the set is empty.

structural_stats(Set)

Returns structural statistics about the B-tree backing Set.

subtract(Set1, Set2)

Equivalent to difference/2.

take_largest(Set1)

Returns {Element, Set2}, where Element is the largest element in Set1 and Set2 is the remaining set. Raises an empty_set error if the set is empty.

take_smallest(Set1)

Returns {Element, Set2}, where Element is the smallest element in Set1 and Set2 is the remaining set. Raises an empty_set error if the set is empty.

to_list(Set)

Returns the elements of Set as an ordered list.

union(SetList)

Returns the union of a list of sets.

union(Set1, Set2)

Returns the union of Set1 and Set2.

unwrap(Term)

Unwraps an opaque set into a plain map representation suitable for cross-language interop (for example, converting to an Elixir struct that uses the same underlying node module). Returns {ok, Unwrapped} on success or {error, Reason} if Term is not a valid set.

wrap/1

Wraps a plain map representation back into an opaque set.

Types

iter()

-type iter() :: iter(_).

Shorthand for iter(_).

iter(Element)

-opaque iter(Element)

An iterator over elements of type Element. See iterator/1 and next/1.

set()

-type set() :: set(_).

Shorthand for set(_).

set(Element)

-opaque set(Element)

An ordered set containing elements of type Element.

unwrapped_set(Element)

-type unwrapped_set(Element) :: #{size := non_neg_integer(), root := xb5_sets_node:t(Element)}.

A plain-map representation of a set, suitable for cross-language serialization (for example, converting to or from an Elixir struct that uses the same underlying node structures).

See unwrap/1 and wrap/1.

Functions

add(Element, Set1)

-spec add(Element, Set1) -> Set2 when Set1 :: set(Element), Set2 :: set(Element).

Adds element Element to set Set1, returning a new set Set2. If Element is already a member of Set1, Set1 is returned unchanged.

Examples

> S0 = xb5_sets:new().
> xb5_sets:to_list(xb5_sets:add(1, S0)).
[1]
> S1 = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:to_list(xb5_sets:add(2, S1)).
[1, 2, 3]
> xb5_sets:to_list(xb5_sets:add(4, S1)).
[1, 2, 3, 4]

add_element(Element, Set1)

-spec add_element(Element, Set1) -> Set2 when Set1 :: set(Element), Set2 :: set(Element).

Equivalent to add/2.

balance(Set1)

-spec balance(Set1) -> Set2 when Set1 :: set(Element), Set2 :: set(Element).

Returns Set unchanged.

This function exists only to ease migration from gb_sets. Since xb5 B-trees are always balanced, calling this function is never necessary.

Examples

> S = xb5_sets:from_list([3, 1, 2]).
> xb5_sets:to_list(xb5_sets:balance(S)).
[1, 2, 3]

del_element(Element, Set1)

-spec del_element(Element, Set1) -> Set2
                     when Element :: term(), Set1 :: set(Element), Set2 :: set(Element).

Equivalent to delete_any/2.

delete(Element, Set1)

-spec delete(Element, Set1) -> Set2 | no_return()
                when Element :: term(), Set1 :: set(Element), Set2 :: set(Element).

Removes element Element from set Set1, returning a new set Set2.

Raises a {badkey, Element} error if Element is not a member of Set1.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:to_list(xb5_sets:delete(2, S)).
[1, 3]

delete_any(Element, Set1)

-spec delete_any(Element, Set1) -> Set2
                    when Element :: term(), Set1 :: set(Element), Set2 :: set(Element).

Removes element Element from set Set1 if present, returning a new set Set2. If Element is not a member, Set1 is returned unchanged.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:to_list(xb5_sets:delete_any(2, S)).
[1, 3]
> xb5_sets:to_list(xb5_sets:delete_any(42, S)).
[1, 2, 3]

difference(Set1, Set2)

-spec difference(Set1, Set2) -> Set3
                    when Set1 :: set(Element), Set2 :: set(Element), Set3 :: set(Element).

Returns the elements of Set1 that are not in Set2.

Examples

> S1 = xb5_sets:from_list([1, 2, 3, 4]).
> S2 = xb5_sets:from_list([2, 4, 5]).
> xb5_sets:to_list(xb5_sets:difference(S1, S2)).
[1, 3]

empty()

-spec empty() -> set(_).

Equivalent to new/0.

filter(Pred, Set1)

-spec filter(Pred, Set1) -> Set2
                when Pred :: fun((Element) -> boolean()), Set1 :: set(Element), Set2 :: set(Element).

Filters elements of Set1 using predicate function Pred, returning a new set Set2 containing only the elements for which Pred returns true.

Examples

> S = xb5_sets:from_list([1, 2, 3, 4, 5]).
> xb5_sets:to_list(xb5_sets:filter(fun(X) -> X > 3 end, S)).
[4, 5]

filtermap(Fun, Set1)

-spec filtermap(Fun, Set1) -> Set2
                   when
                       Fun :: fun((Element1) -> boolean() | {true, Element2}),
                       Set1 :: set(Element1),
                       Set2 :: set(Element1 | Element2).

Filters and maps elements of Set1 using Fun, returning a new set Set2.

For each element, Fun must return either true (keep the element), false (discard it), or {true, NewElement} (replace it with NewElement).

Examples

> S = xb5_sets:from_list([1, 2, 3, 4, 5]).
> xb5_sets:to_list(xb5_sets:filtermap(fun(X) when X rem 2 =:= 0 -> {true, X * 10}; (_) -> false end, S)).
[20, 40]

fold(Function, Acc0, Set)

-spec fold(Function, Acc0, Set) -> Acc1
              when
                  Function :: fun((Element, AccIn) -> AccOut),
                  Acc0 :: Acc,
                  Acc1 :: Acc,
                  AccIn :: Acc,
                  AccOut :: Acc,
                  Set :: set(Element).

Folds Function over every element in Set, returning the final accumulator value. Elements are visited in Erlang term order.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:fold(fun(X, Acc) -> X + Acc end, 0, S).
6

from_list(List)

-spec from_list(List) -> Set when List :: [Element], Set :: set(Element).

Returns a set of the elements in List. Duplicate elements are removed.

It sorts the List and then delegates to from_ordset/1 - see that function for performance characteristics.

Examples

> xb5_sets:to_list(xb5_sets:from_list([3, 1, 2, 1])).
[1, 2, 3]
> xb5_sets:to_list(xb5_sets:from_list([])).
[]

from_ordset(Ordset)

-spec from_ordset(Ordset) -> Set when Ordset :: ordsets:ordset(Element), Set :: set(Element).

Returns a set built from the ordered set Ordset.

The tree is built by recursively splitting the list top-down rather than by sequential insertion, yielding an optimally balanced result without intermediate allocations or element comparisons. This is analogous to gb_sets:from_ordset/1.

Examples

> xb5_sets:to_list(xb5_sets:from_ordset([1, 2, 3])).
[1, 2, 3]

insert(Element, Set1)

-spec insert(Element, Set1) -> Set2 when Set1 :: set(Element), Set2 :: set(Element).

Inserts element Element into set Set1, returning a new set Set2.

Raises a {key_exists, Element} error if Element is already a member of Set1.

Examples

> S0 = xb5_sets:new().
> S1 = xb5_sets:insert(1, S0).
> xb5_sets:to_list(S1).
[1]

intersection(SetList)

-spec intersection(SetList) -> Set when SetList :: [set(Element), ...], Set :: set(Element).

Returns the intersection of the non-empty list of sets.

Examples

> S1 = xb5_sets:from_list([1, 2, 3]).
> S2 = xb5_sets:from_list([2, 3, 4]).
> S3 = xb5_sets:from_list([3, 4, 5]).
> xb5_sets:to_list(xb5_sets:intersection([S1, S2, S3])).
[3]

intersection(Set1, Set2)

-spec intersection(Set1, Set2) -> Set3
                      when Set1 :: set(Element), Set2 :: set(Element), Set3 :: set(Element).

Returns the intersection of Set1 and Set2.

Examples

> S1 = xb5_sets:from_list([1, 2, 3, 4]).
> S2 = xb5_sets:from_list([2, 4, 5, 6]).
> xb5_sets:to_list(xb5_sets:intersection(S1, S2)).
[2, 4]

is_disjoint(Set1, Set2)

-spec is_disjoint(Set1, Set2) -> boolean() when Set1 :: set(Element), Set2 :: set(Element).

Returns true if Set1 and Set2 are disjoint (have no elements in common), otherwise false.

Examples

> S1 = xb5_sets:from_list([1, 2, 3]).
> S2 = xb5_sets:from_list([4, 5, 6]).
> xb5_sets:is_disjoint(S1, S2).
true
> S3 = xb5_sets:from_list([3, 4, 5]).
> xb5_sets:is_disjoint(S1, S3).
false

is_element(Element, Set)

-spec is_element(Element, Set) -> boolean() when Set :: set(Element).

Equivalent to is_member/2.

is_empty(Set)

-spec is_empty(Set) -> boolean() when Set :: set().

Returns true if Set is empty, otherwise false.

Examples

> xb5_sets:is_empty(xb5_sets:new()).
true
> xb5_sets:is_empty(xb5_sets:from_list([1])).
false

is_equal(Set1, Set2)

-spec is_equal(Set1, Set2) -> boolean() when Set1 :: set(), Set2 :: set().

Returns true if Set1 and Set2 contain the same elements, otherwise false.

Examples

> S1 = xb5_sets:from_list([1, 2, 3]).
> S2 = xb5_sets:from_list([3, 1, 2]).
> xb5_sets:is_equal(S1, S2).
true
> S3 = xb5_sets:from_list([1, 2]).
> xb5_sets:is_equal(S1, S3).
false

is_member(Element, Set)

-spec is_member(Element, Set) -> boolean() when Set :: set(Element).

Returns true if Element is a member of Set, otherwise false.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:is_member(2, S).
true
> xb5_sets:is_member(4, S).
false

is_set(Term)

-spec is_set(Term) -> boolean() when Term :: term().

Returns true if Term appears to be a set, otherwise false.

Examples

> xb5_sets:is_set(xb5_sets:new()).
true
> xb5_sets:is_set(xb5_sets:from_list([1, 2])).
true
> xb5_sets:is_set(not_a_set).
false

is_subset(Set1, Set2)

-spec is_subset(Set1, Set2) -> boolean() when Set1 :: set(Element), Set2 :: set(Element).

Returns true if every element of Set1 is also a member of Set2, otherwise false.

Examples

> S1 = xb5_sets:from_list([1, 2]).
> S2 = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:is_subset(S1, S2).
true
> xb5_sets:is_subset(S2, S1).
false

iterator(Set)

-spec iterator(Set) -> Iter when Set :: set(Element), Iter :: iter(Element).

Returns an iterator that can be used for traversing the entries of Set; see next/1. Equivalent to iterator(Set, ordered).

Examples

> S = xb5_sets:from_list([3, 1, 2]).
> I = xb5_sets:iterator(S).
> {1, I2} = xb5_sets:next(I).
> {2, I3} = xb5_sets:next(I2).
> {3, I4} = xb5_sets:next(I3).
> xb5_sets:next(I4).
none

iterator(Set, Order)

-spec iterator(Set, Order) -> Iter
                  when Set :: set(Element), Iter :: iter(Element), Order :: ordered | reversed.

Returns an iterator that can be used for traversing the entries of Set in the given Order; see next/1.

Order must be ordered (ascending) or reversed (descending).

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> I = xb5_sets:iterator(S, reversed).
> {3, I2} = xb5_sets:next(I).
> {2, I3} = xb5_sets:next(I2).
> {1, I4} = xb5_sets:next(I3).
> xb5_sets:next(I4).
none

iterator_from(Element, Set)

-spec iterator_from(Element, Set) -> Iter when Set :: set(Element), Iter :: iter(Element).

Returns an iterator that can be used for traversing the entries of Set starting from element Element; see next/1. Equivalent to iterator_from(Element, Set, ordered).

Examples

> S = xb5_sets:from_list([1, 2, 3, 4, 5]).
> I = xb5_sets:iterator_from(3, S).
> {3, I2} = xb5_sets:next(I).
> {4, I3} = xb5_sets:next(I2).
> {5, I4} = xb5_sets:next(I3).
> xb5_sets:next(I4).
none

iterator_from(Element, Set, Order)

-spec iterator_from(Element, Set, Order) -> Iter
                       when Set :: set(Element), Iter :: iter(Element), Order :: ordered | reversed.

Returns an iterator that can be used for traversing the entries of Set starting from element Element in the given Order; see next/1.

Examples

> S = xb5_sets:from_list([1, 2, 3, 4, 5]).
> I = xb5_sets:iterator_from(3, S, reversed).
> {3, I2} = xb5_sets:next(I).
> {2, I3} = xb5_sets:next(I2).
> {1, I4} = xb5_sets:next(I3).
> xb5_sets:next(I4).
none

larger(Element1, Set)

-spec larger(Element1, Set) -> none | {found, Element2}
                when Element1 :: Element, Element2 :: Element, Set :: set(Element).

Returns {found, Element2} where Element2 is the smallest element in Set that is strictly greater than Element1, or none if no such element exists.

Examples

> S = xb5_sets:from_list([1, 3, 5]).
> xb5_sets:larger(2, S).
{found, 3}
> xb5_sets:larger(5, S).
none

largest(Set)

-spec largest(Set) -> Element when Set :: set(Element).

Returns the largest element in Set. Raises an empty_set error if the set is empty.

Examples

> xb5_sets:largest(xb5_sets:from_list([1, 2, 3])).
3

map(Fun, Set1)

-spec map(Fun, Set1) -> Set2
             when Fun :: fun((Element1) -> Element2), Set1 :: set(Element1), Set2 :: set(Element2).

Maps Fun over all elements of Set1, returning a new set Set2. Duplicates arising from the mapping are removed.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> xb5_sets:to_list(xb5_sets:map(fun(X) -> X * 10 end, S)).
[10, 20, 30]

new()

-spec new() -> Set when Set :: set(_).

Returns a new empty set.

Examples

> xb5_sets:is_empty(xb5_sets:new()).
true
> xb5_sets:size(xb5_sets:new()).
0

next(Iter1)

-spec next(Iter1) -> {Element, Iter2} | none when Iter1 :: iter(Element), Iter2 :: iter(Element).

Returns {Element, Iter2} where Element is the next element referred to by iterator Iter1 and Iter2 is the updated iterator, or none if no more elements remain.

Examples

> S = xb5_sets:from_list([1, 2]).
> I = xb5_sets:iterator(S).
> {1, I2} = xb5_sets:next(I).
> {2, I3} = xb5_sets:next(I2).
> xb5_sets:next(I3).
none

singleton(Element)

-spec singleton(Element) -> set(Element).

Returns a set containing only element Element.

Examples

> xb5_sets:to_list(xb5_sets:singleton(42)).
[42]
> xb5_sets:size(xb5_sets:singleton(42)).
1

size(Set)

-spec size(Set) -> non_neg_integer() when Set :: set().

Returns the number of elements in Set.

Examples

> xb5_sets:size(xb5_sets:new()).
0
> xb5_sets:size(xb5_sets:from_list([1, 2, 3])).
3

smaller(Element1, Set)

-spec smaller(Element1, Set) -> none | {found, Element2}
                 when Element1 :: Element, Element2 :: Element, Set :: set(Element).

Returns {found, Element2} where Element2 is the largest element in Set that is strictly less than Element1, or none if no such element exists.

Examples

> S = xb5_sets:from_list([1, 3, 5]).
> xb5_sets:smaller(4, S).
{found, 3}
> xb5_sets:smaller(1, S).
none

smallest(Set)

-spec smallest(Set) -> Element when Set :: set(Element).

Returns the smallest element in Set. Raises an empty_set error if the set is empty.

Examples

> xb5_sets:smallest(xb5_sets:from_list([3, 1, 2])).
1

structural_stats(Set)

-spec structural_stats(Set) -> Stats when Set :: set(), Stats :: xb5_structural_stats:t().

Returns structural statistics about the B-tree backing Set.

This is primarily intended for debugging and testing. The result is a proplist with keys such as height, total_keys, node_counts, node_percentages, and others.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> Stats = xb5_sets:structural_stats(S).
> {height, 1} = lists:keyfind(height, 1, Stats).
> {total_keys, 3} = lists:keyfind(total_keys, 1, Stats).

subtract(Set1, Set2)

-spec subtract(Set1, Set2) -> Set3 when Set1 :: set(Element), Set2 :: set(Element), Set3 :: set(Element).

Equivalent to difference/2.

take_largest(Set1)

-spec take_largest(Set1) -> {Element, Set2} when Set1 :: set(Element), Set2 :: set(Element).

Returns {Element, Set2}, where Element is the largest element in Set1 and Set2 is the remaining set. Raises an empty_set error if the set is empty.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> {3, S2} = xb5_sets:take_largest(S).
> xb5_sets:to_list(S2).
[1, 2]

take_smallest(Set1)

-spec take_smallest(Set1) -> {Element, Set2} when Set1 :: set(Element), Set2 :: set(Element).

Returns {Element, Set2}, where Element is the smallest element in Set1 and Set2 is the remaining set. Raises an empty_set error if the set is empty.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> {1, S2} = xb5_sets:take_smallest(S).
> xb5_sets:to_list(S2).
[2, 3]

to_list(Set)

-spec to_list(Set) -> List when Set :: set(Element), List :: [Element].

Returns the elements of Set as an ordered list.

Examples

> xb5_sets:to_list(xb5_sets:from_list([3, 1, 2])).
[1, 2, 3]
> xb5_sets:to_list(xb5_sets:new()).
[]

union(SetList)

-spec union(SetList) -> Set when SetList :: [set(Element)], Set :: set(Element).

Returns the union of a list of sets.

Examples

> S1 = xb5_sets:from_list([1, 2]).
> S2 = xb5_sets:from_list([2, 3]).
> S3 = xb5_sets:from_list([3, 4]).
> xb5_sets:to_list(xb5_sets:union([S1, S2, S3])).
[1, 2, 3, 4]
> xb5_sets:to_list(xb5_sets:union([])).
[]

union(Set1, Set2)

-spec union(Set1, Set2) -> Set3 when Set1 :: set(Element), Set2 :: set(Element), Set3 :: set(Element).

Returns the union of Set1 and Set2.

Examples

> S1 = xb5_sets:from_list([1, 2, 3]).
> S2 = xb5_sets:from_list([3, 4, 5]).
> xb5_sets:to_list(xb5_sets:union(S1, S2)).
[1, 2, 3, 4, 5]

unwrap(Term)

-spec unwrap(Term) -> {ok, Unwrapped} | {error, Reason}
                when
                    Term :: set(Element) | term(), Unwrapped :: unwrapped_set(Element), Reason :: term().

Unwraps an opaque set into a plain map representation suitable for cross-language interop (for example, converting to an Elixir struct that uses the same underlying node module). Returns {ok, Unwrapped} on success or {error, Reason} if Term is not a valid set.

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> {ok, Unwrapped} = xb5_sets:unwrap(S).
> maps:get(size, Unwrapped).
3
> {error, _} = xb5_sets:unwrap(not_a_set).

wrap/1

-spec wrap(unwrapped_set(Element)) -> set(Element).

Wraps a plain map representation back into an opaque set.

This is the inverse of unwrap/1 and is intended for cross-language interop (for example, converting from an Elixir struct that shares the same underlying node module).

Examples

> S = xb5_sets:from_list([1, 2, 3]).
> {ok, U} = xb5_sets:unwrap(S).
> S2 = xb5_sets:wrap(U).
> xb5_sets:to_list(S2).
[1, 2, 3]