souffle
2.0.2-371-g6315b36
|
Go to the documentation of this file.
34 #include <shared_mutex>
41 template <
typename TupleType>
42 class EquivalenceRelation {
43 using value_type =
typename TupleType::value_type;
49 using StorePair = std::pair<value_type, StatesBucket>;
67 struct operation_hints {
113 other.genAllDisjointSetLists();
120 const size_t ksize = pl.
size();
121 for (
size_t i = 0;
i < ksize; ++
i) {
138 if (other.size() == 0 || this->size() == 0)
return;
141 other.genAllDisjointSetLists();
143 std::set<value_type> repsCovered;
151 for (; it !=
end; ++it) {
153 if (other.containsElement(el)) {
155 if (repsCovered.count(rep) == 0) {
156 repsCovered.emplace(rep);
166 auto it = other.sds.sparseToDenseMap.begin();
167 auto end = other.sds.sparseToDenseMap.end();
168 for (; it !=
end; ++it) {
170 rep = other.sds.findNode(el);
171 if (repsCovered.count(rep) != 0) {
191 bool contains(
const TupleType& tuple, operation_hints&)
const {
192 return contains(tuple[0], tuple[1]);
195 bool contains(
const TupleType& tuple)
const {
196 return contains(tuple[0], tuple[1]);
226 size_t size()
const {
232 for (
auto&
e : this->equivalencePartition) {
233 const size_t s =
e.second->size();
300 typename TupleType::value_type latter,
const StatesBucket within)
311 inline void setAnterior(
const typename TupleType::value_type a) {
321 inline void setPosterior(
const typename TupleType::value_type
b) {
338 if (
isEndVal && other.isEndVal)
return br == other.br;
343 return !((*this) == other);
357 throw std::out_of_range(
"error: incrementing an out of range iterator");
378 throw std::out_of_range(
"error: encountered a zero size djset");
398 case IterType::ANTERIOR:
407 case IterType::ANTPOST:
412 case IterType::WITHIN:
485 template <
unsigned levels>
487 operation_hints ctxt;
488 return getBoundaries<levels>(entry, ctxt);
501 template <
unsigned levels>
525 std::cerr <<
"invalid state, cannot search for >2 arg start point in getBoundaries, in 2 arg tuple "
527 throw "invalid state, cannot search for >2 arg start point in getBoundaries, in 2 arg tuple store";
541 iterator
lower_bound(
const TupleType& entry, operation_hints&)
const {
568 iterator
lower_bound(
const TupleType& entry)
const {
569 operation_hints hints;
581 iterator
upper_bound(
const TupleType&, operation_hints&)
const {
585 iterator
upper_bound(
const TupleType& entry)
const {
586 operation_hints hints;
594 return this->
size() == 0;
632 return iterator(
this, anteriorVal, posteriorVal, (*found).second);
645 return iterator(
this, (*found).second);
656 std::vector<souffle::range<iterator>>
partition(
size_t chunks)
const {
660 size_t numPairs = this->
size();
661 if (numPairs == 0)
return {};
665 std::vector<souffle::range<iterator>> ret;
676 const size_t perchunk = numPairs / chunks;
678 const size_t s = itp.second->size();
679 if (s * s > perchunk) {
680 for (
const auto&
i : *itp.second) {
691 iterator
find(
const TupleType&, operation_hints&)
const {
692 throw std::runtime_error(
"error: find() is not compatible with equivalence relations");
696 iterator
find(
const TupleType& t)
const {
697 operation_hints context;
698 return find(t, context);
726 if (!this->statesMapStale.load(std::memory_order_acquire)) {
735 for (
size_t i = 0;
i < dSetSize; ++
i) {
736 typename TupleType::value_type sparseVal = this->sds.
toSparse(
i);
745 mapList->append(sparseVal);
T & get(size_t index) const
Retrieve a reference to the stored value at index.
bool sameSet(SparseDomain x, SparseDomain y)
std::shared_mutex statesLock
size_t size() const
Well, returns the number of nodes exist within the list + number of nodes queued to be inserted The r...
A utility class enabling representation of ranges by pairing two iterator instances marking lower and...
void clear()
Clears this tree.
const TupleType & operator*() const
void setAnterior(const typename TupleType::value_type a)
explicit set first half of cPair
std::set< const Atom * > ignore
StatesMap::iterator djSetMapListEnd
std::pair< value_type, StatesBucket > StorePair
iterator find(const TupleType &, operation_hints &) const
bool contains(value_type x, value_type y) const
Returns whether there exists a pair with these two nodes.
iterator(const EquivalenceRelation *br, bool)
std::atomic< bool > statesMapStale
l j a showGridBackground &&c b raw series this eventEmitter e
iterator lower_bound(const TupleType &entry, operation_hints &) const
Act similar to getBoundaries.
const EquivalenceRelation * br
void unionNodes(SparseDomain x, SparseDomain y)
void genAllDisjointSetLists() const
Generate a cache of the sets such that they can be iterated over efficiently.
iterator end() const
iterator pointing to the end of the tuples
ptrdiff_t difference_type
void updateAnterior()
quick update to whatever the current index is pointing to
Functor::result_type insert(Key &k, const Functor &f)
Inserts the given key into this tree.
size_t size() const
Size of relation.
souffle::PiggyList< value_type > StatesList
bool contains(SparseDomain v1, SparseDomain v2)
void extend(const EquivalenceRelation< TupleType > &other)
Extend this relation with another relation, expanding this equivalence relation The supplied relation...
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...
bool operator==(const iterator &other) const
SparseDomain findNode(SparseDomain x)
range< Iter > make_range(const Iter &a, const Iter &b)
A utility function enabling the construction of ranges without explicitly specifying the iterator typ...
void insertAll(const EquivalenceRelation< TupleType > &other)
inserts all nodes from the other relation into this one
const SparseDomain toSparse(const parent_t in) const
For the given dense value, return the associated sparse value Undefined behaviour if dense value not ...
void clear()
Remove all elements from this disjoint set.
void emptyPartition() const
bool containsElement(value_type e) const
constexpr RamSigned MIN_RAM_SIGNED
lower and upper boundaries for the ram types
StatesList * StatesBucket
const TupleType * operator->() const
bool insert(value_type x, value_type y)
Insert the two values symbolically as a binary relation.
range< iterator > getBoundaries(const TupleType &entry) const
Obtains a range of elements matching the prefix of the given entry up to levels elements.
iterator find(const Key &k) const
Locates the given key within this tree and returns an iterator referencing its position.
SparseMap sparseToDenseMap
void clear()
Empty the relation.
iterator & operator=(const iterator &other)=default
l j a showGridBackground &&c b raw series this eventEmitter b
iterator upper_bound(const TupleType &, operation_hints &) const
This function is only here in order to unify interfaces in InterpreterIndex.
void updatePosterior()
quick update to whatever the current index is pointing to
bool nodeExists(const SparseDomain val) const
iterator closure(value_type rep) const
Begin an iterator over all pairs within a single disjoint set - This is used for partition().
souffle::SparseDisjointSet< value_type > sds
A collection of operation hints speeding up some of the involved operations by exploiting temporal lo...
void setPosterior(const typename TupleType::value_type b)
explicit set second half of cPair
StatesMap equivalencePartition
bool empty() const
Check emptiness.
typename TupleType::value_type value_type
Defines a tuple for the OO interface such that relations with varying columns can be accessed.
iterator begin() const
iterator pointing to the beginning of the tuples, with no restrictions
std::forward_iterator_tag iterator_category
StatesMap::iterator djSetMapListIt
iterator antpostit(value_type anteriorVal, value_type posteriorVal) const
Creates an iterator that generates the pair (A, B) for a given A and B.
PiggyList< std::atomic< block_t > > a_blocks
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...
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
bool operator!=(const iterator &other) const