sets.h
Go to the documentation of this file.
1 
5 #ifndef SYMENGINE_SETS_H
6 #define SYMENGINE_SETS_H
7 
8 #include <symengine/functions.h>
9 #include <symengine/complex.h>
10 #include <symengine/symengine_casts.h>
11 #include <iterator>
12 namespace SymEngine
13 {
14 class Set;
15 class BooleanAtom;
16 class Boolean;
17 inline bool is_a_Boolean(const Basic &b);
18 RCP<const BooleanAtom> boolean(bool b);
19 } // namespace SymEngine
20 #include <symengine/logic.h>
21 
22 namespace SymEngine
23 {
24 typedef std::set<RCP<const Set>, RCPBasicKeyLess> set_set;
25 class Set : public Basic
26 {
27 public:
28  virtual vec_basic get_args() const = 0;
29  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const = 0;
30  virtual RCP<const Set> set_union(const RCP<const Set> &o) const = 0;
31  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const = 0;
32  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const = 0;
33  bool is_subset(const RCP<const Set> &o) const
34  {
35  return eq(*this->set_intersection(o), *this);
36  }
37  bool is_proper_subset(const RCP<const Set> &o) const
38  {
39  return not eq(*this, *o) and this->is_subset(o);
40  }
41  bool is_superset(const RCP<const Set> &o) const
42  {
43  return o->is_subset(rcp_from_this_cast<const Set>());
44  }
45  bool is_proper_superset(const RCP<const Set> &o) const
46  {
47  return not eq(*this, *o) and this->is_superset(o);
48  }
49 };
50 
51 class EmptySet : public Set
52 {
53 public:
54  EmptySet(){SYMENGINE_ASSIGN_TYPEID()}
55 
56  IMPLEMENT_TYPEID(SYMENGINE_EMPTYSET)
57  // EmptySet(EmptySet const&) = delete;
58  void
59  operator=(EmptySet const &)
60  = delete;
61  const static RCP<const EmptySet> &getInstance();
62  virtual hash_t __hash__() const;
63  virtual bool __eq__(const Basic &o) const;
64  virtual int compare(const Basic &o) const;
65  virtual vec_basic get_args() const
66  {
67  return {};
68  }
69 
70  template <typename T_, typename... Args>
71  friend inline RCP<T_> make_rcp(Args &&...args);
72 
73  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
74  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
75  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
76  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const
77  {
78  return boolean(false);
79  };
80 };
81 
82 class UniversalSet : public Set
83 {
84 public:
85  UniversalSet()
86  {
87  SYMENGINE_ASSIGN_TYPEID()
88  }
89 
90 public:
91  IMPLEMENT_TYPEID(SYMENGINE_UNIVERSALSET)
92  // UniversalSet(UniversalSet const&) = delete;
93  void operator=(UniversalSet const &) = delete;
94  const static RCP<const UniversalSet> &getInstance();
95  virtual hash_t __hash__() const;
96  virtual bool __eq__(const Basic &o) const;
97  virtual int compare(const Basic &o) const;
98  virtual vec_basic get_args() const
99  {
100  return {};
101  }
102 
103  template <typename T_, typename... Args>
104  friend inline RCP<T_> make_rcp(Args &&...args);
105 
106  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
107  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
108  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
109  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const
110  {
111  return boolean(true);
112  };
113 };
114 
115 class FiniteSet : public Set
116 {
117 private:
118  set_basic container_;
119 
120 public:
121  IMPLEMENT_TYPEID(SYMENGINE_FINITESET)
122  virtual hash_t __hash__() const;
123  virtual bool __eq__(const Basic &o) const;
124  virtual int compare(const Basic &o) const;
125  virtual vec_basic get_args() const
126  {
127  return vec_basic(container_.begin(), container_.end());
128  }
129 
130  FiniteSet(const set_basic &container);
131  static bool is_canonical(const set_basic &container);
132 
133  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
134  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
135  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
136  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
137  RCP<const Set> create(const set_basic &container) const;
138 
139  inline const set_basic &get_container() const
140  {
141  return this->container_;
142  }
143 };
144 
145 class Interval : public Set
146 {
147 private:
148  RCP<const Number> start_;
149  RCP<const Number> end_;
150  bool left_open_, right_open_;
151 
152 public:
153  IMPLEMENT_TYPEID(SYMENGINE_INTERVAL)
154  virtual hash_t __hash__() const;
155  virtual bool __eq__(const Basic &o) const;
156  virtual int compare(const Basic &o) const;
157 
158  Interval(const RCP<const Number> &start, const RCP<const Number> &end,
159  const bool left_open = false, const bool right_open = false);
160 
161  RCP<const Set> open() const;
162  RCP<const Set> close() const;
163  RCP<const Set> Lopen() const;
164  RCP<const Set> Ropen() const;
165 
166  static bool is_canonical(const RCP<const Number> &start,
167  const RCP<const Number> &end, bool left_open,
168  bool right_open);
169 
170  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
171  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
172  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
173  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
174  virtual vec_basic get_args() const;
175 
176  inline const RCP<const Number> &get_start() const
177  {
178  return start_;
179  }
180  inline const RCP<const Number> &get_end() const
181  {
182  return end_;
183  }
184  inline const bool &get_left_open() const
185  {
186  return this->left_open_;
187  }
188  inline const bool &get_right_open() const
189  {
190  return this->right_open_;
191  }
192 };
193 
194 class Reals : public Set
195 {
196 public:
197  Reals()
198  {
199  SYMENGINE_ASSIGN_TYPEID()
200  }
201 
202 public:
203  IMPLEMENT_TYPEID(SYMENGINE_REALS)
204  void operator=(Reals const &) = delete;
205  const static RCP<const Reals> &getInstance();
206  virtual hash_t __hash__() const;
207  virtual bool __eq__(const Basic &o) const;
208  virtual int compare(const Basic &o) const;
209  virtual vec_basic get_args() const
210  {
211  return {};
212  }
213 
214  template <typename T_, typename... Args>
215  friend inline RCP<T_> make_rcp(Args &&...args);
216 
217  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
218  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
219  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
220  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
221 };
222 
223 class Rationals : public Set
224 {
225 public:
226  Rationals()
227  {
228  SYMENGINE_ASSIGN_TYPEID()
229  }
230 
231 public:
232  IMPLEMENT_TYPEID(SYMENGINE_RATIONALS)
233  void operator=(Rationals const &) = delete;
234  const static RCP<const Rationals> &getInstance();
235  virtual hash_t __hash__() const;
236  virtual bool __eq__(const Basic &o) const;
237  virtual int compare(const Basic &o) const;
238  virtual vec_basic get_args() const
239  {
240  return {};
241  }
242 
243  template <typename T_, typename... Args>
244  friend inline RCP<T_> make_rcp(Args &&...args);
245 
246  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
247  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
248  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
249  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
250 };
251 
252 class Integers : public Set
253 {
254 public:
255  Integers()
256  {
257  SYMENGINE_ASSIGN_TYPEID()
258  }
259 
260 public:
261  IMPLEMENT_TYPEID(SYMENGINE_INTEGERS)
262  void operator=(Integers const &) = delete;
263  const static RCP<const Integers> &getInstance();
264  virtual hash_t __hash__() const;
265  virtual bool __eq__(const Basic &o) const;
266  virtual int compare(const Basic &o) const;
267  virtual vec_basic get_args() const
268  {
269  return {};
270  }
271 
272  template <typename T_, typename... Args>
273  friend inline RCP<T_> make_rcp(Args &&...args);
274 
275  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
276  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
277  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
278  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
279 };
280 
281 class Union : public Set
282 {
283 private:
284  set_set container_;
285 
286 public:
287  IMPLEMENT_TYPEID(SYMENGINE_UNION)
288  virtual hash_t __hash__() const;
289  virtual bool __eq__(const Basic &o) const;
290  virtual int compare(const Basic &o) const;
291  virtual vec_basic get_args() const;
292  Union(const set_set &in);
293  static bool is_canonical(const set_set &in);
294 
295  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
296  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
297  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
298  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
299 
300  inline const set_set &get_container() const
301  {
302  return this->container_;
303  }
304 
305  RCP<const Set> create(const set_set &in) const;
306 };
307 
308 class Complement : public Set
309 {
310 private:
311  // represents universe_ - container_
312  RCP<const Set> universe_;
313  RCP<const Set> container_;
314 
315 public:
316  IMPLEMENT_TYPEID(SYMENGINE_COMPLEMENT)
317  virtual hash_t __hash__() const;
318  virtual bool __eq__(const Basic &o) const;
319  virtual int compare(const Basic &o) const;
320  virtual vec_basic get_args() const
321  {
322  return {universe_, container_};
323  }
324  Complement(const RCP<const Set> &universe, const RCP<const Set> &container);
325 
326  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
327  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
328  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
329  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
330 
331  inline const RCP<const Set> &get_universe() const
332  {
333  return this->universe_;
334  }
335  inline const RCP<const Set> &get_container() const
336  {
337  return this->container_;
338  }
339 };
340 
341 class ConditionSet : public Set
342 {
343 private:
344  RCP<const Basic> sym;
345  RCP<const Boolean> condition_;
346 
347 public:
348  IMPLEMENT_TYPEID(SYMENGINE_CONDITIONSET)
349  virtual hash_t __hash__() const;
350  virtual bool __eq__(const Basic &o) const;
351  virtual int compare(const Basic &o) const;
352  virtual vec_basic get_args() const
353  {
354  return {sym, condition_};
355  }
356  ConditionSet(const RCP<const Basic> &sym,
357  const RCP<const Boolean> &condition);
358  static bool is_canonical(const RCP<const Basic> &sym,
359  const RCP<const Boolean> &condition);
360  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
361  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
362  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
363  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
364  inline const RCP<const Basic> &get_symbol() const
365  {
366  return this->sym;
367  }
368  inline const RCP<const Boolean> &get_condition() const
369  {
370  return this->condition_;
371  }
372 };
373 
374 class ImageSet : public Set
375 {
376 private:
377  // represents {expr_ for sym_ in base_}
378  RCP<const Basic> sym_;
379  RCP<const Basic> expr_;
380  RCP<const Set> base_; // base set for all symbols
381 
382 public:
383  IMPLEMENT_TYPEID(SYMENGINE_IMAGESET)
384  virtual hash_t __hash__() const;
385  virtual bool __eq__(const Basic &o) const;
386  virtual int compare(const Basic &o) const;
387  virtual vec_basic get_args() const
388  {
389  return {sym_, expr_, base_};
390  }
391  ImageSet(const RCP<const Basic> &sym, const RCP<const Basic> &expr,
392  const RCP<const Set> &base);
393 
394  static bool is_canonical(const RCP<const Basic> &sym,
395  const RCP<const Basic> &expr,
396  const RCP<const Set> &base);
397  virtual RCP<const Set> set_intersection(const RCP<const Set> &o) const;
398  virtual RCP<const Set> set_union(const RCP<const Set> &o) const;
399  virtual RCP<const Set> set_complement(const RCP<const Set> &o) const;
400  virtual RCP<const Boolean> contains(const RCP<const Basic> &a) const;
401 
402  inline const RCP<const Basic> &get_symbol() const
403  {
404  return this->sym_;
405  }
406  inline const RCP<const Basic> &get_expr() const
407  {
408  return this->expr_;
409  }
410  inline const RCP<const Set> &get_baseset() const
411  {
412  return this->base_;
413  }
414 
415  RCP<const Set> create(const RCP<const Basic> &sym,
416  const RCP<const Basic> &expr,
417  const RCP<const Set> &base) const;
418 };
419 
420 inline bool is_a_Set(const Basic &b)
421 {
422  return (b.get_type_code() == SYMENGINE_EMPTYSET
423  || b.get_type_code() == SYMENGINE_UNIVERSALSET
424  || b.get_type_code() == SYMENGINE_FINITESET
425  || b.get_type_code() == SYMENGINE_COMPLEMENT
426  || b.get_type_code() == SYMENGINE_CONDITIONSET
427  || b.get_type_code() == SYMENGINE_INTERVAL
428  || b.get_type_code() == SYMENGINE_REALS
429  || b.get_type_code() == SYMENGINE_RATIONALS
430  || b.get_type_code() == SYMENGINE_INTEGERS
431  || b.get_type_code() == SYMENGINE_UNION
432  || b.get_type_code() == SYMENGINE_IMAGESET);
433 }
434 
436 inline RCP<const Reals> reals()
437 {
438  return Reals::getInstance();
439 }
440 
442 inline RCP<const Rationals> rationals()
443 {
444  return Rationals::getInstance();
445 }
446 
448 inline RCP<const Integers> integers()
449 {
450  return Integers::getInstance();
451 }
452 
454 inline RCP<const EmptySet> emptyset()
455 {
456  return EmptySet::getInstance();
457 }
458 
460 inline RCP<const UniversalSet> universalset()
461 {
462  return UniversalSet::getInstance();
463 }
464 
466 inline RCP<const Set> finiteset(const set_basic &container)
467 {
468  if (FiniteSet::is_canonical(container)) {
469  return make_rcp<const FiniteSet>(container);
470  }
471  return emptyset();
472 }
473 
475 inline RCP<const Set> interval(const RCP<const Number> &start,
476  const RCP<const Number> &end,
477  const bool left_open = false,
478  const bool right_open = false)
479 {
480  if (Interval::is_canonical(start, end, left_open, right_open))
481  return make_rcp<const Interval>(start, end, left_open, right_open);
482  if (eq(*start, *end) and not(left_open or right_open))
483  return finiteset({start});
484  return emptyset();
485 }
486 
487 // ! \return RCP<const Set>
488 inline RCP<const Set> imageset(const RCP<const Basic> &sym,
489  const RCP<const Basic> &expr,
490  const RCP<const Set> &base)
491 {
492  if (not is_a_sub<Symbol>(*sym))
493  throw SymEngineException("first arg is expected to be a symbol");
494 
495  if (eq(*expr, *sym) or eq(*base, *emptyset()))
496  return base;
497 
498  if (is_a_Number(*expr))
499  return finiteset({expr});
500  if (is_a_Set(*expr)) {
501  for (const auto &s : static_cast<const Set &>(*expr).get_args()) {
502  if (not(is_a_Number(*s) or is_a<Constant>(*s)
503  or is_a_Boolean(*s))) {
504  return make_rcp<const ImageSet>(sym, expr, base);
505  }
506  }
507  return finiteset({expr});
508  }
509 
510  if (is_a<FiniteSet>(*base)) {
511  map_basic_basic d;
512  set_basic temp;
513  for (const auto &s :
514  down_cast<const FiniteSet &>(*base).get_container()) {
515  d[sym] = s;
516  temp.insert(expr->subs(d));
517  d.clear();
518  }
519  return finiteset(temp);
520  }
521 
522  if (is_a<ImageSet>(*base)) {
523  const ImageSet &imbase = down_cast<const ImageSet &>(*base);
524  map_basic_basic d;
525  d[sym] = imbase.get_expr();
526  return imageset(imbase.get_symbol(), expand(expr->subs(d)),
527  imbase.get_baseset());
528  }
529 
530  return make_rcp<const ImageSet>(sym, expr, base);
531 }
532 
533 // ! \return RCP<const Set>
534 RCP<const Set> set_union(const set_set &in);
535 
536 // ! \return RCP<const Set>
537 RCP<const Set> set_intersection(const set_set &in);
538 
539 RCP<const Set> set_complement_helper(const RCP<const Set> &container,
540  const RCP<const Set> &universe);
541 
542 // ! \return RCP<const Set>
543 RCP<const Set> set_complement(const RCP<const Set> &universe,
544  const RCP<const Set> &container);
545 
547 RCP<const Set> conditionset(const RCP<const Basic> &sym,
548  const RCP<const Boolean> &condition);
549 } // namespace SymEngine
550 #endif
#define IMPLEMENT_TYPEID(SYMENGINE_ID)
Inline members and functions.
Definition: basic.h:340
T begin(T... args)
The lowest unit of symbolic representation.
Definition: basic.h:95
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:992
virtual int compare(const Basic &o) const
Definition: sets.cpp:1002
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:320
virtual hash_t __hash__() const
Definition: sets.cpp:984
virtual int compare(const Basic &o) const
Definition: sets.cpp:1078
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:352
virtual hash_t __hash__() const
Definition: sets.cpp:1060
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:1068
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:65
virtual int compare(const Basic &o) const
Definition: sets.cpp:522
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:515
virtual hash_t __hash__() const
Definition: sets.cpp:509
virtual hash_t __hash__() const
Definition: sets.cpp:585
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:593
virtual int compare(const Basic &o) const
Definition: sets.cpp:602
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:125
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:387
virtual int compare(const Basic &o) const
Definition: sets.cpp:1146
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:1136
virtual hash_t __hash__() const
Definition: sets.cpp:1127
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:475
virtual hash_t __hash__() const
Definition: sets.cpp:469
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:267
virtual int compare(const Basic &o) const
Definition: sets.cpp:482
virtual hash_t __hash__() const
Definition: sets.cpp:33
virtual int compare(const Basic &o) const
Definition: sets.cpp:54
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:43
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.cpp:258
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:238
virtual hash_t __hash__() const
Definition: sets.cpp:389
virtual int compare(const Basic &o) const
Definition: sets.cpp:400
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:395
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:209
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:321
virtual hash_t __hash__() const
Definition: sets.cpp:315
virtual int compare(const Basic &o) const
Definition: sets.cpp:328
virtual vec_basic get_args() const =0
Returns the list of arguments.
virtual hash_t __hash__() const
Definition: sets.cpp:881
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:889
virtual int compare(const Basic &o) const
Definition: sets.cpp:913
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.cpp:974
virtual vec_basic get_args() const
Returns the list of arguments.
Definition: sets.h:98
virtual hash_t __hash__() const
Definition: sets.cpp:549
virtual bool __eq__(const Basic &o) const
Test equality.
Definition: sets.cpp:555
virtual int compare(const Basic &o) const
Definition: sets.cpp:562
T end(T... args)
T insert(T... args)
Main namespace for SymEngine package.
Definition: add.cpp:19
bool is_a_Number(const Basic &b)
Definition: number.h:130
RCP< const Set > interval(const RCP< const Number > &start, const RCP< const Number > &end, const bool left_open=false, const bool right_open=false)
Definition: sets.h:475
RCP< const Reals > reals()
Definition: sets.h:436
bool eq(const Basic &a, const Basic &b)
Checks equality for a and b
Definition: basic-inl.h:21
RCP< const EmptySet > emptyset()
Definition: sets.h:454
RCP< const Integers > integers()
Definition: sets.h:448
RCP< const UniversalSet > universalset()
Definition: sets.h:460
RCP< const Set > conditionset(const RCP< const Basic > &sym, const RCP< const Boolean > &condition)
Definition: sets.cpp:1382
RCP< const Set > finiteset(const set_basic &container)
Definition: sets.h:466
RCP< const Basic > expand(const RCP< const Basic > &self, bool deep=true)
Expands self
Definition: expand.cpp:369
RCP< const Rationals > rationals()
Definition: sets.h:442
T set_intersection(T... args)
T set_union(T... args)