1:- module(sets,
2 [ insert/3, ord_delete/3,
3 ord_member/2, ord_test_member/3, ord_subtract/3,
4 ord_intersection/3, ord_intersection_diff/4, ord_intersect/2,
5 ord_subset/2, ord_subset_diff/3,
6 ord_union/3, ord_union_diff/4, ord_union_symdiff/4,
7 ord_union_change/3, merge/3,
8 ord_disjoint/2, setproduct/3
9 ]). 10
11insert([], Element, [Element]).
12insert([Head|Tail], Element, Set) :-
13 compare(Order, Head, Element),
14 insert_comp(Order, Head, Tail, Element, Set).
15
16insert_comp(<, Head, Tail, Element, [Head|Set]) :-
17 insert(Tail, Element, Set).
18insert_comp(=, Head, Tail, _, [Head|Tail]).
19insert_comp(>, Head, Tail, Element, [Element,Head|Tail]).
20
21ord_delete([Y|Ys],X,Zs) :-
22 X @> Y, !,
23 Zs = [Y|NewYs],
24 ord_delete(Ys,X,NewYs).
25ord_delete([Y|Ys],X,Zs) :-
26 X == Y, !,
27 Zs = Ys.
28ord_delete([Y|Ys],_X,Zs) :-
29 30 Zs = [Y|Ys].
31ord_delete([],_,[]).
32
33ord_member(X,[Y|Ys]) :-
34 compare(D,X,Y),
35 ord_member1(D,X,Ys).
36
37ord_member1(=,_,_).
38ord_member1(>,X,[Y|Ys]):-
39 compare(D,X,Y),
40 ord_member1(D,X,Ys).
41
42ord_test_member([],_Y,no).
43ord_test_member([X|Xs],Y,Flag) :-
44 compare(D,X,Y),
45 ord_test_member_(D,Xs,Y,Flag).
46
47ord_test_member_(=,_,_,yes).
48ord_test_member_(<,Xs,Y,Flag):-
49 ord_test_member(Xs,Y,Flag).
50ord_test_member_(>,_Xs,_Y,no).
51
52ord_subtract([], _, []) :- !.
53ord_subtract(Set1, [], Set1) :- !.
54ord_subtract([Head1|Tail1], [Head2|Tail2], Difference) :-
55 compare(Order, Head1, Head2),
56 ord_subtract_(Order, Head1, Tail1, Head2, Tail2, Difference).
57
58ord_subtract_(<, Head1, [], _, _, [Head1]) :- !.
59ord_subtract_(<, Head0, [Head1|Tail1], Head2, Tail2, [Head0|Difference]) :-
60 compare(Order, Head1, Head2),
61 ord_subtract_(Order, Head1, Tail1, Head2, Tail2, Difference).
62ord_subtract_(=, _, Tail1, _, Tail2, Difference) :-
63 ord_subtract(Tail1, Tail2, Difference).
64ord_subtract_(>, Head1, Tail1, _, [], [Head1|Tail1]) :- !.
65ord_subtract_(>, Head1, Tail1, _, [Head2|Tail2], Difference) :-
66 compare(Order, Head1, Head2),
67 ord_subtract_(Order, Head1, Tail1, Head2, Tail2, Difference).
68
69ord_intersect([Head1|Tail1], [Head2|Tail2]) :-
70 compare(Order, Head1, Head2),
71 ord_intersect_(Order, Head1, Tail1, Head2, Tail2).
72
73ord_intersect_(<, _, [Head1|Tail1], Head2, Tail2) :-
74 compare(Order, Head1, Head2),
75 ord_intersect_(Order, Head1, Tail1, Head2, Tail2).
76ord_intersect_(=, _, _, _, _).
77ord_intersect_(>, Head1, Tail1, _, [Head2|Tail2]) :-
78 compare(Order, Head1, Head2),
79 ord_intersect_(Order, Head1, Tail1, Head2, Tail2).
80
81ord_intersection([], _, []) :- !.
82ord_intersection(_, [], []) :- !.
83ord_intersection([Head1|Tail1], [Head2|Tail2], Intersection) :-
84 compare(Order, Head1, Head2),
85 ord_intersection_(Order, Head1, Tail1, Head2, Tail2, Intersection).
86
87ord_intersection_(<, _, [], _, _, []) :- !.
88ord_intersection_(<, _, [Head1|Tail1], Head2, Tail2, Intersection) :-
89 compare(Order, Head1, Head2),
90 ord_intersection_(Order, Head1, Tail1, Head2, Tail2, Intersection).
91ord_intersection_(=, Head, Tail1, _, Tail2, [Head|Intersection]) :-
92 ord_intersection(Tail1, Tail2, Intersection).
93ord_intersection_(>, _, _, _, [], []) :- !.
94ord_intersection_(>, Head1, Tail1, _, [Head2|Tail2], Intersection) :-
95 compare(Order, Head1, Head2),
96 ord_intersection_(Order, Head1, Tail1, Head2, Tail2, Intersection).
97
98ord_intersection_diff([], _, [], []) :- !.
99ord_intersection_diff(Xs, [], [], Xs) :- !.
100ord_intersection_diff([O|Os], [N|Ns], Int, NotInt) :-
101 compare(C, O, N),
102 ord_intersection_diff_(C, O, Os, N, Ns, Int, NotInt).
103
104ord_intersection_diff_(<, O, [], _, _, [], [O]) :- !.
105ord_intersection_diff_(<, O1, [O|Os], N, Ns, Int, [O1|NotInt]) :-
106 compare(C, O, N),
107 ord_intersection_diff_(C, O, Os, N, Ns, Int, NotInt).
108ord_intersection_diff_(=, _, Os, N, Ns, [N|Int], NotInt) :-
109 ord_intersection_diff(Os, Ns, Int, NotInt).
110ord_intersection_diff_(>, O, Os, _, [], [], [O|Os]) :- !.
111ord_intersection_diff_(>, O, Os, _, [N|Ns], Int, NotInt) :-
112 compare(C, O, N),
113 ord_intersection_diff_(C, O, Os, N, Ns, Int, NotInt).
114
115ord_subset([], _).
116ord_subset([Head1|Tail1], [Head2|Tail2]) :-
117 compare(Order, Head1, Head2),
118 ord_subset_(Order, Head1, Tail1, Tail2).
119
120ord_subset_(=, _, Tail1, Tail2) :-
121 ord_subset(Tail1, Tail2).
122ord_subset_(>, Head1, Tail1, [Head2|Tail2]) :-
123 compare(Order, Head1, Head2),
124 ord_subset_(Order, Head1, Tail1, Tail2).
125
126ord_subset_diff([], Ys, Ys).
127ord_subset_diff([Head1|Tail1], [Head2|Tail2], Diff) :-
128 compare(Order, Head1, Head2),
129 ord_subset_diff_(Order, Head1, Tail1, Head2,Tail2, Diff).
130
131ord_subset_diff_(=, _, Tail1, _, Tail2, Diff) :-
132 ord_subset_diff(Tail1, Tail2, Diff).
133ord_subset_diff_(>, Head1, Tail1, Head2, [Head3|Tail2], [Head2|Diff]) :-
134 compare(Order, Head1, Head3),
135 ord_subset_diff_(Order, Head1, Tail1, Head3, Tail2, Diff).
136
137ord_union([], Set2, Set2) :- !.
138ord_union(Set1, [], Set1) :- !.
139ord_union([Head1|Tail1], [Head2|Tail2], Union) :-
140 compare(Order, Head1, Head2),
141 ord_union_(Order, Head1, Tail1, Head2, Tail2, Union).
142
143ord_union_(<, Head0, [], Head2, Tail2, [Head0,Head2|Tail2]) :- !.
144ord_union_(<, Head0, [Head1|Tail1], Head2, Tail2, [Head0|Union]) :-
145 compare(Order, Head1, Head2),
146 ord_union_(Order, Head1, Tail1, Head2, Tail2, Union).
147ord_union_(=, Head, Tail1, _, Tail2, [Head|Union]) :-
148 ord_union(Tail1, Tail2, Union).
149ord_union_(>, Head1, Tail1, Head0, [], [Head0,Head1|Tail1]) :- !.
150ord_union_(>, Head1, Tail1, Head0, [Head2|Tail2], [Head0|Union]) :-
151 compare(Order, Head1, Head2),
152 ord_union_(Order, Head1, Tail1, Head2, Tail2, Union).
153
154merge(Set1,Set2,Union):- ord_union(Set1,Set2,Union).
155
156ord_union_change(Set1, [], Set1) :- !,
157 nonempty(Set1).
158ord_union_change([Head1|Tail1], [Head2|Tail2], Union) :-
159 compare(Order, Head1, Head2),
160 ord_union_change_(Order, Head1, Tail1, Head2, Tail2, Union).
161
162ord_union_change_(<, Head0, [], Head2, Tail2, [Head0,Head2|Tail2]) :- !.
163ord_union_change_(<, Head0, [Head1|Tail1], Head2, Tail2, [Head0|Union]) :-
164 compare(Order, Head1, Head2),
165 ord_union_(Order, Head1, Tail1, Head2, Tail2, Union).
166ord_union_change_(=, Head, Tail1, _, Tail2, [Head|Union]) :-
167 ord_union_change(Tail1, Tail2, Union).
168ord_union_change_(>, Head1, Tail1, Head0, [], [Head0,Head1|Tail1]) :- !.
169ord_union_change_(>, Head1, Tail1, Head0, [Head2|Tail2], [Head0|Union]) :-
170 compare(Order, Head1, Head2),
171 ord_union_change_(Order, Head1, Tail1, Head2, Tail2, Union).
172
173nonempty([_|_]).
174
175ord_union_diff([], Set, Set, Set) :- !.
176ord_union_diff(Set, [], Set, []) :- !.
177ord_union_diff([O|Os], [N|Ns], Set, New) :-
178 compare(C, O, N),
179 ord_union_diff_(C, O, Os, N, Ns, Set, New).
180
181ord_union_diff_(<, O, [], N, Ns, [O,N|Ns], [N|Ns]) :- !.
182ord_union_diff_(<, O1, [O|Os], N, Ns, [O1|Set], New) :-
183 compare(C, O, N),
184 ord_union_diff_(C, O, Os, N, Ns, Set, New).
185ord_union_diff_(=, _, Os, N, Ns, [N|Set], New) :-
186 ord_union_diff(Os, Ns, Set, New).
187ord_union_diff_(>, O, Os, N, [], [N,O|Os], [N]) :- !.
188ord_union_diff_(>, O, Os, N1, [N|Ns], [N1|Set], [N1|New]) :-
189 compare(C, O, N),
190 ord_union_diff_(C, O, Os, N, Ns, Set, New).
191
192ord_union_symdiff(Set1,Set2,Union,Diff):-
193 ord_symdiff_union(Set1,Set2,Diff,Union).
194
195ord_symdiff_union([],Set2,Set2,Set2) :- !.
196ord_symdiff_union(Set1,[],Set1,Set1) :- !.
197ord_symdiff_union([H1|Tail1],[H2|Tail2],Diff,Union) :-
198 compare(Order,H1,H2),
199 ord_symdiff_union_(Order,H1,Tail1,H2,Tail2,Diff,Union).
200
201ord_symdiff_union_(<,H0,[],H2,Tail2,Diff,Union) :- !,
202 Diff = [H0,H2|Tail2],
203 Union = Diff.
204ord_symdiff_union_(<,H0,[H1|Tail1],H2,Tail2,[H0|Diff],[H0|Union]) :-
205 compare(Order,H1,H2),
206 ord_symdiff_union_(Order,H1,Tail1,H2,Tail2,Diff,Union).
207ord_symdiff_union_(=,H1,Tail1,_,Tail2,Diff,[H1|Union]) :-
208 ord_symdiff_union(Tail1,Tail2,Diff,Union).
209ord_symdiff_union_(>,H1,Tail1,H0,[],Diff,Union) :- !,
210 Diff = [H0,H1|Tail1],
211 Union = Diff.
212ord_symdiff_union_(>,H1,Tail1,H0,[H2|Tail2],[H0|Diff],[H0|Union]) :-
213 compare(Order,H1,H2),
214 ord_symdiff_union_(Order,H1,Tail1,H2,Tail2,Diff,Union).
215
216ord_disjoint([], _) :- !.
217ord_disjoint(_, []) :- !.
218ord_disjoint([Head1|Tail1], [Head2|Tail2]) :-
219 compare(Order, Head1, Head2),
220 ord_disjoint_(Order, Head1, Tail1, Head2, Tail2).
221
222ord_disjoint_(<, _, [], _, _) :- !.
223ord_disjoint_(<, _, [Head1|Tail1], Head2, Tail2) :-
224 compare(Order, Head1, Head2),
225 ord_disjoint_(Order, Head1, Tail1, Head2, Tail2).
226ord_disjoint_(>, _, _, _, []) :- !.
227ord_disjoint_(>, Head1, Tail1, _, [Head2|Tail2]) :-
228 compare(Order, Head1, Head2),
229 ord_disjoint_(Order, Head1, Tail1, Head2, Tail2).
230
231setproduct([], _, []).
232setproduct([Head|Tail], Set, SetProduct) :-
233 setproduct_(Set, Head, SetProduct, Rest),
234 setproduct(Tail, Set, Rest).
235
236setproduct_([], _, Set, Set).
237setproduct_([Head|Tail], X, [Set|TailX], Tl) :-
238 sort([Head,X],Set),
239 setproduct_(Tail, X, TailX, Tl)