Implement Polyhedron.fromstring

[linpy.git] / pypol / linear.py

diff --git a/pypol/linear.py b/pypol/linear.py
index 3cd7633..0712e1e 100644 (file)
--- a/pypol/linear.py
+++ b/pypol/linear.py
@@ -1,5 +1,7 @@
+import ast

 import functools
 import numbers
 import functools
 import numbers

+import re

 
 from fractions import Fraction, gcd
 
 
 from fractions import Fraction, gcd
 


@@ -69,7 +71,7 @@ class Expression:
         self._coefficients = {}
         for symbol, coefficient in coefficients:
             if isinstance(symbol, Symbol):
         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):
             elif not isinstance(symbol, str):
                 raise TypeError('symbols must be strings or Symbol instances')
             if isinstance(coefficient, Constant):


@@ -86,9 +88,38 @@ class Expression:
         self._dimension = len(self._symbols)
         return self
 
         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):
     @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):
 
     @property
     def symbols(self):


@@ -126,10 +157,6 @@ class Expression:
             yield self.coefficient(symbol)
         yield self.constant
 
             yield self.coefficient(symbol)
         yield self.constant
 

-    @property
-    def symbol(self):
-        raise ValueError('not a symbol: {}'.format(self))
-

     def issymbol(self):
         return False
 
     def issymbol(self):
         return False
 


@@ -330,26 +357,26 @@ class Symbol(Expression):
 
     def __new__(cls, name):
         if isinstance(name, Symbol):
 
     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)
         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
         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):
 
     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):
 
 def symbols(names):
     if isinstance(names, str):


@@ -416,7 +443,40 @@ class Polyhedron:
 
     @classmethod
     def fromstring(cls, string):
 
     @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):
 
     @property
     def equalities(self):


@@ -528,7 +588,6 @@ class Polyhedron:
         difference = libisl.isl_set_subtract(bset, other)
         return difference
 
         difference = libisl.isl_set_subtract(bset, other)
         return difference
 

-

     def __sub__(self, other):
         return self.difference(other)
 
     def __sub__(self, other):
         return self.difference(other)
 


@@ -560,42 +619,39 @@ class Polyhedron:
     def _toisl(self, symbols=None):
         if symbols is None:
             symbols = self.symbols
     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)
         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))
             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)
                 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)
             bset = libisl.isl_basic_set_add_constraint(bset, ceq)

-        for ineq in self.inequalities:
+        for inequality in self.inequalities:

             cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls))
             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)
                 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 = isl.BasicSet(bset)
         return bset
 
     @classmethod
             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 = ...
         raise NotImplementedError
         equalities = ...
         inequalities = ...


@@ -610,8 +666,7 @@ Empty = eq(0,1)
 Universe = Polyhedron()
 
 if __name__ == '__main__':
 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())