X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/dedaed504aab41867667bb154b9eabfb7af0e881..4a5b05e6a8198c51980c14101b06a3e9e0159f4c:/pypol/linear.py?ds=sidebyside diff --git a/pypol/linear.py b/pypol/linear.py index 2e48a31..0712e1e 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,6 +1,7 @@ -import ctypes, ctypes.util +import ast import functools import numbers +import re from fractions import Fraction, gcd @@ -12,7 +13,7 @@ __all__ = [ 'Expression', 'Constant', 'Symbol', 'symbols', 'eq', 'le', 'lt', 'ge', 'gt', 'Polyhedron', - 'empty', 'universe' + 'Empty', 'Universe' ] @@ -70,7 +71,7 @@ class Expression: self._coefficients = {} for symbol, coefficient in coefficients: if isinstance(symbol, Symbol): - symbol = str(symbol) + symbol = symbol.name elif not isinstance(symbol, str): raise TypeError('symbols must be strings or Symbol instances') if isinstance(coefficient, Constant): @@ -87,9 +88,38 @@ class Expression: self._dimension = len(self._symbols) return self + @classmethod + def _fromast(cls, node): + if isinstance(node, ast.Module): + assert len(node.body) == 1 + return cls._fromast(node.body[0]) + elif isinstance(node, ast.Expr): + return cls._fromast(node.value) + elif isinstance(node, ast.Name): + return Symbol(node.id) + elif isinstance(node, ast.Num): + return Constant(node.n) + elif isinstance(node, ast.UnaryOp): + if isinstance(node.op, ast.USub): + return -cls._fromast(node.operand) + elif isinstance(node, ast.BinOp): + left = cls._fromast(node.left) + right = cls._fromast(node.right) + if isinstance(node.op, ast.Add): + return left + right + elif isinstance(node.op, ast.Sub): + return left - right + elif isinstance(node.op, ast.Mult): + return left * right + elif isinstance(node.op, ast.Div): + return left / right + raise SyntaxError('invalid syntax') + @classmethod def fromstring(cls, string): - raise NotImplementedError + string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string) + tree = ast.parse(string, 'eval') + return cls._fromast(tree) @property def symbols(self): @@ -127,10 +157,6 @@ class Expression: yield self.coefficient(symbol) yield self.constant - @property - def symbol(self): - raise ValueError('not a symbol: {}'.format(self)) - def issymbol(self): return False @@ -331,26 +357,26 @@ class Symbol(Expression): def __new__(cls, name): if isinstance(name, Symbol): - name = name.symbol + name = name.name 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._name = name self._dimension = 1 return self @property - def symbol(self): - return self._symbol + def name(self): + return self._name def issymbol(self): return True def __repr__(self): - return '{}({!r})'.format(self.__class__.__name__, self._symbol) + return '{}({!r})'.format(self.__class__.__name__, self._name) def symbols(names): if isinstance(names, str): @@ -417,7 +443,40 @@ class Polyhedron: @classmethod def fromstring(cls, string): - raise NotImplementedError + string = string.strip() + string = re.sub(r'^\{\s*|\s*\}$', '', string) + string = re.sub(r'([^<=>])=([^<=>])', r'\1==\2', string) + string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string) + equalities = [] + inequalities = [] + for cstr in re.split(r',|;|and|&&|/\\|∧', string, flags=re.I): + tree = ast.parse(cstr.strip(), 'eval') + if not isinstance(tree, ast.Module) or len(tree.body) != 1: + raise SyntaxError('invalid syntax') + node = tree.body[0] + if not isinstance(node, ast.Expr): + raise SyntaxError('invalid syntax') + node = node.value + if not isinstance(node, ast.Compare): + raise SyntaxError('invalid syntax') + left = Expression._fromast(node.left) + for i in range(len(node.ops)): + op = node.ops[i] + right = Expression._fromast(node.comparators[i]) + if isinstance(op, ast.Lt): + inequalities.append(right - left - 1) + elif isinstance(op, ast.LtE): + inequalities.append(right - left) + elif isinstance(op, ast.Eq): + equalities.append(left - right) + elif isinstance(op, ast.GtE): + inequalities.append(left - right) + elif isinstance(op, ast.Gt): + inequalities.append(left - right - 1) + else: + raise SyntaxError('invalid syntax') + left = right + return cls(equalities, inequalities) @property def equalities(self): @@ -528,7 +587,6 @@ class Polyhedron: other = other._toisl(symbols) difference = libisl.isl_set_subtract(bset, other) return difference - def __sub__(self, other): return self.difference(other) @@ -542,10 +600,15 @@ class Polyhedron: return '{{{}}}'.format(', '.join(constraints)) def __repr__(self): - equalities = list(self.equalities) - inequalities = list(self.inequalities) - return '{}(equalities={!r}, inequalities={!r})' \ - ''.format(self.__class__.__name__, equalities, inequalities) + if self.isempty(): + return 'Empty' + elif self.isuniverse(): + return 'Universe' + else: + equalities = list(self.equalities) + inequalities = list(self.inequalities) + return '{}(equalities={!r}, inequalities={!r})' \ + ''.format(self.__class__.__name__, equalities, inequalities) def _symbolunion(self, *others): symbols = set(self.symbols) @@ -556,42 +619,39 @@ class Polyhedron: def _toisl(self, symbols=None): if symbols is None: symbols = self.symbols - num_coefficients = len(symbols) - space = libisl.isl_space_set_alloc(_main_ctx, 0, num_coefficients) + dimension = len(symbols) + space = libisl.isl_space_set_alloc(_main_ctx, 0, dimension) bset = libisl.isl_basic_set_universe(libisl.isl_space_copy(space)) ls = libisl.isl_local_space_from_space(space) - #if there are equalities/inequalities, take each constant and coefficient and add as a constraint to the basic set - for eq in self.equalities: + for equality in self.equalities: ceq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(ls)) - coeff_eq = dict(eq.coefficients()) - if eq.constant: - value = str(eq.constant).encode() - val = libisl.isl_val_read_from_str(_main_ctx, value) + for symbol, coefficient in equality.coefficients(): + val = str(coefficient).encode() + val = libisl.isl_val_read_from_str(_main_ctx, val) + dim = symbols.index(symbol) + ceq = libisl.isl_constraint_set_coefficient_val(ceq, libisl.isl_dim_set, dim, val) + if equality.constant != 0: + val = str(equality.constant).encode() + val = libisl.isl_val_read_from_str(_main_ctx, val) ceq = libisl.isl_constraint_set_constant_val(ceq, val) - for eq in coeff_eq: - number = str(coeff_eq.get(eq)).encode() - num = libisl.isl_val_read_from_str(_main_ctx, number) - iden = symbols.index(eq) - ceq = libisl.isl_constraint_set_coefficient_val(ceq, libisl.isl_dim_set, iden, num) #use 3 for type isl_dim_set - bset = libisl.isl_basic_set_add_constraint(bset, ceq) - for ineq in self.inequalities: + bset = libisl.isl_basic_set_add_constraint(bset, ceq) + for inequality in self.inequalities: cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls)) - coeff_in = dict(ineq.coefficients()) - if ineq.constant: - value = str(ineq.constant).encode() - val = libisl.isl_val_read_from_str(_main_ctx, value) + for symbol, coefficient in inequality.coefficients(): + val = str(coefficient).encode() + val = libisl.isl_val_read_from_str(_main_ctx, val) + dim = symbols.index(symbol) + cin = libisl.isl_constraint_set_coefficient_val(cin, libisl.isl_dim_set, dim, val) + if inequality.constant != 0: + val = str(inequality.constant).encode() + val = libisl.isl_val_read_from_str(_main_ctx, val) cin = libisl.isl_constraint_set_constant_val(cin, val) - for ineq in coeff_in: - number = str(coeff_in.get(ineq)).encode() - num = libisl.isl_val_read_from_str(_main_ctx, number) - iden = symbols.index(ineq) - cin = libisl.isl_constraint_set_coefficient_val(cin, libisl.isl_dim_set, iden, num) #use 3 for type isl_dim_set - bset = libisl.isl_basic_set_add_constraint(bset, cin) + bset = libisl.isl_basic_set_add_constraint(bset, cin) bset = isl.BasicSet(bset) return bset @classmethod - def _fromisl(cls, bset): + def _fromisl(cls, bset, symbols): raise NotImplementedError equalities = ... inequalities = ... @@ -602,12 +662,11 @@ class Polyhedron: our printer is giving form as: { [i0, i1] : 2i1 >= -2 - i0 } ''' -empty = None #eq(0,1) -universe = None #Polyhedron() +Empty = eq(0,1) +Universe = Polyhedron() if __name__ == '__main__': - ex1 = Expression(coefficients={'a': 6, 'b': 6}, constant= 3) #this is the expression that does not work (even without adding values) - ex2 = Expression(coefficients={'x': 4, 'y': 2}, constant= 3) - p = Polyhedron(equalities=[ex2]) - p2 = Polyhedron(equalities=[ex2]) - print(p._toisl()) # checking is values works for toisl + p1 = Polyhedron('2a + 2b + 1 == 0') # empty + print(p1._toisl()) + p2 = Polyhedron('3x + 2y + 3 == 0') # not empty + print(p2._toisl())