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)
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)
sort/2
could be
used this way.
ord_add_element(
+Set1,
+Element,
-Set2)
ord_union(
Set1, [
Element],
Set2)
, but a bit
faster.
ord_del_element(
+Set1,
+Element,
-Set2)
ord_subtract(
Set1, [
Element],
Set2)
, but a bit
faster.
ord_disjoint(
+Set1,
+Set2)
ord_intersect(
+Set1,
+Set2)
ord_intersection(
+Set1,
+Set2,
-Intersection)
ord_intersection(
+Set1,
+Set2,
?Intersection,
?Difference)
ord_intersection(
+ListOfSets,
-Intersection)
ord_member(
+Elt,
+Set)
ord_nonmember(
+Item,
+Set)
ord_seteq(
+Set1,
+Set2)
ord_setproduct(
+Set1,
+Set2,
-Product)
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)
ord_subtract(
+Set1,
+Set2,
-Difference)
ord_symdiff(
+Set1,
+Set2,
-Difference)
ord_disjoint_union(
+Set1,
+Set2,
-Union)
ord_disjoint(Set1, Set2), ord_union(Set1, Set2, Union)
but it is more efficient.
ord_union(
+Set1,
+Set2,
-Union)
ord_union(
+OldSet,
+NewSet,
-Union,
-ReallyNew)
ord_union(
+ListOfSets,
-Union)
ordset_order(
+Xs,
+Ys,
-R)
<
, =
, or >
according as Xs is a subset of Ys,
equal to Ys, or a superset of Ys. Xs and Ys are ordered sets.