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.erl168
1 files changed, 78 insertions, 90 deletions
diff --git a/lib/stdlib/src/gb_sets.erl b/lib/stdlib/src/gb_sets.erl
index ba35a7170a..0a26d0182d 100644
--- a/lib/stdlib/src/gb_sets.erl
+++ b/lib/stdlib/src/gb_sets.erl
@@ -1,8 +1,7 @@
-%% -*- coding: utf-8 -*-
%%
%% %CopyrightBegin%
%%
-%% Copyright Ericsson AB 2001-2012. All Rights Reserved.
+%% Copyright Ericsson AB 2001-2014. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
@@ -197,31 +196,32 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Some types.
--export_type([iter/0]).
+-export_type([set/0, set/1, iter/0, iter/1]).
--type gb_set_node() :: 'nil' | {term(), _, _}.
+-type gb_set_node(Element) :: 'nil' | {Element, _, _}.
+-type gb_set_node() :: gb_set_node(_).
+-opaque set(Element) :: {non_neg_integer(), gb_set_node(Element)}.
+-opaque set() :: set(_).
+-opaque iter(Element) :: [gb_set_node(Element)].
-opaque iter() :: [gb_set_node()].
-%% A declaration equivalent to the following is currently hard-coded
-%% in erl_types.erl
-%%
-%% -opaque gb_set() :: {non_neg_integer(), gb_set_node()}.
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%% gb_sets:set() in OTP 17 only.
+
-spec empty() -> Set when
- Set :: gb_set().
+ Set :: gb_sets:set().
empty() ->
{0, nil}.
-spec new() -> Set when
- Set :: gb_set().
+ Set :: gb_sets:set().
new() -> empty().
-spec is_empty(Set) -> boolean() when
- Set :: gb_set().
+ Set :: gb_sets:set().
is_empty({0, nil}) ->
true;
@@ -229,27 +229,24 @@ is_empty(_) ->
false.
-spec size(Set) -> non_neg_integer() when
- Set :: gb_set().
+ Set :: gb_sets:set().
size({Size, _}) ->
Size.
--spec singleton(Element) -> gb_set() when
- Element :: term().
+-spec singleton(Element) -> set(Element).
singleton(Key) ->
{1, {Key, nil, nil}}.
-spec is_element(Element, Set) -> boolean() when
- Element :: term(),
- Set :: gb_set().
+ Set :: set(Element).
is_element(Key, S) ->
is_member(Key, S).
-spec is_member(Element, Set) -> boolean() when
- Element :: term(),
- Set :: gb_set().
+ Set :: set(Element).
is_member(Key, {_, T}) ->
is_member_1(Key, T).
@@ -264,9 +261,8 @@ is_member_1(_, nil) ->
false.
-spec insert(Element, Set1) -> Set2 when
- Element :: term(),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
insert(Key, {S, T}) ->
S1 = S + 1,
@@ -323,8 +319,8 @@ count(nil) ->
{1, 0}.
-spec balance(Set1) -> Set2 when
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
balance({S, T}) ->
{S, balance(T, S)}.
@@ -350,17 +346,15 @@ balance_list_1(L, 0) ->
{nil, L}.
-spec add_element(Element, Set1) -> Set2 when
- Element :: term(),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
add_element(X, S) ->
add(X, S).
-spec add(Element, Set1) -> Set2 when
- Element :: term(),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
add(X, S) ->
case is_member(X, S) of
@@ -371,32 +365,30 @@ add(X, S) ->
end.
-spec from_list(List) -> Set when
- List :: [term()],
- Set :: gb_set().
+ List :: [Element],
+ Set :: set(Element).
from_list(L) ->
from_ordset(ordsets:from_list(L)).
-spec from_ordset(List) -> Set when
- List :: [term()],
- Set :: gb_set().
+ List :: [Element],
+ Set :: set(Element).
from_ordset(L) ->
S = length(L),
{S, balance_list(L, S)}.
-spec del_element(Element, Set1) -> Set2 when
- Element :: term(),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
del_element(Key, S) ->
delete_any(Key, S).
-spec delete_any(Element, Set1) -> Set2 when
- Element :: term(),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
delete_any(Key, S) ->
case is_member(Key, S) of
@@ -407,9 +399,8 @@ delete_any(Key, S) ->
end.
-spec delete(Element, Set1) -> Set2 when
- Element :: term(),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
delete(Key, {S, T}) ->
{S - 1, delete_1(Key, T)}.
@@ -432,9 +423,8 @@ merge(Smaller, Larger) ->
{Key, Smaller, Larger1}.
-spec take_smallest(Set1) -> {Element, Set2} when
- Set1 :: gb_set(),
- Set2 :: gb_set(),
- Element :: term().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
take_smallest({S, T}) ->
{Key, Larger} = take_smallest1(T),
@@ -446,8 +436,8 @@ take_smallest1({Key, Smaller, Larger}) ->
{Key1, Smaller1} = take_smallest1(Smaller),
{Key1, {Key, Smaller1, Larger}}.
--spec smallest(Set) -> term() when
- Set :: gb_set().
+-spec smallest(Set) -> Element when
+ Set :: set(Element).
smallest({_, T}) ->
smallest_1(T).
@@ -458,9 +448,8 @@ smallest_1({_Key, Smaller, _Larger}) ->
smallest_1(Smaller).
-spec take_largest(Set1) -> {Element, Set2} when
- Set1 :: gb_set(),
- Set2 :: gb_set(),
- Element :: term().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
take_largest({S, T}) ->
{Key, Smaller} = take_largest1(T),
@@ -472,8 +461,8 @@ take_largest1({Key, Smaller, Larger}) ->
{Key1, Larger1} = take_largest1(Larger),
{Key1, {Key, Smaller, Larger1}}.
--spec largest(Set) -> term() when
- Set :: gb_set().
+-spec largest(Set) -> Element when
+ Set :: set(Element).
largest({_, T}) ->
largest_1(T).
@@ -484,8 +473,8 @@ largest_1({_Key, _Smaller, Larger}) ->
largest_1(Larger).
-spec to_list(Set) -> List when
- Set :: gb_set(),
- List :: [term()].
+ Set :: set(Element),
+ List :: [Element].
to_list({_, T}) ->
to_list(T, []).
@@ -497,8 +486,8 @@ to_list({Key, Small, Big}, L) ->
to_list(nil, L) -> L.
-spec iterator(Set) -> Iter when
- Set :: gb_set(),
- Iter :: iter().
+ Set :: set(Element),
+ Iter :: iter(Element).
iterator({_, T}) ->
iterator(T, []).
@@ -514,9 +503,8 @@ iterator(nil, As) ->
As.
-spec next(Iter1) -> {Element, Iter2} | 'none' when
- Iter1 :: iter(),
- Iter2 :: iter(),
- Element :: term().
+ Iter1 :: iter(Element),
+ Iter2 :: iter(Element).
next([{X, _, T} | As]) ->
{X, iterator(T, As)};
@@ -547,9 +535,9 @@ next([]) ->
%% overhead.
-spec union(Set1, Set2) -> Set3 when
- Set1 :: gb_set(),
- Set2 :: gb_set(),
- Set3 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
union({N1, T1}, {N2, T2}) when N2 < N1 ->
union(to_list_1(T2), N2, T1, N1);
@@ -571,7 +559,7 @@ union(L, N1, T2, N2) ->
union_1(L, mk_set(N2, T2))
end.
--spec mk_set(non_neg_integer(), gb_set_node()) -> gb_set().
+-spec mk_set(non_neg_integer(), gb_set_node(T)) -> set(T).
mk_set(N, T) ->
{N, T}.
@@ -652,8 +640,8 @@ balance_revlist_1(L, 0) ->
{nil, L}.
-spec union(SetList) -> Set when
- SetList :: [gb_set(),...],
- Set :: gb_set().
+ SetList :: [set(Element),...],
+ Set :: set(Element).
union([S | Ss]) ->
union_list(S, Ss);
@@ -667,9 +655,9 @@ union_list(S, []) -> S.
%% The rest is modelled on the above.
-spec intersection(Set1, Set2) -> Set3 when
- Set1 :: gb_set(),
- Set2 :: gb_set(),
- Set3 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
intersection({N1, T1}, {N2, T2}) when N2 < N1 ->
intersection(to_list_1(T2), N2, T1, N1);
@@ -718,8 +706,8 @@ intersection_2(_, [], As, S) ->
{S, balance_revlist(As, S)}.
-spec intersection(SetList) -> Set when
- SetList :: [gb_set(),...],
- Set :: gb_set().
+ SetList :: [set(Element),...],
+ Set :: set(Element).
intersection([S | Ss]) ->
intersection_list(S, Ss).
@@ -729,8 +717,8 @@ intersection_list(S, [S1 | Ss]) ->
intersection_list(S, []) -> S.
-spec is_disjoint(Set1, Set2) -> boolean() when
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
is_disjoint({N1, T1}, {N2, T2}) when N1 < N2 ->
is_disjoint_1(T1, T2);
@@ -759,17 +747,17 @@ is_disjoint_1(_, nil) ->
%% traverse the whole element list of the left operand.
-spec subtract(Set1, Set2) -> Set3 when
- Set1 :: gb_set(),
- Set2 :: gb_set(),
- Set3 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
subtract(S1, S2) ->
difference(S1, S2).
-spec difference(Set1, Set2) -> Set3 when
- Set1 :: gb_set(),
- Set2 :: gb_set(),
- Set3 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
difference({N1, T1}, {N2, T2}) ->
difference(to_list_1(T1), N1, T2, N2).
@@ -818,8 +806,8 @@ difference_2(Xs, [], As, S) ->
%% without the construction of a new set.
-spec is_subset(Set1, Set2) -> boolean() when
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Set1 :: set(Element),
+ Set2 :: set(Element).
is_subset({N1, T1}, {N2, T2}) ->
is_subset(to_list_1(T1), N1, T2, N2).
@@ -868,20 +856,20 @@ is_set({N, {_, _, _}}) when is_integer(N), N >= 0 -> true;
is_set(_) -> false.
-spec filter(Pred, Set1) -> Set2 when
- Pred :: fun((E :: term()) -> boolean()),
- Set1 :: gb_set(),
- Set2 :: gb_set().
+ Pred :: fun((Element) -> boolean()),
+ Set1 :: set(Element),
+ Set2 :: set(Element).
filter(F, S) ->
from_ordset([X || X <- to_list(S), F(X)]).
-spec fold(Function, Acc0, Set) -> Acc1 when
- Function :: fun((E :: term(), AccIn) -> AccOut),
- Acc0 :: term(),
- Acc1 :: term(),
- AccIn :: term(),
- AccOut :: term(),
- Set :: gb_set().
+ Function :: fun((Element, AccIn) -> AccOut),
+ Acc0 :: Acc,
+ Acc1 :: Acc,
+ AccIn :: Acc,
+ AccOut :: Acc,
+ Set :: set(Element).
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-23 07:02:37 +0000