index 3939c71..e6d442e 100644 (file)
@@ -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

@@ -48,6 +50,13 @@ class Expression:
This class implements linear expressions.
"""

This class implements linear expressions.
"""

+    __slots__ = (
+        '_coefficients',
+        '_constant',
+        '_symbols',
+        '_dimension',
+    )
+
def __new__(cls, coefficients=None, constant=0):
if isinstance(coefficients, str):
if constant:
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

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)
+                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):
@@ -319,11 +355,18 @@ class Constant(Expression):
return bool(self.constant)

def __repr__(self):
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):

class Symbol(Expression):

+    __slots__ = Expression.__slots__ + (
+        '_name',
+    )
+
def __new__(cls, name):
if isinstance(name, Symbol):
name = name.name
def __new__(cls, name):
if isinstance(name, Symbol):
name = name.name
@@ -379,6 +422,13 @@ class Polyhedron:
This class implements polyhedrons.
"""

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:
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

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):
@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):

@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:
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()
cin = libisl.isl_constraint_set_constant_val(cin, val)
cin = libisl.isl_constraint_set_constant_val(cin, val)
@@ -587,7 +682,7 @@ class Polyhedron:
return bset

@classmethod
return bset

@classmethod
-    def _fromisl(cls, bset):
+    def _fromisl(cls, bset, symbols):
raise NotImplementedError
equalities = ...
inequalities = ...
raise NotImplementedError
equalities = ...
inequalities = ...
@@ -599,12 +694,12 @@ class Polyhedron:
{ [i0, i1] : 2i1 >= -2 - i0 } '''

Empty = eq(0,1)
{ [i0, i1] : 2i1 >= -2 - i0 } '''

Empty = eq(0,1)
+
Universe = Polyhedron()

Universe = Polyhedron()

+
if __name__ == '__main__':
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())
print(p1._toisl())
+    p2 = Polyhedron('3x + 2y + 3 == 0') # not empty
print(p2._toisl())
print(p2._toisl())