3 #include <barvinok/barvinok.h>
4 #include <barvinok/set.h>
5 #include <barvinok/options.h>
6 #include <barvinok/evalue.h>
7 #include <barvinok/util.h>
8 #include "conversion.h"
9 #include "evalue_read.h"
11 #include "lattice_point.h"
13 #include "bernoulli.h"
14 #include "matrix_read.h"
21 void set_from_string(T
& v
, const char *s
)
23 std::istringstream
str(s
);
27 int test_evalue(struct barvinok_options
*options
)
29 unsigned nvar
, nparam
;
33 poly1
= evalue_read_from_str("(1/4 * n^4 + 1/2 * n^3 + 1/4 * n^2)",
34 NULL
, &all_vars
, &nvar
, &nparam
,
36 Free_ParamNames(all_vars
, nvar
+nparam
);
39 evalue_copy(&poly2
, poly1
);
43 assert(EVALUE_IS_ZERO(*poly1
));
45 free_evalue_refs(&poly2
);
48 int test_split_periods(struct barvinok_options
*options
)
50 unsigned nvar
, nparam
;
54 e
= evalue_read_from_str("U + 2V + 3 >= 0\n- U -2V >= 0\n- U 10 >= 0\n"
55 "U >= 0\n\n({( 1/3 * U + ( 2/3 * V + 0 ))})",
56 NULL
, &all_vars
, &nvar
, &nparam
,
58 Free_ParamNames(all_vars
, nvar
+nparam
);
60 evalue_split_periods(e
, 2, options
->MaxRays
);
61 assert(value_zero_p(e
->d
));
62 assert(e
->x
.p
->type
== partition
);
63 assert(e
->x
.p
->size
== 4);
64 assert(value_zero_p(e
->x
.p
->arr
[1].d
));
65 assert(e
->x
.p
->arr
[1].x
.p
->type
== polynomial
);
66 assert(value_zero_p(e
->x
.p
->arr
[3].d
));
67 assert(e
->x
.p
->arr
[3].x
.p
->type
== polynomial
);
71 int test_specialization(struct barvinok_options
*options
)
80 assert(value_cmp_si(n
.coeff
->p
[0], 1) == 0);
81 assert(value_cmp_si(n
.coeff
->p
[1], 5) == 0);
82 assert(value_cmp_si(n
.coeff
->p
[2], 10) == 0);
89 assert(value_cmp_si(d
.coeff
->p
[0], 2) == 0);
90 assert(value_cmp_si(d
.coeff
->p
[1], 1) == 0);
91 assert(value_cmp_si(d
.coeff
->p
[2], 0) == 0);
94 mpq_canonicalize(count
);
95 assert(value_cmp_si(mpq_numref(count
), 31) == 0);
96 assert(value_cmp_si(mpq_denref(count
), 8) == 0);
100 assert(value_cmp_si(n2
.coeff
->p
[0], 1) == 0);
101 assert(value_cmp_si(n2
.coeff
->p
[1], -2) == 0);
102 assert(value_cmp_si(n2
.coeff
->p
[2], 3) == 0);
105 mpq_canonicalize(count
);
106 assert(value_cmp_si(mpq_numref(count
), 6) == 0);
107 assert(value_cmp_si(mpq_denref(count
), 1) == 0);
113 int test_lattice_points(struct barvinok_options
*options
)
117 set_from_string(tmp
, "[[0 0 0 0 4][0 0 0 0 4][-1 0 1 0 4]]");
118 V
.Vertex
= zz2matrix(tmp
);
120 set_from_string(lambda
, "[3 5 7]");
122 set_from_string(rays
, "[[0 1 0][4 0 1][0 0 -1]]");
126 unsigned nvar
, nparam
;
128 point
[0] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
129 "( 7 * {( 1/4 * a + ( 3/4 * c + 3/4 ) ) } + -21/4 ) ) )",
130 "a,b,c", &all_vars
, &nvar
, &nparam
, options
->MaxRays
);
131 Free_ParamNames(all_vars
, nvar
+nparam
);
132 point
[1] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
133 "( 7 * {( 1/4 * a + ( 3/4 * c + 1/2 ) ) } + -1/2 ) ) )",
134 "a,b,c", &all_vars
, &nvar
, &nparam
, options
->MaxRays
);
135 Free_ParamNames(all_vars
, nvar
+nparam
);
136 point
[2] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
137 "( 7 * {( 1/4 * a + ( 3/4 * c + 1/4 ) ) } + 17/4 ) ) )",
138 "a,b,c", &all_vars
, &nvar
, &nparam
, options
->MaxRays
);
139 Free_ParamNames(all_vars
, nvar
+nparam
);
140 point
[3] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
141 "( 7 * {( 1/4 * a + ( 3/4 * c + 0 ) ) } + 9 ) ) )",
142 "a,b,c", &all_vars
, &nvar
, &nparam
, options
->MaxRays
);
143 Free_ParamNames(all_vars
, nvar
+nparam
);
145 lattice_point(&V
, rays
, lambda
, &num
, 4, options
);
146 Matrix_Free(V
.Vertex
);
148 for (int i
= 0; i
< 4; ++i
) {
149 assert(eequal(num
.E
[i
], point
[i
]));
150 evalue_free(point
[i
]);
151 free_evalue_refs(num
.E
[i
]);
157 static int test_icounter(struct barvinok_options
*options
)
163 set_from_string(n_coeff
, "[-2/1 1/1]");
164 set_from_string(n_power
, "[[2 6][3 6]]");
165 d_power
.SetDims(0, 2);
166 cnt
.reduce(n_coeff
, n_power
, d_power
);
167 assert(value_cmp_si(mpq_numref(cnt
.count
), -1) == 0);
168 assert(value_cmp_si(mpq_denref(cnt
.count
), 1) == 0);
171 static Matrix
*matrix_read_from_str(const char *s
)
173 std::istringstream
str(s
);
174 return Matrix_Read(str
);
177 static int test_series(struct barvinok_options
*options
)
179 Matrix
*M
= matrix_read_from_str(
181 " 0 1 0 0 0 0 0 1 0 0 3 \n"
182 " 0 0 1 0 0 0 0 -1 1 0 -5 \n"
183 " 0 0 0 1 0 0 0 0 -2 -1 6 \n"
184 " 0 0 0 0 1 0 0 1 1 0 5 \n"
185 " 0 0 0 0 0 1 0 0 -1 0 0 \n"
186 " 0 0 0 0 0 0 1 -2 0 -1 -3 \n"
187 " 1 0 0 0 0 0 0 2 0 1 3 \n"
188 " 1 0 0 0 0 0 0 1 -1 0 5 \n"
189 " 1 0 0 0 0 0 0 -1 -1 0 -5 \n"
190 " 1 0 0 0 0 0 0 -1 0 0 -3 \n"
191 " 1 0 0 0 0 0 0 0 2 1 -6 \n"
192 " 1 0 0 0 0 0 0 0 1 0 0 \n");
193 Polyhedron
*P
= Constraints2Polyhedron(M
, options
->MaxRays
);
195 Polyhedron
*C
= Universe_Polyhedron(3);
196 gen_fun
*gf
= barvinok_series_with_options(P
, C
, options
);
201 M
= matrix_read_from_str(
203 " 0 1 1 0 0 1 0 2 \n"
204 " 0 0 0 1 0 -2 0 6 \n"
205 " 0 0 0 0 1 -1 0 -1 \n"
206 " 0 0 0 0 0 0 1 0 \n"
207 " 1 0 1 0 0 0 0 0 \n"
208 " 1 0 -1 0 0 -1 0 -2 \n"
209 " 1 0 0 0 0 1 0 -3 \n");
210 P
= Constraints2Polyhedron(M
, options
->MaxRays
);
212 C
= Universe_Polyhedron(2);
213 gf
= barvinok_series_with_options(P
, C
, options
);
221 int test_todd(struct barvinok_options
*options
)
223 tcounter
t(2, options
->max_index
);
224 assert(value_cmp_si(t
.todd
.coeff
->p
[0], 1) == 0);
225 assert(value_cmp_si(t
.todd
.coeff
->p
[1], -3) == 0);
226 assert(value_cmp_si(t
.todd
.coeff
->p
[2], 3) == 0);
227 assert(value_cmp_si(t
.todd_denom
->p
[0], 1) == 0);
228 assert(value_cmp_si(t
.todd_denom
->p
[1], 6) == 0);
229 assert(value_cmp_si(t
.todd_denom
->p
[2], 36) == 0);
232 set_from_string(lambda
, "[1 -1]");
233 zz2values(lambda
, t
.lambda
->p
);
236 set_from_string(rays
, "[[-1 0][-1 1]]");
241 set_from_string(v
, "[2 0 1]");
242 Vector
*vertex
= Vector_Alloc(3);
243 zz2values(v
, vertex
->p
);
245 t
.handle(rays
, vertex
->p
, one
, 1, options
);
246 assert(value_cmp_si(mpq_numref(t
.count
), 71) == 0);
247 assert(value_cmp_si(mpq_denref(t
.count
), 24) == 0);
249 set_from_string(rays
, "[[0 -1][1 -1]]");
250 set_from_string(v
, "[0 2 1]");
251 zz2values(v
, vertex
->p
);
253 t
.handle(rays
, vertex
->p
, one
, 1, options
);
254 assert(value_cmp_si(mpq_numref(t
.count
), 71) == 0);
255 assert(value_cmp_si(mpq_denref(t
.count
), 12) == 0);
257 set_from_string(rays
, "[[1 0][0 1]]");
258 set_from_string(v
, "[0 0 1]");
259 zz2values(v
, vertex
->p
);
261 t
.handle(rays
, vertex
->p
, one
, 1, options
);
262 assert(value_cmp_si(mpq_numref(t
.count
), 6) == 0);
263 assert(value_cmp_si(mpq_denref(t
.count
), 1) == 0);
268 int test_bernoulli(struct barvinok_options
*options
)
270 struct bernoulli_coef
*bernoulli_coef
;
271 struct poly_list
*faulhaber
, *bernoulli
;
272 bernoulli_coef
= bernoulli_coef_compute(2);
273 faulhaber
= faulhaber_compute(4);
274 bernoulli_coef
= bernoulli_coef_compute(8);
275 assert(value_cmp_si(bernoulli_coef
->num
->p
[6], 1) == 0);
276 assert(value_cmp_si(bernoulli_coef
->den
->p
[6], 42) == 0);
277 assert(value_cmp_si(faulhaber
->poly
[3]->p
[0], 0) == 0);
278 assert(value_cmp_si(faulhaber
->poly
[3]->p
[1], 0) == 0);
279 assert(value_cmp_si(faulhaber
->poly
[3]->p
[2], 1) == 0);
280 assert(value_cmp_si(faulhaber
->poly
[3]->p
[3], -2) == 0);
281 assert(value_cmp_si(faulhaber
->poly
[3]->p
[4], 1) == 0);
282 assert(value_cmp_si(faulhaber
->poly
[3]->p
[5], 4) == 0);
284 bernoulli
= bernoulli_compute(6);
285 assert(value_cmp_si(bernoulli
->poly
[6]->p
[0], 1) == 0);
286 assert(value_cmp_si(bernoulli
->poly
[6]->p
[1], 0) == 0);
287 assert(value_cmp_si(bernoulli
->poly
[6]->p
[2], -21) == 0);
288 assert(value_cmp_si(bernoulli
->poly
[6]->p
[3], 0) == 0);
289 assert(value_cmp_si(bernoulli
->poly
[6]->p
[4], 105) == 0);
290 assert(value_cmp_si(bernoulli
->poly
[6]->p
[5], -126) == 0);
291 assert(value_cmp_si(bernoulli
->poly
[6]->p
[6], 42) == 0);
292 assert(value_cmp_si(bernoulli
->poly
[6]->p
[7], 42) == 0);
294 unsigned nvar
, nparam
;
296 evalue
*base
, *sum1
, *sum2
;
297 base
= evalue_read_from_str("(1 * n + 1)", NULL
, &all_vars
, &nvar
, &nparam
,
300 sum1
= evalue_polynomial(faulhaber
->poly
[3], base
);
301 Free_ParamNames(all_vars
, nvar
+nparam
);
303 sum2
= evalue_read_from_str("(1/4 * n^4 + 1/2 * n^3 + 1/4 * n^2)",
304 NULL
, &all_vars
, &nvar
, &nparam
,
306 Free_ParamNames(all_vars
, nvar
+nparam
);
307 assert(eequal(sum1
, sum2
));
313 int test_bernoulli_sum(struct barvinok_options
*options
)
315 unsigned nvar
, nparam
;
317 evalue
*e
, *sum1
, *sum2
;
318 e
= evalue_read_from_str("i + -1 >= 0\n -i + n >= 0\n\n 1 + (-1 *i) + i^2",
319 "i", &all_vars
, &nvar
, &nparam
,
321 Free_ParamNames(all_vars
, nvar
+nparam
);
323 sum1
= Bernoulli_sum_evalue(e
, 1, options
);
324 sum2
= evalue_read_from_str("n -1 >= 0\n\n (1/3 * n^3 + 2/3 * n)",
325 NULL
, &all_vars
, &nvar
, &nparam
,
327 Free_ParamNames(all_vars
, nvar
+nparam
);
331 assert(EVALUE_IS_ZERO(*sum1
));
335 e
= evalue_read_from_str("-i + -1 >= 0\n i + n >= 0\n\n 1 + i + i^2",
336 "i", &all_vars
, &nvar
, &nparam
,
338 Free_ParamNames(all_vars
, nvar
+nparam
);
339 sum1
= Bernoulli_sum_evalue(e
, 1, options
);
343 assert(EVALUE_IS_ZERO(*sum1
));
349 e
= evalue_read_from_str("i + 4 >= 0\n -i + n >= 0\n\n i",
350 "i", &all_vars
, &nvar
, &nparam
,
352 Free_ParamNames(all_vars
, nvar
+nparam
);
353 sum1
= Bernoulli_sum_evalue(e
, 1, options
);
354 sum2
= evalue_read_from_str("n + 0 >= 0\n\n (1/2 * n^2 + 1/2 * n + (-10))\n"
355 "n + 4 >= 0\n -n -1 >= 0\n\n (1/2 * n^2 + 1/2 * n + (-10))",
356 NULL
, &all_vars
, &nvar
, &nparam
,
358 Free_ParamNames(all_vars
, nvar
+nparam
);
362 assert(EVALUE_IS_ZERO(*sum1
));
367 e
= evalue_read_from_str("i -5 >= 0\n -i + n >= 0\n j -1 >= 0\n i -j >= 0\n"
368 "k -1 >= 0\n j -k >= 0\n\n1",
369 "i,j,k", &all_vars
, &nvar
, &nparam
,
371 Free_ParamNames(all_vars
, nvar
+nparam
);
372 sum1
= Bernoulli_sum_evalue(e
, 3, options
);
373 sum2
= evalue_read_from_str("n -5 >= 0\n\n"
374 "1/6 * n^3 + 1/2 * n^2 + 1/3 * n + -20",
375 NULL
, &all_vars
, &nvar
, &nparam
,
377 Free_ParamNames(all_vars
, nvar
+nparam
);
381 assert(EVALUE_IS_ZERO(*sum1
));
387 int main(int argc
, char **argv
)
389 struct barvinok_options
*options
= barvinok_options_new_with_defaults();
390 test_evalue(options
);
391 test_split_periods(options
);
392 test_specialization(options
);
393 test_lattice_points(options
);
394 test_icounter(options
);
395 test_series(options
);
397 test_bernoulli(options
);
398 test_bernoulli_sum(options
);
399 barvinok_options_free(options
);