% This LaTeX document was generated using the LaTeX backend of PlDoc,
% The SWI-Prolog documentation system



\section{library(ordsets): Ordered set manipulation}

\label{sec:ordsets}

Ordered sets are lists with unique elements sorted to the standard order
of terms (see \predref{sort}{2}). Exploiting ordering, many of the set operations
can be expressed in order N rather than N\Shat{}2 when dealing with unordered
sets that may contain duplicates. The \file{library(ordsets)} is available in a
number of Prolog implementations. Our predicates are designed to be
compatible with common practice in the Prolog community. The
implementation is incomplete and relies partly on \file{library(oset)}, an
older ordered set library distributed with SWI-Prolog. New applications
are advised to use \file{library(ordsets)}.

Some of these predicates match directly to corresponding list
operations. It is advised to use the versions from this library to make
clear you are operating on ordered sets. An exception is \predref{member}{2}. See
\predref{ord_memberchk}{2}.

The ordsets library is based on the standard order of terms. This
implies it can handle all Prolog terms, including variables. Note
however, that the ordering is not stable if a term inside the set is
further instantiated. Also note that variable ordering changes if
variables in the set are unified with each other or a variable in the
set is unified with a variable that is `older' than the newest variable
in the set. In practice, this implies that it is allowed to use
\verb$member(X, OrdSet)$ on an ordered set that holds variables only if X is a
fresh variable. In other cases one should cease using it as an ordset
because the order it relies on may have been changed.\vspace{0.7cm}

\begin{description}
    \predicate[semidet]{is_ordset}{1}{@Term}
True if \arg{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, \predref{sort}{2} or
\predref{setof}{3}.

    \predicate[semidet]{ord_empty}{1}{?List}
True when \arg{List} is the empty ordered set. Simply unifies list
with the empty list. Not part of Quintus.

    \predicate[semidet]{ord_seteq}{2}{+Set1, +Set2}
True if \arg{Set1} and \arg{Set2} have the same elements. As both are
canonical sorted lists, this is the same as \predref{\Sequal}{2}.

\begin{tags}
    \tag{Compatibility}
sicstus
\end{tags}

    \predicate[det]{list_to_ord_set}{2}{+List, -OrdSet}
Transform a list into an ordered set. This is the same as
sorting the list.

    \predicate[semidet]{ord_intersect}{2}{+Set1, +Set2}
True if both ordered sets have a non-empty intersection.

    \predicate[semidet]{ord_disjoint}{2}{+Set1, +Set2}
True if \arg{Set1} and \arg{Set2} have no common elements. This is the
negation of \predref{ord_intersect}{2}.

    \predicate{ord_intersect}{3}{+Set1, +Set2, -Intersection}
\arg{Intersection} holds the common elements of \arg{Set1} and \arg{Set2}.

\begin{tags}
    \tag{deprecated}
Use \predref{ord_intersection}{3}
\end{tags}

    \predicate[semidet]{ord_intersection}{2}{+PowerSet, -Intersection}
\arg{Intersection} of a powerset. True when \arg{Intersection} is an ordered set
holding all elements common to all sets in \arg{PowerSet}. Fails if
\arg{PowerSet} is an empty list.

\begin{tags}
    \tag{Compatibility}
sicstus
\end{tags}

    \predicate[det]{ord_intersection}{3}{+Set1, +Set2, -Intersection}
\arg{Intersection} holds the common elements of \arg{Set1} and \arg{Set2}. Uses
\predref{ord_disjoint}{2} if \arg{Intersection} is bound to \verb$[]$ on entry.

    \predicate[det]{ord_intersection}{4}{+Set1, +Set2, ?Intersection, ?Difference}
\arg{Intersection} and difference between two ordered sets.
\arg{Intersection} is the intersection between \arg{Set1} and \arg{Set2}, while
\arg{Difference} is defined by \verb$ord_subtract(Set2, Set1, Difference)$.

\begin{tags}
    \tag{See also}
\predref{ord_intersection}{3} and \predref{ord_subtract}{3}.
\end{tags}

    \predicate[det]{ord_add_element}{3}{+Set1, +Element, ?Set2}
Insert an element into the set. This is the same as
\verb$ord_union(Set1, [Element], Set2)$.

    \predicate[det]{ord_del_element}{3}{+Set, +Element, -NewSet}
Delete an element from an ordered set. This is the same as
\verb$ord_subtract(Set, [Element], NewSet)$.

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

\begin{tags}
    \tag{author}
Richard O'Keefe
\end{tags}

    \predicate[semidet]{ord_memberchk}{2}{+Element, +OrdSet}
True if \arg{Element} is a member of \arg{OrdSet}, compared using ==. Note
that \textit{enumerating} elements of an ordered set can be done using
\predref{member}{2}.

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

\begin{tags}
    \tag{author}
Richard O'Keefe
\end{tags}

    \predicate[semidet]{ord_subset}{2}{+Sub, +Super}
Is true if all elements of \arg{Sub} are in \arg{Super}

    \predicate[det]{ord_subtract}{3}{+InOSet, +NotInOSet, -Diff}
\arg{Diff} is the set holding all elements of \arg{InOSet} that are not in
\arg{NotInOSet}.

    \predicate[det]{ord_union}{2}{+SetOfSets, -Union}
True if \arg{Union} is the union of all elements in the superset
\arg{SetOfSets}. Each member of \arg{SetOfSets} must be an ordered set, the
sets need not be ordered in any way.

\begin{tags}
    \tag{author}
Copied from YAP, probably originally by Richard O'Keefe.
\end{tags}

    \predicate[det]{ord_union}{3}{+Set1, +Set2, -Union}
\arg{Union} is the union of \arg{Set1} and \arg{Set2}

    \predicate[det]{ord_union}{4}{+Set1, +Set2, -Union, -New}
True iff \verb$ord_union(Set1, Set2, Union)$ and
\verb$ord_subtract(Set2, Set1, New)$.

    \predicate[det]{ord_symdiff}{3}{+Set1, +Set2, ?Difference}
Is true when \arg{Difference} is the symmetric difference of \arg{Set1} and
\arg{Set2}. I.e., \arg{Difference} contains all elements that are not in the
intersection of \arg{Set1} and \arg{Set2}. The semantics is the same as the
sequence below (but the actual implementation requires only a
single scan).

\begin{code}
      ord_union(Set1, Set2, Union),
      ord_intersection(Set1, Set2, Intersection),
      ord_subtract(Union, Intersection, Difference).
\end{code}

For example:

\begin{code}
?- ord_symdiff([1,2], [2,3], X).
X = [1,3].
\end{code}

\end{description}