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