View source with formatted comments or as raw
    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_symdiff/3,              % +Set1, +Set2, ?Diff
   57                                        % SICSTus extensions
   58            ord_seteq/2,                % +Set1, +Set2
   59            ord_intersection/2          % +PowerSet, -Intersection
   60          ]).   61:- use_module(library(error)).   62
   63:- set_prolog_flag(generate_debug_info, false).   64
   65/** <module> Ordered set manipulation
   66
   67Ordered sets are lists with unique elements sorted to the standard order
   68of terms (see sort/2). Exploiting ordering,   many of the set operations
   69can be expressed in order N rather  than N^2 when dealing with unordered
   70sets that may contain duplicates. The library(ordsets) is available in a
   71number of Prolog implementations. Our  predicates   are  designed  to be
   72compatible  with  common  practice   in    the   Prolog  community.  The
   73implementation is incomplete and  relies   partly  on  library(oset), an
   74older ordered set library distributed  with SWI-Prolog. New applications
   75are advised to use library(ordsets).
   76
   77Some  of  these  predicates  match    directly   to  corresponding  list
   78operations. It is advised to use the  versions from this library to make
   79clear you are operating on ordered sets.   An exception is member/2. See
   80ord_memberchk/2.
   81
   82The ordsets library is based  on  the   standard  order  of  terms. This
   83implies it can handle  all  Prolog   terms,  including  variables.  Note
   84however, that the ordering is not stable  if   a  term inside the set is
   85further instantiated. Also  note  that   variable  ordering  changes  if
   86variables in the set are unified with each   other  or a variable in the
   87set is unified with a variable that  is `older' than the newest variable
   88in the set. In  practice,  this  implies   that  it  is  allowed  to use
   89member(X, OrdSet) on an ordered set that holds  variables only if X is a
   90fresh variable. In other cases one should   cease  using it as an ordset
   91because the order it relies on may have been changed.
   92*/
   93
   94%!  is_ordset(@Term) is semidet.
   95%
   96%   True if Term is an ordered set.   All predicates in this library
   97%   expect ordered sets as input arguments.  Failing to fullfil this
   98%   assumption results in undefined   behaviour.  Typically, ordered
   99%   sets are created by predicates  from   this  library,  sort/2 or
  100%   setof/3.
  101
  102is_ordset(Term) :-
  103    is_list(Term),
  104    is_ordset2(Term).
  105
  106is_ordset2([]).
  107is_ordset2([H|T]) :-
  108    is_ordset3(T, H).
  109
  110is_ordset3([], _).
  111is_ordset3([H2|T], H) :-
  112    H2 @> H,
  113    is_ordset3(T, H2).
  114
  115
  116%!  ord_empty(?List) is semidet.
  117%
  118%   True when List is the  empty   ordered  set. Simply unifies list
  119%   with the empty list. Not part of Quintus.
  120
  121ord_empty([]).
  122
  123
  124%!  ord_seteq(+Set1, +Set2) is semidet.
  125%
  126%   True if Set1 and Set2  have  the   same  elements.  As  both are
  127%   canonical sorted lists, this is the same as ==/2.
  128%
  129%   @compat sicstus
  130
  131ord_seteq(Set1, Set2) :-
  132    Set1 == Set2.
  133
  134
  135%!  list_to_ord_set(+List, -OrdSet) is det.
  136%
  137%   Transform a list into an ordered set.  This is the same as
  138%   sorting the list.
  139
  140list_to_ord_set(List, Set) :-
  141    sort(List, Set).
  142
  143
  144%!  ord_intersect(+Set1, +Set2) is semidet.
  145%
  146%   True if both ordered sets have a non-empty intersection.
  147
  148ord_intersect([H1|T1], L2) :-
  149    ord_intersect_(L2, H1, T1).
  150
  151ord_intersect_([H2|T2], H1, T1) :-
  152    compare(Order, H1, H2),
  153    ord_intersect__(Order, H1, T1, H2, T2).
  154
  155ord_intersect__(<, _H1, T1,  H2, T2) :-
  156    ord_intersect_(T1, H2, T2).
  157ord_intersect__(=, _H1, _T1, _H2, _T2).
  158ord_intersect__(>, H1, T1,  _H2, T2) :-
  159    ord_intersect_(T2, H1, T1).
  160
  161
  162%!  ord_disjoint(+Set1, +Set2) is semidet.
  163%
  164%   True if Set1 and Set2  have  no   common  elements.  This is the
  165%   negation of ord_intersect/2.
  166
  167ord_disjoint(Set1, Set2) :-
  168    \+ ord_intersect(Set1, Set2).
  169
  170
  171%!  ord_intersect(+Set1, +Set2, -Intersection)
  172%
  173%   Intersection  holds  the  common  elements  of  Set1  and  Set2.
  174%
  175%   @deprecated Use ord_intersection/3
  176
  177ord_intersect(Set1, Set2, Intersection) :-
  178    ord_intersection(Set1, Set2, Intersection).
  179
  180
  181%!  ord_intersection(+PowerSet, -Intersection) is semidet.
  182%
  183%   Intersection of a powerset. True when Intersection is an ordered set
  184%   holding all elements common  to  all   sets  in  PowerSet.  Fails if
  185%   PowerSet is an empty list.
  186%
  187%   @compat sicstus
  188
  189ord_intersection(PowerSet, Intersection) :-
  190    must_be(list, PowerSet),
  191    key_by_length(PowerSet, Pairs),
  192    keysort(Pairs, [_-S|Sorted]),
  193    l_int(Sorted, S, Intersection).
  194
  195key_by_length([], []).
  196key_by_length([H|T0], [L-H|T]) :-
  197    '$skip_list'(L, H, Tail),
  198    (   Tail == []
  199    ->  key_by_length(T0, T)
  200    ;   type_error(list, H)
  201    ).
  202
  203l_int(_, [], I) =>
  204    I = [].
  205l_int([], S, I) =>
  206    I = S.
  207l_int([_-H|T], S0, S) =>
  208    ord_intersection(S0, H, S1),
  209    l_int(T, S1, S).
  210
  211
  212%!  ord_intersection(+Set1, +Set2, -Intersection) is det.
  213%
  214%   Intersection holds the common  elements  of   Set1  and  Set2.  Uses
  215%   ord_disjoint/2 if Intersection is bound to `[]` on entry.
  216
  217ord_intersection(Set1, Set2, Intersection) :-
  218    (   Intersection == []
  219    ->  ord_disjoint(Set1, Set2)
  220    ;   ord_intersection_(Set1, Set2, Intersection)
  221    ).
  222
  223ord_intersection_([], _Int, []).
  224ord_intersection_([H1|T1], L2, Int) :-
  225    isect2(L2, H1, T1, Int).
  226
  227isect2([], _H1, _T1, []).
  228isect2([H2|T2], H1, T1, Int) :-
  229    compare(Order, H1, H2),
  230    isect3(Order, H1, T1, H2, T2, Int).
  231
  232isect3(<, _H1, T1,  H2, T2, Int) :-
  233    isect2(T1, H2, T2, Int).
  234isect3(=, H1, T1, _H2, T2, [H1|Int]) :-
  235    ord_intersection_(T1, T2, Int).
  236isect3(>, H1, T1,  _H2, T2, Int) :-
  237    isect2(T2, H1, T1, Int).
  238
  239
  240%!  ord_intersection(+Set1, +Set2, ?Intersection, ?Difference) is det.
  241%
  242%   Intersection  and  difference   between    two   ordered   sets.
  243%   Intersection is the intersection between   Set1  and Set2, while
  244%   Difference is defined by ord_subtract(Set2, Set1, Difference).
  245%
  246%   @see ord_intersection/3 and ord_subtract/3.
  247
  248ord_intersection([], L, [], L) :- !.
  249ord_intersection([_|_], [], [], []) :- !.
  250ord_intersection([H1|T1], [H2|T2], Intersection, Difference) :-
  251    compare(Diff, H1, H2),
  252    ord_intersection2(Diff, H1, T1, H2, T2, Intersection, Difference).
  253
  254ord_intersection2(=, H1, T1, _H2, T2, [H1|T], Difference) :-
  255    ord_intersection(T1, T2, T, Difference).
  256ord_intersection2(<, _, T1, H2, T2, Intersection, Difference) :-
  257    ord_intersection(T1, [H2|T2], Intersection, Difference).
  258ord_intersection2(>, H1, T1, H2, T2, Intersection, [H2|HDiff]) :-
  259    ord_intersection([H1|T1], T2, Intersection, HDiff).
  260
  261
  262%!  ord_add_element(+Set1, +Element, ?Set2) is det.
  263%
  264%   Insert  an  element  into  the  set.    This   is  the  same  as
  265%   ord_union(Set1, [Element], Set2).
  266
  267ord_add_element([], El, [El]).
  268ord_add_element([H|T], El, Add) :-
  269    compare(Order, H, El),
  270    addel(Order, H, T, El, Add).
  271
  272addel(<, H, T,  El, [H|Add]) :-
  273    ord_add_element(T, El, Add).
  274addel(=, H, T, _El, [H|T]).
  275addel(>, H, T,  El, [El,H|T]).
  276
  277
  278
  279%!  ord_del_element(+Set, +Element, -NewSet) is det.
  280%
  281%   Delete an element from an  ordered  set.   This  is  the same as
  282%   ord_subtract(Set, [Element], NewSet).
  283
  284ord_del_element([], _El, []).
  285ord_del_element([H|T], El, Del) :-
  286    compare(Order, H, El),
  287    delel(Order, H, T, El, Del).
  288
  289delel(<,  H, T,  El, [H|Del]) :-
  290    ord_del_element(T, El, Del).
  291delel(=, _H, T, _El, T).
  292delel(>,  H, T, _El, [H|T]).
  293
  294
  295%!  ord_selectchk(+Item, ?Set1, ?Set2) is semidet.
  296%
  297%   Selectchk/3,  specialised  for  ordered  sets.    Is  true  when
  298%   select(Item, Set1, Set2) and Set1, Set2   are  both sorted lists
  299%   without duplicates. This implementation is only expected to work
  300%   for Item ground and either Set1 or Set2 ground. The "chk" suffix
  301%   is meant to remind you of   memberchk/2,  which also expects its
  302%   first  argument  to  be  ground.    ord_selectchk(X,  S,  T)  =>
  303%   ord_memberchk(X, S) & \+ ord_memberchk(X, T).
  304%
  305%   @author Richard O'Keefe
  306
  307ord_selectchk(Item, [X|Set1], [X|Set2]) :-
  308    X @< Item,
  309    !,
  310    ord_selectchk(Item, Set1, Set2).
  311ord_selectchk(Item, [Item|Set1], Set1) :-
  312    (   Set1 == []
  313    ->  true
  314    ;   Set1 = [Y|_]
  315    ->  Item @< Y
  316    ).
  317
  318
  319%!  ord_memberchk(+Element, +OrdSet) is semidet.
  320%
  321%   True if Element is a member of   OrdSet, compared using ==. Note
  322%   that _enumerating_ elements of an ordered  set can be done using
  323%   member/2.
  324%
  325%   Some Prolog implementations also provide  ord_member/2, with the
  326%   same semantics as ord_memberchk/2.  We   believe  that  having a
  327%   semidet ord_member/2 is unacceptably inconsistent with the *_chk
  328%   convention.  Portable  code  should    use   ord_memberchk/2  or
  329%   member/2.
  330%
  331%   @author Richard O'Keefe
  332
  333ord_memberchk(Item, [X1,X2,X3,X4|Xs]) :-
  334    !,
  335    compare(R4, Item, X4),
  336    (   R4 = (>) -> ord_memberchk(Item, Xs)
  337    ;   R4 = (<) ->
  338        compare(R2, Item, X2),
  339        (   R2 = (>) -> Item == X3
  340        ;   R2 = (<) -> Item == X1
  341        ;/* R2 = (=),   Item == X2 */ true
  342        )
  343    ;/* R4 = (=) */ true
  344    ).
  345ord_memberchk(Item, [X1,X2|Xs]) :-
  346    !,
  347    compare(R2, Item, X2),
  348    (   R2 = (>) -> ord_memberchk(Item, Xs)
  349    ;   R2 = (<) -> Item == X1
  350    ;/* R2 = (=) */ true
  351    ).
  352ord_memberchk(Item, [X1]) :-
  353    Item == X1.
  354
  355
  356%!  ord_subset(+Sub, +Super) is semidet.
  357%
  358%   Is true if all elements of Sub are in Super
  359
  360ord_subset([], _).
  361ord_subset([H1|T1], [H2|T2]) :-
  362    compare(Order, H1, H2),
  363    ord_subset_(Order, H1, T1, T2).
  364
  365ord_subset_(>, H1, T1, [H2|T2]) :-
  366    compare(Order, H1, H2),
  367    ord_subset_(Order, H1, T1, T2).
  368ord_subset_(=, _, T1, T2) :-
  369    ord_subset(T1, T2).
  370
  371
  372%!  ord_subtract(+InOSet, +NotInOSet, -Diff) is det.
  373%
  374%   Diff is the set holding all elements of InOSet that are not in
  375%   NotInOSet.
  376
  377ord_subtract([], _Not, Diff) =>
  378    Diff = [].
  379ord_subtract(List, [], Diff) =>
  380    Diff = List.
  381ord_subtract([H1|T1], L2, Diff) =>
  382    diff21(L2, H1, T1, Diff).
  383
  384diff21([], H1, T1, [H1|T1]).
  385diff21([H2|T2], H1, T1, Diff) :-
  386    compare(Order, H1, H2),
  387    diff3(Order, H1, T1, H2, T2, Diff).
  388
  389diff12([], _H2, _T2, []).
  390diff12([H1|T1], H2, T2, Diff) :-
  391    compare(Order, H1, H2),
  392    diff3(Order, H1, T1, H2, T2, Diff).
  393
  394diff3(<,  H1, T1,  H2, T2, [H1|Diff]) :-
  395    diff12(T1, H2, T2, Diff).
  396diff3(=, _H1, T1, _H2, T2, Diff) :-
  397    ord_subtract(T1, T2, Diff).
  398diff3(>,  H1, T1, _H2, T2, Diff) :-
  399    diff21(T2, H1, T1, Diff).
  400
  401
  402%!  ord_union(+SetOfSets, -Union) is det.
  403%
  404%   True if Union is the  union  of   all  elements  in the superset
  405%   SetOfSets. Each member of SetOfSets must  be an ordered set, the
  406%   sets need not be ordered in any way.
  407%
  408%   @author Copied from YAP, probably originally by Richard O'Keefe.
  409
  410ord_union([], Union) =>
  411    Union = [].
  412ord_union([Set|Sets], Union) =>
  413    length([Set|Sets], NumberOfSets),
  414    ord_union_all(NumberOfSets, [Set|Sets], Union, []).
  415
  416ord_union_all(N, Sets0, Union, Sets) =>
  417    (   N =:= 1
  418    ->  Sets0 = [Union|Sets]
  419    ;   N =:= 2
  420    ->  Sets0 = [Set1,Set2|Sets],
  421        ord_union(Set1,Set2,Union)
  422    ;   A is N>>1,
  423        Z is N-A,
  424        ord_union_all(A, Sets0, X, Sets1),
  425        ord_union_all(Z, Sets1, Y, Sets),
  426        ord_union(X, Y, Union)
  427    ).
  428
  429
  430%!  ord_union(+Set1, +Set2, -Union) is det.
  431%
  432%   Union is the union of Set1 and Set2
  433
  434ord_union([], Set2, Union) =>
  435    Union = Set2.
  436ord_union([H1|T1], L2, Union) =>
  437    union2(L2, H1, T1, Union).
  438
  439union2([], H1, T1, Union) =>
  440    Union = [H1|T1].
  441union2([H2|T2], H1, T1, Union) =>
  442    compare(Order, H1, H2),
  443    union3(Order, H1, T1, H2, T2, Union).
  444
  445union3(<, H1, T1,  H2, T2, Union) =>
  446    Union = [H1|Union0],
  447    union2(T1, H2, T2, Union0).
  448union3(=, H1, T1, _H2, T2, Union) =>
  449    Union = [H1|Union0],
  450    ord_union(T1, T2, Union0).
  451union3(>, H1, T1,  H2, T2, Union) =>
  452    Union = [H2|Union0],
  453    union2(T2, H1, T1, Union0).
  454
  455%!  ord_union(+Set1, +Set2, -Union, -New) is det.
  456%
  457%   True iff ord_union(Set1, Set2, Union) and
  458%   ord_subtract(Set2, Set1, New).
  459
  460ord_union([], Set2, Set2, Set2).
  461ord_union([H|T], Set2, Union, New) :-
  462    ord_union_1(Set2, H, T, Union, New).
  463
  464ord_union_1([], H, T, [H|T], []).
  465ord_union_1([H2|T2], H, T, Union, New) :-
  466    compare(Order, H, H2),
  467    ord_union(Order, H, T, H2, T2, Union, New).
  468
  469ord_union(<, H, T, H2, T2, [H|Union], New) :-
  470    ord_union_2(T, H2, T2, Union, New).
  471ord_union(>, H, T, H2, T2, [H2|Union], [H2|New]) :-
  472    ord_union_1(T2, H, T, Union, New).
  473ord_union(=, H, T, _, T2, [H|Union], New) :-
  474    ord_union(T, T2, Union, New).
  475
  476ord_union_2([], H2, T2, [H2|T2], [H2|T2]).
  477ord_union_2([H|T], H2, T2, Union, New) :-
  478    compare(Order, H, H2),
  479    ord_union(Order, H, T, H2, T2, Union, New).
  480
  481
  482%!  ord_symdiff(+Set1, +Set2, ?Difference) is det.
  483%
  484%   Is true when Difference is the  symmetric difference of Set1 and
  485%   Set2. I.e., Difference contains all elements that are not in the
  486%   intersection of Set1 and Set2. The semantics  is the same as the
  487%   sequence below (but the actual   implementation  requires only a
  488%   single scan).
  489%
  490%     ==
  491%           ord_union(Set1, Set2, Union),
  492%           ord_intersection(Set1, Set2, Intersection),
  493%           ord_subtract(Union, Intersection, Difference).
  494%     ==
  495%
  496%   For example:
  497%
  498%     ==
  499%     ?- ord_symdiff([1,2], [2,3], X).
  500%     X = [1,3].
  501%     ==
  502
  503ord_symdiff([], Set2, Set2).
  504ord_symdiff([H1|T1], Set2, Difference) :-
  505    ord_symdiff(Set2, H1, T1, Difference).
  506
  507ord_symdiff([], H1, T1, [H1|T1]).
  508ord_symdiff([H2|T2], H1, T1, Difference) :-
  509    compare(Order, H1, H2),
  510    ord_symdiff(Order, H1, T1, H2, T2, Difference).
  511
  512ord_symdiff(<, H1, Set1, H2, T2, [H1|Difference]) :-
  513    ord_symdiff(Set1, H2, T2, Difference).
  514ord_symdiff(=, _, T1, _, T2, Difference) :-
  515    ord_symdiff(T1, T2, Difference).
  516ord_symdiff(>, H1, T1, H2, Set2, [H2|Difference]) :-
  517    ord_symdiff(Set2, H1, T1, Difference)