X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/0efaf62e3354a0663031bc16b53d9d8b597f50d0..156db05a9a4c4e6d71a431fcc6343b973ca1d5ab:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 8a61744..8fdece9 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -50,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: @@ -90,8 +97,7 @@ class Expression: @classmethod def _fromast(cls, node): - if isinstance(node, ast.Module): - assert len(node.body) == 1 + 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) @@ -99,9 +105,8 @@ class Expression: 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.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) @@ -117,9 +122,7 @@ class Expression: @classmethod def fromstring(cls, string): - string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', - lambda m: '{}*{}'.format(m.group(1), m.group(2)), - string) + string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string) tree = ast.parse(string, 'eval') return cls._fromast(tree) @@ -357,6 +360,10 @@ class Constant(Expression): class Symbol(Expression): + __slots__ = Expression.__slots__ + ( + '_name', + ) + def __new__(cls, name): if isinstance(name, Symbol): name = name.name @@ -412,6 +419,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: @@ -443,9 +457,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): @@ -612,7 +671,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) @@ -632,12 +691,12 @@ class Polyhedron: { [i0, i1] : 2i1 >= -2 - i0 } ''' Empty = eq(0,1) + Universe = Polyhedron() + if __name__ == '__main__': - e1 = Expression('2a + 2b + 1') - p1 = Polyhedron(equalities=[e1]) # empty - e2 = Expression('3x + 2y + 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())