* Simplify Diophantine decision problem. * * Combine identical coefficients, remove unnecessary variables, and trim * bounds. * * The feasible/infeasible decision result is retained. * * Returns: 0 (success), -1 (integer overflow). */
| 594 | * Returns: 0 (success), -1 (integer overflow). |
| 595 | */ |
| 596 | NPY_VISIBILITY_HIDDEN int |
| 597 | diophantine_simplify(unsigned int *n, diophantine_term_t *E, npy_int64 b) |
| 598 | { |
| 599 | unsigned int i, j, m; |
| 600 | char overflow = 0; |
| 601 | |
| 602 | /* Skip obviously infeasible cases */ |
| 603 | for (j = 0; j < *n; ++j) { |
| 604 | if (E[j].ub < 0) { |
| 605 | return 0; |
| 606 | } |
| 607 | } |
| 608 | |
| 609 | if (b < 0) { |
| 610 | return 0; |
| 611 | } |
| 612 | |
| 613 | /* Sort vs. coefficients */ |
| 614 | qsort(E, *n, sizeof(diophantine_term_t), diophantine_sort_A); |
| 615 | |
| 616 | /* Combine identical coefficients */ |
| 617 | m = *n; |
| 618 | i = 0; |
| 619 | for (j = 1; j < m; ++j) { |
| 620 | if (E[i].a == E[j].a) { |
| 621 | E[i].ub = safe_add(E[i].ub, E[j].ub, &overflow); |
| 622 | --*n; |
| 623 | } |
| 624 | else { |
| 625 | ++i; |
| 626 | if (i != j) { |
| 627 | E[i] = E[j]; |
| 628 | } |
| 629 | } |
| 630 | } |
| 631 | |
| 632 | /* Trim bounds and remove unnecessary variables */ |
| 633 | m = *n; |
| 634 | i = 0; |
| 635 | for (j = 0; j < m; ++j) { |
| 636 | E[j].ub = MIN(E[j].ub, b / E[j].a); |
| 637 | if (E[j].ub == 0) { |
| 638 | /* If the problem is feasible at all, x[i]=0 */ |
| 639 | --*n; |
| 640 | } |
| 641 | else { |
| 642 | if (i != j) { |
| 643 | E[i] = E[j]; |
| 644 | } |
| 645 | ++i; |
| 646 | } |
| 647 | } |
| 648 | |
| 649 | if (overflow) { |
| 650 | return -1; |
| 651 | } |
| 652 | else { |
| 653 | return 0; |
no test coverage detected