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