| 401 | |
| 402 | template<class Card> |
| 403 | forceinline ExecStatus |
| 404 | Bnd<Card>::ubc(Space& home, int& nb, |
| 405 | HallInfo hall[], Rank rank[], int mu[], int nu[]) { |
| 406 | int rightmost = nb + 1; // rightmost accessible value in bounds |
| 407 | int bsize = nb + 2; // number of unique bounds including sentinels |
| 408 | |
| 409 | //Narrow lower bounds (UBC) |
| 410 | |
| 411 | /* |
| 412 | * Initializing tree structure with the values from bounds |
| 413 | * and the interval capacities of neighboured values |
| 414 | * from left to right |
| 415 | */ |
| 416 | |
| 417 | |
| 418 | hall[0].h = 0; |
| 419 | hall[0].t = 0; |
| 420 | hall[0].d = 0; |
| 421 | |
| 422 | for (int i = bsize; --i; ) { |
| 423 | hall[i].h = hall[i].t = i-1; |
| 424 | hall[i].d = ups.sumup(hall[i-1].bounds, hall[i].bounds - 1); |
| 425 | } |
| 426 | |
| 427 | int n = x.size(); |
| 428 | |
| 429 | for (int i = 0; i < n; i++) { |
| 430 | // visit intervals in increasing max order |
| 431 | int x0 = rank[mu[i]].min; |
| 432 | int succ = x0 + 1; |
| 433 | int y = rank[mu[i]].max; |
| 434 | int z = pathmax_t(hall, succ); |
| 435 | int j = hall[z].t; |
| 436 | |
| 437 | /* DOMINATION: |
| 438 | * v^i_j denotes |
| 439 | * unused values in the current interval. If the difference d |
| 440 | * between to critical capacities v^i_j and v^i_z |
| 441 | * is equal to zero, j dominates z |
| 442 | * |
| 443 | * i.e. [hall[l].bounds, hall[nb+1].bounds] is not left-maximal and |
| 444 | * [hall[j].bounds, hall[l].bounds] is a Hall set iff |
| 445 | * [hall[j].bounds, hall[l].bounds] processing a variable x_i uses up a value in the interval |
| 446 | * [hall[z].bounds,hall[z+1].bounds] according to the intervals |
| 447 | * capacity. Therefore, if d = 0 |
| 448 | * the considered value has already been used by processed variables |
| 449 | * m-times, where m = u[i] for value v_i. Since this value must not |
| 450 | * be reconsidered the path can be compressed |
| 451 | */ |
| 452 | if (--hall[z].d == 0) { |
| 453 | hall[z].t = z + 1; |
| 454 | z = pathmax_t(hall, hall[z].t); |
| 455 | if (z >= bsize) |
| 456 | z--; |
| 457 | hall[z].t = j; |
| 458 | } |
| 459 | pathset_t(hall, succ, z, z); // path compression |
| 460 | |