diff options
Diffstat (limited to 'lib/stdlib/src/ordsets.erl')
| -rw-r--r-- | lib/stdlib/src/ordsets.erl | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/lib/stdlib/src/ordsets.erl b/lib/stdlib/src/ordsets.erl new file mode 100644 index 0000000000..05041c15f1 --- /dev/null +++ b/lib/stdlib/src/ordsets.erl @@ -0,0 +1,220 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 1996-2009. 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(ordsets). + +-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]). + +-type ordset(T) :: [T]. + +%% new() -> Set. +%% Return a new empty ordered set. + +-spec new() -> ordset(term()). + +new() -> []. + +%% is_set(Term) -> boolean(). +%% Return 'true' if Set is an ordered set of elements, else 'false'. + +-spec is_set(term()) -> boolean(). + +is_set([E|Es]) -> is_set(Es, E); +is_set([]) -> true; +is_set(_) -> false. + +is_set([E2|Es], E1) when E1 < E2 -> + is_set(Es, E2); +is_set([_|_], _) -> false; +is_set([], _) -> true. + +%% size(OrdSet) -> int(). +%% Return the number of elements in OrdSet. + +-spec size(ordset(_)) -> non_neg_integer(). + +size(S) -> length(S). + +%% to_list(OrdSet) -> [Elem]. +%% Return the elements in OrdSet as a list. + +-spec to_list(ordset(T)) -> [T]. + +to_list(S) -> S. + +%% from_list([Elem]) -> Set. +%% Build an ordered set from the elements in List. + +-spec from_list([T]) -> ordset(T). + +from_list(L) -> + lists:usort(L). + +%% is_element(Element, OrdSet) -> boolean(). +%% Return 'true' if Element is an element of OrdSet, else 'false'. + +-spec is_element(term(), ordset(_)) -> boolean(). + +is_element(E, [H|Es]) when E > H -> is_element(E, Es); +is_element(E, [H|_]) when E < H -> false; +is_element(_E, [_H|_]) -> true; %E == H +is_element(_, []) -> false. + +%% add_element(Element, OrdSet) -> OrdSet. +%% Return OrdSet with Element inserted in it. + +-spec add_element(term(), ordset(_)) -> ordset(_). + +add_element(E, [H|Es]) when E > H -> [H|add_element(E, Es)]; +add_element(E, [H|_]=Set) when E < H -> [E|Set]; +add_element(_E, [_H|_]=Set) -> Set; %E == H +add_element(E, []) -> [E]. + +%% del_element(Element, OrdSet) -> OrdSet. +%% Return OrdSet but with Element removed. + +-spec del_element(term(), ordset(_)) -> ordset(_). + +del_element(E, [H|Es]) when E > H -> [H|del_element(E, Es)]; +del_element(E, [H|_]=Set) when E < H -> Set; +del_element(_E, [_H|Es]) -> Es; %E == H +del_element(_, []) -> []. + +%% union(OrdSet1, OrdSet2) -> OrdSet +%% Return the union of OrdSet1 and OrdSet2. + +-spec union(ordset(_), ordset(_)) -> ordset(_). + +union([E1|Es1], [E2|_]=Set2) when E1 < E2 -> + [E1|union(Es1, Set2)]; +union([E1|_]=Set1, [E2|Es2]) when E1 > E2 -> + [E2|union(Es2, Set1)]; % switch arguments! +union([E1|Es1], [_E2|Es2]) -> %E1 == E2 + [E1|union(Es1, Es2)]; +union([], Es2) -> Es2; +union(Es1, []) -> Es1. + +%% union([OrdSet]) -> OrdSet +%% Return the union of the list of ordered sets. + +-spec union([ordset(_)]) -> ordset(_). + +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(OrdSet1, OrdSet2) -> OrdSet. +%% Return the intersection of OrdSet1 and OrdSet2. + +-spec intersection(ordset(_), ordset(_)) -> ordset(_). + +intersection([E1|Es1], [E2|_]=Set2) when E1 < E2 -> + intersection(Es1, Set2); +intersection([E1|_]=Set1, [E2|Es2]) when E1 > E2 -> + intersection(Es2, Set1); % switch arguments! +intersection([E1|Es1], [_E2|Es2]) -> %E1 == E2 + [E1|intersection(Es1, Es2)]; +intersection([], _) -> + []; +intersection(_, []) -> + []. + +%% intersection([OrdSet]) -> OrdSet. +%% Return the intersection of the list of ordered sets. + +-spec intersection([ordset(_)]) -> ordset(_). + +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(OrdSet1, OrdSet2) -> boolean(). +%% Check whether OrdSet1 and OrdSet2 are disjoint. + +-spec is_disjoint(ordset(_), ordset(_)) -> boolean(). + +is_disjoint([E1|Es1], [E2|_]=Set2) when E1 < E2 -> + is_disjoint(Es1, Set2); +is_disjoint([E1|_]=Set1, [E2|Es2]) when E1 > E2 -> + is_disjoint(Es2, Set1); % switch arguments! +is_disjoint([_E1|_Es1], [_E2|_Es2]) -> %E1 == E2 + false; +is_disjoint([], _) -> + true; +is_disjoint(_, []) -> + true. + +%% subtract(OrdSet1, OrdSet2) -> OrdSet. +%% Return all and only the elements of OrdSet1 which are not also in +%% OrdSet2. + +-spec subtract(ordset(_), ordset(_)) -> ordset(_). + +subtract([E1|Es1], [E2|_]=Set2) when E1 < E2 -> + [E1|subtract(Es1, Set2)]; +subtract([E1|_]=Set1, [E2|Es2]) when E1 > E2 -> + subtract(Set1, Es2); +subtract([_E1|Es1], [_E2|Es2]) -> %E1 == E2 + subtract(Es1, Es2); +subtract([], _) -> []; +subtract(Es1, []) -> Es1. + +%% is_subset(OrdSet1, OrdSet2) -> boolean(). +%% Return 'true' when every element of OrdSet1 is also a member of +%% OrdSet2, else 'false'. + +-spec is_subset(ordset(_), ordset(_)) -> boolean(). + +is_subset([E1|_], [E2|_]) when E1 < E2 -> %E1 not in Set2 + false; +is_subset([E1|_]=Set1, [E2|Es2]) when E1 > E2 -> + is_subset(Set1, Es2); +is_subset([_E1|Es1], [_E2|Es2]) -> %E1 == E2 + is_subset(Es1, Es2); +is_subset([], _) -> true; +is_subset(_, []) -> false. + +%% fold(Fun, Accumulator, OrdSet) -> Accumulator. +%% Fold function Fun over all elements in OrdSet and return Accumulator. + +-spec fold(fun((_, _) -> _), _, ordset(_)) -> _. + +fold(F, Acc, Set) -> + lists:foldl(F, Acc, Set). + +%% filter(Fun, OrdSet) -> OrdSet. +%% Filter OrdSet with Fun. + +-spec filter(fun((_) -> boolean()), ordset(_)) -> ordset(_). + +filter(F, Set) -> + lists:filter(F, Set). |