X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/b96bc9c75fe5a692898435e8fb12fda27566b1aa..9e103619134c8839d143951c5b814bab500fcdcf:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 3939c71..e6d442e 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,5 +1,7 @@ +import ast import functools import numbers +import re from fractions import Fraction, gcd @@ -48,6 +50,13 @@ class Expression: This class implements linear expressions. """ + __slots__ = ( + '_coefficients', + '_constant', + '_symbols', + '_dimension', + ) + def __new__(cls, coefficients=None, constant=0): if isinstance(coefficients, str): if constant: @@ -86,9 +95,36 @@ class Expression: self._dimension = len(self._symbols) return self + @classmethod + def _fromast(cls, node): + if isinstance(node, ast.Module) and 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) and 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): @@ -319,11 +355,18 @@ class Constant(Expression): return bool(self.constant) def __repr__(self): - return '{}({!r})'.format(self.__class__.__name__, self._constant) - + if self.constant.denominator == 1: + return '{}({!r})'.format(self.__class__.__name__, self.constant) + else: + return '{}({!r}, {!r})'.format(self.__class__.__name__, + self.constant.numerator, self.constant.denominator) class Symbol(Expression): + __slots__ = Expression.__slots__ + ( + '_name', + ) + def __new__(cls, name): if isinstance(name, Symbol): name = name.name @@ -379,6 +422,13 @@ class Polyhedron: This class implements polyhedrons. """ + __slots__ = ( + '_equalities', + '_inequalities', + '_constraints', + '_symbols', + ) + def __new__(cls, equalities=None, inequalities=None): if isinstance(equalities, str): if inequalities is not None: @@ -410,9 +460,54 @@ class Polyhedron: self._symbols = tuple(sorted(self._symbols)) return self + @classmethod + def _fromast(cls, node): + if isinstance(node, ast.Module) and len(node.body) == 1: + return cls._fromast(node.body[0]) + elif isinstance(node, ast.Expr): + return cls._fromast(node.value) + elif isinstance(node, ast.BinOp) and isinstance(node.op, ast.BitAnd): + equalities1, inequalities1 = cls._fromast(node.left) + equalities2, inequalities2 = cls._fromast(node.right) + equalities = equalities1 + equalities2 + inequalities = inequalities1 + inequalities2 + return equalities, inequalities + elif isinstance(node, ast.Compare): + equalities = [] + inequalities = [] + 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: + break + left = right + else: + return equalities, inequalities + raise SyntaxError('invalid syntax') + @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) + tokens = re.split(r',|;|and|&&|/\\|∧', string, flags=re.I) + tokens = ['({})'.format(token) for token in tokens] + string = ' & '.join(tokens) + tree = ast.parse(string, 'eval') + equalities, inequalities = cls._fromast(tree) + return cls(equalities, inequalities) @property def equalities(self): @@ -579,7 +674,7 @@ class Polyhedron: dim = symbols.index(symbol) cin = libisl.isl_constraint_set_coefficient_val(cin, libisl.isl_dim_set, dim, val) if inequality.constant != 0: - val = str(ineq.constant).encode() + val = str(inequality.constant).encode() val = libisl.isl_val_read_from_str(_main_ctx, val) cin = libisl.isl_constraint_set_constant_val(cin, val) bset = libisl.isl_basic_set_add_constraint(bset, cin) @@ -587,7 +682,7 @@ class Polyhedron: return bset @classmethod - def _fromisl(cls, bset): + def _fromisl(cls, bset, symbols): raise NotImplementedError equalities = ... inequalities = ... @@ -599,12 +694,12 @@ class Polyhedron: { [i0, i1] : 2i1 >= -2 - i0 } ''' Empty = eq(0,1) + Universe = Polyhedron() + if __name__ == '__main__': - e1 = Expression(coefficients={'a': 2, 'b': 2}, constant= 1) - p1 = Polyhedron(equalities=[e1]) # empty - e2 = Expression(coefficients={'x': 3, 'y': 2}, constant= 3) - p2 = Polyhedron(equalities=[e2]) # not empty + p1 = Polyhedron('2a + 2b + 1 == 0') # empty print(p1._toisl()) + p2 = Polyhedron('3x + 2y + 3 == 0') # not empty print(p2._toisl())