Mention that we use Z-polyhedra
[linpy.git] / linpy / domains.py
1 # Copyright 2014 MINES ParisTech
2 #
3 # This file is part of LinPy.
4 #
5 # LinPy is free software: you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by
7 # the Free Software Foundation, either version 3 of the License, or
8 # (at your option) any later version.
9 #
10 # LinPy is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
14 #
15 # You should have received a copy of the GNU General Public License
16 # along with LinPy. If not, see <http://www.gnu.org/licenses/>.
17
18 import ast
19 import functools
20 import re
21 import math
22
23 from fractions import Fraction
24
25 from . import islhelper
26 from .islhelper import mainctx, libisl
27 from .linexprs import LinExpr, Symbol
28 from .geometry import GeometricObject, Point, Vector
29
30
31 __all__ = [
32 'Domain',
33 'And', 'Or', 'Not',
34 ]
35
36
37 @functools.total_ordering
38 class Domain(GeometricObject):
39 """
40 A domain is a union of polyhedra. Unlike polyhedra, domains allow exact
41 computation of union, subtraction and complementary operations.
42
43 A domain with a unique polyhedron is automatically subclassed as a
44 Polyhedron instance.
45 """
46
47 __slots__ = (
48 '_polyhedra',
49 '_symbols',
50 '_dimension',
51 )
52
53 def __new__(cls, *polyhedra):
54 """
55 Return a domain from a sequence of polyhedra.
56
57 >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
58 >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
59 >>> dom = Domain(square1, square2)
60 >>> dom
61 Or(And(x <= 2, 0 <= x, y <= 2, 0 <= y),
62 And(x <= 3, 1 <= x, y <= 3, 1 <= y))
63
64 It is also possible to build domains from polyhedra using arithmetic
65 operators Domain.__or__(), Domain.__invert__() or functions Or() and
66 Not(), using one of the following instructions:
67
68 >>> dom = square1 | square2
69 >>> dom = Or(square1, square2)
70
71 Alternatively, a domain can be built from a string:
72
73 >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 1 <= x <= 3, 1 <= y <= 3')
74
75 Finally, a domain can be built from a GeometricObject instance, calling
76 the GeometricObject.asdomain() method.
77 """
78 from .polyhedra import Polyhedron
79 if len(polyhedra) == 1:
80 argument = polyhedra[0]
81 if isinstance(argument, str):
82 return cls.fromstring(argument)
83 elif isinstance(argument, GeometricObject):
84 return argument.aspolyhedron()
85 else:
86 raise TypeError('argument must be a string '
87 'or a GeometricObject instance')
88 else:
89 for polyhedron in polyhedra:
90 if not isinstance(polyhedron, Polyhedron):
91 raise TypeError('arguments must be Polyhedron instances')
92 symbols = cls._xsymbols(polyhedra)
93 islset = cls._toislset(polyhedra, symbols)
94 return cls._fromislset(islset, symbols)
95
96 @classmethod
97 def _xsymbols(cls, iterator):
98 """
99 Return the ordered tuple of symbols present in iterator.
100 """
101 symbols = set()
102 for item in iterator:
103 symbols.update(item.symbols)
104 return tuple(sorted(symbols, key=Symbol.sortkey))
105
106 @property
107 def polyhedra(self):
108 """
109 The tuple of polyhedra present in the domain.
110 """
111 return self._polyhedra
112
113 @property
114 def symbols(self):
115 """
116 The tuple of symbols present in the domain equations, sorted according
117 to Symbol.sortkey().
118 """
119 return self._symbols
120
121 @property
122 def dimension(self):
123 """
124 The dimension of the domain, i.e. the number of symbols present in it.
125 """
126 return self._dimension
127
128 def isempty(self):
129 """
130 Return True if the domain is empty, that is, equal to Empty.
131 """
132 islset = self._toislset(self.polyhedra, self.symbols)
133 empty = bool(libisl.isl_set_is_empty(islset))
134 libisl.isl_set_free(islset)
135 return empty
136
137 def __bool__(self):
138 """
139 Return True if the domain is non-empty.
140 """
141 return not self.isempty()
142
143 def isuniverse(self):
144 """
145 Return True if the domain is universal, that is, equal to Universe.
146 """
147 islset = self._toislset(self.polyhedra, self.symbols)
148 universe = bool(libisl.isl_set_plain_is_universe(islset))
149 libisl.isl_set_free(islset)
150 return universe
151
152 def isbounded(self):
153 """
154 Return True if the domain is bounded.
155 """
156 islset = self._toislset(self.polyhedra, self.symbols)
157 bounded = bool(libisl.isl_set_is_bounded(islset))
158 libisl.isl_set_free(islset)
159 return bounded
160
161 def __eq__(self, other):
162 """
163 Return True if two domains are equal.
164 """
165 if isinstance(other, Domain):
166 symbols = self._xsymbols([self, other])
167 islset1 = self._toislset(self.polyhedra, symbols)
168 islset2 = other._toislset(other.polyhedra, symbols)
169 equal = bool(libisl.isl_set_is_equal(islset1, islset2))
170 libisl.isl_set_free(islset1)
171 libisl.isl_set_free(islset2)
172 return equal
173 return NotImplemented
174
175 def isdisjoint(self, other):
176 """
177 Return True if two domains have a null intersection.
178 """
179 if not isinstance(other, Domain):
180 raise TypeError('other must be a Domain instance')
181 symbols = self._xsymbols([self, other])
182 islset1 = self._toislset(self.polyhedra, symbols)
183 islset2 = self._toislset(other.polyhedra, symbols)
184 equal = bool(libisl.isl_set_is_disjoint(islset1, islset2))
185 libisl.isl_set_free(islset1)
186 libisl.isl_set_free(islset2)
187 return equal
188
189 def issubset(self, other):
190 """
191 Report whether another domain contains the domain.
192 """
193 return self < other
194
195 def __le__(self, other):
196 if isinstance(other, Domain):
197 symbols = self._xsymbols([self, other])
198 islset1 = self._toislset(self.polyhedra, symbols)
199 islset2 = self._toislset(other.polyhedra, symbols)
200 equal = bool(libisl.isl_set_is_subset(islset1, islset2))
201 libisl.isl_set_free(islset1)
202 libisl.isl_set_free(islset2)
203 return equal
204 return NotImplemented
205 __le__.__doc__ = issubset.__doc__
206
207 def __lt__(self, other):
208 """
209 Report whether another domain is contained within the domain.
210 """
211 if isinstance(other, Domain):
212 symbols = self._xsymbols([self, other])
213 islset1 = self._toislset(self.polyhedra, symbols)
214 islset2 = self._toislset(other.polyhedra, symbols)
215 equal = bool(libisl.isl_set_is_strict_subset(islset1, islset2))
216 libisl.isl_set_free(islset1)
217 libisl.isl_set_free(islset2)
218 return equal
219 return NotImplemented
220
221 def complement(self):
222 """
223 Return the complementary domain of the domain.
224 """
225 islset = self._toislset(self.polyhedra, self.symbols)
226 islset = libisl.isl_set_complement(islset)
227 return self._fromislset(islset, self.symbols)
228
229 def __invert__(self):
230 return self.complement()
231 __invert__.__doc__ = complement.__doc__
232
233 def make_disjoint(self):
234 """
235 Return an equivalent domain, whose polyhedra are disjoint.
236 """
237 islset = self._toislset(self.polyhedra, self.symbols)
238 islset = libisl.isl_set_make_disjoint(mainctx, islset)
239 return self._fromislset(islset, self.symbols)
240
241 def coalesce(self):
242 """
243 Simplify the representation of the domain by trying to combine pairs of
244 polyhedra into a single polyhedron, and return the resulting domain.
245 """
246 islset = self._toislset(self.polyhedra, self.symbols)
247 islset = libisl.isl_set_coalesce(islset)
248 return self._fromislset(islset, self.symbols)
249
250 def detect_equalities(self):
251 """
252 Simplify the representation of the domain by detecting implicit
253 equalities, and return the resulting domain.
254 """
255 islset = self._toislset(self.polyhedra, self.symbols)
256 islset = libisl.isl_set_detect_equalities(islset)
257 return self._fromislset(islset, self.symbols)
258
259 def remove_redundancies(self):
260 """
261 Remove redundant constraints in the domain, and return the resulting
262 domain.
263 """
264 islset = self._toislset(self.polyhedra, self.symbols)
265 islset = libisl.isl_set_remove_redundancies(islset)
266 return self._fromislset(islset, self.symbols)
267
268 def aspolyhedron(self):
269 from .polyhedra import Polyhedron
270 islset = self._toislset(self.polyhedra, self.symbols)
271 islbset = libisl.isl_set_polyhedral_hull(islset)
272 return Polyhedron._fromislbasicset(islbset, self.symbols)
273
274 def asdomain(self):
275 return self
276
277 def project(self, symbols):
278 """
279 Project out the sequence of symbols given in arguments, and return the
280 resulting domain.
281 """
282 symbols = list(symbols)
283 for symbol in symbols:
284 if not isinstance(symbol, Symbol):
285 raise TypeError('symbols must be Symbol instances')
286 islset = self._toislset(self.polyhedra, self.symbols)
287 n = 0
288 for index, symbol in reversed(list(enumerate(self.symbols))):
289 if symbol in symbols:
290 n += 1
291 elif n > 0:
292 islset = libisl.isl_set_project_out(islset,
293 libisl.isl_dim_set, index + 1, n)
294 n = 0
295 if n > 0:
296 islset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, 0, n)
297 symbols = [symbol for symbol in self.symbols if symbol not in symbols]
298 return Domain._fromislset(islset, symbols)
299
300 def sample(self):
301 """
302 Return a sample of the domain, as an integer instance of Point. If the
303 domain is empty, a ValueError exception is raised.
304 """
305 islset = self._toislset(self.polyhedra, self.symbols)
306 islpoint = libisl.isl_set_sample_point(islset)
307 if bool(libisl.isl_point_is_void(islpoint)):
308 libisl.isl_point_free(islpoint)
309 raise ValueError('domain must be non-empty')
310 point = {}
311 for index, symbol in enumerate(self.symbols):
312 coordinate = libisl.isl_point_get_coordinate_val(islpoint,
313 libisl.isl_dim_set, index)
314 coordinate = islhelper.isl_val_to_int(coordinate)
315 point[symbol] = coordinate
316 libisl.isl_point_free(islpoint)
317 return point
318
319 def intersection(self, *others):
320 """
321 Return the intersection of two or more domains as a new domain. As an
322 alternative, function And() can be used.
323 """
324 result = self
325 for other in others:
326 result &= other
327 return result
328
329 def __and__(self, other):
330 if isinstance(other, Domain):
331 symbols = self._xsymbols([self, other])
332 islset1 = self._toislset(self.polyhedra, symbols)
333 islset2 = other._toislset(other.polyhedra, symbols)
334 islset = libisl.isl_set_intersect(islset1, islset2)
335 return self._fromislset(islset, symbols)
336 return NotImplemented
337 __and__.__doc__ = intersection.__doc__
338
339 def union(self, *others):
340 """
341 Return the union of two or more domains as a new domain. As an
342 alternative, function Or() can be used.
343 """
344 result = self
345 for other in others:
346 result |= other
347 return result
348
349 def __or__(self, other):
350 if isinstance(other, Domain):
351 symbols = self._xsymbols([self, other])
352 islset1 = self._toislset(self.polyhedra, symbols)
353 islset2 = other._toislset(other.polyhedra, symbols)
354 islset = libisl.isl_set_union(islset1, islset2)
355 return self._fromislset(islset, symbols)
356 return NotImplemented
357 __or__.__doc__ = union.__doc__
358
359 def __add__(self, other):
360 return self | other
361 __add__.__doc__ = union.__doc__
362
363 def difference(self, other):
364 """
365 Return the difference of two domains as a new domain.
366 """
367 return self - other
368
369 def __sub__(self, other):
370 if isinstance(other, Domain):
371 symbols = self._xsymbols([self, other])
372 islset1 = self._toislset(self.polyhedra, symbols)
373 islset2 = other._toislset(other.polyhedra, symbols)
374 islset = libisl.isl_set_subtract(islset1, islset2)
375 return self._fromislset(islset, symbols)
376 return NotImplemented
377 __sub__.__doc__ = difference.__doc__
378
379 def lexmin(self):
380 """
381 Return the lexicographic minimum of the elements in the domain.
382 """
383 islset = self._toislset(self.polyhedra, self.symbols)
384 islset = libisl.isl_set_lexmin(islset)
385 return self._fromislset(islset, self.symbols)
386
387 def lexmax(self):
388 """
389 Return the lexicographic maximum of the elements in the domain.
390 """
391 islset = self._toislset(self.polyhedra, self.symbols)
392 islset = libisl.isl_set_lexmax(islset)
393 return self._fromislset(islset, self.symbols)
394
395 if islhelper.isl_version >= '0.13':
396 _RE_COORDINATE = re.compile(r'\((?P<num>\-?\d+)\)(/(?P<den>\d+))?')
397 else:
398 _RE_COORDINATE = None
399
400 def vertices(self):
401 """
402 Return the vertices of the domain, as a list of rational instances of
403 Point.
404 """
405 from .polyhedra import Polyhedron
406 if not self.isbounded():
407 raise ValueError('domain must be bounded')
408 islbset = self._toislbasicset(self.equalities, self.inequalities,
409 self.symbols)
410 vertices = libisl.isl_basic_set_compute_vertices(islbset);
411 vertices = islhelper.isl_vertices_vertices(vertices)
412 points = []
413 for vertex in vertices:
414 expr = libisl.isl_vertex_get_expr(vertex)
415 coordinates = []
416 if self._RE_COORDINATE is None:
417 constraints = islhelper.isl_basic_set_constraints(expr)
418 for constraint in constraints:
419 constant = libisl.isl_constraint_get_constant_val(constraint)
420 constant = islhelper.isl_val_to_int(constant)
421 for index, symbol in enumerate(self.symbols):
422 coefficient = libisl.isl_constraint_get_coefficient_val(constraint,
423 libisl.isl_dim_set, index)
424 coefficient = islhelper.isl_val_to_int(coefficient)
425 if coefficient != 0:
426 coordinate = -Fraction(constant, coefficient)
427 coordinates.append((symbol, coordinate))
428 else:
429 string = islhelper.isl_multi_aff_to_str(expr)
430 matches = self._RE_COORDINATE.finditer(string)
431 for symbol, match in zip(self.symbols, matches):
432 numerator = int(match.group('num'))
433 denominator = match.group('den')
434 denominator = 1 if denominator is None else int(denominator)
435 coordinate = Fraction(numerator, denominator)
436 coordinates.append((symbol, coordinate))
437 points.append(Point(coordinates))
438 return points
439
440 def points(self):
441 """
442 Return the integer points of a bounded domain, as a list of integer
443 instances of Point. If the domain is not bounded, a ValueError exception
444 is raised.
445 """
446 if not self.isbounded():
447 raise ValueError('domain must be bounded')
448 from .polyhedra import Universe, Eq
449 islset = self._toislset(self.polyhedra, self.symbols)
450 islpoints = islhelper.isl_set_points(islset)
451 points = []
452 for islpoint in islpoints:
453 coordinates = {}
454 for index, symbol in enumerate(self.symbols):
455 coordinate = libisl.isl_point_get_coordinate_val(islpoint,
456 libisl.isl_dim_set, index)
457 coordinate = islhelper.isl_val_to_int(coordinate)
458 coordinates[symbol] = coordinate
459 points.append(Point(coordinates))
460 return points
461
462 def __contains__(self, point):
463 """
464 Return True if the point if contained within the domain.
465 """
466 for polyhedron in self.polyhedra:
467 if point in polyhedron:
468 return True
469 return False
470
471 @classmethod
472 def _polygon_inner_point(cls, points):
473 symbols = points[0].symbols
474 coordinates = {symbol: 0 for symbol in symbols}
475 for point in points:
476 for symbol, coordinate in point.coordinates():
477 coordinates[symbol] += coordinate
478 for symbol in symbols:
479 coordinates[symbol] /= len(points)
480 return Point(coordinates)
481
482 @classmethod
483 def _sort_polygon_2d(cls, points):
484 if len(points) <= 3:
485 return points
486 o = cls._polygon_inner_point(points)
487 angles = {}
488 for m in points:
489 om = Vector(o, m)
490 dx, dy = (coordinate for symbol, coordinate in om.coordinates())
491 angle = math.atan2(dy, dx)
492 angles[m] = angle
493 return sorted(points, key=angles.get)
494
495 @classmethod
496 def _sort_polygon_3d(cls, points):
497 if len(points) <= 3:
498 return points
499 o = cls._polygon_inner_point(points)
500 a = points[0]
501 oa = Vector(o, a)
502 norm_oa = oa.norm()
503 for b in points[1:]:
504 ob = Vector(o, b)
505 u = oa.cross(ob)
506 if not u.isnull():
507 u = u.asunit()
508 break
509 else:
510 raise ValueError('degenerate polygon')
511 angles = {a: 0.}
512 for m in points[1:]:
513 om = Vector(o, m)
514 normprod = norm_oa * om.norm()
515 cosinus = max(oa.dot(om) / normprod, -1.)
516 sinus = u.dot(oa.cross(om)) / normprod
517 angle = math.acos(cosinus)
518 angle = math.copysign(angle, sinus)
519 angles[m] = angle
520 return sorted(points, key=angles.get)
521
522 def faces(self):
523 """
524 Return the list of faces of a bounded domain. Each face is represented
525 by a list of vertices, in the form of rational instances of Point. If
526 the domain is not bounded, a ValueError exception is raised.
527 """
528 faces = []
529 for polyhedron in self.polyhedra:
530 vertices = polyhedron.vertices()
531 for constraint in polyhedron.constraints:
532 face = []
533 for vertex in vertices:
534 if constraint.subs(vertex.coordinates()) == 0:
535 face.append(vertex)
536 if len(face) >= 3:
537 faces.append(face)
538 return faces
539
540 def _plot_2d(self, plot=None, **kwargs):
541 import matplotlib.pyplot as plt
542 from matplotlib.patches import Polygon
543 if plot is None:
544 fig = plt.figure()
545 plot = fig.add_subplot(1, 1, 1)
546 xmin, xmax = plot.get_xlim()
547 ymin, ymax = plot.get_ylim()
548 for polyhedron in self.polyhedra:
549 vertices = polyhedron._sort_polygon_2d(polyhedron.vertices())
550 xys = [tuple(vertex.values()) for vertex in vertices]
551 xs, ys = zip(*xys)
552 xmin, xmax = min(xmin, float(min(xs))), max(xmax, float(max(xs)))
553 ymin, ymax = min(ymin, float(min(ys))), max(ymax, float(max(ys)))
554 plot.add_patch(Polygon(xys, closed=True, **kwargs))
555 plot.set_xlim(xmin, xmax)
556 plot.set_ylim(ymin, ymax)
557 return plot
558
559 def _plot_3d(self, plot=None, **kwargs):
560 import matplotlib.pyplot as plt
561 from mpl_toolkits.mplot3d import Axes3D
562 from mpl_toolkits.mplot3d.art3d import Poly3DCollection
563 if plot is None:
564 fig = plt.figure()
565 axes = Axes3D(fig)
566 else:
567 axes = plot
568 xmin, xmax = axes.get_xlim()
569 ymin, ymax = axes.get_ylim()
570 zmin, zmax = axes.get_zlim()
571 poly_xyzs = []
572 for vertices in self.faces():
573 vertices = self._sort_polygon_3d(vertices)
574 vertices.append(vertices[0])
575 face_xyzs = [tuple(vertex.values()) for vertex in vertices]
576 xs, ys, zs = zip(*face_xyzs)
577 xmin, xmax = min(xmin, float(min(xs))), max(xmax, float(max(xs)))
578 ymin, ymax = min(ymin, float(min(ys))), max(ymax, float(max(ys)))
579 zmin, zmax = min(zmin, float(min(zs))), max(zmax, float(max(zs)))
580 poly_xyzs.append(face_xyzs)
581 collection = Poly3DCollection(poly_xyzs, **kwargs)
582 axes.add_collection3d(collection)
583 axes.set_xlim(xmin, xmax)
584 axes.set_ylim(ymin, ymax)
585 axes.set_zlim(zmin, zmax)
586 return axes
587
588 def plot(self, plot=None, **kwargs):
589 """
590 Plot a 2D or 3D domain using matplotlib. Draw it to the current plot
591 object if present, otherwise create a new one. options are keyword
592 arguments passed to the matplotlib drawing functions, they can be used
593 to set the drawing color for example. Raise ValueError is the domain is
594 not 2D or 3D.
595 """
596 if not self.isbounded():
597 raise ValueError('domain must be bounded')
598 elif self.dimension == 2:
599 return self._plot_2d(plot=plot, **kwargs)
600 elif self.dimension == 3:
601 return self._plot_3d(plot=plot, **kwargs)
602 else:
603 raise ValueError('domain must be 2 or 3-dimensional')
604
605 def subs(self, symbol, expression=None):
606 """
607 Substitute the given symbol by an expression in the domain constraints.
608 To perform multiple substitutions at once, pass a sequence or a
609 dictionary of (old, new) pairs to subs. The syntax of this function is
610 similar to LinExpr.subs().
611 """
612 polyhedra = [polyhedron.subs(symbol, expression)
613 for polyhedron in self.polyhedra]
614 return Domain(*polyhedra)
615
616 @classmethod
617 def _fromislset(cls, islset, symbols):
618 from .polyhedra import Polyhedron
619 islset = libisl.isl_set_remove_divs(islset)
620 islbsets = islhelper.isl_set_basic_sets(islset)
621 libisl.isl_set_free(islset)
622 polyhedra = []
623 for islbset in islbsets:
624 polyhedron = Polyhedron._fromislbasicset(islbset, symbols)
625 polyhedra.append(polyhedron)
626 if len(polyhedra) == 0:
627 from .polyhedra import Empty
628 return Empty
629 elif len(polyhedra) == 1:
630 return polyhedra[0]
631 else:
632 self = object().__new__(Domain)
633 self._polyhedra = tuple(polyhedra)
634 self._symbols = cls._xsymbols(polyhedra)
635 self._dimension = len(self._symbols)
636 return self
637
638 @classmethod
639 def _toislset(cls, polyhedra, symbols):
640 polyhedron = polyhedra[0]
641 islbset = polyhedron._toislbasicset(polyhedron.equalities,
642 polyhedron.inequalities, symbols)
643 islset1 = libisl.isl_set_from_basic_set(islbset)
644 for polyhedron in polyhedra[1:]:
645 islbset = polyhedron._toislbasicset(polyhedron.equalities,
646 polyhedron.inequalities, symbols)
647 islset2 = libisl.isl_set_from_basic_set(islbset)
648 islset1 = libisl.isl_set_union(islset1, islset2)
649 return islset1
650
651 @classmethod
652 def _fromast(cls, node):
653 from .polyhedra import Polyhedron
654 if isinstance(node, ast.Module) and len(node.body) == 1:
655 return cls._fromast(node.body[0])
656 elif isinstance(node, ast.Expr):
657 return cls._fromast(node.value)
658 elif isinstance(node, ast.UnaryOp):
659 domain = cls._fromast(node.operand)
660 if isinstance(node.operand, ast.invert):
661 return Not(domain)
662 elif isinstance(node, ast.BinOp):
663 domain1 = cls._fromast(node.left)
664 domain2 = cls._fromast(node.right)
665 if isinstance(node.op, ast.BitAnd):
666 return And(domain1, domain2)
667 elif isinstance(node.op, ast.BitOr):
668 return Or(domain1, domain2)
669 elif isinstance(node, ast.Compare):
670 equalities = []
671 inequalities = []
672 left = LinExpr._fromast(node.left)
673 for i in range(len(node.ops)):
674 op = node.ops[i]
675 right = LinExpr._fromast(node.comparators[i])
676 if isinstance(op, ast.Lt):
677 inequalities.append(right - left - 1)
678 elif isinstance(op, ast.LtE):
679 inequalities.append(right - left)
680 elif isinstance(op, ast.Eq):
681 equalities.append(left - right)
682 elif isinstance(op, ast.GtE):
683 inequalities.append(left - right)
684 elif isinstance(op, ast.Gt):
685 inequalities.append(left - right - 1)
686 else:
687 break
688 left = right
689 else:
690 return Polyhedron(equalities, inequalities)
691 raise SyntaxError('invalid syntax')
692
693 _RE_BRACES = re.compile(r'^\{\s*|\s*\}$')
694 _RE_EQ = re.compile(r'([^<=>])=([^<=>])')
695 _RE_AND = re.compile(r'\band\b|,|&&|/\\|∧|∩')
696 _RE_OR = re.compile(r'\bor\b|;|\|\||\\/|∨|∪')
697 _RE_NOT = re.compile(r'\bnot\b|!|¬')
698 _RE_NUM_VAR = LinExpr._RE_NUM_VAR
699 _RE_OPERATORS = re.compile(r'(&|\||~)')
700
701 @classmethod
702 def fromstring(cls, string):
703 """
704 Create a domain from a string. Raise SyntaxError if the string is not
705 properly formatted.
706 """
707 # Remove curly brackets.
708 string = cls._RE_BRACES.sub(r'', string)
709 # Replace '=' by '=='.
710 string = cls._RE_EQ.sub(r'\1==\2', string)
711 # Replace 'and', 'or', 'not'.
712 string = cls._RE_AND.sub(r' & ', string)
713 string = cls._RE_OR.sub(r' | ', string)
714 string = cls._RE_NOT.sub(r' ~', string)
715 # Add implicit multiplication operators, e.g. '5x' -> '5*x'.
716 string = cls._RE_NUM_VAR.sub(r'\1*\2', string)
717 # Add parentheses to force precedence.
718 tokens = cls._RE_OPERATORS.split(string)
719 for i, token in enumerate(tokens):
720 if i % 2 == 0:
721 token = '({})'.format(token)
722 tokens[i] = token
723 string = ''.join(tokens)
724 tree = ast.parse(string, 'eval')
725 return cls._fromast(tree)
726
727 def __repr__(self):
728 assert len(self.polyhedra) >= 2
729 strings = [repr(polyhedron) for polyhedron in self.polyhedra]
730 return 'Or({})'.format(', '.join(strings))
731
732 def _repr_latex_(self):
733 strings = []
734 for polyhedron in self.polyhedra:
735 strings.append('({})'.format(polyhedron._repr_latex_().strip('$')))
736 return '${}$'.format(' \\vee '.join(strings))
737
738 @classmethod
739 def fromsympy(cls, expr):
740 """
741 Create a domain from a SymPy expression.
742 """
743 import sympy
744 from .polyhedra import Lt, Le, Eq, Ne, Ge, Gt
745 funcmap = {
746 sympy.And: And, sympy.Or: Or, sympy.Not: Not,
747 sympy.Lt: Lt, sympy.Le: Le,
748 sympy.Eq: Eq, sympy.Ne: Ne,
749 sympy.Ge: Ge, sympy.Gt: Gt,
750 }
751 if expr.func in funcmap:
752 args = [Domain.fromsympy(arg) for arg in expr.args]
753 return funcmap[expr.func](*args)
754 elif isinstance(expr, sympy.Expr):
755 return LinExpr.fromsympy(expr)
756 raise ValueError('non-domain expression: {!r}'.format(expr))
757
758 def tosympy(self):
759 """
760 Convert the domain to a SymPy expression.
761 """
762 import sympy
763 polyhedra = [polyhedron.tosympy() for polyhedron in polyhedra]
764 return sympy.Or(*polyhedra)
765
766
767 def And(*domains):
768 """
769 Create the intersection domain of the domains given in arguments.
770 """
771 if len(domains) == 0:
772 from .polyhedra import Universe
773 return Universe
774 else:
775 return domains[0].intersection(*domains[1:])
776
777 def Or(*domains):
778 """
779 Create the union domain of the domains given in arguments.
780 """
781 if len(domains) == 0:
782 from .polyhedra import Empty
783 return Empty
784 else:
785 return domains[0].union(*domains[1:])
786
787 def Not(domain):
788 """
789 Create the complementary domain of the domain given in argument.
790 """
791 return ~domain