/usr/lib/swi-prolog/library/oset.pl is in swi-prolog-nox 7.2.3+dfsg-6.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 | % Filename: oset.pl
% Author--: Jon Jagger, J.R.Jagger@shu.ac.uk
% Created-: 05/03/93
% Version-: 1.0
% Updates-: Mon Oct 21 12:39:41 1996
% Fix in oset_int/3 by Robert van Engelen.
% Notes---: This file provides some basic set manipulation
% predicates. The representation of the sets is
% assumed to be ordered with no duplication. You
% can create an ordered set from a free form list
% by using the sort/2 predicate. The advantage of
% using an ordered representation is that the algorithms
% are order sum of the sizes of the operands, rather than
% product of the sizes of the operands.
%
% I have tried to make all the predicates as efficient as
% possible with respect to first argument indexing, and tail
% clause determinacy.
%
% These routines are provided as is, with no guarantees.
% They have undergone minimal testing.
:- module(oset, [ oset_is/1,
oset_union/3,
oset_int/3,
oset_diff/3,
oset_dint/2,
oset_dunion/2,
oset_addel/3,
oset_delel/3,
oset_power/2
]).
/** <module> Ordered set manipulation
This library defines set operations on sets represented as ordered
lists.
@author Jon Jagger
@deprecated Use the de-facto library ordsets.pl
*/
%% oset_is(+OSet)
% check that OSet in correct format (standard order)
oset_is(-) :- !, fail. % var filter
oset_is([]).
oset_is([H|T]) :-
oset_is(T, H).
oset_is(-, _) :- !, fail. % var filter
oset_is([], _H).
oset_is([H|T], H0) :-
H0 @< H, % use standard order
oset_is(T, H).
%% oset_union(+OSet1, +OSet2, -Union).
oset_union([], Union, Union).
oset_union([H1|T1], L2, Union) :-
union2(L2, H1, T1, Union).
union2([], H1, T1, [H1|T1]).
union2([H2|T2], H1, T1, Union) :-
compare(Order, H1, H2),
union3(Order, H1, T1, H2, T2, Union).
union3(<, H1, T1, H2, T2, [H1|Union]) :-
union2(T1, H2, T2, Union).
union3(=, H1, T1, _H2, T2, [H1|Union]) :-
oset_union(T1, T2, Union).
union3(>, H1, T1, H2, T2, [H2|Union]) :-
union2(T2, H1, T1, Union).
%% oset_int(+OSet1, +OSet2, -Int)
% ordered set intersection
oset_int([], _Int, []).
oset_int([H1|T1], L2, Int) :-
isect2(L2, H1, T1, Int).
isect2([], _H1, _T1, []).
isect2([H2|T2], H1, T1, Int) :-
compare(Order, H1, H2),
isect3(Order, H1, T1, H2, T2, Int).
isect3(<, _H1, T1, H2, T2, Int) :-
isect2(T1, H2, T2, Int).
isect3(=, H1, T1, _H2, T2, [H1|Int]) :-
oset_int(T1, T2, Int).
isect3(>, H1, T1, _H2, T2, Int) :-
isect2(T2, H1, T1, Int).
%% oset_diff(+InOSet, +NotInOSet, -Diff)
% ordered set difference
oset_diff([], _Not, []).
oset_diff([H1|T1], L2, Diff) :-
diff21(L2, H1, T1, Diff).
diff21([], H1, T1, [H1|T1]).
diff21([H2|T2], H1, T1, Diff) :-
compare(Order, H1, H2),
diff3(Order, H1, T1, H2, T2, Diff).
diff12([], _H2, _T2, []).
diff12([H1|T1], H2, T2, Diff) :-
compare(Order, H1, H2),
diff3(Order, H1, T1, H2, T2, Diff).
diff3(<, H1, T1, H2, T2, [H1|Diff]) :-
diff12(T1, H2, T2, Diff).
diff3(=, _H1, T1, _H2, T2, Diff) :-
oset_diff(T1, T2, Diff).
diff3(>, H1, T1, _H2, T2, Diff) :-
diff21(T2, H1, T1, Diff).
%% oset_dunion(+SetofSets, -DUnion)
% distributed union
oset_dunion([], []).
oset_dunion([H|T], DUnion) :-
oset_dunion(T, H, DUnion).
oset_dunion([], DUnion, DUnion).
oset_dunion([H|T], DUnion0, DUnion) :-
oset_union(H, DUnion0, DUnion1),
oset_dunion(T, DUnion1, DUnion).
%% oset_dint(+SetofSets, -DInt)
% distributed intersection
oset_dint([], []).
oset_dint([H|T], DInt) :-
dint(T, H, DInt).
dint([], DInt, DInt).
dint([H|T], DInt0, DInt) :-
oset_int(H, DInt0, DInt1),
dint(T, DInt1, DInt).
%% oset_power(+Set, -PSet)
%
% True when PSet is the powerset of Set. That is, Pset is a set of
% all subsets of Set, where each subset is a proper ordered set.
oset_power(S, PSet) :-
reverse(S, R),
pset(R, [[]], PSet0),
sort(PSet0, PSet).
% The powerset of a set is the powerset of a set of one smaller,
% together with the set of one smaller where each subset is extended
% with the new element. Note that this produces the elements of the set
% in reverse order. Hence the reverse in oset_power/2.
pset([], PSet, PSet).
pset([H|T], PSet0, PSet) :-
happ(PSet0, H, PSet1),
pset(T, PSet1, PSet).
happ([], _, []).
happ([S|Ss], H, [[H|S],S|Rest]) :-
happ(Ss, H, Rest).
%% oset_addel(+Set, +El, -Add)
% ordered set element addition
oset_addel([], El, [El]).
oset_addel([H|T], El, Add) :-
compare(Order, H, El),
addel(Order, H, T, El, Add).
addel(<, H, T, El, [H|Add]) :-
oset_addel(T, El, Add).
addel(=, H, T, _El, [H|T]).
addel(>, H, T, El, [El,H|T]).
%% oset_delel(+Set, +El, -Del)
% ordered set element deletion
oset_delel([], _El, []).
oset_delel([H|T], El, Del) :-
compare(Order, H, El),
delel(Order, H, T, El, Del).
delel(<, H, T, El, [H|Del]) :-
oset_delel(T, El, Del).
delel(=, _H, T, _El, T).
delel(>, H, T, _El, [H|T]).
|