| 300 | } |
| 301 | template<class Card> |
| 302 | inline void |
| 303 | PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) { |
| 304 | int i = 0; |
| 305 | int j = 0; |
| 306 | |
| 307 | // Determine number of holes in the index set |
| 308 | int holes = 0; |
| 309 | for (i = 1; i < elements.size(); i++) { |
| 310 | if (elements[i].card() != elements[i-1].card() + 1) |
| 311 | holes += elements[i].card()-elements[i-1].card()-1; |
| 312 | } |
| 313 | |
| 314 | // we add three elements at the beginning and two at the end |
| 315 | size = elements.size() + holes + 5; |
| 316 | |
| 317 | // memory allocation |
| 318 | if (sum == nullptr) { |
| 319 | sum = home.alloc<int>(2*size); |
| 320 | } |
| 321 | int* ds = &sum[size]; |
| 322 | |
| 323 | int first = elements[0].card(); |
| 324 | |
| 325 | firstValue = first - 3; |
| 326 | lastValue = first + elements.size() + holes + 1; |
| 327 | |
| 328 | // the first three elements |
| 329 | for (i = 3; i--; ) |
| 330 | sum[i] = i; |
| 331 | |
| 332 | /* |
| 333 | * copy the bounds into sum, filling up holes with zeroes |
| 334 | */ |
| 335 | int prevCard = elements[0].card()-1; |
| 336 | i = 0; |
| 337 | for (j = 2; j < elements.size() + holes + 2; j++) { |
| 338 | if (elements[i].card() != prevCard + 1) { |
| 339 | sum[j + 1] = sum[j]; |
| 340 | } else if (up) { |
| 341 | sum[j + 1] = sum[j] + elements[i].max(); |
| 342 | i++; |
| 343 | } else { |
| 344 | sum[j + 1] = sum[j] + elements[i].min(); |
| 345 | i++; |
| 346 | } |
| 347 | prevCard++; |
| 348 | } |
| 349 | sum[j + 1] = sum[j] + 1; |
| 350 | sum[j + 2] = sum[j + 1] + 1; |
| 351 | |
| 352 | // Compute distances, eliminating zeroes |
| 353 | i = elements.size() + holes + 3; |
| 354 | j = i + 1; |
| 355 | for ( ; i > 0; ) { |
| 356 | while(sum[i] == sum[i - 1]) { |
| 357 | ds[i] = j; |
| 358 | i--; |
| 359 | } |