maximize.cc

   1 #include <iostream>
   2 #include <bernstein/bernstein.h>
   3 #include <barvinok/evalue.h>
   4 #include <barvinok/options.h>
   5 #include <barvinok/util.h>
   6 #include <barvinok/bernstein.h>
   7 #include "argp.h"
   8 #include "evalue_convert.h"
   9
  10 using std::cout;
  11 using std::cerr;
  12 using std::endl;
  13 using namespace GiNaC;
  14 using namespace bernstein;
  15 using namespace barvinok;
  16
  17 #define OPT_VARS            (BV_OPT_LAST+1)
  18 #define OPT_SPLIT           (BV_OPT_LAST+2)
  19 #define OPT_MIN             (BV_OPT_LAST+3)
  20
  21 struct argp_option argp_options[] = {
  22     { "split",              OPT_SPLIT,  "int" },
  23     { "variables",          OPT_VARS,   "list", 0,
  24         "comma separated list of variables over which to maximize" },
  25     { "verbose",            'V',        0,      0, },
  26     { "minimize",           OPT_MIN,    0, 0,   "minimize instead of maximize"},
  27     { 0 }
  28 };
  29
  30 struct options {
  31     struct convert_options   convert;
  32     char* var_list;
  33     int verbose;
  34     int split;
  35     int minimize;
  36 };
  37
  38 static error_t parse_opt(int key, char *arg, struct argp_state *state)
  39 {
  40     struct options *options = (struct options*) state->input;
  41
  42     switch (key) {
  43     case ARGP_KEY_INIT:
  44         state->child_inputs[0] = &options->convert;
  45         options->var_list = NULL;
  46         options->verbose = 0;
  47         options->split = 0;
  48         options->minimize = 0;
  49         break;
  50     case 'V':
  51         options->verbose = 1;
  52         break;
  53     case OPT_VARS:
  54         options->var_list = strdup(arg);
  55         break;
  56     case OPT_SPLIT:
  57         options->split = atoi(arg);
  58         break;
  59     case OPT_MIN:
  60         options->minimize = 1;
  61         break;
  62     default:
  63         return ARGP_ERR_UNKNOWN;
  64     }
  65     return 0;
  66 }
  67
  68
  69 #define ALLOC(type) (type*)malloc(sizeof(type))
  70 #define ALLOCN(type,n) (type*)malloc((n) * sizeof(type))
  71
  72 enum token_type { TOKEN_UNKNOWN = 256, TOKEN_VALUE, TOKEN_IDENT, TOKEN_GE,
  73                   TOKEN_UNION };
  74
  75 struct token {
  76     enum token_type  type;
  77
  78     int line;
  79     int col;
  80
  81     union {
  82         Value   v;
  83         char    *s;
  84     } u;
  85 };
  86
  87 static struct token *token_new(int line, int col)
  88 {
  89     struct token *tok = ALLOC(struct token);
  90     tok->line = line;
  91     tok->col = col;
  92     return tok;
  93 }
  94
  95 void token_free(struct token *tok)
  96 {
  97     if (tok->type == TOKEN_VALUE)
  98         value_clear(tok->u.v);
  99     else if (tok->type == TOKEN_IDENT)
 100         free(tok->u.s);
 101     free(tok);
 102 }
 103
 104 struct stream {
 105     FILE            *file;
 106     int             line;
 107     int             col;
 108     int             eof;
 109
 110     char            *buffer;
 111     size_t          size;
 112     size_t          len;
 113     int             c;
 114
 115     struct token    *tokens[5];
 116     int             n_token;
 117 };
 118
 119 static struct stream* stream_new(FILE *file)
 120 {
 121     int i;
 122     struct stream *s = ALLOC(struct stream);
 123     s->file = file;
 124     s->size = 256;
 125     s->buffer = (char*)malloc(s->size);
 126     s->len = 0;
 127     s->line = 1;
 128     s->col = 0;
 129     s->eof = 0;
 130     s->c = -1;
 131     for (i = 0; i < 5; ++i)
 132         s->tokens[i] = NULL;
 133     s->n_token = 0;
 134     return s;
 135 }
 136
 137 static void stream_free(struct stream *s)
 138 {
 139     free(s->buffer);
 140     assert(s->n_token == 0);
 141     free(s);
 142 }
 143
 144 static int stream_getc(struct stream *s)
 145 {
 146     int c;
 147     if (s->eof)
 148         return -1;
 149     c = fgetc(s->file);
 150     if (c == -1)
 151         s->eof = 1;
 152     if (s->c != -1) {
 153         if (s->c == '\n') {
 154             s->line++;
 155             s->col = 0;
 156         } else
 157             s->col++;
 158     }
 159     s->c = c;
 160     return c;
 161 }
 162
 163 static void stream_ungetc(struct stream *s, int c)
 164 {
 165     ungetc(c, s->file);
 166     s->c = -1;
 167 }
 168
 169 static void stream_push_char(struct stream *s, int c)
 170 {
 171     if (s->len >= s->size) {
 172         s->size = (3*s->size)/2;
 173         s->buffer = (char*)realloc(s->buffer, s->size);
 174     }
 175     s->buffer[s->len++] = c;
 176 }
 177
 178 static struct token *stream_push_token(struct stream *s, struct token *tok)
 179 {
 180     assert(s->n_token < 5);
 181     s->tokens[s->n_token++] = tok;
 182 }
 183
 184 static struct token *stream_next_token(struct stream *s)
 185 {
 186     int c;
 187     struct token *tok;
 188     int line, col;
 189
 190     if (s->n_token)
 191         return s->tokens[--s->n_token];
 192
 193     s->len = 0;
 194
 195     /* skip spaces */
 196     while ((c = stream_getc(s)) != -1 && isspace(c))
 197         /* nothing */
 198         ;
 199
 200     line = s->line;
 201     col = s->col;
 202
 203     if (c == -1)
 204         return NULL;
 205     if (c == '(' ||
 206         c == ')' ||
 207         c == '+' ||
 208         c == '/' ||
 209         c == '*' ||
 210         c == '^' ||
 211         c == '=' ||
 212         c == ',' ||
 213         c == '_' ||
 214         c == '[' ||
 215         c == ']' ||
 216         c == '{' ||
 217         c == '}') {
 218         tok = token_new(line, col);
 219         tok->type = (token_type)c;
 220         return tok;
 221     }
 222     if (c == '-' || isdigit(c)) {
 223         tok = token_new(line, col);
 224         tok->type = TOKEN_VALUE;
 225         value_init(tok->u.v);
 226         stream_push_char(s, c);
 227         while ((c = stream_getc(s)) != -1 && isdigit(c))
 228             stream_push_char(s, c);
 229         if (c != -1)
 230             stream_ungetc(s, c);
 231         if (s->len == 1 && s->buffer[0] == '-')
 232             value_set_si(tok->u.v, -1);
 233         else {
 234             stream_push_char(s, '\0');
 235             mpz_set_str(tok->u.v, s->buffer, 0);
 236         }
 237         return tok;
 238     }
 239     if (isalpha(c)) {
 240         tok = token_new(line, col);
 241         stream_push_char(s, c);
 242         while ((c = stream_getc(s)) != -1 && isalpha(c))
 243             stream_push_char(s, c);
 244         if (c != -1)
 245             stream_ungetc(s, c);
 246         stream_push_char(s, '\0');
 247         if (!strcmp(s->buffer, "UNION")) {
 248             tok->type = TOKEN_UNION;
 249         } else {
 250             tok->type = TOKEN_IDENT;
 251             tok->u.s = strdup(s->buffer);
 252         }
 253         return tok;
 254     }
 255     if (c == '>') {
 256         if ((c = stream_getc(s)) == '=') {
 257             tok = token_new(line, col);
 258             tok->type = TOKEN_GE;
 259             return tok;
 260         }
 261         if (c != -1)
 262             stream_ungetc(s, c);
 263     }
 264
 265     tok = token_new(line, col);
 266     tok->type = TOKEN_UNKNOWN;
 267     return tok;
 268 }
 269
 270 void stream_error(struct stream *s, struct token *tok, char *msg)
 271 {
 272     int line = tok ? tok->line : s->line;
 273     int col = tok ? tok->col : s->col;
 274     fprintf(stderr, "syntax error (%d, %d): %s\n", line, col, msg);
 275     if (tok) {
 276         if (tok->type < 256)
 277             fprintf(stderr, "got '%c'\n", tok->type);
 278     }
 279 }
 280
 281 struct parameter {
 282     char                *name;
 283     int                  pos;
 284     struct parameter    *next;
 285 };
 286
 287 struct parameter *parameter_new(char *name, int pos, struct parameter *next)
 288 {
 289     struct parameter *p = ALLOC(struct parameter);
 290     p->name = strdup(name);
 291     p->pos = pos;
 292     p->next = next;
 293     return p;
 294 }
 295
 296 static int parameter_pos(struct parameter **p, char *s)
 297 {
 298     int pos = *p ? (*p)->pos+1 : 0;
 299     struct parameter *q;
 300
 301     for (q = *p; q; q = q->next) {
 302         if (strcmp(q->name, s) == 0)
 303             break;
 304     }
 305     if (q)
 306         pos = q->pos;
 307     else
 308         *p = parameter_new(s, pos, *p);
 309     return pos;
 310 }
 311
 312 static int optional_power(struct stream *s)
 313 {
 314     int pow;
 315     struct token *tok;
 316     tok = stream_next_token(s);
 317     if (!tok)
 318         return 1;
 319     if (tok->type != '^') {
 320         stream_push_token(s, tok);
 321         return 1;
 322     }
 323     token_free(tok);
 324     tok = stream_next_token(s);
 325     if (!tok || tok->type != TOKEN_VALUE) {
 326         stream_error(s, tok, "expecting exponent");
 327         if (tok)
 328             stream_push_token(s, tok);
 329         return 1;
 330     }
 331     pow = VALUE_TO_INT(tok->u.v);
 332     token_free(tok);
 333     return pow;
 334 }
 335
 336 static evalue *evalue_read_factor(struct stream *s, struct parameter **p);
 337 static evalue *evalue_read_term(struct stream *s, struct parameter **p);
 338
 339 static evalue *create_fract_like(struct stream *s, evalue *arg, enode_type type,
 340                                  struct parameter **p)
 341 {
 342     evalue *e;
 343     int pow;
 344     pow = optional_power(s);
 345
 346     e = ALLOC(evalue);
 347     value_init(e->d);
 348     e->x.p = new_enode(type, pow+2, -1);
 349     value_clear(e->x.p->arr[0].d);
 350     e->x.p->arr[0] = *arg;
 351     free(arg);
 352     evalue_set_si(&e->x.p->arr[1+pow], 1, 1);
 353     while (--pow >= 0)
 354         evalue_set_si(&e->x.p->arr[1+pow], 0, 1);
 355
 356     return e;
 357 }
 358
 359 static evalue *read_fract(struct stream *s, struct token *tok, struct parameter **p)
 360 {
 361     evalue *arg;
 362
 363     tok = stream_next_token(s);
 364     assert(tok);
 365     assert(tok->type == '{');
 366
 367     token_free(tok);
 368     arg = evalue_read_term(s, p);
 369     tok = stream_next_token(s);
 370     if (!tok || tok->type != '}') {
 371         stream_error(s, tok, "expecting \"}\"");
 372         if (tok)
 373             stream_push_token(s, tok);
 374     } else
 375         token_free(tok);
 376
 377     return create_fract_like(s, arg, fractional, p);
 378 }
 379
 380 static evalue *read_periodic(struct stream *s, struct parameter **p)
 381 {
 382     evalue **list;
 383     int len;
 384     int n;
 385     evalue *e = NULL;
 386
 387     struct token *tok;
 388     tok = stream_next_token(s);
 389     assert(tok && tok->type == '[');
 390     token_free(tok);
 391
 392     len = 100;
 393     list = (evalue **)malloc(len * sizeof(evalue *));
 394     n = 0;
 395
 396     for (;;) {
 397         evalue *e = evalue_read_term(s, p);
 398         if (!e) {
 399             stream_error(s, NULL, "missing argument or list element");
 400             goto out;
 401         }
 402         if (n >= len) {
 403             len = (3*len)/2;
 404             list = (evalue **)realloc(list, len * sizeof(evalue *));
 405         }
 406         list[n++] = e;
 407
 408         tok = stream_next_token(s);
 409         if (!tok) {
 410             stream_error(s, NULL, "unexpected EOF");
 411             goto out;
 412         }
 413         if (tok->type != ',')
 414             break;
 415         token_free(tok);
 416     }
 417
 418     if (tok->type != ']') {
 419         stream_error(s, tok, "expecting \"]\"");
 420         stream_push_token(s, tok);
 421         goto out;
 422     }
 423
 424     token_free(tok);
 425
 426     tok = stream_next_token(s);
 427     if (tok->type == '_') {
 428         int pos;
 429         token_free(tok);
 430         tok = stream_next_token(s);
 431         if (!tok || tok->type != TOKEN_IDENT) {
 432             stream_error(s, tok, "expecting identifier");
 433             if (tok)
 434                 stream_push_token(s, tok);
 435             goto out;
 436         }
 437         e = ALLOC(evalue);
 438         value_init(e->d);
 439         pos = parameter_pos(p, tok->u.s);
 440         token_free(tok);
 441         e->x.p = new_enode(periodic, n, pos+1);
 442         while (--n >= 0) {
 443             value_clear(e->x.p->arr[n].d);
 444             e->x.p->arr[n] = *list[n];
 445             free(list[n]);
 446         }
 447     } else if (n == 1) {
 448         stream_push_token(s, tok);
 449         e = create_fract_like(s, list[0], flooring, p);
 450         n = 0;
 451     } else {
 452         stream_error(s, tok, "unexpected token");
 453         stream_push_token(s, tok);
 454     }
 455
 456 out:
 457     while (--n >= 0) {
 458         free_evalue_refs(list[n]);
 459         free(list[n]);
 460     }
 461     free(list);
 462     return e;
 463 }
 464
 465 static evalue *evalue_read_factor(struct stream *s, struct parameter **p)
 466 {
 467     struct token *tok;
 468     evalue *e = NULL;
 469
 470     tok = stream_next_token(s);
 471     if (!tok)
 472         return NULL;
 473
 474     if (tok->type == '(') {
 475         token_free(tok);
 476         e = evalue_read_term(s, p);
 477         tok = stream_next_token(s);
 478         if (!tok || tok->type != ')') {
 479             stream_error(s, tok, "expecting \")\"");
 480             if (tok)
 481                 stream_push_token(s, tok);
 482         } else
 483             token_free(tok);
 484     } else if (tok->type == TOKEN_VALUE) {
 485         e = ALLOC(evalue);
 486         value_init(e->d);
 487         value_set_si(e->d, 1);
 488         value_init(e->x.n);
 489         value_assign(e->x.n, tok->u.v);
 490         token_free(tok);
 491         tok = stream_next_token(s);
 492         if (tok && tok->type == '/') {
 493             token_free(tok);
 494             tok = stream_next_token(s);
 495             if (!tok || tok->type != TOKEN_VALUE) {
 496                 stream_error(s, tok, "expecting denominator");
 497                 if (tok)
 498                     stream_push_token(s, tok);
 499                 return NULL;
 500             }
 501             value_assign(e->d, tok->u.v);
 502             token_free(tok);
 503         } else if (tok)
 504             stream_push_token(s, tok);
 505     } else if (tok->type == TOKEN_IDENT) {
 506         int pos = parameter_pos(p, tok->u.s);
 507         int pow = optional_power(s);
 508         token_free(tok);
 509         e = ALLOC(evalue);
 510         value_init(e->d);
 511         e->x.p = new_enode(polynomial, pow+1, pos+1);
 512         evalue_set_si(&e->x.p->arr[pow], 1, 1);
 513         while (--pow >= 0)
 514             evalue_set_si(&e->x.p->arr[pow], 0, 1);
 515     } else if (tok->type == '[') {
 516         stream_push_token(s, tok);
 517         e = read_periodic(s, p);
 518     } else if (tok->type == '{') {
 519         stream_push_token(s, tok);
 520         e = read_fract(s, tok, p);
 521     }
 522
 523     tok = stream_next_token(s);
 524     if (tok && tok->type == '*') {
 525         evalue *e2;
 526         token_free(tok);
 527         e2 = evalue_read_factor(s, p);
 528         if (!e2) {
 529             stream_error(s, NULL, "unexpected EOF");
 530             return NULL;
 531         }
 532         emul(e2, e);
 533         free_evalue_refs(e2);
 534         free(e2);
 535     } else if (tok)
 536         stream_push_token(s, tok);
 537
 538     return e;
 539 }
 540
 541 static evalue *evalue_read_term(struct stream *s, struct parameter **p)
 542 {
 543     struct token *tok;
 544     evalue *e = NULL;
 545
 546     e = evalue_read_factor(s, p);
 547     if (!e)
 548         return NULL;
 549
 550     tok = stream_next_token(s);
 551     if (!tok)
 552         return e;
 553
 554     if (tok->type == '+') {
 555         evalue *e2;
 556         token_free(tok);
 557         e2 = evalue_read_term(s, p);
 558         if (!e2) {
 559             stream_error(s, NULL, "unexpected EOF");
 560             return NULL;
 561         }
 562         eadd(e2, e);
 563         free_evalue_refs(e2);
 564         free(e2);
 565     } else
 566         stream_push_token(s, tok);
 567
 568     return e;
 569 }
 570
 571 struct constraint {
 572     int                  type;
 573     Vector              *v;
 574     struct constraint   *next;
 575     struct constraint   *union_next;
 576 };
 577
 578 static struct constraint *constraint_new()
 579 {
 580     struct constraint *c = ALLOC(struct constraint);
 581     c->type = -1;
 582     c->v = Vector_Alloc(16);
 583     c->next = NULL;
 584     c->union_next = NULL;
 585     return c;
 586 }
 587
 588 static void constraint_free(struct constraint *c)
 589 {
 590     while (c) {
 591         struct constraint *next = c->next ? c->next : c->union_next;
 592         Vector_Free(c->v);
 593         free(c);
 594         c = next;
 595     }
 596 }
 597
 598 static void constraint_extend(struct constraint *c, int pos)
 599 {
 600     Vector *v;
 601     if (pos < c->v->Size)
 602         return;
 603
 604     v = Vector_Alloc((3*c->v->Size)/2);
 605     Vector_Copy(c->v->p, v->p, c->v->Size);
 606     Vector_Free(c->v);
 607     c->v = v;
 608 }
 609
 610 static int evalue_read_constraint(struct stream *s, struct parameter **p,
 611                                   struct constraint **constraints,
 612                                   struct constraint *union_next)
 613 {
 614     struct token *tok;
 615     struct constraint *c = NULL;
 616
 617     while ((tok = stream_next_token(s))) {
 618         struct token *tok2;
 619         int pos;
 620         if (tok->type == '+')
 621             token_free(tok);
 622         else if (tok->type == TOKEN_IDENT) {
 623             if (!c)
 624                 c = constraint_new();
 625             pos = parameter_pos(p, tok->u.s);
 626             constraint_extend(c, 1+pos);
 627             value_set_si(c->v->p[1+pos], 1);
 628             token_free(tok);
 629         } else if (tok->type == TOKEN_VALUE) {
 630             if (!c)
 631                 c = constraint_new();
 632             tok2 = stream_next_token(s);
 633             if (tok2 && tok2->type == TOKEN_IDENT) {
 634                 pos = parameter_pos(p, tok2->u.s);
 635                 constraint_extend(c, 1+pos);
 636                 value_assign(c->v->p[1+pos], tok->u.v);
 637                 token_free(tok);
 638                 token_free(tok2);
 639             } else {
 640                 if (tok2)
 641                     stream_push_token(s, tok2);
 642                 value_assign(c->v->p[0], tok->u.v);
 643                 token_free(tok);
 644             }
 645         } else if (tok->type == TOKEN_GE || tok->type == '=') {
 646             int type = tok->type == TOKEN_GE;
 647             token_free(tok);
 648             tok = stream_next_token(s);
 649             if (!tok || tok->type != TOKEN_VALUE || value_notzero_p(tok->u.v)) {
 650                 stream_error(s, tok, "expecting \"0\"");
 651                 if (tok)
 652                     stream_push_token(s, tok);
 653                 *constraints = NULL;
 654             } else {
 655                 c->type = type;
 656                 c->next = *constraints;
 657                 c->union_next = union_next;
 658                 *constraints = c;
 659                 token_free(tok);
 660             }
 661             break;
 662         } else {
 663             if (!c)
 664                 stream_push_token(s, tok);
 665             else {
 666                 stream_error(s, tok, "unexpected token");
 667                 *constraints = NULL;
 668             }
 669             return 0;
 670         }
 671     }
 672     return tok != NULL;
 673 }
 674
 675 static struct constraint *evalue_read_domain(struct stream *s, struct parameter **p,
 676                                              unsigned MaxRays)
 677 {
 678     struct constraint *constraints = NULL;
 679     struct constraint *union_next = NULL;
 680     struct token *tok;
 681     int line;
 682
 683     tok = stream_next_token(s);
 684     if (!tok)
 685         return NULL;
 686     stream_push_token(s, tok);
 687
 688     line = tok->line;
 689     while (evalue_read_constraint(s, p, &constraints, union_next)) {
 690         tok = stream_next_token(s);
 691         if (tok) {
 692             if (tok->type == TOKEN_UNION) {
 693                 token_free(tok);
 694                 tok = stream_next_token(s);
 695                 if (!tok) {
 696                     stream_error(s, NULL, "unexpected EOF");
 697                     return constraints;
 698                 }
 699                 stream_push_token(s, tok);
 700                 union_next = constraints;
 701                 constraints = NULL;
 702             } else {
 703                 union_next = NULL;
 704                 stream_push_token(s, tok);
 705                 /* empty line separates domain from evalue */
 706                 if (tok->line > line+1)
 707                     break;
 708             }
 709             line = tok->line;
 710         }
 711     }
 712     return constraints;
 713 }
 714
 715 struct section {
 716     struct constraint   *constraints;
 717     evalue              *e;
 718     struct section      *next;
 719 };
 720
 721 static char **extract_parameters(struct parameter *p, unsigned *nparam)
 722 {
 723     int i;
 724     char **params;
 725
 726     *nparam = p ? p->pos+1 : 0;
 727     params = ALLOCN(char *, *nparam);
 728     for (i = 0; i < *nparam; ++i) {
 729         struct parameter *next = p->next;
 730         params[p->pos] = p->name;
 731         free(p);
 732         p = next;
 733     }
 734     return params;
 735 }
 736
 737 static Polyhedron *constraints2domain(struct constraint *constraints,
 738                                       unsigned nparam, unsigned MaxRays)
 739 {
 740     Polyhedron *D;
 741     Matrix *M;
 742     int n;
 743     struct constraint *c;
 744     struct constraint *union_next = NULL;
 745
 746     for (n = 0, c = constraints; c; ++n, c = c->next)
 747         ;
 748     M = Matrix_Alloc(n, 1+nparam+1);
 749     while (--n >= 0) {
 750         struct constraint *next = constraints->next;
 751         union_next = constraints->union_next;
 752         Vector_Copy(constraints->v->p+1, M->p[n]+1, nparam);
 753         if (constraints->type)
 754             value_set_si(M->p[n][0], 1);
 755         value_assign(M->p[n][1+nparam], constraints->v->p[0]);
 756         constraints->next = NULL;
 757         constraints->union_next = NULL;
 758         constraint_free(constraints);
 759         constraints = next;
 760     }
 761     D = Constraints2Polyhedron(M, MaxRays);
 762     Matrix_Free(M);
 763
 764     if (union_next)
 765         D = DomainConcat(D, constraints2domain(union_next, nparam, MaxRays));
 766     return D;
 767 }
 768
 769 static evalue *evalue_read_partition(struct stream *s, struct parameter *p,
 770                                      char ***ppp,
 771                                      unsigned *nparam, unsigned MaxRays)
 772 {
 773     struct section *part = NULL;
 774     struct constraint *constraints;
 775     evalue *e = NULL;
 776     int m = 0;
 777
 778     while ((constraints = evalue_read_domain(s, &p, MaxRays))) {
 779         evalue *e = evalue_read_term(s, &p);
 780         if (!e) {
 781             stream_error(s, NULL, "missing evalue");
 782             break;
 783         }
 784         struct section *sect = ALLOC(struct section);
 785         sect->constraints = constraints;
 786         sect->e = e;
 787         sect->next = part;
 788         part = sect;
 789         ++m;
 790     }
 791
 792     if (part) {
 793         Polyhedron *D;
 794         int j;
 795
 796         *ppp = extract_parameters(p, nparam);
 797         e = ALLOC(evalue);
 798         value_init(e->d);
 799         e->x.p = new_enode(partition, 2*m, *nparam);
 800
 801         for (j = 0; j < m; ++j) {
 802             int n;
 803             struct section *next = part->next;
 804             constraints = part->constraints;
 805             D = constraints2domain(part->constraints, *nparam, MaxRays);
 806             EVALUE_SET_DOMAIN(e->x.p->arr[2*j], D);
 807             value_clear(e->x.p->arr[2*j+1].d);
 808             e->x.p->arr[2*j+1] = *part->e;
 809             free(part->e);
 810             free(part);
 811             part = next;
 812         }
 813     }
 814     return e;
 815 }
 816
 817 static evalue *evalue_read(FILE *in, char *var_list, char ***ppp, unsigned *nvar,
 818                            unsigned *nparam, unsigned MaxRays)
 819 {
 820     struct stream *s = stream_new(in);
 821     struct token *tok;
 822     evalue *e;
 823     struct parameter *p = NULL;
 824     char *next;
 825     int nv;
 826
 827     if (var_list) {
 828         while ((next = strchr(var_list, ','))) {
 829             *next = '\0';
 830             if (next > var_list)
 831                 parameter_pos(&p, var_list);
 832             *next = ',';
 833             var_list = next+1;
 834         }
 835         if (strlen(var_list) > 0)
 836             parameter_pos(&p, var_list);
 837         nv = p ? p->pos+1 : 0;
 838     } else
 839         nv = -1;
 840
 841     if (!(tok = stream_next_token(s)))
 842         return NULL;
 843
 844     if (tok->type == TOKEN_VALUE) {
 845         struct token *tok2 = stream_next_token(s);
 846         if (tok2)
 847             stream_push_token(s, tok2);
 848         stream_push_token(s, tok);
 849         if (tok2 && (tok2->type == TOKEN_IDENT || tok2->type == TOKEN_GE))
 850             e = evalue_read_partition(s, p, ppp, nparam, MaxRays);
 851         else {
 852             e = evalue_read_term(s, &p);
 853             *ppp = extract_parameters(p, nparam);
 854         }
 855     } else if (tok->type == TOKEN_IDENT) {
 856         stream_push_token(s, tok);
 857         e = evalue_read_partition(s, p, ppp, nparam, MaxRays);
 858     }
 859     stream_free(s);
 860     if (nv == -1)
 861         *nvar = *nparam;
 862     else
 863         *nvar = nv;
 864     *nparam -= *nvar;
 865     return e;
 866 }
 867
 868 static void optimize(evalue *EP, char **all_vars, unsigned nvar, unsigned nparam,
 869                      struct options *options, barvinok_options *bv_options)
 870 {
 871     Polyhedron *U;
 872     piecewise_lst *pl = NULL;
 873     U = Universe_Polyhedron(nparam);
 874
 875     exvector params;
 876     params = constructParameterVector(all_vars+nvar, nparam);
 877
 878     if (options->minimize)
 879         bv_options->bernstein_optimize = BV_BERNSTEIN_MIN;
 880     else
 881         bv_options->bernstein_optimize = BV_BERNSTEIN_MAX;
 882     pl = evalue_bernstein_coefficients(NULL, EP, U, params, bv_options);
 883     assert(pl);
 884     if (options->minimize)
 885         pl->minimize();
 886     else
 887         pl->maximize();
 888     cout << *pl << endl;
 889     delete pl;
 890
 891     Polyhedron_Free(U);
 892 }
 893
 894 int main(int argc, char **argv)
 895 {
 896     evalue *EP;
 897     char **all_vars = NULL;
 898     unsigned nvar;
 899     unsigned nparam;
 900     struct options options;
 901     struct barvinok_options *bv_options = barvinok_options_new_with_defaults();
 902     static struct argp_child argp_children[] = {
 903         { &convert_argp,        0,      "input conversion",     1 },
 904         { 0 }
 905     };
 906     static struct argp argp = { argp_options, parse_opt, 0, 0, argp_children };
 907
 908     argp_parse(&argp, argc, argv, 0, 0, &options);
 909
 910     EP = evalue_read(stdin, options.var_list, &all_vars, &nvar, &nparam,
 911                      bv_options->MaxRays);
 912     assert(EP);
 913
 914     if (options.split)
 915         evalue_split_periods(EP, options.split, bv_options->MaxRays);
 916
 917     evalue_convert(EP, &options.convert, nparam, options.verbose ? all_vars : NULL);
 918
 919     if (EVALUE_IS_ZERO(*EP))
 920         print_evalue(stdout, EP, all_vars);
 921     else
 922         optimize(EP, all_vars, nvar, nparam, &options, bv_options);
 923
 924     free_evalue_refs(EP);
 925     free(EP);
 926
 927     if (options.var_list)
 928         free(options.var_list);
 929     Free_ParamNames(all_vars, nvar+nparam);
 930     barvinok_options_free(bv_options);
 931     return 0;
 932 }