% 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]).