code.delx.au - gnu-emacs/blob - test/manual/etags/prol-src/ordsets.prolog

   1 /* Copyright(C) 1988, Swedish Institute of Computer Science */
   2
   3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   4 %   File   : ORDSETS.PL                                                       %
   5 %   Author : Lena Flood                                                       %
   6 %   Updated: 9 September 1988                                                 %
   7 %   Purpose: Ordered set manipulation utilities                               %
   8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   9
  10 :- module(ordsets, [
  11         is_ordset/1,
  12         list_to_ord_set/2,
  13         ord_add_element/3,
  14         ord_del_element/3,
  15         ord_disjoint/2,
  16         ord_intersect/2,
  17         ord_intersection/3,
  18         ord_intersection/4,
  19         ord_intersection/2,
  20         ord_member/2,
  21         ord_seteq/2,
  22         ord_setproduct/3,
  23         ord_subset/2,
  24         ord_subtract/3,
  25         ord_symdiff/3,
  26         ord_union/3,
  27         ord_union/4,
  28         ord_union/2
  29                    ]).
  30
  31 %   Adapted from shared code written by Richard A O'Keefe.
  32
  33 %   In this package, sets are represented by ordered lists with no
  34 %   duplicates.  Thus {c,r,a,f,t} would be [a,c,f,r,t].  The ordering
  35 %   is defined by the @< family of term comparison predicates, which
  36 %   is the ordering used by sort/2 and setof/3.
  37
  38 %   The benefit of the ordered representation is that the elementary
  39 %   set operations can be done in time proportional to the Sum of the
  40 %   argument sizes rather than their Product.
  41
  42
  43
  44 %   is_ordset(+Set)
  45 %   is true when Set is an ordered set.
  46
  47 is_ordset(X) :- var(X), !, fail.
  48 is_ordset([]).
  49 is_ordset([Head|Tail]) :-
  50         is_ordset(Tail, Head).
  51
  52 is_ordset(X, _) :- var(X), !, fail.
  53 is_ordset([], _).
  54 is_ordset([Head|Tail], Left) :-
  55         Left @< Head,
  56         is_ordset(Tail, Head).
  57
  58
  59 %   list_to_ord_set(+List, ?Set)
  60 %   is true when Set is the ordered representation of the set represented
  61 %   by the unordered representation List.
  62
  63 list_to_ord_set(List, Set) :-
  64         sort(List, Set).
  65
  66
  67 %   ord_add_element(+Set1, +Element -Set2)
  68 %   is true when Set2 is Set1 with Element inserted in it, preserving
  69 %   the order.
  70
  71 ord_add_element([], Element, [Element]).
  72 ord_add_element([Head|Tail], Element, Set) :-
  73         compare(Order, Head, Element),
  74         ord_add_element(Order, Head, Tail, Element, Set).
  75
  76 ord_add_element(<, Head, Tail, Element, [Head|Set]) :-
  77         ord_add_element(Tail, Element, Set).
  78 ord_add_element(=, Head, Tail, _, [Head|Tail]).
  79 ord_add_element(>, Head, Tail, Element, [Element,Head|Tail]).
  80
  81
  82 %   ord_del_element(+Set1, +Element, ?Set2)
  83 %   is true when Set2 is Set1 but with Element removed.
  84
  85 ord_del_element([], _, []).
  86 ord_del_element([Head|Tail], Element, Set) :-
  87         compare(Order, Head, Element),
  88         ord_del_element(Order, Head, Tail, Element, Set).
  89
  90 ord_del_element(<, Head, Tail, Element, [Head|Set]) :-
  91         ord_del_element(Tail, Element, Set).
  92 ord_del_element(=, _, Tail, _, Tail).
  93 ord_del_element(>, Head, Tail, _, [Head|Tail]).
  94
  95
  96
  97 %   ord_disjoint(+Set1, +Set2)
  98 %   is true when the two ordered sets have no element in common.
  99
 100 ord_disjoint(Set1, Set2) :-
 101         \+ ord_intersect(Set1, Set2).
 102
 103
 104
 105 %   ord_intersect(+Set1, +Set2)
 106 %   is true when the two ordered sets have at least one element in common.
 107
 108 ord_intersect([Head1|Tail1], [Head2|Tail2]) :-
 109         compare(Order, Head1, Head2),
 110         ord_intersect(Order, Head1, Tail1, Head2, Tail2).
 111
 112 ord_intersect(<, _, [Head1|Tail1], Head2, Tail2) :-
 113         compare(Order, Head1, Head2),
 114         ord_intersect(Order, Head1, Tail1, Head2, Tail2).
 115 ord_intersect(=, _, _, _, _).
 116 ord_intersect(>, Head1, Tail1, _, [Head2|Tail2]) :-
 117         compare(Order, Head1, Head2),
 118         ord_intersect(Order, Head1, Tail1, Head2, Tail2).
 119
 120
 121
 122 %   ord_intersection(+Set1, +Set2, ?Intersection)
 123 %   is true when Intersection is the intersecton of Set1
 124 %   and Set2, provided that Set1 and Set2 are ordered sets.
 125
 126 ord_intersection([], _, []).
 127 ord_intersection([Head1|Tail1], Set2, Intersection) :-
 128         ord_intersection3(Set2, Head1, Tail1, Intersection).
 129
 130 ord_intersection3(<, _, Set1, Head2, Tail2, Intersection) :-
 131         ord_intersection3(Set1, Head2, Tail2, Intersection).
 132 ord_intersection3(=, Head, Tail1, _, Tail2, [Head|Intersection]) :-
 133         ord_intersection(Tail1, Tail2, Intersection).
 134 ord_intersection3(>, Head1, Tail1, _, Set2, Intersection) :-
 135         ord_intersection3(Set2, Head1, Tail1, Intersection).
 136
 137 % could be a disjunction, but is used in three places
 138 ord_intersection3([], _, _, []).
 139 ord_intersection3([Head2|Tail2], Head1, Tail1, Intersection) :-
 140         compare(Order, Head1, Head2),
 141         ord_intersection3(Order, Head1, Tail1, Head2, Tail2, Intersection).
 142
 143
 144
 145 %   ord_intersection(+Set1, +Set2, ?Intersection, ?Difference)
 146 %   is true when Intersection is the intersection of Set1 and Set2,
 147 %   and Differens is Set2 \ Set1 (like in ord_union/4),
 148 %    provided that Set1 and Set2 are ordered sets.
 149
 150 ord_intersection([], Set2, [], Set2).
 151 ord_intersection([Head1|Tail1], Set2, Intersection, Difference) :-
 152         ord_intersection4(Set2, Head1, Tail1, Intersection, Difference).
 153
 154 ord_intersection4(<, _, Set1, Head2, Tail2, Intersection, Difference) :-
 155         (   Set1 = [], Intersection = [], Difference = [Head2|Tail2]
 156         ;   Set1 = [Head1|Tail1],
 157             compare(Order, Head1, Head2),
 158             ord_intersection4(Order, Head1, Tail1, Head2, Tail2, Intersection, Difference)
 159         ).
 160 ord_intersection4(=, Head, Tail1, _, Tail2, [Head|Intersection], Difference) :-
 161         ord_intersection(Tail1, Tail2, Intersection, Difference).
 162 ord_intersection4(>, Head1, Tail1, Head2, Set2, Intersection, [Head2|Difference]) :-
 163         ord_intersection4(Set2, Head1, Tail1, Intersection, Difference).
 164
 165 ord_intersection4([], _, _, [], []).
 166 ord_intersection4([Head2|Tail2], Head1, Tail1, Intersection, Difference) :-
 167         compare(Order, Head1, Head2),
 168         ord_intersection4(Order, Head1, Tail1, Head2, Tail2, Intersection, Difference).
 169
 170
 171
 172 %   ord_intersection(+Sets, ?Intersection)
 173 %   is true when Intersection is the ordered set representation of the
 174 %   intersection of all the sets in Sets.
 175
 176 ord_intersection(Sets, Intersection) :-
 177         length(Sets, NumberOfSets),
 178         NumberOfSets > 0,
 179         ord_intersection2(NumberOfSets, Sets, Intersection, []).
 180
 181 ord_intersection2(1, [Set|Sets], Set0, Sets0) :- !,
 182         Set = Set0,
 183         Sets = Sets0.
 184 ord_intersection2(2, [Set,Set2|Sets], Intersection, Sets0) :- !,
 185         Sets = Sets0,
 186         ord_intersection2(Set, Set2, Intersection).
 187 ord_intersection2(N, Sets0, Intersection, Sets) :-
 188 %       N > 2,
 189         A is N>>1,
 190         Z is N-A,
 191         ord_intersection2(A, Sets0, X, Sets1),
 192         ord_intersection2(Z, Sets1, Y, Sets),
 193         ord_intersection(X, Y, Intersection).
 194
 195
 196
 197 %   ord_member(+Elt, +Set)
 198 %   is true when Elt is a member of Set.  Suggested by Mark Johnson.
 199
 200 ord_member(X, [E|Es]) :-
 201         compare(C, X, E),
 202         ord_member(C, X, Es).
 203
 204 ord_member(=, _X, _Es).
 205 ord_member(>, X, [E|Es]) :-
 206         compare(C, X, E),
 207         ord_member(C, X, Es).
 208
 209
 210
 211 %   ord_seteq(+Set1, +Set2)
 212 %   is true when the two arguments represent the same set.  Since they
 213 %   are assumed to be ordered representations, they must be identical.
 214
 215
 216 ord_seteq(Set1, Set2) :-
 217         Set1 == Set2.
 218
 219
 220 %   ord_setproduct(+Set1, +Set2, ?SetProduct)
 221 %   is true when SetProduct is the cartesian product of Set1 and Set2. The
 222 %   product is represented as pairs Elem1-Elem2, where Elem1 is an element
 223 %   from Set1 and Elem2 is an element from Set2.
 224
 225 ord_setproduct([], _, []).
 226 ord_setproduct([Head|Tail], Set, SetProduct)  :-
 227         ord_setproduct(Set, Head, SetProduct, Rest),
 228         ord_setproduct(Tail, Set, Rest).
 229
 230 ord_setproduct([], _, Set, Set).
 231 ord_setproduct([Head|Tail], X, [X-Head|TailX], Tl) :-
 232         ord_setproduct(Tail, X, TailX, Tl).
 233
 234
 235
 236 %   ord_subset(+Set1, +Set2)
 237 %   is true when every element of the ordered set Set1 appears in the
 238 %   ordered set Set2.
 239
 240 ord_subset([], _).
 241 ord_subset([Head1|Tail1], [Head2|Tail2]) :-
 242         compare(Order, Head1, Head2),
 243         ord_subset(Order, Head1, Tail1, Tail2).
 244
 245 ord_subset(=, _, Tail1, Tail2) :-
 246         ord_subset(Tail1, Tail2).
 247 ord_subset(>, Head1, Tail1, [Head2|Tail2]) :-
 248         compare(Order, Head1, Head2),
 249         ord_subset(Order, Head1, Tail1, Tail2).
 250
 251
 252
 253 %   ord_subtract(+Set1, +Set2, ?Difference)
 254 %   is true when Difference contains all and only the elements of Set1
 255 %   which are not also in Set2, i.e. Set1 \ Set2.
 256
 257 ord_subtract(Set1, Set2, Union) :-
 258         prolog:subtract(Set1, Set2, Union).
 259
 260
 261
 262 %   ord_symdiff(+Set1, +Set2, ?Difference)
 263 %   is true when Difference is the symmetric difference of Set1 and Set2.
 264
 265 ord_symdiff([], Set2, Set2).
 266 ord_symdiff([Head1|Tail1], Set2, Symdiff) :-
 267         ord_symdiff(Set2, Head1, Tail1, Symdiff).
 268
 269 ord_symdiff(<, Head1, Set1, Head2, Tail2, [Head1|Symdiff]) :-
 270         ord_symdiff(Set1, Head2, Tail2, Symdiff).
 271 ord_symdiff(=, _, Tail1, _, Tail2, Symdiff) :-
 272         ord_symdiff(Tail1, Tail2, Symdiff).
 273 ord_symdiff(>, Head1, Tail1, Head2, Set2, [Head2|Symdiff]) :-
 274         ord_symdiff(Set2, Head1, Tail1, Symdiff).
 275
 276 % could be a disjunction, but is used in three places
 277 ord_symdiff([], Head1, Tail1, [Head1|Tail1]).
 278 ord_symdiff([Head2|Tail2], Head1, Tail1, Symdiff) :-
 279         compare(Order, Head1, Head2),
 280         ord_symdiff(Order, Head1, Tail1, Head2, Tail2, Symdiff).
 281
 282
 283
 284 %   ord_union(+Set1, +Set2, ?Union)
 285 %   is true when Union is the union of Set1 and Set2.  Note that when
 286 %   something occurs in both sets, we want to retain only one copy.
 287
 288 ord_union(Set1, Set2, Union) :-
 289         prolog:merge(Set1, Set2, Union).
 290
 291
 292
 293 %   ord_union(+Set1, +Set2, ?Union, ?New)
 294 %   is true when Union is the union of Set1 and Set2, and New is
 295 %   Set2 \ Set1.  This is useful if you
 296 %   are accumulating members of a set and you want to process new
 297 %   elements as they are added to the set.
 298
 299 ord_union([], Set2, Set2, Set2).
 300 ord_union([Head1|Tail1], Set2, Union, Difference) :-
 301         ord_union4(Set2, Head1, Tail1, Union, Difference).
 302
 303 ord_union4(<, Head, Set1, Head2, Tail2, [Head|Union], Difference) :-
 304         (   Set1 = [], Union = [Head2|Tail2], Difference = [Head2|Tail2]
 305         ;   Set1 = [Head1|Tail1],
 306             compare(Order, Head1, Head2),
 307             ord_union4(Order, Head1, Tail1, Head2, Tail2, Union, Difference)
 308         ).
 309 ord_union4(=, Head, Tail1, _, Tail2, [Head|Union], Difference) :-
 310         ord_union(Tail1, Tail2, Union, Difference).
 311 ord_union4(>, Head1, Tail1, Head2, Set2, [Head2|Union], [Head2|Difference]) :-
 312         ord_union4(Set2, Head1, Tail1, Union, Difference).
 313
 314 ord_union4([], Head1, Tail1, [Head1|Tail1], []).
 315 ord_union4([Head2|Tail2], Head1, Tail1, Union, Difference) :-
 316         compare(Order, Head1, Head2),
 317         ord_union4(Order, Head1, Tail1, Head2, Tail2, Union, Difference).
 318
 319
 320
 321 %   ord_union(+Sets, ?Union)
 322 %   is true when Union is the union of all the sets in Sets.
 323
 324 ord_union([], Union) :- !, Union = [].
 325 ord_union(Sets, Union) :-
 326         length(Sets, NumberOfSets),
 327         ord_union_all(NumberOfSets, Sets, Union, []).
 328
 329 ord_union_all(1, [Set|Sets], Set, Sets) :- !.
 330 ord_union_all(2, [Set,Set2|Sets], Union, Sets) :- !,
 331         ord_union(Set, Set2, Union).
 332 ord_union_all(N, Sets0, Union, Sets) :-
 333         A is N>>1,
 334         Z is N-A,
 335         ord_union_all(A, Sets0, X, Sets1),
 336         ord_union_all(Z, Sets1, Y, Sets),
 337         ord_union(X, Y, Union).