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).   65
   66/** <module> Ordered set manipulation
   67
   68Ordered sets are lists with unique elements sorted to the standard order
   69of terms (see sort/2). Exploiting ordering,   many of the set operations
   70can be expressed in order N rather  than N^2 when dealing with unordered
   71sets that may contain duplicates. The library(ordsets) is available in a
   72number of Prolog implementations. Our  predicates   are  designed  to be
   73compatible  with  common  practice   in    the   Prolog  community.  The
   74implementation is incomplete and  relies   partly  on  library(oset), an
   75older ordered set library distributed  with SWI-Prolog. New applications
   76are advised to use library(ordsets).
   77
   78Some  of  these  predicates  match    directly   to  corresponding  list
   79operations. It is advised to use the  versions from this library to make
   80clear you are operating on ordered sets.   An exception is member/2. See
   81ord_memberchk/2.
   82
   83The ordsets library is based  on  the   standard  order  of  terms. This
   84implies it can handle  all  Prolog   terms,  including  variables.  Note
   85however, that the ordering is not stable  if   a  term inside the set is
   86further instantiated. Also  note  that   variable  ordering  changes  if
   87variables in the set are unified with each   other  or a variable in the
   88set is unified with a variable that  is `older' than the newest variable
   89in the set. In  practice,  this  implies   that  it  is  allowed  to use
   90member(X, OrdSet) on an ordered set that holds  variables only if X is a
   91fresh variable. In other cases one should   cease  using it as an ordset
   92because the order it relies on may have been changed.
   93*/
   94
   95%!  is_ordset(@Term) is semidet.
   96%
   97%   True if Term is an ordered set.   All predicates in this library
   98%   expect ordered sets as input arguments.  Failing to fullfil this
   99%   assumption results in undefined   behaviour.  Typically, ordered
  100%   sets are created by predicates  from   this  library,  sort/2 or
  101%   setof/3.
  102
  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).
  115
  116
  117%!  ord_empty(?List) is semidet.
  118%
  119%   True when List is the  empty   ordered  set. Simply unifies list
  120%   with the empty list. Not part of Quintus.
  121
  122ord_empty([]).
  123
  124
  125%!  ord_seteq(+Set1, +Set2) is semidet.
  126%
  127%   True if Set1 and Set2  have  the   same  elements.  As  both are
  128%   canonical sorted lists, this is the same as ==/2.
  129%
  130%   @compat sicstus
  131
  132ord_seteq(Set1, Set2) :-
  133    Set1 == Set2.
  134
  135
  136%!  list_to_ord_set(+List, -OrdSet) is det.
  137%
  138%   Transform a list into an ordered set.  This is the same as
  139%   sorting the list.
  140
  141list_to_ord_set(List, Set) :-
  142    sort(List, Set).
  143
  144
  145%!  ord_intersect(+Set1, +Set2) is semidet.
  146%
  147%   True if both ordered sets have a non-empty intersection.
  148
  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).
  161
  162
  163%!  ord_disjoint(+Set1, +Set2) is semidet.
  164%
  165%   True if Set1 and Set2  have  no   common  elements.  This is the
  166%   negation of ord_intersect/2.
  167
  168ord_disjoint(Set1, Set2) :-
  169    \+ ord_intersect(Set1, Set2).
  170
  171
  172%!  ord_intersect(+Set1, +Set2, -Intersection)
  173%
  174%   Intersection  holds  the  common  elements  of  Set1  and  Set2.
  175%
  176%   @deprecated Use ord_intersection/3
  177
  178ord_intersect(Set1, Set2, Intersection) :-
  179    ord_intersection(Set1, Set2, Intersection).
  180
  181
  182%!  ord_intersection(+PowerSet, -Intersection) is semidet.
  183%
  184%   Intersection of a powerset. True when Intersection is an ordered set
  185%   holding all elements common  to  all   sets  in  PowerSet.  Fails if
  186%   PowerSet is an empty list.
  187%
  188%   @compat sicstus
  189
  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).
  211
  212
  213%!  ord_intersection(+Set1, +Set2, -Intersection) is det.
  214%
  215%   Intersection holds the common  elements  of   Set1  and  Set2.  Uses
  216%   ord_disjoint/2 if Intersection is bound to `[]` on entry.
  217
  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).
  239
  240
  241%!  ord_intersection(+Set1, +Set2, ?Intersection, ?Difference) is det.
  242%
  243%   Intersection  and  difference   between    two   ordered   sets.
  244%   Intersection is the intersection between   Set1  and Set2, while
  245%   Difference is defined by ord_subtract(Set2, Set1, Difference).
  246%
  247%   @see ord_intersection/3 and ord_subtract/3.
  248
  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).
  261
  262
  263%!  ord_add_element(+Set1, +Element, ?Set2) is det.
  264%
  265%   Insert  an  element  into  the  set.    This   is  the  same  as
  266%   ord_union(Set1, [Element], Set2).
  267
  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]).
  277
  278
  279
  280%!  ord_del_element(+Set, +Element, -NewSet) is det.
  281%
  282%   Delete an element from an  ordered  set.   This  is  the same as
  283%   ord_subtract(Set, [Element], NewSet).
  284
  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]).
  294
  295
  296%!  ord_selectchk(+Item, ?Set1, ?Set2) is semidet.
  297%
  298%   Selectchk/3,  specialised  for  ordered  sets.    Is  true  when
  299%   select(Item, Set1, Set2) and Set1, Set2   are  both sorted lists
  300%   without duplicates. This implementation is only expected to work
  301%   for Item ground and either Set1 or Set2 ground. The "chk" suffix
  302%   is meant to remind you of   memberchk/2,  which also expects its
  303%   first  argument  to  be  ground.    ord_selectchk(X,  S,  T)  =>
  304%   ord_memberchk(X, S) & \+ ord_memberchk(X, T).
  305%
  306%   @author Richard O'Keefe
  307
  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    ).
  318
  319
  320%!  ord_memberchk(+Element, +OrdSet) is semidet.
  321%
  322%   True if Element is a member of   OrdSet, compared using ==. Note
  323%   that _enumerating_ elements of an ordered  set can be done using
  324%   member/2.
  325%
  326%   Some Prolog implementations also provide  ord_member/2, with the
  327%   same semantics as ord_memberchk/2.  We   believe  that  having a
  328%   semidet ord_member/2 is unacceptably inconsistent with the *_chk
  329%   convention.  Portable  code  should    use   ord_memberchk/2  or
  330%   member/2.
  331%
  332%   @author Richard O'Keefe
  333
  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.
  355
  356%!  ord_range(+Set, +Min, +Max, -Range) is det.
  357%
  358%   Retrieves a range of elements between `Min` and `Max` (inclusive)
  359%   from a set using standard term comparison.
  360
  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 = [].
  422
  423%!  ord_subset(+Sub, +Super) is semidet.
  424%
  425%   Is true if all elements of Sub are in Super
  426
  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).
  437
  438
  439%!  ord_subtract(+InOSet, +NotInOSet, -Diff) is det.
  440%
  441%   Diff is the set holding all elements of InOSet that are not in
  442%   NotInOSet.
  443
  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).
  467
  468
  469%!  ord_union(+SetOfSets, -Union) is det.
  470%
  471%   True if Union is the  union  of   all  elements  in the superset
  472%   SetOfSets. Each member of SetOfSets must  be an ordered set, the
  473%   sets need not be ordered in any way.
  474%
  475%   @author Copied from YAP, probably originally by Richard O'Keefe.
  476
  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    ).
  495
  496
  497%!  ord_union(+Set1, +Set2, -Union) is det.
  498%
  499%   Union is the union of Set1 and Set2
  500
  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).
  521
  522%!  ord_union(+Set1, +Set2, -Union, -New) is det.
  523%
  524%   True iff ord_union(Set1, Set2, Union) and
  525%   ord_subtract(Set2, Set1, New).
  526
  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).
  547
  548
  549%!  ord_symdiff(+Set1, +Set2, ?Difference) is det.
  550%
  551%   Is true when Difference is the  symmetric difference of Set1 and
  552%   Set2. I.e., Difference contains all elements that are not in the
  553%   intersection of Set1 and Set2. The semantics  is the same as the
  554%   sequence below (but the actual   implementation  requires only a
  555%   single scan).
  556%
  557%     ==
  558%           ord_union(Set1, Set2, Union),
  559%           ord_intersection(Set1, Set2, Intersection),
  560%           ord_subtract(Union, Intersection, Difference).
  561%     ==
  562%
  563%   For example:
  564%
  565%     ==
  566%     ?- ord_symdiff([1,2], [2,3], X).
  567%     X = [1,3].
  568%     ==
  569
  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)