1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2000-2020. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20
21-module(cerl_sets).
22
23%% Standard interface.
24-export([new/0,is_set/1,size/1,to_list/1,from_list/1]).
25-export([is_element/2,add_element/2,del_element/2]).
26-export([union/2,union/1,intersection/2,intersection/1]).
27-export([is_disjoint/2]).
28-export([subtract/2,is_subset/2]).
29-export([fold/3,filter/2]).
30
31-export_type([set/0, set/1]).
32
33%%------------------------------------------------------------------------------
34
35-type set() :: set(_).
36-opaque set(Element) :: #{Element => 'ok'}.
37
38%%------------------------------------------------------------------------------
39
40%% new() -> Set
41-spec new() -> set().
42
43new() -> #{}.
44
45%% is_set(Set) -> boolean().
46%%  Return 'true' if Set is a set of elements, else 'false'.
47-spec is_set(Set) -> boolean() when
48      Set :: term().
49
50is_set(S) when is_map(S) -> true;
51is_set(_) -> false.
52
53%% size(Set) -> int().
54%%  Return the number of elements in Set.
55-spec size(Set) -> non_neg_integer() when
56      Set :: set().
57
58size(S) -> maps:size(S).
59
60%% to_list(Set) -> [Elem].
61%%  Return the elements in Set as a list.
62-spec to_list(Set) -> List when
63      Set :: set(Element),
64      List :: [Element].
65
66to_list(S) -> maps:keys(S).
67
68%% from_list([Elem]) -> Set.
69%%  Build a set from the elements in List.
70-spec from_list(List) -> Set when
71      List :: [Element],
72      Set :: set(Element).
73from_list(Ls) -> maps:from_list([{K,ok}||K<-Ls]).
74
75%% is_element(Element, Set) -> boolean().
76%%  Return 'true' if Element is an element of Set, else 'false'.
77-spec is_element(Element, Set) -> boolean() when
78      Set :: set(Element).
79
80is_element(E,S) ->
81    case S of
82        #{E := _} -> true;
83        _ -> false
84    end.
85
86%% add_element(Element, Set) -> Set.
87%%  Return Set with Element inserted in it.
88-spec add_element(Element, Set1) -> Set2 when
89      Set1 :: set(Element),
90      Set2 :: set(Element).
91
92add_element(E,S) -> S#{E=>ok}.
93
94-spec del_element(Element, Set1) -> Set2 when
95      Set1 :: set(Element),
96      Set2 :: set(Element).
97
98%% del_element(Element, Set) -> Set.
99%%  Return Set but with Element removed.
100del_element(E,S) -> maps:remove(E,S).
101
102%% union(Set1, Set2) -> Set
103%%  Return the union of Set1 and Set2.
104-spec union(Set1, Set2) -> Set3 when
105      Set1 :: set(Element),
106      Set2 :: set(Element),
107      Set3 :: set(Element).
108
109union(S1,S2) -> maps:merge(S1,S2).
110
111%% union([Set]) -> Set
112%%  Return the union of the list of sets.
113-spec union(SetList) -> Set when
114      SetList :: [set(Element)],
115      Set :: set(Element).
116
117union([S1,S2|Ss]) ->
118    union1(union(S1, S2), Ss);
119union([S]) -> S;
120union([]) -> new().
121
122union1(S1, [S2|Ss]) ->
123    union1(union(S1, S2), Ss);
124union1(S1, []) -> S1.
125
126%% intersection(Set1, Set2) -> Set.
127%%  Return the intersection of Set1 and Set2.
128-spec intersection(Set1, Set2) -> Set3 when
129      Set1 :: set(Element),
130      Set2 :: set(Element),
131      Set3 :: set(Element).
132
133intersection(S1, S2) when map_size(S1) >= map_size(S2) ->
134    filter(fun (E) -> is_element(E, S1) end, S2);
135intersection(S1, S2) ->
136    intersection(S2, S1).
137
138%% intersection([Set]) -> Set.
139%%  Return the intersection of the list of sets.
140-spec intersection(SetList) -> Set when
141      SetList :: [set(Element),...],
142      Set :: set(Element).
143
144intersection([S1,S2|Ss]) ->
145    intersection1(intersection(S1, S2), Ss);
146intersection([S]) -> S.
147
148intersection1(S1, [S2|Ss]) ->
149    intersection1(intersection(S1, S2), Ss);
150intersection1(S1, []) -> S1.
151
152%% is_disjoint(Set1, Set2) -> boolean().
153%%  Check whether Set1 and Set2 are disjoint.
154-spec is_disjoint(Set1, Set2) -> boolean() when
155      Set1 :: set(Element),
156      Set2 :: set(Element).
157
158is_disjoint(S1, S2) when map_size(S1) > map_size(S2) ->
159    is_disjoint_1(S1, maps:iterator(S2));
160is_disjoint(S1, S2) ->
161    is_disjoint_1(S2, maps:iterator(S1)).
162
163is_disjoint_1(Set, Iter) ->
164    case maps:next(Iter) of
165        {K, _, NextIter} ->
166            case Set of
167                #{K := _} -> false;
168                #{} -> is_disjoint_1(Set, NextIter)
169            end;
170        none ->
171            true
172    end.
173
174%% subtract(Set1, Set2) -> Set.
175%%  Return all and only the elements of Set1 which are not also in
176%%  Set2.
177-spec subtract(Set1, Set2) -> Set3 when
178      Set1 :: set(Element),
179      Set2 :: set(Element),
180      Set3 :: set(Element).
181
182subtract(S1, S2) ->
183    filter(fun (E) -> not is_element(E, S2) end, S1).
184
185%% is_subset(Set1, Set2) -> boolean().
186%%  Return 'true' when every element of Set1 is also a member of
187%%  Set2, else 'false'.
188-spec is_subset(Set1, Set2) -> boolean() when
189      Set1 :: set(Element),
190      Set2 :: set(Element).
191
192is_subset(S1, S2) when map_size(S1) > map_size(S2) ->
193    false;
194is_subset(S1, S2) ->
195    is_subset_1(S2, maps:iterator(S1)).
196
197is_subset_1(Set, Iter) ->
198    case maps:next(Iter) of
199        {K, _, NextIter} ->
200            case Set of
201                #{K := _} -> is_subset_1(Set, NextIter);
202                #{} -> false
203            end;
204        none ->
205            true
206    end.
207
208%% fold(Fun, Accumulator, Set) -> Accumulator.
209%%  Fold function Fun over all elements in Set and return Accumulator.
210-spec fold(Function, Acc0, Set) -> Acc1 when
211      Function :: fun((Element, AccIn) -> AccOut),
212      Set :: set(Element),
213      Acc0 :: Acc,
214      Acc1 :: Acc,
215      AccIn :: Acc,
216      AccOut :: Acc.
217
218fold(Fun, Init, Set) ->
219    fold_1(Fun, Init, maps:iterator(Set)).
220
221fold_1(Fun, Acc, Iter) ->
222    case maps:next(Iter) of
223        {K, _, NextIter} ->
224            fold_1(Fun, Fun(K,Acc), NextIter);
225        none ->
226            Acc
227    end.
228
229%% filter(Fun, Set) -> Set.
230%%  Filter Set with Fun.
231-spec filter(Pred, Set1) -> Set2 when
232      Pred :: fun((Element) -> boolean()),
233      Set1 :: set(Element),
234      Set2 :: set(Element).
235
236filter(Fun, Set) ->
237    maps:from_list(filter_1(Fun, maps:iterator(Set))).
238
239filter_1(Fun, Iter) ->
240    case maps:next(Iter) of
241        {K, _, NextIter} ->
242            case Fun(K) of
243                true ->
244                    [{K,ok} | filter_1(Fun, NextIter)];
245                false ->
246                    filter_1(Fun, NextIter)
247            end;
248        none ->
249            []
250    end.
251