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_ctx_private.h>
11#include <isl/seq.h>
12#include <isl/vec.h>
13#include <isl_val_private.h>
14
15isl_ctx *isl_vec_get_ctx(__isl_keep isl_vec *vec)
16{
17	return vec ? vec->ctx : NULL;
18}
19
20struct isl_vec *isl_vec_alloc(struct isl_ctx *ctx, unsigned size)
21{
22	struct isl_vec *vec;
23
24	vec = isl_alloc_type(ctx, struct isl_vec);
25	if (!vec)
26		return NULL;
27
28	vec->block = isl_blk_alloc(ctx, size);
29	if (isl_blk_is_error(vec->block))
30		goto error;
31
32	vec->ctx = ctx;
33	isl_ctx_ref(ctx);
34	vec->ref = 1;
35	vec->size = size;
36	vec->el = vec->block.data;
37
38	return vec;
39error:
40	isl_blk_free(ctx, vec->block);
41	return NULL;
42}
43
44__isl_give isl_vec *isl_vec_extend(__isl_take isl_vec *vec, unsigned size)
45{
46	if (!vec)
47		return NULL;
48	if (size <= vec->size)
49		return vec;
50
51	vec = isl_vec_cow(vec);
52	if (!vec)
53		return NULL;
54
55	vec->block = isl_blk_extend(vec->ctx, vec->block, size);
56	if (!vec->block.data)
57		goto error;
58
59	vec->size = size;
60	vec->el = vec->block.data;
61
62	return vec;
63error:
64	isl_vec_free(vec);
65	return NULL;
66}
67
68__isl_give isl_vec *isl_vec_zero_extend(__isl_take isl_vec *vec, unsigned size)
69{
70	int extra;
71
72	if (!vec)
73		return NULL;
74	if (size <= vec->size)
75		return vec;
76
77	vec = isl_vec_cow(vec);
78	if (!vec)
79		return NULL;
80
81	extra = size - vec->size;
82	vec = isl_vec_extend(vec, size);
83	if (!vec)
84		return NULL;
85
86	isl_seq_clr(vec->el + size - extra, extra);
87
88	return vec;
89}
90
91/* Return a vector containing the elements of "vec1" followed by
92 * those of "vec2".
93 */
94__isl_give isl_vec *isl_vec_concat(__isl_take isl_vec *vec1,
95	__isl_take isl_vec *vec2)
96{
97	if (!vec1 || !vec2)
98		goto error;
99
100	if (vec2->size == 0) {
101		isl_vec_free(vec2);
102		return vec1;
103	}
104
105	if (vec1->size == 0) {
106		isl_vec_free(vec1);
107		return vec2;
108	}
109
110	vec1 = isl_vec_extend(vec1, vec1->size + vec2->size);
111	if (!vec1)
112		goto error;
113
114	isl_seq_cpy(vec1->el + vec1->size - vec2->size, vec2->el, vec2->size);
115
116	isl_vec_free(vec2);
117	return vec1;
118error:
119	isl_vec_free(vec1);
120	isl_vec_free(vec2);
121	return NULL;
122}
123
124struct isl_vec *isl_vec_copy(struct isl_vec *vec)
125{
126	if (!vec)
127		return NULL;
128
129	vec->ref++;
130	return vec;
131}
132
133struct isl_vec *isl_vec_dup(struct isl_vec *vec)
134{
135	struct isl_vec *vec2;
136
137	if (!vec)
138		return NULL;
139	vec2 = isl_vec_alloc(vec->ctx, vec->size);
140	if (!vec2)
141		return NULL;
142	isl_seq_cpy(vec2->el, vec->el, vec->size);
143	return vec2;
144}
145
146struct isl_vec *isl_vec_cow(struct isl_vec *vec)
147{
148	struct isl_vec *vec2;
149	if (!vec)
150		return NULL;
151
152	if (vec->ref == 1)
153		return vec;
154
155	vec2 = isl_vec_dup(vec);
156	isl_vec_free(vec);
157	return vec2;
158}
159
160void *isl_vec_free(__isl_take isl_vec *vec)
161{
162	if (!vec)
163		return NULL;
164
165	if (--vec->ref > 0)
166		return NULL;
167
168	isl_ctx_deref(vec->ctx);
169	isl_blk_free(vec->ctx, vec->block);
170	free(vec);
171
172	return NULL;
173}
174
175int isl_vec_size(__isl_keep isl_vec *vec)
176{
177	return vec ? vec->size : -1;
178}
179
180int isl_vec_get_element(__isl_keep isl_vec *vec, int pos, isl_int *v)
181{
182	if (!vec)
183		return -1;
184
185	if (pos < 0 || pos >= vec->size)
186		isl_die(vec->ctx, isl_error_invalid, "position out of range",
187			return -1);
188	isl_int_set(*v, vec->el[pos]);
189	return 0;
190}
191
192/* Extract the element at position "pos" of "vec".
193 */
194__isl_give isl_val *isl_vec_get_element_val(__isl_keep isl_vec *vec, int pos)
195{
196	isl_ctx *ctx;
197
198	if (!vec)
199		return NULL;
200	ctx = isl_vec_get_ctx(vec);
201	if (pos < 0 || pos >= vec->size)
202		isl_die(ctx, isl_error_invalid, "position out of range",
203			return NULL);
204	return isl_val_int_from_isl_int(ctx, vec->el[pos]);
205}
206
207__isl_give isl_vec *isl_vec_set_element(__isl_take isl_vec *vec,
208	int pos, isl_int v)
209{
210	vec = isl_vec_cow(vec);
211	if (!vec)
212		return NULL;
213	if (pos < 0 || pos >= vec->size)
214		isl_die(vec->ctx, isl_error_invalid, "position out of range",
215			goto error);
216	isl_int_set(vec->el[pos], v);
217	return vec;
218error:
219	isl_vec_free(vec);
220	return NULL;
221}
222
223__isl_give isl_vec *isl_vec_set_element_si(__isl_take isl_vec *vec,
224	int pos, int v)
225{
226	vec = isl_vec_cow(vec);
227	if (!vec)
228		return NULL;
229	if (pos < 0 || pos >= vec->size)
230		isl_die(vec->ctx, isl_error_invalid, "position out of range",
231			goto error);
232	isl_int_set_si(vec->el[pos], v);
233	return vec;
234error:
235	isl_vec_free(vec);
236	return NULL;
237}
238
239/* Replace the element at position "pos" of "vec" by "v".
240 */
241__isl_give isl_vec *isl_vec_set_element_val(__isl_take isl_vec *vec,
242	int pos, __isl_take isl_val *v)
243{
244	if (!v)
245		return isl_vec_free(vec);
246	if (!isl_val_is_int(v))
247		isl_die(isl_val_get_ctx(v), isl_error_invalid,
248			"expecting integer value", goto error);
249	vec = isl_vec_set_element(vec, pos, v->n);
250	isl_val_free(v);
251	return vec;
252error:
253	isl_val_free(v);
254	return isl_vec_free(vec);
255}
256
257/* Compare the elements of "vec1" and "vec2" at position "pos".
258 */
259int isl_vec_cmp_element(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2,
260	int pos)
261{
262	if (!vec1 || !vec2)
263		return 0;
264	if (pos < 0 || pos >= vec1->size || pos >= vec2->size)
265		isl_die(isl_vec_get_ctx(vec1), isl_error_invalid,
266			"position out of range", return 0);
267	return isl_int_cmp(vec1->el[pos], vec2->el[pos]);
268}
269
270int isl_vec_is_equal(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2)
271{
272	if (!vec1 || !vec2)
273		return -1;
274
275	if (vec1->size != vec2->size)
276		return 0;
277
278	return isl_seq_eq(vec1->el, vec2->el, vec1->size);
279}
280
281__isl_give isl_printer *isl_printer_print_vec(__isl_take isl_printer *printer,
282	__isl_keep isl_vec *vec)
283{
284	int i;
285
286	if (!printer || !vec)
287		goto error;
288
289	printer = isl_printer_print_str(printer, "[");
290	for (i = 0; i < vec->size; ++i) {
291		if (i)
292			printer = isl_printer_print_str(printer, ",");
293		printer = isl_printer_print_isl_int(printer, vec->el[i]);
294	}
295	printer = isl_printer_print_str(printer, "]");
296
297	return printer;
298error:
299	isl_printer_free(printer);
300	return NULL;
301}
302
303void isl_vec_dump(struct isl_vec *vec)
304{
305	isl_printer *printer;
306
307	if (!vec)
308		return;
309
310	printer = isl_printer_to_file(vec->ctx, stderr);
311	printer = isl_printer_print_vec(printer, vec);
312	printer = isl_printer_end_line(printer);
313
314	isl_printer_free(printer);
315}
316
317__isl_give isl_vec *isl_vec_set(__isl_take isl_vec *vec, isl_int v)
318{
319	vec = isl_vec_cow(vec);
320	if (!vec)
321		return NULL;
322	isl_seq_set(vec->el, v, vec->size);
323	return vec;
324}
325
326__isl_give isl_vec *isl_vec_set_si(__isl_take isl_vec *vec, int v)
327{
328	vec = isl_vec_cow(vec);
329	if (!vec)
330		return NULL;
331	isl_seq_set_si(vec->el, v, vec->size);
332	return vec;
333}
334
335/* Replace all elements of "vec" by "v".
336 */
337__isl_give isl_vec *isl_vec_set_val(__isl_take isl_vec *vec,
338	__isl_take isl_val *v)
339{
340	vec = isl_vec_cow(vec);
341	if (!vec || !v)
342		goto error;
343	if (!isl_val_is_int(v))
344		isl_die(isl_val_get_ctx(v), isl_error_invalid,
345			"expecting integer value", goto error);
346	isl_seq_set(vec->el, v->n, vec->size);
347	isl_val_free(v);
348	return vec;
349error:
350	isl_vec_free(vec);
351	isl_val_free(v);
352	return NULL;
353}
354
355__isl_give isl_vec *isl_vec_clr(__isl_take isl_vec *vec)
356{
357	vec = isl_vec_cow(vec);
358	if (!vec)
359		return NULL;
360	isl_seq_clr(vec->el, vec->size);
361	return vec;
362}
363
364void isl_vec_lcm(struct isl_vec *vec, isl_int *lcm)
365{
366	isl_seq_lcm(vec->block.data, vec->size, lcm);
367}
368
369/* Given a rational vector, with the denominator in the first element
370 * of the vector, round up all coordinates.
371 */
372struct isl_vec *isl_vec_ceil(struct isl_vec *vec)
373{
374	vec = isl_vec_cow(vec);
375	if (!vec)
376		return NULL;
377
378	isl_seq_cdiv_q(vec->el + 1, vec->el + 1, vec->el[0], vec->size - 1);
379
380	isl_int_set_si(vec->el[0], 1);
381
382	return vec;
383}
384
385struct isl_vec *isl_vec_normalize(struct isl_vec *vec)
386{
387	if (!vec)
388		return NULL;
389	isl_seq_normalize(vec->ctx, vec->el, vec->size);
390	return vec;
391}
392
393__isl_give isl_vec *isl_vec_neg(__isl_take isl_vec *vec)
394{
395	vec = isl_vec_cow(vec);
396	if (!vec)
397		return NULL;
398	isl_seq_neg(vec->el, vec->el, vec->size);
399	return vec;
400}
401
402__isl_give isl_vec *isl_vec_scale(__isl_take isl_vec *vec, isl_int m)
403{
404	if (isl_int_is_one(m))
405		return vec;
406	vec = isl_vec_cow(vec);
407	if (!vec)
408		return NULL;
409	isl_seq_scale(vec->el, vec->el, m, vec->size);
410	return vec;
411}
412
413/* Reduce the elements of "vec" modulo "m".
414 */
415__isl_give isl_vec *isl_vec_fdiv_r(__isl_take isl_vec *vec, isl_int m)
416{
417	vec = isl_vec_cow(vec);
418	if (!vec)
419		return NULL;
420
421	isl_seq_fdiv_r(vec->el, vec->el, m, vec->size);
422
423	return vec;
424}
425
426__isl_give isl_vec *isl_vec_add(__isl_take isl_vec *vec1,
427	__isl_take isl_vec *vec2)
428{
429	vec1 = isl_vec_cow(vec1);
430	if (!vec1 || !vec2)
431		goto error;
432
433	isl_assert(vec1->ctx, vec1->size == vec2->size, goto error);
434
435	isl_seq_combine(vec1->el, vec1->ctx->one, vec1->el,
436			vec1->ctx->one, vec2->el, vec1->size);
437
438	isl_vec_free(vec2);
439	return vec1;
440error:
441	isl_vec_free(vec1);
442	isl_vec_free(vec2);
443	return NULL;
444}
445
446static int qsort_int_cmp(const void *p1, const void *p2)
447{
448	const isl_int *i1 = (const isl_int *) p1;
449	const isl_int *i2 = (const isl_int *) p2;
450
451	return isl_int_cmp(*i1, *i2);
452}
453
454__isl_give isl_vec *isl_vec_sort(__isl_take isl_vec *vec)
455{
456	if (!vec)
457		return NULL;
458
459	qsort(vec->el, vec->size, sizeof(*vec->el), &qsort_int_cmp);
460
461	return vec;
462}
463
464__isl_give isl_vec *isl_vec_drop_els(__isl_take isl_vec *vec,
465	unsigned pos, unsigned n)
466{
467	if (n == 0)
468		return vec;
469	vec = isl_vec_cow(vec);
470	if (!vec)
471		return NULL;
472
473	if (pos + n > vec->size)
474		isl_die(vec->ctx, isl_error_invalid,
475			"range out of bounds", goto error);
476
477	if (pos + n != vec->size)
478		isl_seq_cpy(vec->el + pos, vec->el + pos + n,
479			    vec->size - pos - n);
480
481	vec->size -= n;
482
483	return vec;
484error:
485	isl_vec_free(vec);
486	return NULL;
487}
488
489__isl_give isl_vec *isl_vec_insert_els(__isl_take isl_vec *vec,
490	unsigned pos, unsigned n)
491{
492	isl_vec *ext = NULL;
493
494	if (n == 0)
495		return vec;
496	if (!vec)
497		return NULL;
498
499	if (pos > vec->size)
500		isl_die(vec->ctx, isl_error_invalid,
501			"position out of bounds", goto error);
502
503	ext =  isl_vec_alloc(vec->ctx, vec->size + n);
504	if (!ext)
505		goto error;
506
507	isl_seq_cpy(ext->el, vec->el, pos);
508	isl_seq_cpy(ext->el + pos + n, vec->el + pos, vec->size - pos);
509
510	isl_vec_free(vec);
511	return ext;
512error:
513	isl_vec_free(vec);
514	isl_vec_free(ext);
515	return NULL;
516}
517
518__isl_give isl_vec *isl_vec_insert_zero_els(__isl_take isl_vec *vec,
519	unsigned pos, unsigned n)
520{
521	vec = isl_vec_insert_els(vec, pos, n);
522	if (!vec)
523		return NULL;
524
525	isl_seq_clr(vec->el + pos, n);
526
527	return vec;
528}
529