**provides**- x-ozlib://duchier/cp/Select.ozf

The idea of the *selection constraint* is based on the
intuitive notion of selecting the `I`

th element out of a
sequence of values. Abstractly, we might write this as
follows:
`X = <V1 ... Vn>[I]`

However, this is more than just:
`X = {Nth [V1 ... Vn] I}`

because it is intended to function as a constraint: all of
`X`

, `V1`

, ..., `Vn`

, and
`I`

can be variables (e.g. finite set variables). In
particular, constraining `X`

should restrict the values
that `I`

may take to only those positions in 1..n
corresponding to elements `Vk`

that are not yet
inconsistent with `X`

. Conversely, if all elements that
may still be selected by `I`

have a basic constraint in
common, the latter should be propagated to `V`

. This
lifting of common information is a form of *constructive
disjunction*.

As of version 1.3, this package also provides the *selection
union constraint*:
`S = U<S1 ... Sn>[SI]`

where `SI`

is a set variable of indices. Its declarative
semantics is that `S`

is the union of the sets
`Si`

for all `i`

in `SI`

.

As of version 1.5, this package also provides the *selection
intersection constraint*:
`S = &<S1 ... Sn>[SI]`

where `SI`

is a set variable of indices. Its declarative
semantics is that `S`

is the intersection of the sets
`Si`

for all `i`

in `SI`

.

As of version 1.6, this package provides the *sequenced union
constraint*:
`S = (<<U)<S1 ... Sn>`

where `S`

is the union of the sets `Si`

which are
additionally constrained to be sequential, i.e. for
`i<j`

all elements of `Si`

are smaller than
elements of `Sj`

.

Version 1.8 - added *indexed union constraint*:
`S = IU<(I1,S1) ... (In,Sn)>[SI]`

which returns the union of
the `Sk`

for `Ik`

in `SI`

.

This package implements the selection constraint for homogenous
vectors of finite domains or of finite sets, and the selection union
constraint. It is available as a
module that exports features `fd`

, `fs`

,
and `union`

:

`import Select(fd fs union) at 'x-ozlib://duchier/cp/Select.ozf'`

`{Select.fd L I D}`

`L`

must be a vector (list, tuple, record) of integers and/or finite domain variables.`I`

and`D`

are nestable and will be constrained to finite domain variables if necessary.`{Select.fs L I S}`

`L`

must be a vector of finite set values or variables. Again,`I`

and`S`

are nestable and will be constrained respectively to a finite domain variable and a finite set variable if necessary.`{Select.union L SI S}`

`L`

must be a vector of finite set values or variables,`SI`

a set value/variable selecting positions in`L`

. Both`SI`

and`S`

are nestable.`{Select.inter L SI S}`

`L`

must be a vector of finite set values or variables,`SI`

a set value/variable selecting positions in`L`

. Both`SI`

and`S`

are nestable.`{Select.seqUnion L S}`

`S`

is the union of the`Si`

in`L`

. Furthermore the`Si`

are constrained to be sequential, i.e. for`i<j`

, all elements of`Si`

must be smaller than elements of`Sj`

.`{Select.indexedUnion L SI S}`

`L`

is either a list of`Ik#Sk`

where`Ik`

is an integer and`Sk`

is a FS variable, or a record mapping features`Ik`

to values`Sk`

.`S`

is constrained to be the union of the`Sk`

for`k`

in`SI`

.

As of version 1.5, the `Select`

module also exports
features `fdom`

and `fset`

to distinguish
between constraints according to the type of the sequence:

`{Select.fdom.nth L I J}`

`{Select.fset.nth L I S}`

`{Select.fset.union L SI S}`

`{Select.fset.inter L SI S}`

`{Select.fset.seqUnion L S}`

`{Select.fset.indexedUnion L SI S}`

Here is an example to help clarify what the selection constraint can
do for you. Let's import the module implementing the selection
constraint:
```
declare [Select]={Module.link ['x-ozlib://duchier/cp/Select.ozf']}
```

Now we create 3 sets `S1`

, `S2`

,
`S3`

, and an index `I`

ranging from 1 to 3 to
select one of them. `S1`

contains just 5, `S2`

contains 1 and 21, and `S3`

contains 1 and 77:
```
declare
S1 = {FS.value.make [5]}
S2 = {FS.value.make [1 21]}
S3 = {FS.value.make [1 77]}
I I::1#3
```

Now we define `S`

to be the `I`

th element of the
sequence of finite sets `[S1 S2 S3]`

:
```
declare S = {Select.fs [S1 S2 S3] I}
```

Using `Show`

, here is what is currently known about
`S`

and `I`

:
```
S{{}..{1 5 21 77}}#{1#2}
I{1#3}
```

Thus it is already known that `S`

can have at most as
elements integers 1, 5, 21 and 77; i.e. this information has been lifted
to `S`

. Now let's explicitly remove element 5:
```
{FS.exclude 5 S}
```

Now, here is what is known:
```
S{{1}..{1 21 77}}#2
I{2 3}
```

In other words, it has been noticed that `I=1`

would be
inconsistent, thus this value has been removed from the domain of
`I`

. Furthermore `S`

is now known to contain 1
and maybe 21 and 77. It is known to contain 1 because only
`S2`

and `S3`

remain as possibilities and both
contain 1.

Starting 5 Oct 2001, this contribution is only distributed as an
`ozmake --install --package=duchier-select.pkg`

If this package was already installed on your computer and you want to
upgrade to a newer version, invoke:
`ozmake --upgrade --package=duchier-select.pkg`

or else

Denys Duchier