aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLibravatar Kristóf Marussy <marussy@mit.bme.hu>2023-06-29 02:30:40 +0200
committerLibravatar GitHub <noreply@github.com>2023-06-29 02:30:40 +0200
commit7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5 (patch)
tree9cc6850dba18ed526eb27a911bc3f73b28752a14
parentfix: FilteredView default value (diff)
parentfeat: ordered query ResultSet (diff)
downloadrefinery-7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5.tar.gz
refinery-7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5.tar.zst
refinery-7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5.zip
Merge pull request #27 from kris7t/ordered-result-set
feat: ordered query ResultSet
Diffstat
-rw-r--r--subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java6
-rw-r--r--subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java32
-rw-r--r--subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java34
-rw-r--r--subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java10
-rw-r--r--subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java29
-rw-r--r--subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java4
-rw-r--r--subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java117
-rw-r--r--subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java2
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java2
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java2
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Reduction.java (renamed from subprojects/store-query/src/main/java/tools/refinery/store/query/Reduction.java)2
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java63
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java (renamed from subprojects/store-query/src/main/java/tools/refinery/store/query/AnyResultSet.java)3
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java (renamed from subprojects/store-query/src/main/java/tools/refinery/store/query/EmptyResultSet.java)13
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java80
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java (renamed from subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java)6
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java13
-rw-r--r--subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java754
-rw-r--r--subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java634
-rw-r--r--subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/ReasoningAdapter.java2
-rw-r--r--subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/internal/ReasoningAdapterImpl.java2
-rw-r--r--subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/literal/ModalConstraint.java2
-rw-r--r--subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/translator/base/BaseDecisionInterpretation.java2
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java20
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java4
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java13
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java14
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java18
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java22
29 files changed, 1844 insertions, 61 deletions
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
index 7103a561..5f3e86b4 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
@@ -13,9 +13,9 @@ import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackend;
13import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory; 13import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
14import tools.refinery.store.model.Model; 14import tools.refinery.store.model.Model;
15import tools.refinery.store.model.ModelListener; 15import tools.refinery.store.model.ModelListener;
16import tools.refinery.store.query.AnyResultSet; 16import tools.refinery.store.query.resultset.AnyResultSet;
17import tools.refinery.store.query.EmptyResultSet; 17import tools.refinery.store.query.resultset.EmptyResultSet;
18import tools.refinery.store.query.ResultSet; 18import tools.refinery.store.query.resultset.ResultSet;
19import tools.refinery.store.query.dnf.AnyQuery; 19import tools.refinery.store.query.dnf.AnyQuery;
20import tools.refinery.store.query.dnf.FunctionalQuery; 20import tools.refinery.store.query.dnf.FunctionalQuery;
21import tools.refinery.store.query.dnf.Query; 21import tools.refinery.store.query.dnf.Query;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java
new file mode 100644
index 00000000..99b0a3d8
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java
@@ -0,0 +1,32 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.query.viatra.internal.matcher;
7
8import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
9import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable;
10import tools.refinery.store.query.dnf.Query;
11import tools.refinery.store.query.resultset.AbstractResultSet;
12import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
13
14public abstract class AbstractViatraMatcher<T> extends AbstractResultSet<T> implements IUpdateable {
15 protected final IQueryResultProvider backend;
16
17 protected AbstractViatraMatcher(ViatraModelQueryAdapterImpl adapter, Query<T> query,
18 RawPatternMatcher rawPatternMatcher) {
19 super(adapter, query);
20 backend = rawPatternMatcher.getBackend();
21 }
22
23 @Override
24 protected void startListeningForChanges() {
25 backend.addUpdateListener(this, this, false);
26 }
27
28 @Override
29 protected void stopListeningForChanges() {
30 backend.removeUpdateListener(this);
31 }
32}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
index f018288b..db4740cd 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
@@ -5,16 +5,12 @@
5 */ 5 */
6package tools.refinery.store.query.viatra.internal.matcher; 6package tools.refinery.store.query.viatra.internal.matcher;
7 7
8import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
9import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; 8import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
10import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; 9import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
11import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer; 10import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer;
12import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; 11import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher;
13import tools.refinery.store.map.Cursor; 12import tools.refinery.store.map.Cursor;
14import tools.refinery.store.query.ModelQueryAdapter;
15import tools.refinery.store.query.ResultSet;
16import tools.refinery.store.query.dnf.FunctionalQuery; 13import tools.refinery.store.query.dnf.FunctionalQuery;
17import tools.refinery.store.query.dnf.Query;
18import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; 14import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
19import tools.refinery.store.tuple.Tuple; 15import tools.refinery.store.tuple.Tuple;
20 16
@@ -28,23 +24,18 @@ import tools.refinery.store.tuple.Tuple;
28 * implementation for these methods. 24 * implementation for these methods.
29 * Using this class with any other runtime context may lead to undefined behavior. 25 * Using this class with any other runtime context may lead to undefined behavior.
30 */ 26 */
31public class FunctionalViatraMatcher<T> implements ResultSet<T> { 27public class FunctionalViatraMatcher<T> extends AbstractViatraMatcher<T> {
32 private final ViatraModelQueryAdapterImpl adapter;
33 private final FunctionalQuery<T> query;
34 private final TupleMask emptyMask; 28 private final TupleMask emptyMask;
35 private final TupleMask omitOutputMask; 29 private final TupleMask omitOutputMask;
36 private final IQueryResultProvider backend;
37 private final IterableIndexer omitOutputIndexer; 30 private final IterableIndexer omitOutputIndexer;
38 31
39 public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl adapter, FunctionalQuery<T> query, 32 public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl adapter, FunctionalQuery<T> query,
40 RawPatternMatcher rawPatternMatcher) { 33 RawPatternMatcher rawPatternMatcher) {
41 this.adapter = adapter; 34 super(adapter, query, rawPatternMatcher);
42 this.query = query;
43 int arity = query.arity(); 35 int arity = query.arity();
44 int arityWithOutput = arity + 1; 36 int arityWithOutput = arity + 1;
45 emptyMask = TupleMask.empty(arityWithOutput); 37 emptyMask = TupleMask.empty(arityWithOutput);
46 omitOutputMask = TupleMask.omit(arity, arityWithOutput); 38 omitOutputMask = TupleMask.omit(arity, arityWithOutput);
47 backend = rawPatternMatcher.getBackend();
48 if (backend instanceof RetePatternMatcher reteBackend) { 39 if (backend instanceof RetePatternMatcher reteBackend) {
49 var maybeIterableOmitOutputIndexer = IndexerUtils.getIndexer(reteBackend, omitOutputMask); 40 var maybeIterableOmitOutputIndexer = IndexerUtils.getIndexer(reteBackend, omitOutputMask);
50 if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) { 41 if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) {
@@ -58,16 +49,6 @@ public class FunctionalViatraMatcher<T> implements ResultSet<T> {
58 } 49 }
59 50
60 @Override 51 @Override
61 public ModelQueryAdapter getAdapter() {
62 return adapter;
63 }
64
65 @Override
66 public Query<T> getQuery() {
67 return query;
68 }
69
70 @Override
71 public T get(Tuple parameters) { 52 public T get(Tuple parameters) {
72 var tuple = MatcherUtils.toViatraTuple(parameters); 53 var tuple = MatcherUtils.toViatraTuple(parameters);
73 if (omitOutputIndexer == null) { 54 if (omitOutputIndexer == null) {
@@ -93,4 +74,15 @@ public class FunctionalViatraMatcher<T> implements ResultSet<T> {
93 } 74 }
94 return omitOutputIndexer.getBucketCount(); 75 return omitOutputIndexer.getBucketCount();
95 } 76 }
77
78 @Override
79 public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) {
80 var key = MatcherUtils.keyToRefineryTuple(updateElement);
81 var value = MatcherUtils.<T>getValue(updateElement);
82 if (isInsertion) {
83 notifyChange(key, null, value);
84 } else {
85 notifyChange(key, value, null);
86 }
87 }
96} 88}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
index 1c784492..6e24812a 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
@@ -86,6 +86,13 @@ final class MatcherUtils {
86 return getWrapper(viatraTuple, index).value0(); 86 return getWrapper(viatraTuple, index).value0();
87 } 87 }
88 88
89 public static <T> T getValue(ITuple match) {
90 // This is only safe if we know for sure that match came from a functional query of type {@code T}.
91 @SuppressWarnings("unchecked")
92 var result = (T) match.get(match.getSize() - 1);
93 return result;
94 }
95
89 public static <T> T getSingleValue(@Nullable Iterable<? extends ITuple> viatraTuples) { 96 public static <T> T getSingleValue(@Nullable Iterable<? extends ITuple> viatraTuples) {
90 if (viatraTuples == null) { 97 if (viatraTuples == null) {
91 return null; 98 return null;
@@ -98,8 +105,7 @@ final class MatcherUtils {
98 return null; 105 return null;
99 } 106 }
100 var match = iterator.next(); 107 var match = iterator.next();
101 @SuppressWarnings("unchecked") 108 var result = MatcherUtils.<T>getValue(match);
102 var result = (T) match.get(match.getSize() - 1);
103 if (iterator.hasNext()) { 109 if (iterator.hasNext()) {
104 var input = keyToRefineryTuple(match); 110 var input = keyToRefineryTuple(match);
105 throw new IllegalStateException("Query is not functional for input tuple: " + input); 111 throw new IllegalStateException("Query is not functional for input tuple: " + input);
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
index d1476920..ac95dcc0 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
@@ -5,16 +5,12 @@
5 */ 5 */
6package tools.refinery.store.query.viatra.internal.matcher; 6package tools.refinery.store.query.viatra.internal.matcher;
7 7
8import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
9import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; 8import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
10import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; 9import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
11import org.eclipse.viatra.query.runtime.rete.index.Indexer; 10import org.eclipse.viatra.query.runtime.rete.index.Indexer;
12import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; 11import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher;
13import tools.refinery.store.map.Cursor; 12import tools.refinery.store.map.Cursor;
14import tools.refinery.store.map.Cursors; 13import tools.refinery.store.map.Cursors;
15import tools.refinery.store.query.ModelQueryAdapter;
16import tools.refinery.store.query.ResultSet;
17import tools.refinery.store.query.dnf.Query;
18import tools.refinery.store.query.dnf.RelationalQuery; 14import tools.refinery.store.query.dnf.RelationalQuery;
19import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; 15import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
20import tools.refinery.store.tuple.Tuple; 16import tools.refinery.store.tuple.Tuple;
@@ -29,22 +25,17 @@ import tools.refinery.store.tuple.Tuple;
29 * implementation for these methods. 25 * implementation for these methods.
30 * Using this class with any other runtime context may lead to undefined behavior. 26 * Using this class with any other runtime context may lead to undefined behavior.
31 */ 27 */
32public class RelationalViatraMatcher implements ResultSet<Boolean> { 28public class RelationalViatraMatcher extends AbstractViatraMatcher<Boolean> {
33 private final ViatraModelQueryAdapterImpl adapter;
34 private final RelationalQuery query;
35 private final TupleMask emptyMask; 29 private final TupleMask emptyMask;
36 private final TupleMask identityMask; 30 private final TupleMask identityMask;
37 private final IQueryResultProvider backend;
38 private final Indexer emptyMaskIndexer; 31 private final Indexer emptyMaskIndexer;
39 32
40 public RelationalViatraMatcher(ViatraModelQueryAdapterImpl adapter, RelationalQuery query, 33 public RelationalViatraMatcher(ViatraModelQueryAdapterImpl adapter, RelationalQuery query,
41 RawPatternMatcher rawPatternMatcher) { 34 RawPatternMatcher rawPatternMatcher) {
42 this.adapter = adapter; 35 super(adapter, query, rawPatternMatcher);
43 this.query = query;
44 int arity = query.arity(); 36 int arity = query.arity();
45 emptyMask = TupleMask.empty(arity); 37 emptyMask = TupleMask.empty(arity);
46 identityMask = TupleMask.identity(arity); 38 identityMask = TupleMask.identity(arity);
47 backend = rawPatternMatcher.getBackend();
48 if (backend instanceof RetePatternMatcher reteBackend) { 39 if (backend instanceof RetePatternMatcher reteBackend) {
49 emptyMaskIndexer = IndexerUtils.getIndexer(reteBackend, emptyMask); 40 emptyMaskIndexer = IndexerUtils.getIndexer(reteBackend, emptyMask);
50 } else { 41 } else {
@@ -53,16 +44,6 @@ public class RelationalViatraMatcher implements ResultSet<Boolean> {
53 } 44 }
54 45
55 @Override 46 @Override
56 public ModelQueryAdapter getAdapter() {
57 return adapter;
58 }
59
60 @Override
61 public Query<Boolean> getQuery() {
62 return query;
63 }
64
65 @Override
66 public Boolean get(Tuple parameters) { 47 public Boolean get(Tuple parameters) {
67 var tuple = MatcherUtils.toViatraTuple(parameters); 48 var tuple = MatcherUtils.toViatraTuple(parameters);
68 if (emptyMaskIndexer == null) { 49 if (emptyMaskIndexer == null) {
@@ -90,4 +71,10 @@ public class RelationalViatraMatcher implements ResultSet<Boolean> {
90 var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf()); 71 var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf());
91 return matches == null ? 0 : matches.size(); 72 return matches == null ? 0 : matches.size();
92 } 73 }
74
75 @Override
76 public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) {
77 var key = MatcherUtils.toRefineryTuple(updateElement);
78 notifyChange(key, !isInsertion, isInsertion);
79 }
93} 80}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
index 4a41d724..b0b507fe 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
@@ -46,9 +46,7 @@ class UnsafeFunctionalCursor<T> implements Cursor<Tuple, T> {
46 if (!terminated && tuplesIterator.hasNext()) { 46 if (!terminated && tuplesIterator.hasNext()) {
47 var match = tuplesIterator.next(); 47 var match = tuplesIterator.next();
48 key = MatcherUtils.keyToRefineryTuple(match); 48 key = MatcherUtils.keyToRefineryTuple(match);
49 @SuppressWarnings("unchecked") 49 value = MatcherUtils.getValue(match);
50 var typedValue = (T) match.get(match.getSize() - 1);
51 value = typedValue;
52 return true; 50 return true;
53 } 51 }
54 terminated = true; 52 terminated = true;
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java
new file mode 100644
index 00000000..8ede6c80
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java
@@ -0,0 +1,117 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.query.viatra;
7
8import org.junit.jupiter.api.Test;
9import tools.refinery.store.model.ModelStore;
10import tools.refinery.store.query.ModelQueryAdapter;
11import tools.refinery.store.query.dnf.Query;
12import tools.refinery.store.query.resultset.OrderedResultSet;
13import tools.refinery.store.query.term.Variable;
14import tools.refinery.store.query.view.AnySymbolView;
15import tools.refinery.store.query.view.KeyOnlyView;
16import tools.refinery.store.representation.Symbol;
17import tools.refinery.store.tuple.Tuple;
18
19import static org.hamcrest.MatcherAssert.assertThat;
20import static org.hamcrest.Matchers.is;
21
22class OrderedResultSetTest {
23 private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
24 private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
25
26 @Test
27 void relationalFlushTest() {
28 var query = Query.of("Relation", (builder, p1, p2) -> builder.clause(
29 friendView.call(p1, p2)
30 ));
31
32 var store = ModelStore.builder()
33 .symbols(friend)
34 .with(ViatraModelQueryAdapter.builder()
35 .queries(query))
36 .build();
37
38 var model = store.createEmptyModel();
39 var friendInterpretation = model.getInterpretation(friend);
40 var queryEngine = model.getAdapter(ModelQueryAdapter.class);
41 var resultSet = queryEngine.getResultSet(query);
42
43 friendInterpretation.put(Tuple.of(0, 1), true);
44 friendInterpretation.put(Tuple.of(1, 2), true);
45 friendInterpretation.put(Tuple.of(1, 1), true);
46 queryEngine.flushChanges();
47
48 try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
49 assertThat(orderedResultSet.size(), is(3));
50 assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
51 assertThat(orderedResultSet.getKey(1), is(Tuple.of(1, 1)));
52 assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 2)));
53
54 friendInterpretation.put(Tuple.of(1, 2), false);
55 friendInterpretation.put(Tuple.of(0, 2), true);
56 queryEngine.flushChanges();
57
58 assertThat(orderedResultSet.size(), is(3));
59 assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
60 assertThat(orderedResultSet.getKey(1), is(Tuple.of(0, 2)));
61 assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 1)));
62 }
63 }
64
65 @Test
66 void functionalFlushTest() {
67 var query = Query.of("Function", Integer.class, (builder, p1, output) -> builder.clause(
68 friendView.call(p1, Variable.of()),
69 output.assign(friendView.count(p1, Variable.of()))
70 ));
71
72 var store = ModelStore.builder()
73 .symbols(friend)
74 .with(ViatraModelQueryAdapter.builder()
75 .queries(query))
76 .build();
77
78 var model = store.createEmptyModel();
79 var friendInterpretation = model.getInterpretation(friend);
80 var queryEngine = model.getAdapter(ModelQueryAdapter.class);
81 var resultSet = queryEngine.getResultSet(query);
82
83 friendInterpretation.put(Tuple.of(0, 1), true);
84 friendInterpretation.put(Tuple.of(1, 2), true);
85 friendInterpretation.put(Tuple.of(1, 1), true);
86 queryEngine.flushChanges();
87
88 try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
89 assertThat(orderedResultSet.size(), is(2));
90 assertThat(orderedResultSet.getKey(0), is(Tuple.of(0)));
91 assertThat(orderedResultSet.getKey(1), is(Tuple.of(1)));
92
93 friendInterpretation.put(Tuple.of(0, 1), false);
94 friendInterpretation.put(Tuple.of(2, 1), true);
95 queryEngine.flushChanges();
96
97 assertThat(orderedResultSet.size(), is(2));
98 assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
99 assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
100
101 friendInterpretation.put(Tuple.of(1, 1), false);
102 queryEngine.flushChanges();
103
104 assertThat(orderedResultSet.size(), is(2));
105 assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
106 assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
107
108 friendInterpretation.put(Tuple.of(1, 2), false);
109 friendInterpretation.put(Tuple.of(1, 0), true);
110 queryEngine.flushChanges();
111
112 assertThat(orderedResultSet.size(), is(2));
113 assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
114 assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
115 }
116 }
117}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
index 7a25cfdc..ca089a9d 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
@@ -6,7 +6,7 @@
6package tools.refinery.store.query.viatra.tests; 6package tools.refinery.store.query.viatra.tests;
7 7
8import org.junit.jupiter.api.function.Executable; 8import org.junit.jupiter.api.function.Executable;
9import tools.refinery.store.query.ResultSet; 9import tools.refinery.store.query.resultset.ResultSet;
10import tools.refinery.store.tuple.Tuple; 10import tools.refinery.store.tuple.Tuple;
11 11
12import java.util.*; 12import java.util.*;
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java
index ae3bbcbb..1fa96a07 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java
@@ -8,6 +8,8 @@ package tools.refinery.store.query;
8import tools.refinery.store.adapter.ModelAdapter; 8import tools.refinery.store.adapter.ModelAdapter;
9import tools.refinery.store.query.dnf.AnyQuery; 9import tools.refinery.store.query.dnf.AnyQuery;
10import tools.refinery.store.query.dnf.Query; 10import tools.refinery.store.query.dnf.Query;
11import tools.refinery.store.query.resultset.AnyResultSet;
12import tools.refinery.store.query.resultset.ResultSet;
11 13
12public interface ModelQueryAdapter extends ModelAdapter { 14public interface ModelQueryAdapter extends ModelAdapter {
13 ModelQueryStoreAdapter getStoreAdapter(); 15 ModelQueryStoreAdapter getStoreAdapter();
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java
index c5b51b81..50b245f7 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java
@@ -6,7 +6,7 @@
6package tools.refinery.store.query.dnf; 6package tools.refinery.store.query.dnf;
7 7
8import tools.refinery.store.query.Constraint; 8import tools.refinery.store.query.Constraint;
9import tools.refinery.store.query.Reduction; 9import tools.refinery.store.query.literal.Reduction;
10import tools.refinery.store.query.equality.DnfEqualityChecker; 10import tools.refinery.store.query.equality.DnfEqualityChecker;
11import tools.refinery.store.query.equality.LiteralEqualityHelper; 11import tools.refinery.store.query.equality.LiteralEqualityHelper;
12import tools.refinery.store.query.term.Parameter; 12import tools.refinery.store.query.term.Parameter;
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/Reduction.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Reduction.java
index 82c52b04..ee155a9a 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/Reduction.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Reduction.java
@@ -3,7 +3,7 @@
3 * 3 *
4 * SPDX-License-Identifier: EPL-2.0 4 * SPDX-License-Identifier: EPL-2.0
5 */ 5 */
6package tools.refinery.store.query; 6package tools.refinery.store.query.literal;
7 7
8public enum Reduction { 8public enum Reduction {
9 /** 9 /**
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java
new file mode 100644
index 00000000..a710c64d
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java
@@ -0,0 +1,63 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.query.resultset;
7
8import tools.refinery.store.query.ModelQueryAdapter;
9import tools.refinery.store.query.dnf.Query;
10import tools.refinery.store.tuple.Tuple;
11
12import java.util.ArrayList;
13import java.util.List;
14
15public abstract class AbstractResultSet<T> implements ResultSet<T> {
16 private final ModelQueryAdapter adapter;
17 private final Query<T> query;
18 private final List<ResultSetListener<T>> listeners = new ArrayList<>();
19
20 protected AbstractResultSet(ModelQueryAdapter adapter, Query<T> query) {
21 this.adapter = adapter;
22 this.query = query;
23 }
24
25 @Override
26 public ModelQueryAdapter getAdapter() {
27 return adapter;
28 }
29
30 @Override
31 public Query<T> getQuery() {
32 return query;
33 }
34
35 @Override
36 public void addListener(ResultSetListener<T> listener) {
37 if (listeners.isEmpty()) {
38 startListeningForChanges();
39 }
40 listeners.add(listener);
41 }
42
43 @Override
44 public void removeListener(ResultSetListener<T> listener) {
45 listeners.remove(listener);
46 if (listeners.isEmpty()) {
47 stopListeningForChanges();
48 }
49 }
50
51 protected abstract void startListeningForChanges();
52
53 protected abstract void stopListeningForChanges();
54
55 protected void notifyChange(Tuple key, T oldValue, T newValue) {
56 int listenerCount = listeners.size();
57 // Use a for loop instead of a for-each loop to avoid {@code Iterator} allocation overhead.
58 //noinspection ForLoopReplaceableByForEach
59 for (int i = 0; i < listenerCount; i++) {
60 listeners.get(i).put(key, oldValue, newValue);
61 }
62 }
63}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/AnyResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java
index f29bb278..02809477 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/AnyResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java
@@ -3,8 +3,9 @@
3 * 3 *
4 * SPDX-License-Identifier: EPL-2.0 4 * SPDX-License-Identifier: EPL-2.0
5 */ 5 */
6package tools.refinery.store.query; 6package tools.refinery.store.query.resultset;
7 7
8import tools.refinery.store.query.ModelQueryAdapter;
8import tools.refinery.store.query.dnf.AnyQuery; 9import tools.refinery.store.query.dnf.AnyQuery;
9 10
10public sealed interface AnyResultSet permits ResultSet { 11public sealed interface AnyResultSet permits ResultSet {
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/EmptyResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java
index 5361f645..2795a44b 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/EmptyResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java
@@ -3,10 +3,11 @@
3 * 3 *
4 * SPDX-License-Identifier: EPL-2.0 4 * SPDX-License-Identifier: EPL-2.0
5 */ 5 */
6package tools.refinery.store.query; 6package tools.refinery.store.query.resultset;
7 7
8import tools.refinery.store.map.Cursor; 8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.map.Cursors; 9import tools.refinery.store.map.Cursors;
10import tools.refinery.store.query.ModelQueryAdapter;
10import tools.refinery.store.query.dnf.Query; 11import tools.refinery.store.query.dnf.Query;
11import tools.refinery.store.tuple.Tuple; 12import tools.refinery.store.tuple.Tuple;
12 13
@@ -35,4 +36,14 @@ public record EmptyResultSet<T>(ModelQueryAdapter adapter, Query<T> query) imple
35 public int size() { 36 public int size() {
36 return 0; 37 return 0;
37 } 38 }
39
40 @Override
41 public void addListener(ResultSetListener<T> listener) {
42 // No need to store the listener, because the empty result set will never change.
43 }
44
45 @Override
46 public void removeListener(ResultSetListener<T> listener) {
47 // No need to remove the listener, because we never stored it.
48 }
38} 49}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java
new file mode 100644
index 00000000..39006d65
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java
@@ -0,0 +1,80 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.query.resultset;
7
8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.query.ModelQueryAdapter;
10import tools.refinery.store.query.dnf.Query;
11import tools.refinery.store.query.utils.OrderStatisticTree;
12import tools.refinery.store.tuple.Tuple;
13
14import java.util.Objects;
15
16public class OrderedResultSet<T> implements AutoCloseable, ResultSet<T> {
17 private final ResultSet<T> resultSet;
18 private final OrderStatisticTree<Tuple> tree = new OrderStatisticTree<>();
19 private final ResultSetListener<T> listener = (key, fromValue, toValue) -> {
20 var defaultValue = getQuery().defaultValue();
21 if (Objects.equals(defaultValue, toValue)) {
22 tree.remove(key);
23 } else {
24 tree.add(key);
25 }
26 };
27
28 public OrderedResultSet(ResultSet<T> resultSet) {
29 this.resultSet = resultSet;
30 resultSet.addListener(listener);
31 var cursor = resultSet.getAll();
32 while (cursor.move()) {
33 tree.add(cursor.getKey());
34 }
35 }
36
37 @Override
38 public ModelQueryAdapter getAdapter() {
39 return resultSet.getAdapter();
40 }
41
42 @Override
43 public int size() {
44 return resultSet.size();
45 }
46
47 @Override
48 public Query<T> getQuery() {
49 return resultSet.getQuery();
50 }
51
52 @Override
53 public T get(Tuple parameters) {
54 return resultSet.get(parameters);
55 }
56
57 public Tuple getKey(int index) {
58 return tree.get(index);
59 }
60
61 @Override
62 public Cursor<Tuple, T> getAll() {
63 return resultSet.getAll();
64 }
65
66 @Override
67 public void addListener(ResultSetListener<T> listener) {
68 resultSet.addListener(listener);
69 }
70
71 @Override
72 public void removeListener(ResultSetListener<T> listener) {
73 resultSet.removeListener(listener);
74 }
75
76 @Override
77 public void close() {
78 resultSet.removeListener(listener);
79 }
80}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java
index 9ab83172..33d1ea95 100644
--- a/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java
@@ -3,7 +3,7 @@
3 * 3 *
4 * SPDX-License-Identifier: EPL-2.0 4 * SPDX-License-Identifier: EPL-2.0
5 */ 5 */
6package tools.refinery.store.query; 6package tools.refinery.store.query.resultset;
7 7
8import tools.refinery.store.map.Cursor; 8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.query.dnf.Query; 9import tools.refinery.store.query.dnf.Query;
@@ -15,4 +15,8 @@ public non-sealed interface ResultSet<T> extends AnyResultSet {
15 T get(Tuple parameters); 15 T get(Tuple parameters);
16 16
17 Cursor<Tuple, T> getAll(); 17 Cursor<Tuple, T> getAll();
18
19 void addListener(ResultSetListener<T> listener);
20
21 void removeListener(ResultSetListener<T> listener);
18} 22}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java
new file mode 100644
index 00000000..fd8a503e
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java
@@ -0,0 +1,13 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.query.resultset;
7
8import tools.refinery.store.tuple.Tuple;
9
10@FunctionalInterface
11public interface ResultSetListener<T> {
12 void put(Tuple key, T fromValue, T toValue);
13}
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java
new file mode 100644
index 00000000..b568b99d
--- /dev/null
+++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java
@@ -0,0 +1,754 @@
1/*
2 * Copyright (c) 2021 Rodion Efremov
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 *
5 * SPDX-License-Identifier: MIT OR EPL-2.0
6 */
7package tools.refinery.store.query.utils;
8
9import java.util.*;
10
11/**
12 * This class implements an order statistic tree which is based on AVL-trees.
13 * <p>
14 * This class was copied into <i>Refinery</i> from
15 * <a href="https://github.com/coderodde/OrderStatisticTree/tree/546c343b9f5d868e394a079ff32691c9dbfd83e3">https://github.com/coderodde/OrderStatisticTree</a>
16 * and is available under the
17 * <a href="https://github.com/coderodde/OrderStatisticTree/blob/master/LICENSE">MIT License</a>.
18 * We also incorporated changes by <a href="https://github.com/coderodde/OrderStatisticTree/issues/3">Eugene Schava</a>
19 * and cleaned up some linter warnings.
20 *
21 * @param <T> the actual element type.
22 * @author Rodion "rodde" Efremov
23 * @version based on 1.6 (Feb 11, 2016)
24 */
25public class OrderStatisticTree<T extends Comparable<? super T>> implements Set<T> {
26
27 @Override
28 public Iterator<T> iterator() {
29 return new TreeIterator();
30 }
31
32 private final class TreeIterator implements Iterator<T> {
33
34 private Node<T> previousNode;
35 private Node<T> nextNode;
36 private int expectedModCount = modCount;
37
38 TreeIterator() {
39 if (root == null) {
40 nextNode = null;
41 } else {
42 nextNode = minimumNode(root);
43 }
44 }
45
46 @Override
47 public boolean hasNext() {
48 return nextNode != null;
49 }
50
51 @Override
52 public T next() {
53 if (nextNode == null) {
54 throw new NoSuchElementException("Iteration exceeded.");
55 }
56
57 checkConcurrentModification();
58 T datum = nextNode.key;
59 previousNode = nextNode;
60 nextNode = successorOf(nextNode);
61 return datum;
62 }
63
64 @Override
65 public void remove() {
66 if (previousNode == null) {
67 throw new IllegalStateException(
68 nextNode == null ?
69 "Not a single call to next(); nothing to remove." :
70 "Removing the same element twice."
71 );
72 }
73
74 checkConcurrentModification();
75
76 Node<T> x = deleteNode(previousNode);
77 fixAfterModification(x, false);
78
79 if (x == nextNode) {
80 nextNode = previousNode;
81 }
82
83 expectedModCount = ++modCount;
84 size--;
85 previousNode = null;
86 }
87
88 private void checkConcurrentModification() {
89 if (expectedModCount != modCount) {
90 throw new ConcurrentModificationException(
91 "The set was modified while iterating.");
92 }
93 }
94
95 private Node<T> successorOf(Node<T> node) {
96 if (node.right != null) {
97 node = node.right;
98
99 while (node.left != null) {
100 node = node.left;
101 }
102
103 return node;
104 }
105
106 Node<T> parent = node.parent;
107
108 while (parent != null && parent.right == node) {
109 node = parent;
110 parent = parent.parent;
111 }
112
113 return parent;
114 }
115 }
116
117 @Override
118 public Object[] toArray() {
119 Object[] array = new Object[size];
120 Iterator<T> iterator = iterator();
121 int index = 0;
122
123 while (iterator.hasNext()) {
124 array[index++] = iterator.next();
125 }
126
127 return array;
128 }
129
130 @Override
131 public <U> U[] toArray(U[] a) {
132 Iterator<T> iterator = iterator();
133
134 if (size > a.length) {
135 a = Arrays.copyOf(a, size);
136 }
137
138 int index = 0;
139
140 for (; index < size; ++index) {
141 @SuppressWarnings("unchecked")
142 var convertedValue = (U) iterator.next();
143 a[index] = convertedValue;
144 }
145
146 if (index < a.length) {
147 a[index] = null;
148 }
149
150 return a;
151 }
152
153 @Override
154 public boolean containsAll(Collection<?> c) {
155 for (Object element : c) {
156 if (!contains(element)) {
157 return false;
158 }
159 }
160
161 return true;
162 }
163
164 @Override
165 public boolean addAll(Collection<? extends T> c) {
166 boolean modified = false;
167
168 for (T element : c) {
169 if (add(element)) {
170 modified = true;
171 }
172 }
173
174 return modified;
175 }
176
177 @Override
178 public boolean retainAll(Collection<?> c) {
179 if (!c.getClass().equals(HashSet.class)) {
180 c = new HashSet<>(c);
181 }
182
183 Iterator<T> iterator = iterator();
184 boolean modified = false;
185
186 while (iterator.hasNext()) {
187 T element = iterator.next();
188
189 if (!c.contains(element)) {
190 iterator.remove();
191 modified = true;
192 }
193 }
194
195 return modified;
196 }
197
198 @Override
199 public boolean removeAll(Collection<?> c) {
200 boolean modified = false;
201
202 for (Object element : c) {
203 if (remove(element)) {
204 modified = true;
205 }
206 }
207
208 return modified;
209 }
210
211 private static final class Node<T> {
212 T key;
213
214 Node<T> parent;
215 Node<T> left;
216 Node<T> right;
217
218 int height;
219 int count;
220
221 Node(T key) {
222 this.key = key;
223 }
224 }
225
226 private Node<T> root;
227 private int size;
228 private int modCount;
229
230 @Override
231 public boolean add(T element) {
232 Objects.requireNonNull(element, "The input element is null.");
233
234 if (root == null) {
235 root = new Node<>(element);
236 size = 1;
237 modCount++;
238 return true;
239 }
240
241 Node<T> parent = null;
242 Node<T> node = root;
243 int cmp;
244
245 while (node != null) {
246 cmp = element.compareTo(node.key);
247
248 if (cmp == 0) {
249 // The element is already in this tree.
250 return false;
251 }
252
253 parent = node;
254
255 if (cmp < 0) {
256 node = node.left;
257 } else {
258 node = node.right;
259 }
260 }
261
262 Node<T> newnode = new Node<>(element);
263
264 if (element.compareTo(parent.key) < 0) {
265 parent.left = newnode;
266 } else {
267 parent.right = newnode;
268 }
269
270 newnode.parent = parent;
271 size++;
272 modCount++;
273 Node<T> hi = parent;
274 Node<T> lo = newnode;
275
276 while (hi != null) {
277 if (hi.left == lo) {
278 hi.count++;
279 }
280
281 lo = hi;
282 hi = hi.parent;
283 }
284
285 fixAfterModification(newnode, true);
286 return true;
287 }
288
289 @Override
290 public boolean contains(Object o) {
291 @SuppressWarnings("unchecked")
292 T element = (T) o;
293 Node<T> x = root;
294 int cmp;
295
296 while (x != null && (cmp = element.compareTo(x.key)) != 0) {
297 if (cmp < 0) {
298 x = x.left;
299 } else {
300 x = x.right;
301 }
302 }
303
304 return x != null;
305 }
306
307 @Override
308 public boolean remove(Object o) {
309 @SuppressWarnings("unchecked")
310 T element = (T) o;
311 Node<T> x = root;
312 int cmp;
313
314 while (x != null && (cmp = element.compareTo(x.key)) != 0) {
315 if (cmp < 0) {
316 x = x.left;
317 } else {
318 x = x.right;
319 }
320 }
321
322 if (x == null) {
323 return false;
324 }
325
326 x = deleteNode(x);
327 fixAfterModification(x, false);
328 size--;
329 modCount++;
330 return true;
331 }
332
333 public T get(int index) {
334 checkIndex(index);
335 Node<T> node = root;
336
337 while (true) {
338 if (index > node.count) {
339 index -= node.count + 1;
340 node = node.right;
341 } else if (index < node.count) {
342 node = node.left;
343 } else {
344 return node.key;
345 }
346 }
347 }
348
349 public int indexOf(T element) {
350 Node<T> node = root;
351
352 if (root == null) {
353 return -1;
354 }
355
356 int rank = root.count;
357 int cmp;
358
359 while (true) {
360 if ((cmp = element.compareTo(node.key)) < 0) {
361 if (node.left == null) {
362 return -1;
363 }
364
365 rank -= (node.count - node.left.count);
366 node = node.left;
367 } else if (cmp > 0) {
368 if (node.right == null) {
369 return -1;
370 }
371
372 rank += 1 + node.right.count;
373 node = node.right;
374 } else {
375 return rank;
376 }
377 }
378 }
379
380 @Override
381 public int size() {
382 return size;
383 }
384
385 @Override
386 public boolean isEmpty() {
387 return size == 0;
388 }
389
390 @Override
391 public void clear() {
392 modCount += size;
393 root = null;
394 size = 0;
395 }
396
397
398 private void checkIndex(int index) {
399 if (index < 0) {
400 throw new IndexOutOfBoundsException(
401 "The input index is negative: " + index);
402 }
403
404 if (index >= size) {
405 throw new IndexOutOfBoundsException(
406 "The input index is too large: " + index +
407 ", the size of this tree is " + size);
408 }
409 }
410
411 @SuppressWarnings("squid:S3776")
412 private Node<T> deleteNode(Node<T> node) {
413 if (node.left == null && node.right == null) {
414 // 'node' has no children.
415 Node<T> parent = node.parent;
416
417 if (parent == null) {
418 // 'node' is the root node of this tree.
419 root = null;
420 ++modCount;
421 return node;
422 }
423
424 Node<T> lo = node;
425 Node<T> hi = parent;
426
427 while (hi != null) {
428 if (hi.left == lo) {
429 hi.count--;
430 }
431
432 lo = hi;
433 hi = hi.parent;
434 }
435
436 if (node == parent.left) {
437 parent.left = null;
438 } else {
439 parent.right = null;
440 }
441
442 return node;
443 }
444
445 if (node.left != null && node.right != null) {
446 // 'node' has both children.
447 Node<T> successor = minimumNode(node.right);
448 node.key = successor.key;
449 Node<T> child = successor.right;
450 Node<T> parent = successor.parent;
451
452 if (parent.left == successor) {
453 parent.left = child;
454 } else {
455 parent.right = child;
456 }
457
458 if (child != null) {
459 child.parent = parent;
460 }
461
462 Node<T> lo = child;
463 Node<T> hi = parent;
464
465 while (hi != null) {
466 if (hi.left == lo) {
467 hi.count--;
468 }
469
470 lo = hi;
471 hi = hi.parent;
472 }
473
474 return successor;
475 }
476
477 Node<T> child;
478
479 // 'node' has only one child.
480 if (node.left != null) {
481 child = node.left;
482 } else {
483 child = node.right;
484 }
485
486 Node<T> parent = node.parent;
487 child.parent = parent;
488
489 if (parent == null) {
490 root = child;
491 return node;
492 }
493
494 if (node == parent.left) {
495 parent.left = child;
496 } else {
497 parent.right = child;
498 }
499
500 Node<T> hi = parent;
501 Node<T> lo = child;
502
503 while (hi != null) {
504 if (hi.left == lo) {
505 hi.count--;
506 }
507
508 lo = hi;
509 hi = hi.parent;
510 }
511
512 return node;
513
514 }
515
516 private Node<T> minimumNode(Node<T> node) {
517 while (node.left != null) {
518 node = node.left;
519 }
520
521 return node;
522 }
523
524 private int height(Node<T> node) {
525 return node == null ? -1 : node.height;
526 }
527
528 private Node<T> leftRotate(Node<T> node1) {
529 Node<T> node2 = node1.right;
530 node2.parent = node1.parent;
531 node1.parent = node2;
532 node1.right = node2.left;
533 node2.left = node1;
534
535 if (node1.right != null) {
536 node1.right.parent = node1;
537 }
538
539 node1.height = Math.max(height(node1.left), height(node1.right)) + 1;
540 node2.height = Math.max(height(node2.left), height(node2.right)) + 1;
541 node2.count += node1.count + 1;
542 return node2;
543 }
544
545 private Node<T> rightRotate(Node<T> node1) {
546 Node<T> node2 = node1.left;
547 node2.parent = node1.parent;
548 node1.parent = node2;
549 node1.left = node2.right;
550 node2.right = node1;
551
552 if (node1.left != null) {
553 node1.left.parent = node1;
554 }
555
556 node1.height = Math.max(height(node1.left), height(node1.right)) + 1;
557 node2.height = Math.max(height(node2.left), height(node2.right)) + 1;
558 node1.count -= node2.count + 1;
559 return node2;
560 }
561
562 private Node<T> rightLeftRotate(Node<T> node1) {
563 Node<T> node2 = node1.right;
564 node1.right = rightRotate(node2);
565 return leftRotate(node1);
566 }
567
568 private Node<T> leftRightRotate(Node<T> node1) {
569 Node<T> node2 = node1.left;
570 node1.left = leftRotate(node2);
571 return rightRotate(node1);
572 }
573
574 // Fixing an insertion: use insertionMode = true.
575 // Fixing a deletion: use insertionMode = false.
576 @SuppressWarnings("squid:S3776")
577 private void fixAfterModification(Node<T> node, boolean insertionMode) {
578 Node<T> parent = node.parent;
579 Node<T> grandParent;
580 Node<T> subTree;
581
582 while (parent != null) {
583 if (height(parent.left) == height(parent.right) + 2) {
584 grandParent = parent.parent;
585
586 if (height(parent.left.left) >= height(parent.left.right)) {
587 subTree = rightRotate(parent);
588 } else {
589 subTree = leftRightRotate(parent);
590 }
591
592 if (grandParent == null) {
593 root = subTree;
594 } else if (grandParent.left == parent) {
595 grandParent.left = subTree;
596 } else {
597 grandParent.right = subTree;
598 }
599
600 if (grandParent != null) {
601 grandParent.height = Math.max(
602 height(grandParent.left),
603 height(grandParent.right)) + 1;
604 }
605
606 if (insertionMode) {
607 // Whenever fixing after insertion, at most one rotation is
608 // required in order to maintain the balance.
609 return;
610 }
611 } else if (height(parent.right) == height(parent.left) + 2) {
612 grandParent = parent.parent;
613
614 if (height(parent.right.right) >= height(parent.right.left)) {
615 subTree = leftRotate(parent);
616 } else {
617 subTree = rightLeftRotate(parent);
618 }
619
620 if (grandParent == null) {
621 root = subTree;
622 } else if (grandParent.left == parent) {
623 grandParent.left = subTree;
624 } else {
625 grandParent.right = subTree;
626 }
627
628 if (grandParent != null) {
629 grandParent.height =
630 Math.max(height(grandParent.left),
631 height(grandParent.right)) + 1;
632 }
633
634 if (insertionMode) {
635 return;
636 }
637 }
638
639 parent.height = Math.max(height(parent.left),
640 height(parent.right)) + 1;
641 parent = parent.parent;
642 }
643 }
644
645 boolean isHealthy() {
646 if (root == null) {
647 return true;
648 }
649
650 return !containsCycles()
651 && heightsAreCorrect()
652 && isBalanced()
653 && isWellIndexed();
654 }
655
656 private boolean containsCycles() {
657 Set<Node<T>> visitedNodes = new HashSet<>();
658 return containsCycles(root, visitedNodes);
659 }
660
661 private boolean containsCycles(Node<T> current, Set<Node<T>> visitedNodes) {
662 if (current == null) {
663 return false;
664 }
665
666 if (visitedNodes.contains(current)) {
667 return true;
668 }
669
670 visitedNodes.add(current);
671
672 return containsCycles(current.left, visitedNodes)
673 || containsCycles(current.right, visitedNodes);
674 }
675
676 private boolean heightsAreCorrect() {
677 return getHeight(root) == root.height;
678 }
679
680 private int getHeight(Node<T> node) {
681 if (node == null) {
682 return -1;
683 }
684
685 int leftTreeHeight = getHeight(node.left);
686
687 if (leftTreeHeight == Integer.MIN_VALUE) {
688 return Integer.MIN_VALUE;
689 }
690
691 int rightTreeHeight = getHeight(node.right);
692
693 if (rightTreeHeight == Integer.MIN_VALUE) {
694 return Integer.MIN_VALUE;
695 }
696
697 if (node.height == Math.max(leftTreeHeight, rightTreeHeight) + 1) {
698 return node.height;
699 }
700
701 return Integer.MIN_VALUE;
702 }
703
704 private boolean isBalanced() {
705 return isBalanced(root);
706 }
707
708 private boolean isBalanced(Node<T> node) {
709 if (node == null) {
710 return true;
711 }
712
713 if (!isBalanced(node.left)) {
714 return false;
715 }
716
717 if (!isBalanced(node.right)) {
718 return false;
719 }
720
721 int leftHeight = height(node.left);
722 int rightHeight = height(node.right);
723
724 return Math.abs(leftHeight - rightHeight) < 2;
725 }
726
727 private boolean isWellIndexed() {
728 return size == count(root);
729 }
730
731 private int count(Node<T> node) {
732 if (node == null) {
733 return 0;
734 }
735
736 int leftTreeSize = count(node.left);
737
738 if (leftTreeSize == Integer.MIN_VALUE) {
739 return Integer.MIN_VALUE;
740 }
741
742 if (node.count != leftTreeSize) {
743 return Integer.MIN_VALUE;
744 }
745
746 int rightTreeSize = count(node.right);
747
748 if (rightTreeSize == Integer.MIN_VALUE) {
749 return Integer.MIN_VALUE;
750 }
751
752 return leftTreeSize + 1 + rightTreeSize;
753 }
754}
diff --git a/subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java b/subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java
new file mode 100644
index 00000000..cbb48603
--- /dev/null
+++ b/subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java
@@ -0,0 +1,634 @@
1/*
2 * Copyright (c) 2021 Rodion Efremov
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 *
5 * SPDX-License-Identifier: MIT OR EPL-2.0
6 */
7package tools.refinery.store.query.utils;
8
9import org.junit.jupiter.api.BeforeEach;
10import org.junit.jupiter.api.Test;
11import org.junit.jupiter.params.ParameterizedTest;
12import org.junit.jupiter.params.provider.Arguments;
13import org.junit.jupiter.params.provider.MethodSource;
14
15import java.util.*;
16import java.util.stream.Stream;
17
18import static org.junit.jupiter.api.Assertions.*;
19
20/**
21 * Tests for an order statistic tree which is based on AVL-trees.
22 * <p>
23 * This class was copied into <i>Refinery</i> from
24 * <a href="https://github.com/coderodde/OrderStatisticTree/tree/546c343b9f5d868e394a079ff32691c9dbfd83e3">https://github.com/coderodde/OrderStatisticTree</a>
25 * and is available under the
26 * <a href="https://github.com/coderodde/OrderStatisticTree/blob/master/LICENSE">MIT License</a>.
27 * We also migrated the code to Junit 5, cleaned up some linter warnings, and made the tests deterministic by fixing
28 * the random seeds.
29 *
30 * @author Rodion "rodde" Efremov
31 * @version based on 1.6 (Feb 11, 2016)
32 */
33class OrderStatisticTreeTest {
34 private final OrderStatisticTree<Integer> tree = new OrderStatisticTree<>();
35
36 private final TreeSet<Integer> set = new TreeSet<>();
37
38 @BeforeEach
39 void before() {
40 tree.clear();
41 set.clear();
42 }
43
44 @Test
45 void testAdd() {
46 assertEquals(set.isEmpty(), tree.isEmpty());
47
48 for (int i = 10; i < 30; i += 2) {
49 assertTrue(tree.isHealthy());
50 assertEquals(set.contains(i), tree.contains(i));
51 assertEquals(set.add(i), tree.add(i));
52 assertEquals(set.add(i), tree.add(i));
53 assertEquals(set.contains(i), tree.contains(i));
54 assertTrue(tree.isHealthy());
55 }
56
57 assertEquals(set.isEmpty(), tree.isEmpty());
58 }
59
60 @Test
61 void testAddAll() {
62 for (int i = 0; i < 10; ++i) {
63 assertEquals(set.add(i), tree.add(i));
64 }
65
66 Collection<Integer> coll = Arrays.asList(10, 9, 7, 11, 12);
67
68 assertEquals(set.addAll(coll), tree.addAll(coll));
69 assertEquals(set.size(), tree.size());
70
71 for (int i = -10; i < 20; ++i) {
72 assertEquals(set.contains(i), tree.contains(i));
73 }
74 }
75
76 @Test
77 void testClear() {
78 for (int i = 0; i < 2000; ++i) {
79 set.add(i);
80 tree.add(i);
81 }
82
83 assertEquals(set.size(), tree.size());
84 set.clear();
85 tree.clear();
86 // We expect {@code tree.size()} to always be 0, but we also test for it.
87 //noinspection ConstantValue
88 assertEquals(0, tree.size());
89 }
90
91 @Test
92 void testContains() {
93 for (int i = 100; i < 200; i += 3) {
94 assertTrue(tree.isHealthy());
95 assertEquals(set.add(i), tree.add(i));
96 assertTrue(tree.isHealthy());
97 }
98
99 assertEquals(set.size(), tree.size());
100
101 for (int i = 0; i < 300; ++i) {
102 assertEquals(set.contains(i), tree.contains(i));
103 }
104 }
105
106 @Test
107 void testContainsAll() {
108 for (int i = 0; i < 50; ++i) {
109 set.add(i);
110 tree.add(i);
111 }
112
113 Collection<Integer> coll = new HashSet<>();
114
115 for (int i = 10; i < 20; ++i) {
116 coll.add(i);
117 }
118
119 assertEquals(set.containsAll(coll), tree.containsAll(coll));
120 coll.add(100);
121 assertEquals(set.containsAll(coll), tree.containsAll(coll));
122 }
123
124 @Test
125 void testRemove() {
126 for (int i = 0; i < 200; ++i) {
127 assertEquals(set.add(i), tree.add(i));
128 }
129
130 for (int i = 50; i < 150; i += 2) {
131 assertEquals(set.remove(i), tree.remove(i));
132 assertTrue(tree.isHealthy());
133 }
134
135 for (int i = -100; i < 300; ++i) {
136 assertEquals(set.contains(i), tree.contains(i));
137 }
138 }
139
140 @Test
141 void testRemoveLast() {
142 tree.add(1);
143 tree.remove(1);
144 assertEquals(0, tree.size());
145 }
146
147 @Test
148 void testRemoveAll() {
149 for (int i = 0; i < 40; ++i) {
150 set.add(i);
151 tree.add(i);
152 }
153
154 Collection<Integer> coll = new HashSet<>();
155
156 for (int i = 10; i < 20; ++i) {
157 coll.add(i);
158 }
159
160 assertEquals(set.removeAll(coll), tree.removeAll(coll));
161
162 for (int i = -10; i < 50; ++i) {
163 assertEquals(set.contains(i), tree.contains(i));
164 }
165
166 assertEquals(set.removeAll(coll), tree.removeAll(coll));
167
168 for (int i = -10; i < 50; ++i) {
169 assertEquals(set.contains(i), tree.contains(i));
170 }
171 }
172
173 @Test
174 void testSize() {
175 for (int i = 0; i < 200; ++i) {
176 assertEquals(set.size(), tree.size());
177 assertEquals(set.add(i), tree.add(i));
178 assertEquals(set.size(), tree.size());
179 }
180 }
181
182 @Test
183 void testIndexOf() {
184 for (int i = 0; i < 100; ++i) {
185 assertTrue(tree.add(i * 2));
186 }
187
188 for (int i = 0; i < 100; ++i) {
189 assertEquals(i, tree.indexOf(2 * i));
190 }
191
192 for (int i = 100; i < 150; ++i) {
193 assertEquals(-1, tree.indexOf(2 * i));
194 }
195 }
196
197 @Test
198 void testEmpty() {
199 assertEquals(set.isEmpty(), tree.isEmpty());
200 set.add(0);
201 tree.add(0);
202 assertEquals(set.isEmpty(), tree.isEmpty());
203 }
204
205 @Test
206 void testEmptyTreeGetThrowsOnNegativeIndex() {
207 assertThrows(IndexOutOfBoundsException.class, () -> tree.get(-1));
208 }
209
210 @Test
211 void testEmptyTreeSelectThrowsOnTooLargeIndex() {
212 assertThrows(IndexOutOfBoundsException.class, () -> tree.get(0));
213 }
214
215 @Test
216 void testSelectThrowsOnNegativeIndex() {
217 for (int i = 0; i < 5; ++i) {
218 tree.add(i);
219 }
220
221 assertThrows(IndexOutOfBoundsException.class, () -> tree.get(-1));
222 }
223
224 @Test
225 void testSelectThrowsOnTooLargeIndex() {
226 for (int i = 0; i < 5; ++i) {
227 tree.add(i);
228 }
229
230 assertThrows(IndexOutOfBoundsException.class, () -> tree.get(5));
231 }
232
233 @Test
234 void testGet() {
235 for (int i = 0; i < 100; i += 3) {
236 tree.add(i);
237 }
238
239 for (int i = 0; i < tree.size(); ++i) {
240 assertEquals(Integer.valueOf(3 * i), tree.get(i));
241 }
242 }
243
244 @Test
245 void findBug() {
246 tree.add(0);
247 assertTrue(tree.isHealthy());
248
249 tree.add(-1);
250 tree.remove(-1);
251 assertTrue(tree.isHealthy());
252
253 tree.add(1);
254 tree.remove(1);
255 assertTrue(tree.isHealthy());
256
257 tree.add(-1);
258 tree.add(1);
259 tree.remove(0);
260 assertTrue(tree.isHealthy());
261
262 tree.clear();
263 tree.add(0);
264 tree.add(-1);
265 tree.add(10);
266 tree.add(5);
267 tree.add(15);
268 tree.add(11);
269 tree.add(30);
270 tree.add(7);
271
272 tree.remove(-1);
273
274 assertTrue(tree.isHealthy());
275 }
276
277 @ParameterizedTest(name = "seed = {0}")
278 @MethodSource("seedSource")
279 void tryReproduceTheCounterBug(long seed) {
280 Random random = new Random(seed);
281 List<Integer> list = new ArrayList<>();
282
283 for (int i = 0; i < 10; ++i) {
284 int number = random.nextInt(1000);
285 list.add(number);
286 tree.add(number);
287 assertTrue(tree.isHealthy());
288 }
289
290 for (Integer i : list) {
291 tree.remove(i);
292 boolean healthy = tree.isHealthy();
293 assertTrue(healthy);
294 }
295 }
296
297 @Test
298 void testEmptyIterator() {
299 var iterator = tree.iterator();
300 assertThrows(NoSuchElementException.class, iterator::next);
301 }
302
303 @Test
304 void testIteratorThrowsOnDoubleRemove() {
305 for (int i = 10; i < 20; ++i) {
306 set.add(i);
307 tree.add(i);
308 }
309
310 Iterator<Integer> iterator1 = set.iterator();
311 Iterator<Integer> iterator2 = tree.iterator();
312
313 for (int i = 0; i < 3; ++i) {
314 assertEquals(iterator1.next(), iterator2.next());
315 }
316
317 iterator1.remove();
318 iterator2.remove();
319
320 assertThrows(IllegalStateException.class, iterator1::remove);
321 assertThrows(IllegalStateException.class, iterator2::remove);
322 }
323
324 @Test
325 void testIterator() {
326 for (int i = 0; i < 5; ++i) {
327 tree.add(i);
328 set.add(i);
329 }
330
331 Iterator<Integer> iterator1 = set.iterator();
332 Iterator<Integer> iterator2 = tree.iterator();
333
334 for (int i = 0; i < 5; ++i) {
335 assertEquals(iterator1.hasNext(), iterator2.hasNext());
336 assertEquals(iterator1.next(), iterator2.next());
337 }
338
339 assertEquals(iterator1.hasNext(), iterator2.hasNext());
340
341 assertThrows(NoSuchElementException.class, iterator1::next);
342 assertThrows(NoSuchElementException.class, iterator2::next);
343 }
344
345 @Test
346 void testRemoveBeforeNextThrowsEmpty() {
347 var setIterator = set.iterator();
348 assertThrows(IllegalStateException.class, setIterator::remove);
349
350 var treeIterator = tree.iterator();
351 assertThrows(IllegalStateException.class, treeIterator::remove);
352 }
353
354 @Test
355 void testRemoveThrowsWithoutNext() {
356 for (int i = 0; i < 10; ++i) {
357 tree.add(i);
358 set.add(i);
359 }
360
361 Iterator<Integer> iterator1 = set.iterator();
362 Iterator<Integer> iterator2 = tree.iterator();
363
364 for (int i = 0; i < 4; ++i) {
365 assertEquals(iterator1.hasNext(), iterator2.hasNext());
366 assertEquals(iterator1.next(), iterator2.next());
367 }
368
369 iterator1.remove();
370 iterator2.remove();
371
372 assertThrows(IllegalStateException.class, iterator1::remove);
373 assertThrows(IllegalStateException.class, iterator2::remove);
374 }
375
376 @Test
377 void testRetainAll() {
378 for (int i = 0; i < 100; ++i) {
379 set.add(i);
380 tree.add(i);
381 }
382
383 Collection<Integer> coll = Arrays.asList(26, 29, 25);
384
385 assertEquals(set.retainAll(coll), tree.retainAll(coll));
386 assertEquals(set.size(), tree.size());
387
388 assertTrue(set.containsAll(tree));
389 assertTrue(tree.containsAll(set));
390 }
391
392 @Test
393 void testIteratorRemove() {
394 for (int i = 10; i < 16; ++i) {
395 assertEquals(set.add(i), tree.add(i));
396 }
397
398 Iterator<Integer> iterator1 = set.iterator();
399 Iterator<Integer> iterator2 = tree.iterator();
400
401 assertEquals(iterator1.hasNext(), iterator2.hasNext());
402 assertEquals(iterator1.next(), iterator2.next());
403
404 assertEquals(iterator1.hasNext(), iterator2.hasNext());
405 assertEquals(iterator1.next(), iterator2.next());
406
407 iterator1.remove(); // remove 11
408 iterator2.remove();
409
410 assertEquals(iterator1.hasNext(), iterator2.hasNext());
411 assertEquals(iterator1.next(), iterator2.next());
412
413 assertEquals(iterator1.hasNext(), iterator2.hasNext());
414 assertEquals(iterator1.next(), iterator2.next());
415
416 iterator1.remove(); // remove 13
417 iterator2.remove();
418
419 assertEquals(set.size(), tree.size());
420
421 for (int i = 10; i < 16; ++i) {
422 assertEquals(set.contains(i), tree.contains(i));
423 }
424 }
425
426 @ParameterizedTest(name = "seed = {0}")
427 @MethodSource("seedSource")
428 void testIteratorBruteForce(long seed) {
429 for (int i = 0; i < 1000; ++i) {
430 assertEquals(set.add(i), tree.add(i));
431 }
432
433 Iterator<Integer> iterator1 = set.iterator();
434 Iterator<Integer> iterator2 = tree.iterator();
435
436 Random random = new Random(seed);
437
438 while (true) {
439 if (!iterator1.hasNext()) {
440 assertFalse(iterator2.hasNext());
441 break;
442 }
443
444 boolean toRemove = random.nextBoolean();
445
446 if (toRemove) {
447 boolean thrown = false;
448
449 try {
450 iterator1.remove();
451 } catch (IllegalStateException ex) {
452 thrown = true;
453 }
454
455 if (thrown) {
456 assertThrows(IllegalStateException.class, iterator2::remove);
457 } else {
458 iterator2.remove();
459 }
460 } else {
461 assertEquals(iterator1.hasNext(), iterator2.hasNext());
462
463 if (iterator1.hasNext()) {
464 assertEquals(iterator1.next(), iterator2.next());
465 } else {
466 break;
467 }
468 }
469 }
470
471 assertEquals(set.size(), tree.size());
472 assertTrue(tree.isHealthy());
473 assertTrue(set.containsAll(tree));
474 assertTrue(tree.containsAll(set));
475 }
476
477 @Test
478 void testIteratorConcurrentModification() {
479 for (int i = 0; i < 100; ++i) {
480 set.add(i);
481 tree.add(i);
482 }
483
484 Iterator<Integer> iterator1 = set.iterator();
485 Iterator<Integer> iterator2 = tree.iterator();
486
487 set.remove(10);
488 tree.remove(10);
489
490 assertEquals(iterator1.hasNext(), iterator2.hasNext());
491
492 boolean thrown = false;
493
494 try {
495 iterator1.next();
496 } catch (ConcurrentModificationException ex) {
497 thrown = true;
498 }
499
500 if (thrown) {
501 assertThrows(ConcurrentModificationException.class, iterator2::next);
502 } else {
503 iterator2.next();
504 }
505 }
506
507 @Test
508 void testIteratorConcurrentRemove() {
509 for (int i = 10; i < 20; ++i) {
510 set.add(i);
511 tree.add(i);
512 }
513
514 Iterator<Integer> iterator1 = set.iterator();
515 Iterator<Integer> iterator2 = tree.iterator();
516
517 for (int i = 0; i < 4; ++i) {
518 iterator1.next();
519 iterator2.next();
520 }
521
522 // None of them contains 2, should not change the modification count.
523 set.remove(2);
524 tree.remove(2);
525
526 iterator1.remove();
527 iterator2.remove();
528
529 iterator1.next();
530 iterator2.next();
531
532 set.remove(12);
533 tree.remove(12);
534
535 // Both of them should throw.
536 assertThrows(ConcurrentModificationException.class, iterator1::remove);
537 assertThrows(ConcurrentModificationException.class, iterator2::remove);
538 }
539
540 @Test
541 void testConcurrentOrIllegalStateOnRemove() {
542 for (int i = 0; i < 10; ++i) {
543 set.add(i);
544 tree.add(i);
545 }
546
547 Iterator<Integer> iterator1 = set.iterator();
548 Iterator<Integer> iterator2 = tree.iterator();
549
550 set.add(100);
551 tree.add(100);
552
553 assertThrows(IllegalStateException.class, iterator1::remove);
554 assertThrows(IllegalStateException.class, iterator2::remove);
555 }
556
557 @Test
558 void testConcurrentIterators() {
559 for (int i = 0; i < 10; ++i) {
560 set.add(i);
561 tree.add(i);
562 }
563
564 Iterator<Integer> iterator1a = set.iterator();
565 Iterator<Integer> iterator1b = set.iterator();
566 Iterator<Integer> iterator2a = tree.iterator();
567 Iterator<Integer> iterator2b = tree.iterator();
568
569 for (int i = 0; i < 3; ++i) {
570 iterator1a.next();
571 iterator2a.next();
572 }
573
574 iterator1a.remove();
575 iterator2a.remove();
576
577 assertEquals(iterator1b.hasNext(), iterator2b.hasNext());
578
579 assertThrows(ConcurrentModificationException.class, iterator1b::next);
580 assertThrows(ConcurrentModificationException.class, iterator2b::next);
581 }
582
583 @ParameterizedTest(name = "seed = {0}")
584 @MethodSource("seedSource")
585 void testToArray(long seed) {
586 Random r = new Random(seed);
587
588 for (int i = 0; i < 50; ++i) {
589 int num = r.nextInt();
590 set.add(num);
591 tree.add(num);
592 }
593
594 assertArrayEquals(set.toArray(), tree.toArray());
595 }
596
597 @Test
598 void testToArrayGeneric() {
599 for (int i = 0; i < 100; ++i) {
600 set.add(i);
601 tree.add(i);
602 }
603
604 Integer[] array1before = new Integer[99];
605 Integer[] array2before = new Integer[99];
606
607 Integer[] array1after = set.toArray(array1before);
608 Integer[] array2after = tree.toArray(array2before);
609
610 assertNotSame(array1before, array1after);
611 assertNotSame(array2before, array2after);
612 assertArrayEquals(array1after, array2after);
613
614 set.remove(1);
615 tree.remove(1);
616
617 array1after = set.toArray(array1before);
618 array2after = tree.toArray(array2before);
619
620 assertSame(array1before, array1after);
621 assertSame(array2before, array2after);
622 assertArrayEquals(array1after, array2after);
623 }
624
625 static Stream<Arguments> seedSource() {
626 return Stream.of(
627 Arguments.of(0L),
628 Arguments.of(1L),
629 Arguments.of(2L),
630 Arguments.of(3L),
631 Arguments.of(4L)
632 );
633 }
634}
diff --git a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/ReasoningAdapter.java b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/ReasoningAdapter.java
index 8f319242..6d5d6f89 100644
--- a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/ReasoningAdapter.java
+++ b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/ReasoningAdapter.java
@@ -6,7 +6,7 @@
6package tools.refinery.store.reasoning; 6package tools.refinery.store.reasoning;
7 7
8import tools.refinery.store.adapter.ModelAdapter; 8import tools.refinery.store.adapter.ModelAdapter;
9import tools.refinery.store.query.ResultSet; 9import tools.refinery.store.query.resultset.ResultSet;
10import tools.refinery.store.query.dnf.Dnf; 10import tools.refinery.store.query.dnf.Dnf;
11import tools.refinery.store.reasoning.representation.AnyPartialSymbol; 11import tools.refinery.store.reasoning.representation.AnyPartialSymbol;
12import tools.refinery.store.reasoning.representation.PartialRelation; 12import tools.refinery.store.reasoning.representation.PartialRelation;
diff --git a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/internal/ReasoningAdapterImpl.java b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/internal/ReasoningAdapterImpl.java
index 33b6f3c6..1bd3ad2e 100644
--- a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/internal/ReasoningAdapterImpl.java
+++ b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/internal/ReasoningAdapterImpl.java
@@ -10,7 +10,7 @@ import tools.refinery.store.reasoning.ReasoningAdapter;
10import tools.refinery.store.reasoning.PartialInterpretation; 10import tools.refinery.store.reasoning.PartialInterpretation;
11import tools.refinery.store.reasoning.representation.PartialSymbol; 11import tools.refinery.store.reasoning.representation.PartialSymbol;
12import tools.refinery.store.query.dnf.Dnf; 12import tools.refinery.store.query.dnf.Dnf;
13import tools.refinery.store.query.ResultSet; 13import tools.refinery.store.query.resultset.ResultSet;
14 14
15public class ReasoningAdapterImpl implements ReasoningAdapter { 15public class ReasoningAdapterImpl implements ReasoningAdapter {
16 private final Model model; 16 private final Model model;
diff --git a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/literal/ModalConstraint.java b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/literal/ModalConstraint.java
index 5ad1d5f8..4e5a6099 100644
--- a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/literal/ModalConstraint.java
+++ b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/literal/ModalConstraint.java
@@ -7,7 +7,7 @@ package tools.refinery.store.reasoning.literal;
7 7
8import tools.refinery.store.query.Constraint; 8import tools.refinery.store.query.Constraint;
9import tools.refinery.store.query.equality.LiteralEqualityHelper; 9import tools.refinery.store.query.equality.LiteralEqualityHelper;
10import tools.refinery.store.query.Reduction; 10import tools.refinery.store.query.literal.Reduction;
11import tools.refinery.store.query.term.Parameter; 11import tools.refinery.store.query.term.Parameter;
12 12
13import java.util.List; 13import java.util.List;
diff --git a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/translator/base/BaseDecisionInterpretation.java b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/translator/base/BaseDecisionInterpretation.java
index e7b67ae4..2a151aa2 100644
--- a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/translator/base/BaseDecisionInterpretation.java
+++ b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/translator/base/BaseDecisionInterpretation.java
@@ -7,7 +7,7 @@ package tools.refinery.store.reasoning.translator.base;
7 7
8import tools.refinery.store.map.Cursor; 8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.model.Interpretation; 9import tools.refinery.store.model.Interpretation;
10import tools.refinery.store.query.ResultSet; 10import tools.refinery.store.query.resultset.ResultSet;
11import tools.refinery.store.reasoning.MergeResult; 11import tools.refinery.store.reasoning.MergeResult;
12import tools.refinery.store.reasoning.PartialInterpretation; 12import tools.refinery.store.reasoning.PartialInterpretation;
13import tools.refinery.store.reasoning.ReasoningAdapter; 13import tools.refinery.store.reasoning.ReasoningAdapter;
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java
index 6700417a..aae7b344 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java
@@ -5,11 +5,29 @@
5 */ 5 */
6package tools.refinery.store.tuple; 6package tools.refinery.store.tuple;
7 7
8public sealed interface Tuple permits Tuple0, Tuple1, Tuple2, Tuple3, Tuple4, TupleN { 8import org.jetbrains.annotations.NotNull;
9
10public sealed interface Tuple extends Comparable<Tuple> permits Tuple0, Tuple1, Tuple2, Tuple3, Tuple4, TupleN {
9 int getSize(); 11 int getSize();
10 12
11 int get(int element); 13 int get(int element);
12 14
15 @Override
16 default int compareTo(@NotNull Tuple other) {
17 int size = getSize();
18 int compareSize = Integer.compare(size, other.getSize());
19 if (compareSize != 0) {
20 return compareSize;
21 }
22 for (int i = 0; i < size; i++) {
23 int compareElement = Integer.compare(get(i), other.get(i));
24 if (compareElement != 0) {
25 return compareElement;
26 }
27 }
28 return 0;
29 }
30
13 static Tuple0 of() { 31 static Tuple0 of() {
14 return Tuple0.INSTANCE; 32 return Tuple0.INSTANCE;
15 } 33 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java
index 1451099c..a9aa9bf2 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java
@@ -8,6 +8,10 @@ package tools.refinery.store.tuple;
8import static tools.refinery.store.tuple.TupleConstants.TUPLE_BEGIN; 8import static tools.refinery.store.tuple.TupleConstants.TUPLE_BEGIN;
9import static tools.refinery.store.tuple.TupleConstants.TUPLE_END; 9import static tools.refinery.store.tuple.TupleConstants.TUPLE_END;
10 10
11/**
12 * Singleton implementation to ensure only a single empty tuple exists.
13 */
14@SuppressWarnings("squid:S6548")
11public final class Tuple0 implements Tuple { 15public final class Tuple0 implements Tuple {
12 public static final Tuple0 INSTANCE = new Tuple0(); 16 public static final Tuple0 INSTANCE = new Tuple0();
13 17
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java
index cda145d7..388ee3a9 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java
@@ -5,6 +5,7 @@
5 */ 5 */
6package tools.refinery.store.tuple; 6package tools.refinery.store.tuple;
7 7
8import org.jetbrains.annotations.NotNull;
8import tools.refinery.store.model.TupleHashProvider; 9import tools.refinery.store.model.TupleHashProvider;
9 10
10import java.util.Arrays; 11import java.util.Arrays;
@@ -54,11 +55,23 @@ public final class Tuple1 implements Tuple {
54 return 31 + value0; 55 return 31 + value0;
55 } 56 }
56 57
58 @Override
59 public int compareTo(@NotNull Tuple other) {
60 if (other instanceof Tuple1 other1) {
61 return Integer.compare(value0, other1.value0);
62 }
63 return Tuple.super.compareTo(other);
64 }
65
57 /** 66 /**
58 * This class uses safe double-checked locking, see 67 * This class uses safe double-checked locking, see
59 * <a href="https://shipilev.net/blog/2014/safe-public-construction/">Safe Publication and Safe Initialization in 68 * <a href="https://shipilev.net/blog/2014/safe-public-construction/">Safe Publication and Safe Initialization in
60 * Java</a> for details. 69 * Java</a> for details.
70 * <p>
71 * This class implements the singleton pattern to ensure only a single cache exists. This is thread-safe because
72 * of the locking of the cache.
61 */ 73 */
74 @SuppressWarnings("squid:S6548")
62 public static class Cache { 75 public static class Cache {
63 private static final int MIN_CACHE_SIZE = 256; 76 private static final int MIN_CACHE_SIZE = 256;
64 77
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java
index b669674b..6d886fd3 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java
@@ -5,6 +5,8 @@
5 */ 5 */
6package tools.refinery.store.tuple; 6package tools.refinery.store.tuple;
7 7
8import org.jetbrains.annotations.NotNull;
9
8import static tools.refinery.store.tuple.TupleConstants.*; 10import static tools.refinery.store.tuple.TupleConstants.*;
9 11
10public record Tuple2(int value0, int value1) implements Tuple { 12public record Tuple2(int value0, int value1) implements Tuple {
@@ -41,4 +43,16 @@ public record Tuple2(int value0, int value1) implements Tuple {
41 hash = 31 * hash + value1; 43 hash = 31 * hash + value1;
42 return hash; 44 return hash;
43 } 45 }
46
47 @Override
48 public int compareTo(@NotNull Tuple other) {
49 if (other instanceof Tuple2 other2) {
50 int compare0 = Integer.compare(value0, other2.value0);
51 if (compare0 != 0) {
52 return compare0;
53 }
54 return Integer.compare(value1, other2.value1);
55 }
56 return Tuple.super.compareTo(other);
57 }
44} 58}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java
index 542ed328..734e45c2 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java
@@ -5,6 +5,8 @@
5 */ 5 */
6package tools.refinery.store.tuple; 6package tools.refinery.store.tuple;
7 7
8import org.jetbrains.annotations.NotNull;
9
8import static tools.refinery.store.tuple.TupleConstants.*; 10import static tools.refinery.store.tuple.TupleConstants.*;
9 11
10public record Tuple3(int value0, int value1, int value2) implements Tuple { 12public record Tuple3(int value0, int value1, int value2) implements Tuple {
@@ -43,4 +45,20 @@ public record Tuple3(int value0, int value1, int value2) implements Tuple {
43 hash = 31 * hash + value2; 45 hash = 31 * hash + value2;
44 return hash; 46 return hash;
45 } 47 }
48
49 @Override
50 public int compareTo(@NotNull Tuple other) {
51 if (other instanceof Tuple3 other3) {
52 int compare0 = Integer.compare(value0, other3.value0);
53 if (compare0 != 0) {
54 return compare0;
55 }
56 int compare1 = Integer.compare(value1, other3.value1);
57 if (compare1 != 0) {
58 return compare1;
59 }
60 return Integer.compare(value2, other3.value2);
61 }
62 return Tuple.super.compareTo(other);
63 }
46} 64}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java
index 121a15f6..e1b93e7b 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java
@@ -5,6 +5,8 @@
5 */ 5 */
6package tools.refinery.store.tuple; 6package tools.refinery.store.tuple;
7 7
8import org.jetbrains.annotations.NotNull;
9
8import static tools.refinery.store.tuple.TupleConstants.*; 10import static tools.refinery.store.tuple.TupleConstants.*;
9 11
10public record Tuple4(int value0, int value1, int value2, int value3) implements Tuple { 12public record Tuple4(int value0, int value1, int value2, int value3) implements Tuple {
@@ -46,4 +48,24 @@ public record Tuple4(int value0, int value1, int value2, int value3) implements
46 hash = 31 * hash + value3; 48 hash = 31 * hash + value3;
47 return hash; 49 return hash;
48 } 50 }
51
52 @Override
53 public int compareTo(@NotNull Tuple other) {
54 if (other instanceof Tuple4 other4) {
55 int compare0 = Integer.compare(value0, other4.value0);
56 if (compare0 != 0) {
57 return compare0;
58 }
59 int compare1 = Integer.compare(value1, other4.value1);
60 if (compare1 != 0) {
61 return compare1;
62 }
63 int compare2 = Integer.compare(value2, other4.value2);
64 if (compare2 != 0) {
65 return compare2;
66 }
67 return Integer.compare(value3, other4.value3);
68 }
69 return Tuple.super.compareTo(other);
70 }
49} 71}
generated by cgit v1.2.3-54-g00ecf (git 2.45.1) at 2024-05-28 07:37:33 +0000