| 305 | // cardinality rules for PartitionN constraint |
| 306 | template<class View0, class View1> |
| 307 | ExecStatus |
| 308 | partitionNCard(Space& home, |
| 309 | bool& modified, ViewArray<View0>& x, View1& y, |
| 310 | GLBndSet& unionOfDets) { |
| 311 | unsigned int cardMinSum=unionOfDets.size(); |
| 312 | unsigned int cardMaxSum=unionOfDets.size(); |
| 313 | int xsize = x.size(); |
| 314 | for (int i=xsize; i--; ) { |
| 315 | cardMinSum+=x[i].cardMin(); |
| 316 | if (cardMinSum < x[i].cardMin()) { |
| 317 | //sum of mins overflows: fail the space. |
| 318 | GECODE_ME_CHECK(ME_SET_FAILED); |
| 319 | } |
| 320 | } |
| 321 | GECODE_ME_CHECK_MODIFIED(modified, y.cardMin(home,cardMinSum)); |
| 322 | for (int i=xsize; i--; ) { |
| 323 | cardMaxSum+=x[i].cardMax(); |
| 324 | if (cardMaxSum < x[i].cardMax()) { |
| 325 | //sum of maxes overflows: no useful information to tell. |
| 326 | goto overflow; |
| 327 | } |
| 328 | } |
| 329 | GECODE_ME_CHECK_MODIFIED(modified, y.cardMax(home,cardMaxSum)); |
| 330 | |
| 331 | if (x.size() == 0) |
| 332 | return ES_NOFIX; |
| 333 | |
| 334 | overflow: |
| 335 | |
| 336 | //Cardinality of each x[i] limited by cardinality of y minus all x[j]s: |
| 337 | |
| 338 | { |
| 339 | Region r; |
| 340 | unsigned int* rightMinSum = r.alloc<unsigned int>(xsize); |
| 341 | unsigned int* rightMaxSum = r.alloc<unsigned int>(xsize); |
| 342 | rightMinSum[xsize-1]=0; |
| 343 | rightMaxSum[xsize-1]=0; |
| 344 | |
| 345 | for (int i=x.size()-1;i--;) { |
| 346 | rightMaxSum[i] = rightMaxSum[i+1] + x[i+1].cardMax(); |
| 347 | if (rightMaxSum[i] < rightMaxSum[i+1]) { |
| 348 | //overflow, fill the rest of the array. |
| 349 | for (int j=i; j>0;j--) { |
| 350 | rightMaxSum[j]=Limits::card; |
| 351 | } |
| 352 | break; |
| 353 | } |
| 354 | } |
| 355 | for (int i=x.size()-1;i--;) { |
| 356 | rightMinSum[i] = rightMinSum[i+1] + x[i+1].cardMin(); |
| 357 | if (rightMinSum[i] < rightMinSum[i+1]) { |
| 358 | //overflow, fail the space |
| 359 | GECODE_ME_CHECK(ME_SET_FAILED); |
| 360 | } |
| 361 | } |
| 362 | unsigned int leftMinAcc=unionOfDets.size(); |
| 363 | unsigned int leftMaxAcc=unionOfDets.size(); |
| 364 | |