OILS / vendor / souffle / datastructure / EqRel.h View on Github | oilshell.org

179 lines, 121 significant
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
23namespace souffle {
24
25/** Equivalence relations */
26struct 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