souffle  2.0.2-371-g6315b36
EquivalenceRelation.h
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2017 The Souffle Developers. 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 EquivalenceRelation.h
12  *
13  * Defines a binary relation interface to be used with Souffle as a relational store.
14  * Pairs inserted into this relation implicitly store a reflexive, symmetric, and transitive relation
15  * with each other.
16  *
17  ***********************************************************************/
18 
19 #pragma once
20 
21 #include "souffle/RamTypes.h"
27 #include <atomic>
28 #include <cassert>
29 #include <cstddef>
30 #include <functional>
31 #include <iostream>
32 #include <iterator>
33 #include <set>
34 #include <shared_mutex>
35 #include <stdexcept>
36 #include <tuple>
37 #include <utility>
38 #include <vector>
39 
40 namespace souffle {
41 template <typename TupleType>
42 class EquivalenceRelation {
43  using value_type = typename TupleType::value_type;
44 
45  // mapping from representative to disjoint set
46  // just a cache, essentially, used for iteration over
48  using StatesBucket = StatesList*;
49  using StorePair = std::pair<value_type, StatesBucket>;
52 
53 public:
54  using element_type = TupleType;
55 
59  }
60 
61  /**
62  * A collection of operation hints speeding up some of the involved operations
63  * by exploiting temporal locality.
64  * Unused in this class, as there is no speedup to be gained.
65  * This is just defined as the class expects it.
66  */
67  struct operation_hints {
68  // resets all hints (to be triggered e.g. when deleting nodes)
69  void clear() {}
70  };
71 
72  /**
73  * Insert the two values symbolically as a binary relation
74  * @param x node to be added/paired
75  * @param y node to be added/paired
76  * @return true if the pair is new to the data structure
77  */
78  bool insert(value_type x, value_type y) {
79  operation_hints z;
80  return insert(x, y, z);
81  };
82 
83  /**
84  * Insert the tuple symbolically.
85  * @param tuple The tuple to be inserted
86  * @return true if the tuple is new to the data structure
87  */
88  bool insert(const TupleType& tuple) {
89  operation_hints hints;
90  return insert(tuple[0], tuple[1], hints);
91  };
92 
93  /**
94  * Insert the two values symbolically as a binary relation
95  * @param x node to be added/paired
96  * @param y node to be added/paired
97  * @param z the hints to where the pair should be inserted (not applicable atm)
98  * @return true if the pair is new to the data structure
99  */
100  bool insert(value_type x, value_type y, operation_hints) {
101  // indicate that iterators will have to generate on request
102  this->statesMapStale.store(true, std::memory_order_relaxed);
103  bool retval = contains(x, y);
105  return retval;
106  }
107 
108  /**
109  * inserts all nodes from the other relation into this one
110  * @param other the binary relation from which to add elements from
111  */
112  void insertAll(const EquivalenceRelation<TupleType>& other) {
113  other.genAllDisjointSetLists();
114 
115  // iterate over partitions at a time
116  for (typename StatesMap::chunk it : other.equivalencePartition.getChunks(MAX_THREADS)) {
117  for (auto& p : it) {
118  value_type rep = p.first;
119  StatesList& pl = *p.second;
120  const size_t ksize = pl.size();
121  for (size_t i = 0; i < ksize; ++i) {
122  this->sds.unionNodes(rep, pl.get(i));
123  }
124  }
125  }
126  // invalidate iterators unconditionally
127  this->statesMapStale.store(true, std::memory_order_relaxed);
128  }
129 
130  /**
131  * Extend this relation with another relation, expanding this equivalence relation
132  * The supplied relation is the old knowledge, whilst this relation only contains
133  * explicitly new knowledge. After this operation the "implicitly new tuples" are now
134  * explicitly inserted this relation.
135  */
136  void extend(const EquivalenceRelation<TupleType>& other) {
137  // nothing to extend if there's no new/original knowledge
138  if (other.size() == 0 || this->size() == 0) return;
139 
140  this->genAllDisjointSetLists();
141  other.genAllDisjointSetLists();
142 
143  std::set<value_type> repsCovered;
144 
145  // find all the disjoint sets that need to be added to this relation
146  // that exist in other (and exist in this)
147  {
148  auto it = this->sds.sparseToDenseMap.begin();
149  auto end = this->sds.sparseToDenseMap.end();
150  value_type el;
151  for (; it != end; ++it) {
152  std::tie(el, std::ignore) = *it;
153  if (other.containsElement(el)) {
154  value_type rep = other.sds.findNode(el);
155  if (repsCovered.count(rep) == 0) {
156  repsCovered.emplace(rep);
157  }
158  }
159  }
160  }
161 
162  // add the intersecting dj sets into this one
163  {
164  value_type el;
165  value_type rep;
166  auto it = other.sds.sparseToDenseMap.begin();
167  auto end = other.sds.sparseToDenseMap.end();
168  for (; it != end; ++it) {
169  std::tie(el, std::ignore) = *it;
170  rep = other.sds.findNode(el);
171  if (repsCovered.count(rep) != 0) {
172  this->insert(el, rep);
173  }
174  }
175  }
176  }
177 
178  /**
179  * Returns whether there exists a pair with these two nodes
180  * @param x front of pair
181  * @param y back of pair
182  */
183  bool contains(value_type x, value_type y) const {
184  return sds.contains(x, y);
185  }
186 
187  /**
188  * Returns whether there exists given tuple.
189  * @param tuple The tuple to search for.
190  */
191  bool contains(const TupleType& tuple, operation_hints&) const {
192  return contains(tuple[0], tuple[1]);
193  };
194 
195  bool contains(const TupleType& tuple) const {
196  return contains(tuple[0], tuple[1]);
197  };
198 
199  void emptyPartition() const {
200  // delete the beautiful values inside (they're raw ptrs, so they need to be.)
201  for (auto& pair : equivalencePartition) {
202  delete pair.second;
203  }
204  // invalidate it my dude
205  this->statesMapStale.store(true, std::memory_order_relaxed);
206 
208  }
209 
210  /**
211  * Empty the relation
212  */
213  void clear() {
214  statesLock.lock();
215 
216  sds.clear();
217  emptyPartition();
218 
219  statesLock.unlock();
220  }
221 
222  /**
223  * Size of relation
224  * @return the sum of the number of pairs per disjoint set
225  */
226  size_t size() const {
228 
229  statesLock.lock_shared();
230 
231  size_t retVal = 0;
232  for (auto& e : this->equivalencePartition) {
233  const size_t s = e.second->size();
234  retVal += s * s;
235  }
236 
237  statesLock.unlock_shared();
238  return retVal;
239  }
240 
241  // an almighty iterator for several types of iteration.
242  // Unfortunately, subclassing isn't an option with souffle
243  // - we don't deal with pointers (so no virtual)
244  // - and a single iter type is expected (see Relation::iterator e.g.) (i think)
245  class iterator {
246  public:
247  typedef std::forward_iterator_tag iterator_category;
248  using value_type = TupleType;
249  using difference_type = ptrdiff_t;
250  using pointer = value_type*;
251  using reference = value_type&;
252 
253  // one iterator for signalling the end (simplifies)
254  explicit iterator(const EquivalenceRelation* br, bool /* signalIsEndIterator */)
255  : br(br), isEndVal(true){};
256 
257  explicit iterator(const EquivalenceRelation* br)
258  : br(br), ityp(IterType::ALL), djSetMapListIt(br->equivalencePartition.begin()),
260  // no need to fast forward if this iterator is empty
262  isEndVal = true;
263  return;
264  }
265  // grab the pointer to the list, and make it our current list
266  djSetList = (*djSetMapListIt).second;
267  assert(djSetList->size() != 0);
268 
269  updateAnterior();
271  }
272 
273  // WITHIN: iterator for everything within the same DJset (used for EquivalenceRelation.partition())
274  explicit iterator(const EquivalenceRelation* br, const StatesBucket within)
275  : br(br), ityp(IterType::WITHIN), djSetList(within) {
276  // empty dj set
277  if (djSetList->size() == 0) {
278  isEndVal = true;
279  }
280 
281  updateAnterior();
282  updatePosterior();
283  }
284 
285  // ANTERIOR: iterator that yields all (former, _) \in djset(former) (djset(former) === within)
286  explicit iterator(const EquivalenceRelation* br, const typename TupleType::value_type former,
287  const StatesBucket within)
288  : br(br), ityp(IterType::ANTERIOR), djSetList(within) {
289  if (djSetList->size() == 0) {
290  isEndVal = true;
291  }
292 
293  setAnterior(former);
294  updatePosterior();
295  }
296 
297  // ANTPOST: iterator that yields all (former, latter) \in djset(former), (djset(former) ==
298  // djset(latter) == within)
299  explicit iterator(const EquivalenceRelation* br, const typename TupleType::value_type former,
300  typename TupleType::value_type latter, const StatesBucket within)
301  : br(br), ityp(IterType::ANTPOST), djSetList(within) {
302  if (djSetList->size() == 0) {
303  isEndVal = true;
304  }
305 
306  setAnterior(former);
307  setPosterior(latter);
308  }
309 
310  /** explicit set first half of cPair */
311  inline void setAnterior(const typename TupleType::value_type a) {
312  this->cPair[0] = a;
313  }
314 
315  /** quick update to whatever the current index is pointing to */
316  inline void updateAnterior() {
317  this->cPair[0] = this->djSetList->get(this->cAnteriorIndex);
318  }
319 
320  /** explicit set second half of cPair */
321  inline void setPosterior(const typename TupleType::value_type b) {
322  this->cPair[1] = b;
323  }
324 
325  /** quick update to whatever the current index is pointing to */
326  inline void updatePosterior() {
327  this->cPair[1] = this->djSetList->get(this->cPosteriorIndex);
328  }
329 
330  // copy ctor
331  iterator(const iterator& other) = default;
332  // move ctor
333  iterator(iterator&& other) = default;
334  // assign iter
335  iterator& operator=(const iterator& other) = default;
336 
337  bool operator==(const iterator& other) const {
338  if (isEndVal && other.isEndVal) return br == other.br;
339  return isEndVal == other.isEndVal && cPair == other.cPair;
340  }
341 
342  bool operator!=(const iterator& other) const {
343  return !((*this) == other);
344  }
345 
346  const TupleType& operator*() const {
347  return cPair;
348  }
349 
350  const TupleType* operator->() const {
351  return &cPair;
352  }
353 
354  /* pre-increment */
355  iterator& operator++() {
356  if (isEndVal) {
357  throw std::out_of_range("error: incrementing an out of range iterator");
358  }
359 
360  switch (ityp) {
361  case IterType::ALL:
362  // move posterior along one
363  // see if we can't move the posterior along
364  if (++cPosteriorIndex == djSetList->size()) {
365  // move anterior along one
366  // see if we can't move the anterior along one
367  if (++cAnteriorIndex == djSetList->size()) {
368  // move the djset it along one
369  // see if we can't move it along one (we're at the end)
370  if (++djSetMapListIt == djSetMapListEnd) {
371  isEndVal = true;
372  return *this;
373  }
374 
375  // we can't iterate along this djset if it is empty
376  djSetList = (*djSetMapListIt).second;
377  if (djSetList->size() == 0) {
378  throw std::out_of_range("error: encountered a zero size djset");
379  }
380 
381  // update our cAnterior and cPosterior
382  cAnteriorIndex = 0;
383  cPosteriorIndex = 0;
384  updateAnterior();
385  updatePosterior();
386  }
387 
388  // we moved our anterior along one
389  updateAnterior();
390 
391  cPosteriorIndex = 0;
392  updatePosterior();
393  }
394  // we just moved our posterior along one
395  updatePosterior();
396 
397  break;
398  case IterType::ANTERIOR:
399  // step posterior along one, and if we can't, then we're done.
400  if (++cPosteriorIndex == djSetList->size()) {
401  isEndVal = true;
402  return *this;
403  }
404  updatePosterior();
405 
406  break;
407  case IterType::ANTPOST:
408  // fixed anterior and posterior literally only points to one, so if we increment, its the
409  // end
410  isEndVal = true;
411  break;
412  case IterType::WITHIN:
413  // move posterior along one
414  // see if we can't move the posterior along
415  if (++cPosteriorIndex == djSetList->size()) {
416  // move anterior along one
417  // see if we can't move the anterior along one
418  if (++cAnteriorIndex == djSetList->size()) {
419  isEndVal = true;
420  return *this;
421  }
422 
423  // we moved our anterior along one
424  updateAnterior();
425 
426  cPosteriorIndex = 0;
427  updatePosterior();
428  }
429  // we just moved our posterior along one
430  updatePosterior();
431  break;
432  }
433 
434  return *this;
435  }
436 
437  private:
438  const EquivalenceRelation* br = nullptr;
439  // special tombstone value to notify that this iter represents the end
440  bool isEndVal = false;
441 
442  // all the different types of iterator this can be
443  enum IterType { ALL, ANTERIOR, ANTPOST, WITHIN };
444  IterType ityp;
445 
446  TupleType cPair;
447 
448  // the disjoint set that we're currently iterating through
450  typename StatesMap::iterator djSetMapListIt;
451  typename StatesMap::iterator djSetMapListEnd;
452 
453  // used for ALL, and POSTERIOR (just a current index in the cList)
454  size_t cAnteriorIndex = 0;
455  // used for ALL, and ANTERIOR (just a current index in the cList)
456  size_t cPosteriorIndex = 0;
457  };
458 
459 public:
460  /**
461  * iterator pointing to the beginning of the tuples, with no restrictions
462  * @return the iterator that corresponds to the beginning of the binary relation
463  */
464  iterator begin() const {
466  return iterator(this);
467  }
468 
469  /**
470  * iterator pointing to the end of the tuples
471  * @return the iterator which represents the end of the binary rel
472  */
473  iterator end() const {
474  return iterator(this, true);
475  }
476 
477  /**
478  * Obtains a range of elements matching the prefix of the given entry up to
479  * levels elements.
480  *
481  * @tparam levels the length of the requested matching prefix
482  * @param entry the entry to be looking for
483  * @return the corresponding range of matching elements
484  */
485  template <unsigned levels>
486  range<iterator> getBoundaries(const TupleType& entry) const {
487  operation_hints ctxt;
488  return getBoundaries<levels>(entry, ctxt);
489  }
490 
491  /**
492  * Obtains a range of elements matching the prefix of the given entry up to
493  * levels elements. A operation context may be provided to exploit temporal
494  * locality.
495  *
496  * @tparam levels the length of the requested matching prefix
497  * @param entry the entry to be looking for
498  * @param ctxt the operation context to be utilized
499  * @return the corresponding range of matching elements
500  */
501  template <unsigned levels>
502  range<iterator> getBoundaries(const TupleType& entry, operation_hints&) const {
503  // if nothing is bound => just use begin and end
504  if (levels == 0) return make_range(begin(), end());
505 
506  // as disjoint set is exactly two args (equiv relation)
507  // we only need to handle these cases
508 
509  if (levels == 1) {
510  // need to test if the entry actually exists
511  if (!sds.nodeExists(entry[0])) return make_range(end(), end());
512 
513  // return an iterator over all (entry[0], _)
514  return make_range(anteriorIt(entry[0]), end());
515  }
516 
517  if (levels == 2) {
518  // need to test if the entry actually exists
519  if (!sds.contains(entry[0], entry[1])) return make_range(end(), end());
520 
521  // if so return an iterator containing exactly that node
522  return make_range(antpostit(entry[0], entry[1]), end());
523  }
524 
525  std::cerr << "invalid state, cannot search for >2 arg start point in getBoundaries, in 2 arg tuple "
526  "store\n";
527  throw "invalid state, cannot search for >2 arg start point in getBoundaries, in 2 arg tuple store";
528 
529  return make_range(end(), end());
530  }
531 
532  /**
533  * Act similar to getBoundaries. But non-static.
534  * This function should be used ONLY by interpreter,
535  * and its behavior is tightly coupling with InterpreterIndex.
536  * Do Not rely on this interface outside the interpreter.
537  *
538  * @param entry the entry to be looking for
539  * @return the corresponding range of matching elements
540  */
541  iterator lower_bound(const TupleType& entry, operation_hints&) const {
542  if (entry[0] == MIN_RAM_SIGNED && entry[1] == MIN_RAM_SIGNED) {
543  // Return an iterator over all tuples.
544  return begin();
545  }
546 
547  if (entry[0] != MIN_RAM_SIGNED && entry[1] == MIN_RAM_SIGNED) {
548  // Return an iterator over all (entry[0], _)
549 
550  if (!sds.nodeExists(entry[0])) {
551  return end();
552  }
553  return anteriorIt(entry[0]);
554  }
555 
556  if (entry[0] != MIN_RAM_SIGNED && entry[1] != MIN_RAM_SIGNED) {
557  // Return an iterator point to the exact same node.
558 
559  if (!sds.contains(entry[0], entry[1])) {
560  return end();
561  }
562  return antpostit(entry[0], entry[1]);
563  }
564 
565  return end();
566  }
567 
568  iterator lower_bound(const TupleType& entry) const {
569  operation_hints hints;
570  return lower_bound(entry, hints);
571  }
572 
573  /**
574  * This function is only here in order to unify interfaces in InterpreterIndex.
575  * Unlike the name suggestes, it omit the arguments and simply return the end
576  * iterator of the relation.
577  *
578  * @param omitted
579  * @return the end iterator.
580  */
581  iterator upper_bound(const TupleType&, operation_hints&) const {
582  return end();
583  }
584 
585  iterator upper_bound(const TupleType& entry) const {
586  operation_hints hints;
587  return upper_bound(entry, hints);
588  }
589 
590  /**
591  * Check emptiness.
592  */
593  bool empty() const {
594  return this->size() == 0;
595  }
596 
597  /**
598  * Creates an iterator that generates all pairs (A, X)
599  * for a given A, and X are elements within A's disjoint set.
600  * @param anteriorVal: The first value of the tuple to be generated for
601  * @return the iterator representing this.
602  */
603  iterator anteriorIt(value_type anteriorVal) const {
605 
606  // locate the blocklist that the anterior val resides in
607  auto found = equivalencePartition.find({sds.findNode(anteriorVal), nullptr});
608  assert(found != equivalencePartition.end() && "iterator called on partition that doesn't exist");
609 
610  return iterator(static_cast<const EquivalenceRelation*>(this),
611  static_cast<const value_type>(anteriorVal), static_cast<const StatesBucket>((*found).second));
612  }
613 
614  /**
615  * Creates an iterator that generates the pair (A, B)
616  * for a given A and B. If A and B don't exist, or aren't in the same set,
617  * then the end() iterator is returned.
618  * @param anteriorVal: the A value of the tuple
619  * @param posteriorVal: the B value of the tuple
620  * @return the iterator representing this
621  */
622  iterator antpostit(value_type anteriorVal, value_type posteriorVal) const {
623  // obv if they're in diff sets, then iteration for this pair just ends.
624  if (!sds.sameSet(anteriorVal, posteriorVal)) return end();
625 
627 
628  // locate the blocklist that the val resides in
629  auto found = equivalencePartition.find({sds.findNode(posteriorVal), nullptr});
630  assert(found != equivalencePartition.end() && "iterator called on partition that doesn't exist");
631 
632  return iterator(this, anteriorVal, posteriorVal, (*found).second);
633  }
634 
635  /**
636  * Begin an iterator over all pairs within a single disjoint set - This is used for partition().
637  * @param rep the representative of (or element within) a disjoint set of which to generate all pairs
638  * @return an iterator that will generate all pairs within the disjoint set
639  */
640  iterator closure(value_type rep) const {
642 
643  // locate the blocklist that the val resides in
644  auto found = equivalencePartition.find({sds.findNode(rep), nullptr});
645  return iterator(this, (*found).second);
646  }
647 
648  /**
649  * Generate an approximate number of iterators for parallel iteration
650  * The iterators returned are not necessarily equal in size, but in practise are approximately similarly
651  * sized
652  * Depending on the structure of the data, there can be more or less partitions returned than requested.
653  * @param chunks the number of requested partitions
654  * @return a list of the iterators as ranges
655  */
656  std::vector<souffle::range<iterator>> partition(size_t chunks) const {
657  // generate all reps
659 
660  size_t numPairs = this->size();
661  if (numPairs == 0) return {};
662  if (numPairs == 1 || chunks <= 1) return {souffle::make_range(begin(), end())};
663 
664  // if there's more dj sets than requested chunks, then just return an iter per dj set
665  std::vector<souffle::range<iterator>> ret;
666  if (chunks <= equivalencePartition.size()) {
667  for (auto& p : equivalencePartition) {
668  ret.push_back(souffle::make_range(closure(p.first), end()));
669  }
670  return ret;
671  }
672 
673  // keep it simple stupid
674  // just go through and if the size of the binrel is > numpairs/chunks, then generate an anteriorIt for
675  // each
676  const size_t perchunk = numPairs / chunks;
677  for (const auto& itp : equivalencePartition) {
678  const size_t s = itp.second->size();
679  if (s * s > perchunk) {
680  for (const auto& i : *itp.second) {
681  ret.push_back(souffle::make_range(anteriorIt(i), end()));
682  }
683  } else {
684  ret.push_back(souffle::make_range(closure(itp.first), end()));
685  }
686  }
687 
688  return ret;
689  }
690 
691  iterator find(const TupleType&, operation_hints&) const {
692  throw std::runtime_error("error: find() is not compatible with equivalence relations");
693  return begin();
694  }
695 
696  iterator find(const TupleType& t) const {
697  operation_hints context;
698  return find(t, context);
699  }
700 
701 protected:
702  bool containsElement(value_type e) const {
703  return this->sds.nodeExists(e);
704  }
705 
706 private:
707  // marked as mutable due to difficulties with the const enforcement via the Relation API
708  // const operations *may* safely change internal state (i.e. collapse djset forest)
710 
711  // read/write lock on equivalencePartition
712  mutable std::shared_mutex statesLock;
713 
715  // whether the cache is stale
716  mutable std::atomic<bool> statesMapStale;
717 
718  /**
719  * Generate a cache of the sets such that they can be iterated over efficiently.
720  * Each set is partitioned into a PiggyList.
721  */
722  void genAllDisjointSetLists() const {
723  statesLock.lock();
724 
725  // no need to generate again, already done.
726  if (!this->statesMapStale.load(std::memory_order_acquire)) {
727  statesLock.unlock();
728  return;
729  }
730 
731  // btree version
733 
734  size_t dSetSize = this->sds.ds.a_blocks.size();
735  for (size_t i = 0; i < dSetSize; ++i) {
736  typename TupleType::value_type sparseVal = this->sds.toSparse(i);
737  parent_t rep = this->sds.findNode(sparseVal);
738 
739  StorePair p = {static_cast<value_type>(rep), nullptr};
740  StatesList* mapList = equivalencePartition.insert(p, [&](StorePair& sp) {
741  auto* r = new StatesList(1);
742  sp.second = r;
743  return r;
744  });
745  mapList->append(sparseVal);
746  }
747 
748  statesMapStale.store(false, std::memory_order_release);
749  statesLock.unlock();
750  }
751 };
752 } // namespace souffle
souffle::PiggyList::get
T & get(size_t index) const
Retrieve a reference to the stored value at index.
Definition: PiggyList.h:235
souffle::EquivalenceRelation::iterator::reference
value_type & reference
Definition: EquivalenceRelation.h:267
souffle::SparseDisjointSet::sameSet
bool sameSet(SparseDomain x, SparseDomain y)
Definition: UnionFind.h:319
souffle::EquivalenceRelation::statesLock
std::shared_mutex statesLock
Definition: EquivalenceRelation.h:728
souffle::parent_t
uint64_t parent_t
Definition: UnionFind.h:41
souffle::PiggyList::size
size_t size() const
Well, returns the number of nodes exist within the list + number of nodes queued to be inserted The r...
Definition: PiggyList.h:181
souffle::EquivalenceRelation::iterator
Definition: EquivalenceRelation.h:261
souffle::SparseDisjointSet< value_type >
souffle::EquivalenceRelation::iterator::cPosteriorIndex
size_t cPosteriorIndex
Definition: EquivalenceRelation.h:472
souffle::range
A utility class enabling representation of ranges by pairing two iterator instances marking lower and...
Definition: ContainerUtil.h:313
souffle::detail::btree::clear
void clear()
Clears this tree.
Definition: BTree.h:1948
souffle::EquivalenceRelation::iterator::operator*
const TupleType & operator*() const
Definition: EquivalenceRelation.h:362
souffle::EquivalenceRelation::iterator::setAnterior
void setAnterior(const typename TupleType::value_type a)
explicit set first half of cPair
Definition: EquivalenceRelation.h:327
ignore
std::set< const Atom * > ignore
Definition: Ground.cpp:169
souffle::EquivalenceRelation::iterator::djSetMapListEnd
StatesMap::iterator djSetMapListEnd
Definition: EquivalenceRelation.h:467
souffle::EquivalenceRelation::StorePair
std::pair< value_type, StatesBucket > StorePair
Definition: EquivalenceRelation.h:65
souffle::EquivalenceRelation::find
iterator find(const TupleType &, operation_hints &) const
Definition: EquivalenceRelation.h:707
souffle::EquivalenceRelation::contains
bool contains(value_type x, value_type y) const
Returns whether there exists a pair with these two nodes.
Definition: EquivalenceRelation.h:199
souffle::detail::btree::end
iterator end() const
Definition: BTree.h:1729
ParallelUtil.h
souffle::EquivalenceRelation::iterator::iterator
iterator(const EquivalenceRelation *br, bool)
Definition: EquivalenceRelation.h:270
souffle::EquivalenceRelation::statesMapStale
std::atomic< bool > statesMapStale
Definition: EquivalenceRelation.h:732
e
l j a showGridBackground &&c b raw series this eventEmitter e
Definition: htmlJsChartistMin.h:15
souffle::EquivalenceRelation::lower_bound
iterator lower_bound(const TupleType &entry, operation_hints &) const
Act similar to getBoundaries.
Definition: EquivalenceRelation.h:557
souffle::EquivalenceRelation::iterator::br
const EquivalenceRelation * br
Definition: EquivalenceRelation.h:454
souffle::SparseDisjointSet::unionNodes
void unionNodes(SparseDomain x, SparseDomain y)
Definition: UnionFind.h:327
souffle::EquivalenceRelation::iterator::cPair
TupleType cPair
Definition: EquivalenceRelation.h:462
souffle::EquivalenceRelation::genAllDisjointSetLists
void genAllDisjointSetLists() const
Generate a cache of the sets such that they can be iterated over efficiently.
Definition: EquivalenceRelation.h:738
souffle::EquivalenceRelation::end
iterator end() const
iterator pointing to the end of the tuples
Definition: EquivalenceRelation.h:489
souffle::EquivalenceRelation::iterator::operator++
iterator & operator++()
Definition: EquivalenceRelation.h:371
MAX_THREADS
#define MAX_THREADS
Definition: ParallelUtil.h:98
souffle::EquivalenceRelation::iterator::difference_type
ptrdiff_t difference_type
Definition: EquivalenceRelation.h:265
souffle::EquivalenceRelation::iterator::ityp
IterType ityp
Definition: EquivalenceRelation.h:460
souffle::EquivalenceRelation::iterator::updateAnterior
void updateAnterior()
quick update to whatever the current index is pointing to
Definition: EquivalenceRelation.h:332
souffle::detail::LambdaBTree::insert
Functor::result_type insert(Key &k, const Functor &f)
Inserts the given key into this tree.
Definition: LambdaBTree.h:87
souffle::EquivalenceRelation::size
size_t size() const
Size of relation.
Definition: EquivalenceRelation.h:242
souffle::EquivalenceRelation::StatesList
souffle::PiggyList< value_type > StatesList
Definition: EquivalenceRelation.h:63
souffle::SparseDisjointSet::contains
bool contains(SparseDomain v1, SparseDomain v2)
Definition: UnionFind.h:355
LambdaBTree.h
souffle::EquivalenceRelation::iterator::isEndVal
bool isEndVal
Definition: EquivalenceRelation.h:456
souffle::EquivalenceRelation::extend
void extend(const EquivalenceRelation< TupleType > &other)
Extend this relation with another relation, expanding this equivalence relation The supplied relation...
Definition: EquivalenceRelation.h:152
souffle::detail::btree::begin
iterator begin() const
Definition: BTree.h:1724
souffle::EquivalenceRelation::anteriorIt
iterator anteriorIt(value_type anteriorVal) const
Creates an iterator that generates all pairs (A, X) for a given A, and X are elements within A's disj...
Definition: EquivalenceRelation.h:619
UnionFind.h
souffle::EquivalenceRelation::iterator::operator==
bool operator==(const iterator &other) const
Definition: EquivalenceRelation.h:353
souffle::SparseDisjointSet::findNode
SparseDomain findNode(SparseDomain x)
Definition: UnionFind.h:323
i
size_t i
Definition: json11.h:663
ContainerUtil.h
souffle::PiggyList
Definition: PiggyList.h:143
souffle::EquivalenceRelation::iterator::ANTERIOR
@ ANTERIOR
Definition: EquivalenceRelation.h:459
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::EquivalenceRelation::insertAll
void insertAll(const EquivalenceRelation< TupleType > &other)
inserts all nodes from the other relation into this one
Definition: EquivalenceRelation.h:128
souffle::SparseDisjointSet::toSparse
const SparseDomain toSparse(const parent_t in) const
For the given dense value, return the associated sparse value Undefined behaviour if dense value not ...
Definition: UnionFind.h:314
souffle::SparseDisjointSet::clear
void clear()
Remove all elements from this disjoint set.
Definition: UnionFind.h:338
PiggyList.h
souffle::EquivalenceRelation::element_type
TupleType element_type
Definition: EquivalenceRelation.h:70
souffle::EqrelMapComparator
Definition: UnionFind.h:237
souffle::EquivalenceRelation::emptyPartition
void emptyPartition() const
Definition: EquivalenceRelation.h:215
souffle::EquivalenceRelation::iterator::cAnteriorIndex
size_t cAnteriorIndex
Definition: EquivalenceRelation.h:470
souffle::EquivalenceRelation::iterator::ANTPOST
@ ANTPOST
Definition: EquivalenceRelation.h:459
souffle::EquivalenceRelation::containsElement
bool containsElement(value_type e) const
Definition: EquivalenceRelation.h:718
souffle::detail::btree::size
size_type size() const
Definition: BTree.h:1321
souffle::MIN_RAM_SIGNED
constexpr RamSigned MIN_RAM_SIGNED
lower and upper boundaries for the ram types
Definition: RamTypes.h:96
souffle::EquivalenceRelation::StatesBucket
StatesList * StatesBucket
Definition: EquivalenceRelation.h:64
souffle::EquivalenceRelation::iterator::operator->
const TupleType * operator->() const
Definition: EquivalenceRelation.h:366
souffle::EquivalenceRelation::insert
bool insert(value_type x, value_type y)
Insert the two values symbolically as a binary relation.
Definition: EquivalenceRelation.h:94
souffle::EquivalenceRelation::getBoundaries
range< iterator > getBoundaries(const TupleType &entry) const
Obtains a range of elements matching the prefix of the given entry up to levels elements.
Definition: EquivalenceRelation.h:502
souffle::detail::btree::find
iterator find(const Key &k) const
Locates the given key within this tree and returns an iterator referencing its position.
Definition: BTree.h:1772
souffle::SparseDisjointSet::sparseToDenseMap
SparseMap sparseToDenseMap
Definition: UnionFind.h:271
souffle::EquivalenceRelation::clear
void clear()
Empty the relation.
Definition: EquivalenceRelation.h:229
souffle::EquivalenceRelation::iterator::operator=
iterator & operator=(const iterator &other)=default
souffle::EquivalenceRelation::iterator::djSetList
StatesBucket djSetList
Definition: EquivalenceRelation.h:465
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::EquivalenceRelation::EquivalenceRelation
EquivalenceRelation()
Definition: EquivalenceRelation.h:72
souffle::EquivalenceRelation::upper_bound
iterator upper_bound(const TupleType &, operation_hints &) const
This function is only here in order to unify interfaces in InterpreterIndex.
Definition: EquivalenceRelation.h:597
souffle::EquivalenceRelation::operation_hints::clear
void clear()
Definition: EquivalenceRelation.h:85
RamTypes.h
souffle::EquivalenceRelation::iterator::IterType
IterType
Definition: EquivalenceRelation.h:459
souffle
Definition: AggregateOp.h:25
souffle::EquivalenceRelation::iterator::updatePosterior
void updatePosterior()
quick update to whatever the current index is pointing to
Definition: EquivalenceRelation.h:342
souffle::SparseDisjointSet::nodeExists
bool nodeExists(const SparseDomain val) const
Definition: UnionFind.h:351
souffle::EquivalenceRelation::closure
iterator closure(value_type rep) const
Begin an iterator over all pairs within a single disjoint set - This is used for partition().
Definition: EquivalenceRelation.h:656
souffle::EquivalenceRelation::iterator::WITHIN
@ WITHIN
Definition: EquivalenceRelation.h:459
souffle::EquivalenceRelation::sds
souffle::SparseDisjointSet< value_type > sds
Definition: EquivalenceRelation.h:725
souffle::LambdaBTreeSet< StorePair, std::function< StatesBucket(StorePair &)>, souffle::EqrelMapComparator< StorePair > >
souffle::EquivalenceRelation::operation_hints
A collection of operation hints speeding up some of the involved operations by exploiting temporal lo...
Definition: EquivalenceRelation.h:83
souffle::EquivalenceRelation
Definition: EquivalenceRelation.h:50
souffle::EquivalenceRelation::~EquivalenceRelation
~EquivalenceRelation()
Definition: EquivalenceRelation.h:73
souffle::EquivalenceRelation::iterator::setPosterior
void setPosterior(const typename TupleType::value_type b)
explicit set second half of cPair
Definition: EquivalenceRelation.h:337
souffle::EquivalenceRelation::equivalencePartition
StatesMap equivalencePartition
Definition: EquivalenceRelation.h:730
souffle::EquivalenceRelation::empty
bool empty() const
Check emptiness.
Definition: EquivalenceRelation.h:609
souffle::EquivalenceRelation::value_type
typename TupleType::value_type value_type
Definition: EquivalenceRelation.h:59
souffle::tuple
Defines a tuple for the OO interface such that relations with varying columns can be accessed.
Definition: SouffleInterface.h:443
souffle::EquivalenceRelation::begin
iterator begin() const
iterator pointing to the beginning of the tuples, with no restrictions
Definition: EquivalenceRelation.h:480
souffle::EquivalenceRelation::iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: EquivalenceRelation.h:263
souffle::EquivalenceRelation::iterator::djSetMapListIt
StatesMap::iterator djSetMapListIt
Definition: EquivalenceRelation.h:466
souffle::EquivalenceRelation::antpostit
iterator antpostit(value_type anteriorVal, value_type posteriorVal) const
Creates an iterator that generates the pair (A, B) for a given A and B.
Definition: EquivalenceRelation.h:638
souffle::EquivalenceRelation::iterator::pointer
value_type * pointer
Definition: EquivalenceRelation.h:266
souffle::DisjointSet::a_blocks
PiggyList< std::atomic< block_t > > a_blocks
Definition: UnionFind.h:58
souffle::EquivalenceRelation::partition
std::vector< souffle::range< iterator > > partition(size_t chunks) const
Generate an approximate number of iterators for parallel iteration The iterators returned are not nec...
Definition: EquivalenceRelation.h:672
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::SparseDisjointSet::ds
DisjointSet ds
Definition: UnionFind.h:259
souffle::EquivalenceRelation::iterator::operator!=
bool operator!=(const iterator &other) const
Definition: EquivalenceRelation.h:358
souffle::EquivalenceRelation::iterator::ALL
@ ALL
Definition: EquivalenceRelation.h:459