/* Copyright(C) 1988, Swedish Institute of Computer Science */ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % File : ORDSETS.PL % % Author : Lena Flood % % Updated: 9 September 1988 % % Purpose: Ordered set manipulation utilities % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% :- module(ordsets, [ is_ordset/1, list_to_ord_set/2, ord_add_element/3, ord_del_element/3, ord_disjoint/2, ord_intersect/2, ord_intersection/3, ord_intersection/4, ord_intersection/2, ord_member/2, ord_seteq/2, ord_setproduct/3, ord_subset/2, ord_subtract/3, ord_symdiff/3, ord_union/3, ord_union/4, ord_union/2 ]). % Adapted from shared code written by Richard A O'Keefe. % In this package, sets are represented by ordered lists with no % duplicates. Thus {c,r,a,f,t} would be [a,c,f,r,t]. The ordering % is defined by the @< family of term comparison predicates, which % is the ordering used by sort/2 and setof/3. % The benefit of the ordered representation is that the elementary % set operations can be done in time proportional to the Sum of the % argument sizes rather than their Product. % is_ordset(+Set) % is true when Set is an ordered set. is_ordset(X) :- var(X), !, fail. is_ordset([]). is_ordset([Head|Tail]) :- is_ordset(Tail, Head). is_ordset(X, _) :- var(X), !, fail. is_ordset([], _). is_ordset([Head|Tail], Left) :- Left @< Head, is_ordset(Tail, Head). % list_to_ord_set(+List, ?Set) % is true when Set is the ordered representation of the set represented % by the unordered representation List. list_to_ord_set(List, Set) :- sort(List, Set). % ord_add_element(+Set1, +Element -Set2) % is true when Set2 is Set1 with Element inserted in it, preserving % the order. ord_add_element([], Element, [Element]). ord_add_element([Head|Tail], Element, Set) :- compare(Order, Head, Element), ord_add_element(Order, Head, Tail, Element, Set). ord_add_element(<, Head, Tail, Element, [Head|Set]) :- ord_add_element(Tail, Element, Set). ord_add_element(=, Head, Tail, _, [Head|Tail]). ord_add_element(>, Head, Tail, Element, [Element,Head|Tail]). % ord_del_element(+Set1, +Element, ?Set2) % is true when Set2 is Set1 but with Element removed. ord_del_element([], _, []). ord_del_element([Head|Tail], Element, Set) :- compare(Order, Head, Element), ord_del_element(Order, Head, Tail, Element, Set). ord_del_element(<, Head, Tail, Element, [Head|Set]) :- ord_del_element(Tail, Element, Set). ord_del_element(=, _, Tail, _, Tail). ord_del_element(>, Head, Tail, _, [Head|Tail]). % ord_disjoint(+Set1, +Set2) % is true when the two ordered sets have no element in common. ord_disjoint(Set1, Set2) :- \+ ord_intersect(Set1, Set2). % ord_intersect(+Set1, +Set2) % is true when the two ordered sets have at least one element in common. ord_intersect([Head1|Tail1], [Head2|Tail2]) :- compare(Order, Head1, Head2), ord_intersect(Order, Head1, Tail1, Head2, Tail2). ord_intersect(<, _, [Head1|Tail1], Head2, Tail2) :- compare(Order, Head1, Head2), ord_intersect(Order, Head1, Tail1, Head2, Tail2). ord_intersect(=, _, _, _, _). ord_intersect(>, Head1, Tail1, _, [Head2|Tail2]) :- compare(Order, Head1, Head2), ord_intersect(Order, Head1, Tail1, Head2, Tail2). % ord_intersection(+Set1, +Set2, ?Intersection) % is true when Intersection is the intersecton of Set1 % and Set2, provided that Set1 and Set2 are ordered sets. ord_intersection([], _, []). ord_intersection([Head1|Tail1], Set2, Intersection) :- ord_intersection3(Set2, Head1, Tail1, Intersection). ord_intersection3(<, _, Set1, Head2, Tail2, Intersection) :- ord_intersection3(Set1, Head2, Tail2, Intersection). ord_intersection3(=, Head, Tail1, _, Tail2, [Head|Intersection]) :- ord_intersection(Tail1, Tail2, Intersection). ord_intersection3(>, Head1, Tail1, _, Set2, Intersection) :- ord_intersection3(Set2, Head1, Tail1, Intersection). % could be a disjunction, but is used in three places ord_intersection3([], _, _, []). ord_intersection3([Head2|Tail2], Head1, Tail1, Intersection) :- compare(Order, Head1, Head2), ord_intersection3(Order, Head1, Tail1, Head2, Tail2, Intersection). % ord_intersection(+Set1, +Set2, ?Intersection, ?Difference) % is true when Intersection is the intersection of Set1 and Set2, % and Differens is Set2 \ Set1 (like in ord_union/4), % provided that Set1 and Set2 are ordered sets. ord_intersection([], Set2, [], Set2). ord_intersection([Head1|Tail1], Set2, Intersection, Difference) :- ord_intersection4(Set2, Head1, Tail1, Intersection, Difference). ord_intersection4(<, _, Set1, Head2, Tail2, Intersection, Difference) :- ( Set1 = [], Intersection = [], Difference = [Head2|Tail2] ; Set1 = [Head1|Tail1], compare(Order, Head1, Head2), ord_intersection4(Order, Head1, Tail1, Head2, Tail2, Intersection, Difference) ). ord_intersection4(=, Head, Tail1, _, Tail2, [Head|Intersection], Difference) :- ord_intersection(Tail1, Tail2, Intersection, Difference). ord_intersection4(>, Head1, Tail1, Head2, Set2, Intersection, [Head2|Difference]) :- ord_intersection4(Set2, Head1, Tail1, Intersection, Difference). ord_intersection4([], _, _, [], []). ord_intersection4([Head2|Tail2], Head1, Tail1, Intersection, Difference) :- compare(Order, Head1, Head2), ord_intersection4(Order, Head1, Tail1, Head2, Tail2, Intersection, Difference). % ord_intersection(+Sets, ?Intersection) % is true when Intersection is the ordered set representation of the % intersection of all the sets in Sets. ord_intersection(Sets, Intersection) :- length(Sets, NumberOfSets), NumberOfSets > 0, ord_intersection2(NumberOfSets, Sets, Intersection, []). ord_intersection2(1, [Set|Sets], Set0, Sets0) :- !, Set = Set0, Sets = Sets0. ord_intersection2(2, [Set,Set2|Sets], Intersection, Sets0) :- !, Sets = Sets0, ord_intersection2(Set, Set2, Intersection). ord_intersection2(N, Sets0, Intersection, Sets) :- % N > 2, A is N>>1, Z is N-A, ord_intersection2(A, Sets0, X, Sets1), ord_intersection2(Z, Sets1, Y, Sets), ord_intersection(X, Y, Intersection). % ord_member(+Elt, +Set) % is true when Elt is a member of Set. Suggested by Mark Johnson. ord_member(X, [E|Es]) :- compare(C, X, E), ord_member(C, X, Es). ord_member(=, _X, _Es). ord_member(>, X, [E|Es]) :- compare(C, X, E), ord_member(C, X, Es). % ord_seteq(+Set1, +Set2) % is true when the two arguments represent the same set. Since they % are assumed to be ordered representations, they must be identical. ord_seteq(Set1, Set2) :- Set1 == Set2. % ord_setproduct(+Set1, +Set2, ?SetProduct) % is true when SetProduct is the cartesian product of Set1 and Set2. The % product is represented as pairs Elem1-Elem2, where Elem1 is an element % from Set1 and Elem2 is an element from Set2. ord_setproduct([], _, []). ord_setproduct([Head|Tail], Set, SetProduct) :- ord_setproduct(Set, Head, SetProduct, Rest), ord_setproduct(Tail, Set, Rest). ord_setproduct([], _, Set, Set). ord_setproduct([Head|Tail], X, [X-Head|TailX], Tl) :- ord_setproduct(Tail, X, TailX, Tl). % ord_subset(+Set1, +Set2) % is true when every element of the ordered set Set1 appears in the % ordered set Set2. ord_subset([], _). ord_subset([Head1|Tail1], [Head2|Tail2]) :- compare(Order, Head1, Head2), ord_subset(Order, Head1, Tail1, Tail2). ord_subset(=, _, Tail1, Tail2) :- ord_subset(Tail1, Tail2). ord_subset(>, Head1, Tail1, [Head2|Tail2]) :- compare(Order, Head1, Head2), ord_subset(Order, Head1, Tail1, Tail2). % ord_subtract(+Set1, +Set2, ?Difference) % is true when Difference contains all and only the elements of Set1 % which are not also in Set2, i.e. Set1 \ Set2. ord_subtract(Set1, Set2, Union) :- prolog:subtract(Set1, Set2, Union). % ord_symdiff(+Set1, +Set2, ?Difference) % is true when Difference is the symmetric difference of Set1 and Set2. ord_symdiff([], Set2, Set2). ord_symdiff([Head1|Tail1], Set2, Symdiff) :- ord_symdiff(Set2, Head1, Tail1, Symdiff). ord_symdiff(<, Head1, Set1, Head2, Tail2, [Head1|Symdiff]) :- ord_symdiff(Set1, Head2, Tail2, Symdiff). ord_symdiff(=, _, Tail1, _, Tail2, Symdiff) :- ord_symdiff(Tail1, Tail2, Symdiff). ord_symdiff(>, Head1, Tail1, Head2, Set2, [Head2|Symdiff]) :- ord_symdiff(Set2, Head1, Tail1, Symdiff). % could be a disjunction, but is used in three places ord_symdiff([], Head1, Tail1, [Head1|Tail1]). ord_symdiff([Head2|Tail2], Head1, Tail1, Symdiff) :- compare(Order, Head1, Head2), ord_symdiff(Order, Head1, Tail1, Head2, Tail2, Symdiff). % ord_union(+Set1, +Set2, ?Union) % is true when Union is the union of Set1 and Set2. Note that when % something occurs in both sets, we want to retain only one copy. ord_union(Set1, Set2, Union) :- prolog:merge(Set1, Set2, Union). % ord_union(+Set1, +Set2, ?Union, ?New) % is true when Union is the union of Set1 and Set2, and New is % Set2 \ Set1. This is useful if you % are accumulating members of a set and you want to process new % elements as they are added to the set. ord_union([], Set2, Set2, Set2). ord_union([Head1|Tail1], Set2, Union, Difference) :- ord_union4(Set2, Head1, Tail1, Union, Difference). ord_union4(<, Head, Set1, Head2, Tail2, [Head|Union], Difference) :- ( Set1 = [], Union = [Head2|Tail2], Difference = [Head2|Tail2] ; Set1 = [Head1|Tail1], compare(Order, Head1, Head2), ord_union4(Order, Head1, Tail1, Head2, Tail2, Union, Difference) ). ord_union4(=, Head, Tail1, _, Tail2, [Head|Union], Difference) :- ord_union(Tail1, Tail2, Union, Difference). ord_union4(>, Head1, Tail1, Head2, Set2, [Head2|Union], [Head2|Difference]) :- ord_union4(Set2, Head1, Tail1, Union, Difference). ord_union4([], Head1, Tail1, [Head1|Tail1], []). ord_union4([Head2|Tail2], Head1, Tail1, Union, Difference) :- compare(Order, Head1, Head2), ord_union4(Order, Head1, Tail1, Head2, Tail2, Union, Difference). % ord_union(+Sets, ?Union) % is true when Union is the union of all the sets in Sets. ord_union([], Union) :- !, Union = []. ord_union(Sets, Union) :- length(Sets, NumberOfSets), ord_union_all(NumberOfSets, Sets, Union, []). ord_union_all(1, [Set|Sets], Set, Sets) :- !. ord_union_all(2, [Set,Set2|Sets], Union, Sets) :- !, ord_union(Set, Set2, Union). ord_union_all(N, Sets0, Union, Sets) :- A is N>>1, Z is N-A, ord_union_all(A, Sets0, X, Sets1), ord_union_all(Z, Sets1, Y, Sets), ord_union(X, Y, Union).