feat: ordered query ResultSet

Enable deterministic state-space exploration by ordering activations in
lexicographic order.

This preliminary implementation adds oredering as a wrapper for ResultSet
instances, but more sophisticated support could be built directly into query
engine adapters if a query engine supports deterministic output by default.

* Implements Comparable for tuples with loops unrolled for small tuples by hand.
* Cleans up the contents of the (root of the) tools.refinery.query package.
* Adds ResultSetListener to notify clients about ResultSet changes.
* Adds OrderStatisticTree data structure for determinisitc ordering of keys.

6 files changed, 90 insertions, 1 deletions

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 @@
  */
 package tools.refinery.store.tuple;
 
-public sealed interface Tuple permits Tuple0, Tuple1, Tuple2, Tuple3, Tuple4, TupleN {
+import org.jetbrains.annotations.NotNull;
+
+public sealed interface Tuple extends Comparable<Tuple> permits Tuple0, Tuple1, Tuple2, Tuple3, Tuple4, TupleN {
         int getSize();
 
         int get(int element);
 
+        @Override
+        default int compareTo(@NotNull Tuple other) {
+                int size = getSize();
+                int compareSize = Integer.compare(size, other.getSize());
+                if (compareSize != 0) {
+                        return compareSize;
+                }
+                for (int i = 0; i < size; i++) {
+                        int compareElement = Integer.compare(get(i), other.get(i));
+                        if (compareElement != 0) {
+                                return compareElement;
+                        }
+                }
+                return 0;
+        }
+
         static Tuple0 of() {
                 return Tuple0.INSTANCE;
         }
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;
 import static tools.refinery.store.tuple.TupleConstants.TUPLE_BEGIN;
 import static tools.refinery.store.tuple.TupleConstants.TUPLE_END;
 
+/**
+ * Singleton implementation to ensure only a single empty tuple exists.
+ */
+@SuppressWarnings("squid:S6548")
 public final class Tuple0 implements Tuple {
         public static final Tuple0 INSTANCE = new Tuple0();
 
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 @@
  */
 package tools.refinery.store.tuple;
 
+import org.jetbrains.annotations.NotNull;
 import tools.refinery.store.model.TupleHashProvider;
 
 import java.util.Arrays;
@@ -54,11 +55,23 @@ public final class Tuple1 implements Tuple {
                 return 31 + value0;
         }
 
+        @Override
+        public int compareTo(@NotNull Tuple other) {
+                if (other instanceof Tuple1 other1) {
+                        return Integer.compare(value0, other1.value0);
+                }
+                return Tuple.super.compareTo(other);
+        }
+
         /**
          * This class uses safe double-checked locking, see
          * <a href="https://shipilev.net/blog/2014/safe-public-construction/">Safe Publication and Safe Initialization in
          * Java</a> for details.
+         * <p>
+         * This class implements the singleton pattern to ensure only a single cache exists. This is thread-safe because
+         * of the locking of the cache.
          */
+        @SuppressWarnings("squid:S6548")
         public static class Cache {
                 private static final int MIN_CACHE_SIZE = 256;
 
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 @@
  */
 package tools.refinery.store.tuple;
 
+import org.jetbrains.annotations.NotNull;
+
 import static tools.refinery.store.tuple.TupleConstants.*;
 
 public record Tuple2(int value0, int value1) implements Tuple {
@@ -41,4 +43,16 @@ public record Tuple2(int value0, int value1) implements Tuple {
                 hash = 31 * hash + value1;
                 return hash;
         }
+
+        @Override
+        public int compareTo(@NotNull Tuple other) {
+                if (other instanceof Tuple2 other2) {
+                        int compare0 = Integer.compare(value0, other2.value0);
+                        if (compare0 != 0) {
+                                return compare0;
+                        }
+                        return Integer.compare(value1, other2.value1);
+                }
+                return Tuple.super.compareTo(other);
+        }
 }
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 @@
  */
 package tools.refinery.store.tuple;
 
+import org.jetbrains.annotations.NotNull;
+
 import static tools.refinery.store.tuple.TupleConstants.*;
 
 public 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 {
                 hash = 31 * hash + value2;
                 return hash;
         }
+
+        @Override
+        public int compareTo(@NotNull Tuple other) {
+                if (other instanceof Tuple3 other3) {
+                        int compare0 = Integer.compare(value0, other3.value0);
+                        if (compare0 != 0) {
+                                return compare0;
+                        }
+                        int compare1 = Integer.compare(value1, other3.value1);
+                        if (compare1 != 0) {
+                                return compare1;
+                        }
+                        return Integer.compare(value2, other3.value2);
+                }
+                return Tuple.super.compareTo(other);
+        }
 }
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 @@
  */
 package tools.refinery.store.tuple;
 
+import org.jetbrains.annotations.NotNull;
+
 import static tools.refinery.store.tuple.TupleConstants.*;
 
 public 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
                 hash = 31 * hash + value3;
                 return hash;
         }
+
+        @Override
+        public int compareTo(@NotNull Tuple other) {
+                if (other instanceof Tuple4 other4) {
+                        int compare0 = Integer.compare(value0, other4.value0);
+                        if (compare0 != 0) {
+                                return compare0;
+                        }
+                        int compare1 = Integer.compare(value1, other4.value1);
+                        if (compare1 != 0) {
+                                return compare1;
+                        }
+                        int compare2 = Integer.compare(value2, other4.value2);
+                        if (compare2 != 0) {
+                                return compare2;
+                        }
+                        return Integer.compare(value3, other4.value3);
+                }
+                return Tuple.super.compareTo(other);
+        }
 }