%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 1998-2010. 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%
%%
%%
%% Copyright (C) 1991, Ellemtel Telecommunications Systems Laboratories
%% File : ordsets.erl
%% Author : Robert Virding
%% Purpose : Functions for manipulating sets as ordered lists.
%% As yet some of these are not very efficiently written.
-module(ordsets1).
-export([new_set/0,is_set/1,set_to_list/1,list_to_set/1]).
-export([is_element/2,add_element/2,del_element/2]).
-export([union/2,union/1,intersection/2,intersection/1]).
-export([subtract/2,subset/2]).
%% new_set()
%% Return a new empty ordered set.
new_set() ->
[].
%% is_set(Set)
%% Return 'true' if Set is an ordered set of elements, else 'false'.
is_set([E|Es]) ->
is_set(Es, E);
is_set([]) ->
true.
is_set([E2|Es], E1) when E1 < E2 ->
is_set(Es, E2);
is_set([E2|Es], E1) ->
false;
is_set([], E1) ->
true.
%% set_to_list(OrdSet)
%% Return the elements in OrdSet as a list.
set_to_list(S) ->
S.
%% list_to_set(List)
%% Build an ordered set from the elements in List.
list_to_set([E|Es]) ->
add_element(E, list_to_set(Es));
list_to_set([]) ->
[].
%% is_element(Element, OrdSet)
%% Return 'true' if Element is an element of OrdSet, else 'false'.
is_element(E, [H|Es]) when E < H ->
false;
is_element(E, [H|Es]) when E == H ->
true;
is_element(E, [H|Es]) when E > H ->
is_element(E, Es);
is_element(E, []) ->
false.
%% add_element(Element, OrdSet)
%% Return OrdSet with Element inserted in it.
add_element(E, [H|Es]) when E < H ->
[E,H|Es];
add_element(E, [H|Es]) when E == H ->
[H|Es];
add_element(E, [H|Es]) when E > H ->
[H|add_element(E, Es)];
add_element(E, []) ->
[E].
%% del_element(Element, OrdSet)
%% Return OrdSet but with Element removed.
del_element(E, [H|Es]) when E < H ->
[H|Es];
del_element(E, [H|Es]) when E == H ->
Es;
del_element(E, [H|Es]) when E > H ->
[H|del_element(E, Es)];
del_element(E, []) ->
[].
%% union(Set1, Set2)
%% Return the union of Set1 and Set2.
union([H1|Es1], [H2|Es2]) when H1 < H2 ->
[H1|union(Es1, [H2|Es2])];
union([H1|Es1], [H2|Es2]) when H1 == H2 ->
[H1|union(Es1, Es2)];
union([H1|Es1], [H2|Es2]) when H1 > H2 ->
[H2|union([H1|Es1], Es2)];
union([], Es2) ->
Es2;
union(Es1, []) ->
Es1.
%% union(OrdSets)
%% Return the union of the list of sets.
union([S1,S2|Ss]) ->
union1(union(S1,S2), Ss);
union([S]) ->
S;
union([]) ->
[].
union1(S1, [S2|Ss]) ->
union1(union(S1, S2), Ss);
union1(S1, []) ->
S1.
%% intersection(Set1, Set2)
%% Return the intersection of Set1 and Set2.
intersection([H1|Es1], [H2|Es2]) when H1 < H2 ->
intersection(Es1, [H2|Es2]);
intersection([H1|Es1], [H2|Es2]) when H1 == H2 ->
[H1|intersection(Es1, Es2)];
intersection([H1|Es1], [H2|Es2]) when H1 > H2 ->
intersection([H1|Es1], Es2);
intersection([], Es2) ->
[];
intersection(Es1, []) ->
[].
%% intersection(OrdSets)
%% Return the intersection of the list of sets.
intersection([S1,S2|Ss]) ->
intersection1(intersection(S1,S2), Ss);
intersection([S]) ->
S;
intersection([]) ->
[].
intersection1(S1, [S2|Ss]) ->
intersection1(intersection(S1, S2), Ss);
intersection1(S1, []) ->
S1.
%% subtract(Set1, Set2)
%% Return all and only the elements of Set1 which are not also in Set2.
subtract([H1|Es1], [H2|Es2]) when H1 < H2 ->
[H1|subtract(Es1, [H2|Es2])];
subtract([H1|Es1], [H2|Es2]) when H1 == H2 ->
subtract(Es1, Es2);
subtract([H1|Es1], [H2|Es2]) when H1 > H2 ->
subtract([H1|Es1], Es2);
subtract([], Es2) ->
[];
subtract(Es1, []) ->
Es1.
%% subset(Set1, Set2)
%% Return 'true' when every element of Set1 is also a member of Set2,
%% else 'false'.
subset([H1|Es1], [H2|Es2]) when H1 < H2 -> %H1 not in Set2
false;
subset([H1|Es1], [H2|Es2]) when H1 == H2 ->
subset(Es1, Es2);
subset([H1|Es1], [H2|Es2]) when H1 > H2 ->
subset([H1|Es1], Es2);
subset([], Es2) ->
true;
subset(Es1, []) ->
false.
