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

 oset_is(+OSet)

check that OSet in correct format (standard order)

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

 oset_union(+OSet1, +OSet2, -Union)

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

 oset_int(+OSet1, +OSet2, -Int)

ordered set intersection

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

 oset_diff(+InOSet, +NotInOSet, -Diff)

ordered set difference

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

 oset_dunion(+SetofSets, -DUnion)

distributed union

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

 oset_dint(+SetofSets, -DInt)

distributed intersection

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

 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.

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

 oset_addel(+Set, +El, -Add)

ordered set element addition

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

 oset_delel(+Set, +El, -Del)

ordered set element deletion

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