Method propagate

gecode/set/int/weights.hpp:246–354

  template<class View>
  ExecStatus
  Weights<View>::propagate(Space& home, const ModEventDelta&) {
    ModEvent me = ME_SET_NONE;

    if (!x.assigned()) {
      // Collect the weights of the elements in the unknown set in an array
      int size = elements.size();
      Region r;
      int* minWeights = r.alloc<int>(size);
      int* maxWeights = r.alloc<int>(size);

      UnknownRanges<View> ur(x);
      Iter::Ranges::ToValues<UnknownRanges<View> > urv(ur);
      for (int i=0; i<size; i++) {
        if (!urv() || elements[i]<urv.val()) {
          minWeights[i] = INT_MAX;
          maxWeights[i] = INT_MIN;
        } else {
          assert(elements[i] == urv.val());
          minWeights[i] = weights[i];
          maxWeights[i] = weights[i];
          ++urv;
        }
      }

      // Sort the weights of the unknown elements
      IntLess il;
      Support::quicksort<int>(minWeights, size, il);
      Support::quicksort<int>(maxWeights, size, il);

      // The maximum number of elements that can still be added to x
      int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));

      // The weight of the elements already in x
      GlbRanges<View> glb(x);
      int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);

      // Compute the weight of the current lower bound of x, plus at most
      // delta-1 further elements with smallest negative weights. This weight
      // determines which elements in the upper bound cannot possibly be
      // added to x (those whose weight would exceed the capacity even if
      // all other elements are minimal)
      int lowWeight = glbWeight;
      for (int i=0; i<delta-1; i++) {
        if (minWeights[i] >= 0)
          break;
        lowWeight+=minWeights[i];
      }

      // Compute the lowest possible weight of x. If there is another element
      // with negative weight left, then add its weight to lowWeight.
      // Otherwise lowWeight is already the lowest possible weight.
      int lowestWeight = lowWeight;
      if (delta>0 && minWeights[delta-1]<0)
        lowestWeight+=minWeights[delta-1];

      // If after including the minimal number of required elements,
      // no more element with negative weight is available, then