From a8bb1d373098fbaaac285cc7aeea6b9b380f2fd7 Mon Sep 17 00:00:00 2001 From: Danielle Bolan Date: Tue, 1 Jul 2014 16:03:38 +0200 Subject: [PATCH 01/16] Project_out working --- pypol/domains.py | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/pypol/domains.py b/pypol/domains.py index 4a1f9aa..6c10de3 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -154,15 +154,19 @@ class Domain: def drop_dims(self, dims): # use to remove certain variables use isl_set_drop_constraints_involving_dims instead? - from .polyhedra import Polyhedron + from .polyhedra import Polyhedron dims = list(dims) symbols = list(self.symbols) + print(symbols) islset = self._toislset(self.polyhedra, self.symbols) for dim in dims: if dim in symbols: - num = symbols.index(dim) - islbset = libisl.isl_set_drop_constraints_involving_dims(islset, libisl.isl_dim_set, num, 1) - return Polyhedron._fromislset(islbset, self.symbols) + first = symbols.index(dim) + islbset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, first, 1) + symbols.__delitem__(first) + else: + islbset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, 0, 0) + return Polyhedron._fromislset(islbset, symbols) def sample(self): from .polyhedra import Polyhedron -- 2.20.1 From 49b7b1b00f4cbbf5110ec77e72df004764f2b4bd Mon Sep 17 00:00:00 2001 From: Danielle Bolan Date: Tue, 1 Jul 2014 16:17:53 +0200 Subject: [PATCH 02/16] Remove print statement --- pypol/domains.py | 1 - 1 file changed, 1 deletion(-) diff --git a/pypol/domains.py b/pypol/domains.py index 6c10de3..be87ffb 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -157,7 +157,6 @@ class Domain: from .polyhedra import Polyhedron dims = list(dims) symbols = list(self.symbols) - print(symbols) islset = self._toislset(self.polyhedra, self.symbols) for dim in dims: if dim in symbols: -- 2.20.1 From 7db03eb9ea6c6d0a3896d8682b64fd404a833e92 Mon Sep 17 00:00:00 2001 From: Danielle Bolan Date: Tue, 1 Jul 2014 16:22:41 +0200 Subject: [PATCH 03/16] Add basic tests for drop_dims --- examples/squares.py | 4 +++- pypol/tests/test_domains.py | 7 +++++++ 2 files changed, 10 insertions(+), 1 deletion(-) diff --git a/examples/squares.py b/examples/squares.py index d23e636..e140e30 100755 --- a/examples/squares.py +++ b/examples/squares.py @@ -63,5 +63,7 @@ print() print('sq6:', sq6) print('sq6 simplified:', sq6.sample()) print() -print('sq7 with out constraints involving y and a', sq7.drop_dims('y a')) +#print(u.drop_dims(' ')) +print('sq7 with out constraints involving y and a', sq7.drop_dims('y a')) #drops dims that are passed + diff --git a/pypol/tests/test_domains.py b/pypol/tests/test_domains.py index 555c331..1beaa85 100644 --- a/pypol/tests/test_domains.py +++ b/pypol/tests/test_domains.py @@ -21,6 +21,7 @@ class TestDomain(unittest.TestCase): self.disjoint = And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)) self.compliment = Or(Ge(-x - 1, 0), Ge(x - 3, 0), And(Ge(x, 0), Ge(-x + 2, 0), Ge(-y - 1, 0)), And(Ge(x, 0), Ge(-x + 2, 0), Ge(y - 3, 0))) self.hull = And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)) + self.dropped = And(Ge(y, 0), Ge(-y + 2, 0)) self.sample = And(Eq(y - 3, 0), Eq(x - 1, 0)) self.intersection = And(Ge(x - 1, 0), Ge(-x + 2, 0), Ge(y - 1, 0), Ge(-y + 2, 0)) self.union = Or(And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)), And(Ge(x - 1, 0), Ge(-x + 3, 0), Ge(y - 1, 0), Ge(-y + 3, 0))) @@ -75,6 +76,12 @@ class TestDomain(unittest.TestCase): def test_polyhedral_hull(self): self.assertEqual(self.square1.polyhedral_hull(), self.hull) + + def test_drop_dims(self): + self.assertEqual(self.square1.drop_dims('x'), self.dropped) + self.assertEqual(self.square1.drop_dims('x y'), self.universe) + self.assertEqual(self.universe.drop_dims(' '), self.universe) + self.assertEqual(self.empty.drop_dims(' '), Empty) @unittest.expectedFailure def test_simplify(self): -- 2.20.1 From 1b9c772ffc21a71d146a093537d371d63be16c75 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Tue, 1 Jul 2014 16:29:15 +0200 Subject: [PATCH 04/16] Add diamond example --- examples/diamond.py | 9 +++++++++ 1 file changed, 9 insertions(+) create mode 100755 examples/diamond.py diff --git a/examples/diamond.py b/examples/diamond.py new file mode 100755 index 0000000..148cdca --- /dev/null +++ b/examples/diamond.py @@ -0,0 +1,9 @@ +#!/usr/bin/env python3 + +from pypol import * + +x, y = symbols('x y') +diam = Ge(y, x - 1) & Le(y, x + 1) & Ge(y, -x - 1) & Le(y, -x + 1) +print('diamond:', diam) +print('projected on x:', diam.drop_dims('y')) + -- 2.20.1 From ead3c442d29f0c45989d165f34e27dd0eb7d87c4 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Tue, 1 Jul 2014 18:31:13 +0200 Subject: [PATCH 05/16] Fix make test --- examples/diamond.py | 1 - examples/squares.py | 10 ++++------ pypol/tests/test_domains.py | 3 +-- 3 files changed, 5 insertions(+), 9 deletions(-) diff --git a/examples/diamond.py b/examples/diamond.py index 148cdca..ad0942b 100755 --- a/examples/diamond.py +++ b/examples/diamond.py @@ -6,4 +6,3 @@ x, y = symbols('x y') diam = Ge(y, x - 1) & Le(y, x + 1) & Ge(y, -x - 1) & Le(y, -x + 1) print('diamond:', diam) print('projected on x:', diam.drop_dims('y')) - diff --git a/examples/squares.py b/examples/squares.py index e140e30..d606631 100755 --- a/examples/squares.py +++ b/examples/squares.py @@ -8,7 +8,7 @@ sq1 = Le(0, x) & Le(x, 2) & Le(0, y) & Le(y, 2) sq2 = Le(2, x) & Le(x, 4) & Le(2, y) & Le(y, 4) sq3 = Le(0, x) & Le(x, 3) & Le(0, y) & Le(y, 3) sq4 = Le(1, x) & Le(x, 2) & Le(1, y) & Le(y, 2) -sq5 = Le(1, x) & Le(x, 2) & Le(1, y) +sq5 = Le(1, x) & Le(x, 2) & Le(1, y) sq6 = Le(1, x) & Le(x, 2) & Le(1, y) & Eq(y, 3) sq7 = Le(0, x) & Le(x, 2) & Le(0, y) & Eq(z, 2) & Le(a, 3) u = Polyhedron([]) @@ -20,7 +20,7 @@ print('sq3 =', sq3) #print correct square print('sq4 =', sq4) #print correct square print('u =', u) #print correct square print() -print('¬sq1 =', ~sq1) #test compliment +print('¬sq1 =', ~sq1) #test complement print() print('sq1 + sq1 =', sq1 + sq2) #test addition print('sq1 + sq2 =', Polyhedron(sq1 + sq2)) #test addition @@ -39,7 +39,7 @@ print('sq1 ⊔ sq2 =', Polyhedron(sq1 | sq2)) # test convex union print() print('check if sq1 and sq2 disjoint:', sq1.isdisjoint(sq2)) #should return false print() -print('sq1 disjoint:', sq1.disjoint()) #make disjoint +print('sq1 disjoint:', sq1.disjoint()) #make disjoint print('sq2 disjoint:', sq2.disjoint()) #make disjoint print() print('is square 1 universe?:', sq1.isuniverse()) #test if square is universe @@ -54,7 +54,7 @@ print() print('lexographic min of sq2:', sq2.lexmin()) #test lexmax() print('lexographic max of sq2:', sq2.lexmax()) #test lexmax() print() -print('Polyhedral hull of sq1 + sq2 is:', x.polyhedral_hull()) #test polyhedral hull, returns same +print('Polyhedral hull of sq1 + sq2 is:', x.polyhedral_hull()) #test polyhedral hull, returns same #value as Polyhedron(sq1 + sq2) print() print('is sq1 bounded?', sq1.isbounded()) #unbounded should return True @@ -65,5 +65,3 @@ print('sq6 simplified:', sq6.sample()) print() #print(u.drop_dims(' ')) print('sq7 with out constraints involving y and a', sq7.drop_dims('y a')) #drops dims that are passed - - diff --git a/pypol/tests/test_domains.py b/pypol/tests/test_domains.py index 1beaa85..0e06771 100644 --- a/pypol/tests/test_domains.py +++ b/pypol/tests/test_domains.py @@ -76,14 +76,13 @@ class TestDomain(unittest.TestCase): def test_polyhedral_hull(self): self.assertEqual(self.square1.polyhedral_hull(), self.hull) - + def test_drop_dims(self): self.assertEqual(self.square1.drop_dims('x'), self.dropped) self.assertEqual(self.square1.drop_dims('x y'), self.universe) self.assertEqual(self.universe.drop_dims(' '), self.universe) self.assertEqual(self.empty.drop_dims(' '), Empty) - @unittest.expectedFailure def test_simplify(self): self.assertEqual(self.universe.simplify(), self.universe) self.assertEqual(self.empty.simplify(), Empty) -- 2.20.1 From b47140c554b345a934698a04a2a8c0e64685ed17 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Tue, 1 Jul 2014 18:32:54 +0200 Subject: [PATCH 06/16] Let's test complement, not compliment --- pypol/tests/test_domains.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/pypol/tests/test_domains.py b/pypol/tests/test_domains.py index 0e06771..692627c 100644 --- a/pypol/tests/test_domains.py +++ b/pypol/tests/test_domains.py @@ -19,7 +19,7 @@ class TestDomain(unittest.TestCase): self.universe = Polyhedron([]) self.empty = Empty self.disjoint = And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)) - self.compliment = Or(Ge(-x - 1, 0), Ge(x - 3, 0), And(Ge(x, 0), Ge(-x + 2, 0), Ge(-y - 1, 0)), And(Ge(x, 0), Ge(-x + 2, 0), Ge(y - 3, 0))) + self.complement = Or(Ge(-x - 1, 0), Ge(x - 3, 0), And(Ge(x, 0), Ge(-x + 2, 0), Ge(-y - 1, 0)), And(Ge(x, 0), Ge(-x + 2, 0), Ge(y - 3, 0))) self.hull = And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)) self.dropped = And(Ge(y, 0), Ge(-y + 2, 0)) self.sample = And(Eq(y - 3, 0), Eq(x - 1, 0)) @@ -71,8 +71,8 @@ class TestDomain(unittest.TestCase): self.assertTrue(self.square4 < self.square3) self.assertFalse(self.square3 < self.square4) - def test_compliment(self): - self.assertEqual(~self.square1, self.compliment) + def test_complement(self): + self.assertEqual(~self.square1, self.complement) def test_polyhedral_hull(self): self.assertEqual(self.square1.polyhedral_hull(), self.hull) -- 2.20.1 From 4ae512f39c14835badbfab6fc1ce877f601d104e Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Tue, 1 Jul 2014 18:47:54 +0200 Subject: [PATCH 07/16] Alternative implementation of projection --- pypol/domains.py | 26 +++++++++++--------------- pypol/tests/test_domains.py | 10 +++++----- 2 files changed, 16 insertions(+), 20 deletions(-) diff --git a/pypol/domains.py b/pypol/domains.py index be87ffb..c844e55 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -139,7 +139,7 @@ class Domain: def simplify(self): #does not change anything in any of the examples - #isl seems to do this naturally + #isl seems to do this naturally islset = self._toislset(self.polyhedra, self.symbols) islset = libisl.isl_set_remove_redundancies(islset) return self._fromislset(islset, self.symbols) @@ -152,21 +152,17 @@ class Domain: islbset = libisl.isl_set_polyhedral_hull(islset) return Polyhedron._fromislbasicset(islbset, self.symbols) - def drop_dims(self, dims): - # use to remove certain variables use isl_set_drop_constraints_involving_dims instead? - from .polyhedra import Polyhedron - dims = list(dims) - symbols = list(self.symbols) + def project_out(self, symbols): + # use to remove certain variables islset = self._toislset(self.polyhedra, self.symbols) - for dim in dims: - if dim in symbols: - first = symbols.index(dim) - islbset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, first, 1) - symbols.__delitem__(first) - else: - islbset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, 0, 0) - return Polyhedron._fromislset(islbset, symbols) - + # the trick is to walk symbols in reverse order, to avoid index updates + for index, symbol in reversed(list(enumerate(self.symbols))): + if symbol in symbols: + islset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, index, 1) + # remaining symbols + symbols = [symbol for symbol in self.symbols if symbol not in symbols] + return Domain._fromislset(islset, symbols) + def sample(self): from .polyhedra import Polyhedron islset = self._toislset(self.polyhedra, self.symbols) diff --git a/pypol/tests/test_domains.py b/pypol/tests/test_domains.py index 692627c..55853fd 100644 --- a/pypol/tests/test_domains.py +++ b/pypol/tests/test_domains.py @@ -77,11 +77,11 @@ class TestDomain(unittest.TestCase): def test_polyhedral_hull(self): self.assertEqual(self.square1.polyhedral_hull(), self.hull) - def test_drop_dims(self): - self.assertEqual(self.square1.drop_dims('x'), self.dropped) - self.assertEqual(self.square1.drop_dims('x y'), self.universe) - self.assertEqual(self.universe.drop_dims(' '), self.universe) - self.assertEqual(self.empty.drop_dims(' '), Empty) + def test_project_out(self): + self.assertEqual(self.square1.project_out('x'), self.dropped) + self.assertEqual(self.square1.project_out('x y'), self.universe) + self.assertEqual(self.universe.project_out(' '), self.universe) + self.assertEqual(self.empty.project_out(' '), Empty) def test_simplify(self): self.assertEqual(self.universe.simplify(), self.universe) -- 2.20.1 From d6444456ceaeed6fcf1d44386edefb5b1fb8ec66 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Tue, 1 Jul 2014 19:05:07 +0200 Subject: [PATCH 08/16] Overloading for Domains.project_out(), to be improved --- examples/diamond.py | 2 +- pypol/domains.py | 11 ++++++++++- 2 files changed, 11 insertions(+), 2 deletions(-) diff --git a/examples/diamond.py b/examples/diamond.py index ad0942b..1681054 100755 --- a/examples/diamond.py +++ b/examples/diamond.py @@ -5,4 +5,4 @@ from pypol import * x, y = symbols('x y') diam = Ge(y, x - 1) & Le(y, x + 1) & Ge(y, -x - 1) & Le(y, -x + 1) print('diamond:', diam) -print('projected on x:', diam.drop_dims('y')) +print('projected on x:', diam.project_out([y])) diff --git a/pypol/domains.py b/pypol/domains.py index c844e55..6b47fe8 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -5,7 +5,7 @@ import re from . import islhelper from .islhelper import mainctx, libisl, isl_set_basic_sets -from .linexprs import Expression +from .linexprs import Expression, Symbol __all__ = [ @@ -154,6 +154,15 @@ class Domain: def project_out(self, symbols): # use to remove certain variables + if isinstance(symbols, str): + symbols = symbols.replace(',', ' ').split() + else: + symbols = list(symbols) + for i, symbol in enumerate(symbols): + if isinstance(symbol, Symbol): + symbols[i] = symbol.name + elif not isinstance(symbol, str): + raise TypeError('symbols must be strings or Symbol instances') islset = self._toislset(self.polyhedra, self.symbols) # the trick is to walk symbols in reverse order, to avoid index updates for index, symbol in reversed(list(enumerate(self.symbols))): -- 2.20.1 From 66eaddd271c4beff5451fab2030389cd634e1385 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 06:10:18 +0200 Subject: [PATCH 09/16] Add missing classmethod decorator --- pypol/domains.py | 1 + 1 file changed, 1 insertion(+) diff --git a/pypol/domains.py b/pypol/domains.py index 6b47fe8..b4780fc 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -249,6 +249,7 @@ class Domain: self._dimension = len(self._symbols) return self + @classmethod def _toislset(cls, polyhedra, symbols): polyhedron = polyhedra[0] islbset = polyhedron._toislbasicset(polyhedron.equalities, -- 2.20.1 From 4eabec44af2e635408d9cba8672e947145cc6971 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 06:32:12 +0200 Subject: [PATCH 10/16] Improve hash functions in linexprs --- pypol/linexprs.py | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/pypol/linexprs.py b/pypol/linexprs.py index d8b020d..3aef337 100644 --- a/pypol/linexprs.py +++ b/pypol/linexprs.py @@ -36,6 +36,7 @@ class Expression: '_constant', '_symbols', '_dimension', + '_hash', ) def __new__(cls, coefficients=None, constant=0): @@ -77,6 +78,7 @@ class Expression: self._constant = constant self._symbols = tuple(self._coefficients) self._dimension = len(self._symbols) + self._hash = hash((tuple(self._coefficients.items()), self._constant)) return self def coefficient(self, symbol): @@ -106,6 +108,9 @@ class Expression: def dimension(self): return self._dimension + def __hash__(self): + return self._hash + def isconstant(self): return False @@ -220,9 +225,6 @@ class Expression: from .polyhedra import Gt return Gt(self, other) - def __hash__(self): - return hash((tuple(self.coefficients()), self._constant)) - def _toint(self): lcm = functools.reduce(lambda a, b: a*b // gcd(a, b), [value.denominator for value in self.values()]) @@ -348,11 +350,12 @@ class Symbol(Expression): raise TypeError('name must be a string or a Symbol instance') name = name.strip() self = object().__new__(cls) - self._coefficients = {name: 1} + self._coefficients = OrderedDict([(name, 1)]) self._constant = 0 self._symbols = tuple(name) self._name = name self._dimension = 1 + self._hash = hash(self._name) return self @property @@ -398,9 +401,10 @@ class Constant(Expression): self._constant = numerator.constant else: self._constant = Fraction(numerator, denominator) - self._coefficients = {} + self._coefficients = OrderedDict() self._symbols = () self._dimension = 0 + self._hash = hash(self._constant) return self def isconstant(self): -- 2.20.1 From c3d305942999eeb429c6941184b47e7f1b55c499 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 06:53:14 +0200 Subject: [PATCH 11/16] Better implementation of symbols and constants --- pypol/linexprs.py | 73 +++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 64 insertions(+), 9 deletions(-) diff --git a/pypol/linexprs.py b/pypol/linexprs.py index 3aef337..9449219 100644 --- a/pypol/linexprs.py +++ b/pypol/linexprs.py @@ -83,7 +83,7 @@ class Expression: def coefficient(self, symbol): if isinstance(symbol, Symbol): - symbol = str(symbol) + symbol = symbol.name elif not isinstance(symbol, str): raise TypeError('symbol must be a string or a Symbol instance') try: @@ -339,8 +339,9 @@ class Expression: class Symbol(Expression): - __slots__ = Expression.__slots__ + ( + __slots__ = ( '_name', + '_hash', ) def __new__(cls, name): @@ -350,11 +351,7 @@ class Symbol(Expression): raise TypeError('name must be a string or a Symbol instance') name = name.strip() self = object().__new__(cls) - self._coefficients = OrderedDict([(name, 1)]) - self._constant = 0 - self._symbols = tuple(name) self._name = name - self._dimension = 1 self._hash = hash(self._name) return self @@ -362,9 +359,40 @@ class Symbol(Expression): def name(self): return self._name + def __hash__(self): + return self._hash + + def coefficient(self, symbol): + if isinstance(symbol, Symbol): + symbol = symbol.name + elif not isinstance(symbol, str): + raise TypeError('symbol must be a string or a Symbol instance') + if symbol == self.name: + return 1 + else: + return 0 + + def coefficients(self): + yield self.name, 1 + + @property + def constant(self): + return 0 + + @property + def symbols(self): + return self.name, + + @property + def dimension(self): + return 1 + def issymbol(self): return True + def __eq__(self, other): + return isinstance(other, Symbol) and self.name == other.name + @classmethod def _fromast(cls, node): if isinstance(node, ast.Module) and len(node.body) == 1: @@ -395,21 +423,48 @@ def symbols(names): class Constant(Expression): + __slots__ = ( + '_constant', + '_hash', + ) + def __new__(cls, numerator=0, denominator=None): self = object().__new__(cls) if denominator is None and isinstance(numerator, Constant): self._constant = numerator.constant else: self._constant = Fraction(numerator, denominator) - self._coefficients = OrderedDict() - self._symbols = () - self._dimension = 0 self._hash = hash(self._constant) return self + def __hash__(self): + return self._hash + + def coefficient(self, symbol): + if isinstance(symbol, Symbol): + symbol = symbol.name + elif not isinstance(symbol, str): + raise TypeError('symbol must be a string or a Symbol instance') + return 0 + + def coefficients(self): + yield from [] + + @property + def symbols(self): + return () + + @property + def dimension(self): + return 0 + def isconstant(self): return True + @_polymorphic + def __eq__(self, other): + return isinstance(other, Constant) and self.constant == other.constant + def __bool__(self): return self.constant != 0 -- 2.20.1 From 556abe7f3b2c7e3985560f3e3cfb6f66bacc4122 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 07:08:11 +0200 Subject: [PATCH 12/16] Helper functions symbolname and symbolnames --- pypol/domains.py | 13 +++---------- pypol/linexprs.py | 41 +++++++++++++++++++---------------------- 2 files changed, 22 insertions(+), 32 deletions(-) diff --git a/pypol/domains.py b/pypol/domains.py index b4780fc..6060dc9 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -5,7 +5,7 @@ import re from . import islhelper from .islhelper import mainctx, libisl, isl_set_basic_sets -from .linexprs import Expression, Symbol +from .linexprs import Expression, Symbol, symbolnames __all__ = [ @@ -154,15 +154,7 @@ class Domain: def project_out(self, symbols): # use to remove certain variables - if isinstance(symbols, str): - symbols = symbols.replace(',', ' ').split() - else: - symbols = list(symbols) - for i, symbol in enumerate(symbols): - if isinstance(symbol, Symbol): - symbols[i] = symbol.name - elif not isinstance(symbol, str): - raise TypeError('symbols must be strings or Symbol instances') + symbols = symbolnames(symbols) islset = self._toislset(self.polyhedra, self.symbols) # the trick is to walk symbols in reverse order, to avoid index updates for index, symbol in reversed(list(enumerate(self.symbols))): @@ -346,6 +338,7 @@ class Domain: def tosympy(self): raise NotImplementedError + def And(*domains): if len(domains) == 0: from .polyhedra import Universe diff --git a/pypol/linexprs.py b/pypol/linexprs.py index 9449219..ed68493 100644 --- a/pypol/linexprs.py +++ b/pypol/linexprs.py @@ -9,7 +9,7 @@ from fractions import Fraction, gcd __all__ = [ 'Expression', - 'Symbol', 'symbols', + 'Symbol', 'symbols', 'symbolname', 'symbolnames', 'Constant', ] @@ -59,10 +59,7 @@ class Expression: self = object().__new__(cls) self._coefficients = {} for symbol, coefficient in coefficients: - if isinstance(symbol, Symbol): - symbol = symbol.name - elif not isinstance(symbol, str): - raise TypeError('symbols must be strings or Symbol instances') + symbol = symbolname(symbol) if isinstance(coefficient, Constant): coefficient = coefficient.constant if not isinstance(coefficient, numbers.Rational): @@ -82,10 +79,7 @@ class Expression: return self def coefficient(self, symbol): - if isinstance(symbol, Symbol): - symbol = symbol.name - elif not isinstance(symbol, str): - raise TypeError('symbol must be a string or a Symbol instance') + symbol = symbolname(symbol) try: return self._coefficients[symbol] except KeyError: @@ -345,11 +339,7 @@ class Symbol(Expression): ) def __new__(cls, name): - if isinstance(name, Symbol): - name = name.name - elif not isinstance(name, str): - raise TypeError('name must be a string or a Symbol instance') - name = name.strip() + name = symbolname(name) self = object().__new__(cls) self._name = name self._hash = hash(self._name) @@ -363,10 +353,7 @@ class Symbol(Expression): return self._hash def coefficient(self, symbol): - if isinstance(symbol, Symbol): - symbol = symbol.name - elif not isinstance(symbol, str): - raise TypeError('symbol must be a string or a Symbol instance') + symbol = symbolname(symbol) if symbol == self.name: return 1 else: @@ -420,6 +407,19 @@ def symbols(names): names = names.replace(',', ' ').split() return (Symbol(name) for name in names) +def symbolname(symbol): + if isinstance(symbol, str): + return symbol.strip() + elif isinstance(symbol, Symbol): + return symbol.name + else: + raise TypeError('symbol must be a string or a Symbol instance') + +def symbolnames(symbols): + if isinstance(symbols, str): + return symbols.replace(',', ' ').split() + return (symbolname(symbol) for symbol in symbols) + class Constant(Expression): @@ -441,10 +441,7 @@ class Constant(Expression): return self._hash def coefficient(self, symbol): - if isinstance(symbol, Symbol): - symbol = symbol.name - elif not isinstance(symbol, str): - raise TypeError('symbol must be a string or a Symbol instance') + symbol = symbolname(symbol) return 0 def coefficients(self): -- 2.20.1 From 2ffea1a47578a1b1d09906d57511062d68e6abea Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 09:00:15 +0200 Subject: [PATCH 13/16] New method Expression.subs --- pypol/_islhelper.c | 2 +- pypol/linexprs.py | 23 +++++++++++++++++++++++ pypol/tests/test_linexprs.py | 12 ++++++++++++ 3 files changed, 36 insertions(+), 1 deletion(-) diff --git a/pypol/_islhelper.c b/pypol/_islhelper.c index bc62968..eaacc67 100644 --- a/pypol/_islhelper.c +++ b/pypol/_islhelper.c @@ -36,7 +36,7 @@ static PyObject * isl_basic_set_constraints(PyObject *self, PyObject* args) { return NULL; } bset = (isl_basic_set *) ptr; - bset = isl_basic_set_finalize(bset); + bset = isl_basic_set_finalize(bset); // this instruction should not be required n = isl_basic_set_n_constraint(bset); if (n == -1) { PyErr_SetString(PyExc_RuntimeError, diff --git a/pypol/linexprs.py b/pypol/linexprs.py index ed68493..b330045 100644 --- a/pypol/linexprs.py +++ b/pypol/linexprs.py @@ -249,6 +249,29 @@ class Expression: return left / right raise SyntaxError('invalid syntax') + def subs(self, symbol, expression=None): + if expression is None: + if isinstance(symbol, dict): + symbol = symbol.items() + substitutions = symbol + else: + substitutions = [(symbol, expression)] + result = self + for symbol, expression in substitutions: + symbol = symbolname(symbol) + result = result._subs(symbol, expression) + return result + + def _subs(self, symbol, expression): + coefficients = {name: coefficient + for name, coefficient in self.coefficients() + if name != symbol} + constant = self.constant + coefficient = self.coefficient(symbol) + result = Expression(coefficients, self.constant) + result += coefficient * expression + return result + _RE_NUM_VAR = re.compile(r'(\d+|\))\s*([^\W\d_]\w*|\()') @classmethod diff --git a/pypol/tests/test_linexprs.py b/pypol/tests/test_linexprs.py index 1606ea0..5862351 100644 --- a/pypol/tests/test_linexprs.py +++ b/pypol/tests/test_linexprs.py @@ -145,6 +145,18 @@ class TestExpression(unittest.TestCase): self.assertEqual((self.x + self.y/2 + self.z/3)._toint(), 6*self.x + 3*self.y + 2*self.z) + def test_subs(self): + self.assertEqual(self.x.subs('x', 3), 3) + self.assertEqual(self.x.subs('x', self.x), self.x) + self.assertEqual(self.x.subs('x', self.y), self.y) + self.assertEqual(self.x.subs('x', self.x + self.y), self.x + self.y) + self.assertEqual(self.x.subs('y', 3), self.x) + self.assertEqual(self.pi.subs('x', 3), self.pi) + self.assertEqual(self.expr.subs('x', -3), -2 * self.y) + self.assertEqual(self.expr.subs([('x', self.y), ('y', self.x)]), 3 - self.x) + self.assertEqual(self.expr.subs({'x': self.y, 'y': self.x}), 3 - self.x) + self.assertEqual(self.expr.subs({self.x: self.y, self.y: self.x}), 3 - self.x) + def test_fromstring(self): self.assertEqual(Expression.fromstring('x'), self.x) self.assertEqual(Expression.fromstring('-x'), -self.x) -- 2.20.1 From b7d06b55d601833b4bef47afd732334ed77587fb Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 09:08:56 +0200 Subject: [PATCH 14/16] Fix tests for Expression.subs --- pypol/tests/test_linexprs.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/pypol/tests/test_linexprs.py b/pypol/tests/test_linexprs.py index 5862351..a3e81b0 100644 --- a/pypol/tests/test_linexprs.py +++ b/pypol/tests/test_linexprs.py @@ -155,7 +155,7 @@ class TestExpression(unittest.TestCase): self.assertEqual(self.expr.subs('x', -3), -2 * self.y) self.assertEqual(self.expr.subs([('x', self.y), ('y', self.x)]), 3 - self.x) self.assertEqual(self.expr.subs({'x': self.y, 'y': self.x}), 3 - self.x) - self.assertEqual(self.expr.subs({self.x: self.y, self.y: self.x}), 3 - self.x) + self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}), -self.z + 3) def test_fromstring(self): self.assertEqual(Expression.fromstring('x'), self.x) -- 2.20.1 From e27fd6a18fd36b8ec81f37cd800399703bf7ef4f Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 09:24:23 +0200 Subject: [PATCH 15/16] Helper module for sympy in unitary tests --- pypol/tests/libhelper.py | 20 ++++++++++++++++++++ pypol/tests/test_linexprs.py | 32 +++++++++++--------------------- pypol/tests/test_polyhedra.py | 22 +++++----------------- 3 files changed, 36 insertions(+), 38 deletions(-) create mode 100644 pypol/tests/libhelper.py diff --git a/pypol/tests/libhelper.py b/pypol/tests/libhelper.py new file mode 100644 index 0000000..e75b4fb --- /dev/null +++ b/pypol/tests/libhelper.py @@ -0,0 +1,20 @@ +import functools +import unittest + +try: + + import sympy + + def requires_sympy(func): + @functools.wraps(func) + def wrapper(self): + return func(self) + return wrapper + +except ImportError: + + def requires_sympy(func): + @functools.wraps(func) + def wrapper(self): + raise unittest.SkipTest('SymPy is not available') + return wrapper diff --git a/pypol/tests/test_linexprs.py b/pypol/tests/test_linexprs.py index a3e81b0..bc062b6 100644 --- a/pypol/tests/test_linexprs.py +++ b/pypol/tests/test_linexprs.py @@ -4,21 +4,7 @@ import unittest from fractions import Fraction from ..linexprs import * - - -try: - import sympy - def _requires_sympy(func): - @functools.wraps(func) - def wrapper(self): - return func(self) - return wrapper -except ImportError: - def _requires_sympy(func): - @functools.wraps(func) - def wrapper(self): - raise unittest.SkipTest('SymPy is not available') - return wrapper +from .libhelper import requires_sympy class TestExpression(unittest.TestCase): @@ -154,8 +140,8 @@ class TestExpression(unittest.TestCase): self.assertEqual(self.pi.subs('x', 3), self.pi) self.assertEqual(self.expr.subs('x', -3), -2 * self.y) self.assertEqual(self.expr.subs([('x', self.y), ('y', self.x)]), 3 - self.x) - self.assertEqual(self.expr.subs({'x': self.y, 'y': self.x}), 3 - self.x) - self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}), -self.z + 3) + self.assertEqual(self.expr.subs({'x': self.z, 'y': self.z}), 3 - self.z) + self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}), 3 - self.z) def test_fromstring(self): self.assertEqual(Expression.fromstring('x'), self.x) @@ -179,8 +165,9 @@ class TestExpression(unittest.TestCase): self.assertEqual(repr(self.x + self.one), "Expression('x + 1')") self.assertEqual(repr(self.expr), "Expression('x - 2*y + 3')") - @_requires_sympy + @requires_sympy def test_fromsympy(self): + import sympy sp_x, sp_y = sympy.symbols('x y') self.assertEqual(Expression.fromsympy(sp_x), self.x) self.assertEqual(Expression.fromsympy(sympy.Rational(22, 7)), self.pi) @@ -188,8 +175,9 @@ class TestExpression(unittest.TestCase): with self.assertRaises(ValueError): Expression.fromsympy(sp_x*sp_y) - @_requires_sympy + @requires_sympy def test_tosympy(self): + import sympy sp_x, sp_y = sympy.symbols('x y') self.assertEqual(self.x.tosympy(), sp_x) self.assertEqual(self.pi.tosympy(), sympy.Rational(22, 7)) @@ -225,8 +213,9 @@ class TestSymbol(unittest.TestCase): def test_repr(self): self.assertEqual(repr(self.x), "Symbol('x')") - @_requires_sympy + @requires_sympy def test_fromsympy(self): + import sympy sp_x = sympy.Symbol('x') self.assertEqual(Symbol.fromsympy(sp_x), self.x) with self.assertRaises(TypeError): @@ -274,8 +263,9 @@ class TestConstant(unittest.TestCase): self.assertEqual(repr(self.one), 'Constant(1)') self.assertEqual(repr(self.pi), 'Constant(22, 7)') - @_requires_sympy + @requires_sympy def test_fromsympy(self): + import sympy self.assertEqual(Constant.fromsympy(sympy.Rational(22, 7)), self.pi) with self.assertRaises(TypeError): Constant.fromsympy(sympy.Symbol('x')) diff --git a/pypol/tests/test_polyhedra.py b/pypol/tests/test_polyhedra.py index c74e25f..c7a58a4 100644 --- a/pypol/tests/test_polyhedra.py +++ b/pypol/tests/test_polyhedra.py @@ -3,21 +3,7 @@ import unittest from ..linexprs import symbols from ..polyhedra import * - - -try: - import sympy - def _requires_sympy(func): - @functools.wraps(func) - def wrapper(self): - return func(self) - return wrapper -except ImportError: - def _requires_sympy(func): - @functools.wraps(func) - def wrapper(self): - raise unittest.SkipTest('SymPy is not available') - return wrapper +from .libhelper import requires_sympy class TestPolyhedron(unittest.TestCase): @@ -50,14 +36,16 @@ class TestPolyhedron(unittest.TestCase): def test_isuniverse(self): self.assertFalse(self.square.isuniverse()) - @_requires_sympy + @requires_sympy def test_fromsympy(self): + import sympy sp_x, sp_y = sympy.symbols('x y') self.assertEqual(Polyhedron.fromsympy((sp_x >= 0) & (sp_x <= 1) & (sp_y >= 0) & (sp_y <= 1)), self.square) - @_requires_sympy + @requires_sympy def test_tosympy(self): + import sympy sp_x, sp_y = sympy.symbols('x y') self.assertEqual(self.square.tosympy(), sympy.And(-sp_x + 1 >= 0, -sp_y + 1 >= 0, sp_x >= 0, sp_y >= 0)) -- 2.20.1 From f2561050230a9c56f842acb698853f6998528aaa Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Wed, 2 Jul 2014 10:25:55 +0200 Subject: [PATCH 16/16] Make symbolnames return a tuple --- pypol/linexprs.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/pypol/linexprs.py b/pypol/linexprs.py index b330045..10daf9d 100644 --- a/pypol/linexprs.py +++ b/pypol/linexprs.py @@ -441,7 +441,7 @@ def symbolname(symbol): def symbolnames(symbols): if isinstance(symbols, str): return symbols.replace(',', ' ').split() - return (symbolname(symbol) for symbol in symbols) + return tuple(symbolname(symbol) for symbol in symbols) class Constant(Expression): -- 2.20.1