feat: base indexer for store

9 files changed, 349 insertions, 9 deletions

diff --git a/subprojects/store/build.gradle.kts b/subprojects/store/build.gradle.kts
index 2c485020..d653f01d 100644
--- a/subprojects/store/build.gradle.kts
+++ b/subprojects/store/build.gradle.kts
@@ -8,3 +8,8 @@ plugins {
         id("tools.refinery.gradle.java-library")
         id("tools.refinery.gradle.jmh")
 }
+
+dependencies {
+        implementation(libs.eclipseCollections)
+        implementation(libs.eclipseCollections.api)
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Cursors.java b/subprojects/store/src/main/java/tools/refinery/store/map/Cursors.java
index 0a94d449..1080a248 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/Cursors.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/Cursors.java
@@ -14,6 +14,10 @@ public final class Cursors {
         return new Empty<>();
     }
 
+        public static <K, V> Cursor<K, V> singleton(K key, V value) {
+                return new Singleton<>(key, value);
+        }
+
     private static class Empty<K, V> implements Cursor<K, V> {
         private boolean terminated = false;
 
@@ -38,4 +42,53 @@ public final class Cursors {
             return false;
         }
     }
+
+        private static class Singleton<K, V> implements Cursor<K, V> {
+                private State state = State.INITIAL;
+                private final K key;
+                private final V value;
+
+                public Singleton(K key, V value) {
+                        this.key = key;
+                        this.value = value;
+                }
+
+                @Override
+                public K getKey() {
+                        if (state == State.STARTED) {
+                                return key;
+                        }
+                        return null;
+                }
+
+                @Override
+                public V getValue() {
+                        if (state == State.STARTED) {
+                                return value;
+                        }
+                        return null;
+                }
+
+                @Override
+                public boolean isTerminated() {
+                        return state == State.TERMINATED;
+                }
+
+                @Override
+                public boolean move() {
+                        if (state == State.INITIAL) {
+                                state = State.STARTED;
+                                return true;
+                        }
+                        state = State.TERMINATED;
+                        return false;
+                }
+
+
+                private enum State {
+                        INITIAL,
+                        STARTED,
+                        TERMINATED
+                }
+        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/AnyInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/AnyInterpretation.java
index f906b48a..d650bd06 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/AnyInterpretation.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/AnyInterpretation.java
@@ -13,4 +13,6 @@ public sealed interface AnyInterpretation permits Interpretation {
         AnySymbol getSymbol();
 
         long getSize();
+
+        int getAdjacentSize(int slot, int node);
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java
index 26ad9a69..ea670cbc 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java
@@ -18,6 +18,8 @@ public non-sealed interface Interpretation<T> extends AnyInterpretation {
 
         Cursor<Tuple, T> getAll();
 
+        Cursor<Tuple, T> getAdjacent(int slot, int node);
+
         T put(Tuple key, T value);
 
         void putAll(Cursor<Tuple, T> cursor);
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/BaseIndexer.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/BaseIndexer.java
new file mode 100644
index 00000000..d9245c1d
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/BaseIndexer.java
@@ -0,0 +1,135 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.model.internal;
+
+import org.eclipse.collections.api.factory.Maps;
+import org.eclipse.collections.api.factory.primitive.IntObjectMaps;
+import org.eclipse.collections.api.map.MutableMap;
+import org.eclipse.collections.api.map.primitive.MutableIntObjectMap;
+import tools.refinery.store.map.AnyVersionedMap;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.Cursors;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+class BaseIndexer<T> {
+        private final MutableIntObjectMap<MutableMap<Tuple, T>>[] maps;
+        private final VersionedMap<Tuple, T> versionedMap;
+
+        public BaseIndexer(int arity, VersionedMap<Tuple, T> map) {
+                if (arity < 2) {
+                        throw new IllegalArgumentException("Only arity >= 2 symbols need to be indexed");
+                }
+                // There is no way in Java to create a generic array in a checked way.
+                @SuppressWarnings({"unchecked", "squid:S1905"})
+                var uncheckedMaps = (MutableIntObjectMap<MutableMap<Tuple, T>>[]) new MutableIntObjectMap[arity];
+                maps = uncheckedMaps;
+                for (int i = 0; i < arity; i++) {
+                        maps[i] = IntObjectMaps.mutable.empty();
+                }
+                this.versionedMap = map;
+                if (map != null) {
+                        var cursor = map.getAll();
+                        while (cursor.move()) {
+                                put(cursor.getKey(), cursor.getValue());
+                        }
+                }
+        }
+
+        public void put(Tuple key, T value) {
+                for (int i = 0; i < maps.length; i++) {
+                        var map = maps[i];
+                        int element = key.get(i);
+                        var adjacentTuples = map.getIfAbsentPut(element, Maps.mutable::empty);
+                        adjacentTuples.put(key, value);
+                }
+        }
+
+        public void remove(Tuple key) {
+                for (int i = 0; i < maps.length; i++) {
+                        var map = maps[i];
+                        int element = key.get(i);
+                        var adjacentTuples = map.get(element);
+                        if (adjacentTuples == null) {
+                                continue;
+                        }
+                        adjacentTuples.remove(key);
+                        if (adjacentTuples.isEmpty()) {
+                                map.remove(element);
+                        }
+                }
+        }
+
+        private MutableMap<Tuple, T> getAdjacentMap(int slot, int node) {
+                if (slot < 0 || slot >= maps.length) {
+                        throw new IllegalArgumentException("Invalid index: " + slot);
+                }
+                var map = maps[slot];
+                return map.get(node);
+        }
+
+        public int getAdjacentSize(int slot, int node) {
+                var adjacentTuples = getAdjacentMap(slot, node);
+                if (adjacentTuples == null) {
+                        return 0;
+                }
+                return adjacentTuples.size();
+        }
+
+        public Cursor<Tuple, T> getAdjacent(int slot, int node) {
+                var adjacentTuples = getAdjacentMap(slot, node);
+                if (adjacentTuples == null) {
+                        return Cursors.empty();
+                }
+                return new IndexCursor<>(adjacentTuples, versionedMap);
+        }
+
+        private static class IndexCursor<T> implements Cursor<Tuple, T> {
+                private final Set<AnyVersionedMap> dependingMaps;
+                private final Iterator<Map.Entry<Tuple, T>> iterator;
+                private Map.Entry<Tuple, T> entry;
+                private boolean terminated;
+
+                public IndexCursor(MutableMap<Tuple, T> adjacentTuples, VersionedMap<Tuple, T> versionedMap) {
+                        dependingMaps = versionedMap == null ? Set.of() : Set.of(versionedMap);
+                        iterator = adjacentTuples.entrySet().iterator();
+                }
+
+                @Override
+                public Tuple getKey() {
+                        return entry.getKey();
+                }
+
+                @Override
+                public T getValue() {
+                        return entry.getValue();
+                }
+
+                @Override
+                public boolean isTerminated() {
+                        return terminated;
+                }
+
+                @Override
+                public boolean move() {
+                        if (!terminated && iterator.hasNext()) {
+                                entry = iterator.next();
+                                return true;
+                        }
+                        terminated = true;
+                        return false;
+                }
+
+                @Override
+                public Set<AnyVersionedMap> getDependingMaps() {
+                        return dependingMaps;
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/IndexedVersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/IndexedVersionedInterpretation.java
new file mode 100644
index 00000000..e0a371de
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/IndexedVersionedInterpretation.java
@@ -0,0 +1,50 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.model.internal;
+
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Objects;
+
+class IndexedVersionedInterpretation<T> extends VersionedInterpretation<T> {
+        private final BaseIndexer<T> indexer;
+
+        public IndexedVersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
+                                                                                  VersionedMap<Tuple, T> map) {
+                super(model, symbol, store, map);
+                indexer = new BaseIndexer<>(symbol.arity(), map);
+        }
+
+        @Override
+        public Cursor<Tuple, T> getAdjacent(int slot, int node) {
+                return indexer.getAdjacent(slot, node);
+        }
+
+        @Override
+        public int getAdjacentSize(int slot, int node) {
+                return indexer.getAdjacentSize(slot, node);
+        }
+
+        @Override
+        protected boolean shouldNotifyRestoreListeners() {
+                // Always call the {@code valueChanged} method to update the index.
+                return true;
+        }
+
+        @Override
+        protected void valueChanged(Tuple key, T fromValue, T toValue, boolean restoring) {
+                if (Objects.equals(toValue, getSymbol().defaultValue())) {
+                        indexer.remove(key);
+                } else {
+                        indexer.put(key, toValue);
+                }
+                super.valueChanged(key, fromValue, toValue, restoring);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/NullaryVersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/NullaryVersionedInterpretation.java
new file mode 100644
index 00000000..96639a8e
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/NullaryVersionedInterpretation.java
@@ -0,0 +1,29 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.model.internal;
+
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+class NullaryVersionedInterpretation<T> extends VersionedInterpretation<T> {
+        public NullaryVersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
+                                                                                  VersionedMap<Tuple, T> map) {
+                super(model, symbol, store, map);
+        }
+
+        @Override
+        public Cursor<Tuple, T> getAdjacent(int slot, int node) {
+                throw new IllegalArgumentException("Invalid index: " + slot);
+        }
+
+        @Override
+        public int getAdjacentSize(int slot, int node) {
+                throw new IllegalArgumentException("Invalid index: " + slot);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/UnaryVersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/UnaryVersionedInterpretation.java
new file mode 100644
index 00000000..4ec04358
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/UnaryVersionedInterpretation.java
@@ -0,0 +1,50 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.model.internal;
+
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.Cursors;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Objects;
+
+class UnaryVersionedInterpretation<T> extends VersionedInterpretation<T> {
+        public UnaryVersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
+                                                                                VersionedMap<Tuple, T> map) {
+                super(model, symbol, store, map);
+        }
+
+        private void validateSlot(int slot) {
+                if (slot != 0) {
+                        throw new IllegalArgumentException("Invalid index: " + slot);
+                }
+        }
+
+        @Override
+        public Cursor<Tuple, T> getAdjacent(int slot, int node) {
+                validateSlot(slot);
+                var key = Tuple.of(node);
+                var value = get(key);
+                if (Objects.equals(value, getSymbol().defaultValue())) {
+                        return Cursors.empty();
+                }
+                return Cursors.singleton(key, value);
+        }
+
+        @Override
+        public int getAdjacentSize(int slot, int node) {
+                validateSlot(slot);
+                var key = Tuple.of(node);
+                var value = get(key);
+                if (Objects.equals(value, getSymbol().defaultValue())) {
+                        return 0;
+                }
+                return 1;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
index 86101ce3..877028cc 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
@@ -21,7 +21,7 @@ import tools.refinery.store.tuple.Tuple;
 import java.util.ArrayList;
 import java.util.List;
 
-public class VersionedInterpretation<T> implements Interpretation<T> {
+public abstract class VersionedInterpretation<T> implements Interpretation<T> {
         private final ModelImpl model;
         private final Symbol<T> symbol;
         private final VersionedMapStore<Tuple, T> store;
@@ -29,8 +29,8 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
         private final List<InterpretationListener<T>> listeners = new ArrayList<>();
         private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>();
 
-        private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
-                                                                        VersionedMap<Tuple, T> map) {
+        protected VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
+                                                                          VersionedMap<Tuple, T> map) {
                 this.model = model;
                 this.symbol = symbol;
                 this.store = store;
@@ -58,6 +58,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                                         .formatted(symbol, symbol.arity()));
                 }
         }
+
         @Override
         public T get(Tuple key) {
                 checkKey(key);
@@ -69,7 +70,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 return map.getAll();
         }
 
-        private void notifyListeners(Tuple key, T fromValue, T toValue, boolean restoring) {
+        protected void valueChanged(Tuple key, T fromValue, T toValue, boolean restoring) {
                 var listenerList = restoring ? restoreListeners : listeners;
                 int listenerCount = listenerList.size();
                 // Use a for loop instead of a for-each loop to avoid <code>Iterator</code> allocation overhead.
@@ -84,7 +85,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 checkKey(key);
                 model.markAsChanged();
                 var oldValue = map.put(key, value);
-                notifyListeners(key, oldValue, value, false);
+                valueChanged(key, oldValue, value, false);
                 return oldValue;
         }
 
@@ -125,11 +126,15 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 return map.commit();
         }
 
+        protected boolean shouldNotifyRestoreListeners() {
+                return !restoreListeners.isEmpty();
+        }
+
         public void restore(long state) {
-                if (!restoreListeners.isEmpty()) {
+                if (shouldNotifyRestoreListeners()) {
                         var diffCursor = getDiffCursor(state);
                         while (diffCursor.move()) {
-                                notifyListeners(diffCursor.getKey(), diffCursor.getFromValue(), diffCursor.getToValue(), true);
+                                valueChanged(diffCursor.getKey(), diffCursor.getFromValue(), diffCursor.getToValue(), true);
                         }
                 }
                 map.restore(state);
@@ -153,7 +158,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 @SuppressWarnings("unchecked")
                 var typedSymbol = (Symbol<T>) symbol;
                 var map = store.createMap();
-                return new VersionedInterpretation<>(model, typedSymbol, store, map);
+                return of(model, typedSymbol, store, map);
         }
 
         static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store,
@@ -161,6 +166,15 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 @SuppressWarnings("unchecked")
                 var typedSymbol = (Symbol<T>) symbol;
                 var map = store.createMap(state);
-                return new VersionedInterpretation<>(model, typedSymbol, store, map);
+                return of(model, typedSymbol, store, map);
+        }
+
+        private static <T> VersionedInterpretation<T> of(ModelImpl model, Symbol<T> typedSymbol,
+                                                                                                         VersionedMapStore<Tuple, T> store, VersionedMap<Tuple, T> map) {
+                return switch (typedSymbol.arity()) {
+                        case 0 -> new NullaryVersionedInterpretation<>(model, typedSymbol, store, map);
+                        case 1 -> new UnaryVersionedInterpretation<>(model, typedSymbol, store, map);
+                        default -> new IndexedVersionedInterpretation<>(model, typedSymbol, store, map);
+                };
         }
 }