1 | /*
|
2 | * Souffle - A Datalog Compiler
|
3 | * Copyright (c) 2022, 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 EqRel.h
|
12 | *
|
13 | * Datastructure for Equivalence relations
|
14 | *
|
15 | ***********************************************************************/
|
16 |
|
17 | #pragma once
|
18 |
|
19 | #include "souffle/RamTypes.h"
|
20 | #include "souffle/SouffleInterface.h"
|
21 | #include "souffle/datastructure/EquivalenceRelation.h"
|
22 |
|
23 | namespace souffle {
|
24 |
|
25 | /** Equivalence relations */
|
26 | struct t_eqrel {
|
27 | static constexpr Relation::arity_type Arity = 2;
|
28 | using t_tuple = Tuple<RamDomain, 2>;
|
29 | using t_ind = EquivalenceRelation<t_tuple>;
|
30 | t_ind ind;
|
31 | class iterator_0 : public std::iterator<std::forward_iterator_tag, t_tuple> {
|
32 | using nested_iterator = typename t_ind::iterator;
|
33 | nested_iterator nested;
|
34 | t_tuple value;
|
35 |
|
36 | public:
|
37 | iterator_0(const nested_iterator& iter) : nested(iter), value(*iter) {}
|
38 | iterator_0(const iterator_0& other) = default;
|
39 | iterator_0& operator=(const iterator_0& other) = default;
|
40 | bool operator==(const iterator_0& other) const {
|
41 | return nested == other.nested;
|
42 | }
|
43 | bool operator!=(const iterator_0& other) const {
|
44 | return !(*this == other);
|
45 | }
|
46 | const t_tuple& operator*() const {
|
47 | return value;
|
48 | }
|
49 | const t_tuple* operator->() const {
|
50 | return &value;
|
51 | }
|
52 | iterator_0& operator++() {
|
53 | ++nested;
|
54 | value = *nested;
|
55 | return *this;
|
56 | }
|
57 | };
|
58 | class iterator_1 : public std::iterator<std::forward_iterator_tag, t_tuple> {
|
59 | using nested_iterator = typename t_ind::iterator;
|
60 | nested_iterator nested;
|
61 | t_tuple value;
|
62 |
|
63 | public:
|
64 | iterator_1(const nested_iterator& iter) : nested(iter), value(reorder(*iter)) {}
|
65 | iterator_1(const iterator_1& other) = default;
|
66 | iterator_1& operator=(const iterator_1& other) = default;
|
67 | bool operator==(const iterator_1& other) const {
|
68 | return nested == other.nested;
|
69 | }
|
70 | bool operator!=(const iterator_1& other) const {
|
71 | return !(*this == other);
|
72 | }
|
73 | const t_tuple& operator*() const {
|
74 | return value;
|
75 | }
|
76 | const t_tuple* operator->() const {
|
77 | return &value;
|
78 | }
|
79 | iterator_1& operator++() {
|
80 | ++nested;
|
81 | value = reorder(*nested);
|
82 | return *this;
|
83 | }
|
84 | };
|
85 | using iterator = iterator_0;
|
86 | struct context {
|
87 | t_ind::operation_hints hints;
|
88 | };
|
89 | context createContext() {
|
90 | return context();
|
91 | }
|
92 | bool insert(const t_tuple& t) {
|
93 | return ind.insert(t[0], t[1]);
|
94 | }
|
95 | bool insert(const t_tuple& t, context& h) {
|
96 | return ind.insert(t[0], t[1], h.hints);
|
97 | }
|
98 | bool insert(const RamDomain* ramDomain) {
|
99 | RamDomain data[2];
|
100 | std::copy(ramDomain, ramDomain + 2, data);
|
101 | auto& tuple = reinterpret_cast<const t_tuple&>(data);
|
102 | context h;
|
103 | return insert(tuple, h);
|
104 | }
|
105 | bool insert(RamDomain a1, RamDomain a2) {
|
106 | RamDomain data[2] = {a1, a2};
|
107 | return insert(data);
|
108 | }
|
109 | void extendAndInsert(t_eqrel& other) {
|
110 | ind.extendAndInsert(other.ind);
|
111 | }
|
112 | bool contains(const t_tuple& t) const {
|
113 | return ind.contains(t[0], t[1]);
|
114 | }
|
115 | bool contains(const t_tuple& t, context&) const {
|
116 | return ind.contains(t[0], t[1]);
|
117 | }
|
118 | std::size_t size() const {
|
119 | return ind.size();
|
120 | }
|
121 | iterator find(const t_tuple& t) const {
|
122 | return ind.find(t);
|
123 | }
|
124 | iterator find(const t_tuple& t, context&) const {
|
125 | return ind.find(t);
|
126 | }
|
127 | range<iterator> lowerUpperRange_10(const t_tuple& lower, const t_tuple& /*upper*/, context& h) const {
|
128 | auto r = ind.template getBoundaries<1>((lower), h.hints);
|
129 | return make_range(iterator(r.begin()), iterator(r.end()));
|
130 | }
|
131 | range<iterator> lowerUpperRange_10(const t_tuple& lower, const t_tuple& upper) const {
|
132 | context h;
|
133 | return lowerUpperRange_10(lower, upper, h);
|
134 | }
|
135 | range<iterator_1> lowerUpperRange_01(const t_tuple& lower, const t_tuple& /*upper*/, context& h) const {
|
136 | auto r = ind.template getBoundaries<1>(reorder(lower), h.hints);
|
137 | return make_range(iterator_1(r.begin()), iterator_1(r.end()));
|
138 | }
|
139 | range<iterator_1> lowerUpperRange_01(const t_tuple& lower, const t_tuple& upper) const {
|
140 | context h;
|
141 | return lowerUpperRange_01(lower, upper, h);
|
142 | }
|
143 | range<iterator> lowerUpperRange_11(const t_tuple& lower, const t_tuple& /*upper*/, context& h) const {
|
144 | auto r = ind.template getBoundaries<2>((lower), h.hints);
|
145 | return make_range(iterator(r.begin()), iterator(r.end()));
|
146 | }
|
147 | range<iterator> lowerUpperRange_11(const t_tuple& lower, const t_tuple& upper) const {
|
148 | context h;
|
149 | return lowerUpperRange_11(lower, upper, h);
|
150 | }
|
151 | bool empty() const {
|
152 | return ind.size() == 0;
|
153 | }
|
154 | std::vector<range<iterator>> partition() const {
|
155 | std::vector<range<iterator>> res;
|
156 | for (const auto& cur : ind.partition(10000)) {
|
157 | res.push_back(make_range(iterator(cur.begin()), iterator(cur.end())));
|
158 | }
|
159 | return res;
|
160 | }
|
161 | void purge() {
|
162 | ind.clear();
|
163 | }
|
164 | iterator begin() const {
|
165 | return iterator(ind.begin());
|
166 | }
|
167 | iterator end() const {
|
168 | return iterator(ind.end());
|
169 | }
|
170 | static t_tuple reorder(const t_tuple& t) {
|
171 | t_tuple res;
|
172 | res[0] = t[1];
|
173 | res[1] = t[0];
|
174 | return res;
|
175 | }
|
176 | void printStatistics(std::ostream& /* o */) const {}
|
177 | };
|
178 |
|
179 | } // namespace souffle |