1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2001-2014, University of Amsterdam 7 VU University Amsterdam 8 All rights reserved. 9 10 Redistribution and use in source and binary forms, with or without 11 modification, are permitted provided that the following conditions 12 are met: 13 14 1. Redistributions of source code must retain the above copyright 15 notice, this list of conditions and the following disclaimer. 16 17 2. Redistributions in binary form must reproduce the above copyright 18 notice, this list of conditions and the following disclaimer in 19 the documentation and/or other materials provided with the 20 distribution. 21 22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 POSSIBILITY OF SUCH DAMAGE. 34*/ 35 36:- module(ordsets, 37 [ is_ordset/1, % @Term 38 list_to_ord_set/2, % +List, -OrdSet 39 ord_add_element/3, % +Set, +Element, -NewSet 40 ord_del_element/3, % +Set, +Element, -NewSet 41 ord_selectchk/3, % +Item, ?Set1, ?Set2 42 ord_intersect/2, % +Set1, +Set2 (test non-empty) 43 ord_intersect/3, % +Set1, +Set2, -Intersection 44 ord_intersection/3, % +Set1, +Set2, -Intersection 45 ord_intersection/4, % +Set1, +Set2, -Intersection, -Diff 46 ord_disjoint/2, % +Set1, +Set2 47 ord_subtract/3, % +Set, +Delete, -Remaining 48 ord_union/2, % +SetOfOrdSets, -Set 49 ord_union/3, % +Set1, +Set2, -Union 50 ord_union/4, % +Set1, +Set2, -Union, -New 51 ord_subset/2, % +Sub, +Super (test Sub is in Super) 52 % Non-Quintus extensions 53 ord_empty/1, % ?Set 54 ord_memberchk/2, % +Element, +Set, 55 ord_symdiff/3, % +Set1, +Set2, ?Diff 56 % SICSTus extensions 57 ord_seteq/2, % +Set1, +Set2 58 ord_intersection/2 % +PowerSet, -Intersection 59 ]). 60:- use_module(library(oset)). 61:- set_prolog_flag(generate_debug_info, false). 62 63/** <module> Ordered set manipulation 64 65Ordered sets are lists with unique elements sorted to the standard order 66of terms (see sort/2). Exploiting ordering, many of the set operations 67can be expressed in order N rather than N^2 when dealing with unordered 68sets that may contain duplicates. The library(ordsets) is available in a 69number of Prolog implementations. Our predicates are designed to be 70compatible with common practice in the Prolog community. The 71implementation is incomplete and relies partly on library(oset), an 72older ordered set library distributed with SWI-Prolog. New applications 73are advised to use library(ordsets). 74 75Some of these predicates match directly to corresponding list 76operations. It is advised to use the versions from this library to make 77clear you are operating on ordered sets. An exception is member/2. See 78ord_memberchk/2. 79 80The ordsets library is based on the standard order of terms. This 81implies it can handle all Prolog terms, including variables. Note 82however, that the ordering is not stable if a term inside the set is 83further instantiated. Also note that variable ordering changes if 84variables in the set are unified with each other or a variable in the 85set is unified with a variable that is `older' than the newest variable 86in the set. In practice, this implies that it is allowed to use 87member(X, OrdSet) on an ordered set that holds variables only if X is a 88fresh variable. In other cases one should cease using it as an ordset 89because the order it relies on may have been changed. 90*/ 91 92%! is_ordset(@Term) is semidet. 93% 94% True if Term is an ordered set. All predicates in this library 95% expect ordered sets as input arguments. Failing to fullfil this 96% assumption results in undefined behaviour. Typically, ordered 97% sets are created by predicates from this library, sort/2 or 98% setof/3. 99 100is_ordset(Term) :- 101 is_list(Term), 102 is_ordset2(Term). 103 104is_ordset2([]). 105is_ordset2([H|T]) :- 106 is_ordset3(T, H). 107 108is_ordset3([], _). 109is_ordset3([H2|T], H) :- 110 H2 @> H, 111 is_ordset3(T, H2). 112 113 114%! ord_empty(?List) is semidet. 115% 116% True when List is the empty ordered set. Simply unifies list 117% with the empty list. Not part of Quintus. 118 119ord_empty([]). 120 121 122%! ord_seteq(+Set1, +Set2) is semidet. 123% 124% True if Set1 and Set2 have the same elements. As both are 125% canonical sorted lists, this is the same as ==/2. 126% 127% @compat sicstus 128 129ord_seteq(Set1, Set2) :- 130 Set1 == Set2. 131 132 133%! list_to_ord_set(+List, -OrdSet) is det. 134% 135% Transform a list into an ordered set. This is the same as 136% sorting the list. 137 138list_to_ord_set(List, Set) :- 139 sort(List, Set). 140 141 142%! ord_intersect(+Set1, +Set2) is semidet. 143% 144% True if both ordered sets have a non-empty intersection. 145 146ord_intersect([H1|T1], L2) :- 147 ord_intersect_(L2, H1, T1). 148 149ord_intersect_([H2|T2], H1, T1) :- 150 compare(Order, H1, H2), 151 ord_intersect__(Order, H1, T1, H2, T2). 152 153ord_intersect__(<, _H1, T1, H2, T2) :- 154 ord_intersect_(T1, H2, T2). 155ord_intersect__(=, _H1, _T1, _H2, _T2). 156ord_intersect__(>, H1, T1, _H2, T2) :- 157 ord_intersect_(T2, H1, T1). 158 159 160%! ord_disjoint(+Set1, +Set2) is semidet. 161% 162% True if Set1 and Set2 have no common elements. This is the 163% negation of ord_intersect/2. 164 165ord_disjoint(Set1, Set2) :- 166 \+ ord_intersect(Set1, Set2). 167 168 169%! ord_intersect(+Set1, +Set2, -Intersection) 170% 171% Intersection holds the common elements of Set1 and Set2. 172% 173% @deprecated Use ord_intersection/3 174 175ord_intersect(Set1, Set2, Intersection) :- 176 oset_int(Set1, Set2, Intersection). 177 178 179%! ord_intersection(+PowerSet, -Intersection) 180% 181% Intersection of a powerset. True when Intersection is an ordered 182% set holding all elements common to all sets in PowerSet. 183% 184% @compat sicstus 185 186ord_intersection(PowerSet, Intersection) :- 187 key_by_length(PowerSet, Pairs), 188 keysort(Pairs, [_-S|Sorted]), 189 l_int(Sorted, S, Intersection). 190 191key_by_length([], []). 192key_by_length([H|T0], [L-H|T]) :- 193 length(H, L), 194 key_by_length(T0, T). 195 196l_int([], S, S). 197l_int([_-H|T], S0, S) :- 198 ord_intersection(S0, H, S1), 199 l_int(T, S1, S). 200 201 202%! ord_intersection(+Set1, +Set2, -Intersection) is det. 203% 204% Intersection holds the common elements of Set1 and Set2. Uses 205% ord_disjoint/2 if Intersection is bound to `[]` on entry. 206 207ord_intersection(Set1, Set2, Intersection) :- 208 ( Intersection == [] 209 -> ord_disjoint(Set1, Set2) 210 ; oset_int(Set1, Set2, Intersection) 211 ). 212 213 214%! ord_intersection(+Set1, +Set2, ?Intersection, ?Difference) is det. 215% 216% Intersection and difference between two ordered sets. 217% Intersection is the intersection between Set1 and Set2, while 218% Difference is defined by ord_subtract(Set2, Set1, Difference). 219% 220% @see ord_intersection/3 and ord_subtract/3. 221 222ord_intersection([], L, [], L) :- !. 223ord_intersection([_|_], [], [], []) :- !. 224ord_intersection([H1|T1], [H2|T2], Intersection, Difference) :- 225 compare(Diff, H1, H2), 226 ord_intersection2(Diff, H1, T1, H2, T2, Intersection, Difference). 227 228ord_intersection2(=, H1, T1, _H2, T2, [H1|T], Difference) :- 229 ord_intersection(T1, T2, T, Difference). 230ord_intersection2(<, _, T1, H2, T2, Intersection, Difference) :- 231 ord_intersection(T1, [H2|T2], Intersection, Difference). 232ord_intersection2(>, H1, T1, H2, T2, Intersection, [H2|HDiff]) :- 233 ord_intersection([H1|T1], T2, Intersection, HDiff). 234 235 236%! ord_add_element(+Set1, +Element, ?Set2) is det. 237% 238% Insert an element into the set. This is the same as 239% ord_union(Set1, [Element], Set2). 240 241ord_add_element(Set1, Element, Set2) :- 242 oset_addel(Set1, Element, Set2). 243 244 245%! ord_del_element(+Set, +Element, -NewSet) is det. 246% 247% Delete an element from an ordered set. This is the same as 248% ord_subtract(Set, [Element], NewSet). 249 250ord_del_element(Set, Element, NewSet) :- 251 oset_delel(Set, Element, NewSet). 252 253 254%! ord_selectchk(+Item, ?Set1, ?Set2) is semidet. 255% 256% Selectchk/3, specialised for ordered sets. Is true when 257% select(Item, Set1, Set2) and Set1, Set2 are both sorted lists 258% without duplicates. This implementation is only expected to work 259% for Item ground and either Set1 or Set2 ground. The "chk" suffix 260% is meant to remind you of memberchk/2, which also expects its 261% first argument to be ground. ord_selectchk(X, S, T) => 262% ord_memberchk(X, S) & \+ ord_memberchk(X, T). 263% 264% @author Richard O'Keefe 265 266ord_selectchk(Item, [X|Set1], [X|Set2]) :- 267 X @< Item, 268 !, 269 ord_selectchk(Item, Set1, Set2). 270ord_selectchk(Item, [Item|Set1], Set1) :- 271 ( Set1 == [] 272 -> true 273 ; Set1 = [Y|_] 274 -> Item @< Y 275 ). 276 277 278%! ord_memberchk(+Element, +OrdSet) is semidet. 279% 280% True if Element is a member of OrdSet, compared using ==. Note 281% that _enumerating_ elements of an ordered set can be done using 282% member/2. 283% 284% Some Prolog implementations also provide ord_member/2, with the 285% same semantics as ord_memberchk/2. We believe that having a 286% semidet ord_member/2 is unacceptably inconsistent with the *_chk 287% convention. Portable code should use ord_memberchk/2 or 288% member/2. 289% 290% @author Richard O'Keefe 291 292ord_memberchk(Item, [X1,X2,X3,X4|Xs]) :- 293 !, 294 compare(R4, Item, X4), 295 ( R4 = (>) -> ord_memberchk(Item, Xs) 296 ; R4 = (<) -> 297 compare(R2, Item, X2), 298 ( R2 = (>) -> Item == X3 299 ; R2 = (<) -> Item == X1 300 ;/* R2 = (=), Item == X2 */ true 301 ) 302 ;/* R4 = (=) */ true 303 ). 304ord_memberchk(Item, [X1,X2|Xs]) :- 305 !, 306 compare(R2, Item, X2), 307 ( R2 = (>) -> ord_memberchk(Item, Xs) 308 ; R2 = (<) -> Item == X1 309 ;/* R2 = (=) */ true 310 ). 311ord_memberchk(Item, [X1]) :- 312 Item == X1. 313 314 315%! ord_subset(+Sub, +Super) is semidet. 316% 317% Is true if all elements of Sub are in Super 318 319ord_subset([], _). 320ord_subset([H1|T1], [H2|T2]) :- 321 compare(Order, H1, H2), 322 ord_subset_(Order, H1, T1, T2). 323 324ord_subset_(>, H1, T1, [H2|T2]) :- 325 compare(Order, H1, H2), 326 ord_subset_(Order, H1, T1, T2). 327ord_subset_(=, _, T1, T2) :- 328 ord_subset(T1, T2). 329 330 331%! ord_subtract(+InOSet, +NotInOSet, -Diff) is det. 332% 333% Diff is the set holding all elements of InOSet that are not in 334% NotInOSet. 335 336ord_subtract(InOSet, NotInOSet, Diff) :- 337 oset_diff(InOSet, NotInOSet, Diff). 338 339 340%! ord_union(+SetOfSets, -Union) is det. 341% 342% True if Union is the union of all elements in the superset 343% SetOfSets. Each member of SetOfSets must be an ordered set, the 344% sets need not be ordered in any way. 345% 346% @author Copied from YAP, probably originally by Richard O'Keefe. 347 348ord_union([], []). 349ord_union([Set|Sets], Union) :- 350 length([Set|Sets], NumberOfSets), 351 ord_union_all(NumberOfSets, [Set|Sets], Union, []). 352 353ord_union_all(N, Sets0, Union, Sets) :- 354 ( N =:= 1 355 -> Sets0 = [Union|Sets] 356 ; N =:= 2 357 -> Sets0 = [Set1,Set2|Sets], 358 ord_union(Set1,Set2,Union) 359 ; A is N>>1, 360 Z is N-A, 361 ord_union_all(A, Sets0, X, Sets1), 362 ord_union_all(Z, Sets1, Y, Sets), 363 ord_union(X, Y, Union) 364 ). 365 366 367%! ord_union(+Set1, +Set2, ?Union) is det. 368% 369% Union is the union of Set1 and Set2 370 371ord_union(Set1, Set2, Union) :- 372 oset_union(Set1, Set2, Union). 373 374 375%! ord_union(+Set1, +Set2, -Union, -New) is det. 376% 377% True iff ord_union(Set1, Set2, Union) and 378% ord_subtract(Set2, Set1, New). 379 380ord_union([], Set2, Set2, Set2). 381ord_union([H|T], Set2, Union, New) :- 382 ord_union_1(Set2, H, T, Union, New). 383 384ord_union_1([], H, T, [H|T], []). 385ord_union_1([H2|T2], H, T, Union, New) :- 386 compare(Order, H, H2), 387 ord_union(Order, H, T, H2, T2, Union, New). 388 389ord_union(<, H, T, H2, T2, [H|Union], New) :- 390 ord_union_2(T, H2, T2, Union, New). 391ord_union(>, H, T, H2, T2, [H2|Union], [H2|New]) :- 392 ord_union_1(T2, H, T, Union, New). 393ord_union(=, H, T, _, T2, [H|Union], New) :- 394 ord_union(T, T2, Union, New). 395 396ord_union_2([], H2, T2, [H2|T2], [H2|T2]). 397ord_union_2([H|T], H2, T2, Union, New) :- 398 compare(Order, H, H2), 399 ord_union(Order, H, T, H2, T2, Union, New). 400 401 402%! ord_symdiff(+Set1, +Set2, ?Difference) is det. 403% 404% Is true when Difference is the symmetric difference of Set1 and 405% Set2. I.e., Difference contains all elements that are not in the 406% intersection of Set1 and Set2. The semantics is the same as the 407% sequence below (but the actual implementation requires only a 408% single scan). 409% 410% == 411% ord_union(Set1, Set2, Union), 412% ord_intersection(Set1, Set2, Intersection), 413% ord_subtract(Union, Intersection, Difference). 414% == 415% 416% For example: 417% 418% == 419% ?- ord_symdiff([1,2], [2,3], X). 420% X = [1,3]. 421% == 422 423ord_symdiff([], Set2, Set2). 424ord_symdiff([H1|T1], Set2, Difference) :- 425 ord_symdiff(Set2, H1, T1, Difference). 426 427ord_symdiff([], H1, T1, [H1|T1]). 428ord_symdiff([H2|T2], H1, T1, Difference) :- 429 compare(Order, H1, H2), 430 ord_symdiff(Order, H1, T1, H2, T2, Difference). 431 432ord_symdiff(<, H1, Set1, H2, T2, [H1|Difference]) :- 433 ord_symdiff(Set1, H2, T2, Difference). 434ord_symdiff(=, _, T1, _, T2, Difference) :- 435 ord_symdiff(T1, T2, Difference). 436ord_symdiff(>, H1, T1, H2, Set2, [H2|Difference]) :- 437 ord_symdiff(Set2, H1, T1, Difference)