aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/compiler/src/Makefile1
-rw-r--r--lib/compiler/src/cerl_sets.erl206
-rw-r--r--lib/compiler/src/compiler.app.src1
3 files changed, 208 insertions, 0 deletions
diff --git a/lib/compiler/src/Makefile b/lib/compiler/src/Makefile
index 7c4cebdc28..78efc8dff0 100644
--- a/lib/compiler/src/Makefile
+++ b/lib/compiler/src/Makefile
@@ -70,6 +70,7 @@ MODULES = \
cerl \
cerl_clauses \
cerl_inline \
+ cerl_sets \
cerl_trees \
compile \
core_lib \
diff --git a/lib/compiler/src/cerl_sets.erl b/lib/compiler/src/cerl_sets.erl
new file mode 100644
index 0000000000..4df78dc432
--- /dev/null
+++ b/lib/compiler/src/cerl_sets.erl
@@ -0,0 +1,206 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2000-2015. 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
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%%
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%%
+%% %CopyrightEnd%
+%%
+
+-module(cerl_sets).
+
+%% Standard interface.
+-export([new/0,is_set/1,size/1,to_list/1,from_list/1]).
+-export([is_element/2,add_element/2,del_element/2]).
+-export([union/2,union/1,intersection/2,intersection/1]).
+-export([is_disjoint/2]).
+-export([subtract/2,is_subset/2]).
+-export([fold/3,filter/2]).
+
+-export_type([set/0, set/1]).
+
+%%------------------------------------------------------------------------------
+
+-type set() :: set(_).
+-opaque set(Element) :: #{Element => 'ok'}.
+
+%%------------------------------------------------------------------------------
+
+%% new() -> Set
+-spec new() -> set().
+
+new() -> #{}.
+
+%% is_set(Set) -> boolean().
+%% Return 'true' if Set is a set of elements, else 'false'.
+-spec is_set(Set) -> boolean() when
+ Set :: term().
+
+is_set(S) when is_map(S) -> true;
+is_set(_) -> false.
+
+%% size(Set) -> int().
+%% Return the number of elements in Set.
+-spec size(Set) -> non_neg_integer() when
+ Set :: set().
+
+size(S) -> maps:size(S).
+
+%% to_list(Set) -> [Elem].
+%% Return the elements in Set as a list.
+-spec to_list(Set) -> List when
+ Set :: set(Element),
+ List :: [Element].
+
+to_list(S) -> maps:keys(S).
+
+%% from_list([Elem]) -> Set.
+%% Build a set from the elements in List.
+-spec from_list(List) -> Set when
+ List :: [Element],
+ Set :: set(Element).
+from_list(Ls) -> maps:from_list([{K,ok}||K<-Ls]).
+
+%% is_element(Element, Set) -> boolean().
+%% Return 'true' if Element is an element of Set, else 'false'.
+-spec is_element(Element, Set) -> boolean() when
+ Set :: set(Element).
+
+is_element(E,S) ->
+ case S of
+ #{E := _} -> true;
+ _ -> false
+ end.
+
+%% add_element(Element, Set) -> Set.
+%% Return Set with Element inserted in it.
+-spec add_element(Element, Set1) -> Set2 when
+ Set1 :: set(Element),
+ Set2 :: set(Element).
+
+add_element(E,S) -> S#{E=>ok}.
+
+-spec del_element(Element, Set1) -> Set2 when
+ Set1 :: set(Element),
+ Set2 :: set(Element).
+
+%% del_element(Element, Set) -> Set.
+%% Return Set but with Element removed.
+del_element(E,S) -> maps:remove(E,S).
+
+%% union(Set1, Set2) -> Set
+%% Return the union of Set1 and Set2.
+-spec union(Set1, Set2) -> Set3 when
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
+
+union(S1,S2) -> maps:merge(S1,S2).
+
+%% union([Set]) -> Set
+%% Return the union of the list of sets.
+-spec union(SetList) -> Set when
+ SetList :: [set(Element)],
+ Set :: set(Element).
+
+union([S1,S2|Ss]) ->
+ union1(union(S1, S2), Ss);
+union([S]) -> S;
+union([]) -> new().
+
+union1(S1, [S2|Ss]) ->
+ union1(union(S1, S2), Ss);
+union1(S1, []) -> S1.
+
+%% intersection(Set1, Set2) -> Set.
+%% Return the intersection of Set1 and Set2.
+-spec intersection(Set1, Set2) -> Set3 when
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
+
+intersection(S1, S2) ->
+ filter(fun (E) -> is_element(E, S1) end, S2).
+
+%% intersection([Set]) -> Set.
+%% Return the intersection of the list of sets.
+-spec intersection(SetList) -> Set when
+ SetList :: [set(Element),...],
+ Set :: set(Element).
+
+intersection([S1,S2|Ss]) ->
+ intersection1(intersection(S1, S2), Ss);
+intersection([S]) -> S.
+
+intersection1(S1, [S2|Ss]) ->
+ intersection1(intersection(S1, S2), Ss);
+intersection1(S1, []) -> S1.
+
+%% is_disjoint(Set1, Set2) -> boolean().
+%% Check whether Set1 and Set2 are disjoint.
+-spec is_disjoint(Set1, Set2) -> boolean() when
+ Set1 :: set(Element),
+ Set2 :: set(Element).
+
+is_disjoint(S1, S2) when map_size(S1) < map_size(S2) ->
+ fold(fun (_, false) -> false;
+ (E, true) -> not is_element(E, S2)
+ end, true, S1);
+is_disjoint(S1, S2) ->
+ fold(fun (_, false) -> false;
+ (E, true) -> not is_element(E, S1)
+ end, true, S2).
+
+%% subtract(Set1, Set2) -> Set.
+%% Return all and only the elements of Set1 which are not also in
+%% Set2.
+-spec subtract(Set1, Set2) -> Set3 when
+ Set1 :: set(Element),
+ Set2 :: set(Element),
+ Set3 :: set(Element).
+
+subtract(S1, S2) ->
+ filter(fun (E) -> not is_element(E, S2) end, S1).
+
+%% is_subset(Set1, Set2) -> boolean().
+%% Return 'true' when every element of Set1 is also a member of
+%% Set2, else 'false'.
+-spec is_subset(Set1, Set2) -> boolean() when
+ Set1 :: set(Element),
+ Set2 :: set(Element).
+
+is_subset(S1, S2) ->
+ fold(fun (E, Sub) -> Sub andalso is_element(E, S2) end, true, S1).
+
+%% fold(Fun, Accumulator, Set) -> Accumulator.
+%% Fold function Fun over all elements in Set and return Accumulator.
+-spec fold(Function, Acc0, Set) -> Acc1 when
+ Function :: fun((Element, AccIn) -> AccOut),
+ Set :: set(Element),
+ Acc0 :: Acc,
+ Acc1 :: Acc,
+ AccIn :: Acc,
+ AccOut :: Acc.
+
+fold(F, Init, D) ->
+ lists:foldl(fun(E,Acc) -> F(E,Acc) end,Init,maps:keys(D)).
+
+%% filter(Fun, Set) -> Set.
+%% Filter Set with Fun.
+-spec filter(Pred, Set1) -> Set2 when
+ Pred :: fun((Element) -> boolean()),
+ Set1 :: set(Element),
+ Set2 :: set(Element).
+
+filter(F, D) ->
+ maps:from_list(lists:filter(fun({K,_}) -> F(K) end, maps:to_list(D))).
diff --git a/lib/compiler/src/compiler.app.src b/lib/compiler/src/compiler.app.src
index 2a40c1c379..3076400f58 100644
--- a/lib/compiler/src/compiler.app.src
+++ b/lib/compiler/src/compiler.app.src
@@ -45,6 +45,7 @@
cerl,
cerl_clauses,
cerl_inline,
+ cerl_sets,
cerl_trees,
compile,
core_scan,
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-18 00:22:18 +0000