1/*  Part of SWI-Prolog
    2
    3    Author:        Jan Wielemaker and Jon Jagger
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c)  2001-2021, University of Amsterdam
    7                              VU University Amsterdam
    8                              SWI-Prolog Solutions b.v.
    9    All rights reserved.
   10
   11    Redistribution and use in source and binary forms, with or without
   12    modification, are permitted provided that the following conditions
   13    are met:
   14
   15    1. Redistributions of source code must retain the above copyright
   16       notice, this list of conditions and the following disclaimer.
   17
   18    2. Redistributions in binary form must reproduce the above copyright
   19       notice, this list of conditions and the following disclaimer in
   20       the documentation and/or other materials provided with the
   21       distribution.
   22
   23    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   24    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   25    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   26    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   27    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   28    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   29    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   30    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   31    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   32    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   33    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   34    POSSIBILITY OF SUCH DAMAGE.
   35*/
   36
   37:- module(ordsets,
   38          [ is_ordset/1,                % @Term
   39            list_to_ord_set/2,          % +List, -OrdSet
   40            ord_add_element/3,          % +Set, +Element, -NewSet
   41            ord_del_element/3,          % +Set, +Element, -NewSet
   42            ord_selectchk/3,            % +Item, ?Set1, ?Set2
   43            ord_intersect/2,            % +Set1, +Set2 (test non-empty)
   44            ord_intersect/3,            % +Set1, +Set2, -Intersection
   45            ord_intersection/3,         % +Set1, +Set2, -Intersection
   46            ord_intersection/4,         % +Set1, +Set2, -Intersection, -Diff
   47            ord_disjoint/2,             % +Set1, +Set2
   48            ord_subtract/3,             % +Set, +Delete, -Remaining
   49            ord_union/2,                % +SetOfOrdSets, -Set
   50            ord_union/3,                % +Set1, +Set2, -Union
   51            ord_union/4,                % +Set1, +Set2, -Union, -New
   52            ord_subset/2,               % +Sub, +Super (test Sub is in Super)
   53                                        % Non-Quintus extensions
   54            ord_empty/1,                % ?Set
   55            ord_memberchk/2,            % +Element, +Set,
   56            ord_range/4,                % +Set, +Min, +Max, -Range
   57            ord_symdiff/3,              % +Set1, +Set2, ?Diff
   58                                        % SICSTus extensions
   59            ord_seteq/2,                % +Set1, +Set2
   60            ord_intersection/2          % +PowerSet, -Intersection
   61          ]).   62:- use_module(library(error)).   63
   64:- set_prolog_flag(generate_debug_info, false).

 is_ordset(@Term) is semidet

True if Term is an ordered set. All predicates in this library expect ordered sets as input arguments. Failing to fullfil this assumption results in undefined behaviour. Typically, ordered sets are created by predicates from this library, sort/2 or setof/3.

  103is_ordset(Term) :-
  104    is_list(Term),
  105    is_ordset2(Term).
  106
  107is_ordset2([]).
  108is_ordset2([H|T]) :-
  109    is_ordset3(T, H).
  110
  111is_ordset3([], _).
  112is_ordset3([H2|T], H) :-
  113    H2 @> H,
  114    is_ordset3(T, H2).

 ord_empty(?List) is semidet

True when List is the empty ordered set. Simply unifies list with the empty list. Not part of Quintus.

  122ord_empty([]).

 ord_seteq(+Set1, +Set2) is semidet

True if Set1 and Set2 have the same elements. As both are canonical sorted lists, this is the same as ==/2.

Compatibility

- sicstus

  132ord_seteq(Set1, Set2) :-
  133    Set1 == Set2.

 list_to_ord_set(+List, -OrdSet) is det

Transform a list into an ordered set. This is the same as sorting the list.

  141list_to_ord_set(List, Set) :-
  142    sort(List, Set).

 ord_intersect(+Set1, +Set2) is semidet

True if both ordered sets have a non-empty intersection.

  149ord_intersect([H1|T1], L2) :-
  150    ord_intersect_(L2, H1, T1).
  151
  152ord_intersect_([H2|T2], H1, T1) :-
  153    compare(Order, H1, H2),
  154    ord_intersect__(Order, H1, T1, H2, T2).
  155
  156ord_intersect__(<, _H1, T1,  H2, T2) :-
  157    ord_intersect_(T1, H2, T2).
  158ord_intersect__(=, _H1, _T1, _H2, _T2).
  159ord_intersect__(>, H1, T1,  _H2, T2) :-
  160    ord_intersect_(T2, H1, T1).

 ord_disjoint(+Set1, +Set2) is semidet

True if Set1 and Set2 have no common elements. This is the negation of ord_intersect/2.

  168ord_disjoint(Set1, Set2) :-
  169    \+ ord_intersect(Set1, Set2).

 ord_intersect(+Set1, +Set2, -Intersection)

Intersection holds the common elements of Set1 and Set2.

deprecated

- Use ord_intersection/3

  178ord_intersect(Set1, Set2, Intersection) :-
  179    ord_intersection(Set1, Set2, Intersection).

 ord_intersection(+PowerSet, -Intersection) is semidet

Intersection of a powerset. True when Intersection is an ordered set holding all elements common to all sets in PowerSet. Fails if PowerSet is an empty list.

Compatibility

- sicstus

  190ord_intersection(PowerSet, Intersection) :-
  191    must_be(list, PowerSet),
  192    key_by_length(PowerSet, Pairs),
  193    keysort(Pairs, [_-S|Sorted]),
  194    l_int(Sorted, S, Intersection).
  195
  196key_by_length([], []).
  197key_by_length([H|T0], [L-H|T]) :-
  198    '$skip_list'(L, H, Tail),
  199    (   Tail == []
  200    ->  key_by_length(T0, T)
  201    ;   type_error(list, H)
  202    ).
  203
  204l_int(_, [], I) =>
  205    I = [].
  206l_int([], S, I) =>
  207    I = S.
  208l_int([_-H|T], S0, S) =>
  209    ord_intersection(S0, H, S1),
  210    l_int(T, S1, S).

 ord_intersection(+Set1, +Set2, -Intersection) is det

Intersection holds the common elements of Set1 and Set2. Uses ord_disjoint/2 if Intersection is bound to [] on entry.

  218ord_intersection(Set1, Set2, Intersection) :-
  219    (   Intersection == []
  220    ->  ord_disjoint(Set1, Set2)
  221    ;   ord_intersection_(Set1, Set2, Intersection)
  222    ).
  223
  224ord_intersection_([], _Int, []).
  225ord_intersection_([H1|T1], L2, Int) :-
  226    isect2(L2, H1, T1, Int).
  227
  228isect2([], _H1, _T1, []).
  229isect2([H2|T2], H1, T1, Int) :-
  230    compare(Order, H1, H2),
  231    isect3(Order, H1, T1, H2, T2, Int).
  232
  233isect3(<, _H1, T1,  H2, T2, Int) :-
  234    isect2(T1, H2, T2, Int).
  235isect3(=, H1, T1, _H2, T2, [H1|Int]) :-
  236    ord_intersection_(T1, T2, Int).
  237isect3(>, H1, T1,  _H2, T2, Int) :-
  238    isect2(T2, H1, T1, Int).

 ord_intersection(+Set1, +Set2, ?Intersection, ?Difference) is det

Intersection and difference between two ordered sets. Intersection is the intersection between Set1 and Set2, while Difference is defined by ord_subtract(Set2, Set1, Difference).

See also

- ord_intersection/3 and ord_subtract/3.

  249ord_intersection([], L, [], L) :- !.
  250ord_intersection([_|_], [], [], []) :- !.
  251ord_intersection([H1|T1], [H2|T2], Intersection, Difference) :-
  252    compare(Diff, H1, H2),
  253    ord_intersection2(Diff, H1, T1, H2, T2, Intersection, Difference).
  254
  255ord_intersection2(=, H1, T1, _H2, T2, [H1|T], Difference) :-
  256    ord_intersection(T1, T2, T, Difference).
  257ord_intersection2(<, _, T1, H2, T2, Intersection, Difference) :-
  258    ord_intersection(T1, [H2|T2], Intersection, Difference).
  259ord_intersection2(>, H1, T1, H2, T2, Intersection, [H2|HDiff]) :-
  260    ord_intersection([H1|T1], T2, Intersection, HDiff).

 ord_add_element(+Set1, +Element, ?Set2) is det

Insert an element into the set. This is the same as ord_union(Set1, [Element], Set2).

  268ord_add_element([], El, [El]).
  269ord_add_element([H|T], El, Add) :-
  270    compare(Order, H, El),
  271    addel(Order, H, T, El, Add).
  272
  273addel(<, H, T,  El, [H|Add]) :-
  274    ord_add_element(T, El, Add).
  275addel(=, H, T, _El, [H|T]).
  276addel(>, H, T,  El, [El,H|T]).

 ord_del_element(+Set, +Element, -NewSet) is det

Delete an element from an ordered set. This is the same as ord_subtract(Set, [Element], NewSet).

  285ord_del_element([], _El, []).
  286ord_del_element([H|T], El, Del) :-
  287    compare(Order, H, El),
  288    delel(Order, H, T, El, Del).
  289
  290delel(<,  H, T,  El, [H|Del]) :-
  291    ord_del_element(T, El, Del).
  292delel(=, _H, T, _El, T).
  293delel(>,  H, T, _El, [H|T]).

 ord_selectchk(+Item, ?Set1, ?Set2) is semidet

Selectchk/3, specialised for ordered sets. Is true when select(Item, Set1, Set2) and Set1, Set2 are both sorted lists without duplicates. This implementation is only expected to work for Item ground and either Set1 or Set2 ground. The "chk" suffix is meant to remind you of memberchk/2, which also expects its first argument to be ground. ord_selectchk(X, S, T) => ord_memberchk(X, S) & \+ ord_memberchk(X, T).

author

- Richard O'Keefe

  308ord_selectchk(Item, [X|Set1], [X|Set2]) :-
  309    X @< Item,
  310    !,
  311    ord_selectchk(Item, Set1, Set2).
  312ord_selectchk(Item, [Item|Set1], Set1) :-
  313    (   Set1 == []
  314    ->  true
  315    ;   Set1 = [Y|_]
  316    ->  Item @< Y
  317    ).

 ord_memberchk(+Element, +OrdSet) is semidet

True if Element is a member of OrdSet, compared using ==. Note that enumerating elements of an ordered set can be done using member/2.

Some Prolog implementations also provide ord_member/2, with the same semantics as ord_memberchk/2. We believe that having a semidet ord_member/2 is unacceptably inconsistent with the *_chk convention. Portable code should use ord_memberchk/2 or member/2.

author

- Richard O'Keefe

  334ord_memberchk(Item, [X1,X2,X3,X4|Xs]) :-
  335    !,
  336    compare(R4, Item, X4),
  337    (   R4 = (>) -> ord_memberchk(Item, Xs)
  338    ;   R4 = (<) ->
  339        compare(R2, Item, X2),
  340        (   R2 = (>) -> Item == X3
  341        ;   R2 = (<) -> Item == X1
  342        ;/* R2 = (=),   Item == X2 */ true
  343        )
  344    ;/* R4 = (=) */ true
  345    ).
  346ord_memberchk(Item, [X1,X2|Xs]) :-
  347    !,
  348    compare(R2, Item, X2),
  349    (   R2 = (>) -> ord_memberchk(Item, Xs)
  350    ;   R2 = (<) -> Item == X1
  351    ;/* R2 = (=) */ true
  352    ).
  353ord_memberchk(Item, [X1]) :-
  354    Item == X1.

 ord_range(+Set, +Min, +Max, -Range) is det

Retrieves a range of elements between Min and Max (inclusive) from a set using standard term comparison.

  361ord_range([X1, X2, X3, X4|Xs], Min, Max, Range) =>
  362    (   X4 @< Min
  363    ->  ord_range(Xs, Min, Max, Range)
  364    ;   (   X2 @< Min
  365        ->  (   X3 @< Min
  366            ->  ord_take([X4 | Xs], Max, Range)
  367            ;   ord_take([X3, X4 | Xs], Max, Range)
  368            )
  369        ;   (   X1 @< Min
  370            ->  ord_take([X2, X3, X4 | Xs], Max, Range)
  371            ;   ord_take([X1, X2, X3, X4 | Xs], Max, Range)
  372            )
  373        )
  374    ).
  375ord_range([X1, X2 | Xs], Min, Max, Range) =>
  376    (   X2 @< Min
  377    ->  ord_range(Xs, Min, Max, Range)
  378    ;   (   X1 @< Min
  379        ->  ord_take([X2 | Xs], Max, Range)
  380        ;   ord_take([X1, X2 | Xs], Max, Range)
  381        )
  382    ).
  383ord_range([X], Min, Max, Range) =>
  384    (   X @>= Min, X @=< Max
  385    -> Range = [X]
  386    ;   Range = []
  387    ).
  388ord_range([], _Min, _Max, Range) =>
  389    Range = [].
  390
  391ord_take([X1, X2, X3, X4|Xs], Max, Range) =>
  392    (   X4 @=< Max
  393    ->  Range = [X1, X2, X3, X4|Rest],
  394        ord_take(Xs, Max, Rest)
  395    ;   (   X2 @=< Max
  396        ->  (   X3 @=< Max
  397            ->  Range = [X1, X2, X3]
  398            ;   Range = [X1, X2]
  399            )
  400        ;   (   X1 @=< Max
  401            ->  Range = [X1]
  402            ;   Range = []
  403            )
  404        )
  405    ).
  406ord_take([X1, X2 | Xs], Max, Range) =>
  407    (   X2 @=< Max
  408    ->  Range = [X1, X2 | Rest],
  409        ord_take(Xs, Max, Rest)
  410    ;   (   X1 @=< Max
  411        ->  Range = [X1]
  412        ;   Range = []
  413        )
  414    ).
  415ord_take([X], Max, Range) =>
  416    (   X @=< Max
  417    ->  Range = [X]
  418    ;   Range = []
  419    ).
  420ord_take([], _Max, Range) =>
  421    Range = [].

 ord_subset(+Sub, +Super) is semidet

Is true if all elements of Sub are in Super

  427ord_subset([], _).
  428ord_subset([H1|T1], [H2|T2]) :-
  429    compare(Order, H1, H2),
  430    ord_subset_(Order, H1, T1, T2).
  431
  432ord_subset_(>, H1, T1, [H2|T2]) :-
  433    compare(Order, H1, H2),
  434    ord_subset_(Order, H1, T1, T2).
  435ord_subset_(=, _, T1, T2) :-
  436    ord_subset(T1, T2).

 ord_subtract(+InOSet, +NotInOSet, -Diff) is det

Diff is the set holding all elements of InOSet that are not in NotInOSet.

  444ord_subtract([], _Not, Diff) =>
  445    Diff = [].
  446ord_subtract(List, [], Diff) =>
  447    Diff = List.
  448ord_subtract([H1|T1], L2, Diff) =>
  449    diff21(L2, H1, T1, Diff).
  450
  451diff21([], H1, T1, [H1|T1]).
  452diff21([H2|T2], H1, T1, Diff) :-
  453    compare(Order, H1, H2),
  454    diff3(Order, H1, T1, H2, T2, Diff).
  455
  456diff12([], _H2, _T2, []).
  457diff12([H1|T1], H2, T2, Diff) :-
  458    compare(Order, H1, H2),
  459    diff3(Order, H1, T1, H2, T2, Diff).
  460
  461diff3(<,  H1, T1,  H2, T2, [H1|Diff]) :-
  462    diff12(T1, H2, T2, Diff).
  463diff3(=, _H1, T1, _H2, T2, Diff) :-
  464    ord_subtract(T1, T2, Diff).
  465diff3(>,  H1, T1, _H2, T2, Diff) :-
  466    diff21(T2, H1, T1, Diff).

 ord_union(+SetOfSets, -Union) is det

True if Union is the union of all elements in the superset SetOfSets. Each member of SetOfSets must be an ordered set, the sets need not be ordered in any way.

author

- Copied from YAP, probably originally by Richard O'Keefe.

  477ord_union([], Union) =>
  478    Union = [].
  479ord_union([Set|Sets], Union) =>
  480    length([Set|Sets], NumberOfSets),
  481    ord_union_all(NumberOfSets, [Set|Sets], Union, []).
  482
  483ord_union_all(N, Sets0, Union, Sets) =>
  484    (   N =:= 1
  485    ->  Sets0 = [Union|Sets]
  486    ;   N =:= 2
  487    ->  Sets0 = [Set1,Set2|Sets],
  488        ord_union(Set1,Set2,Union)
  489    ;   A is N>>1,
  490        Z is N-A,
  491        ord_union_all(A, Sets0, X, Sets1),
  492        ord_union_all(Z, Sets1, Y, Sets),
  493        ord_union(X, Y, Union)
  494    ).

 ord_union(+Set1, +Set2, -Union) is det

Union is the union of Set1 and Set2

  501ord_union([], Set2, Union) =>
  502    Union = Set2.
  503ord_union([H1|T1], L2, Union) =>
  504    union2(L2, H1, T1, Union).
  505
  506union2([], H1, T1, Union) =>
  507    Union = [H1|T1].
  508union2([H2|T2], H1, T1, Union) =>
  509    compare(Order, H1, H2),
  510    union3(Order, H1, T1, H2, T2, Union).
  511
  512union3(<, H1, T1,  H2, T2, Union) =>
  513    Union = [H1|Union0],
  514    union2(T1, H2, T2, Union0).
  515union3(=, H1, T1, _H2, T2, Union) =>
  516    Union = [H1|Union0],
  517    ord_union(T1, T2, Union0).
  518union3(>, H1, T1,  H2, T2, Union) =>
  519    Union = [H2|Union0],
  520    union2(T2, H1, T1, Union0).

 ord_union(+Set1, +Set2, -Union, -New) is det

True iff ord_union(Set1, Set2, Union) and ord_subtract(Set2, Set1, New).

  527ord_union([], Set2, Set2, Set2).
  528ord_union([H|T], Set2, Union, New) :-
  529    ord_union_1(Set2, H, T, Union, New).
  530
  531ord_union_1([], H, T, [H|T], []).
  532ord_union_1([H2|T2], H, T, Union, New) :-
  533    compare(Order, H, H2),
  534    ord_union(Order, H, T, H2, T2, Union, New).
  535
  536ord_union(<, H, T, H2, T2, [H|Union], New) :-
  537    ord_union_2(T, H2, T2, Union, New).
  538ord_union(>, H, T, H2, T2, [H2|Union], [H2|New]) :-
  539    ord_union_1(T2, H, T, Union, New).
  540ord_union(=, H, T, _, T2, [H|Union], New) :-
  541    ord_union(T, T2, Union, New).
  542
  543ord_union_2([], H2, T2, [H2|T2], [H2|T2]).
  544ord_union_2([H|T], H2, T2, Union, New) :-
  545    compare(Order, H, H2),
  546    ord_union(Order, H, T, H2, T2, Union, New).

 ord_symdiff(+Set1, +Set2, ?Difference) is det

Is true when Difference is the symmetric difference of Set1 and Set2. I.e., Difference contains all elements that are not in the intersection of Set1 and Set2. The semantics is the same as the sequence below (but the actual implementation requires only a single scan).

      ord_union(Set1, Set2, Union),
      ord_intersection(Set1, Set2, Intersection),
      ord_subtract(Union, Intersection, Difference).

For example:

?- ord_symdiff([1,2], [2,3], X).
X = [1,3].

  570ord_symdiff([], Set2, Set2).
  571ord_symdiff([H1|T1], Set2, Difference) :-
  572    ord_symdiff(Set2, H1, T1, Difference).
  573
  574ord_symdiff([], H1, T1, [H1|T1]).
  575ord_symdiff([H2|T2], H1, T1, Difference) :-
  576    compare(Order, H1, H2),
  577    ord_symdiff(Order, H1, T1, H2, T2, Difference).
  578
  579ord_symdiff(<, H1, Set1, H2, T2, [H1|Difference]) :-
  580    ord_symdiff(Set1, H2, T2, Difference).
  581ord_symdiff(=, _, T1, _, T2, Difference) :-
  582    ord_symdiff(T1, T2, Difference).
  583ord_symdiff(>, H1, T1, H2, Set2, [H2|Difference]) :-
  584    ord_symdiff(Set2, H1, T1, Difference)