1/*  Part of SWI-Prolog
    2
    3    WWW:           http://www.swi-prolog.org
    4    Copyright (c)  2021, SWI-Prolog Solutions b.v.
    5    All rights reserved.
    6
    7    Redistribution and use in source and binary forms, with or without
    8    modification, are permitted provided that the following conditions
    9    are met:
   10
   11    1. Redistributions of source code must retain the above copyright
   12       notice, this list of conditions and the following disclaimer.
   13
   14    2. Redistributions in binary form must reproduce the above copyright
   15       notice, this list of conditions and the following disclaimer in
   16       the documentation and/or other materials provided with the
   17       distribution.
   18
   19    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   20    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   21    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   22    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   23    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   24    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   25    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   26    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   27    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   28    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   29    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   30    POSSIBILITY OF SUCH DAMAGE.
   31*/
   32
   33:- module(sets,
   34	  [ add_element/3,		% +Element, +Set1, -Set2
   35	    del_element/3,		% +Element, +Set1, -Set2
   36	    disjoint/2,			% +Set1, +Set2
   37	    intersect/2,		% +Set1, +Set2
   38	    set_order/3,		% +Xs, +Ys, -R
   39	    seteq/2,			% +Set1, +Set2
   40	    list_to_set/2,		% +List, -Set
   41	    disjoint_union/3,		% +Set1, +Set2, -Union
   42	    union/4			% +Set1, +Set2, -Union, -Difference
   43	  ]).   44:- reexport(library(lists),
   45	    [ is_set/1,
   46	      subset/2,
   47	      intersection/3,
   48	      subtract/3,
   49	      union/3
   50	    ]).   51:- use_module(library(lists), [selectchk/3]).   52
   53/** <module> SICStus 4 library(sets).
   54
   55@tbd	This library is incomplete.
   56	As of SICStus 4.6.0, the following predicates are missing:
   57
   58	* pairfrom/4
   59	* power_set/2
   60	* intersection/2
   61	* symdiff/3
   62	* setproduct/3
   63	* union/2
   64
   65@see	https://sicstus.sics.se/sicstus/docs/4.6.0/html/sicstus.html/lib_002dsets.html
   66*/
   67
   68add_element(Element, Set1, Set2) :-
   69	(   memberchk(Element, Set1)
   70	->  Set2 = Set1
   71	;   Set2 = [Element|Set1]
   72	).
   73
   74del_element(Element, Set1, Set2) :-
   75	(   selectchk(Element, Set1, Set2)
   76	->  true
   77	;   Set2 = Set1
   78	).
   79
   80disjoint(Set1, Set2) :-
   81	intersection(Set1, Set2, []).
   82
   83intersect(Set1, Set2) :-
   84	intersection(Set1, Set2, Intersection),
   85	Intersection \= [].
   86
   87set_order(Xs, Ys, R) :-
   88	(   subset(Xs, Ys)
   89	->  (   subset(Ys, Xs)
   90	    ->  R = (=)
   91	    ;   R = (<)
   92	    )
   93	;   (   subset(Ys, Xs)
   94	    ->  R = (>)
   95	    ;   fail
   96	    )
   97	).
   98
   99seteq(Set1, Set2) :- set_order(Set1, Set2, =).
  100
  101%%	list_to_set(+List, -Set) is det.
  102%
  103%	Set is List with all duplicates removed. Duplicates are removed
  104%	by unification. This is not the same as SWI-Prolog's
  105%	list_to_set/2 in library(lists), which finds duplicates based on
  106%	term equality (==).
  107%
  108%	@compat SICStus 4
  109
  110list_to_set([], []).
  111list_to_set([X|Tail], Set) :-
  112	(   memberchk(X, Tail)
  113	->  Set = SetTail
  114	;   Set = [X|SetTail]
  115	),
  116	list_to_set(Tail, SetTail).
  117
  118disjoint_union(Set1, Set2, Union) :-
  119	disjoint(Set1, Set2),
  120	append(Set1, Set2, Union).
  121
  122union(Set1, Set2, Union, Difference) :-
  123	union(Set1, Set2, Union),
  124	subtract(Set1, Set2, Difference)