1/*  Part of SWI-Prolog
   2
   3    Author:        Jon Jagger
   4    E-mail:        J.R.Jagger@shu.ac.uk
   5    Copyright (c)  1993-2011, Jon Jagger
   6    All rights reserved.
   7
   8    Redistribution and use in source and binary forms, with or without
   9    modification, are permitted provided that the following conditions
  10    are met:
  11
  12    1. Redistributions of source code must retain the above copyright
  13       notice, this list of conditions and the following disclaimer.
  14
  15    2. Redistributions in binary form must reproduce the above copyright
  16       notice, this list of conditions and the following disclaimer in
  17       the documentation and/or other materials provided with the
  18       distribution.
  19
  20    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31    POSSIBILITY OF SUCH DAMAGE.
  32*/
  33
  34:- module(oset, [  oset_is/1,
  35                    oset_union/3,
  36                    oset_int/3,
  37                    oset_diff/3,
  38                    oset_dint/2,
  39                    oset_dunion/2,
  40                    oset_addel/3,
  41                    oset_delel/3,
  42                    oset_power/2
  43                 ]).
  44
  45
  46/** <module> Ordered set manipulation
  47
  48This library defines set operations on sets represented as ordered
  49lists.
  50
  51@author Jon Jagger
  52@deprecated Use the de-facto library ordsets.pl
  53*/
  54
  55
  56%% oset_is(+OSet)
  57%   check that OSet in correct format (standard order)
  58
  59oset_is(-) :- !, fail.    % var filter
  60oset_is([]).
  61oset_is([H|T]) :-
  62    oset_is(T, H).
  63
  64oset_is(-, _) :- !, fail.  % var filter
  65oset_is([], _H).
  66oset_is([H|T], H0) :-
  67    H0 @< H,               % use standard order
  68    oset_is(T, H).
  69
  70
  71
  72%% oset_union(+OSet1, +OSet2, -Union).
  73
  74oset_union([], Union, Union).
  75oset_union([H1|T1], L2, Union) :-
  76    union2(L2, H1, T1, Union).
  77
  78union2([], H1, T1, [H1|T1]).
  79union2([H2|T2], H1, T1, Union) :-
  80    compare(Order, H1, H2),
  81    union3(Order, H1, T1, H2, T2, Union).
  82
  83union3(<, H1, T1,  H2, T2, [H1|Union]) :-
  84    union2(T1, H2, T2, Union).
  85union3(=, H1, T1, _H2, T2, [H1|Union]) :-
  86    oset_union(T1, T2, Union).
  87union3(>, H1, T1,  H2, T2, [H2|Union]) :-
  88    union2(T2, H1, T1, Union).
  89
  90
  91%% oset_int(+OSet1, +OSet2, -Int)
  92%   ordered set intersection
  93
  94oset_int([], _Int, []).
  95oset_int([H1|T1], L2, Int) :-
  96    isect2(L2, H1, T1, Int).
  97
  98isect2([], _H1, _T1, []).
  99isect2([H2|T2], H1, T1, Int) :-
 100    compare(Order, H1, H2),
 101    isect3(Order, H1, T1, H2, T2, Int).
 102
 103isect3(<, _H1, T1,  H2, T2, Int) :-
 104    isect2(T1, H2, T2, Int).
 105isect3(=, H1, T1, _H2, T2, [H1|Int]) :-
 106    oset_int(T1, T2, Int).
 107isect3(>, H1, T1,  _H2, T2, Int) :-
 108    isect2(T2, H1, T1, Int).
 109
 110
 111%% oset_diff(+InOSet, +NotInOSet, -Diff)
 112%   ordered set difference
 113
 114oset_diff([], _Not, []).
 115oset_diff([H1|T1], L2, Diff) :-
 116    diff21(L2, H1, T1, Diff).
 117
 118diff21([], H1, T1, [H1|T1]).
 119diff21([H2|T2], H1, T1, Diff) :-
 120    compare(Order, H1, H2),
 121    diff3(Order, H1, T1, H2, T2, Diff).
 122
 123diff12([], _H2, _T2, []).
 124diff12([H1|T1], H2, T2, Diff) :-
 125    compare(Order, H1, H2),
 126    diff3(Order, H1, T1, H2, T2, Diff).
 127
 128diff3(<,  H1, T1,  H2, T2, [H1|Diff]) :-
 129    diff12(T1, H2, T2, Diff).
 130diff3(=, _H1, T1, _H2, T2, Diff) :-
 131    oset_diff(T1, T2, Diff).
 132diff3(>,  H1, T1, _H2, T2, Diff) :-
 133    diff21(T2, H1, T1, Diff).
 134
 135
 136%% oset_dunion(+SetofSets, -DUnion)
 137%   distributed union
 138
 139oset_dunion([], []).
 140oset_dunion([H|T], DUnion) :-
 141    oset_dunion(T, H, DUnion).
 142
 143oset_dunion([], DUnion, DUnion).
 144oset_dunion([H|T], DUnion0, DUnion) :-
 145    oset_union(H, DUnion0, DUnion1),
 146    oset_dunion(T, DUnion1, DUnion).
 147
 148
 149%% oset_dint(+SetofSets, -DInt)
 150%   distributed intersection
 151
 152oset_dint([], []).
 153oset_dint([H|T], DInt) :-
 154    dint(T, H, DInt).
 155
 156dint([], DInt, DInt).
 157dint([H|T], DInt0, DInt) :-
 158    oset_int(H, DInt0, DInt1),
 159    dint(T, DInt1, DInt).
 160
 161
 162%!  oset_power(+Set, -PSet)
 163%
 164%   True when PSet is the powerset of Set. That is, Pset is a set of
 165%   all subsets of Set, where each subset is a proper ordered set.
 166
 167oset_power(S, PSet) :-
 168    reverse(S, R),
 169    pset(R, [[]], PSet0),
 170    sort(PSet0, PSet).
 171
 172% The powerset of a set  is  the  powerset   of  a  set  of one smaller,
 173% together with the set of one  smaller   where  each subset is extended
 174% with the new element.  Note that this produces the elements of the set
 175% in reverse order.  Hence the reverse in oset_power/2.
 176
 177pset([], PSet, PSet).
 178pset([H|T], PSet0, PSet) :-
 179    happ(PSet0, H, PSet1),
 180    pset(T, PSet1, PSet).
 181
 182happ([], _, []).
 183happ([S|Ss], H, [[H|S],S|Rest]) :-
 184    happ(Ss, H, Rest).
 185
 186
 187
 188%% oset_addel(+Set, +El, -Add)
 189%   ordered set element addition
 190
 191oset_addel([], El, [El]).
 192oset_addel([H|T], El, Add) :-
 193    compare(Order, H, El),
 194    addel(Order, H, T, El, Add).
 195
 196addel(<, H, T,  El, [H|Add]) :-
 197    oset_addel(T, El, Add).
 198addel(=, H, T, _El, [H|T]).
 199addel(>, H, T,  El, [El,H|T]).
 200
 201
 202%% oset_delel(+Set, +El, -Del)
 203%   ordered set element deletion
 204
 205oset_delel([], _El, []).
 206oset_delel([H|T], El, Del) :-
 207    compare(Order, H, El),
 208    delel(Order, H, T, El, Del).
 209
 210delel(<,  H, T,  El, [H|Del]) :-
 211    oset_delel(T, El, Del).
 212delel(=, _H, T, _El, T).
 213delel(>,  H, T, _El, [H|T]).