pypol/domains.py

   1 import functools
   2
   3 from . import islhelper
   4
   5 from .islhelper import mainctx, libisl, isl_set_basic_sets
   6
   7
   8 __all__ = [
   9     'Domain',
  10     'And', 'Or', 'Not',
  11 ]
  12
  13
  14 @functools.total_ordering
  15 class Domain:
  16
  17     __slots__ = (
  18         '_polyhedra',
  19         '_symbols',
  20         '_dimension',
  21     )
  22
  23     def __new__(cls, *polyhedra):
  24         from .polyhedra import Polyhedron
  25         if len(polyhedra) == 1:
  26             polyhedron = polyhedra[0]
  27             if isinstance(polyhedron, str):
  28                 return cls.fromstring(polyhedron)
  29             elif isinstance(polyhedron, Polyhedron):
  30                 return polyhedron
  31             else:
  32                 raise TypeError('argument must be a string '
  33                     'or a Polyhedron instance')
  34         else:
  35             for polyhedron in polyhedra:
  36                 if not isinstance(polyhedron, Polyhedron):
  37                     raise TypeError('arguments must be Polyhedron instances')
  38             symbols = cls._xsymbols(polyhedra)
  39             islset = cls._toislset(polyhedra, symbols)
  40             return cls._fromislset(islset, symbols)
  41
  42     @classmethod
  43     def _xsymbols(cls, iterator):
  44         """
  45         Return the ordered tuple of symbols present in iterator.
  46         """
  47         symbols = set()
  48         for item in iterator:
  49             symbols.update(item.symbols)
  50         return tuple(sorted(symbols))
  51
  52     @property
  53     def polyhedra(self):
  54         return self._polyhedra
  55
  56     @property
  57     def symbols(self):
  58         return self._symbols
  59
  60     @property
  61     def dimension(self):
  62         return self._dimension
  63
  64     def disjoint(self):
  65         islset = self._toislset(self.polyhedra, self.symbols)
  66         islset = libisl.isl_set_make_disjoint(mainctx, islset)
  67         return self._fromislset(islset, self.symbols)
  68
  69     def isempty(self):
  70         islset = self._toislset(self.polyhedra, self.symbols)
  71         empty = bool(libisl.isl_set_is_empty(islset))
  72         libisl.isl_set_free(islset)
  73         return empty
  74
  75     def __bool__(self):
  76         return not self.isempty()
  77
  78     def isuniverse(self):
  79         islset = self._toislset(self.polyhedra, self.symbols)
  80         universe = bool(libisl.isl_set_plain_is_universe(islset))
  81         libisl.isl_set_free(islset)
  82         return universe
  83
  84     def isbounded(self):
  85         islset = self._toislset(self.polyhedra, self.symbols)
  86         bounded = bool(libisl.isl_set_is_bounded(islset))
  87         libisl.isl_set_free(islset)
  88         return bounded
  89
  90     def __eq__(self, other):
  91         symbols = self._xsymbols([self, other])
  92         islset1 = self._toislset(self.polyhedra, symbols)
  93         islset2 = other._toislset(other.polyhedra, symbols)
  94         equal = bool(libisl.isl_set_is_equal(islset1, islset2))
  95         libisl.isl_set_free(islset1)
  96         libisl.isl_set_free(islset2)
  97         return equal
  98
  99     def isdisjoint(self, other):
 100         symbols = self._xsymbols([self, other])
 101         islset1 = self._toislset(self.polyhedra, symbols)
 102         islset2 = self._toislset(other.polyhedra, symbols)
 103         equal = bool(libisl.isl_set_is_disjoint(islset1, islset2))
 104         libisl.isl_set_free(islset1)
 105         libisl.isl_set_free(islset2)
 106         return equal
 107
 108     def issubset(self, other):
 109         symbols = self._xsymbols([self, other])
 110         islset1 = self._toislset(self.polyhedra, symbols)
 111         islset2 = self._toislset(other.polyhedra, symbols)
 112         equal = bool(libisl.isl_set_is_subset(islset1, islset2))
 113         libisl.isl_set_free(islset1)
 114         libisl.isl_set_free(islset2)
 115         return equal
 116
 117     def __le__(self, other):
 118         return self.issubset(other)
 119
 120     def __lt__(self, other):
 121         symbols = self._xsymbols([self, other])
 122         islset1 = self._toislset(self.polyhedra, symbols)
 123         islset2 = self._toislset(other.polyhedra, symbols)
 124         equal = bool(libisl.isl_set_is_strict_subset(islset1, islset2))
 125         libisl.isl_set_free(islset1)
 126         libisl.isl_set_free(islset2)
 127         return equal
 128
 129     def complement(self):
 130         islset = self._toislset(self.polyhedra, self.symbols)
 131         islset = libisl.isl_set_complement(islset)
 132         return self._fromislset(islset, self.symbols)
 133
 134     def __invert__(self):
 135         return self.complement()
 136
 137     def simplify(self):
 138         # see isl_set_coalesce, isl_set_detect_equalities,
 139         # isl_set_remove_redundancies
 140         # which ones? in which order?
 141         raise NotImplementedError
 142
 143     def polyhedral_hull(self):
 144         # several types of hull are available
 145         # polyhedral seems to be the more appropriate, to be checked
 146         from .polyhedra import Polyhedron
 147         islset = self._toislset(self.polyhedra, self.symbols)
 148         islbset = libisl.isl_set_polyhedral_hull(islset)
 149         return Polyhedron._fromislbasicset(islbset, self.symbols)
 150
 151     def project(self, symbols):
 152         # not sure what isl_set_project_out actually does…
 153         # use isl_set_drop_constraints_involving_dims instead?
 154         raise NotImplementedError
 155
 156     def sample(self):
 157         from .polyhedra import Polyhedron
 158         islset = self._toislset(self.polyhedra, self.symbols)
 159         islbset = libisl.isl_set_sample(islset)
 160         return Polyhedron._fromislbasicset(islbset, self.symbols)
 161
 162     def intersection(self, *others):
 163         if len(others) == 0:
 164             return self
 165         symbols = self._xsymbols((self,) + others)
 166         islset1 = self._toislset(self.polyhedra, symbols)
 167         for other in others:
 168             islset2 = other._toislset(other.polyhedra, symbols)
 169             islset1 = libisl.isl_set_intersect(islset1, islset2)
 170         return self._fromislset(islset1, symbols)
 171
 172     def __and__(self, other):
 173         return self.intersection(other)
 174
 175     def union(self, *others):
 176         if len(others) == 0:
 177             return self
 178         symbols = self._xsymbols((self,) + others)
 179         islset1 = self._toislset(self.polyhedra, symbols)
 180         for other in others:
 181             islset2 = other._toislset(other.polyhedra, symbols)
 182             islset1 = libisl.isl_set_union(islset1, islset2)
 183         return self._fromislset(islset1, symbols)
 184
 185     def __or__(self, other):
 186         return self.union(other)
 187
 188     def __add__(self, other):
 189         return self.union(other)
 190
 191     def difference(self, other):
 192         symbols = self._xsymbols([self, other])
 193         islset1 = self._toislset(self.polyhedra, symbols)
 194         islset2 = other._toislset(other.polyhedra, symbols)
 195         islset = libisl.isl_set_subtract(islset1, islset2)
 196         return self._fromislset(islset, symbols)
 197
 198     def __sub__(self, other):
 199         return self.difference(other)
 200
 201     def lexmin(self):
 202         islset = self._toislset(self.polyhedra, self.symbols)
 203         islset = libisl.isl_set_lexmin(islset)
 204         return self._fromislset(islset, self.symbols)
 205
 206     def lexmax(self):
 207         islset = self._toislset(self.polyhedra, self.symbols)
 208         islset = libisl.isl_set_lexmax(islset)
 209         return self._fromislset(islset, self.symbols)
 210
 211     @classmethod
 212     def _fromislset(cls, islset, symbols):
 213         from .polyhedra import Polyhedron
 214         islset = libisl.isl_set_remove_divs(islset)
 215         islbsets = isl_set_basic_sets(islset)
 216         libisl.isl_set_free(islset)
 217         polyhedra = []
 218         for islbset in islbsets:
 219             polyhedron = Polyhedron._fromislbasicset(islbset, symbols)
 220             polyhedra.append(polyhedron)
 221         if len(polyhedra) == 0:
 222             from .polyhedra import Empty
 223             return Empty
 224         elif len(polyhedra) == 1:
 225             return polyhedra[0]
 226         else:
 227             self = object().__new__(Domain)
 228             self._polyhedra = tuple(polyhedra)
 229             self._symbols = cls._xsymbols(polyhedra)
 230             self._dimension = len(self._symbols)
 231             return self
 232
 233     def _toislset(cls, polyhedra, symbols):
 234         polyhedron = polyhedra[0]
 235         islbset = polyhedron._toislbasicset(polyhedron.equalities,
 236             polyhedron.inequalities, symbols)
 237         islset1 = libisl.isl_set_from_basic_set(islbset)
 238         for polyhedron in polyhedra[1:]:
 239             islbset = polyhedron._toislbasicset(polyhedron.equalities,
 240                 polyhedron.inequalities, symbols)
 241             islset2 = libisl.isl_set_from_basic_set(islbset)
 242             islset1 = libisl.isl_set_union(islset1, islset2)
 243         return islset1
 244
 245     @classmethod
 246     def fromstring(cls, string):
 247         raise NotImplementedError
 248
 249     def __repr__(self):
 250         assert len(self.polyhedra) >= 2
 251         strings = [repr(polyhedron) for polyhedron in self.polyhedra]
 252         return 'Or({})'.format(', '.join(strings))
 253
 254     @classmethod
 255     def fromsympy(cls, expr):
 256         raise NotImplementedError
 257
 258     def tosympy(self):
 259         raise NotImplementedError
 260
 261
 262 def And(*domains):
 263     if len(domains) == 0:
 264         from .polyhedra import Universe
 265         return Universe
 266     else:
 267         return domains[0].intersection(*domains[1:])
 268
 269 def Or(*domains):
 270     if len(domains) == 0:
 271         from .polyhedra import Empty
 272         return Empty
 273     else:
 274         return domains[0].union(*domains[1:])
 275
 276 def Not(domain):
 277     return ~domain