X-Git-Url: https://scm.cri.mines-paristech.fr/git/linpy.git/blobdiff_plain/841943174bb4d3b602e8e055592d8b54d1bb086d..bec8e9379d875b91dd49058aeae0075bda66d6d8:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 5b5d8aa..5dfddfe 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,9 +1,14 @@ - import functools import numbers +import json +import ctypes, ctypes.util +from pypol import isl from fractions import Fraction, gcd +libisl = ctypes.CDLL(ctypes.util.find_library('isl')) + +libisl.isl_printer_get_str.restype = ctypes.c_char_p __all__ = [ 'Expression', @@ -13,6 +18,75 @@ __all__ = [ 'empty', 'universe' ] +''' +def symbolToInt(self): + make dictionary of key:value (letter:integer) + iterate through the dictionary to find matching symbol + return the given integer value + d = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 6, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, + 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26} + if self in d: + num = d.get(self) + return num +''' + +ids = {} + +def get_ids(co): + if co in ids: + return ids.get(co) + else: + idd = len(ids) + ids[co] = idd + print(ids) + return idd + +def _polymorphic_method(func): + @functools.wraps(func) + def wrapper(a, b): + if isinstance(b, Expression): + return func(a, b) + if isinstance(b, numbers.Rational): + b = constant(b) + return func(a, b) + return NotImplemented + return wrapper + +def _polymorphic_operator(func): + # A polymorphic operator should call a polymorphic method, hence we just + # have to test the left operand. + @functools.wraps(func) + def wrapper(a, b): + if isinstance(a, numbers.Rational): + a = constant(a) + return func(a, b) + elif isinstance(a, Expression): + return func(a, b) + raise TypeError('arguments must be linear expressions') + return wrapper + +class Context: + + __slots__ = ('_ic') + + def __init__(self): + self._ic = libisl.isl_ctx_alloc() + + @property + def _as_parameter_(self): + return self._ic + + #comment out so does not delete itself after being created + #def __del__(self): + # libisl.isl_ctx_free(self) + + def __eq__(self, other): + if not isinstance(other, Context): + return False + return self._ic == other._ic + + + class Expression: """ @@ -43,6 +117,7 @@ class Expression: self._constant = constant return self + def symbols(self): yield from sorted(self._coefficients) @@ -78,6 +153,12 @@ class Expression: yield self.coefficient(symbol) yield self.constant + def values_int(self): + for symbol in self.symbols(): + return self.coefficient(symbol) + return int(self.constant) + + def symbol(self): if not self.issymbol(): raise ValueError('not a symbol: {}'.format(self)) @@ -96,18 +177,7 @@ class Expression: def __neg__(self): return self * -1 - def _polymorphic(func): - @functools.wraps(func) - def wrapper(self, other): - if isinstance(other, Expression): - return func(self, other) - if isinstance(other, numbers.Rational): - other = Expression(constant=other) - return func(self, other) - return NotImplemented - return wrapper - - @_polymorphic + @_polymorphic_method def __add__(self, other): coefficients = dict(self.coefficients()) for symbol, coefficient in other.coefficients(): @@ -120,7 +190,7 @@ class Expression: __radd__ = __add__ - @_polymorphic + @_polymorphic_method def __sub__(self, other): coefficients = dict(self.coefficients()) for symbol, coefficient in other.coefficients(): @@ -131,9 +201,10 @@ class Expression: constant = self.constant - other.constant return Expression(coefficients, constant) - __rsub__ = __sub__ - - @_polymorphic + def __rsub__(self, other): + return -(self - other) + + @_polymorphic_method def __mul__(self, other): if other.isconstant(): coefficients = dict(self.coefficients()) @@ -148,7 +219,7 @@ class Expression: __rmul__ = __mul__ - @_polymorphic + @_polymorphic_method def __truediv__(self, other): if other.isconstant(): coefficients = dict(self.coefficients()) @@ -163,7 +234,7 @@ class Expression: return NotImplemented def __rtruediv__(self, other): - if isinstance(other, Rational): + if isinstance(other, self): if self.isconstant(): constant = Fraction(other, self.constant) return Expression(constant=constant) @@ -206,6 +277,8 @@ class Expression: elif constant < 0: constant *= -1 string += ' - {}'.format(constant) + if string == '': + string = '0' return string def _parenstr(self, always=False): @@ -228,7 +301,7 @@ class Expression: def fromstring(cls, string): raise NotImplementedError - @_polymorphic + @_polymorphic_method def __eq__(self, other): # "normal" equality # see http://docs.sympy.org/dev/tutorial/gotchas.html#equals-signs @@ -244,29 +317,32 @@ class Expression: [value.denominator for value in self.values()]) return self * lcm - @_polymorphic + @_polymorphic_method def _eq(self, other): return Polyhedron(equalities=[(self - other)._canonify()]) - @_polymorphic + @_polymorphic_method def __le__(self, other): return Polyhedron(inequalities=[(self - other)._canonify()]) - @_polymorphic + @_polymorphic_method def __lt__(self, other): return Polyhedron(inequalities=[(self - other)._canonify() + 1]) - @_polymorphic + @_polymorphic_method def __ge__(self, other): return Polyhedron(inequalities=[(other - self)._canonify()]) - @_polymorphic + @_polymorphic_method def __gt__(self, other): return Polyhedron(inequalities=[(other - self)._canonify() + 1]) def constant(numerator=0, denominator=None): - return Expression(constant=Fraction(numerator, denominator)) + if denominator is None and isinstance(numerator, numbers.Rational): + return Expression(constant=3) + else: + return Expression(constant=Fraction(numerator, denominator)) def symbol(name): if not isinstance(name, str): @@ -279,35 +355,23 @@ def symbols(names): return (symbol(name) for name in names) -def _operator(func): - @functools.wraps(func) - def wrapper(a, b): - if isinstance(a, numbers.Rational): - a = constant(a) - if isinstance(b, numbers.Rational): - b = constant(b) - if isinstance(a, Expression) and isinstance(b, Expression): - return func(a, b) - raise TypeError('arguments must be linear expressions') - return wrapper - -@_operator +@_polymorphic_operator def eq(a, b): return a._eq(b) -@_operator +@_polymorphic_operator def le(a, b): return a <= b -@_operator +@_polymorphic_operator def lt(a, b): return a < b -@_operator +@_polymorphic_operator def ge(a, b): return a >= b -@_operator +@_polymorphic_operator def gt(a, b): return a > b @@ -338,9 +402,16 @@ class Polyhedron: if value.denominator != 1: raise TypeError('non-integer constraint: ' '{} <= 0'.format(constraint)) - self._inequalities.append(constraint) - return self - + self._inequalities.append(constraint) + self._bset = self.to_isl() + #print(self._bset) + #put this here just to test from isl method + #from_isl = self.from_isl(self._bset) + #print(from_isl) + #rint(self) + return self._bset + + @property def equalities(self): yield from self._equalities @@ -348,24 +419,40 @@ class Polyhedron: @property def inequalities(self): yield from self._inequalities + + @property + def constant(self): + return self._constant + + def isconstant(self): + return len(self._coefficients) == 0 + + + def isempty(self): + return bool(libisl.isl_basic_set_is_empty(self._bset)) def constraints(self): yield from self.equalities yield from self.inequalities + def symbols(self): s = set() for constraint in self.constraints(): s.update(constraint.symbols) - yield from sorted(s) - + yield from sorted(s) + @property def dimension(self): return len(self.symbols()) def __bool__(self): # return false if the polyhedron is empty, true otherwise - raise NotImplementedError + if self._equalities or self._inequalities: + return False + else: + return True + def __contains__(self, value): # is the value in the polyhedron? @@ -374,8 +461,8 @@ class Polyhedron: def __eq__(self, other): raise NotImplementedError - def isempty(self): - return self == empty + def is_empty(self): + return def isuniverse(self): return self == universe @@ -395,6 +482,11 @@ class Polyhedron: def issuperset(self, other): # test whether every element in other is in the polyhedron + for value in other: + if value == self.constraints(): + return True + else: + return False raise NotImplementedError def __ge__(self, other): @@ -451,8 +543,58 @@ class Polyhedron: @classmethod def fromstring(cls, string): raise NotImplementedError + + def to_isl(self): + #d = Expression().__dict__ #write expression values to dictionary in form {'_constant': value, '_coefficients': value} + d = {'_constant': 2, '_coefficients': {'b':1}} + coeff = d.get('_coefficients') + num_coefficients = len(coeff) + space = libisl.isl_space_set_alloc(Context(), 0, num_coefficients) + bset = libisl.isl_basic_set_empty(libisl.isl_space_copy(space)) + ls = libisl.isl_local_space_from_space(libisl.isl_space_copy(space)) + ceq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(ls)) + cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls)) + '''if there are equalities/inequalities, take each constant and coefficient and add as a constraint to the basic set + need to change the symbols method to a lookup table for the integer value for each letter that could be a symbol''' + if self._equalities: + if '_constant' in d: + value = d.get('_constant') + ceq = libisl.isl_constraint_set_constant_si(ceq, value) + if '_coefficients' in d: + value_co = d.get('_coefficients') + for co in value_co: + num = value_co.get(co) + ceq = libisl.isl_constraint_set_coefficient_si(ceq, 3, get_ids(co), num) #use 3 for type isl_dim_set + bset = libisl.isl_set_add_constraint(bset, ceq) + + if self._inequalities: + if '_constant' in d: + value = d.get('_constant') + cin = libisl.isl_constraint_set_constant_si(cin, value) + if '_coefficients' in d: + value_co = d.get('_coefficients') + for co in value_co: + num = value_co.get(co) + if value_co: #if dictionary not empty add coefficient as to constraint + cin = libisl.isl_constraint_set_coefficient_si(cin, 3, get_ids(co), num) #use 3 for type isl_dim_set + bset = libisl.isl_set_add_constraint(bset, cin) + ip = libisl.isl_printer_to_str(Context()) #create string printer + ip = libisl.isl_printer_print_set(ip, bset) #print set to printer + string = libisl.isl_printer_get_str(ip) #get string from printer + string = str(string) + print(string) + return string + + + def from_isl(self, bset): + '''takes basic set in isl form and puts back into python version of polyhedron + isl example code gives idl form as: + "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}");''' + + poly = 0 + return poly + +empty = eq(1,1) -empty = le(1, 0) - universe = Polyhedron()