aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/src/gb_sets.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/stdlib/src/gb_sets.erl')
-rw-r--r--lib/stdlib/src/gb_sets.erl147
1 files changed, 113 insertions, 34 deletions
diff --git a/lib/stdlib/src/gb_sets.erl b/lib/stdlib/src/gb_sets.erl
index fc5beb28b0..91d21d869c 100644
--- a/lib/stdlib/src/gb_sets.erl
+++ b/lib/stdlib/src/gb_sets.erl
@@ -197,6 +197,7 @@
%% Some types.
-type gb_set_node() :: 'nil' | {term(), _, _}.
+-opaque iter() :: [gb_set_node()].
%% A declaration equivalent to the following is currently hard-coded
%% in erl_types.erl
@@ -205,38 +206,47 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
--spec empty() -> gb_set().
+-spec empty() -> Set when
+ Set :: gb_set().
empty() ->
{0, nil}.
--spec new() -> gb_set().
+-spec new() -> Set when
+ Set :: gb_set().
new() -> empty().
--spec is_empty(gb_set()) -> boolean().
+-spec is_empty(Set) -> boolean() when
+ Set :: gb_set().
is_empty({0, nil}) ->
true;
is_empty(_) ->
false.
--spec size(gb_set()) -> non_neg_integer().
+-spec size(Set) -> non_neg_integer() when
+ Set :: gb_set().
size({Size, _}) ->
Size.
--spec singleton(term()) -> gb_set().
+-spec singleton(Element) -> gb_set() when
+ Element :: term().
singleton(Key) ->
{1, {Key, nil, nil}}.
--spec is_element(term(), gb_set()) -> boolean().
+-spec is_element(Element, Set) -> boolean() when
+ Element :: term(),
+ Set :: gb_set().
is_element(Key, S) ->
is_member(Key, S).
--spec is_member(term(), gb_set()) -> boolean().
+-spec is_member(Element, Set) -> boolean() when
+ Element :: term(),
+ Set :: gb_set().
is_member(Key, {_, T}) ->
is_member_1(Key, T).
@@ -250,7 +260,10 @@ is_member_1(_, {_, _, _}) ->
is_member_1(_, nil) ->
false.
--spec insert(term(), gb_set()) -> gb_set().
+-spec insert(Element, Set1) -> Set2 when
+ Element :: term(),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
insert(Key, {S, T}) ->
S1 = S + 1,
@@ -306,7 +319,9 @@ count({_, Sm, Bi}) ->
count(nil) ->
{1, 0}.
--spec balance(gb_set()) -> gb_set().
+-spec balance(Set1) -> Set2 when
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
balance({S, T}) ->
{S, balance(T, S)}.
@@ -331,12 +346,18 @@ balance_list_1([Key | L], 1) ->
balance_list_1(L, 0) ->
{nil, L}.
--spec add_element(term(), gb_set()) -> gb_set().
+-spec add_element(Element, Set1) -> Set2 when
+ Element :: term(),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
add_element(X, S) ->
add(X, S).
--spec add(term(), gb_set()) -> gb_set().
+-spec add(Element, Set1) -> Set2 when
+ Element :: term(),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
add(X, S) ->
case is_member(X, S) of
@@ -346,23 +367,33 @@ add(X, S) ->
insert(X, S)
end.
--spec from_list([term()]) -> gb_set().
+-spec from_list(List) -> Set when
+ List :: [term()],
+ Set :: gb_set().
from_list(L) ->
from_ordset(ordsets:from_list(L)).
--spec from_ordset([term()]) -> gb_set().
+-spec from_ordset(List) -> Set when
+ List :: [term()],
+ Set :: gb_set().
from_ordset(L) ->
S = length(L),
{S, balance_list(L, S)}.
--spec del_element(term(), gb_set()) -> gb_set().
+-spec del_element(Element, Set1) -> Set2 when
+ Element :: term(),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
del_element(Key, S) ->
delete_any(Key, S).
--spec delete_any(term(), gb_set()) -> gb_set().
+-spec delete_any(Element, Set1) -> Set2 when
+ Element :: term(),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
delete_any(Key, S) ->
case is_member(Key, S) of
@@ -372,7 +403,10 @@ delete_any(Key, S) ->
S
end.
--spec delete(term(), gb_set()) -> gb_set().
+-spec delete(Element, Set1) -> Set2 when
+ Element :: term(),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
delete(Key, {S, T}) ->
{S - 1, delete_1(Key, T)}.
@@ -394,7 +428,10 @@ merge(Smaller, Larger) ->
{Key, Larger1} = take_smallest1(Larger),
{Key, Smaller, Larger1}.
--spec take_smallest(gb_set()) -> {term(), gb_set()}.
+-spec take_smallest(Set1) -> {Element, Set2} when
+ Set1 :: gb_set(),
+ Set2 :: gb_set(),
+ Element :: term().
take_smallest({S, T}) ->
{Key, Larger} = take_smallest1(T),
@@ -406,7 +443,8 @@ take_smallest1({Key, Smaller, Larger}) ->
{Key1, Smaller1} = take_smallest1(Smaller),
{Key1, {Key, Smaller1, Larger}}.
--spec smallest(gb_set()) -> term().
+-spec smallest(Set) -> term() when
+ Set :: gb_set().
smallest({_, T}) ->
smallest_1(T).
@@ -416,7 +454,10 @@ smallest_1({Key, nil, _Larger}) ->
smallest_1({_Key, Smaller, _Larger}) ->
smallest_1(Smaller).
--spec take_largest(gb_set()) -> {term(), gb_set()}.
+-spec take_largest(Set1) -> {Element, Set2} when
+ Set1 :: gb_set(),
+ Set2 :: gb_set(),
+ Element :: term().
take_largest({S, T}) ->
{Key, Smaller} = take_largest1(T),
@@ -428,7 +469,8 @@ take_largest1({Key, Smaller, Larger}) ->
{Key1, Larger1} = take_largest1(Larger),
{Key1, {Key, Smaller, Larger1}}.
--spec largest(gb_set()) -> term().
+-spec largest(Set) -> term() when
+ Set :: gb_set().
largest({_, T}) ->
largest_1(T).
@@ -438,7 +480,9 @@ largest_1({Key, _Smaller, nil}) ->
largest_1({_Key, _Smaller, Larger}) ->
largest_1(Larger).
--spec to_list(gb_set()) -> [term()].
+-spec to_list(Set) -> List when
+ Set :: gb_set(),
+ List :: [term()].
to_list({_, T}) ->
to_list(T, []).
@@ -449,7 +493,9 @@ to_list({Key, Small, Big}, L) ->
to_list(Small, [Key | to_list(Big, L)]);
to_list(nil, L) -> L.
--spec iterator(gb_set()) -> [term()].
+-spec iterator(Set) -> Iter when
+ Set :: gb_set(),
+ Iter :: iter().
iterator({_, T}) ->
iterator(T, []).
@@ -464,7 +510,10 @@ iterator({_, L, _} = T, As) ->
iterator(nil, As) ->
As.
--spec next([term()]) -> {term(), [term()]} | 'none'.
+-spec next(Iter1) -> {Element, Iter2} | 'none' when
+ Iter1 :: iter(),
+ Iter2 :: iter(),
+ Element :: term().
next([{X, _, T} | As]) ->
{X, iterator(T, As)};
@@ -494,7 +543,10 @@ next([]) ->
%% traversing the elements can be devised, but they all have higher
%% overhead.
--spec union(gb_set(), gb_set()) -> gb_set().
+-spec union(Set1, Set2) -> Set3 when
+ Set1 :: gb_set(),
+ Set2 :: gb_set(),
+ Set3 :: gb_set().
union({N1, T1}, {N2, T2}) when N2 < N1 ->
union(to_list_1(T2), N2, T1, N1);
@@ -596,7 +648,9 @@ balance_revlist_1([Key | L], 1) ->
balance_revlist_1(L, 0) ->
{nil, L}.
--spec union([gb_set()]) -> gb_set().
+-spec union(SetList) -> Set when
+ SetList :: [gb_set(),...],
+ Set :: gb_set().
union([S | Ss]) ->
union_list(S, Ss);
@@ -609,7 +663,10 @@ union_list(S, []) -> S.
%% The rest is modelled on the above.
--spec intersection(gb_set(), gb_set()) -> gb_set().
+-spec intersection(Set1, Set2) -> Set3 when
+ Set1 :: gb_set(),
+ Set2 :: gb_set(),
+ Set3 :: gb_set().
intersection({N1, T1}, {N2, T2}) when N2 < N1 ->
intersection(to_list_1(T2), N2, T1, N1);
@@ -657,7 +714,9 @@ intersection_2([], _, As, S) ->
intersection_2(_, [], As, S) ->
{S, balance_revlist(As, S)}.
--spec intersection([gb_set(),...]) -> gb_set().
+-spec intersection(SetList) -> Set when
+ SetList :: [gb_set(),...],
+ Set :: gb_set().
intersection([S | Ss]) ->
intersection_list(S, Ss).
@@ -666,7 +725,9 @@ intersection_list(S, [S1 | Ss]) ->
intersection_list(intersection(S, S1), Ss);
intersection_list(S, []) -> S.
--spec is_disjoint(gb_set(), gb_set()) -> boolean().
+-spec is_disjoint(Set1, Set2) -> boolean() when
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
is_disjoint({N1, T1}, {N2, T2}) when N1 < N2 ->
is_disjoint_1(T1, T2);
@@ -694,12 +755,18 @@ is_disjoint_1(_, nil) ->
%% the sets. Therefore, we always build a new tree, and thus we need to
%% traverse the whole element list of the left operand.
--spec subtract(gb_set(), gb_set()) -> gb_set().
+-spec subtract(Set1, Set2) -> Set3 when
+ Set1 :: gb_set(),
+ Set2 :: gb_set(),
+ Set3 :: gb_set().
subtract(S1, S2) ->
difference(S1, S2).
--spec difference(gb_set(), gb_set()) -> gb_set().
+-spec difference(Set1, Set2) -> Set3 when
+ Set1 :: gb_set(),
+ Set2 :: gb_set(),
+ Set3 :: gb_set().
difference({N1, T1}, {N2, T2}) ->
difference(to_list_1(T1), N1, T2, N2).
@@ -747,7 +814,9 @@ difference_2(Xs, [], As, S) ->
%% Subset testing is much the same thing as set difference, but
%% without the construction of a new set.
--spec is_subset(gb_set(), gb_set()) -> boolean().
+-spec is_subset(Set1, Set2) -> boolean() when
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
is_subset({N1, T1}, {N2, T2}) ->
is_subset(to_list_1(T1), N1, T2, N2).
@@ -788,18 +857,28 @@ is_subset_2(_, []) ->
%% For compatibility with `sets':
--spec is_set(term()) -> boolean().
+-spec is_set(Term) -> boolean() when
+ Term :: term().
is_set({0, nil}) -> true;
is_set({N, {_, _, _}}) when is_integer(N), N >= 0 -> true;
is_set(_) -> false.
--spec filter(fun((term()) -> boolean()), gb_set()) -> gb_set().
+-spec filter(Pred, Set1) -> Set2 when
+ Pred :: fun((E :: term()) -> boolean()),
+ Set1 :: gb_set(),
+ Set2 :: gb_set().
filter(F, S) ->
from_ordset([X || X <- to_list(S), F(X)]).
--spec fold(fun((term(), term()) -> term()), term(), gb_set()) -> term().
+-spec fold(Function, Acc0, Set) -> Acc1 when
+ Function :: fun((E :: term(), AccIn) -> AccOut),
+ Acc0 :: term(),
+ Acc1 :: term(),
+ AccIn :: term(),
+ AccOut :: term(),
+ Set :: gb_set().
fold(F, A, {_, T}) when is_function(F, 2) ->
fold_1(F, A, T).
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-02 12:43:52 +0000