X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/b3af8a414781471620fb930f819f0c63bfab87f6..37b02d24c845fa3c75c48a99e5e658d772b72289:/pypol/linear.py?ds=inline diff --git a/pypol/linear.py b/pypol/linear.py index 4f3aeef..bd7037b 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -9,8 +9,7 @@ from .isl import libisl __all__ = [ - 'Expression', - 'constant', 'symbol', 'symbols', + 'Expression', 'Constant', 'Symbol', 'symbols', 'eq', 'le', 'lt', 'ge', 'gt', 'Polyhedron', 'empty', 'universe' @@ -23,7 +22,7 @@ def _polymorphic_method(func): if isinstance(b, Expression): return func(a, b) if isinstance(b, numbers.Rational): - b = constant(b) + b = Constant(b) return func(a, b) return NotImplemented return wrapper @@ -34,7 +33,7 @@ def _polymorphic_operator(func): @functools.wraps(func) def wrapper(a, b): if isinstance(a, numbers.Rational): - a = constant(a) + a = Constant(a) return func(a, b) elif isinstance(a, Expression): return func(a, b) @@ -55,27 +54,43 @@ class Expression: if constant: raise TypeError('too many arguments') return cls.fromstring(coefficients) - self = super().__new__(cls) - self._coefficients = {} if isinstance(coefficients, dict): coefficients = coefficients.items() - if coefficients is not None: - for symbol, coefficient in coefficients: - if isinstance(symbol, Expression) and symbol.issymbol(): - symbol = str(symbol) - elif not isinstance(symbol, str): - raise TypeError('symbols must be strings') - if not isinstance(coefficient, numbers.Rational): - raise TypeError('coefficients must be rational numbers') - if coefficient != 0: - self._coefficients[symbol] = coefficient + if coefficients is None: + return Constant(constant) + coefficients = [(symbol, coefficient) + for symbol, coefficient in coefficients if coefficient != 0] + if len(coefficients) == 0: + return Constant(constant) + elif len(coefficients) == 1: + symbol, coefficient = coefficients[0] + if coefficient == 1: + return Symbol(symbol) + self = object().__new__(cls) + self._coefficients = {} + for symbol, coefficient in coefficients: + if isinstance(symbol, Symbol): + symbol = str(symbol) + elif not isinstance(symbol, str): + raise TypeError('symbols must be strings or Symbol instances') + if isinstance(coefficient, Constant): + coefficient = coefficient.constant + if not isinstance(coefficient, numbers.Rational): + raise TypeError('coefficients must be rational numbers or Constant instances') + self._coefficients[symbol] = coefficient + if isinstance(constant, Constant): + constant = constant.constant if not isinstance(constant, numbers.Rational): - raise TypeError('constant must be a rational number') + raise TypeError('constant must be a rational number or a Constant instance') self._constant = constant self._symbols = tuple(sorted(self._coefficients)) self._dimension = len(self._symbols) return self + @classmethod + def fromstring(cls, string): + raise NotImplementedError + @property def symbols(self): return self._symbols @@ -85,10 +100,10 @@ class Expression: return self._dimension def coefficient(self, symbol): - if isinstance(symbol, Expression) and symbol.issymbol(): + if isinstance(symbol, Symbol): symbol = str(symbol) elif not isinstance(symbol, str): - raise TypeError('symbol must be a string') + raise TypeError('symbol must be a string or a Symbol instance') try: return self._coefficients[symbol] except KeyError: @@ -105,30 +120,22 @@ class Expression: return self._constant def isconstant(self): - return len(self._coefficients) == 0 + return False def values(self): for symbol in self.symbols: yield self.coefficient(symbol) yield self.constant - def values_int(self): - for symbol in self.symbols: - return self.coefficient(symbol) - return int(self.constant) - @property def symbol(self): - if not self.issymbol(): - raise ValueError('not a symbol: {}'.format(self)) - for symbol in self.symbols: - return symbol + raise ValueError('not a symbol: {}'.format(self)) def issymbol(self): - return len(self._coefficients) == 1 and self._constant == 0 + return False def __bool__(self): - return (not self.isconstant()) or bool(self.constant) + True def __pos__(self): return self @@ -139,7 +146,7 @@ class Expression: @_polymorphic_method def __add__(self, other): coefficients = dict(self.coefficients()) - for symbol, coefficient in other.coefficients: + for symbol, coefficient in other.coefficients(): if symbol in coefficients: coefficients[symbol] += coefficient else: @@ -152,7 +159,7 @@ class Expression: @_polymorphic_method def __sub__(self, other): coefficients = dict(self.coefficients()) - for symbol, coefficient in other.coefficients: + for symbol, coefficient in other.coefficients(): if symbol in coefficients: coefficients[symbol] -= coefficient else: @@ -205,8 +212,8 @@ class Expression: def __str__(self): string = '' i = 0 - for symbol in symbols: - coefficient = self[symbol] + for symbol in self.symbols: + coefficient = self.coefficient(symbol) if coefficient == 1: if i == 0: string += symbol @@ -255,10 +262,6 @@ class Expression: string += '}}, {!r})'.format(self.constant) return string - @classmethod - def fromstring(cls, string): - raise NotImplementedError - @_polymorphic_method def __eq__(self, other): # "normal" equality @@ -270,42 +273,84 @@ class Expression: def __hash__(self): return hash((self._coefficients, self._constant)) - def _canonify(self): + def _toint(self): lcm = functools.reduce(lambda a, b: a*b // gcd(a, b), [value.denominator for value in self.values()]) return self * lcm @_polymorphic_method def _eq(self, other): - return Polyhedron(equalities=[(self - other)._canonify()]) + return Polyhedron(equalities=[(self - other)._toint()]) @_polymorphic_method def __le__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify()]) + return Polyhedron(inequalities=[(other - self)._toint()]) @_polymorphic_method def __lt__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify() - 1]) + return Polyhedron(inequalities=[(other - self)._toint() - 1]) @_polymorphic_method def __ge__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify()]) + return Polyhedron(inequalities=[(self - other)._toint()]) @_polymorphic_method def __gt__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify() - 1]) + return Polyhedron(inequalities=[(self - other)._toint() - 1]) + +class Constant(Expression): + + def __new__(cls, numerator=0, denominator=None): + self = object().__new__(cls) + if denominator is None: + if isinstance(numerator, numbers.Rational): + self._constant = numerator + elif isinstance(numerator, Constant): + self._constant = numerator.constant + else: + raise TypeError('constant must be a rational number or a Constant instance') + else: + self._constant = Fraction(numerator, denominator) + self._coefficients = {} + self._symbols = () + self._dimension = 0 + return self -def constant(numerator=0, denominator=None): - if denominator is None and isinstance(numerator, numbers.Rational): - return Expression(constant=numerator) - else: - return Expression(constant=Fraction(numerator, denominator)) + def isconstant(self): + return True -def symbol(name): - if not isinstance(name, str): - raise TypeError('name must be a string') - return Expression(coefficients={name: 1}) + def __bool__(self): + return bool(self.constant) + + def __repr__(self): + return '{}({!r})'.format(self.__class__.__name__, self._constant) + + +class Symbol(Expression): + + def __new__(cls, name): + if isinstance(name, Symbol): + name = name.symbol + elif not isinstance(name, str): + raise TypeError('name must be a string or a Symbol instance') + self = object().__new__(cls) + self._coefficients = {name: 1} + self._constant = 0 + self._symbols = tuple(name) + self._symbol = name + self._dimension = 1 + return self + + @property + def symbol(self): + return self._symbol + + def issymbol(self): + return True + + def __repr__(self): + return '{}({!r})'.format(self.__class__.__name__, self._symbol) def symbols(names): if isinstance(names, str): @@ -370,6 +415,10 @@ class Polyhedron: self._symbols = tuple(sorted(self._symbols)) return self + @classmethod + def fromstring(cls, string): + raise NotImplementedError + @property def equalities(self): return self._equalities @@ -378,16 +427,6 @@ class Polyhedron: def inequalities(self): return self._inequalities - @property - def constant(self): - return self._constant - - def isconstant(self): - return len(self._coefficients) == 0 - - def isempty(self): - return bool(libisl.isl_basic_set_is_empty(self._bset)) - @property def constraints(self): return self._constraints @@ -411,10 +450,11 @@ class Polyhedron: raise NotImplementedError def isempty(self): - return self == empty + bset = self._toisl() + return bool(libisl.isl_basic_set_is_empty(bset)) def isuniverse(self): - return self == universe + raise NotImplementedError def isdisjoint(self, other): # return true if the polyhedron has no elements in common with other @@ -484,17 +524,13 @@ class Polyhedron: return '{}(equalities={!r}, inequalities={!r})' \ ''.format(self.__class__.__name__, equalities, inequalities) - @classmethod - def fromstring(cls, string): - raise NotImplementedError - def _symbolunion(self, *others): symbols = set(self.symbols) for other in others: symbols.update(other.symbols) return sorted(symbols) - def _to_isl(self, symbols=None): + def _toisl(self, symbols=None): if symbols is None: symbols = self.symbols num_coefficients = len(symbols) @@ -530,16 +566,16 @@ class Polyhedron: return bset @classmethod - def from_isl(cls, bset): - '''takes basic set in isl form and puts back into python version of polyhedron - isl example code gives isl form as: - "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}") - our printer is giving form as: - b'{ [i0] : 1 = 0 }' ''' + def _fromisl(cls, bset): raise NotImplementedError equalities = ... inequalities = ... return cls(equalities, inequalities) + '''takes basic set in isl form and puts back into python version of polyhedron + isl example code gives isl form as: + "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}") + our printer is giving form as: + b'{ [i0] : 1 = 0 }' ''' #bset = self # if self._equalities: # constraints = libisl.isl_basic_set_equalities_matrix(bset, 3) @@ -556,5 +592,7 @@ if __name__ == '__main__': ex1 = Expression(coefficients={'a': 1, 'x': 2}, constant=2) ex2 = Expression(coefficients={'a': 3 , 'b': 2}, constant=3) p = Polyhedron(inequalities=[ex1, ex2]) - bs = p._to_isl() + bs = p._toisl() print(bs) + print('empty ?', p.isempty()) + print('empty ?', eq(0, 1).isempty())