dict.h
Go to the documentation of this file.
1 
7 #ifndef SYMENGINE_DICT_H
8 #define SYMENGINE_DICT_H
9 #include <symengine/mp_class.h>
10 #include <algorithm>
11 #include <cstdint>
12 #include <map>
13 #include <vector>
14 #include <unordered_map>
15 #include <set>
16 #include <unordered_set>
17 
18 namespace SymEngine
19 {
20 
21 class Basic;
22 class Number;
23 class Integer;
24 class Expression;
25 class Symbol;
26 struct RCPBasicHash;
27 struct RCPBasicKeyEq;
28 struct RCPBasicKeyLess;
29 struct RCPIntegerKeyLess;
30 
31 bool eq(const Basic &, const Basic &);
32 typedef uint64_t hash_t;
33 typedef std::unordered_map<RCP<const Basic>, RCP<const Number>, RCPBasicHash,
34  RCPBasicKeyEq>
35  umap_basic_num;
36 typedef std::unordered_map<short, RCP<const Basic>> umap_short_basic;
37 typedef std::unordered_map<int, RCP<const Basic>> umap_int_basic;
38 typedef std::unordered_map<RCP<const Basic>, RCP<const Basic>, RCPBasicHash,
39  RCPBasicKeyEq>
40  umap_basic_basic;
41 typedef std::unordered_set<RCP<const Basic>, RCPBasicHash, RCPBasicKeyEq>
42  uset_basic;
43 
44 typedef std::vector<int> vec_int;
45 typedef std::vector<RCP<const Basic>> vec_basic;
46 typedef std::vector<RCP<const Integer>> vec_integer;
47 typedef std::vector<unsigned int> vec_uint;
48 typedef std::vector<integer_class> vec_integer_class;
49 typedef std::vector<RCP<const Symbol>> vec_sym;
50 typedef std::set<RCP<const Basic>, RCPBasicKeyLess> set_basic;
51 typedef std::multiset<RCP<const Basic>, RCPBasicKeyLess> multiset_basic;
53 typedef std::map<vec_uint, integer_class> map_vec_mpz;
54 typedef std::map<RCP<const Basic>, RCP<const Number>, RCPBasicKeyLess>
55  map_basic_num;
56 typedef std::map<RCP<const Basic>, RCP<const Basic>, RCPBasicKeyLess>
57  map_basic_basic;
58 typedef std::map<RCP<const Integer>, unsigned, RCPIntegerKeyLess>
59  map_integer_uint;
60 typedef std::map<unsigned, integer_class> map_uint_mpz;
61 typedef std::map<unsigned, rational_class> map_uint_mpq;
62 typedef std::map<int, Expression> map_int_Expr;
63 typedef std::unordered_map<RCP<const Basic>, unsigned int, RCPBasicHash,
64  RCPBasicKeyEq>
65  umap_basic_uint;
66 typedef std::vector<std::pair<RCP<const Basic>, RCP<const Basic>>> vec_pair;
67 
68 template <typename T>
69 struct vec_hash {
70  hash_t operator()(const T &v) const;
71 };
72 
82 template <typename T1, typename T2, typename T3>
83 inline void insert(T1 &m, const T2 &first, const T3 &second)
84 {
85  m.insert(std::pair<T2, T3>(first, second));
86 }
87 
88 // Takes an unordered map of type M with key type K and returns a vector of K
89 // ordered by C.
90 template <class M, typename C = std::less<typename M::key_type>>
91 std::vector<typename M::key_type> sorted_keys(const M &d)
92 {
94  v.reserve(d.size());
95  for (auto &p : d) {
96  v.push_back(p.first);
97  }
98  std::sort(v.begin(), v.end(), C());
99  return v;
100 }
101 
102 template <bool B, class T = void>
103 using enable_if_t = typename std::enable_if<B, T>::type;
104 
105 template <typename T, typename U>
106 inline bool unified_eq(const std::pair<T, U> &a, const std::pair<T, U> &b)
107 {
108  return unified_eq(a.first, b.first) and unified_eq(a.second, b.second);
109 }
110 
111 template <typename T, typename U>
112 inline bool unified_eq(const std::set<T, U> &a, const std::set<T, U> &b)
113 {
114  return ordered_eq(a, b);
115 }
116 
117 template <typename T, typename U>
118 inline bool unified_eq(const std::multiset<T, U> &a,
119  const std::multiset<T, U> &b)
120 {
121  return ordered_eq(a, b);
122 }
123 
124 template <typename K, typename V, typename C>
125 inline bool unified_eq(const std::map<K, V, C> &a, const std::map<K, V, C> &b)
126 {
127  return ordered_eq(a, b);
128 }
129 
130 template <typename K, typename V, typename H, typename E>
131 inline bool unified_eq(const std::unordered_map<K, V, H, E> &a,
133 {
134  return unordered_eq(a, b);
135 }
136 
137 template <typename T, typename U,
138  typename = enable_if_t<std::is_base_of<Basic, T>::value
140 inline bool unified_eq(const RCP<const T> &a, const RCP<const U> &b)
141 {
142  return eq(*a, *b);
143 }
144 
145 template <typename T,
146  typename = enable_if_t<std::is_arithmetic<T>::value
148 inline bool unified_eq(const T &a, const T &b)
149 {
150  return a == b;
151 }
152 
155 template <class T>
156 inline bool unordered_eq(const T &a, const T &b)
157 {
158  // This follows the same algorithm as Python's dictionary comparison
159  // (a==b), which is implemented by "dict_equal" function in
160  // Objects/dictobject.c.
161 
162  // Can't be equal if # of entries differ:
163  if (a.size() != b.size())
164  return false;
165  // Loop over keys in "a":
166  for (const auto &p : a) {
167  // O(1) lookup of the key in "b":
168  auto f = b.find(p.first);
169  if (f == b.end())
170  return false; // no such element in "b"
171  if (not unified_eq(p.second, f->second))
172  return false; // values not equal
173  }
174  return true;
175 }
176 
177 template <class T>
178 inline bool ordered_eq(const T &A, const T &B)
179 {
180  // Can't be equal if # of entries differ:
181  if (A.size() != B.size())
182  return false;
183  // Loop over elements in "a" and "b":
184  auto a = A.begin();
185  auto b = B.begin();
186  for (; a != A.end(); ++a, ++b) {
187  if (not unified_eq(*a, *b))
188  return false; // values not equal
189  }
190  return true;
191 }
192 
193 template <typename T>
194 inline bool unified_eq(const std::vector<T> &a, const std::vector<T> &b)
195 {
196  return ordered_eq(a, b);
197 }
198 
201 template <typename T,
202  typename = enable_if_t<std::is_arithmetic<T>::value
205 inline int unified_compare(const T &a, const T &b)
206 {
207  if (a == b)
208  return 0;
209  return a < b ? -1 : 1;
210 }
211 
212 template <typename T, typename U,
213  typename = enable_if_t<std::is_base_of<Basic, T>::value
215 inline int unified_compare(const RCP<const T> &a, const RCP<const U> &b)
216 {
217  return a->__cmp__(*b);
218 }
219 
220 template <class T>
221 inline int ordered_compare(const T &A, const T &B);
222 
223 template <typename T>
224 inline int unified_compare(const std::vector<T> &a, const std::vector<T> &b)
225 {
226  return ordered_compare(a, b);
227 }
228 
229 template <typename T, typename U>
230 inline int unified_compare(const std::set<T, U> &a, const std::set<T, U> &b)
231 {
232  return ordered_compare(a, b);
233 }
234 
235 template <typename T, typename U>
236 inline int unified_compare(const std::multiset<T, U> &a,
237  const std::multiset<T, U> &b)
238 {
239  return ordered_compare(a, b);
240 }
241 
242 template <typename T, typename U>
243 inline int unified_compare(const std::pair<T, U> &a, const std::pair<T, U> &b)
244 {
245  auto t = unified_compare(a.first, b.first);
246  if (t == 0) {
247  return unified_compare(a.second, b.second);
248  } else {
249  return t;
250  }
251 }
252 
253 template <typename K, typename V, typename C>
254 inline int unified_compare(const std::map<K, V, C> &a,
255  const std::map<K, V, C> &b)
256 {
257  return ordered_compare(a, b);
258 }
259 
260 template <typename K, typename V, typename H, typename E>
263 {
264  return unordered_compare(a, b);
265 }
266 
267 template <class T>
268 inline int ordered_compare(const T &A, const T &B)
269 {
270  // Can't be equal if # of entries differ:
271  if (A.size() != B.size())
272  return A.size() < B.size() ? -1 : 1;
273 
274  // Loop over elements in "a" and "b":
275  auto a = A.begin();
276  auto b = B.begin();
277  for (; a != A.end(); ++a, ++b) {
278  auto t = unified_compare(*a, *b);
279  if (t != 0)
280  return t; // values not equal
281  }
282  return 0;
283 }
284 
285 template <class M, typename C = std::less<typename M::key_type>>
286 inline int unordered_compare(const M &a, const M &b)
287 {
288  // Can't be equal if # of entries differ:
289  if (a.size() != b.size())
290  return a.size() < b.size() ? -1 : 1;
291 
292  std::vector<typename M::key_type> va = sorted_keys<M, C>(a);
293  std::vector<typename M::key_type> vb = sorted_keys<M, C>(b);
294 
295  for (unsigned int i = 0; i < va.size() && i < vb.size(); i++) {
296  bool s = C()(va[i], vb[i]);
297  if (s)
298  return -1;
299  s = C()(vb[i], va[i]);
300  if (s)
301  return 1;
302 
303  int t = unified_compare(a.find(va[i])->second, b.find(vb[i])->second);
304  if (t != 0)
305  return t;
306  }
307  return 0;
308 }
309 
311 bool vec_basic_eq_perm(const vec_basic &a, const vec_basic &b);
312 
317  const SymEngine::map_basic_basic &d);
319  const SymEngine::umap_basic_basic &d);
324 
325 } // namespace SymEngine
326 
327 #endif
T begin(T... args)
T end(T... args)
Main namespace for SymEngine package.
Definition: add.cpp:19
bool eq(const Basic &a, const Basic &b)
Checks equality for a and b
Definition: basic-inl.h:21
void insert(T1 &m, const T2 &first, const T3 &second)
Definition: dict.h:83
bool vec_basic_eq_perm(const vec_basic &a, const vec_basic &b)
misc functions
Definition: dict.cpp:103
int unified_compare(const T &a, const T &b)
Definition: dict.h:205
std::ostream & operator<<(std::ostream &out, const SymEngine::Basic &p)
<< Operator
Definition: basic-inl.h:53
bool unordered_eq(const T &a, const T &b)
Definition: dict.h:156
STL namespace.
T push_back(T... args)
T reserve(T... args)
T size(T... args)
T sort(T... args)