5
6
11
16
23
24:- module(ordered_set_utilities,
25 [ insert_merge/3, 26 insert_merge/4, 27 merge/3, 28 merge/4, 29 list_to_ord_set/2, 30 list_to_ord_set/3, 31 insert/3, 32 insert/4, 33 ord_disjoint/2, 34 ord_disjoint/2, 35 ord_intersect_chk/2, 36 ord_intersect_chk/3, 37 ord_intersect/3, 38 ord_intersect/4, 39 ord_seteq/2, 40 41 ord_subset/2, 42 ord_subset/3, 43 ord_subtract/3, 44 ord_subtract/4, 45 46 ord_symdiff/4, 47 ord_union/3, 48 ord_union/4, 49 ord_union_and_new/4, 50 ord_union_and_new/5 51 ]). 52
53:- ensure_loaded((utils_higher_order)). 54
75
76
86
87insert_merge(Set0, Item, Set):-
88 insert_merge(Set0, Item, compare, Set).
89
90insert_merge([], Item, _, [Item]).
91insert_merge([Element|Set0], Item, Comparator, Set):-
92 call(Comparator, Order, Element, Item),
93 insert_merge2(Order, Element, Item, Set0, Comparator, Set).
94
95 insert_merge2(<, Element, Item, Set0, Comparator, [Element|Set]):-
96 insert_merge(Set0, Item, Comparator, Set).
97 insert_merge2(=, Element, Item, Set, _, [Item, Element|Set]).
98 insert_merge2(>, Element, Item, Set, _, [Item, Element|Set]).
99
100
109
110merge(List1, List2, Merged):-
111 merge(List1, List2, compare, Merged).
112
113merge(List1, List2, Comparator, Merged):-
114 foldl(List1,
115 [Merged0, Element, Merged1]^insert_merge(Merged0, Element, Comparator, Merged1),
116 List2, Merged).
117
118
123
124insert(Set0, Item, Set):-
125 insert(Set0, Item, compare, Set).
126
127insert([], Item, _, [Item]).
128insert([Element|Set0], Item, Comparator, Set):-
129 call(Comparator, Order, Element, Item),
130 insert2(Order, Element, Item, Set0, Comparator, Set).
131
132 insert2(<, Element, Item, Set0, Comparator, [Element|Set]):-
133 insert(Set0, Item, Comparator, Set).
134 insert2(=, Element, _, Set, _, [Element|Set]).
135 insert2(>, Element, Item, Set, _, [Item, Element|Set]).
136
137
144
145list_to_ord_set(List, Set) :-
146 sort(List, Set).
147
149list_to_ord_set(List, Comparator, Set):-
150 foldl(List, [Set0, Element, Set1]^insert(Set0, Element, Comparator, Set1), [], Set).
151
152
157
158ord_intersect_chk(Set1, Set2):-
159 ord_intersect_chk(Set1, Set2, compare).
160
161ord_intersect_chk([H1|T1], Set2, Comparator):-
162 ord_intersect_chk2(Set2, H1, T1, Comparator).
163
164 ord_intersect_chk2([H2|T2], H1, T1, Comparator):-
165 call(Comparator, Order, H1, H2),
166 ord_intersect_chk3(Order, H1, T1, H2, T2, Comparator).
167
168 ord_intersect_chk3(<, _H1, T1, H2, T2, Comparator):-
169 ord_intersect_chk2(T1, H2, T2, Comparator).
170 ord_intersect_chk3(=, _, _, _, _, _).
171 ord_intersect_chk3(>, H1, T1, _H2, T2, Comparator):-
172 ord_intersect_chk2(T2, H1, T1, Comparator).
173
174
175
180
181ord_intersect(Set1, Set2, Intersection):-
182 ord_intersect(Set1, Set2, compare, Intersection).
183
184ord_intersect([], _, _, []).
185ord_intersect([H1|T1], Set2, Comparator, Intersection):-
186 ord_intersect2(Set2, H1, T1, Comparator, Intersection).
187
188 ord_intersect2([], _, _, _, []).
189 ord_intersect2([H2|T2], H1, T1, Comparator, Intersection):-
190 call(Comparator, Order, H1, H2),
191 ord_intersect3(Order, H1, T1, H2, T2, Comparator, Intersection).
192
193 ord_intersect3(<, _H1, T1, H2, T2, Comparator, Intersection):-
194 ord_intersect2(T1, H2, T2, Comparator, Intersection).
195 ord_intersect3(=, H, T1, _H, T2, Comparator, [H|Intersection]):-
196 ord_intersect(T1, T2, Comparator, Intersection).
197 ord_intersect3(>, H1, T1, _H2, T2, Comparator, Intersection):-
198 ord_intersect2(T2, H1, T1, Comparator, Intersection).
199
200
201
205
206
207ord_seteq(Set1, Set2) :-
208 Set1 == Set2.
209
210
211
216
217ord_disjoint(Set1, Set2):-
218 ord_disjoint(Set1, Set2, compare).
219
220ord_disjoint([], _, _).
221ord_disjoint([H1|T1], Set2, Comparator):-
222 ord_disjoint2(Set2, H1, T1, Comparator).
223
224 ord_disjoint2([], _, _, _).
225 ord_disjoint2([H2|T2], H1, T1, Comparator):-
226 call(Comparator, Order, H1, H2),
227 ord_disjoiont3(Order, H1, T1, H2, T2, Comparator).
228
229 ord_disjoint3(<, _H1, T1, H2, T2, Comparator):-
230 ord_disjoint2(T1, H2, T2, Comparator).
231 ord_disjoint3(>, H1, T1, _H2, T2, Comparator):-
232 ord_disjoint2(T2, H1, T1, Comparator).
233
234
235
240
241ord_subset(Set1, Set2):-
242 ord_subset(Set1, Set2, compare).
243
244ord_subset([], _, _).
245ord_subset([H1|T1], Set2, Comparator):-
246 ord_subset2(Set2, H1, T1, Comparator).
247
248 ord_subset2([H2|T2], H1, T1, Comparator):-
249 call(Comparator, Order, H1, H2),
250 ord_subset3(Order, H1, T1, H2, T2, Comparator).
251
252 ord_subset3(=, _H, T1, _H, T2, Comparator):-
253 ord_subset(T1, T2, Comparator).
254 ord_subset3(>, H1, T1, _H2, T2, Comparator):-
255 ord_subset2(T2, H1, T1, Comparator).
256
257
258
263
264ord_subtract(Set1, Set2, Difference):-
265 ord_subtract(Set1, Set2, compare, Difference).
266
267ord_subtract([], _, _, []).
268ord_subtract([H1|T1], Set2, Comparator, Difference):-
269 ord_subtract2(Set2, H1, T1, Comparator, Difference).
270
271 ord_subtract2([], H1, T1, _, [H1|T1]).
272 ord_subtract2([H2|T2], H1, T1, Comparator, Difference):-
273 call(Comparator, Order, H1, H2),
274 ord_subtract3(Order, H1, T1, H2, T2, Comparator, Difference).
275
276 ord_subtract2a([], _, _, _, []).
277 ord_subtract2a([H1|T1], H2, T2, Comparator, Difference):-
278 call(Comparator, Order, H1, H2),
279 ord_subtract3(Order, H1, T1, H2, T2, Comparator, Difference).
280
281 ord_subtract4(<, H1, T1, H2, T2, Comparator, [H1|Difference]):-
282 ord_subtract2a(T1, H2, T2, Comparator, Difference).
283 ord_subtract4(=, _H, T1, _H, T2, Comparator, Difference):-
284 ord_subtract(T1, T2, Comparator, Difference).
285 ord_subtract4(>, H1, T1, _H2, T2, Comparator, Difference):-
286 ord_subtract2(T2, H1, T1, Comparator, Difference).
287
288
293
294ord_symmdiff(Set1, Set2, Difference):-
295 ord_symmdiff(Set1, Set2, compare, Difference).
296
297ord_symdiff([], Set2, _, Set2).
298ord_symdiff([H1|T1], Set2, Comparator, Difference):-
299 ord_symdiff2(Set2, H1, T1, Comparator, Difference).
300
301 ord_symdiff2([], H1, T1, _, [H1|T1]).
302 ord_symdiff2([H2|T2], H1, T1, Comparator, Difference):-
303 call(Comparator, Order, H1, H2),
304 ord_symdiff3(Order, H1, T1, H2, T2, Comparator, Difference).
305
306 ord_symdiff3(<, H1, T1, H2, T2, Comparator, [H1|Difference]):-
307 ord_symdiff2(T1, H2, T2, Comparator, Difference).
308 ord_symdiff3(=, _H, T1, _H, T2, Comparator, Difference):-
309 ord_symdiff(T1, T2, Comparator, Difference).
310 ord_symdiff3(>, H1, T1, H2, T2, Comparator, [H2|Difference]):-
311 ord_symdiff2(T2, H1, T1, Comparator, Difference).
312
313
314
319
320ord_union(Set1, Set2, Union):-
321 ord_union(Set1, Set2, compare, Union).
322
323ord_union(Set1, Set2, Comparator, Union):-
324 foldl(Set1,
325 [SetA, Element, SetB]^insert(SetA, Element, Comparator, SetB),
326 Set2, Union).
327
328
329
335
336ord_union_and_new(Set1, Set2, Union, ReallyNew):-
337 ord_union_and_new(Set1, Set2, compare, Union, ReallyNew).
338
339ord_union_and_new([], Set2, _, Set2, Set2).
340ord_union_and_new([H1|T1], Set2, Comparator, Union, ReallyNew):-
341 ord_union_and_new_2(Set2, H1, T1, Comparator, Union, ReallyNew).
342
343 ord_union_and_new_2([], H1, T1, _, [H1|T1], []).
344 ord_union_and_new_2([H2|T2], H1, T1, Comparator, Union, ReallyNew):-
345 call(Comparator, Order, H1, H2),
346 ord_union_and_new_3(Order, H1, T1, H2, T2, Comparator, Union, ReallyNew).
347
348 ord_union_and_new_2a([], H2, T2, _, [H2|T2], [H2|T2]).
349 ord_union_and_new_2a([H1|T1], H2, T2, Comparator, Union, ReallyNew):-
350 call(Comparator, Order, H1, H2),
351 ord_union_and_new_3(Order, H1, T1, H2, T2, Comparator, Union, ReallyNew).
352
353 ord_union_and_new_3(<, H1, T1, H2, T2, Comparator, [H1|Union], ReallyNew):-
354 ord_union_and_new_2a(T1, H2, T2, Comparator, Union, ReallyNew).
355 ord_union_and_new_3(=, H1, T1, _H2, T2, Comparator, [H1|Union], ReallyNew):-
356 ord_union_and_new(T1, T2, Comparator, Union, ReallyNew).
357 ord_union_and_new_3(>, H1, T1, H2, T2, Comparator, [H2|Union], [H2|ReallyNew]):-
358 ord_union_and_new_2(T2, H1, T1, Comparator, Union, ReallyNew)