| 127 | |
| 128 | template<class VY> |
| 129 | ExecStatus |
| 130 | IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) { |
| 131 | assert(n_dis > 0); |
| 132 | |
| 133 | // At least one more value will be needed |
| 134 | GECODE_ME_CHECK(y.gq(home,vs.size() + 1)); |
| 135 | |
| 136 | Region r; |
| 137 | |
| 138 | // Only one additional value is allowed |
| 139 | if (y.max() == vs.size() + 1) { |
| 140 | // Compute possible values |
| 141 | ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis); |
| 142 | for (int i=n_dis; i--; ) |
| 143 | r_dis[i] = ViewRanges<IntView>(x[dis[i]]); |
| 144 | Iter::Ranges::NaryInter iv(r, r_dis, n_dis); |
| 145 | // Is there a common value at all? |
| 146 | if (!iv()) |
| 147 | return ES_FAILED; |
| 148 | ValSet::Ranges vsr(vs); |
| 149 | Iter::Ranges::NaryUnion pv(r,iv,vsr); |
| 150 | // Enforce common values |
| 151 | for (int i=x.size(); i--; ) { |
| 152 | pv.reset(); |
| 153 | GECODE_ME_CHECK(x[i].inter_r(home, pv, false)); |
| 154 | } |
| 155 | return ES_OK; |
| 156 | } |
| 157 | |
| 158 | // Compute independent set for lower bound |
| 159 | // ovl is a bit-matrix defining whether two views overlap |
| 160 | SymBitMatrix ovl(r,x.size()); |
| 161 | // deg[i] is the degree of x[i] |
| 162 | int* deg = r.alloc<int>(x.size()); |
| 163 | // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i] |
| 164 | int** ovl_i = r.alloc<int*>(x.size()); |
| 165 | // n_ovl_i[i] defines how many integers are stored for ovl_i[i] |
| 166 | int* n_ovl_i = r.alloc<int>(x.size()); |
| 167 | { |
| 168 | #ifndef NDEBUG |
| 169 | // Initialize all to null pointers so that things crash ;-) |
| 170 | for (int i=x.size(); i--; ) |
| 171 | ovl_i[i] = nullptr; |
| 172 | #endif |
| 173 | // For each i there can be at most n_dis-1 entries in ovl_i[i] |
| 174 | int* m = r.alloc<int>(n_dis*(n_dis-1)); |
| 175 | for (int i=n_dis; i--; ) { |
| 176 | deg[dis[i]] = 0; |
| 177 | ovl_i[dis[i]] = m; m += n_dis-1; |
| 178 | } |
| 179 | } |
| 180 | |
| 181 | // Initialize overlap matrix by analyzing the view ranges |
| 182 | { |
| 183 | // Compute how many events are needed |
| 184 | // One event for the end marker |
| 185 | int n_re = 1; |
| 186 | // Two events for each range |