Better implementation of NSAD'10 example
[linpy.git] / pypol / linexprs.py
1 import ast
2 import functools
3 import numbers
4 import re
5
6 from collections import OrderedDict, defaultdict
7 from fractions import Fraction, gcd
8
9
10 __all__ = [
11 'Expression',
12 'Symbol', 'symbols', 'Dummy',
13 'Rational',
14 ]
15
16
17 def _polymorphic(func):
18 @functools.wraps(func)
19 def wrapper(left, right):
20 if isinstance(right, Expression):
21 return func(left, right)
22 elif isinstance(right, numbers.Rational):
23 right = Rational(right)
24 return func(left, right)
25 return NotImplemented
26 return wrapper
27
28
29 class Expression:
30 """
31 This class implements linear expressions.
32 """
33
34 __slots__ = (
35 '_coefficients',
36 '_constant',
37 '_symbols',
38 '_dimension',
39 )
40
41 def __new__(cls, coefficients=None, constant=0):
42 if isinstance(coefficients, str):
43 if constant:
44 raise TypeError('too many arguments')
45 return Expression.fromstring(coefficients)
46 if coefficients is None:
47 return Rational(constant)
48 if isinstance(coefficients, dict):
49 coefficients = coefficients.items()
50 for symbol, coefficient in coefficients:
51 if not isinstance(symbol, Symbol):
52 raise TypeError('symbols must be Symbol instances')
53 coefficients = [(symbol, coefficient)
54 for symbol, coefficient in coefficients if coefficient != 0]
55 if len(coefficients) == 0:
56 return Rational(constant)
57 if len(coefficients) == 1 and constant == 0:
58 symbol, coefficient = coefficients[0]
59 if coefficient == 1:
60 return symbol
61 self = object().__new__(cls)
62 self._coefficients = OrderedDict()
63 for symbol, coefficient in sorted(coefficients,
64 key=lambda item: item[0].sortkey()):
65 if isinstance(coefficient, Rational):
66 coefficient = coefficient.constant
67 if not isinstance(coefficient, numbers.Rational):
68 raise TypeError('coefficients must be rational numbers '
69 'or Rational instances')
70 self._coefficients[symbol] = coefficient
71 if isinstance(constant, Rational):
72 constant = constant.constant
73 if not isinstance(constant, numbers.Rational):
74 raise TypeError('constant must be a rational number '
75 'or a Rational instance')
76 self._constant = constant
77 self._symbols = tuple(self._coefficients)
78 self._dimension = len(self._symbols)
79 return self
80
81 def coefficient(self, symbol):
82 if not isinstance(symbol, Symbol):
83 raise TypeError('symbol must be a Symbol instance')
84 try:
85 return self._coefficients[symbol]
86 except KeyError:
87 return 0
88
89 __getitem__ = coefficient
90
91 def coefficients(self):
92 yield from self._coefficients.items()
93
94 @property
95 def constant(self):
96 return self._constant
97
98 @property
99 def symbols(self):
100 return self._symbols
101
102 @property
103 def dimension(self):
104 return self._dimension
105
106 def __hash__(self):
107 return hash((tuple(self._coefficients.items()), self._constant))
108
109 def isconstant(self):
110 return False
111
112 def issymbol(self):
113 return False
114
115 def values(self):
116 yield from self._coefficients.values()
117 yield self.constant
118
119 def __bool__(self):
120 return True
121
122 def __pos__(self):
123 return self
124
125 def __neg__(self):
126 return self * -1
127
128 @_polymorphic
129 def __add__(self, other):
130 coefficients = defaultdict(Rational, self.coefficients())
131 for symbol, coefficient in other.coefficients():
132 coefficients[symbol] += coefficient
133 constant = self.constant + other.constant
134 return Expression(coefficients, constant)
135
136 __radd__ = __add__
137
138 @_polymorphic
139 def __sub__(self, other):
140 coefficients = defaultdict(Rational, self.coefficients())
141 for symbol, coefficient in other.coefficients():
142 coefficients[symbol] -= coefficient
143 constant = self.constant - other.constant
144 return Expression(coefficients, constant)
145
146 def __rsub__(self, other):
147 return -(self - other)
148
149 @_polymorphic
150 def __mul__(self, other):
151 if other.isconstant():
152 coefficients = dict(self.coefficients())
153 for symbol in coefficients:
154 coefficients[symbol] *= other.constant
155 constant = self.constant * other.constant
156 return Expression(coefficients, constant)
157 if isinstance(other, Expression) and not self.isconstant():
158 raise ValueError('non-linear expression: '
159 '{} * {}'.format(self._parenstr(), other._parenstr()))
160 return NotImplemented
161
162 __rmul__ = __mul__
163
164 @_polymorphic
165 def __truediv__(self, other):
166 if other.isconstant():
167 coefficients = dict(self.coefficients())
168 for symbol in coefficients:
169 coefficients[symbol] = Rational(coefficients[symbol], other.constant)
170 constant = Rational(self.constant, other.constant)
171 return Expression(coefficients, constant)
172 if isinstance(other, Expression):
173 raise ValueError('non-linear expression: '
174 '{} / {}'.format(self._parenstr(), other._parenstr()))
175 return NotImplemented
176
177 def __rtruediv__(self, other):
178 if isinstance(other, self):
179 if self.isconstant():
180 return Rational(other, self.constant)
181 else:
182 raise ValueError('non-linear expression: '
183 '{} / {}'.format(other._parenstr(), self._parenstr()))
184 return NotImplemented
185
186 @_polymorphic
187 def __eq__(self, other):
188 # "normal" equality
189 # see http://docs.sympy.org/dev/tutorial/gotchas.html#equals-signs
190 return isinstance(other, Expression) and \
191 self._coefficients == other._coefficients and \
192 self.constant == other.constant
193
194 @_polymorphic
195 def __le__(self, other):
196 from .polyhedra import Le
197 return Le(self, other)
198
199 @_polymorphic
200 def __lt__(self, other):
201 from .polyhedra import Lt
202 return Lt(self, other)
203
204 @_polymorphic
205 def __ge__(self, other):
206 from .polyhedra import Ge
207 return Ge(self, other)
208
209 @_polymorphic
210 def __gt__(self, other):
211 from .polyhedra import Gt
212 return Gt(self, other)
213
214 def scaleint(self):
215 lcm = functools.reduce(lambda a, b: a*b // gcd(a, b),
216 [value.denominator for value in self.values()])
217 return self * lcm
218
219 def subs(self, symbol, expression=None):
220 if expression is None:
221 if isinstance(symbol, dict):
222 symbol = symbol.items()
223 substitutions = symbol
224 else:
225 substitutions = [(symbol, expression)]
226 result = self
227 for symbol, expression in substitutions:
228 coefficients = [(othersymbol, coefficient)
229 for othersymbol, coefficient in result.coefficients()
230 if othersymbol != symbol]
231 coefficient = result.coefficient(symbol)
232 constant = result.constant
233 result = Expression(coefficients, constant) + coefficient*expression
234 return result
235
236 @classmethod
237 def _fromast(cls, node):
238 if isinstance(node, ast.Module) and len(node.body) == 1:
239 return cls._fromast(node.body[0])
240 elif isinstance(node, ast.Expr):
241 return cls._fromast(node.value)
242 elif isinstance(node, ast.Name):
243 return Symbol(node.id)
244 elif isinstance(node, ast.Num):
245 return Rational(node.n)
246 elif isinstance(node, ast.UnaryOp) and isinstance(node.op, ast.USub):
247 return -cls._fromast(node.operand)
248 elif isinstance(node, ast.BinOp):
249 left = cls._fromast(node.left)
250 right = cls._fromast(node.right)
251 if isinstance(node.op, ast.Add):
252 return left + right
253 elif isinstance(node.op, ast.Sub):
254 return left - right
255 elif isinstance(node.op, ast.Mult):
256 return left * right
257 elif isinstance(node.op, ast.Div):
258 return left / right
259 raise SyntaxError('invalid syntax')
260
261 _RE_NUM_VAR = re.compile(r'(\d+|\))\s*([^\W\d_]\w*|\()')
262
263 @classmethod
264 def fromstring(cls, string):
265 # add implicit multiplication operators, e.g. '5x' -> '5*x'
266 string = Expression._RE_NUM_VAR.sub(r'\1*\2', string)
267 tree = ast.parse(string, 'eval')
268 return cls._fromast(tree)
269
270 def __repr__(self):
271 string = ''
272 i = 0
273 for symbol in self.symbols:
274 coefficient = self.coefficient(symbol)
275 if coefficient == 1:
276 if i == 0:
277 string += symbol.name
278 else:
279 string += ' + {}'.format(symbol)
280 elif coefficient == -1:
281 if i == 0:
282 string += '-{}'.format(symbol)
283 else:
284 string += ' - {}'.format(symbol)
285 else:
286 if i == 0:
287 string += '{}*{}'.format(coefficient, symbol)
288 elif coefficient > 0:
289 string += ' + {}*{}'.format(coefficient, symbol)
290 else:
291 assert coefficient < 0
292 coefficient *= -1
293 string += ' - {}*{}'.format(coefficient, symbol)
294 i += 1
295 constant = self.constant
296 if constant != 0 and i == 0:
297 string += '{}'.format(constant)
298 elif constant > 0:
299 string += ' + {}'.format(constant)
300 elif constant < 0:
301 constant *= -1
302 string += ' - {}'.format(constant)
303 if string == '':
304 string = '0'
305 return string
306
307 def _parenstr(self, always=False):
308 string = str(self)
309 if not always and (self.isconstant() or self.issymbol()):
310 return string
311 else:
312 return '({})'.format(string)
313
314 @classmethod
315 def fromsympy(cls, expr):
316 import sympy
317 coefficients = []
318 constant = 0
319 for symbol, coefficient in expr.as_coefficients_dict().items():
320 coefficient = Fraction(coefficient.p, coefficient.q)
321 if symbol == sympy.S.One:
322 constant = coefficient
323 elif isinstance(symbol, sympy.Symbol):
324 symbol = Symbol(symbol.name)
325 coefficients.append((symbol, coefficient))
326 else:
327 raise ValueError('non-linear expression: {!r}'.format(expr))
328 return Expression(coefficients, constant)
329
330 def tosympy(self):
331 import sympy
332 expr = 0
333 for symbol, coefficient in self.coefficients():
334 term = coefficient * sympy.Symbol(symbol.name)
335 expr += term
336 expr += self.constant
337 return expr
338
339
340 class Symbol(Expression):
341
342 __slots__ = (
343 '_name',
344 )
345
346 def __new__(cls, name):
347 if not isinstance(name, str):
348 raise TypeError('name must be a string')
349 self = object().__new__(cls)
350 self._name = name.strip()
351 return self
352
353 @property
354 def name(self):
355 return self._name
356
357 def __hash__(self):
358 return hash(self.sortkey())
359
360 def coefficient(self, symbol):
361 if not isinstance(symbol, Symbol):
362 raise TypeError('symbol must be a Symbol instance')
363 if symbol == self:
364 return 1
365 else:
366 return 0
367
368 def coefficients(self):
369 yield self, 1
370
371 @property
372 def constant(self):
373 return 0
374
375 @property
376 def symbols(self):
377 return self,
378
379 @property
380 def dimension(self):
381 return 1
382
383 def sortkey(self):
384 return self.name,
385
386 def issymbol(self):
387 return True
388
389 def values(self):
390 yield 1
391
392 def __eq__(self, other):
393 return not isinstance(other, Dummy) and isinstance(other, Symbol) \
394 and self.name == other.name
395
396 def asdummy(self):
397 return Dummy(self.name)
398
399 @classmethod
400 def _fromast(cls, node):
401 if isinstance(node, ast.Module) and len(node.body) == 1:
402 return cls._fromast(node.body[0])
403 elif isinstance(node, ast.Expr):
404 return cls._fromast(node.value)
405 elif isinstance(node, ast.Name):
406 return Symbol(node.id)
407 raise SyntaxError('invalid syntax')
408
409 @classmethod
410 def fromsympy(cls, expr):
411 import sympy
412 if isinstance(expr, sympy.Symbol):
413 return Symbol(expr.name)
414 else:
415 raise TypeError('expr must be a sympy.Symbol instance')
416
417
418 def symbols(names):
419 if isinstance(names, str):
420 names = names.replace(',', ' ').split()
421 return tuple(Symbol(name) for name in names)
422
423
424 class Dummy(Symbol):
425
426 __slots__ = (
427 '_name',
428 '_index',
429 )
430
431 _count = 0
432
433 def __new__(cls, name=None):
434 if name is None:
435 name = 'Dummy_{}'.format(Dummy._count)
436 self = object().__new__(cls)
437 self._name = name.strip()
438 self._index = Dummy._count
439 Dummy._count += 1
440 return self
441
442 def __hash__(self):
443 return hash(self.sortkey())
444
445 def sortkey(self):
446 return self._name, self._index
447
448 def __eq__(self, other):
449 return isinstance(other, Dummy) and self._index == other._index
450
451
452 class Rational(Expression):
453
454 __slots__ = (
455 '_constant',
456 )
457
458 def __new__(cls, numerator=0, denominator=None):
459 self = object().__new__(cls)
460 if denominator is None and isinstance(numerator, Rational):
461 self._constant = numerator.constant
462 else:
463 self._constant = Fraction(numerator, denominator)
464 return self
465
466 def __hash__(self):
467 return hash(self.constant)
468
469 def coefficient(self, symbol):
470 if not isinstance(symbol, Symbol):
471 raise TypeError('symbol must be a Symbol instance')
472 return 0
473
474 def coefficients(self):
475 yield from ()
476
477 @property
478 def symbols(self):
479 return ()
480
481 @property
482 def dimension(self):
483 return 0
484
485 def isconstant(self):
486 return True
487
488 def values(self):
489 yield self._constant
490
491 @_polymorphic
492 def __eq__(self, other):
493 return isinstance(other, Rational) and self.constant == other.constant
494
495 def __bool__(self):
496 return self.constant != 0
497
498 @classmethod
499 def fromstring(cls, string):
500 if not isinstance(string, str):
501 raise TypeError('string must be a string instance')
502 return Rational(Fraction(string))
503
504 @classmethod
505 def fromsympy(cls, expr):
506 import sympy
507 if isinstance(expr, sympy.Rational):
508 return Rational(expr.p, expr.q)
509 elif isinstance(expr, numbers.Rational):
510 return Rational(expr)
511 else:
512 raise TypeError('expr must be a sympy.Rational instance')