Function ExecStatus edgefinding

gecode/int/cumulative/edge-finding.hpp:67–174

  template<class TaskView>
  forceinline ExecStatus
  edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
    sort<TaskView,STO_LCT,false>(t);

    Region r;

    ///////////////////////
    // Detection

    int* prec = r.alloc<int>(t.size());
    for (int i=0; i<t.size(); i++)
      prec[i] = t[i].ect();

    OmegaLambdaTree<TaskView> ol(r,c,t);

    for (int j=0; j<t.size(); j++) {
      while (!ol.lempty() &&
             (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
        int i = ol.responsible();
        prec[i] = std::max(prec[i], t[j].lct());
        ol.lremove(i);
      }
      ol.shift(j);
    }

    ///////////////////////
    // Propagation

    // Compute array of unique capacities and a mapping
    // from the task array to the corresponding entry in
    // the capacity array

    int* cap = r.alloc<int>(t.size());
    for (int i=0; i<t.size(); i++)
      cap[i] = i;
    SortMap<TaskView,StoCap,true> o(t);
    Support::quicksort(cap, t.size(), o);

    int* capacities = r.alloc<int>(t.size());
    int* capInv = r.alloc<int>(t.size());
    for (int i=t.size(); i--;) {
      capacities[cap[i]] = t[i].c();
      capInv[cap[i]] = i;
    }

    int n_c = 0;
    for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
      if (capacities[i] != cur_c)
        capacities[n_c++] = cur_c = capacities[i];
      cap[capInv[i]] = n_c-1;
    }
    r.free<int>(capInv, t.size());

    // Compute update values for each capacity and LCut

    int* update = r.alloc<int>(t.size()*n_c);
    for (int i=0; i<t.size()*n_c; i++)
      update[i] = -Limits::infinity;