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