1 /**
2 * Copyright 2015, SRI International.
3 *
4 * This file is part of LibPoly.
5 *
6 * LibPoly is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * LibPoly is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public License
17 * along with LibPoly. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "polypyVariable.h"
21 #include "polypyInteger.h"
22 #include "polypyPolynomial.h"
23 #include "utils.h"
24
25 #include <structmember.h>
26
27 /** Default variable database */
28 static lp_variable_db_t* default_var_db = 0;
29
Variable_init_default_db(void)30 void Variable_init_default_db(void) {
31 if (default_var_db) {
32 lp_variable_db_detach(default_var_db);
33 }
34 default_var_db = lp_variable_db_new();
35 }
36
Variable_get_default_db(void)37 lp_variable_db_t* Variable_get_default_db(void) {
38 if (!default_var_db) {
39 Variable_init_default_db();
40 }
41 return default_var_db;
42 }
43
44 static PyObject*
45 Variable_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
46
47 static int
48 Variable_init(Variable* self, PyObject* args);
49
50 static void
51 Variable_dealloc(Variable* self);
52
53 static PyObject*
54 Variable_str(PyObject* self);
55
56 static PyObject*
57 Variable_repr(PyObject* self);
58
59 static long
60 Variable_hash(PyObject* self);
61
62 static PyObject *
63 Variable_richcompare(PyObject *self, PyObject *other, int op);
64
65 PyMethodDef Variable_methods[] = {
66 {NULL} /* Sentinel */
67 };
68
69 static PyObject*
70 Variable_add(PyObject* self, PyObject* args);
71
72 static PyObject*
73 Variable_neg(PyObject* self);
74
75 static PyObject*
76 Variable_sub(PyObject* self, PyObject* args);
77
78 static PyObject*
79 Variable_mul(PyObject* self, PyObject* args);
80
81 static PyObject*
82 Variable_pow(PyObject* self, PyObject* args);
83
84 PyNumberMethods Variable_NumberMethods = {
85 Variable_add, // binaryfunc nb_add;
86 Variable_sub, // binaryfunc nb_subtract;
87 Variable_mul, // binaryfunc nb_multiply;
88 0, // binaryfunc nb_remainder;
89 0, // binaryfunc nb_divmod;
90 (ternaryfunc)Variable_pow, // ternaryfunc nb_power;
91 Variable_neg, // unaryfunc nb_negative;
92 0, // unaryfunc nb_positive;
93 0, // unaryfunc nb_absolute;
94 0, // inquiry nb_bool;
95 0, // unaryfunc nb_invert;
96 0, // binaryfunc nb_lshift;
97 0, // binaryfunc nb_rshift;
98 0, // binaryfunc nb_and;
99 0, // binaryfunc nb_xor;
100 0, // binaryfunc nb_or;
101 0, // unaryfunc nb_int;
102 0, // void *nb_reserved;
103 0, // unaryfunc nb_float;
104 0, // binaryfunc nb_inplace_add;
105 0, // binaryfunc nb_inplace_subtract;
106 0, // binaryfunc nb_inplace_multiply;
107 0, // binaryfunc nb_inplace_remainder;
108 0, // ternaryfunc nb_inplace_power;
109 0, // binaryfunc nb_inplace_lshift;
110 0, // binaryfunc nb_inplace_rshift;
111 0, // binaryfunc nb_inplace_and;
112 0, // binaryfunc nb_inplace_xor;
113 0, // binaryfunc nb_inplace_or;
114 0, // binaryfunc nb_floor_divide;
115 0, // binaryfunc nb_true_divide;
116 0, // binaryfunc nb_inplace_floor_divide;
117 0, // binaryfunc nb_inplace_true_divide;
118 0, // unaryfunc nb_index;
119 0, // binaryfunc nb_matrix_multiply;
120 0, // binaryfunc nb_inplace_matrix_multiply;
121 };
122
123 PyTypeObject VariableType = {
124 {PyObject_HEAD_INIT(NULL)}, // PyObject_VAR_HEAD
125 "polypy.Variable", // const char *tp_name;
126 sizeof(Variable), // Py_ssize_t tp_basicsize;
127 0, // Py_ssize_t tp_itemsize;
128 (destructor)Variable_dealloc, // destructor tp_dealloc;
129 0, // printfunc tp_print;
130 0, // getattrfunc tp_getattr;
131 0, // setattrfunc tp_setattr;
132 0, // PyAsyncMethods *tp_as_async;
133 Variable_repr, // reprfunc tp_repr;
134 &Variable_NumberMethods, // PyNumberMethods *tp_as_number;
135 0, // PySequenceMethods *tp_as_sequence;
136 0, // PyMappingMethods *tp_as_mapping;
137 Variable_hash, // hashfunc tp_hash;
138 0, // ternaryfunc tp_call;
139 Variable_str, // reprfunc tp_str;
140 0, // getattrofunc tp_getattro;
141 0, // setattrofunc tp_setattro;
142 0, // PyBufferProcs *tp_as_buffer;
143 Py_TPFLAGS_DEFAULT, // unsigned long tp_flags;
144 "Variable objects", // const char *tp_doc;
145 0, // traverseproc tp_traverse;
146 0, // inquiry tp_clear;
147 Variable_richcompare, // richcmpfunc tp_richcompare;
148 0, // Py_ssize_t tp_weaklistoffset;
149 0, // getiterfunc tp_iter;
150 0, // iternextfunc tp_iternext;
151 Variable_methods, // struct PyMethodDef *tp_methods;
152 0, // istruct PyMemberDef *tp_members;
153 0, // istruct PyGetSetDef *tp_getset;
154 0, // istruct _typeobject *tp_base;
155 0, // iPyObject *tp_dict;
156 0, // idescrgetfunc tp_descr_get;
157 0, // idescrsetfunc tp_descr_set;
158 0, // iPy_ssize_t tp_dictoffset;
159 (initproc)Variable_init, // initproc tp_init;
160 0, // allocfunc tp_alloc;
161 Variable_new, // newfunc tp_new;
162 0, // freefunc tp_free;
163 0, // inquiry tp_is_gc;
164 0, // PyObject *tp_bases;
165 0, // PyObject *tp_mro;
166 0, // PyObject *tp_cache;
167 0, // PyObject *tp_subclasses;
168 0, // PyObject *tp_weaklist;
169 0, // destructor tp_del;
170 0, // unsigned int tp_version_tag;
171 0, // destructor tp_finalize;
172 };
173
174 PyObject*
PyVariable_create(lp_variable_t x)175 PyVariable_create(lp_variable_t x) {
176 Variable *self;
177 self = (Variable*)VariableType.tp_alloc(&VariableType, 0);
178 if (self != NULL) {
179 self->x = x;
180 }
181 return (PyObject *)self;
182 }
183
184 static PyObject*
Variable_new(PyTypeObject * type,PyObject * args,PyObject * kwds)185 Variable_new(PyTypeObject *type, PyObject *args, PyObject *kwds) {
186 return PyVariable_create(0);
187 }
188
189 static int
Variable_init(Variable * self,PyObject * args)190 Variable_init(Variable* self, PyObject* args)
191 {
192 if (PyTuple_Check(args) && PyTuple_Size(args) == 1) {
193 PyObject* obj = PyTuple_GetItem(args, 0);
194 if (PyUnicode_Check(obj) || PyBytes_Check(obj)) {
195 const char* c_str = pythonObject2CharStar(obj);
196 lp_variable_t x = lp_variable_db_new_variable(Variable_get_default_db(), c_str);
197 self->x = x;
198 } else {
199 return -1;
200 }
201 } else {
202 return -1;
203 }
204 return 0;
205 }
206
207 static void
Variable_dealloc(Variable * self)208 Variable_dealloc(Variable* self)
209 {
210 ((PyObject*)self)->ob_type->tp_free((PyObject*)self);
211 }
212
Variable_str(PyObject * self)213 static PyObject* Variable_str(PyObject* self) {
214 Variable* x = (Variable*) self;
215 const char* x_str = lp_variable_db_get_name(Variable_get_default_db(), x->x);
216 PyObject* str = PyUnicode_FromString(x_str);
217 return str;
218 }
219
Variable_repr(PyObject * self)220 static PyObject* Variable_repr(PyObject* self) {
221 Variable* x = (Variable*) self;
222 const char* x_str = lp_variable_db_get_name(Variable_get_default_db(), x->x);
223 char* x_repr = malloc(strlen(x_str) + strlen(VariableType.tp_name) + 5);
224 sprintf(x_repr, "%s('%s')", VariableType.tp_name, x_str);
225 PyObject* str = PyUnicode_FromString(x_repr);
226 free(x_repr);
227 return str;
228 }
229
Variable_hash(PyObject * self)230 static long Variable_hash(PyObject* self) {
231 Variable* x = (Variable*) self;
232 return x->x;
233 }
234
235 static
PyLong_Or_Int_to_polynomial(PyObject * number)236 lp_polynomial_t* PyLong_Or_Int_to_polynomial(PyObject* number) {
237 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
238 lp_integer_t c;
239 PyLong_or_Int_to_integer(number, 0, &c);
240 lp_polynomial_t* p_c = lp_polynomial_alloc();
241 lp_polynomial_construct_simple(p_c, ctx, &c, 0, 0);
242 lp_integer_destruct(&c);
243 return p_c;
244 }
245
246 static
Variable_to_polynomial(PyObject * var)247 lp_polynomial_t* Variable_to_polynomial(PyObject* var) {
248 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
249 Variable* x = (Variable*) var;
250 lp_integer_t one;
251 lp_integer_construct_from_int(lp_Z, &one, 1);
252 lp_polynomial_t* p_x = lp_polynomial_alloc();
253 lp_polynomial_construct_simple(p_x, ctx, &one, x->x, 1);
254 lp_integer_destruct(&one);
255 return p_x;
256 }
257
258 static PyObject*
Variable_add_number(PyObject * self,PyObject * other)259 Variable_add_number(PyObject* self, PyObject* other) {
260
261 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
262
263 // The x polynomial
264 lp_polynomial_t* p_x = Variable_to_polynomial(self);
265 // The c polynomial
266 lp_polynomial_t* p_c = PyLong_Or_Int_to_polynomial(other);
267
268 // x + c polynomial
269 lp_polynomial_t* p_sum = lp_polynomial_new(ctx);
270 lp_polynomial_add(p_sum, p_x, p_c);
271
272 // Remove temporaries
273 lp_polynomial_destruct(p_x);
274 lp_polynomial_destruct(p_c);
275 free(p_x);
276 free(p_c);
277
278 return Polynomial_create(p_sum);
279 }
280
281 static PyObject*
Variable_add_Variable(PyObject * self,PyObject * other)282 Variable_add_Variable(PyObject* self, PyObject* other) {
283
284 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
285
286 // The x polynomial
287 lp_polynomial_t* p_x = Variable_to_polynomial(self);
288 // The c polynomial
289 lp_polynomial_t* p_y = Variable_to_polynomial(other);
290
291 // x + c polynomial
292 lp_polynomial_t* p_sum = lp_polynomial_new(ctx);
293 lp_polynomial_add(p_sum, p_x, p_y);
294
295 // Remove temporaries
296 lp_polynomial_destruct(p_x);
297 lp_polynomial_destruct(p_y);
298 free(p_x);
299 free(p_y);
300
301 return Polynomial_create(p_sum);
302 }
303
304 static PyObject*
Variable_add(PyObject * self,PyObject * other)305 Variable_add(PyObject* self, PyObject* other) {
306 // Integer addition
307 if (PyLong_or_Int_Check(other)) {
308 return Variable_add_number(self, other);
309 } else if (PyLong_or_Int_Check(self)) {
310 return Variable_add_number(other, self);
311 } else if (PyVariable_CHECK(other)) {
312 return Variable_add_Variable(self, other);
313 } else {
314 Py_INCREF(Py_NotImplemented);
315 return Py_NotImplemented;
316 }
317 }
318
319 static PyObject*
Variable_neg(PyObject * self)320 Variable_neg(PyObject* self) {
321
322 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
323
324 // The x polynomial
325 lp_polynomial_t* p_x = Variable_to_polynomial(self);
326
327 // -x polynomial
328 lp_polynomial_t* p_neg = lp_polynomial_new(ctx);
329 lp_polynomial_neg(p_neg, p_x);
330
331 // Remove temporaries
332 lp_polynomial_destruct(p_x);
333 free(p_x);
334
335 return Polynomial_create(p_neg);
336 }
337
338 static PyObject*
Variable_sub_number(PyObject * self,PyObject * other)339 Variable_sub_number(PyObject* self, PyObject* other) {
340
341 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
342
343 // The x polynomial
344 lp_polynomial_t* p_x = Variable_to_polynomial(self);
345 // The c polynomial
346 lp_polynomial_t* p_c = PyLong_Or_Int_to_polynomial(other);
347
348 // x + c polynomial
349 lp_polynomial_t* p_sub = lp_polynomial_new(ctx);
350 lp_polynomial_sub(p_sub, p_x, p_c);
351
352 // Remove temporaries
353 lp_polynomial_destruct(p_x);
354 lp_polynomial_destruct(p_c);
355 free(p_x);
356 free(p_c);
357
358 return Polynomial_create(p_sub);
359 }
360
361 static PyObject*
Variable_sub_Variable(PyObject * self,PyObject * other)362 Variable_sub_Variable(PyObject* self, PyObject* other) {
363
364 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
365
366 // The x polynomial
367 lp_polynomial_t* p_x = Variable_to_polynomial(self);
368 // The c polynomial
369 lp_polynomial_t* p_y = Variable_to_polynomial(other);
370
371 // x - y polynomial
372 lp_polynomial_t* p_sub = lp_polynomial_new(ctx);
373 lp_polynomial_sub(p_sub, p_x, p_y);
374
375 // Remove temporaries
376 lp_polynomial_destruct(p_x);
377 lp_polynomial_destruct(p_y);
378 free(p_x);
379 free(p_y);
380
381 return Polynomial_create(p_sub);
382 }
383
384 static PyObject*
Variable_sub(PyObject * self,PyObject * other)385 Variable_sub(PyObject* self, PyObject* other) {
386 // Integer addition
387 if (PyLong_or_Int_Check(other)) {
388 return Variable_sub_number(self, other);
389 } else if (PyLong_or_Int_Check(self)) {
390 Polynomial* result = (Polynomial*) Variable_sub_number(other, self);
391 lp_polynomial_neg(result->p, result->p);
392 return (PyObject*) result;
393 } else if (PyVariable_CHECK(other)) {
394 return Variable_sub_Variable(self, other);
395 } else {
396 Py_INCREF(Py_NotImplemented);
397 return Py_NotImplemented;
398 }
399 }
400
401 static PyObject*
Variable_mul_number(PyObject * self,PyObject * other)402 Variable_mul_number(PyObject* self, PyObject* other) {
403
404 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
405
406 // The x polynomial
407 lp_polynomial_t* p_x = Variable_to_polynomial(self);
408 // The c polynomial
409 lp_polynomial_t* p_c = PyLong_Or_Int_to_polynomial(other);
410
411 // x + c polynomial
412 lp_polynomial_t* p_mul = lp_polynomial_new(ctx);
413 lp_polynomial_mul(p_mul, p_x, p_c);
414
415 // Remove temporaries
416 lp_polynomial_destruct(p_x);
417 lp_polynomial_destruct(p_c);
418 free(p_x);
419 free(p_c);
420
421 return Polynomial_create(p_mul);
422 }
423
424 static PyObject*
Variable_mul_Variable(PyObject * self,PyObject * other)425 Variable_mul_Variable(PyObject* self, PyObject* other) {
426
427 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
428
429 // The x polynomial
430 lp_polynomial_t* p_x = Variable_to_polynomial(self);
431 // The c polynomial
432 lp_polynomial_t* p_y = Variable_to_polynomial(other);
433
434 // x + c polynomial
435 lp_polynomial_t* p_mul = lp_polynomial_new(ctx);
436 lp_polynomial_mul(p_mul, p_x, p_y);
437
438 // Remove temporaries
439 lp_polynomial_destruct(p_x);
440 lp_polynomial_destruct(p_y);
441 free(p_x);
442 free(p_y);
443
444 return Polynomial_create(p_mul);
445 }
446
447 static PyObject*
Variable_mul(PyObject * self,PyObject * other)448 Variable_mul(PyObject* self, PyObject* other) {
449 // Integer addition
450 if (PyLong_or_Int_Check(other)) {
451 return Variable_mul_number(self, other);
452 } else if (PyLong_or_Int_Check(self)) {
453 return Variable_mul_number(other, self);
454 } else if (PyVariable_CHECK(other)) {
455 return Variable_mul_Variable(other, self);
456 } else {
457 Py_INCREF(Py_NotImplemented);
458 return Py_NotImplemented;
459 }
460 }
461
462 static PyObject*
Variable_pow(PyObject * self,PyObject * other)463 Variable_pow(PyObject* self, PyObject* other) {
464 // Check arguments
465 if (!PyVariable_CHECK(self) || !PyLong_Check(other)) {
466 Py_INCREF(Py_NotImplemented);
467 return Py_NotImplemented;
468 } else {
469 long n = PyLong_AsLong(other);
470 if (n < 0) {
471 Py_INCREF(Py_NotImplemented);
472 return Py_NotImplemented;
473 } else {
474 const lp_polynomial_context_t* ctx = Polynomial_get_default_context();
475 Variable* var = (Variable*) self;
476 lp_integer_t one;
477 lp_integer_construct_from_int(lp_Z, &one, 1);
478 lp_polynomial_t* pow_x = lp_polynomial_alloc();
479 lp_polynomial_construct_simple(pow_x, ctx, &one, var->x, n);
480 lp_integer_destruct(&one);
481 return Polynomial_create(pow_x);
482 }
483 }
484 }
485
486 static PyObject *
Variable_richcompare(PyObject * self,PyObject * other,int op)487 Variable_richcompare(PyObject *self, PyObject *other, int op){
488 PyObject *result = Py_NotImplemented;
489
490 if (!PyVariable_CHECK(other)) {
491 if(op == Py_EQ){ return Py_False; }
492 if(op == Py_NE){ return Py_True; }
493 } else {
494 Variable* x = (Variable*) self;
495 Variable* y = (Variable*) other;
496
497 switch (op) {
498 case Py_LT:
499 result = (x->x < y->x ? Py_True : Py_False);
500 break;
501 case Py_LE:
502 result = (x->x <= y->x ? Py_True : Py_False);
503 break;
504 case Py_EQ:
505 result = (x->x == y->x ? Py_True : Py_False);
506 break;
507 case Py_NE:
508 result = (x->x != y->x ? Py_True : Py_False);
509 break;
510 case Py_GT:
511 result = (x->x > y->x ? Py_True : Py_False);
512 break;
513 case Py_GE:
514 result = (x->x >= y->x ? Py_True : Py_False);
515 break;
516 }
517 }
518 return result;
519 }
520
521