souffle  2.0.2-371-g6315b36
ContainerUtil.h
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file ContainerUtil.h
12  *
13  * @brief Datalog project utilities
14  *
15  ***********************************************************************/
16 
17 #pragma once
18 
19 #include <algorithm>
20 #include <functional>
21 #include <iterator>
22 #include <map>
23 #include <memory>
24 #include <set>
25 #include <type_traits>
26 #include <utility>
27 #include <vector>
28 
29 namespace souffle {
30 
31 // -------------------------------------------------------------------------------
32 // General Container Utilities
33 // -------------------------------------------------------------------------------
34 
35 template <typename A>
36 using Own = std::unique_ptr<A>;
37 
38 template <typename A>
39 using VecOwn = std::vector<Own<A>>;
40 
41 template <typename A, typename B = A, typename... Args>
42 Own<A> mk(Args&&... xs) {
43  return Own<A>(new B(std::forward<Args>(xs)...));
44 }
45 
46 /**
47  * Use to range-for iterate in reverse.
48  * Assumes `std::rbegin` and `std::rend` are defined for type `A`.
49  */
50 template <typename A>
51 struct reverse {
53  A& iterable;
54 
55  auto begin() {
56  return std::rbegin(iterable);
57  }
58 
59  auto end() {
60  return std::rend(iterable);
61  }
62 };
63 
64 /**
65  * A utility to check generically whether a given element is contained in a given
66  * container.
67  */
68 template <typename C>
69 bool contains(const C& container, const typename C::value_type& element) {
70  return std::find(container.begin(), container.end(), element) != container.end();
71 }
72 
73 // TODO: Detect and generalise to other set types?
74 template <typename A>
75 bool contains(const std::set<A>& container, const A& element) {
76  return container.find(element) != container.end();
77 }
78 
79 /**
80  * Version of contains specialised for maps.
81  *
82  * This workaround is needed because of set container, for which value_type == key_type,
83  * which is ambiguous in this context.
84  */
85 template <typename C>
86 bool contains(const C& container, const typename C::value_type::first_type& element) {
87  return container.find(element) != container.end();
88 }
89 
90 /**
91  * Returns the first element in a container that satisfies a given predicate,
92  * nullptr otherwise.
93  */
94 template <typename C>
95 typename C::value_type getIf(const C& container, std::function<bool(const typename C::value_type)> pred) {
96  auto res = std::find_if(container.begin(), container.end(),
97  [&](const typename C::value_type item) { return pred(item); });
98  return res == container.end() ? nullptr : *res;
99 }
100 
101 /**
102  * Get value for a given key; if not found, return default value.
103  */
104 template <typename C>
105 typename C::mapped_type const& getOr(
106  const C& container, typename C::key_type key, const typename C::mapped_type& defaultValue) {
107  auto it = container.find(key);
108 
109  if (it != container.end()) {
110  return it->second;
111  } else {
112  return defaultValue;
113  }
114 }
115 
116 /**
117  * A utility function enabling the creation of a vector with a fixed set of
118  * elements within a single expression. This is the base case covering empty
119  * vectors.
120  */
121 template <typename T>
122 std::vector<T> toVector() {
123  return std::vector<T>();
124 }
125 
126 /**
127  * A utility function enabling the creation of a vector with a fixed set of
128  * elements within a single expression. This is the step case covering vectors
129  * of arbitrary length.
130  */
131 template <typename T, typename... R>
132 std::vector<T> toVector(const T& first, const R&... rest) {
133  return {first, rest...};
134 }
135 
136 /**
137  * A utility function enabling the creation of a vector of pointers.
138  */
139 template <typename T>
140 std::vector<T*> toPtrVector(const std::vector<std::unique_ptr<T>>& v) {
141  std::vector<T*> res;
142  for (auto& e : v) {
143  res.push_back(e.get());
144  }
145  return res;
146 }
147 
148 /**
149  * Applies a function to each element of a vector and returns the results.
150  */
151 template <typename A, typename F /* : A -> B */>
152 auto map(const std::vector<A>& xs, F&& f) {
153  std::vector<decltype(f(xs[0]))> ys;
154  ys.reserve(xs.size());
155  for (auto&& x : xs) {
156  ys.emplace_back(f(x));
157  }
158  return ys;
159 }
160 
161 // -------------------------------------------------------------------------------
162 // Cloning Utilities
163 // -------------------------------------------------------------------------------
164 
165 template <typename A>
166 auto clone(const std::vector<A*>& xs) {
167  std::vector<std::unique_ptr<A>> ys;
168  ys.reserve(xs.size());
169  for (auto&& x : xs) {
170  ys.emplace_back(x ? std::unique_ptr<A>(x->clone()) : nullptr);
171  }
172  return ys;
173 }
174 
175 template <typename A>
176 auto clone(const std::vector<std::unique_ptr<A>>& xs) {
177  std::vector<std::unique_ptr<A>> ys;
178  ys.reserve(xs.size());
179  for (auto&& x : xs) {
180  ys.emplace_back(x ? std::unique_ptr<A>(x->clone()) : nullptr);
181  }
182  return ys;
183 }
184 
185 // -------------------------------------------------------------
186 // Iterators
187 // -------------------------------------------------------------
188 
189 /**
190  * A wrapper for an iterator obtaining pointers of a certain type,
191  * dereferencing values before forwarding them to the consumer.
192  *
193  * @tparam Iter ... the type of wrapped iterator
194  * @tparam T ... the value to be accessed by the resulting iterator
195  */
197 struct IterDerefWrapper : public std::iterator<std::forward_iterator_tag, T> {
198  /* The nested iterator. */
199  Iter iter;
200 
201 public:
202  // some constructors
203  IterDerefWrapper() = default;
204  IterDerefWrapper(const Iter& iter) : iter(iter) {}
205 
206  // defaulted copy and move constructors
207  IterDerefWrapper(const IterDerefWrapper&) = default;
208  IterDerefWrapper(IterDerefWrapper&&) = default;
209 
210  // default assignment operators
211  IterDerefWrapper& operator=(const IterDerefWrapper&) = default;
213 
214  /* The equality operator as required by the iterator concept. */
215  bool operator==(const IterDerefWrapper& other) const {
216  return iter == other.iter;
217  }
218 
219  /* The not-equality operator as required by the iterator concept. */
220  bool operator!=(const IterDerefWrapper& other) const {
221  return iter != other.iter;
222  }
223 
224  /* The deref operator as required by the iterator concept. */
225  const T& operator*() const {
226  return **iter;
227  }
228 
229  /* Support for the pointer operator. */
230  const T* operator->() const {
231  return &(**iter);
232  }
233 
234  /* The increment operator as required by the iterator concept. */
236  ++iter;
237  return *this;
238  }
239 };
240 
241 /**
242  * A factory function enabling the construction of a dereferencing
243  * iterator utilizing the automated deduction of template parameters.
244  */
245 template <typename Iter>
246 IterDerefWrapper<Iter> derefIter(const Iter& iter) {
247  return IterDerefWrapper<Iter>(iter);
248 }
249 
250 /**
251  * An iterator to be utilized if there is only a single element to iterate over.
252  */
253 template <typename T>
254 class SingleValueIterator : public std::iterator<std::forward_iterator_tag, T> {
255  T value;
256 
257  bool end = true;
258 
259 public:
260  SingleValueIterator() = default;
261 
262  SingleValueIterator(const T& value) : value(value), end(false) {}
263 
264  // a copy constructor
265  SingleValueIterator(const SingleValueIterator& other) = default;
266 
267  // an assignment operator
269 
270  // the equality operator as required by the iterator concept
271  bool operator==(const SingleValueIterator& other) const {
272  // only equivalent if pointing to the end
273  return end && other.end;
274  }
275 
276  // the not-equality operator as required by the iterator concept
277  bool operator!=(const SingleValueIterator& other) const {
278  return !(*this == other);
279  }
280 
281  // the deref operator as required by the iterator concept
282  const T& operator*() const {
283  return value;
284  }
285 
286  // support for the pointer operator
287  const T* operator->() const {
288  return &value;
289  }
290 
291  // the increment operator as required by the iterator concept
293  end = true;
294  return *this;
295  }
296 };
297 
298 // -------------------------------------------------------------
299 // Ranges
300 // -------------------------------------------------------------
301 
302 /**
303  * A utility class enabling representation of ranges by pairing
304  * two iterator instances marking lower and upper boundaries.
305  */
306 template <typename Iter>
307 struct range {
308  // the lower and upper boundary
309  Iter a, b;
310 
311  // a constructor accepting a lower and upper boundary
312  range(Iter a, Iter b) : a(std::move(a)), b(std::move(b)) {}
313 
314  // default copy / move and assignment support
315  range(const range&) = default;
316  range(range&&) = default;
317  range& operator=(const range&) = default;
318 
319  // get the lower boundary (for for-all loop)
320  Iter& begin() {
321  return a;
322  }
323  const Iter& begin() const {
324  return a;
325  }
326 
327  // get the upper boundary (for for-all loop)
328  Iter& end() {
329  return b;
330  }
331  const Iter& end() const {
332  return b;
333  }
334 
335  // emptiness check
336  bool empty() const {
337  return a == b;
338  }
339 
340  // splits up this range into the given number of partitions
341  std::vector<range> partition(int np = 100) {
342  // obtain the size
343  int n = 0;
344  for (auto i = a; i != b; ++i) {
345  n++;
346  }
347 
348  // split it up
349  auto s = n / np;
350  auto r = n % np;
351  std::vector<range> res;
352  res.reserve(np);
353  auto cur = a;
354  auto last = cur;
355  int i = 0;
356  int p = 0;
357  while (cur != b) {
358  ++cur;
359  i++;
360  if (i >= (s + (p < r ? 1 : 0))) {
361  res.push_back({last, cur});
362  last = cur;
363  p++;
364  i = 0;
365  }
366  }
367  if (cur != last) {
368  res.push_back({last, cur});
369  }
370  return res;
371  }
372 };
373 
374 /**
375  * A utility function enabling the construction of ranges
376  * without explicitly specifying the iterator type.
377  *
378  * @tparam Iter .. the iterator type
379  * @param a .. the lower boundary
380  * @param b .. the upper boundary
381  */
382 template <typename Iter>
383 range<Iter> make_range(const Iter& a, const Iter& b) {
384  return range<Iter>(a, b);
385 }
386 
387 // -------------------------------------------------------------------------------
388 // Equality Utilities
389 // -------------------------------------------------------------------------------
390 
391 /**
392  * Cast the values, from baseType to toType and compare using ==. (if casting fails -> return false.)
393  *
394  * @tparam baseType, initial Type of values
395  * @tparam toType, type where equality comparison takes place.
396  */
397 template <typename toType, typename baseType>
398 bool castEq(const baseType* left, const baseType* right) {
399  if (auto castedLeft = dynamic_cast<const toType*>(left)) {
400  if (auto castedRight = dynamic_cast<const toType*>(right)) {
401  return castedLeft == castedRight;
402  }
403  }
404  return false;
405 }
406 
407 /**
408  * A functor class supporting the values pointers are pointing to.
409  */
410 template <typename T>
411 struct comp_deref {
412  bool operator()(const T& a, const T& b) const {
413  if (a == nullptr) {
414  return false;
415  }
416  if (b == nullptr) {
417  return false;
418  }
419  return *a == *b;
420  }
421 };
422 
423 /**
424  * A function testing whether two containers are equal with the given Comparator.
425  */
426 template <typename Container, typename Comparator>
427 bool equal_targets(const Container& a, const Container& b, const Comparator& comp) {
428  // check reference
429  if (&a == &b) {
430  return true;
431  }
432 
433  // check size
434  if (a.size() != b.size()) {
435  return false;
436  }
437 
438  // check content
439  return std::equal(a.begin(), a.end(), b.begin(), comp);
440 }
441 
442 /**
443  * A function testing whether two containers of pointers are referencing equivalent
444  * targets.
445  */
446 template <typename T, template <typename...> class Container>
447 bool equal_targets(const Container<T*>& a, const Container<T*>& b) {
448  return equal_targets(a, b, comp_deref<T*>());
449 }
450 
451 /**
452  * A function testing whether two containers of unique pointers are referencing equivalent
453  * targets.
454  */
455 template <typename T, template <typename...> class Container>
456 bool equal_targets(const Container<std::unique_ptr<T>>& a, const Container<std::unique_ptr<T>>& b) {
457  return equal_targets(a, b, comp_deref<std::unique_ptr<T>>());
458 }
459 
460 /**
461  * A function testing whether two maps of unique pointers are referencing to equivalent
462  * targets.
463  */
464 template <typename Key, typename Value>
465 bool equal_targets(
466  const std::map<Key, std::unique_ptr<Value>>& a, const std::map<Key, std::unique_ptr<Value>>& b) {
467  auto comp = comp_deref<std::unique_ptr<Value>>();
468  return equal_targets(
469  a, b, [&comp](auto& a, auto& b) { return a.first == b.first && comp(a.second, b.second); });
470 }
471 
472 } // namespace souffle
souffle::range::range
range(Iter a, Iter b)
Definition: ContainerUtil.h:318
souffle::range
A utility class enabling representation of ranges by pairing two iterator instances marking lower and...
Definition: ContainerUtil.h:313
souffle::IterDerefWrapper::operator=
IterDerefWrapper & operator=(const IterDerefWrapper &)=default
souffle::range::end
Iter & end()
Definition: ContainerUtil.h:334
souffle::comp_deref::operator()
bool operator()(const T &a, const T &b) const
Definition: ContainerUtil.h:418
souffle::reverse::begin
auto begin()
Definition: ContainerUtil.h:61
souffle::reverse::iterable
A & iterable
Definition: ContainerUtil.h:59
souffle::range::operator=
range & operator=(const range &)=default
souffle::contains
bool contains(const C &container, const typename C::value_type &element)
A utility to check generically whether a given element is contained in a given container.
Definition: ContainerUtil.h:75
souffle::range::b
Iter b
Definition: ContainerUtil.h:315
Comparator
souffle::SingleValueIterator::operator++
SingleValueIterator & operator++()
Definition: ContainerUtil.h:298
e
l j a showGridBackground &&c b raw series this eventEmitter e
Definition: htmlJsChartistMin.h:15
souffle::IterDerefWrapper::operator==
bool operator==(const IterDerefWrapper &other) const
Definition: ContainerUtil.h:221
souffle::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
souffle::map
auto map(const std::vector< A > &xs, F &&f)
Applies a function to each element of a vector and returns the results.
Definition: ContainerUtil.h:158
souffle::IterDerefWrapper::IterDerefWrapper
IterDerefWrapper()=default
souffle::SingleValueIterator::operator*
const T & operator*() const
Definition: ContainerUtil.h:288
souffle::castEq
bool castEq(const baseType *left, const baseType *right)
Cast the values, from baseType to toType and compare using ==.
Definition: ContainerUtil.h:404
souffle::reverse::reverse
reverse(A &iterable)
Definition: ContainerUtil.h:58
souffle::SingleValueIterator
An iterator to be utilized if there is only a single element to iterate over.
Definition: ContainerUtil.h:260
n
var n
Definition: htmlJsChartistMin.h:15
souffle::derefIter
IterDerefWrapper< Iter > derefIter(const Iter &iter)
A factory function enabling the construction of a dereferencing iterator utilizing the automated dedu...
Definition: ContainerUtil.h:252
souffle::SingleValueIterator::end
bool end
Definition: ContainerUtil.h:263
souffle::IterDerefWrapper::operator!=
bool operator!=(const IterDerefWrapper &other) const
Definition: ContainerUtil.h:226
souffle::getOr
C::mapped_type const & getOr(const C &container, typename C::key_type key, const typename C::mapped_type &defaultValue)
Get value for a given key; if not found, return default value.
Definition: ContainerUtil.h:111
souffle::reverse::end
auto end()
Definition: ContainerUtil.h:65
souffle::clone
auto clone(const std::vector< A * > &xs)
Definition: ContainerUtil.h:172
souffle::mk
Own< A > mk(Args &&... xs)
Definition: ContainerUtil.h:48
i
size_t i
Definition: json11.h:663
souffle::reverse
Use to range-for iterate in reverse.
Definition: ContainerUtil.h:57
souffle::SingleValueIterator::SingleValueIterator
SingleValueIterator()=default
souffle::make_range
range< Iter > make_range(const Iter &a, const Iter &b)
A utility function enabling the construction of ranges without explicitly specifying the iterator typ...
Definition: ContainerUtil.h:389
souffle::equal_targets
bool equal_targets(const Container &a, const Container &b, const Comparator &comp)
A function testing whether two containers are equal with the given Comparator.
Definition: ContainerUtil.h:433
souffle::IterDerefWrapper::operator->
const T * operator->() const
Definition: ContainerUtil.h:236
souffle::IterDerefWrapper
A wrapper for an iterator obtaining pointers of a certain type, dereferencing values before forwardin...
Definition: ContainerUtil.h:203
souffle::SingleValueIterator::operator=
SingleValueIterator & operator=(const SingleValueIterator &other)=default
souffle::toVector
std::vector< T > toVector()
A utility function enabling the creation of a vector with a fixed set of elements within a single exp...
Definition: ContainerUtil.h:128
souffle::range::partition
std::vector< range > partition(int np=100)
Definition: ContainerUtil.h:347
souffle::IterDerefWrapper::operator*
const T & operator*() const
Definition: ContainerUtil.h:231
souffle::getIf
C::value_type getIf(const C &container, std::function< bool(const typename C::value_type)> pred)
Returns the first element in a container that satisfies a given predicate, nullptr otherwise.
Definition: ContainerUtil.h:101
souffle::range::begin
Iter & begin()
Definition: ContainerUtil.h:326
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::range::a
Iter a
Definition: ContainerUtil.h:315
souffle::SingleValueIterator::operator->
const T * operator->() const
Definition: ContainerUtil.h:293
souffle::SingleValueIterator::value
T value
Definition: ContainerUtil.h:261
souffle::IterDerefWrapper::iter
Iter iter
Definition: ContainerUtil.h:205
souffle::SingleValueIterator::operator!=
bool operator!=(const SingleValueIterator &other) const
Definition: ContainerUtil.h:283
souffle
Definition: AggregateOp.h:25
souffle::IterDerefWrapper::operator++
IterDerefWrapper & operator++()
Definition: ContainerUtil.h:241
souffle::comp_deref
A functor class supporting the values pointers are pointing to.
Definition: ContainerUtil.h:417
souffle::SingleValueIterator::operator==
bool operator==(const SingleValueIterator &other) const
Definition: ContainerUtil.h:277
souffle::toPtrVector
std::vector< T * > toPtrVector(const std::vector< std::unique_ptr< T >> &v)
A utility function enabling the creation of a vector of pointers.
Definition: ContainerUtil.h:146
souffle::VecOwn
std::vector< Own< A > > VecOwn
Definition: ContainerUtil.h:45
std::type
ElementType type
Definition: span.h:640
p
a horizontalBars(j=m=void 0===a.axisX.type?new c.AutoScaleAxis(c.Axis.units.x, b.normalized.series, o, c.extend({}, a.axisX,{highLow:d, referenceValue:0})):a.axisX.type.call(c, c.Axis.units.x, b.normalized.series, o, c.extend({}, a.axisX,{highLow:d, referenceValue:0})), l=n=void 0===a.axisY.type?new c.StepAxis(c.Axis.units.y, b.normalized.series, o,{ticks:k}):a.axisY.type.call(c, c.Axis.units.y, b.normalized.series, o, a.axisY)) var p
Definition: htmlJsChartistMin.h:15
souffle::range::empty
bool empty() const
Definition: ContainerUtil.h:342