5 from . import islhelper
7 from .islhelper
import mainctx
, libisl
, isl_set_basic_sets
8 from .linexprs
import Expression
, Symbol
17 @functools.total_ordering
26 def __new__(cls
, *polyhedra
):
27 from .polyhedra
import Polyhedron
28 if len(polyhedra
) == 1:
29 polyhedron
= polyhedra
[0]
30 if isinstance(polyhedron
, str):
31 return cls
.fromstring(polyhedron
)
32 elif isinstance(polyhedron
, Polyhedron
):
35 raise TypeError('argument must be a string '
36 'or a Polyhedron instance')
38 for polyhedron
in polyhedra
:
39 if not isinstance(polyhedron
, Polyhedron
):
40 raise TypeError('arguments must be Polyhedron instances')
41 symbols
= cls
._xsymbols
(polyhedra
)
42 islset
= cls
._toislset
(polyhedra
, symbols
)
43 return cls
._fromislset
(islset
, symbols
)
46 def _xsymbols(cls
, iterator
):
48 Return the ordered tuple of symbols present in iterator.
52 symbols
.update(item
.symbols
)
53 return tuple(sorted(symbols
, key
=Symbol
.sortkey
))
57 return self
._polyhedra
65 return self
._dimension
68 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
69 islset
= libisl
.isl_set_make_disjoint(mainctx
, islset
)
70 return self
._fromislset
(islset
, self
.symbols
)
73 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
74 empty
= bool(libisl
.isl_set_is_empty(islset
))
75 libisl
.isl_set_free(islset
)
79 return not self
.isempty()
82 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
83 universe
= bool(libisl
.isl_set_plain_is_universe(islset
))
84 libisl
.isl_set_free(islset
)
88 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
89 bounded
= bool(libisl
.isl_set_is_bounded(islset
))
90 libisl
.isl_set_free(islset
)
93 def __eq__(self
, other
):
94 symbols
= self
._xsymbols
([self
, other
])
95 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
96 islset2
= other
._toislset
(other
.polyhedra
, symbols
)
97 equal
= bool(libisl
.isl_set_is_equal(islset1
, islset2
))
98 libisl
.isl_set_free(islset1
)
99 libisl
.isl_set_free(islset2
)
102 def isdisjoint(self
, other
):
103 symbols
= self
._xsymbols
([self
, other
])
104 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
105 islset2
= self
._toislset
(other
.polyhedra
, symbols
)
106 equal
= bool(libisl
.isl_set_is_disjoint(islset1
, islset2
))
107 libisl
.isl_set_free(islset1
)
108 libisl
.isl_set_free(islset2
)
111 def issubset(self
, other
):
112 symbols
= self
._xsymbols
([self
, other
])
113 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
114 islset2
= self
._toislset
(other
.polyhedra
, symbols
)
115 equal
= bool(libisl
.isl_set_is_subset(islset1
, islset2
))
116 libisl
.isl_set_free(islset1
)
117 libisl
.isl_set_free(islset2
)
120 def __le__(self
, other
):
121 return self
.issubset(other
)
123 def __lt__(self
, other
):
124 symbols
= self
._xsymbols
([self
, other
])
125 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
126 islset2
= self
._toislset
(other
.polyhedra
, symbols
)
127 equal
= bool(libisl
.isl_set_is_strict_subset(islset1
, islset2
))
128 libisl
.isl_set_free(islset1
)
129 libisl
.isl_set_free(islset2
)
132 def complement(self
):
133 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
134 islset
= libisl
.isl_set_complement(islset
)
135 return self
._fromislset
(islset
, self
.symbols
)
137 def __invert__(self
):
138 return self
.complement()
141 #does not change anything in any of the examples
142 #isl seems to do this naturally
143 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
144 islset
= libisl
.isl_set_remove_redundancies(islset
)
145 return self
._fromislset
(islset
, self
.symbols
)
147 def polyhedral_hull(self
):
148 # several types of hull are available
149 # polyhedral seems to be the more appropriate, to be checked
150 from .polyhedra
import Polyhedron
151 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
152 islbset
= libisl
.isl_set_polyhedral_hull(islset
)
153 return Polyhedron
._fromislbasicset
(islbset
, self
.symbols
)
155 def project_out(self
, dims
):
156 # use to remove certain variables
157 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
159 for index
, symbol
in reversed(list(enumerate(self
.symbols
))):
163 islset
= libisl
.isl_set_project_out(islset
, libisl
.isl_dim_set
, index
+ 1, n
)
166 islset
= libisl
.isl_set_project_out(islset
, libisl
.isl_dim_set
, 0, n
)
167 dims
= [symbol
for symbol
in self
.symbols
if symbol
not in dims
]
168 return Domain
._fromislset
(islset
, dims
)
171 from .polyhedra
import Polyhedron
172 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
173 islbset
= libisl
.isl_set_sample(islset
)
174 return Polyhedron
._fromislbasicset
(islbset
, self
.symbols
)
176 def intersection(self
, *others
):
179 symbols
= self
._xsymbols
((self
,) + others
)
180 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
182 islset2
= other
._toislset
(other
.polyhedra
, symbols
)
183 islset1
= libisl
.isl_set_intersect(islset1
, islset2
)
184 return self
._fromislset
(islset1
, symbols
)
186 def __and__(self
, other
):
187 return self
.intersection(other
)
189 def union(self
, *others
):
192 symbols
= self
._xsymbols
((self
,) + others
)
193 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
195 islset2
= other
._toislset
(other
.polyhedra
, symbols
)
196 islset1
= libisl
.isl_set_union(islset1
, islset2
)
197 return self
._fromislset
(islset1
, symbols
)
199 def __or__(self
, other
):
200 return self
.union(other
)
202 def __add__(self
, other
):
203 return self
.union(other
)
205 def difference(self
, other
):
206 symbols
= self
._xsymbols
([self
, other
])
207 islset1
= self
._toislset
(self
.polyhedra
, symbols
)
208 islset2
= other
._toislset
(other
.polyhedra
, symbols
)
209 islset
= libisl
.isl_set_subtract(islset1
, islset2
)
210 return self
._fromislset
(islset
, symbols
)
212 def __sub__(self
, other
):
213 return self
.difference(other
)
216 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
217 islset
= libisl
.isl_set_lexmin(islset
)
218 return self
._fromislset
(islset
, self
.symbols
)
221 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
222 islset
= libisl
.isl_set_lexmax(islset
)
223 return self
._fromislset
(islset
, self
.symbols
)
225 def num_parameters(self
):
226 #could be useful with large, complicated polyhedrons
227 islbset
= self
._toislbasicset
(self
.equalities
, self
.inequalities
, self
.symbols
)
228 num
= libisl
.isl_basic_set_dim(islbset
, libisl
.isl_dim_set
)
231 def involves_dims(self
, dims
):
232 #could be useful with large, complicated polyhedrons
233 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
235 symbols
= sorted(list(self
.symbols
))
240 first
= symbols
.index(dims
[0])
246 value
= bool(libisl
.isl_set_involves_dims(islset
, libisl
.isl_dim_set
, first
, n
))
247 libisl
.isl_set_free(islset
)
252 islbset
= self
._toislbasicset
(self
.equalities
, self
.inequalities
, self
.symbols
)
253 vertices
= libisl
.isl_basic_set_compute_vertices(islbset
);
254 vertexes
= islhelper
.isl_vertices_vertices(vertices
)
255 #vertex = libisl.isl_vertices_get_n_vertices(vertices)
256 for verts
in vertexes
:
257 expr
= libisl
.isl_vertex_get_expr(verts
);
258 this
= islhelper
.isl_set_to_str(expr
)
261 raise TypeError('set must be bounded')
267 symbols
= self
.symbols
269 islset
= self
._toislset
(self
.polyhedra
, self
.symbols
)
270 points
= islhelper
.isl_set_points(islset
)
273 coordinate
= libisl
.isl_point_get_coordinate_val(point
, libisl
.isl_dim_set
, symbols
.index(sym
))
274 coordinate
= islhelper
.isl_val_to_int(coordinate
)
275 coordinates
.append(coordinate
)
277 raise TypeError('set must be bounded')
281 def _fromislset(cls
, islset
, symbols
):
282 from .polyhedra
import Polyhedron
283 islset
= libisl
.isl_set_remove_divs(islset
)
284 islbsets
= isl_set_basic_sets(islset
)
285 libisl
.isl_set_free(islset
)
287 for islbset
in islbsets
:
288 polyhedron
= Polyhedron
._fromislbasicset
(islbset
, symbols
)
289 polyhedra
.append(polyhedron
)
290 if len(polyhedra
) == 0:
291 from .polyhedra
import Empty
293 elif len(polyhedra
) == 1:
296 self
= object().__new
__(Domain
)
297 self
._polyhedra
= tuple(polyhedra
)
298 self
._symbols
= cls
._xsymbols
(polyhedra
)
299 self
._dimension
= len(self
._symbols
)
302 def _toislset(cls
, polyhedra
, symbols
):
303 polyhedron
= polyhedra
[0]
304 islbset
= polyhedron
._toislbasicset
(polyhedron
.equalities
,
305 polyhedron
.inequalities
, symbols
)
306 islset1
= libisl
.isl_set_from_basic_set(islbset
)
307 for polyhedron
in polyhedra
[1:]:
308 islbset
= polyhedron
._toislbasicset
(polyhedron
.equalities
,
309 polyhedron
.inequalities
, symbols
)
310 islset2
= libisl
.isl_set_from_basic_set(islbset
)
311 islset1
= libisl
.isl_set_union(islset1
, islset2
)
315 def _fromast(cls
, node
):
316 from .polyhedra
import Polyhedron
317 if isinstance(node
, ast
.Module
) and len(node
.body
) == 1:
318 return cls
._fromast
(node
.body
[0])
319 elif isinstance(node
, ast
.Expr
):
320 return cls
._fromast
(node
.value
)
321 elif isinstance(node
, ast
.UnaryOp
):
322 domain
= cls
._fromast
(node
.operand
)
323 if isinstance(node
.operand
, ast
.invert
):
325 elif isinstance(node
, ast
.BinOp
):
326 domain1
= cls
._fromast
(node
.left
)
327 domain2
= cls
._fromast
(node
.right
)
328 if isinstance(node
.op
, ast
.BitAnd
):
329 return And(domain1
, domain2
)
330 elif isinstance(node
.op
, ast
.BitOr
):
331 return Or(domain1
, domain2
)
332 elif isinstance(node
, ast
.Compare
):
335 left
= Expression
._fromast
(node
.left
)
336 for i
in range(len(node
.ops
)):
338 right
= Expression
._fromast
(node
.comparators
[i
])
339 if isinstance(op
, ast
.Lt
):
340 inequalities
.append(right
- left
- 1)
341 elif isinstance(op
, ast
.LtE
):
342 inequalities
.append(right
- left
)
343 elif isinstance(op
, ast
.Eq
):
344 equalities
.append(left
- right
)
345 elif isinstance(op
, ast
.GtE
):
346 inequalities
.append(left
- right
)
347 elif isinstance(op
, ast
.Gt
):
348 inequalities
.append(left
- right
- 1)
353 return Polyhedron(equalities
, inequalities
)
354 raise SyntaxError('invalid syntax')
356 _RE_BRACES
= re
.compile(r
'^\{\s*|\s*\}$')
357 _RE_EQ
= re
.compile(r
'([^<=>])=([^<=>])')
358 _RE_AND
= re
.compile(r
'\band\b|,|&&|/\\|∧|∩')
359 _RE_OR
= re
.compile(r
'\bor\b|;|\|\||\\/|∨|∪')
360 _RE_NOT
= re
.compile(r
'\bnot\b|!|¬')
361 _RE_NUM_VAR
= Expression
._RE
_NUM
_VAR
362 _RE_OPERATORS
= re
.compile(r
'(&|\||~)')
365 def fromstring(cls
, string
):
366 # remove curly brackets
367 string
= cls
._RE
_BRACES
.sub(r
'', string
)
368 # replace '=' by '=='
369 string
= cls
._RE
_EQ
.sub(r
'\1==\2', string
)
370 # replace 'and', 'or', 'not'
371 string
= cls
._RE
_AND
.sub(r
' & ', string
)
372 string
= cls
._RE
_OR
.sub(r
' | ', string
)
373 string
= cls
._RE
_NOT
.sub(r
' ~', string
)
374 # add implicit multiplication operators, e.g. '5x' -> '5*x'
375 string
= cls
._RE
_NUM
_VAR
.sub(r
'\1*\2', string
)
376 # add parentheses to force precedence
377 tokens
= cls
._RE
_OPERATORS
.split(string
)
378 for i
, token
in enumerate(tokens
):
380 token
= '({})'.format(token
)
382 string
= ''.join(tokens
)
383 tree
= ast
.parse(string
, 'eval')
384 return cls
._fromast
(tree
)
387 assert len(self
.polyhedra
) >= 2
388 strings
= [repr(polyhedron
) for polyhedron
in self
.polyhedra
]
389 return 'Or({})'.format(', '.join(strings
))
392 def fromsympy(cls
, expr
):
394 from .polyhedra
import Lt
, Le
, Eq
, Ne
, Ge
, Gt
396 sympy
.And
: And
, sympy
.Or
: Or
, sympy
.Not
: Not
,
397 sympy
.Lt
: Lt
, sympy
.Le
: Le
,
398 sympy
.Eq
: Eq
, sympy
.Ne
: Ne
,
399 sympy
.Ge
: Ge
, sympy
.Gt
: Gt
,
401 if expr
.func
in funcmap
:
402 args
= [Domain
.fromsympy(arg
) for arg
in expr
.args
]
403 return funcmap
[expr
.func
](*args
)
404 elif isinstance(expr
, sympy
.Expr
):
405 return Expression
.fromsympy(expr
)
406 raise ValueError('non-domain expression: {!r}'.format(expr
))
410 polyhedra
= [polyhedron
.tosympy() for polyhedron
in polyhedra
]
411 return sympy
.Or(*polyhedra
)
415 if len(domains
) == 0:
416 from .polyhedra
import Universe
419 return domains
[0].intersection(*domains
[1:])
422 if len(domains
) == 0:
423 from .polyhedra
import Empty
426 return domains
[0].union(*domains
[1:])