1. Domain with an Arbitrary Set of Values

To use more easily the integer variables from MiniCP, you will implement a missing constructor within IntVarImpl.

public IntVarImpl(Solver cp, Set<Integer> values) {
    throw new NotImplementedException();
}

This exercise is straightforward: just create a dense domain and then remove the values not present in the set.

Check that your implementation passes the tests arbitrarySetDomainsMaxInt and arbitrarySetDomains from IntVarTest.java.

2. Implement a Domain Iterator

Many filtering algorithms require iteration over the values of a domain.

A naive (but correct) way of iterating over a domain is:

for (int v = x.min(); v <= x.max(); x++) {
    if (x.contains(i)) {
        // do something
    }
}

This method is rather inefficient because it will also consider the values that are not present in the domain. Instead, the fillArray method from StateSparseSet.java allows filling an array with all the values present in the sparse set. In case of an offset value of 0, you could even use the very efficient System.arraycopy.

The main advantage over the iterator mechanism is that no object is created (and thus garbage collected). Indeed dest is typically a container array stored as an instance variable and reused many times. It is important for efficiency to avoid creating objects on the heap at each execution of a propagator. Never forget that a propagate() method of Constraint may be called thousands of times per second.

This implementation using fillArray avoids the ConcurrentModificationException discussion when implementing an Iterator: should we allow modifying a domain while iterating on it? The answer here is very clear: you get a snapshot of the domain at the time of the call to fillArray and you can thus safely iterate over this dest array and modify the domain at the same time.

To do:

• Improve the efficiency of fillArray from StateSparseSet.java in order to use System.arraycopy when possible.
• Implement public int fillArray(int [] dest) in IntVarImpl.java.
• Check that your implementation passes all the tests from IntVarTest.java and StateSparseSetTest.java.

3. The Maximum Constraint

The maximum constraint links an array of variables x with one variable y such that y = maximum(x[0],x[1],...,x[n]).

Implement Maximum.java. Your algorithm needs to be bound-consistent:

1. Update the minimum and maximum of each x[i] based on the bounds of y
2. Update the minimum and maximum y based on the bounds of all x[i]

The propagation itself should be done within the propagate() method. Within the post() method, you should register the constraints for the variables (through IntVar.propagateOnBoundChange()) and trigger a first time the propagation. You can have a look at the LessOrEqual.java constraint if you are unsure about the differences between a post() and a propagate() and need a working example to see how to start.

@Override
public void post() {
    // TODO very first filtering and register the propagation for changes:
    //  - call the constraint on all bound changes for the variables (x.propagateOnBoundChange(this))
    //  - call a first time the propagate() method to trigger the propagation
}

@Override
public void propagate() {
    // TODO the filtering itself:
    //  - update the min and max values of each x[i] based on the bounds of y
    //  - update the min and max values of each y based on the bounds of all x[i]
}

Check that your implementation passes the tests MaximumTest.java.