Next: lib-pillow, Previous: lib-odbc, Up: The Prolog Library [Contents][Index]

`library(ordsets)`

This library module provides operations on sets represented as ordered lists with no
duplicates. Thus `{c,r,a,f,t}`

would be `[a,c,f,r,t]`

. The ordering
is defined by the `@<`

family of term comparison predicates, which
is the ordering used by `sort/2`

and `setof/3`

.

The benefit of the ordered representation is that the elementary
set operations can be done in time proportional to the sum of the
argument sizes rather than their product. You should use the
operations defined here in preference to those in `library(sets)`

unless there is a compelling reason why you can’t. Some of the
unordered set routines, such as `member/2`

, `length/2`

and `select/3`

can
be used unchanged on ordered sets; feel free so to use them.

There is no `ordset_to_list/2`

, as an ordered set is a list already.
Exported predicates:

`is_ordset(`

`+List`)-
is true when

`List`is a list of terms`[T1,T2,...,Tn]`and the terms are strictly increasing:`T1 @< T2 @< ... @< Tn`. The output of`sort/2`

always satisfies this test. Anything which satisfies this test can be given to the predicates in this file, regardless of where you got it. `list_to_ord_set(`

`+List`,`-Set`)-
is true when

`Set`is the ordered representation of the set represented by the unordered representation List. The only reason for giving it a name at all is that you may not have realized that`sort/2`

could be used this way. `ord_add_element(`

`+Set1`,`+Element`,`-Set2`)-
Equivalent to

`ord_union(`

, but a bit faster.`Set1`, [`Element`],`Set2`) `ord_del_element(`

`+Set1`,`+Element`,`-Set2`)-
Equivalent to

`ord_subtract(`

, but a bit faster.`Set1`, [`Element`],`Set2`) `ord_disjoint(`

`+Set1`,`+Set2`)-
is true when the two ordered sets have no element in common.

`ord_intersect(`

`+Set1`,`+Set2`)-
is true when the two ordered sets have at least one element in common.

`ord_intersection(`

`+Set1`,`+Set2`,`-Intersection`)-
is true when

`Intersection`is the ordered representation of`Set1`and`Set2`, provided that`Set1`and`Set2`are ordered sets. `ord_intersection(`

`+Set1`,`+Set2`,`?Intersection`,`?Difference`)is true when

`Intersection`is the intersection of`Set1`and`Set2`, and`Difference`is`Set2 \ Set1`(like in ord_union/4), provided that`Set1`and`Set2`are ordered sets.`ord_intersection(`

`+ListOfSets`,`-Intersection`)is true when

`ListOfSets`is a nonempty proper list of ordered sets and`Intersection`is their intersection.`ord_member(`

`+Elt`,`+Set`)-
is true when

`Elt`is a member of`Set`. Suggested by Mark Johnson. `ord_nonmember(`

`+Item`,`+Set`)-
is true when the given

`Item`is*not*an element of the given`Set`. `ord_seteq(`

`+Set1`,`+Set2`)-
is true when the two arguments represent the same set. Since they are assumed to be ordered representations, they must be identical.

`ord_setproduct(`

`+Set1`,`+Set2`,`-Product`)-
If

`Set1`and`Set2`are ordered sets,`Product`will be an ordered set of`x1-x2`pairs. Note that we cannot solve for`Set1`and`Set2`, because there are infinitely many solutions when`Product`is empty, and may be a large number in other cases. Could be defined as:ord_setproduct(Set1, Set2, Product) :- ( foreach(H1,Set1), param(Set2), fromto(Product,P1,P3,[]) do ( foreach(H2,Set2), param(H1), fromto(P1,[H1-H2|P2],P2,P3) do true ) ).

`ord_subset(`

`+Set1`,`+Set2`)-
is true when every element of the ordered set

`Set1`appears in the ordered set`Set2`. `ord_subtract(`

`+Set1`,`+Set2`,`-Difference`)-
is true when

`Difference`contains all and only the elements of`Set1`which are not also in`Set2`. `ord_symdiff(`

`+Set1`,`+Set2`,`-Difference`)-
is true when

`Difference`is the symmetric difference of`Set1`and`Set2`. `ord_disjoint_union(`

`+Set1`,`+Set2`,`-Union`)-
is true when

`Set1`and`Set2`(given to be ordered sets) have no element in common, and`Union`is their union. The meaning is the same asord_disjoint(Set1, Set2), ord_union(Set1, Set2, Union)

but it is more efficient.

`ord_union(`

`+Set1`,`+Set2`,`-Union`)-
is true when

`Union`is the union of`Set1`and`Set2`. Note that when something occurs in both sets, we want to retain only one copy. `ord_union(`

`+OldSet`,`+NewSet`,`-Union`,`-ReallyNew`)is true when

`Union`is`NewSet U OldSet`and`ReallyNew`is`NewSet \ OldSet`. This is useful when you have an iterative problem, and you’re adding some possibly new elements (`NewSet`) to a set (`OldSet`), and as well as getting the updated set (`Union`) you would like to know which if any of the "new" elements didn’t already occur in the set (`ReallyNew`).`ord_union(`

`+ListOfSets`,`-Union`)is true when

`ListOfSets`is given as a proper list of ordered sets and`Union`is their union. Letting`K`be the length of`ListOfSets`, and`N`the sum of the sizes of its elements, the cost is`O(N lg K)`.`ordset_order(`

`+Xs`,`+Ys`,`-R`)-
is true when

`R`is`<`

,`=`

, or`>`

according as`Xs`is a subset of`Ys`, equal to`Ys`, or a superset of`Ys`.`Xs`and`Ys`are ordered sets.

Send feedback on this subject.