variables. Second, and more importantly, iterators transparently perform the transformations needed for set-valued operations on views, and thus constitute a perfect fit for deriving propagators.

Range sequences and range iterators. A *range* [m .. n] denotes the set of integers
{l ∈ Z | m ≤ l ≤ n}. A *range sequence* ranges(S) for a finite set of integers S ⊆ Z
is the shortest sequence s = h[m1 .. n1],...,[mk.. nk]i such that S =
Sk i=1
[mi.. ni] and the ranges are ordered by their smallest elements (mi ≤ mi+1 for 1 ≤ i < k). We thus define the set covered by a range sequence as set(s) = Sk i=1[mi.. ni]. The above range sequence is also written as h[mi.. ni]i k i=1
. Clearly, the range sequence of a set is unique, none of its ranges is empty, and ni +1 < mi+1 for 1 ≤ i < k.

A *range iterator* for a range sequence s = h[ni.. mi]i k i=1 is an object that provides iteration over s: each of the [mi.. ni] can be obtained in sequential order but only one at a time. A range iterator r provides the following operations: r.**done**() tests whether all ranges have been iterated, r.**next**() moves to the next range, and r.min() and r.max() return the minimum and maximum value for the current range. By set(r) we refer to the set defined by an iterator r (which must coincide with set(s)).

A range iterator naturally hides its implementation. It can iterate a sequence (for instance an array) directly by position, but it can just as well traverse a linked list or the leaves of a balanced tree, or for example iterate over the union of two other iterators.

Iterators are consumed by iteration. Hence, if the same sequence needs to be iterated twice, a fresh iterator is needed. If iteration is cheap, an iterator can support multiple iterations by providing a reset operation. Otherwise, a *cache iterator* takes an arbitrary range iterator as input, iterates it completely, and stores the obtained ranges in an array. Its operations then use the array. The cache iterator implements a reset operation, so that the possibly costly input iterator is used only once, while the cache iterator can be used as often as needed.

Iterators for variables. The two basic set-valued operations on integer variables are domain access and domain update. For an integer variable x, the operation x.**getdom**()
returns a range iterator for ranges(d(x)). The operation x.**setdom**(r) updates the variable domain of x to set(r) given a range iterator r, provided that set(r) ⊆ d(x). The responsibility for ensuring that set(r) ⊆ d(x) is left to the programmer.

In order to provide safer and richer operations, we can use *iterator combinators*.

For example, an *intersection iterator r* = iinter(r1,r2) combines two range iterators r1 and r2 such that set(r) = set(r1) ∩ set(r2). Similarly, a *difference iterator r* = iminus(r1,r2) yields set(r) = set(r1) \ set(r2).

Richer set-valued operations are then effortless. The operation x.**adjdom**(r) adjusts the domain d(x) by set(r), yielding d(x)∩set(r), whereas x.**excdom**(r) excludes set(r) from d(x), yielding d(x) \ set(r):
x.**adjdom**(r) = x.**setdom**(iinter(x.**getdom**(),r))
x.**excdom**(r) = x.**setdom**(iminus(x.**getdom**(),r))
In contrast to the x.**setdom**(·) operation, the richer set-valued operations are inherently contracting, and thus safer to use when implementing a propagator.

Iterators also serve as the natural interface for operations on set variables, which are usually approximated as set intervals defined by a lower and an upper bound [25, 13]:
d(x) = [glb(d(x)) .. lub(d(x))] = {s | glb(d(x)) ⊆ s,s ⊆ lub(d(x))}