1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10#include <isl/map.h>
11#include <isl/vec.h>
12#include <isl/lp.h>
13#include "isl_piplib.h"
14#include "isl_map_piplib.h"
15
16static void copy_solution(struct isl_vec *vec, int maximize, isl_int *opt,
17	isl_int *opt_denom, PipQuast *sol)
18{
19	int i;
20	PipList *list;
21	isl_int tmp;
22
23	if (opt) {
24		if (opt_denom) {
25			isl_seq_cpy_from_pip(opt,
26				 &sol->list->vector->the_vector[0], 1);
27			isl_seq_cpy_from_pip(opt_denom,
28				 &sol->list->vector->the_deno[0], 1);
29		} else if (maximize)
30			mpz_fdiv_q(*opt, sol->list->vector->the_vector[0],
31					 sol->list->vector->the_deno[0]);
32		else
33			mpz_cdiv_q(*opt, sol->list->vector->the_vector[0],
34					 sol->list->vector->the_deno[0]);
35	}
36
37	if (!vec)
38		return;
39
40	isl_int_init(tmp);
41	isl_int_set_si(vec->el[0], 1);
42	for (i = 0, list = sol->list->next; list; ++i, list = list->next) {
43		isl_seq_cpy_from_pip(&vec->el[1 + i],
44			&list->vector->the_deno[0], 1);
45		isl_int_lcm(vec->el[0], vec->el[0], vec->el[1 + i]);
46	}
47	for (i = 0, list = sol->list->next; list; ++i, list = list->next) {
48		isl_seq_cpy_from_pip(&tmp, &list->vector->the_deno[0], 1);
49		isl_int_divexact(tmp, vec->el[0], tmp);
50		isl_seq_cpy_from_pip(&vec->el[1 + i],
51			&list->vector->the_vector[0], 1);
52		isl_int_mul(vec->el[1 + i], vec->el[1 + i], tmp);
53	}
54	isl_int_clear(tmp);
55}
56
57enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize,
58				      isl_int *f, isl_int denom, isl_int *opt,
59				      isl_int *opt_denom,
60				      struct isl_vec **vec)
61{
62	enum isl_lp_result res = isl_lp_ok;
63	PipMatrix	*domain = NULL;
64	PipOptions	*options;
65	PipQuast   	*sol;
66	unsigned	 total;
67
68	total = isl_basic_map_total_dim(bmap);
69	domain = isl_basic_map_to_pip(bmap, 0, 1, 0);
70	if (!domain)
71		goto error;
72	entier_set_si(domain->p[0][1], -1);
73	isl_int_set(domain->p[0][domain->NbColumns - 1], f[0]);
74	isl_seq_cpy_to_pip(domain->p[0]+2, f+1, total);
75
76	options = pip_options_init();
77	if (!options)
78		goto error;
79	options->Urs_unknowns = -1;
80	options->Maximize = maximize;
81	options->Nq = 0;
82	sol = pip_solve(domain, NULL, -1, options);
83	pip_options_free(options);
84	if (!sol)
85		goto error;
86
87	if (vec) {
88		isl_ctx *ctx = isl_basic_map_get_ctx(bmap);
89		*vec = isl_vec_alloc(ctx, 1 + total);
90	}
91	if (vec && !*vec)
92		res = isl_lp_error;
93	else if (!sol->list)
94		res = isl_lp_empty;
95	else if (entier_zero_p(sol->list->vector->the_deno[0]))
96		res = isl_lp_unbounded;
97	else
98		copy_solution(*vec, maximize, opt, opt_denom, sol);
99	pip_matrix_free(domain);
100	pip_quast_free(sol);
101	return res;
102error:
103	if (domain)
104		pip_matrix_free(domain);
105	return isl_lp_error;
106}
107