Merge remote-tracking branch 'OszkarSemerath/datastructure' into partial-interpretation

70 files changed, 3524 insertions, 931 deletions

diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java
index 25fc91e6..01099eb0 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java
@@ -42,4 +42,9 @@ public sealed interface AnyVersionedMap extends Versioned permits VersionedMap {
         @SuppressWarnings("squid:S1133")
         @Deprecated(since = "0.0.0")
         boolean equals(Object obj);
+
+        /**
+         * Checks the integrity of the map, and throws an exception if an inconsistency is detected.
+         */
+        void checkIntegrity();
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java
index 8e451230..abc044d0 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java
@@ -5,17 +5,17 @@
  */
 package tools.refinery.store.map;
 
-import tools.refinery.store.map.internal.Node;
+import tools.refinery.store.map.internal.state.Node;
 
 /**
  * A class representing an equivalence relation for a type {@code K} with a
  * continuous hash function.
- * 
+ *
  * @author Oszkar Semerath
  *
  * @param <K> Target java type.
  */
-public interface ContinousHashProvider<K> {
+public interface ContinuousHashProvider<K> {
         public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
         public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1;
 
@@ -38,9 +38,9 @@ public interface ContinousHashProvider<K> {
          * {@link #EFFECTIVE_BITS}
          * </ul>
          * Check {@link #equals} for further details.
-         * 
+         *
          * @param key   The target data object.
-         * @param index The depth of the the hash code. Needs to be non-negative.
+         * @param index The depth of the hash code. Needs to be non-negative.
          * @return A hash code.
          */
         public int getHash(K key, int index);
@@ -53,7 +53,7 @@ public interface ContinousHashProvider<K> {
                 if (key1.equals(key2)) {
                         return 0;
                 } else {
-                        for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
+                        for (int i = 0; i < ContinuousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
                                 int hash1 = getEffectiveHash(key1, i);
                                 int hash2 = getEffectiveHash(key2, i);
                                 for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
@@ -68,7 +68,7 @@ public interface ContinousHashProvider<K> {
                         }
                         throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
                                         + ") have the same hashcode over the practical depth limitation ("
-                                        + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
+                                        + ContinuousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
                 }
         }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java
new file mode 100644
index 00000000..29b03edf
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java
@@ -0,0 +1,64 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map;
+
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+public class IteratorAsCursor<K, V> implements Cursor<K, V> {
+        final Iterator<Entry<K, V>> iterator;
+        final VersionedMap<K, V> source;
+
+        private boolean terminated;
+        private K key;
+        private V value;
+
+        public IteratorAsCursor(VersionedMap<K, V> source, Map<K, V> current) {
+                this.iterator = current.entrySet().iterator();
+                this.source = source;
+        }
+
+        @Override
+        public K getKey() {
+                return key;
+        }
+
+        @Override
+        public V getValue() {
+                return value;
+        }
+
+        @Override
+        public boolean isTerminated() {
+                return terminated;
+        }
+
+        @Override
+        public boolean move() {
+                terminated = !iterator.hasNext();
+                if (terminated) {
+                        this.key = null;
+                        this.value = null;
+                } else {
+                        Entry<K, V> next = iterator.next();
+                        this.key = next.getKey();
+                        this.value = next.getValue();
+                }
+                return !terminated;
+        }
+
+        @Override
+        public boolean isDirty() {
+                return false;
+        }
+
+        @Override
+        public Set<AnyVersionedMap> getDependingMaps() {
+                return Set.of(this.source);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Version.java b/subprojects/store/src/main/java/tools/refinery/store/map/Version.java
new file mode 100644
index 00000000..fa2734e4
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/Version.java
@@ -0,0 +1,26 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map;
+
+/**
+ * Interface denoting versions of {@link Versioned}.
+ */
+public interface Version {
+        /**
+         * Hashcode should be updated in accordance with equals.
+         * @return a hashcode of the object.
+         */
+        int hashCode();
+
+        /**
+         * Equivalence of two {@link Version}. This equivalence must satisfy the following constraint (in addition to the
+         * constraints of {@link Object#equals(Object)}: if {@code v1} and {@code v2} are {@link Version}s, and {@code v1
+         * .equals(v2)}, then {@code versioned.restore(v1)} must be {@code equals} to {@code versioned.restore(v2)}.
+         * @param o the other object.
+         * @return weather the two versions are equals.
+         */
+        boolean equals(Object o);
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java b/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java
index 55720db3..da12b0a9 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java
@@ -5,8 +5,20 @@
  */
 package tools.refinery.store.map;
 
+/**
+ * Object that can save and restore its state.
+ */
 public interface Versioned {
-        public long commit();
-        //maybe revert()?
-        public void restore(long state);
+        /**
+         * Saves the state of the object.
+         * @return an object that marks the version of the object at the time the function was called.
+         */
+        Version commit();
+
+        /**
+         * Restores the state of the object.
+         * @param state a {@link Version} object that marks the version. The state must be a {@link Version} object
+         *                 returned by a previous {@link #commit()}!
+         */
+        void restore(Version state);
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java
index 9bbde24d..28194b58 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java
@@ -6,6 +6,8 @@
 package tools.refinery.store.map;
 
 public non-sealed interface VersionedMap<K, V> extends AnyVersionedMap {
+        V getDefaultValue();
+
         V get(K key);
 
         Cursor<K, V> getAll();
@@ -14,5 +16,5 @@ public non-sealed interface VersionedMap<K, V> extends AnyVersionedMap {
 
         void putAll(Cursor<K, V> cursor);
 
-        DiffCursor<K, V> getDiffCursor(long state);
+        DiffCursor<K, V> getDiffCursor(Version state);
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java
index 5aafa338..55cf08a5 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java
@@ -5,15 +5,17 @@
  */
 package tools.refinery.store.map;
 
-import java.util.Set;
+import tools.refinery.store.map.internal.VersionedMapStoreFactoryBuilderImpl;
 
 public interface VersionedMapStore<K, V> {
-        
-        public VersionedMap<K, V> createMap();
 
-        public VersionedMap<K, V> createMap(long state);
-        
-        public Set<Long> getStates();
+        VersionedMap<K, V> createMap();
 
-        public DiffCursor<K,V> getDiffCursor(long fromState, long toState);
-}
\ No newline at end of file
+        VersionedMap<K, V> createMap(Version state);
+
+        DiffCursor<K,V> getDiffCursor(Version fromState, Version toState);
+
+        static <K,V> VersionedMapStoreFactoryBuilder<K,V> builder() {
+                return new VersionedMapStoreFactoryBuilderImpl<>();
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactory.java
new file mode 100644
index 00000000..baf6ab50
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactory.java
@@ -0,0 +1,24 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map;
+
+import java.util.List;
+
+public interface VersionedMapStoreFactory<K,V> {
+        /**
+         * Constructs a new instance of {@link VersionedMap}.
+         * @return The new instance.
+         */
+        VersionedMapStore<K,V> createOne();
+
+        /**
+         * Constructs a group of {@link VersionedMap}s with the same configuration. If possible, the stores share
+         * resources with each other.
+         * @param amount The amount of new instances to be created.
+         * @return A list of new stores with the given number of elements.
+         */
+        List<VersionedMapStore<K, V>> createGroup(int amount);
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java
new file mode 100644
index 00000000..0ac196f2
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java
@@ -0,0 +1,30 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map;
+
+public interface VersionedMapStoreFactoryBuilder<K,V> {
+        enum StoreStrategy {
+                STATE, DELTA
+        }
+
+        enum DeltaTransactionStrategy {
+                LIST, SET
+        }
+
+        enum SharingStrategy {
+                NO_NODE_CACHE, SHARED_NODE_CACHE, SHARED_NODE_CACHE_IN_GROUP
+        }
+
+        VersionedMapStoreFactoryBuilder<K,V> defaultValue(V defaultValue);
+        VersionedMapStoreFactoryBuilder<K,V> strategy(StoreStrategy strategy);
+        VersionedMapStoreFactoryBuilder<K,V> versionFreeing(boolean enabled);
+        VersionedMapStoreFactoryBuilder<K,V> stateBasedImmutableWhenCommitting(boolean transformToImmutable);
+        VersionedMapStoreFactoryBuilder<K,V> stateBasedSharingStrategy(SharingStrategy sharingStrategy);
+        VersionedMapStoreFactoryBuilder<K,V> stateBasedHashProvider(ContinuousHashProvider<K> hashProvider);
+        VersionedMapStoreFactoryBuilder<K,V> deltaTransactionStrategy(DeltaTransactionStrategy deltaStrategy);
+
+        VersionedMapStoreFactory<K,V> build();
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
deleted file mode 100644
index aade4aeb..00000000
--- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
+++ /dev/null
@@ -1,132 +0,0 @@
-/*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
- *
- * SPDX-License-Identifier: EPL-2.0
- */
-package tools.refinery.store.map;
-
-import tools.refinery.store.map.internal.ImmutableNode;
-import tools.refinery.store.map.internal.MapDiffCursor;
-import tools.refinery.store.map.internal.Node;
-import tools.refinery.store.map.internal.VersionedMapImpl;
-
-import java.util.*;
-
-public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
-        // Configuration
-        private final boolean immutableWhenCommitting;
-
-        // Static data
-        protected final ContinousHashProvider<K> hashProvider;
-        protected final V defaultValue;
-
-        // Dynamic data
-        protected final Map<Long, ImmutableNode<K, V>> states = new HashMap<>();
-        protected final Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
-        protected long nextID = 0;
-
-        public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
-                        VersionedMapStoreConfiguration config) {
-                this.immutableWhenCommitting = config.isImmutableWhenCommitting();
-                this.hashProvider = hashProvider;
-                this.defaultValue = defaultValue;
-                if (config.isSharedNodeCacheInStore()) {
-                        nodeCache = new HashMap<>();
-                } else {
-                        nodeCache = null;
-                }
-        }
-
-        private VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
-                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache, VersionedMapStoreConfiguration config) {
-                this.immutableWhenCommitting = config.isImmutableWhenCommitting();
-                this.hashProvider = hashProvider;
-                this.defaultValue = defaultValue;
-                this.nodeCache = nodeCache;
-        }
-
-        public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue) {
-                this(hashProvider, defaultValue, new VersionedMapStoreConfiguration());
-        }
-
-        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
-                        ContinousHashProvider<K> hashProvider, V defaultValue,
-                        VersionedMapStoreConfiguration config) {
-                List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
-                if (config.isSharedNodeCacheInStoreGroups()) {
-                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
-                        if (config.isSharedNodeCacheInStore()) {
-                                nodeCache = new HashMap<>();
-                        } else {
-                                nodeCache = null;
-                        }
-                        for (int i = 0; i < amount; i++) {
-                                result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config));
-                        }
-                } else {
-                        for (int i = 0; i < amount; i++) {
-                                result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config));
-                        }
-                }
-                return result;
-        }
-
-        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
-                        ContinousHashProvider<K> hashProvider, V defaultValue) {
-                return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration());
-        }
-
-        @Override
-        public synchronized Set<Long> getStates() {
-                return new HashSet<>(states.keySet());
-        }
-
-        @Override
-        public VersionedMap<K, V> createMap() {
-                return new VersionedMapImpl<>(this, hashProvider, defaultValue);
-        }
-
-        @Override
-        public VersionedMap<K, V> createMap(long state) {
-                ImmutableNode<K, V> data = revert(state);
-                return new VersionedMapImpl<>(this, hashProvider, defaultValue, data);
-        }
-
-        public synchronized ImmutableNode<K, V> revert(long state) {
-                if (states.containsKey(state)) {
-                        return states.get(state);
-                } else {
-                        ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
-                        Collections.sort(existingKeys);
-                        throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: "
-                                        + Arrays.toString(existingKeys.toArray()));
-                }
-        }
-
-        public synchronized long commit(Node<K, V> data, VersionedMapImpl<K, V> mapToUpdateRoot) {
-                ImmutableNode<K, V> immutable;
-                if (data != null) {
-                        immutable = data.toImmutable(this.nodeCache);
-                } else {
-                        immutable = null;
-                }
-
-                if (nextID == Long.MAX_VALUE)
-                        throw new IllegalStateException("Map store run out of Id-s");
-                long id = nextID++;
-                this.states.put(id, immutable);
-                if (this.immutableWhenCommitting) {
-                        mapToUpdateRoot.setRoot(immutable);
-                }
-                return id;
-        }
-
-        @Override
-        public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
-                VersionedMap<K, V> map1 = createMap(fromState);
-                VersionedMap<K, V> map2 = createMap(toState);
-                Cursor<K, V> cursor1 = map1.getAll();
-                Cursor<K, V> cursor2 = map2.getAll();
-                return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2);
-        }
-}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java
deleted file mode 100644
index 61b3d1b8..00000000
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java
+++ /dev/null
@@ -1,23 +0,0 @@
-/*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
- *
- * SPDX-License-Identifier: EPL-2.0
- */
-package tools.refinery.store.map.internal;
-
-enum HashClash {
-        /**
-         * Not stuck.
-         */
-        NONE,
-        
-        /**
-         * Clashed, next we should return the key of cursor 1.
-         */
-        STUCK_CURSOR_1,
-        
-        /**
-         * Clashed, next we should return the key of cursor 2.
-         */
-        STUCK_CURSOR_2
-}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
deleted file mode 100644
index d31f1a05..00000000
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
+++ /dev/null
@@ -1,229 +0,0 @@
-/*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
- *
- * SPDX-License-Identifier: EPL-2.0
- */
-package tools.refinery.store.map.internal;
-
-import tools.refinery.store.map.AnyVersionedMap;
-import tools.refinery.store.map.ContinousHashProvider;
-import tools.refinery.store.map.Cursor;
-import tools.refinery.store.map.DiffCursor;
-
-import java.util.Set;
-import java.util.stream.Collectors;
-import java.util.stream.Stream;
-
-/**
- * A cursor representing the difference between two states of a map.
- *
- * @author Oszkar Semerath
- *
- */
-public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
-        /**
-         * Default nodeId representing missing elements.
-         */
-        private final V defaultValue;
-        private final MapCursor<K, V> cursor1;
-        private final MapCursor<K, V> cursor2;
-        private final ContinousHashProvider<? super K> hashProvider;
-
-        // Values
-        private K key;
-        private V fromValue;
-        private V toValue;
-
-        // State
-        /**
-         * Positive number if cursor 1 is behind, negative number if cursor 2 is behind,
-         * and 0 if they are at the same position.
-         */
-        private int cursorRelation;
-        private HashClash hashClash = HashClash.NONE;
-
-        public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1,
-                        Cursor<K, V> cursor2) {
-                super();
-                this.hashProvider = hashProvider;
-                this.defaultValue = defaultValue;
-                this.cursor1 = (MapCursor<K, V>) cursor1;
-                this.cursor2 = (MapCursor<K, V>) cursor2;
-        }
-
-        @Override
-        public K getKey() {
-                return key;
-        }
-
-        @Override
-        public V getFromValue() {
-                return fromValue;
-        }
-
-        @Override
-        public V getToValue() {
-                return toValue;
-        }
-
-        @Override
-        public V getValue() {
-                return getToValue();
-        }
-
-        public boolean isTerminated() {
-                return cursor1.isTerminated() && cursor2.isTerminated();
-        }
-
-        @Override
-        public boolean isDirty() {
-                return this.cursor1.isDirty() || this.cursor2.isDirty();
-        }
-
-        @Override
-        public Set<AnyVersionedMap> getDependingMaps() {
-                return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream())
-                                .map(AnyVersionedMap.class::cast)
-                                .collect(Collectors.toUnmodifiableSet());
-        }
-
-        protected void updateState() {
-                if (!isTerminated()) {
-                        this.cursorRelation = MapCursor.compare(cursor1, cursor2);
-                        if (cursorRelation > 0 || cursor2.isTerminated()) {
-                                this.key = cursor1.getKey();
-                                this.fromValue = cursor1.getValue();
-                                this.toValue = defaultValue;
-                        } else if (cursorRelation < 0 || cursor1.isTerminated()) {
-                                this.key = cursor2.getKey();
-                                this.fromValue = defaultValue;
-                                this.toValue = cursor1.getValue();
-                        } else {
-                                // cursor1 = cursor2
-                                if (cursor1.getKey().equals(cursor2.getKey())) {
-                                        this.key = cursor1.getKey();
-                                        this.fromValue = cursor1.getValue();
-                                        this.toValue = defaultValue;
-                                } else {
-                                        resolveHashClashWithFirstEntry();
-                                }
-                        }
-                }
-        }
-
-        protected void resolveHashClashWithFirstEntry() {
-                int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key);
-                if (compareResult < 0) {
-                        this.hashClash = HashClash.STUCK_CURSOR_2;
-                        this.cursorRelation = 0;
-                        this.key = cursor1.key;
-                        this.fromValue = cursor1.value;
-                        this.toValue = defaultValue;
-                } else if (compareResult > 0) {
-                        this.hashClash = HashClash.STUCK_CURSOR_1;
-                        this.cursorRelation = 0;
-                        this.key = cursor2.key;
-                        this.fromValue = defaultValue;
-                        this.toValue = cursor2.value;
-                } else {
-                        throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
-                }
-        }
-
-        protected boolean isInHashClash() {
-                return this.hashClash != HashClash.NONE;
-        }
-
-        protected void resolveHashClashWithSecondEntry() {
-                switch (this.hashClash) {
-                case STUCK_CURSOR_1:
-                        this.hashClash = HashClash.NONE;
-                        this.cursorRelation = 0;
-                        this.key = cursor1.key;
-                        this.fromValue = cursor1.value;
-                        this.toValue = defaultValue;
-                        break;
-                case STUCK_CURSOR_2:
-                        this.hashClash = HashClash.NONE;
-                        this.cursorRelation = 0;
-                        this.key = cursor2.key;
-                        this.fromValue = defaultValue;
-                        this.toValue = cursor2.value;
-                        break;
-                default:
-                        throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
-                }
-        }
-
-        protected boolean sameValues() {
-                if (this.fromValue == null) {
-                        return this.toValue == null;
-                } else {
-                        return this.fromValue.equals(this.toValue);
-                }
-        }
-
-        protected boolean moveOne() {
-                if (isTerminated()) {
-                        return false;
-                }
-                if (this.cursorRelation > 0 || cursor2.isTerminated()) {
-                        return cursor1.move();
-                } else if (this.cursorRelation < 0 || cursor1.isTerminated()) {
-                        return cursor2.move();
-                } else {
-                        boolean moved1 = cursor1.move();
-                        boolean moved2 = cursor2.move();
-                        return moved1 && moved2;
-                }
-        }
-
-        private boolean skipNode() {
-                if (isTerminated()) {
-                        throw new IllegalStateException("DiffCursor tries to skip when terminated!");
-                }
-                boolean update1 = cursor1.skipCurrentNode();
-                boolean update2 = cursor2.skipCurrentNode();
-                updateState();
-                return update1 && update2;
-        }
-
-        protected boolean moveToConsistentState() {
-                if (!isTerminated()) {
-                        boolean changed;
-                        boolean lastResult = true;
-                        do {
-                                changed = false;
-                                if (MapCursor.sameSubnode(cursor1, cursor2)) {
-                                        lastResult = skipNode();
-                                        changed = true;
-                                }
-                                if (sameValues()) {
-                                        lastResult = moveOne();
-                                        changed = true;
-                                }
-                                updateState();
-                        } while (changed && !isTerminated());
-                        return lastResult;
-                } else {
-                        return false;
-                }
-        }
-
-        public boolean move() {
-                if (!isTerminated()) {
-                        if (isInHashClash()) {
-                                this.resolveHashClashWithSecondEntry();
-                                return true;
-                        } else {
-                                if (moveOne()) {
-                                        return moveToConsistentState();
-                                } else {
-                                        return false;
-                                }
-                        }
-
-                } else
-                        return false;
-        }
-}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
deleted file mode 100644
index 958d645f..00000000
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
+++ /dev/null
@@ -1,90 +0,0 @@
-/*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
- *
- * SPDX-License-Identifier: EPL-2.0
- */
-package tools.refinery.store.map.internal;
-
-import java.util.Map;
-
-import tools.refinery.store.map.ContinousHashProvider;
-
-public abstract class Node<K,V>{
-        public static final int BRANCHING_FACTOR_BITS = 5;
-        public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
-        protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
-        protected static final int FACTOR_MASK = FACTOR-1;
-        public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
-
-        /**
-         * Calculates the index for the continuous hash.
-         * @param depth The depth of the node in the tree.
-         * @return The index of the continuous hash.
-         */
-        protected static int hashDepth(int depth) {
-                return depth/NUMBER_OF_FACTORS;
-        }
-
-        /**
-         * Calculates the which segment of a single hash should be used.
-         * @param depth The depth of the node in the tree.
-         * @return The segment of a hash code.
-         */
-        protected static int shiftDepth(int depth) {
-                return depth%NUMBER_OF_FACTORS;
-        }
-        /**
-         * Selects a segments from a complete hash for a given depth.
-         * @param hash A complete hash.
-         * @param shiftDepth The index of the segment.
-         * @return The segment as an integer.
-         */
-        protected static int hashFragment(int hash, int shiftDepth) {
-                if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
-                return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK;
-        }
-
-        /**
-         * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1.
-         * @param key The key.
-         * @param hash Hash code for depth-1
-         * @param depth The depth.
-         * @return The new hash code.
-         */
-        protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) {
-                final int hashDepth = hashDepth(depth);
-                if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) {
-                        throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!");
-                }
-                return depth%NUMBER_OF_FACTORS == 0?
-                                hashProvider.getHash(key, hashDepth) :
-                                hash;
-        }
-
-
-        public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue,  int hash, int depth);
-        public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
-        public abstract long getSize();
-
-        abstract MutableNode<K, V> toMutable();
-        public abstract ImmutableNode<K, V> toImmutable(
-                        Map<Node<K, V>,ImmutableNode<K, V>> cache);
-        protected abstract MutableNode<K, V> isMutable();
-        /**
-         * Moves a {@link MapCursor} to its next position.
-         * @param cursor the cursor
-         * @return Whether there was a next nodeId to move on.
-         */
-        abstract boolean moveToNext(MapCursor<K,V> cursor);
-
-        ///////// FOR printing
-        public abstract void prettyPrint(StringBuilder builder, int depth, int code);
-        @Override
-        public String toString() {
-                StringBuilder stringBuilder = new StringBuilder();
-                prettyPrint(stringBuilder, 0, -1);
-                return stringBuilder.toString();
-        }
-        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
-
-}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java
new file mode 100644
index 00000000..9f419ce1
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java
@@ -0,0 +1,150 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal;
+
+import tools.refinery.store.map.ContinuousHashProvider;
+import tools.refinery.store.map.VersionedMapStoreFactory;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
+import tools.refinery.store.map.internal.delta.DeltaBasedVersionedMapStoreFactory;
+import tools.refinery.store.map.internal.state.StateBasedVersionedMapStoreFactory;
+
+public class VersionedMapStoreFactoryBuilderImpl<K, V> implements VersionedMapStoreFactoryBuilder<K, V> {
+
+        private boolean defaultSet = false;
+        private V defaultValue;
+        private StoreStrategy strategy = null;
+        private Boolean transformToImmutable = null;
+        private SharingStrategy sharingStrategy = null;
+        private Boolean enableVersionFreeing = null;
+        private ContinuousHashProvider<K> continuousHashProvider = null;
+        private DeltaTransactionStrategy deltaTransactionStrategy = null;
+
+        private StoreStrategy checkStrategy() {
+                StoreStrategy currentStrategy = strategy;
+                currentStrategy = mergeStrategies(currentStrategy, transformToImmutable, StoreStrategy.STATE);
+                currentStrategy = mergeStrategies(currentStrategy, sharingStrategy, StoreStrategy.STATE);
+                currentStrategy = mergeStrategies(currentStrategy, continuousHashProvider, StoreStrategy.STATE);
+                currentStrategy = mergeStrategies(currentStrategy, deltaTransactionStrategy, StoreStrategy.DELTA);
+                return currentStrategy;
+        }
+
+        private StoreStrategy mergeStrategies(StoreStrategy old, StoreStrategy newStrategy) {
+                if (old != null && newStrategy != null && old != newStrategy) {
+                        throw new IllegalArgumentException("Mixed strategy parametrization in VersionedMap builder!");
+                }
+
+                if (old != null) {
+                        return old;
+                } else {
+                        return newStrategy;
+                }
+        }
+
+        private StoreStrategy mergeStrategies(StoreStrategy old, Object parameter, StoreStrategy newStrategy) {
+                if (parameter != null) {
+                        return mergeStrategies(old, newStrategy);
+                } else {
+                        return old;
+                }
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> defaultValue(V defaultValue) {
+                this.defaultSet = true;
+                this.defaultValue = defaultValue;
+                return this;
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> strategy(StoreStrategy strategy) {
+                this.strategy = strategy;
+                checkStrategy();
+                return this;
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> versionFreeing(boolean enabled) {
+                this.enableVersionFreeing = enabled;
+                checkStrategy();
+                return this;
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> stateBasedImmutableWhenCommitting(boolean transformToImmutable) {
+                this.transformToImmutable = transformToImmutable;
+                checkStrategy();
+                return this;
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> stateBasedSharingStrategy(SharingStrategy sharingStrategy) {
+                this.sharingStrategy = sharingStrategy;
+                checkStrategy();
+                return this;
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> stateBasedHashProvider(ContinuousHashProvider<K> hashProvider) {
+                this.continuousHashProvider = hashProvider;
+                checkStrategy();
+                return this;
+        }
+
+        @Override
+        public VersionedMapStoreFactoryBuilder<K, V> deltaTransactionStrategy(DeltaTransactionStrategy deltaTransactionStrategy) {
+                this.deltaTransactionStrategy = deltaTransactionStrategy;
+                checkStrategy();
+                return this;
+        }
+
+        private <T> T getOrDefault(T value, T defaultValue) {
+                if(value != null) {
+                        return value;
+                } else {
+                        return defaultValue;
+                }
+        }
+
+        @Override
+        public VersionedMapStoreFactory<K, V> build() {
+                if (!defaultSet) {
+                        throw new IllegalArgumentException("Default value is missing!");
+                }
+                var strategyToUse = checkStrategy();
+                if (strategyToUse == null) {
+                        return new DeltaBasedVersionedMapStoreFactory<>(defaultValue,
+                                        getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST));
+                }
+                return switch (strategyToUse) {
+                        case STATE -> {
+                                if(continuousHashProvider == null) {
+                                        throw new IllegalArgumentException("Continuous hash provider is missing!");
+                                }
+                                yield new StateBasedVersionedMapStoreFactory<>(defaultValue,
+                                                getOrDefault(transformToImmutable,true),
+                                                getOrDefault(sharingStrategy, SharingStrategy.SHARED_NODE_CACHE_IN_GROUP),
+                                                getOrDefault(enableVersionFreeing, true),
+                                                continuousHashProvider);
+                        }
+                        case DELTA -> new DeltaBasedVersionedMapStoreFactory<>(defaultValue,
+                                        getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST));
+                };
+        }
+
+        @Override
+        public String toString() {
+                return "VersionedMapStoreFactoryBuilderImpl{" +
+                                "defaultSet=" + defaultSet +
+                                ", defaultValue=" + defaultValue +
+                                ", strategy=" + strategy +
+                                ", transformToImmutable=" + transformToImmutable +
+                                ", sharingStrategy=" + sharingStrategy +
+                                ", enableVersionFreeing=" + enableVersionFreeing +
+                                ", continuousHashProvider=" + continuousHashProvider +
+                                ", deltaTransactionStrategy=" + deltaTransactionStrategy +
+                                '}';
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java
new file mode 100644
index 00000000..cedcdc0b
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java
@@ -0,0 +1,38 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreFactory;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class DeltaBasedVersionedMapStoreFactory<K, V> implements VersionedMapStoreFactory<K, V> {
+        private final V defaultValue;
+        private final boolean summarizeChanges;
+
+        public DeltaBasedVersionedMapStoreFactory(V defaultValue,
+                                                                                          VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy deltaTransactionStrategy) {
+                this.defaultValue = defaultValue;
+                this.summarizeChanges = deltaTransactionStrategy == VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET;
+        }
+
+        @Override
+        public VersionedMapStore<K, V> createOne() {
+                return new VersionedMapStoreDeltaImpl<>(summarizeChanges, defaultValue);
+        }
+
+        @Override
+        public List<VersionedMapStore<K, V>> createGroup(int amount) {
+                List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
+                for(int i=0; i<amount; i++) {
+                        result.add(new VersionedMapStoreDeltaImpl<>(summarizeChanges,defaultValue));
+                }
+                return result;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java
new file mode 100644
index 00000000..ce10b246
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java
@@ -0,0 +1,147 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import tools.refinery.store.map.AnyVersionedMap;
+import tools.refinery.store.map.DiffCursor;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+
+public class DeltaDiffCursor<K, V> implements DiffCursor<K, V> {
+        final List<MapDelta<K, V>[]> backwardTransactions;
+        final List<MapDelta<K, V>[]> forwardTransactions;
+
+        boolean started;
+        /**
+         * Denotes the direction of traversal. False means backwards, true means
+         * forward.
+         */
+        boolean direction;
+        int listIndex;
+        int arrayIndex;
+
+        public DeltaDiffCursor(List<MapDelta<K, V>[]> backwardTransactions, List<MapDelta<K, V>[]> forwardTransactions) {
+                this.backwardTransactions = backwardTransactions;
+                this.forwardTransactions = forwardTransactions;
+
+                if (!backwardTransactions.isEmpty()) {
+                        direction = false;
+                        listIndex = 0;
+                        arrayIndex = backwardTransactions.get(listIndex).length - 1;
+                } else if (!forwardTransactions.isEmpty()) {
+                        direction = true;
+                        listIndex = forwardTransactions.size() - 1;
+                        arrayIndex = 0;
+                } else {
+                        direction = true;
+                        listIndex = -1;
+                }
+                started = false;
+        }
+
+        protected MapDelta<K, V> getCurrentDelta() {
+                final List<MapDelta<K, V>[]> list;
+                if (!direction) {
+                        list = this.backwardTransactions;
+                } else {
+                        list = this.forwardTransactions;
+                }
+                return list.get(listIndex)[arrayIndex];
+        }
+
+        @Override
+        public K getKey() {
+                return getCurrentDelta().getKey();
+        }
+
+        @Override
+        public V getValue() {
+                return getToValue();
+        }
+
+        @Override
+        public boolean isTerminated() {
+                return this.direction && listIndex == -1;
+        }
+
+
+        @Override
+        public boolean move() {
+                if(!started) {
+                        started = true;
+                        return !isTerminated();
+                } else if (isTerminated()) {
+                        return false;
+                } else {
+                        if (this.direction) {
+                                if (arrayIndex+1 < forwardTransactions.get(listIndex).length) {
+                                        arrayIndex++;
+                                        return true;
+                                } else {
+                                        if (listIndex-1 >= 0) {
+                                                listIndex--;
+                                                arrayIndex = 0;
+                                                return true;
+                                        } else {
+                                                listIndex = -1;
+                                                return false;
+                                        }
+                                }
+                        } else {
+                                if (arrayIndex > 0) {
+                                        arrayIndex--;
+                                        return true;
+                                } else {
+                                        if (listIndex+1 < backwardTransactions.size()) {
+                                                listIndex++;
+                                                this.arrayIndex = backwardTransactions.get(listIndex).length - 1;
+                                                return true;
+                                        } else {
+                                                this.direction = true;
+                                                if (!this.forwardTransactions.isEmpty()) {
+                                                        listIndex = forwardTransactions.size() - 1;
+                                                        arrayIndex = 0;
+                                                        return true;
+                                                } else {
+                                                        listIndex = -1;
+                                                        return false;
+                                                }
+                                        }
+                                }
+                        }
+                }
+        }
+
+        @Override
+        public boolean isDirty() {
+                return false;
+        }
+
+        @Override
+        public Set<AnyVersionedMap> getDependingMaps() {
+                return Collections.emptySet();
+        }
+
+        @Override
+        public V getFromValue() {
+                if(this.direction) {
+                        return getCurrentDelta().getOldValue();
+                } else {
+                        return getCurrentDelta().getNewValue();
+                }
+        }
+
+        @Override
+        public V getToValue() {
+                if(this.direction) {
+                        return getCurrentDelta().getNewValue();
+                } else {
+                        return getCurrentDelta().getOldValue();
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java
new file mode 100644
index 00000000..0c0cc906
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java
@@ -0,0 +1,20 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+public record MapDelta<K, V>(K key, V oldValue, V newValue) {
+        public K getKey() {
+                return key;
+        }
+
+        public V getOldValue() {
+                return oldValue;
+        }
+
+        public V getNewValue() {
+                return newValue;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java
new file mode 100644
index 00000000..6f3fa6d7
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java
@@ -0,0 +1,41 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import tools.refinery.store.map.Version;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+public record MapTransaction<K, V>(MapDelta<K, V>[] deltas, MapTransaction<K, V> parent, int depth) implements Version {
+
+        @Override
+        public int hashCode() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + Arrays.hashCode(deltas);
+                result = prime * result + Objects.hash(parent, depth);
+                return result;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (getClass() != obj.getClass())
+                        return false;
+                @SuppressWarnings("unchecked")
+                MapTransaction<K, V> other = (MapTransaction<K, V>) obj;
+                return depth == other.depth && Objects.equals(parent, other.parent) && Arrays.equals(deltas, other.deltas);
+        }
+
+        @Override
+        public String toString() {
+                return "MapTransaction " + depth + " " + Arrays.toString(deltas);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java
new file mode 100644
index 00000000..1f6a9000
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java
@@ -0,0 +1,36 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class UncommittedDeltaArrayStore<K, V> implements UncommittedDeltaStore<K, V> {
+        final List<MapDelta<K, V>> uncommittedOldValues = new ArrayList<>();
+
+        @Override
+        public void processChange(K key, V oldValue, V newValue) {
+                uncommittedOldValues.add(new MapDelta<>(key, oldValue, newValue));
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractDeltas() {
+                if (uncommittedOldValues.isEmpty()) {
+                        return null;
+                } else {
+                        @SuppressWarnings("unchecked")
+                        MapDelta<K, V>[] result = uncommittedOldValues.toArray(new MapDelta[0]);
+                        return result;
+                }
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractAndDeleteDeltas() {
+                MapDelta<K, V>[] res = extractDeltas();
+                this.uncommittedOldValues.clear();
+                return res;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java
new file mode 100644
index 00000000..644884a6
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java
@@ -0,0 +1,53 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import java.util.*;
+import java.util.Map.Entry;
+
+import tools.refinery.store.map.VersionedMap;
+
+public class UncommittedDeltaMapStore<K, V> implements UncommittedDeltaStore<K, V> {
+        final VersionedMap<K, V> source;
+        final Map<K, V> uncommittedOldValues = new HashMap<>();
+
+        public UncommittedDeltaMapStore(VersionedMap<K, V> source) {
+                this.source = source;
+        }
+
+        @Override
+        public void processChange(K key, V oldValue, V newValue) {
+                if(!uncommittedOldValues.containsKey(key)) {
+                        this.uncommittedOldValues.put(key,oldValue);
+                }
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractDeltas() {
+                if (uncommittedOldValues.isEmpty()) {
+                        return null;
+                } else {
+                        @SuppressWarnings("unchecked")
+                        MapDelta<K,V>[] deltas = new MapDelta[uncommittedOldValues.size()];
+                        int i = 0;
+                        for (Entry<K, V> entry : uncommittedOldValues.entrySet()) {
+                                final K key = entry.getKey();
+                                final V oldValue = entry.getValue();
+                                final V newValue = source.get(key);
+                                deltas[i++] = new MapDelta<>(key, oldValue, newValue);
+                        }
+
+                        return deltas;
+                }
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractAndDeleteDeltas() {
+                MapDelta<K, V>[] res = extractDeltas();
+                this.uncommittedOldValues.clear();
+                return res;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java
new file mode 100644
index 00000000..ecd33c5f
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java
@@ -0,0 +1,29 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+public interface UncommittedDeltaStore<K, V> {
+        void processChange(K key, V oldValue, V newValue);
+
+        MapDelta<K, V>[] extractDeltas();
+
+        MapDelta<K, V>[] extractAndDeleteDeltas();
+
+        default void checkIntegrity() {
+                MapDelta<K, V>[] extractedDeltas = extractDeltas();
+                if(extractedDeltas != null) {
+                        for(var uncommittedOldValue : extractedDeltas) {
+                                if(uncommittedOldValue == null) {
+                                        throw new IllegalArgumentException("Null entry in deltas!");
+                                }
+                                if(uncommittedOldValue.getKey() == null) {
+                                        throw new IllegalStateException("Null key in deltas!");
+                                }
+                        }
+                }
+        }
+
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java
new file mode 100644
index 00000000..d530ae87
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java
@@ -0,0 +1,237 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import tools.refinery.store.map.*;
+
+import java.util.*;
+
+public class VersionedMapDeltaImpl<K, V> implements VersionedMap<K, V> {
+        protected final VersionedMapStoreDeltaImpl<K, V> store;
+
+        final Map<K, V> current;
+
+        final UncommittedDeltaStore<K, V> uncommittedStore;
+        MapTransaction<K, V> previous;
+
+        protected final V defaultValue;
+
+        public VersionedMapDeltaImpl(VersionedMapStoreDeltaImpl<K, V> store, boolean summarizeChanges, V defaultValue) {
+                this.store = store;
+                this.defaultValue = defaultValue;
+
+                current = new HashMap<>();
+                if (summarizeChanges) {
+                        this.uncommittedStore = new UncommittedDeltaMapStore<>(this);
+                } else {
+                        this.uncommittedStore = new UncommittedDeltaArrayStore<>();
+                }
+        }
+
+        @Override
+        public V getDefaultValue() {
+                return defaultValue;
+        }
+
+        @Override
+        public Version commit() {
+                MapDelta<K, V>[] deltas = uncommittedStore.extractAndDeleteDeltas();
+                final MapTransaction<K,V> committedTransaction = this.store.appendTransaction(deltas, previous);
+                this.previous = committedTransaction;
+                return committedTransaction;
+        }
+
+        @Override
+        public void restore(Version state) {
+                // 1. restore uncommitted states
+                MapDelta<K, V>[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas();
+                if (uncommitted != null) {
+                        backward(uncommitted);
+                }
+
+                // 2. get common ancestor
+                final MapTransaction<K,V> parent;
+                List<MapDelta<K, V>[]> forward = new ArrayList<>();
+                if (this.previous == null) {
+                        parent = this.store.getPath(state, forward);
+                        this.forward(forward);
+                } else {
+                        List<MapDelta<K, V>[]> backward = new ArrayList<>();
+                        parent = this.store.getPath(this.previous, state, backward, forward);
+                        this.backward(backward);
+                        this.forward(forward);
+                }
+                this.previous = parent;
+        }
+
+        protected void forward(List<MapDelta<K, V>[]> changes) {
+                for (int i = changes.size() - 1; i >= 0; i--) {
+                        forward(changes.get(i));
+                }
+        }
+
+        protected void backward(List<MapDelta<K, V>[]> changes) {
+                //Currently, this loop statement is faster.
+                //noinspection ForLoopReplaceableByForEach
+                for (int i = 0; i < changes.size(); i++) {
+                        backward(changes.get(i));
+                }
+        }
+
+        protected void forward(MapDelta<K, V>[] changes) {
+                //Currently, this loop statement is faster.
+                //noinspection ForLoopReplaceableByForEach
+                for (int i = 0; i < changes.length; i++) {
+                        final MapDelta<K, V> change = changes[i];
+                        K key = change.getKey();
+                        V newValue = change.getNewValue();
+
+                        if(newValue == defaultValue) {
+                                current.remove(key);
+                        } else {
+                                current.put(key,newValue);
+                        }
+                }
+        }
+
+        protected void backward(MapDelta<K, V>[] changes) {
+                for (int i = changes.length - 1; i >= 0; i--) {
+                        final MapDelta<K, V> change = changes[i];
+                        K key = change.getKey();
+                        V oldValue = change.oldValue();
+
+                        if(oldValue == defaultValue) {
+                                current.remove(key);
+                        } else {
+                                current.put(key,oldValue);
+                        }
+                }
+        }
+
+        @Override
+        public V get(K key) {
+                return current.getOrDefault(key, defaultValue);
+        }
+
+        @Override
+        public Cursor<K, V> getAll() {
+                return new IteratorAsCursor<>(this, current);
+        }
+
+        @Override
+        public V put(K key, V value) {
+                final V oldValue;
+                if (Objects.equals(value, defaultValue)) {
+                        final V res = current.remove(key);
+                        if (res == null) {
+                                // no changes: default > default
+                                oldValue = defaultValue;
+                        } else {
+                                oldValue = res;
+                        }
+                } else {
+                        final var mapValue = current.put(key, value);
+                        if (mapValue == null) {
+                                oldValue = defaultValue;
+                        } else {
+                                oldValue = mapValue;
+                        }
+                }
+                if(!Objects.equals(oldValue,value)) {
+                        uncommittedStore.processChange(key, oldValue, value);
+                }
+                return oldValue;
+        }
+
+        @Override
+        public void putAll(Cursor<K, V> cursor) {
+                if (cursor.getDependingMaps().contains(this)) {
+                        List<K> keys = new ArrayList<>();
+                        List<V> values = new ArrayList<>();
+                        while (cursor.move()) {
+                                keys.add(cursor.getKey());
+                                values.add(cursor.getValue());
+                        }
+                        for (int i = 0; i < keys.size(); i++) {
+                                this.put(keys.get(i), values.get(i));
+                        }
+                } else {
+                        while (cursor.move()) {
+                                this.put(cursor.getKey(), cursor.getValue());
+                        }
+                }
+        }
+
+        @Override
+        public long getSize() {
+                return current.size();
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(Version state) {
+                MapDelta<K, V>[] backward = this.uncommittedStore.extractDeltas();
+                List<MapDelta<K, V>[]> backwardTransactions = new ArrayList<>();
+                List<MapDelta<K, V>[]> forwardTransactions = new ArrayList<>();
+
+                if (backward != null) {
+                        backwardTransactions.add(backward);
+                }
+
+                if (this.previous != null) {
+                        store.getPath(this.previous, state, backwardTransactions, forwardTransactions);
+                } else {
+                        store.getPath(state, forwardTransactions);
+                }
+
+                return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions);
+        }
+
+        @Override
+        public int contentHashCode(ContentHashCode mode) {
+                return this.current.hashCode();
+        }
+
+        @Override
+        public boolean contentEquals(AnyVersionedMap other) {
+                if (other instanceof VersionedMapDeltaImpl<?, ?> versioned) {
+                        if (versioned == this) {
+                                return true;
+                        } else {
+                                return Objects.equals(this.defaultValue, versioned.defaultValue) && Objects.equals(this.current, versioned.current);
+                        }
+                } else {
+                        throw new UnsupportedOperationException("Comparing different map implementations is ineffective.");
+                }
+        }
+
+        @Override
+        public void checkIntegrity() {
+                this.uncommittedStore.checkIntegrity();
+
+                for (var entry : this.current.entrySet()) {
+                        var value = entry.getValue();
+                        if (value == this.defaultValue) {
+                                throw new IllegalStateException("Default value stored in map!");
+                        } else if (value == null) {
+                                throw new IllegalStateException("null value stored in map!");
+                        }
+                }
+                MapTransaction<K,V> transaction = this.previous;
+                while(transaction != null) {
+                        MapTransaction<K,V> parent = transaction.parent();
+                        if(parent != null) {
+                                if(parent.depth() != transaction.depth()-1) {
+                                        throw new IllegalStateException("Parent depths are inconsistent!");
+                                }
+                        } else {
+                                if(transaction.depth() != 0) {
+                                        throw new IllegalArgumentException("Root depth is not 0!");
+                                }
+                        }
+                        transaction = transaction.parent();
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java
new file mode 100644
index 00000000..ed169409
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java
@@ -0,0 +1,94 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.delta;
+
+import tools.refinery.store.map.DiffCursor;
+import tools.refinery.store.map.Version;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.VersionedMapStore;
+
+import java.util.*;
+
+public class VersionedMapStoreDeltaImpl<K, V> implements VersionedMapStore<K, V> {
+        // Configuration
+        protected final boolean summarizeChanges;
+
+        // Static data
+        protected final V defaultValue;
+
+        public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) {
+                this.summarizeChanges = summarizeChanges;
+                this.defaultValue = defaultValue;
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap() {
+                return new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue);
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap(Version state) {
+                VersionedMapDeltaImpl<K, V> result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue);
+                result.restore(state);
+                return result;
+        }
+
+        public MapTransaction<K, V> appendTransaction(MapDelta<K, V>[] deltas, MapTransaction<K, V> previous) {
+                if (deltas == null) {
+                        return previous;
+                } else {
+                        final int depth;
+                        if(previous != null) {
+                                depth = previous.depth()+1;
+                        } else {
+                                depth = 0;
+                        }
+                        return new MapTransaction<>(deltas, previous, depth);
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        private MapTransaction<K, V> getState(Version state) {
+                return (MapTransaction<K, V>) state;
+        }
+
+        public MapTransaction<K, V> getPath(Version to, List<MapDelta<K, V>[]> forwardTransactions) {
+                final MapTransaction<K, V> target = getState(to);
+                MapTransaction<K, V> toTransaction = target;
+                while (toTransaction != null) {
+                        forwardTransactions.add(toTransaction.deltas());
+                        toTransaction = toTransaction.parent();
+                }
+                return target;
+        }
+
+        public MapTransaction<K, V> getPath(Version from, Version to,
+                                                List<MapDelta<K, V>[]> backwardTransactions,
+                                                List<MapDelta<K, V>[]> forwardTransactions) {
+                MapTransaction<K, V> fromTransaction = getState(from);
+                final MapTransaction<K, V> target = getState(to);
+                MapTransaction<K, V> toTransaction = target;
+
+                while (fromTransaction != toTransaction) {
+                        if (fromTransaction == null || (toTransaction != null && fromTransaction.depth() < toTransaction.depth())) {
+                                forwardTransactions.add(toTransaction.deltas());
+                                toTransaction = toTransaction.parent();
+                        } else {
+                                backwardTransactions.add(fromTransaction.deltas());
+                                fromTransaction = fromTransaction.parent();
+                        }
+                }
+                return target;
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(Version fromState, Version toState) {
+                List<MapDelta<K, V>[]> backwardTransactions = new ArrayList<>();
+                List<MapDelta<K, V>[]> forwardTransactions = new ArrayList<>();
+                getPath(fromState, toState, backwardTransactions, forwardTransactions);
+                return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java
index 03dffc15..5b1d8b77 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java
@@ -1,16 +1,17 @@
 /*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
  *
  * SPDX-License-Identifier: EPL-2.0
  */
-package tools.refinery.store.map.internal;
+package tools.refinery.store.map.internal.state;
 
 import java.util.Arrays;
 import java.util.Map;
 
-import tools.refinery.store.map.ContinousHashProvider;
+import tools.refinery.store.map.ContinuousHashProvider;
+import tools.refinery.store.map.Version;
 
-public class ImmutableNode<K, V> extends Node<K, V> {
+public class ImmutableNode<K, V> extends Node<K, V> implements Version {
         /**
          * Bitmap defining the stored key and values.
          */
@@ -20,7 +21,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
          */
         final int nodeMap;
         /**
-         * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored
+         * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored
          * backwards.
          */
         final Object[] content;
@@ -47,8 +48,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
          *              available.
          * @return an immutable version of the input node.
          */
-        static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node,
-                        Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+        static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, Map<Node<K, V>, ImmutableNode<K, V>> cache) {
                 // 1. try to return from cache
                 if (cache != null) {
                         ImmutableNode<K, V> cachedResult = cache.get(node);
@@ -71,25 +71,24 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 int resultDataMap = 0;
                 int resultNodeMap = 0;
                 final Object[] resultContent = new Object[size];
-                int bitposition = 1;
+                int bitPosition = 1;
                 for (int i = 0; i < FACTOR; i++) {
                         Object key = node.content[i * 2];
                         if (key != null) {
-                                resultDataMap |= bitposition;
+                                resultDataMap |= bitPosition;
                                 resultContent[datas * 2] = key;
                                 resultContent[datas * 2 + 1] = node.content[i * 2 + 1];
                                 datas++;
                         } else {
-                                @SuppressWarnings("unchecked")
-                                var subnode = (Node<K, V>) node.content[i * 2 + 1];
+                                @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1];
                                 if (subnode != null) {
-                                        ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache);
-                                        resultNodeMap |= bitposition;
-                                        resultContent[size - 1 - nodes] = immutableSubnode;
+                                        ImmutableNode<K, V> immutableSubNode = subnode.toImmutable(cache);
+                                        resultNodeMap |= bitPosition;
+                                        resultContent[size - 1 - nodes] = immutableSubNode;
                                         nodes++;
                                 }
                         }
-                        bitposition <<= 1;
+                        bitPosition <<= 1;
                 }
                 final int resultHash = node.hashCode();
                 var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash);
@@ -106,17 +105,15 @@ public class ImmutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+        public V getValue(K key, ContinuousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
                 int bitposition = 1 << selectedHashFragment;
                 // If the key is stored as a data
                 if ((dataMap & bitposition) != 0) {
                         int keyIndex = 2 * index(dataMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        K keyCandidate = (K) content[keyIndex];
+                        @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex];
                         if (keyCandidate.equals(key)) {
-                                @SuppressWarnings("unchecked")
-                                V value = (V) content[keyIndex + 1];
+                                @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1];
                                 return value;
                         } else {
                                 return defaultValue;
@@ -125,9 +122,8 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 // the key is stored as a node
                 else if ((nodeMap & bitposition) != 0) {
                         int keyIndex = content.length - 1 - index(nodeMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        var subNode = (ImmutableNode<K, V>) content[keyIndex];
-                        int newDepth = depth + 1;
+                        @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex];
+                        int newDepth = incrementDepth(depth);
                         int newHash = newHash(hashProvider, key, hash, newDepth);
                         return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
                 }
@@ -138,44 +134,41 @@ public class ImmutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider,
-                        V defaultValue, int hash, int depth) {
+        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinuousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
-                int bitposition = 1 << selectedHashFragment;
-                if ((dataMap & bitposition) != 0) {
-                        int keyIndex = 2 * index(dataMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        K keyCandidate = (K) content[keyIndex];
+                int bitPosition = 1 << selectedHashFragment;
+                if ((dataMap & bitPosition) != 0) {
+                        int keyIndex = 2 * index(dataMap, bitPosition);
+                        @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex];
                         if (keyCandidate.equals(key)) {
                                 if (value == defaultValue) {
                                         // delete
                                         MutableNode<K, V> mutable = this.toMutable();
                                         return mutable.removeEntry(selectedHashFragment, oldValue);
                                 } else if (value == content[keyIndex + 1]) {
-                                        // dont change
+                                        // don't change
                                         oldValue.setOldValue(value);
                                         return this;
                                 } else {
-                                        // update existing nodeId
+                                        // update existing value
                                         MutableNode<K, V> mutable = this.toMutable();
                                         return mutable.updateValue(value, oldValue, selectedHashFragment);
                                 }
                         } else {
                                 if (value == defaultValue) {
-                                        // dont change
+                                        // don't change
                                         oldValue.setOldValue(defaultValue);
                                         return this;
                                 } else {
-                                        // add new key + nodeId
+                                        // add new key + value
                                         MutableNode<K, V> mutable = this.toMutable();
                                         return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
                                 }
                         }
-                } else if ((nodeMap & bitposition) != 0) {
-                        int keyIndex = content.length - 1 - index(nodeMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        var subNode = (ImmutableNode<K, V>) content[keyIndex];
-                        int newDepth = depth + 1;
+                } else if ((nodeMap & bitPosition) != 0) {
+                        int keyIndex = content.length - 1 - index(nodeMap, bitPosition);
+                        @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex];
+                        int newDepth = incrementDepth(depth);
                         int newHash = newHash(hashProvider, key, hash, newDepth);
                         var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth);
 
@@ -184,10 +177,11 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                 return this;
                         } else {
                                 MutableNode<K, V> mutable = toMutable();
-                                return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue));
+                                return mutable.updateWithSubNode(selectedHashFragment, newsubNode,
+                                                (value == null && defaultValue == null) || (value != null && value.equals(defaultValue)));
                         }
                 } else {
-                        // add new key + nodeId
+                        // add new key + value
                         MutableNode<K, V> mutable = this.toMutable();
                         return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
                 }
@@ -197,8 +191,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
         public long getSize() {
                 int result = Integer.bitCount(this.dataMap);
                 for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
-                        @SuppressWarnings("unchecked")
-                        var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex];
+                        @SuppressWarnings("unchecked") var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex];
                         result += subnode.getSize();
                 }
                 return result;
@@ -238,6 +231,9 @@ public class ImmutableNode<K, V> extends Node<K, V> {
 
                 // 2. look inside the subnodes
                 int nodes = Integer.bitCount(this.nodeMap);
+                if(cursor.nodeIndexStack.peek()==null) {
+                        throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
+                }
                 int newNodeIndex = cursor.nodeIndexStack.peek() + 1;
                 if (newNodeIndex < nodes) {
                         // 2.1 found next subnode, move down to the subnode
@@ -264,10 +260,51 @@ public class ImmutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public void prettyPrint(StringBuilder builder, int depth, int code) {
-                for (int i = 0; i < depth; i++) {
-                        builder.append("\t");
+        @SuppressWarnings("unchecked")
+        boolean moveToNextInorder(InOrderMapCursor<K, V> cursor) {
+                if(cursor.nodeIndexStack.peek()==null) {
+                        throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
                 }
+
+                int position = cursor.nodeIndexStack.peek();
+                for (int index = position + 1; index < FACTOR; index++) {
+                        final int mask = 1<<index;
+                        if((this.dataMap & mask) != 0) {
+                                // data found
+                                cursor.nodeIndexStack.pop();
+                                cursor.nodeIndexStack.push(index);
+
+                                cursor.key = (K) this.content[2 * index(dataMap, mask)];
+                                cursor.value = (V) this.content[2 * index(dataMap, mask) +1];
+                                return true;
+                        } else if((this.nodeMap & mask) != 0) {
+                                // node found
+                                Node<K,V> subnode = (Node<K, V>) this.content[this.content.length - 1 - index(nodeMap, mask)];
+                                cursor.nodeIndexStack.pop();
+                                cursor.nodeIndexStack.push(index);
+                                cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START);
+                                cursor.nodeStack.push(subnode);
+
+                                return subnode.moveToNextInorder(cursor);
+                        }
+                }
+
+                // nothing found
+                cursor.nodeStack.pop();
+                cursor.nodeIndexStack.pop();
+                if (!cursor.nodeStack.isEmpty()) {
+                        Node<K, V> supernode = cursor.nodeStack.peek();
+                        return supernode.moveToNextInorder(cursor);
+                } else {
+                        cursor.key = null;
+                        cursor.value = null;
+                        return false;
+                }
+        }
+
+        @Override
+        public void prettyPrint(StringBuilder builder, int depth, int code) {
+                builder.append("\t".repeat(Math.max(0, depth)));
                 if (code >= 0) {
                         builder.append(code);
                         builder.append(":");
@@ -294,17 +331,16 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 int nodeMask = 1;
                 for (int i = 0; i < FACTOR; i++) {
                         if ((nodeMask & nodeMap) != 0) {
-                                @SuppressWarnings("unchecked")
-                                Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)];
+                                @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)];
                                 builder.append("\n");
-                                subNode.prettyPrint(builder, depth + 1, i);
+                                subNode.prettyPrint(builder, incrementDepth(depth), i);
                         }
                         nodeMask <<= 1;
                 }
         }
 
         @Override
-        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+        public void checkIntegrity(ContinuousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
                 if (depth > 0) {
                         boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0;
                         if (orphaned) {
@@ -315,12 +351,11 @@ public class ImmutableNode<K, V> extends Node<K, V> {
 
                 // check subnodes
                 for (int i = 0; i < Integer.bitCount(nodeMap); i++) {
-                        @SuppressWarnings("unchecked")
-                        var subnode = (Node<K, V>) this.content[this.content.length - 1 - i];
+                        @SuppressWarnings("unchecked") var subnode = (Node<K, V>) this.content[this.content.length - 1 - i];
                         if (!(subnode instanceof ImmutableNode<?, ?>)) {
                                 throw new IllegalStateException("Immutable node contains mutable subnodes!");
                         } else {
-                                subnode.checkIntegrity(hashProvider, defaultValue, depth + 1);
+                                subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth));
                         }
                 }
         }
@@ -332,13 +367,10 @@ public class ImmutableNode<K, V> extends Node<K, V> {
 
         @Override
         public boolean equals(Object obj) {
-                if (this == obj)
-                        return true;
-                if (obj == null)
-                        return false;
+                if (this == obj) return true;
+                if (obj == null) return false;
                 if (obj instanceof ImmutableNode<?, ?> other) {
-                        return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap
-                                        && Arrays.deepEquals(content, other.content);
+                        return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content);
                 } else if (obj instanceof MutableNode<?, ?> mutableObj) {
                         return ImmutableNode.compareImmutableMutable(this, mutableObj);
                 } else {
@@ -356,19 +388,17 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                         if (key != null) {
                                 // Check whether a new Key-Value pair can fit into the immutable container
                                 if (datas * 2 + nodes + 2 <= immutableLength) {
-                                        if (!immutable.content[datas * 2].equals(key)
-                                                        || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) {
+                                        if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) {
                                                 return false;
                                         }
-                                } else
-                                        return false;
+                                } else return false;
                                 datas++;
                         } else {
                                 var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1];
                                 if (mutableSubnode != null) {
                                         if (datas * 2 + nodes + 1 <= immutableLength) {
-                                                Object immutableSubnode = immutable.content[immutableLength - 1 - nodes];
-                                                if (!mutableSubnode.equals(immutableSubnode)) {
+                                                Object immutableSubNode = immutable.content[immutableLength - 1 - nodes];
+                                                if (!mutableSubnode.equals(immutableSubNode)) {
                                                         return false;
                                                 }
                                                 nodes++;
@@ -378,6 +408,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                 }
                         }
                 }
-                return true;
+
+                return datas * 2 + nodes == immutable.content.length;
         }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java
new file mode 100644
index 00000000..7cc91004
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java
@@ -0,0 +1,146 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.state;
+
+import tools.refinery.store.map.AnyVersionedMap;
+import tools.refinery.store.map.ContentHashCode;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.VersionedMap;
+
+import java.util.*;
+
+public class InOrderMapCursor<K, V> implements Cursor<K, V> {
+        // Constants
+        static final int INDEX_START = -1;
+
+        // Tree stack
+        ArrayDeque<Node<K, V>> nodeStack;
+        ArrayDeque<Integer> nodeIndexStack;
+
+
+        // Values
+        K key;
+        V value;
+
+        // Hash code for checking concurrent modifications
+        final VersionedMap<K, V> map;
+        final int creationHash;
+
+        public InOrderMapCursor(VersionedMapStateImpl<K, V> map) {
+                // Initializing tree stack
+                super();
+                this.nodeStack = new ArrayDeque<>();
+                this.nodeIndexStack = new ArrayDeque<>();
+                if (map.root != null) {
+                        this.nodeStack.add(map.root);
+                        this.nodeIndexStack.push(INDEX_START);
+                }
+
+                // Initializing cache
+                this.key = null;
+                this.value = null;
+
+                // Initializing state
+                this.map = map;
+                this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST);
+        }
+
+        public K getKey() {
+                return key;
+        }
+
+        public V getValue() {
+                return value;
+        }
+
+        public boolean isTerminated() {
+                return this.nodeStack.isEmpty();
+        }
+
+        public boolean move() {
+                if (isDirty()) {
+                        throw new ConcurrentModificationException();
+                }
+                if (!isTerminated()) {
+                        var node = this.nodeStack.peek();
+                        if (node == null) {
+                                throw new IllegalStateException("Cursor is not terminated but the current node is missing");
+                        }
+                        boolean result = node.moveToNextInorder(this);
+                        if (this.nodeIndexStack.size() != this.nodeStack.size()) {
+                                throw new IllegalArgumentException("Node stack is corrupted by illegal moves!");
+                        }
+                        return result;
+                }
+                return false;
+        }
+
+        public boolean skipCurrentNode() {
+                nodeStack.pop();
+                nodeIndexStack.pop();
+                return move();
+        }
+
+        @Override
+        public boolean isDirty() {
+                return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash;
+        }
+
+        @Override
+        public Set<AnyVersionedMap> getDependingMaps() {
+                return Set.of(this.map);
+        }
+
+        public static <K, V> boolean sameSubNode(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
+                Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
+                Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
+                return Objects.equals(nodeOfCursor1, nodeOfCursor2);
+        }
+
+        /**
+         * Compares the state of two cursors started on two {@link VersionedMap} of the same
+         * {@link tools.refinery.store.map.VersionedMapStore}.
+         * @param <K> Key type
+         * @param <V> Value type
+         * @param cursor1 first cursor
+         * @param cursor2 second cursor
+         * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the
+         * same position.
+         */
+        public static <K, V> int comparePosition(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
+                // If the state does not determine the order, then compare @nodeIndexStack.
+                Iterator<Integer> nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator();
+                Iterator<Integer> nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator();
+
+                while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){
+                        final int index1 = nodeIndexStack1.next();
+                        final int index2 = nodeIndexStack2.next();
+                        if(index1 < index2) {
+                                return 1;
+                        } else if(index1 > index2) {
+                                return -1;
+                        }
+                }
+
+                return 0;
+        }
+
+        /**
+         * Compares the depth of two cursors started on  @{@link VersionedMap} of the same
+         *        {@link tools.refinery.store.map.VersionedMapStore}.
+         * @param <K> Key type
+         * @param <V> Value type
+         * @param cursor1 first cursor
+         * @param cursor2 second cursor
+         * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the
+         *  same depth.
+         */
+        public static <K, V> int compareDepth(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
+                int d1 = cursor1.nodeIndexStack.size();
+                int d2 = cursor2.nodeIndexStack.size();
+                return Integer.compare(d1, d2);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java
index f34ec7bb..0db50d04 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java
@@ -1,9 +1,9 @@
 /*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
  *
  * SPDX-License-Identifier: EPL-2.0
  */
-package tools.refinery.store.map.internal;
+package tools.refinery.store.map.internal.state;
 
 import tools.refinery.store.map.AnyVersionedMap;
 import tools.refinery.store.map.ContentHashCode;
@@ -12,7 +12,6 @@ import tools.refinery.store.map.VersionedMap;
 
 import java.util.ArrayDeque;
 import java.util.ConcurrentModificationException;
-import java.util.Iterator;
 import java.util.Set;
 
 public class MapCursor<K, V> implements Cursor<K, V> {
@@ -84,13 +83,6 @@ public class MapCursor<K, V> implements Cursor<K, V> {
                 return false;
         }
 
-        public boolean skipCurrentNode() {
-                nodeStack.pop();
-                nodeIndexStack.pop();
-                dataIndex = INDEX_FINISH;
-                return move();
-        }
-
         @Override
         public boolean isDirty() {
                 return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash;
@@ -100,46 +92,4 @@ public class MapCursor<K, V> implements Cursor<K, V> {
         public Set<AnyVersionedMap> getDependingMaps() {
                 return Set.of(this.map);
         }
-
-        public static <K, V> boolean sameSubnode(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) {
-                Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
-                Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
-                if (nodeOfCursor1 != null && nodeOfCursor2 != null) {
-                        return nodeOfCursor1.equals(nodeOfCursor2);
-                } else {
-                        return false;
-                }
-        }
-
-        /**
-         * @param <K>
-         * @param <V>
-         * @param cursor1
-         * @param cursor2
-         * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the
-         * same position.
-         */
-        public static <K, V> int compare(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) {
-                // two cursors are equally deep
-                Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator();
-                Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator();
-                if (stack1.hasNext()) {
-                        if (!stack2.hasNext()) {
-                                // stack 2 has no more element, thus stack 1 is deeper
-                                return 1;
-                        }
-                        int val1 = stack1.next();
-                        int val2 = stack2.next();
-                        if (val1 < val2) {
-                                return -1;
-                        } else if (val2 < val1) {
-                                return 1;
-                        }
-                }
-                if (stack2.hasNext()) {
-                        // stack 2 has more element, thus stack 2 is deeper
-                        return 1;
-                }
-                return Integer.compare(cursor1.dataIndex, cursor2.dataIndex);
-        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java
new file mode 100644
index 00000000..083bf8cf
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java
@@ -0,0 +1,264 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.state;
+
+import tools.refinery.store.map.AnyVersionedMap;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.DiffCursor;
+
+import java.util.Objects;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+/**
+ * A cursor representing the difference between two states of a map.
+ *
+ * @author Oszkar Semerath
+ */
+public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
+        private enum State {
+                /**
+                 * initialized state.
+                 */
+                INIT,
+                /**
+                 * Unstable state.
+                 */
+                MOVING_MOVING_SAME_KEY_SAME_VALUE,
+                /**
+                 * Both cursors are moving, and they are on the same sub-node.
+                 */
+                MOVING_MOVING_SAME_NODE,
+                /**
+                 * Both cursors are moving, cursor 1 is behind.
+                 */
+                MOVING_MOVING_BEHIND1,
+                /**
+                 * Both cursors are moving, cursor 2 is behind.
+                 */
+                MOVING_MOVING_BEHIND2,
+                /**
+                 * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different
+                 */
+                MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE,
+                /**
+                 * Cursor 1 is moving, Cursor 2 is terminated.
+                 */
+                MOVING_TERMINATED,
+                /**
+                 * Cursor 1 is terminated , Cursor 2 is moving.
+                 */
+                TERMINATED_MOVING,
+                /**
+                 * Both cursors are terminated.
+                 */
+                TERMINATED_TERMINATED,
+                /**
+                 * Both Cursors are moving, and they are on an incomparable position.
+                 * It is resolved by showing Cursor 1.
+                 */
+                MOVING_MOVING_HASH1,
+                /**
+                 * Both Cursors are moving, and they are on an incomparable position.
+                 * It is resolved by showing Cursor 2.
+                 */
+                MOVING_MOVING_HASH2
+        }
+
+        /**
+         * Default nodeId representing missing elements.
+         */
+        private final V defaultValue;
+        private final InOrderMapCursor<K, V> cursor1;
+        private final InOrderMapCursor<K, V> cursor2;
+
+        // State
+        State state = State.INIT;
+
+        // Values
+        private K key;
+        private V fromValue;
+        private V toValue;
+
+
+        public MapDiffCursor(V defaultValue, InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
+                super();
+                this.defaultValue = defaultValue;
+                this.cursor1 = cursor1;
+                this.cursor2 = cursor2;
+        }
+
+        @Override
+        public K getKey() {
+                return key;
+        }
+
+        @Override
+        public V getFromValue() {
+                return fromValue;
+        }
+
+        @Override
+        public V getToValue() {
+                return toValue;
+        }
+
+        @Override
+        public V getValue() {
+                return getToValue();
+        }
+
+        public boolean isTerminated() {
+                return this.state == State.TERMINATED_TERMINATED;
+        }
+
+        @Override
+        public boolean isDirty() {
+                return this.cursor1.isDirty() || this.cursor2.isDirty();
+        }
+
+        @Override
+        public Set<AnyVersionedMap> getDependingMaps() {
+                return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet());
+        }
+
+        private boolean isInStableState() {
+                return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE
+                                && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT;
+        }
+
+        private boolean updateAndReturnWithResult() {
+                return switch (this.state) {
+                        case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!");
+                        case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE ->
+                                        throw new IllegalStateException("DiffCursor terminated in unstable state!");
+                        case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> {
+                                this.key = this.cursor1.getKey();
+                                this.fromValue = this.cursor1.getValue();
+                                this.toValue = this.defaultValue;
+                                yield true;
+                        }
+                        case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> {
+                                this.key = this.cursor2.getKey();
+                                this.fromValue = this.defaultValue;
+                                this.toValue = cursor2.getValue();
+                                yield true;
+                        }
+                        case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> {
+                                this.key = this.cursor1.getKey();
+                                this.fromValue = this.cursor1.getValue();
+                                this.toValue = this.cursor2.getValue();
+                                yield true;
+                        }
+                        case TERMINATED_TERMINATED -> {
+                                this.key = null;
+                                this.fromValue = null;
+                                this.toValue = null;
+                                yield false;
+                        }
+                };
+        }
+
+        public boolean move() {
+                do {
+                        this.state = moveOne(this.state);
+                } while (!isInStableState());
+                return updateAndReturnWithResult();
+        }
+
+        private State moveOne(State currentState) {
+                return switch (currentState) {
+                        case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> {
+                                boolean cursor1Moved = cursor1.move();
+                                boolean cursor2Moved = cursor2.move();
+                                yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved);
+                        }
+                        case MOVING_MOVING_SAME_NODE -> {
+                                boolean cursor1Moved = cursor1.skipCurrentNode();
+                                boolean cursor2Moved = cursor2.skipCurrentNode();
+                                yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved);
+                        }
+                        case MOVING_MOVING_BEHIND1 -> {
+                                boolean cursorMoved = cursor1.move();
+                                if (cursorMoved) {
+                                        yield recalculateStateBasedOnCursorRelation();
+                                } else {
+                                        yield State.TERMINATED_MOVING;
+                                }
+                        }
+                        case MOVING_MOVING_BEHIND2 -> {
+                                boolean cursorMoved = cursor2.move();
+                                if (cursorMoved) {
+                                        yield recalculateStateBasedOnCursorRelation();
+                                } else {
+                                        yield State.MOVING_TERMINATED;
+                                }
+                        }
+                        case TERMINATED_MOVING -> {
+                                boolean cursorMoved = cursor2.move();
+                                if (cursorMoved) {
+                                        yield State.TERMINATED_MOVING;
+                                } else {
+                                        yield State.TERMINATED_TERMINATED;
+                                }
+                        }
+                        case MOVING_TERMINATED -> {
+                                boolean cursorMoved = cursor1.move();
+                                if (cursorMoved) {
+                                        yield State.MOVING_TERMINATED;
+                                } else {
+                                        yield State.TERMINATED_TERMINATED;
+                                }
+                        }
+                        case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2;
+                        case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!");
+                };
+        }
+
+        private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) {
+                if (cursor1Moved && cursor2Moved) {
+                        return recalculateStateBasedOnCursorRelation();
+                } else if (cursor1Moved) {
+                        return State.MOVING_TERMINATED;
+                } else if (cursor2Moved) {
+                        return State.TERMINATED_MOVING;
+                } else {
+                        return State.TERMINATED_TERMINATED;
+                }
+        }
+
+        private State recalculateStateBasedOnCursorRelation() {
+                final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2);
+
+                if (relation > 0) {
+                        return State.MOVING_MOVING_BEHIND1;
+                } else if (relation < 0) {
+                        return State.MOVING_MOVING_BEHIND2;
+                }
+
+                if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) {
+                        return State.MOVING_MOVING_SAME_NODE;
+                } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) {
+                        if (Objects.equals(cursor1.getValue(), cursor2.getValue())) {
+                                return State.MOVING_MOVING_SAME_KEY_SAME_VALUE;
+                        } else {
+                                return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE;
+                        }
+                }
+
+                final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2);
+
+                if (depth > 0) {
+                        return State.MOVING_MOVING_BEHIND1;
+                } else if (depth < 0) {
+                        return State.MOVING_MOVING_BEHIND2;
+                } else {
+                        return State.MOVING_MOVING_HASH1;
+                }
+
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java
index 1129ee5a..408ed62c 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java
@@ -1,26 +1,26 @@
 /*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
  *
  * SPDX-License-Identifier: EPL-2.0
  */
-package tools.refinery.store.map.internal;
+package tools.refinery.store.map.internal.state;
 
-import tools.refinery.store.map.ContinousHashProvider;
+import tools.refinery.store.map.ContinuousHashProvider;
 
 import java.util.Arrays;
 import java.util.Map;
 
 public class MutableNode<K, V> extends Node<K, V> {
         int cachedHash;
+        protected boolean cachedHashValid;
         protected Object[] content;
 
         protected MutableNode() {
                 this.content = new Object[2 * FACTOR];
-                updateHash();
+                invalidateHash();
         }
 
-        public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider,
-                        V defaultValue) {
+        public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinuousHashProvider<? super K> hashProvider, V defaultValue) {
                 if (value == defaultValue) {
                         return null;
                 } else {
@@ -29,7 +29,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                         MutableNode<K, V> res = new MutableNode<>();
                         res.content[2 * fragment] = key;
                         res.content[2 * fragment + 1] = value;
-                        res.updateHash();
+                        res.invalidateHash();
                         return res;
                 }
         }
@@ -37,44 +37,41 @@ public class MutableNode<K, V> extends Node<K, V> {
         /**
          * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
          *
-         * @param node
+         * @param node to be transformed
          */
         protected MutableNode(ImmutableNode<K, V> node) {
                 this.content = new Object[2 * FACTOR];
                 int dataUsed = 0;
                 int nodeUsed = 0;
                 for (int i = 0; i < FACTOR; i++) {
-                        int bitposition = 1 << i;
-                        if ((node.dataMap & bitposition) != 0) {
+                        int bitPosition = 1 << i;
+                        if ((node.dataMap & bitPosition) != 0) {
                                 content[2 * i] = node.content[dataUsed * 2];
                                 content[2 * i + 1] = node.content[dataUsed * 2 + 1];
                                 dataUsed++;
-                        } else if ((node.nodeMap & bitposition) != 0) {
+                        } else if ((node.nodeMap & bitPosition) != 0) {
                                 content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed];
                                 nodeUsed++;
                         }
                 }
-                this.cachedHash = node.hashCode();
+                this.cachedHashValid = false;
         }
 
         @Override
-        public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+        public V getValue(K key, ContinuousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
-                @SuppressWarnings("unchecked")
-                K keyCandidate = (K) this.content[2 * selectedHashFragment];
+                @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment];
                 if (keyCandidate != null) {
                         if (keyCandidate.equals(key)) {
-                                @SuppressWarnings("unchecked")
-                                V value = (V) this.content[2 * selectedHashFragment + 1];
+                                @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1];
                                 return value;
                         } else {
                                 return defaultValue;
                         }
                 } else {
-                        @SuppressWarnings("unchecked")
-                        var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
                         if (nodeCandidate != null) {
-                                int newDepth = depth + 1;
+                                int newDepth = incrementDepth(depth);
                                 int newHash = newHash(hashProvider, key, hash, newDepth);
                                 return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
                         } else {
@@ -84,13 +81,11 @@ public class MutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider,
-                        V defaultValue, int hash, int depth) {
+        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinuousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
-                @SuppressWarnings("unchecked")
-                K keyCandidate = (K) content[2 * selectedHashFragment];
+                @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment];
                 if (keyCandidate != null) {
-                        // If has key
+                        // If it has key
                         if (keyCandidate.equals(key)) {
                                 // The key is equals to an existing key -> update entry
                                 if (value == defaultValue) {
@@ -111,25 +106,22 @@ public class MutableNode<K, V> extends Node<K, V> {
                                         return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
                                 }
                         }
+                }
+                // If it does not have key, check for value
+                @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                if (nodeCandidate != null) {
+                        // If it has value, it is a sub-node -> update that
+                        int newDepth = incrementDepth(depth);
+                        var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth);
+                        return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue)));
                 } else {
-                        // If it does not have key, check for nodeId
-                        @SuppressWarnings("unchecked")
-                        var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
-                        if (nodeCandidate != null) {
-                                // If it has nodeId, it is a subnode -> upate that
-                                var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue,
-                                                newHash(hashProvider, key, hash, depth + 1), depth + 1);
-                                return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
+                        // If it does not have value, put it in the empty place
+                        if (value == defaultValue) {
+                                // don't need to add new key-value pair
+                                oldValueBox.setOldValue(defaultValue);
+                                return this;
                         } else {
-                                // If it does not have nodeId, put it in the empty place
-                                if (value == defaultValue) {
-                                        // dont need to add new key-nodeId pair
-                                        oldValueBox.setOldValue(defaultValue);
-                                        return this;
-                                } else {
-                                        return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue);
-                                }
-
+                                return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue);
                         }
                 }
         }
@@ -138,30 +130,31 @@ public class MutableNode<K, V> extends Node<K, V> {
                 content[2 * selectedHashFragment] = key;
                 oldValueBox.setOldValue(defaultValue);
                 content[2 * selectedHashFragment + 1] = value;
-                updateHash();
+                invalidateHash();
                 return this;
         }
 
         /**
-         * Updates an entry in a selected hash-fragment to a non-default nodeId.
+         * Updates an entry in a selected hash-fragment to a non-default value.
          *
-         * @param value
-         * @param selectedHashFragment
-         * @return
+         * @param value new value
+         * @param selectedHashFragment position of the value
+         * @return updated node
          */
         @SuppressWarnings("unchecked")
         Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) {
                 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
                 content[2 * selectedHashFragment + 1] = value;
-                updateHash();
+                invalidateHash();
                 return this;
         }
 
         /**
+         * Updates an entry in a selected hash-fragment with a subtree.
          *
-         * @param selectedHashFragment
-         * @param newNode
-         * @return
+         * @param selectedHashFragment position of the value
+         * @param newNode the subtree
+         * @return updated node
          */
         Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
                 if (deletionHappened) {
@@ -169,7 +162,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                                 // Check whether this node become empty
                                 content[2 * selectedHashFragment + 1] = null; // i.e. the new node
                                 if (hasContent()) {
-                                        updateHash();
+                                        invalidateHash();
                                         return this;
                                 } else {
                                         return null;
@@ -180,10 +173,10 @@ public class MutableNode<K, V> extends Node<K, V> {
                                 if (immutableNewNode != null) {
                                         int orphaned = immutableNewNode.isOrphaned();
                                         if (orphaned >= 0) {
-                                                // orphan subnode data is replaced with data
+                                                // orphan sub-node data is replaced with data
                                                 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
                                                 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
-                                                updateHash();
+                                                invalidateHash();
                                                 return this;
                                         }
                                 }
@@ -191,15 +184,13 @@ public class MutableNode<K, V> extends Node<K, V> {
                 }
                 // normal behaviour
                 content[2 * selectedHashFragment + 1] = newNode;
-                updateHash();
+                invalidateHash();
                 return this;
-
         }
 
         private boolean hasContent() {
                 for (Object element : this.content) {
-                        if (element != null)
-                                return true;
+                        if (element != null) return true;
                 }
                 return false;
         }
@@ -226,27 +217,24 @@ public class MutableNode<K, V> extends Node<K, V> {
         }
 
         @SuppressWarnings("unchecked")
-        private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue,
-                        K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
+        private Node<K, V> moveDownAndSplit(ContinuousHashProvider<? super K> hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
                 V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
 
-                MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
-                                hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
+                MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth));
 
                 content[2 * selectedHashFragmentOfCurrentDepth] = null;
                 content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
-                updateHash();
+                invalidateHash();
                 return this;
         }
 
         // Pass everything as parameters for performance.
         @SuppressWarnings("squid:S107")
-        private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1,
-                        int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
-                int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
-                int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
-                int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
-                int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
+        private MutableNode<K, V> newNodeWithTwoEntries(ContinuousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) {
+                int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth);
+                int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth);
+                int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth));
+                int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth));
 
                 MutableNode<K, V> subNode = new MutableNode<>();
                 if (newFragment1 != newFragment2) {
@@ -256,11 +244,10 @@ public class MutableNode<K, V> extends Node<K, V> {
                         subNode.content[newFragment2 * 2] = key2;
                         subNode.content[newFragment2 * 2 + 1] = value2;
                 } else {
-                        MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2,
-                                        newHash2, newdepth + 1);
+                        MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth));
                         subNode.content[newFragment1 * 2 + 1] = subSubNode;
                 }
-                subNode.updateHash();
+                subNode.invalidateHash();
                 return subNode;
         }
 
@@ -270,7 +257,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
                 content[2 * selectedHashFragment + 1] = null;
                 if (hasContent()) {
-                        updateHash();
+                        invalidateHash();
                         return this;
                 } else {
                         return null;
@@ -321,10 +308,13 @@ public class MutableNode<K, V> extends Node<K, V> {
                         cursor.dataIndex = MapCursor.INDEX_FINISH;
                 }
 
-                // 2. look inside the subnodes
+                // 2. look inside the sub-nodes
+                if(cursor.nodeIndexStack.peek()==null) {
+                        throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
+                }
                 for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) {
                         if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) {
-                                // 2.1 found next subnode, move down to the subnode
+                                // 2.1 found next sub-node, move down to the sub-node
                                 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
 
                                 cursor.dataIndex = MapCursor.INDEX_START;
@@ -336,7 +326,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                                 return subnode.moveToNext(cursor);
                         }
                 }
-                // 3. no subnode found, move up
+                // 3. no sub-node found, move up
                 cursor.nodeStack.pop();
                 cursor.nodeIndexStack.pop();
                 if (!cursor.nodeStack.isEmpty()) {
@@ -350,10 +340,51 @@ public class MutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public void prettyPrint(StringBuilder builder, int depth, int code) {
-                for (int i = 0; i < depth; i++) {
-                        builder.append("\t");
+        @SuppressWarnings("unchecked")
+        boolean moveToNextInorder(InOrderMapCursor<K,V> cursor) {
+                if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) {
+                        throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
                 }
+
+                int position = cursor.nodeIndexStack.peek();
+
+                for (int index = position + 1; index < FACTOR; index++) {
+                        // data found
+                        if (this.content[index * 2] != null) {
+                                cursor.nodeIndexStack.pop();
+                                cursor.nodeIndexStack.push(index);
+
+                                cursor.key = (K) this.content[index * 2];
+                                cursor.value = (V) this.content[index * 2 + 1];
+                                return true;
+                        } else if (this.content[index * 2 +1] != null) {
+                                // sub-node found
+                                Node<K,V> subnode = (Node<K, V>) this.content[index * 2 +1];
+                                cursor.nodeIndexStack.pop();
+                                cursor.nodeIndexStack.push(index);
+                                cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START);
+                                cursor.nodeStack.push(subnode);
+
+                                return subnode.moveToNextInorder(cursor);
+                        }
+                }
+
+                // nothing found
+                cursor.nodeStack.pop();
+                cursor.nodeIndexStack.pop();
+                if (!cursor.nodeStack.isEmpty()) {
+                        Node<K, V> supernode = cursor.nodeStack.peek();
+                        return supernode.moveToNextInorder(cursor);
+                } else {
+                        cursor.key = null;
+                        cursor.value = null;
+                        return false;
+                }
+        }
+
+        @Override
+        public void prettyPrint(StringBuilder builder, int depth, int code) {
+                builder.append("\t".repeat(Math.max(0, depth)));
                 if (code >= 0) {
                         builder.append(code);
                         builder.append(":");
@@ -376,19 +407,18 @@ public class MutableNode<K, V> extends Node<K, V> {
                         }
                 }
                 builder.append(")");
-                // print subnodes
+                // print sub-nodes
                 for (int i = 0; i < FACTOR; i++) {
                         if (content[2 * i] == null && content[2 * i + 1] != null) {
-                                @SuppressWarnings("unchecked")
-                                Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
+                                @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
                                 builder.append("\n");
-                                subNode.prettyPrint(builder, depth + 1, i);
+                                subNode.prettyPrint(builder, incrementDepth(depth), i);
                         }
                 }
         }
 
         @Override
-        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+        public void checkIntegrity(ContinuousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
                 // check for orphan nodes
                 if (depth > 0) {
                         int orphaned = isOrphaned();
@@ -399,57 +429,67 @@ public class MutableNode<K, V> extends Node<K, V> {
                 // check the place of data
                 for (int i = 0; i < FACTOR; i++) {
                         if (this.content[2 * i] != null) {
-                                @SuppressWarnings("unchecked")
-                                K key = (K) this.content[2 * i];
-                                @SuppressWarnings("unchecked")
-                                V value = (V) this.content[2 * i + 1];
+                                @SuppressWarnings("unchecked") K key = (K) this.content[2 * i];
+                                @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1];
 
                                 if (value == defaultValue) {
-                                        throw new IllegalStateException("Node contains default nodeId!");
+                                        throw new IllegalStateException("Node contains default value!");
                                 }
                                 int hashCode = hashProvider.getHash(key, hashDepth(depth));
                                 int shiftDepth = shiftDepth(depth);
                                 int selectedHashFragment = hashFragment(hashCode, shiftDepth);
                                 if (i != selectedHashFragment) {
-                                        throw new IllegalStateException("Key " + key + " with hash code " + hashCode
-                                                        + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
+                                        throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
                                 }
                         }
                 }
-                // check subnodes
+                // check sub-nodes
                 for (int i = 0; i < FACTOR; i++) {
                         if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
-                                @SuppressWarnings("unchecked")
-                                var subNode = (Node<K, V>) this.content[2 * i + 1];
-                                subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
+                                @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1];
+                                subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth));
                         }
                 }
                 // check the hash
-                int oldHash = this.cachedHash;
-                updateHash();
-                int newHash = this.cachedHash;
-                if (oldHash != newHash) {
-                        throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
+                if (cachedHashValid) {
+                        int oldHash = this.cachedHash;
+                        invalidateHash();
+                        int newHash = hashCode();
+                        if (oldHash != newHash) {
+                                throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
+                        }
                 }
         }
 
-        protected void updateHash() {
-                this.cachedHash = Arrays.hashCode(content);
+        protected void invalidateHash() {
+                this.cachedHashValid = false;
         }
 
         @Override
         public int hashCode() {
+                if (!this.cachedHashValid) {
+                        this.cachedHash = Arrays.hashCode(content);
+                        this.cachedHashValid = true;
+                }
                 return this.cachedHash;
         }
 
         @Override
         public boolean equals(Object obj) {
-                if (this == obj)
-                        return true;
-                if (obj == null)
-                        return false;
+                if (this == obj) return true;
+                if (obj == null) return false;
                 if (obj instanceof MutableNode<?, ?> mutableObj) {
-                        return Arrays.deepEquals(this.content, mutableObj.content);
+                        if (obj.hashCode() != this.hashCode()) {
+                                return false;
+                        } else {
+                                for (int i = 0; i < FACTOR * 2; i++) {
+                                        Object thisContent = this.content[i];
+                                        if (thisContent != null && !thisContent.equals(mutableObj.content[i])) {
+                                                return false;
+                                        }
+                                }
+                                return true;
+                        }
                 } else if (obj instanceof ImmutableNode<?, ?> immutableObj) {
                         return ImmutableNode.compareImmutableMutable(immutableObj, this);
                 } else {
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java
new file mode 100644
index 00000000..0ecf2712
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java
@@ -0,0 +1,131 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.state;
+
+import java.util.Map;
+
+import tools.refinery.store.map.ContinuousHashProvider;
+
+public abstract class Node<K, V> {
+        public static final int BRANCHING_FACTOR_BITS = 5;
+        public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS;
+        protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
+        protected static final int FACTOR_MASK = FACTOR - 1;
+        public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
+        public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS);
+        public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1;
+        public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS;
+
+        /**
+         * Increments the depth of the search in the tree. The depth parameter has two
+         * components: the least few bits selects the fragment of the hashcode, the
+         * other part selects the continuous hash.
+         *
+         * @param depth parameter encoding the fragment and the depth
+         * @return new depth.
+         */
+        protected int incrementDepth(int depth) {
+                int newDepth = depth + 1;
+                if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) {
+                        newDepth += INCREMENT_BIG_STEP;
+                }
+                return newDepth;
+        }
+
+        /**
+         * Calculates the index for the continuous hash.
+         *
+         * @param depth The depth of the node in the tree.
+         * @return The index of the continuous hash.
+         */
+        protected static int hashDepth(int depth) {
+                return depth >> FACTOR_SELECTION_BITS;
+        }
+
+        /**
+         * Calculates the which segment of a single hash should be used.
+         *
+         * @param depth The depth of the node in the tree.
+         * @return The segment of a hash code.
+         */
+        protected static int shiftDepth(int depth) {
+                return depth & FACTOR_SELECTION_MASK;
+        }
+
+        /**
+         * Selects a segments from a complete hash for a given depth.
+         *
+         * @param hash       A complete hash.
+         * @param shiftDepth The index of the segment.
+         * @return The segment as an integer.
+         */
+        protected static int hashFragment(int hash, int shiftDepth) {
+                if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth)
+                        throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth);
+                return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK;
+        }
+
+        /**
+         * Returns the hash code for a given depth. It may calculate new hash code, or
+         * reuse a hash code calculated for depth-1.
+         *
+         * @param key   The key.
+         * @param hash  Hash code for depth-1
+         * @param depth The depth.
+         * @return The new hash code.
+         */
+        protected int newHash(final ContinuousHashProvider<? super K> hashProvider, K key, int hash, int depth) {
+                final int shiftDepth = shiftDepth(depth);
+                if (shiftDepth == 0) {
+                        final int hashDepth = hashDepth(depth);
+                        if (hashDepth >= ContinuousHashProvider.MAX_PRACTICAL_DEPTH) {
+                                throw new IllegalArgumentException(
+                                                "Key " + key + " have the clashing hashcode over the practical depth limitation ("
+                                                                + ContinuousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
+                        }
+                        return hashProvider.getHash(key, hashDepth);
+                } else {
+                        return hash;
+                }
+        }
+
+        public abstract V getValue(K key, ContinuousHashProvider<? super K> hashProvider, V defaultValue, int hash,
+                                                           int depth);
+
+        public abstract Node<K, V> putValue(K key, V value, OldValueBox<V> old,
+                                                                                ContinuousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
+
+        public abstract long getSize();
+
+        abstract MutableNode<K, V> toMutable();
+
+        public abstract ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache);
+
+        protected abstract MutableNode<K, V> isMutable();
+
+        /**
+         * Moves a {@link MapCursor} to its next position.
+         *
+         * @param cursor the cursor
+         * @return Whether there was a next value to move on.
+         */
+        abstract boolean moveToNext(MapCursor<K, V> cursor);
+        abstract boolean moveToNextInorder(InOrderMapCursor<K, V> cursor);
+
+        ///////// FOR printing
+        public abstract void prettyPrint(StringBuilder builder, int depth, int code);
+
+
+        @Override
+        public String toString() {
+                StringBuilder stringBuilder = new StringBuilder();
+                prettyPrint(stringBuilder, 0, -1);
+                return stringBuilder.toString();
+        }
+
+        public void checkIntegrity(ContinuousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java
index 354af51d..1b0a4b0c 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java
@@ -1,9 +1,9 @@
 /*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
  *
  * SPDX-License-Identifier: EPL-2.0
  */
-package tools.refinery.store.map.internal;
+package tools.refinery.store.map.internal.state;
 
 public class OldValueBox<V>{
         V oldValue;
@@ -20,5 +20,5 @@ public class OldValueBox<V>{
                 this.oldValue = ouldValue;
                 isSet = true;
         }
-        
+
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java
new file mode 100644
index 00000000..ccc791a8
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java
@@ -0,0 +1,43 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.state;
+
+import tools.refinery.store.map.*;
+
+import java.util.List;
+
+public class StateBasedVersionedMapStoreFactory<K, V> implements VersionedMapStoreFactory<K, V> {
+        private final V defaultValue;
+        private final ContinuousHashProvider<K> continuousHashProvider;
+        private final VersionedMapStoreStateConfiguration config;
+
+        public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable,
+                                                                                          VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy,
+                                                                                          boolean versionFreeingEnabled,
+                                                                                          ContinuousHashProvider<K> continuousHashProvider) {
+                this.defaultValue = defaultValue;
+                this.continuousHashProvider = continuousHashProvider;
+
+                this.config = new VersionedMapStoreStateConfiguration(
+                                transformToImmutable,
+                                sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE
+                                                || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP,
+                                sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP,
+                                versionFreeingEnabled);
+        }
+
+        @Override
+        public VersionedMapStore<K, V> createOne() {
+                return new VersionedMapStoreStateImpl<>(continuousHashProvider, defaultValue, config);
+
+        }
+
+        @Override
+        public List<VersionedMapStore<K, V>> createGroup(int amount) {
+                return VersionedMapStoreStateImpl.createSharedVersionedMapStores(amount, continuousHashProvider, defaultValue,
+                                config);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java
index 7abece0d..57eeccf6 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java
@@ -1,9 +1,9 @@
 /*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
  *
  * SPDX-License-Identifier: EPL-2.0
  */
-package tools.refinery.store.map.internal;
+package tools.refinery.store.map.internal.state;
 
 import tools.refinery.store.map.*;
 
@@ -19,19 +19,18 @@ import java.util.Objects;
  * @param <V>
  * @author Oszkar Semerath
  */
-public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
-        protected final VersionedMapStoreImpl<K, V> store;
-
-        protected final ContinousHashProvider<K> hashProvider;
+public class VersionedMapStateImpl<K, V> implements VersionedMap<K, V> {
+        protected final VersionedMapStoreStateImpl<K, V> store;
 
+        protected final ContinuousHashProvider<K> hashProvider;
         protected final V defaultValue;
         protected Node<K, V> root;
 
         private final OldValueBox<V> oldValueBox = new OldValueBox<>();
 
-        public VersionedMapImpl(
-                        VersionedMapStoreImpl<K, V> store,
-                        ContinousHashProvider<K> hashProvider,
+        public VersionedMapStateImpl(
+                        VersionedMapStoreStateImpl<K, V> store,
+                        ContinuousHashProvider<K> hashProvider,
                         V defaultValue) {
                 this.store = store;
                 this.hashProvider = hashProvider;
@@ -39,9 +38,9 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                 this.root = null;
         }
 
-        public VersionedMapImpl(
-                        VersionedMapStoreImpl<K, V> store,
-                        ContinousHashProvider<K> hashProvider,
+        public VersionedMapStateImpl(
+                        VersionedMapStoreStateImpl<K, V> store,
+                        ContinuousHashProvider<K> hashProvider,
                         V defaultValue, Node<K, V> data) {
                 this.store = store;
                 this.hashProvider = hashProvider;
@@ -49,11 +48,12 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                 this.root = data;
         }
 
+        @Override
         public V getDefaultValue() {
                 return defaultValue;
         }
 
-        public ContinousHashProvider<K> getHashProvider() {
+        public ContinuousHashProvider<K> getHashProvider() {
                 return hashProvider;
         }
 
@@ -80,7 +80,9 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                         Iterator<K> keyIterator = keys.iterator();
                         Iterator<V> valueIterator = values.iterator();
                         while (keyIterator.hasNext()) {
-                                this.put(keyIterator.next(), valueIterator.next());
+                                var key = keyIterator.next();
+                                var value = valueIterator.next();
+                                this.put(key,value);
                         }
                 } else {
                         while (cursor.move()) {
@@ -113,17 +115,16 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
         }
 
         @Override
-        public DiffCursor<K, V> getDiffCursor(long toVersion) {
-                Cursor<K, V> fromCursor = this.getAll();
-                VersionedMap<K, V> toMap = this.store.createMap(toVersion);
-                Cursor<K, V> toCursor = toMap.getAll();
-                return new MapDiffCursor<>(this.hashProvider, this.defaultValue, fromCursor, toCursor);
-
+        public DiffCursor<K, V> getDiffCursor(Version toVersion) {
+                InOrderMapCursor<K, V> fromCursor = new InOrderMapCursor<>(this);
+                VersionedMapStateImpl<K, V> toMap = (VersionedMapStateImpl<K, V>) this.store.createMap(toVersion);
+                InOrderMapCursor<K, V> toCursor = new InOrderMapCursor<>(toMap);
+                return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor);
         }
 
 
         @Override
-        public long commit() {
+        public Version commit() {
                 return this.store.commit(root, this);
         }
 
@@ -132,20 +133,21 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
         }
 
         @Override
-        public void restore(long state) {
+        public void restore(Version state) {
                 root = this.store.revert(state);
         }
 
-        public void prettyPrint() {
-                StringBuilder s = new StringBuilder();
+        public String prettyPrint() {
                 if (this.root != null) {
+                        StringBuilder s = new StringBuilder();
                         this.root.prettyPrint(s, 0, -1);
-                        System.out.println(s.toString());
+                        return s.toString();
                 } else {
-                        System.out.println("empty tree");
+                        return "empty tree";
                 }
         }
 
+        @Override
         public void checkIntegrity() {
                 if (this.root != null) {
                         this.root.checkIntegrity(hashProvider, defaultValue, 0);
@@ -155,11 +157,15 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
         @Override
         public int contentHashCode(ContentHashCode mode) {
                 // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode.
-                return Objects.hashCode(root);
+                if(root == null) {
+                        return 0;
+                } else {
+                        return root.hashCode();
+                }
         }
 
         @Override
         public boolean contentEquals(AnyVersionedMap other) {
-                return other instanceof VersionedMapImpl<?, ?> otherImpl && Objects.equals(root, otherImpl.root);
+                return other instanceof VersionedMapStateImpl<?, ?> otherImpl && Objects.equals(root, otherImpl.root);
         }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java
index b00cd961..6650f565 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java
@@ -1,21 +1,25 @@
 /*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
  *
  * SPDX-License-Identifier: EPL-2.0
  */
-package tools.refinery.store.map;
+package tools.refinery.store.map.internal.state;
 
-public class VersionedMapStoreConfiguration {
+import tools.refinery.store.map.ContinuousHashProvider;
+import tools.refinery.store.map.VersionedMapStore;
 
-        public VersionedMapStoreConfiguration() {
+public class VersionedMapStoreStateConfiguration {
+
+        public VersionedMapStoreStateConfiguration() {
 
         }
-        public VersionedMapStoreConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore,
-                        boolean sharedNodeCacheInStoreGroups) {
+        public VersionedMapStoreStateConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore,
+                                                                                           boolean sharedNodeCacheInStoreGroups, boolean versionFreeingEnabled) {
                 super();
                 this.immutableWhenCommitting = immutableWhenCommitting;
                 this.sharedNodeCacheInStore = sharedNodeCacheInStore;
                 this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups;
+                this.versionFreeingEnabled = versionFreeingEnabled;
         }
 
         /**
@@ -42,12 +46,17 @@ public class VersionedMapStoreConfiguration {
 
         /**
          * If true, all sub-nodes are cached within a group of
-         * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}.
-         * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is
+         * {@link VersionedMapStoreStateImpl#createSharedVersionedMapStores(int, ContinuousHashProvider, Object, VersionedMapStoreStateConfiguration)}.
+         * If {@link VersionedMapStoreStateConfiguration#sharedNodeCacheInStore} is
          * <code>false</code>, then it has currently no impact.
          */
         private boolean sharedNodeCacheInStoreGroups = true;
         public boolean isSharedNodeCacheInStoreGroups() {
                 return sharedNodeCacheInStoreGroups;
         }
+
+        private boolean versionFreeingEnabled = true;
+        public boolean isVersionFreeingEnabled() {
+                return versionFreeingEnabled;
+        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java
new file mode 100644
index 00000000..8ff3f8e7
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java
@@ -0,0 +1,119 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal.state;
+
+import tools.refinery.store.map.*;
+
+import java.util.*;
+
+public class VersionedMapStoreStateImpl<K, V> implements VersionedMapStore<K, V> {
+        // Configuration
+        private final boolean immutableWhenCommitting;
+
+        // Static data
+        protected final ContinuousHashProvider<K> hashProvider;
+        protected final V defaultValue;
+
+        protected final Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
+
+        public VersionedMapStoreStateImpl(ContinuousHashProvider<K> hashProvider, V defaultValue,
+                                                                          VersionedMapStoreStateConfiguration config) {
+                this.immutableWhenCommitting = config.isImmutableWhenCommitting();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                if (config.isSharedNodeCacheInStore()) {
+                        nodeCache = createNoteCache(config);
+                } else {
+                        nodeCache = null;
+                }
+        }
+
+        private VersionedMapStoreStateImpl(ContinuousHashProvider<K> hashProvider, V defaultValue,
+                                                                           Map<Node<K, V>, ImmutableNode<K, V>> nodeCache, VersionedMapStoreStateConfiguration config) {
+                this.immutableWhenCommitting = config.isImmutableWhenCommitting();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.nodeCache = nodeCache;
+        }
+
+        public VersionedMapStoreStateImpl(ContinuousHashProvider<K> hashProvider, V defaultValue) {
+                this(hashProvider, defaultValue, new VersionedMapStoreStateConfiguration());
+        }
+
+        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
+                                                                                                                                                                          ContinuousHashProvider<K> hashProvider, V defaultValue,
+                                                                                                                                                                          VersionedMapStoreStateConfiguration config) {
+                List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
+                if (config.isSharedNodeCacheInStoreGroups()) {
+                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
+                        if (config.isSharedNodeCacheInStore()) {
+                                nodeCache = createNoteCache(config);
+                        } else {
+                                nodeCache = null;
+                        }
+                        for (int i = 0; i < amount; i++) {
+                                result.add(new VersionedMapStoreStateImpl<>(hashProvider, defaultValue, nodeCache, config));
+                        }
+                } else {
+                        for (int i = 0; i < amount; i++) {
+                                result.add(new VersionedMapStoreStateImpl<>(hashProvider, defaultValue, config));
+                        }
+                }
+                return result;
+        }
+
+        private static <K,V> Map<K,V> createNoteCache(VersionedMapStoreStateConfiguration config) {
+                if(config.isVersionFreeingEnabled()) {
+                        return new WeakHashMap<>();
+                } else {
+                        return new HashMap<>();
+                }
+        }
+
+        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
+                                                                                                                                                                          ContinuousHashProvider<K> hashProvider, V defaultValue) {
+                return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreStateConfiguration());
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap() {
+                return new VersionedMapStateImpl<>(this, hashProvider, defaultValue);
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap(Version state) {
+                ImmutableNode<K, V> data = revert(state);
+                return new VersionedMapStateImpl<>(this, hashProvider, defaultValue, data);
+        }
+
+        @SuppressWarnings("unchecked")
+        public synchronized ImmutableNode<K, V> revert(Version state) {
+                return (ImmutableNode<K, V>) state;
+        }
+
+        public synchronized Version commit(Node<K, V> data, VersionedMapStateImpl<K, V> mapToUpdateRoot) {
+                ImmutableNode<K, V> immutable;
+                if (data != null) {
+                        immutable = data.toImmutable(this.nodeCache);
+                } else {
+                        immutable = null;
+                }
+
+                if (this.immutableWhenCommitting) {
+                        mapToUpdateRoot.setRoot(immutable);
+                }
+                return immutable;
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(Version fromState, Version toState) {
+                VersionedMapStateImpl<K, V> map1 = (VersionedMapStateImpl<K, V>) createMap(fromState);
+                VersionedMapStateImpl<K, V> map2 = (VersionedMapStateImpl<K, V>) createMap(toState);
+                InOrderMapCursor<K, V> cursor1 = new InOrderMapCursor<>(map1);
+                InOrderMapCursor<K, V> cursor2 = new InOrderMapCursor<>(map2);
+                return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2);
+        }
+}
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 ea670cbc..1b15e4cf 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
@@ -7,6 +7,7 @@ package tools.refinery.store.model;
 
 import tools.refinery.store.map.Cursor;
 import tools.refinery.store.map.DiffCursor;
+import tools.refinery.store.map.Version;
 import tools.refinery.store.representation.Symbol;
 import tools.refinery.store.tuple.Tuple;
 
@@ -24,7 +25,7 @@ public non-sealed interface Interpretation<T> extends AnyInterpretation {
 
         void putAll(Cursor<Tuple, T> cursor);
 
-        DiffCursor<Tuple, T> getDiffCursor(long to);
+        DiffCursor<Tuple, T> getDiffCursor(Version to);
 
         void addListener(InterpretationListener<T> listener, boolean alsoWhenRestoring);
 
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/Model.java b/subprojects/store/src/main/java/tools/refinery/store/model/Model.java
index d58d91c3..e2ab72e7 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/Model.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/Model.java
@@ -6,18 +6,20 @@
 package tools.refinery.store.model;
 
 import tools.refinery.store.adapter.ModelAdapter;
+import tools.refinery.store.map.Version;
 import tools.refinery.store.map.Versioned;
+import tools.refinery.store.model.internal.VersionedInterpretation;
 import tools.refinery.store.representation.AnySymbol;
 import tools.refinery.store.representation.Symbol;
 
+import java.util.Map;
 import java.util.Optional;
 
 public interface Model extends Versioned {
-        long NO_STATE_ID = -1;
-
+        Version NO_STATE_ID = null;
         ModelStore getStore();
 
-        long getState();
+        Version getState();
 
         boolean hasUncommittedChanges();
 
@@ -27,7 +29,7 @@ public interface Model extends Versioned {
 
         <T> Interpretation<T> getInterpretation(Symbol<T> symbol);
 
-        ModelDiffCursor getDiffCursor(long to);
+        ModelDiffCursor getDiffCursor(Version to);
 
         <T extends ModelAdapter> Optional<T> tryGetAdapter(Class<? extends T> adapterType);
 
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java
index a9ad8cfd..703ee10a 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java
@@ -5,6 +5,8 @@
  */
 package tools.refinery.store.model;
 
+import tools.refinery.store.map.Version;
+
 public interface ModelListener {
         default void beforeCommit() {
         }
@@ -12,7 +14,7 @@ public interface ModelListener {
         default void afterCommit() {
         }
 
-        default void beforeRestore(long state) {
+        default void beforeRestore(Version state) {
         }
 
         default void afterRestore() {
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java
index b10eb8a4..89382b3a 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java
@@ -6,23 +6,21 @@
 package tools.refinery.store.model;
 
 import tools.refinery.store.adapter.ModelStoreAdapter;
+import tools.refinery.store.map.Version;
 import tools.refinery.store.model.internal.ModelStoreBuilderImpl;
 import tools.refinery.store.representation.AnySymbol;
 
 import java.util.Collection;
 import java.util.Optional;
-import java.util.Set;
 
 public interface ModelStore {
         Collection<AnySymbol> getSymbols();
 
         Model createEmptyModel();
 
-        Model createModelForState(long state);
+        Model createModelForState(Version state);
 
-        Set<Long> getStates();
-
-        ModelDiffCursor getDiffCursor(long from, long to);
+        ModelDiffCursor getDiffCursor(Version from, Version to);
 
         <T extends ModelStoreAdapter> Optional<T> tryGetAdapter(Class<? extends T> adapterType);
 
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java
index fe1c2ab5..3c94541f 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java
@@ -5,41 +5,45 @@
  */
 package tools.refinery.store.model;
 
-import tools.refinery.store.map.ContinousHashProvider;
+import tools.refinery.store.map.ContinuousHashProvider;
 import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple1;
+import tools.refinery.store.tuple.Tuple2;
 
-public class TupleHashProvider implements ContinousHashProvider<Tuple> {
-        protected static final int[] primes = new int[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
-                        103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
-                        223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
-                        347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
-                        463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
-                        607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
-                        743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
-                        883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021,
-                        1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
-                        1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
-                        1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429,
-                        1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549,
-                        1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
-                        1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
-                        1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
-                        1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089,
-                        2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
-                        2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
-                        2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
-                        2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677,
-                        2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
-                        2797, 2801, 2803, 2819, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,
-                        3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
-                        3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517,
-                        3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637,
-                        3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793,
-                        3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911 };
+public class TupleHashProvider implements ContinuousHashProvider<Tuple> {
+        protected static final int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
+                        61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
+                        179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
+                        293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
+                        431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563,
+                        569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683,
+                        691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
+                        839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
+                        991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
+                        1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231,
+                        1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
+                        1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
+                        1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
+                        1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759,
+                        1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907,
+                        1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
+                        2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
+                        2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339,
+                        2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459,
+                        2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
+                        2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
+                        2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169,
+                        3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319,
+                        3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463,
+                        3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593,
+                        3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733,
+                        3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889,
+                        3907, 3911 };
 
-        public static final long LARGEST_PRIME_30_BITS = 1073741789;
-
-        public static final int MAX_MODEL_SIZE = (int) LARGEST_PRIME_30_BITS;
+        protected static final long LARGEST_PRIME_30_BITS_LONG = 1073741789;
+        protected static final int LARGEST_PRIME_30_BITS_INTEGER = 1073741789;
+        protected static final int LARGEST_BINARY_INDEX_1 = LARGEST_PRIME_30_BITS_INTEGER / 4;
+        public static final int MAX_MODEL_SIZE = LARGEST_PRIME_30_BITS_INTEGER;
 
         public static final TupleHashProvider INSTANCE = new TupleHashProvider();
 
@@ -52,15 +56,68 @@ public class TupleHashProvider implements ContinousHashProvider<Tuple> {
 
         @Override
         public int getHash(Tuple key, int index) {
-                if (index >= primes.length) {
-                        throw new IllegalArgumentException("Not enough prime numbers to support index");
+                if(key instanceof Tuple1 t1) {
+                        return t1.value0();
+                } else if(key instanceof Tuple2 t2){
+                        if(index == 0) {
+                                return murmur3T2(t2.value0(), t2.value1());
+                        } else if(index == 1) {
+                                return lagrangeT2I0Quick(t2);
+                        } else if(index == 2) {
+                                return lagrangeT2I1Quick(t2);
+                        } else {
+                                return lagrangeTXIX(key, index-1);
+                        }
+                } else {
+                        return lagrangeTXIX(key, index);
                 }
+
+        }
+
+        private static int lagrangeT2I0Quick(Tuple2 t2) {
+                int result = 2 * t2.value0() + t2.value1();
+                if (result > LARGEST_PRIME_30_BITS_INTEGER) {
+                        return result % LARGEST_PRIME_30_BITS_INTEGER;
+                } else
+                        return result;
+        }
+        private static int lagrangeT2I1Quick(Tuple2 t2) {
+                int value0 = t2.value0();
+                int value1 = t2.value1();
+                if(value0 < LARGEST_BINARY_INDEX_1 && value1 < LARGEST_BINARY_INDEX_1) {
+                        return 3* value0 + value1;
+                } else {
+                        return lagrangeTXIX(t2, 1);
+                }
+        }
+
+        private static int lagrangeTXIX(Tuple key, int index) {
                 long accumulator = 0;
                 final int prime = primes[index];
                 for (int i = 0; i < key.getSize(); i++) {
-                        accumulator = (prime * accumulator + key.get(i)) % MAX_MODEL_SIZE;
+                        accumulator = (prime * accumulator + key.get(i)) % LARGEST_PRIME_30_BITS_LONG;
                 }
 
                 return (int) accumulator;
         }
+
+        private static int murmur3T2(int v0, int v1)
+        {
+                int h = 0;
+
+                h = murmur32Scramble(v0, h);
+                h = murmur32Scramble(v1, h);
+
+                return h;
+        }
+
+        private static int murmur32Scramble(int k, int h) {
+                k *= 0xcc9e2d51;
+                k = (k << 15) | (k >>> 17);
+                k *= 0x1b873593;
+                h ^= k;
+                h = (h << 13) | (h >>> 19);
+                h = h * 5 + 0xe6546b64;
+                return h;
+        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java
deleted file mode 100644
index 14116a90..00000000
--- a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java
+++ /dev/null
@@ -1,34 +0,0 @@
-/*
- * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
- *
- * SPDX-License-Identifier: EPL-2.0
- */
-package tools.refinery.store.model;
-
-import tools.refinery.store.map.ContinousHashProvider;
-import tools.refinery.store.tuple.Tuple;
-
-public class TupleHashProviderBitMagic implements ContinousHashProvider<Tuple> {
-
-        @Override
-        public int getHash(Tuple key, int index) {
-                if(key.getSize() == 1) {
-                        return key.get(0);
-                }
-
-                int result = 0;
-                final int startBitIndex = index*30;
-                final int finalBitIndex = startBitIndex+30;
-                final int arity = key.getSize();
-
-                for(int i = startBitIndex; i<=finalBitIndex; i++) {
-                        final int selectedKey = key.get(i%arity);
-                        final int selectedPosition = 1<<(i/arity);
-                        if((selectedKey&selectedPosition) != 0) {
-                                result |= 1<<(i%30);
-                        }
-                }
-
-                return result;
-        }
-}
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
index e0a371de..0be16f77 100644
--- 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
@@ -7,7 +7,6 @@ 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;
 
@@ -16,9 +15,8 @@ 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);
+        public IndexedVersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) {
+                super(model, symbol, map);
                 indexer = new BaseIndexer<>(symbol.arity(), map);
         }
 
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java
index c5475a1a..2b12d5a6 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java
@@ -8,6 +8,7 @@ package tools.refinery.store.model.internal;
 import tools.refinery.store.adapter.AdapterUtils;
 import tools.refinery.store.adapter.ModelAdapter;
 import tools.refinery.store.map.DiffCursor;
+import tools.refinery.store.map.Version;
 import tools.refinery.store.model.*;
 import tools.refinery.store.representation.AnySymbol;
 import tools.refinery.store.representation.Symbol;
@@ -17,21 +18,21 @@ import java.util.*;
 
 public class ModelImpl implements Model {
         private final ModelStore store;
-        private long state;
-        private Map<? extends AnySymbol, ? extends VersionedInterpretation<?>> interpretations;
+        private Version state;
+        private LinkedHashMap<? extends AnySymbol, ? extends VersionedInterpretation<?>> interpretations;
         private final List<ModelAdapter> adapters;
         private final List<ModelListener> listeners = new ArrayList<>();
         private boolean uncommittedChanges;
         private ModelAction pendingAction = ModelAction.NONE;
-        private long restoringToState = NO_STATE_ID;
+        private Version restoringToState = null;
 
-        ModelImpl(ModelStore store, long state, int adapterCount) {
+        ModelImpl(ModelStore store, Version state, int adapterCount) {
                 this.store = store;
                 this.state = state;
                 adapters = new ArrayList<>(adapterCount);
         }
 
-        void setInterpretations(Map<? extends AnySymbol, ? extends VersionedInterpretation<?>> interpretations) {
+        void setInterpretations(LinkedHashMap<? extends AnySymbol, ? extends VersionedInterpretation<?>> interpretations) {
                 this.interpretations = interpretations;
         }
 
@@ -41,7 +42,7 @@ public class ModelImpl implements Model {
         }
 
         @Override
-        public long getState() {
+        public Version getState() {
                 return state;
         }
 
@@ -57,7 +58,7 @@ public class ModelImpl implements Model {
         }
 
         @Override
-        public ModelDiffCursor getDiffCursor(long to) {
+        public ModelDiffCursor getDiffCursor(Version to) {
                 var diffCursors = new HashMap<AnySymbol, DiffCursor<Tuple, ?>>(interpretations.size());
                 for (var entry : interpretations.entrySet()) {
                         diffCursors.put(entry.getKey(), entry.getValue().getDiffCursor(to));
@@ -65,7 +66,7 @@ public class ModelImpl implements Model {
                 return new ModelDiffCursor(diffCursors);
         }
 
-        private void setState(long state) {
+        private void setState(Version state) {
                 this.state = state;
                 uncommittedChanges = false;
         }
@@ -82,11 +83,11 @@ public class ModelImpl implements Model {
         }
 
         private boolean hasPendingAction() {
-                return pendingAction != ModelAction.NONE || restoringToState != NO_STATE_ID;
+                return pendingAction != ModelAction.NONE || restoringToState != null;
         }
 
         @Override
-        public long commit() {
+        public Version commit() {
                 if (hasPendingAction()) {
                         throw pendingActionError("commit");
                 }
@@ -94,43 +95,40 @@ public class ModelImpl implements Model {
                 try {
                         int listenerCount = listeners.size();
                         int i = listenerCount;
-                        long version = 0;
+
+                        // Before commit message to listeners
                         while (i > 0) {
                                 i--;
                                 listeners.get(i).beforeCommit();
                         }
-                        boolean versionSet = false;
-                        for (var interpretation : interpretations.values()) {
-                                long newVersion = interpretation.commit();
-                                if (versionSet) {
-                                        if (version != newVersion) {
-                                                throw new IllegalStateException("Interpretations in model have different versions (%d and %d)"
-                                                                .formatted(version, newVersion));
-                                        }
-                                } else {
-                                        version = newVersion;
-                                        versionSet = true;
-                                }
+
+                        // Doing the commit on the interpretations
+                        Version[] interpretationVersions = new Version[interpretations.size()];
+                        int j = 0;
+                        for (var interpretationEntry : interpretations.entrySet()) {
+                                interpretationVersions[j++] = interpretationEntry.getValue().commit();
                         }
-                        setState(version);
+                        ModelVersion modelVersion = new ModelVersion(interpretationVersions);
+                        setState(modelVersion);
+
+                        // After commit message to listeners
                         while (i < listenerCount) {
                                 listeners.get(i).afterCommit();
                                 i++;
                         }
-                        return version;
+
+                        return modelVersion;
                 } finally {
                         pendingAction = ModelAction.NONE;
                 }
         }
 
         @Override
-        public void restore(long version) {
+        public void restore(Version version) {
                 if (hasPendingAction()) {
-                        throw pendingActionError("restore to %d".formatted(version));
-                }
-                if (!store.getStates().contains(version)) {
-                        throw new IllegalArgumentException("Store does not contain state %d".formatted(version));
+                        throw pendingActionError("restore to %s".formatted(version));
                 }
+
                 pendingAction = ModelAction.RESTORE;
                 restoringToState = version;
                 try {
@@ -140,9 +138,11 @@ public class ModelImpl implements Model {
                                 i--;
                                 listeners.get(i).beforeRestore(version);
                         }
+                        int j = 0;
                         for (var interpretation : interpretations.values()) {
-                                interpretation.restore(version);
+                                interpretation.restore(ModelVersion.getInternalVersion(version, j++));
                         }
+
                         setState(version);
                         while (i < listenerCount) {
                                 listeners.get(i).afterRestore();
@@ -150,7 +150,7 @@ public class ModelImpl implements Model {
                         }
                 } finally {
                         pendingAction = ModelAction.NONE;
-                        restoringToState = NO_STATE_ID;
+                        restoringToState = null;
                 }
         }
 
@@ -159,7 +159,7 @@ public class ModelImpl implements Model {
                         case NONE -> throw new IllegalArgumentException("Trying to throw pending action error when there is no " +
                                         "pending action");
                         case COMMIT -> "commit";
-                        case RESTORE -> "restore to %d".formatted(restoringToState);
+                        case RESTORE -> "restore to %s".formatted(restoringToState);
                 };
                 return new IllegalStateException("Cannot %s due to pending %s".formatted(currentActionName, pendingActionName));
         }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java
index 5c688178..2dde7a4c 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java
@@ -8,11 +8,11 @@ package tools.refinery.store.model.internal;
 import tools.refinery.store.adapter.AdapterUtils;
 import tools.refinery.store.adapter.ModelAdapterBuilder;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.VersionedMapStoreImpl;
+import tools.refinery.store.map.VersionedMapStoreFactory;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
 import tools.refinery.store.model.ModelStore;
 import tools.refinery.store.model.ModelStoreBuilder;
 import tools.refinery.store.model.ModelStoreConfiguration;
-import tools.refinery.store.model.TupleHashProvider;
 import tools.refinery.store.representation.AnySymbol;
 import tools.refinery.store.representation.Symbol;
 import tools.refinery.store.tuple.Tuple;
@@ -20,8 +20,8 @@ import tools.refinery.store.tuple.Tuple;
 import java.util.*;
 
 public class ModelStoreBuilderImpl implements ModelStoreBuilder {
-        private final Set<AnySymbol> allSymbols = new HashSet<>();
-        private final Map<SymbolEquivalenceClass<?>, List<AnySymbol>> equivalenceClasses = new HashMap<>();
+        private final LinkedHashSet<AnySymbol> allSymbols = new LinkedHashSet<>();
+        private final LinkedHashMap<SymbolEquivalenceClass<?>, List<AnySymbol>> equivalenceClasses = new LinkedHashMap<>();
         private final List<ModelAdapterBuilder> adapters = new ArrayList<>();
 
         @Override
@@ -71,7 +71,7 @@ public class ModelStoreBuilderImpl implements ModelStoreBuilder {
                 for (int i = adapters.size() - 1; i >= 0; i--) {
                         adapters.get(i).configure(this);
                 }
-                var stores = new HashMap<AnySymbol, VersionedMapStore<Tuple, ?>>(allSymbols.size());
+                var stores = new LinkedHashMap<AnySymbol, VersionedMapStore<Tuple, ?>>(allSymbols.size());
                 for (var entry : equivalenceClasses.entrySet()) {
                         createStores(stores, entry.getKey(), entry.getValue());
                 }
@@ -86,8 +86,12 @@ public class ModelStoreBuilderImpl implements ModelStoreBuilder {
         private <T> void createStores(Map<AnySymbol, VersionedMapStore<Tuple, ?>> stores,
                                                                   SymbolEquivalenceClass<T> equivalenceClass, List<AnySymbol> symbols) {
                 int size = symbols.size();
-                var storeGroup = VersionedMapStoreImpl.createSharedVersionedMapStores(size, TupleHashProvider.INSTANCE,
-                                equivalenceClass.defaultValue());
+                VersionedMapStoreFactory<Tuple,T> mapFactory = VersionedMapStore
+                                .<Tuple,T>builder()
+                                .strategy(VersionedMapStoreFactoryBuilder.StoreStrategy.DELTA)
+                                .defaultValue(equivalenceClass.defaultValue())
+                                .build();
+                var storeGroup = mapFactory.createGroup(size);
                 for (int i = 0; i < size; i++) {
                         stores.put(symbols.get(i), storeGroup.get(i));
                 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java
index 60b735e6..a320a618 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java
@@ -8,8 +8,8 @@ package tools.refinery.store.model.internal;
 import tools.refinery.store.adapter.AdapterUtils;
 import tools.refinery.store.adapter.ModelStoreAdapter;
 import tools.refinery.store.map.DiffCursor;
+import tools.refinery.store.map.Version;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.model.Model;
 import tools.refinery.store.model.ModelDiffCursor;
 import tools.refinery.store.model.ModelStore;
 import tools.refinery.store.representation.AnySymbol;
@@ -18,10 +18,10 @@ import tools.refinery.store.tuple.Tuple;
 import java.util.*;
 
 public class ModelStoreImpl implements ModelStore {
-        private final Map<? extends AnySymbol, ? extends VersionedMapStore<Tuple, ?>> stores;
+        private final LinkedHashMap<? extends AnySymbol, ? extends VersionedMapStore<Tuple, ?>> stores;
         private final List<ModelStoreAdapter> adapters;
 
-        ModelStoreImpl(Map<? extends AnySymbol, ? extends VersionedMapStore<Tuple, ?>> stores, int adapterCount) {
+        ModelStoreImpl(LinkedHashMap<? extends AnySymbol, ? extends VersionedMapStore<Tuple, ?>> stores, int adapterCount) {
                 this.stores = stores;
                 adapters = new ArrayList<>(adapterCount);
         }
@@ -31,14 +31,14 @@ public class ModelStoreImpl implements ModelStore {
                 return Collections.unmodifiableCollection(stores.keySet());
         }
 
-        private ModelImpl createModelWithoutInterpretations(long state) {
+        private ModelImpl createModelWithoutInterpretations(Version state) {
                 return new ModelImpl(this, state, adapters.size());
         }
 
         @Override
         public ModelImpl createEmptyModel() {
-                var model = createModelWithoutInterpretations(Model.NO_STATE_ID);
-                var interpretations = new HashMap<AnySymbol, VersionedInterpretation<?>>(stores.size());
+                var model = createModelWithoutInterpretations(null);
+                var interpretations = new LinkedHashMap<AnySymbol, VersionedInterpretation<?>>(stores.size());
                 for (var entry : this.stores.entrySet()) {
                         var symbol = entry.getKey();
                         interpretations.put(symbol, VersionedInterpretation.of(model, symbol, entry.getValue()));
@@ -49,13 +49,21 @@ public class ModelStoreImpl implements ModelStore {
         }
 
         @Override
-        public synchronized ModelImpl createModelForState(long state) {
+        public synchronized ModelImpl createModelForState(Version state) {
                 var model = createModelWithoutInterpretations(state);
-                var interpretations = new HashMap<AnySymbol, VersionedInterpretation<?>>(stores.size());
+                var interpretations = new LinkedHashMap<AnySymbol, VersionedInterpretation<?>>(stores.size());
+
+                int i=0;
                 for (var entry : this.stores.entrySet()) {
                         var symbol = entry.getKey();
-                        interpretations.put(symbol, VersionedInterpretation.of(model, symbol, entry.getValue(), state));
+                        interpretations.put(symbol,
+                                        VersionedInterpretation.of(
+                                                        model,
+                                                        symbol,
+                                                        entry.getValue(),
+                                                        ModelVersion.getInternalVersion(state,i++)));
                 }
+
                 model.setInterpretations(interpretations);
                 adaptModel(model);
                 return model;
@@ -69,16 +77,7 @@ public class ModelStoreImpl implements ModelStore {
         }
 
         @Override
-        public synchronized Set<Long> getStates() {
-                var iterator = stores.values().iterator();
-                if (iterator.hasNext()) {
-                        return Set.copyOf(iterator.next().getStates());
-                }
-                return Set.of(0L);
-        }
-
-        @Override
-        public synchronized ModelDiffCursor getDiffCursor(long from, long to) {
+        public synchronized ModelDiffCursor getDiffCursor(Version from, Version to) {
                 var diffCursors = new HashMap<AnySymbol, DiffCursor<?, ?>>();
                 for (var entry : stores.entrySet()) {
                         var representation = entry.getKey();
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.java
new file mode 100644
index 00000000..c3e52084
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.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.Version;
+
+import java.util.Arrays;
+
+public class ModelVersion implements Version {
+        final Version[] mapVersions;
+
+        public ModelVersion(Version[] mapVersions) {
+                this.mapVersions = mapVersions;
+        }
+
+        public static Version getInternalVersion(Version modelVersion, int interpretationIndex) {
+                return ((ModelVersion) modelVersion).mapVersions[interpretationIndex];
+        }
+
+        @Override
+        public String toString() {
+                return "ModelVersion{" +
+                                "mapVersions=" + Arrays.toString(mapVersions) +
+                                '}';
+        }
+}
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
index 96639a8e..4a8e6752 100644
--- 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
@@ -7,14 +7,12 @@ 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);
+        public NullaryVersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) {
+                super(model, symbol, map);
         }
 
         @Override
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
index 4ec04358..75946680 100644
--- 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
@@ -8,16 +8,14 @@ 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);
+        public UnaryVersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) {
+                super(model, symbol, map);
         }
 
         private void validateSlot(int slot) {
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 877028cc..71df3962 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
@@ -5,15 +5,10 @@
  */
 package tools.refinery.store.model.internal;
 
-import tools.refinery.store.map.Cursor;
-import tools.refinery.store.map.DiffCursor;
-import tools.refinery.store.map.VersionedMap;
-import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.internal.MapDiffCursor;
+import tools.refinery.store.map.*;
 import tools.refinery.store.model.Interpretation;
 import tools.refinery.store.model.InterpretationListener;
 import tools.refinery.store.model.Model;
-import tools.refinery.store.model.TupleHashProvider;
 import tools.refinery.store.representation.AnySymbol;
 import tools.refinery.store.representation.Symbol;
 import tools.refinery.store.tuple.Tuple;
@@ -24,16 +19,13 @@ import java.util.List;
 public abstract class VersionedInterpretation<T> implements Interpretation<T> {
         private final ModelImpl model;
         private final Symbol<T> symbol;
-        private final VersionedMapStore<Tuple, T> store;
         private final VersionedMap<Tuple, T> map;
         private final List<InterpretationListener<T>> listeners = new ArrayList<>();
         private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>();
 
-        protected VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
-                                                                          VersionedMap<Tuple, T> map) {
+        protected VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) {
                 this.model = model;
                 this.symbol = symbol;
-                this.store = store;
                 this.map = map;
         }
 
@@ -116,13 +108,11 @@ public abstract class VersionedInterpretation<T> implements Interpretation<T> {
         }
 
         @Override
-        public DiffCursor<Tuple, T> getDiffCursor(long to) {
-                var fromCursor = getAll();
-                var toCursor = store.createMap(to).getAll();
-                return new MapDiffCursor<>(TupleHashProvider.INSTANCE, symbol.defaultValue(), fromCursor, toCursor);
+        public DiffCursor<Tuple, T> getDiffCursor(Version to) {
+                return map.getDiffCursor(to);
         }
 
-        public long commit() {
+        Version commit() {
                 return map.commit();
         }
 
@@ -130,7 +120,7 @@ public abstract class VersionedInterpretation<T> implements Interpretation<T> {
                 return !restoreListeners.isEmpty();
         }
 
-        public void restore(long state) {
+        public void restore(Version state) {
                 if (shouldNotifyRestoreListeners()) {
                         var diffCursor = getDiffCursor(state);
                         while (diffCursor.move()) {
@@ -158,23 +148,23 @@ public abstract class VersionedInterpretation<T> implements Interpretation<T> {
                 @SuppressWarnings("unchecked")
                 var typedSymbol = (Symbol<T>) symbol;
                 var map = store.createMap();
-                return of(model, typedSymbol, store, map);
+                return of(model, typedSymbol, map);
         }
 
         static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store,
-                                                                                         long state) {
+                                                                                         Version state) {
                 @SuppressWarnings("unchecked")
                 var typedSymbol = (Symbol<T>) symbol;
                 var map = store.createMap(state);
-                return of(model, typedSymbol, store, map);
+                return of(model, typedSymbol, map);
         }
 
         private static <T> VersionedInterpretation<T> of(ModelImpl model, Symbol<T> typedSymbol,
-                                                                                                         VersionedMapStore<Tuple, T> store, VersionedMap<Tuple, T> map) {
+                                                                                                         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);
+                        case 0 -> new NullaryVersionedInterpretation<>(model, typedSymbol, map);
+                        case 1 -> new UnaryVersionedInterpretation<>(model, typedSymbol, map);
+                        default -> new IndexedVersionedInterpretation<>(model, typedSymbol, map);
                 };
         }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/Morphism.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/Morphism.java
new file mode 100644
index 00000000..d4ac3b58
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/Morphism.java
@@ -0,0 +1,11 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+public interface Morphism {
+        int get(int object);
+        int getSize();
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/ObjectCode.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/ObjectCode.java
new file mode 100644
index 00000000..840253ea
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/ObjectCode.java
@@ -0,0 +1,11 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+public interface ObjectCode {
+        long get(int object);
+        int getSize();
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java
new file mode 100644
index 00000000..b7f1d81a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java
@@ -0,0 +1,10 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+public interface StateCodeCalculator {
+        StateCoderResult calculateCodes();
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java
new file mode 100644
index 00000000..04e17a13
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java
@@ -0,0 +1,15 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+import org.eclipse.collections.api.set.primitive.IntSet;
+import tools.refinery.store.model.Interpretation;
+
+import java.util.List;
+
+public interface StateCodeCalculatorFactory {
+        StateCodeCalculator create(List<? extends Interpretation<?>> interpretations, IntSet individuals);
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java
new file mode 100644
index 00000000..cb73d27e
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java
@@ -0,0 +1,23 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+import tools.refinery.store.adapter.ModelAdapter;
+import tools.refinery.store.statecoding.internal.StateCoderBuilderImpl;
+
+public interface StateCoderAdapter extends ModelAdapter {
+        StateCoderResult calculateStateCode();
+        default int calculateModelCode() {
+                return calculateStateCode().modelCode();
+        }
+        default ObjectCode calculateObjectCode() {
+                return calculateStateCode().objectCode();
+        }
+
+        static StateCoderBuilder builder() {
+                return new StateCoderBuilderImpl();
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java
new file mode 100644
index 00000000..54650825
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java
@@ -0,0 +1,45 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+import tools.refinery.store.adapter.ModelAdapterBuilder;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.representation.AnySymbol;
+import tools.refinery.store.tuple.Tuple1;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+
+public interface StateCoderBuilder extends ModelAdapterBuilder {
+        StateCoderBuilder exclude(AnySymbol symbol);
+        default StateCoderBuilder excludeAll(Collection<? extends AnySymbol> symbols) {
+                for(var symbol : symbols) {
+                        exclude(symbol);
+                }
+                return this;
+        }
+        default StateCoderBuilder excludeAll(AnySymbol... symbols) {
+                return excludeAll(List.of(symbols));
+        }
+
+        StateCoderBuilder individual(Tuple1 tuple);
+        default StateCoderBuilder individual(Collection<Tuple1> tuple1s) {
+                for(Tuple1 tuple : tuple1s){
+                        individual(tuple);
+                }
+                return this;
+        }
+        default StateCoderBuilder individuals(Tuple1... tuple1s) {
+                return individual(Arrays.stream(tuple1s).toList());
+        }
+
+        StateCoderBuilder stateCodeCalculatorFactory(StateCodeCalculatorFactory codeCalculatorFactory);
+        StateCoderBuilder stateEquivalenceChecker(StateEquivalenceChecker stateEquivalenceChecker);
+
+        @Override
+        StateCoderStoreAdapter build(ModelStore store);
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderResult.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderResult.java
new file mode 100644
index 00000000..d2aff836
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderResult.java
@@ -0,0 +1,9 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+public record StateCoderResult(int modelCode, ObjectCode objectCode) {
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java
new file mode 100644
index 00000000..c6509521
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java
@@ -0,0 +1,17 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+import tools.refinery.store.adapter.ModelStoreAdapter;
+import tools.refinery.store.map.Version;
+import tools.refinery.store.model.Model;
+
+public interface StateCoderStoreAdapter extends ModelStoreAdapter {
+        StateEquivalenceChecker.EquivalenceResult checkEquivalence(Version v1, Version v2);
+
+        @Override
+        StateCoderAdapter createModelAdapter(Model model);
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java
new file mode 100644
index 00000000..0f0023ed
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java
@@ -0,0 +1,21 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding;
+
+import org.eclipse.collections.api.set.primitive.IntSet;
+import tools.refinery.store.model.AnyInterpretation;
+
+import java.util.List;
+
+public interface StateEquivalenceChecker {
+        enum EquivalenceResult {
+                ISOMORPHIC, UNKNOWN, DIFFERENT
+        }
+
+        EquivalenceResult constructMorphism(
+                        IntSet individuals, List<? extends AnyInterpretation> interpretations1, ObjectCode code1,
+                        List<? extends AnyInterpretation> interpretations2, ObjectCode code2);
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java
new file mode 100644
index 00000000..a2471916
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java
@@ -0,0 +1,39 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.internal;
+
+import tools.refinery.store.adapter.ModelStoreAdapter;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.statecoding.StateCodeCalculator;
+import tools.refinery.store.statecoding.StateCoderAdapter;
+import tools.refinery.store.statecoding.StateCoderResult;
+
+public class StateCoderAdapterImpl implements StateCoderAdapter {
+        final ModelStoreAdapter storeAdapter;
+        final Model model;
+        final StateCodeCalculator calculator;
+
+        StateCoderAdapterImpl(ModelStoreAdapter storeAdapter, StateCodeCalculator calculator,  Model model) {
+                this.storeAdapter = storeAdapter;
+                this.model = model;
+                this.calculator = calculator;
+        }
+
+        @Override
+        public Model getModel() {
+                return model;
+        }
+
+        @Override
+        public ModelStoreAdapter getStoreAdapter() {
+                return storeAdapter;
+        }
+
+        @Override
+        public StateCoderResult calculateStateCode() {
+                return calculator.calculateCodes();
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java
new file mode 100644
index 00000000..eed591e7
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java
@@ -0,0 +1,71 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.internal;
+
+import org.eclipse.collections.api.factory.primitive.IntSets;
+import org.eclipse.collections.api.set.primitive.MutableIntSet;
+import tools.refinery.store.adapter.AbstractModelAdapterBuilder;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.representation.AnySymbol;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.statecoding.StateCodeCalculatorFactory;
+import tools.refinery.store.statecoding.StateCoderBuilder;
+import tools.refinery.store.statecoding.StateCoderStoreAdapter;
+import tools.refinery.store.statecoding.StateEquivalenceChecker;
+import tools.refinery.store.statecoding.neighbourhood.NeighbourhoodCalculator;
+import tools.refinery.store.statecoding.stateequivalence.StateEquivalenceCheckerImpl;
+import tools.refinery.store.tuple.Tuple1;
+
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.Set;
+
+public class StateCoderBuilderImpl extends AbstractModelAdapterBuilder<StateCoderStoreAdapter>
+                implements StateCoderBuilder {
+        private final Set<AnySymbol> excluded = new HashSet<>();
+        private final MutableIntSet individuals = IntSets.mutable.empty();
+        private StateCodeCalculatorFactory calculator = NeighbourhoodCalculator::new;
+        private StateEquivalenceChecker checker = new StateEquivalenceCheckerImpl();
+
+        @Override
+        public StateCoderBuilder exclude(AnySymbol symbol) {
+                checkNotConfigured();
+                excluded.add(symbol);
+                return this;
+        }
+
+        @Override
+        public StateCoderBuilder individual(Tuple1 tuple) {
+                checkNotConfigured();
+                individuals.add(tuple.get(0));
+                return this;
+        }
+
+        @Override
+        public StateCoderBuilder stateEquivalenceChecker(StateEquivalenceChecker stateEquivalenceChecker) {
+                checkNotConfigured();
+                this.checker = stateEquivalenceChecker;
+                return this;
+        }
+
+        @Override
+        public StateCoderBuilder stateCodeCalculatorFactory(StateCodeCalculatorFactory codeCalculatorFactory) {
+                checkNotConfigured();
+                this.calculator = codeCalculatorFactory;
+                return this;
+        }
+
+        @Override
+        protected StateCoderStoreAdapter doBuild(ModelStore store) {
+                Set<Symbol<?>> symbols = new LinkedHashSet<>();
+                for (AnySymbol symbol : store.getSymbols()) {
+                        if (!excluded.contains(symbol) && (symbol instanceof Symbol<?> typed)) {
+                                symbols.add(typed);
+                        }
+                }
+                return new StateCoderStoreAdapterImpl(store, calculator, checker, symbols, individuals);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java
new file mode 100644
index 00000000..89586bfb
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java
@@ -0,0 +1,74 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.internal;
+
+import org.eclipse.collections.api.set.primitive.IntSet;
+import tools.refinery.store.map.Version;
+import tools.refinery.store.model.Model;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.statecoding.StateCodeCalculatorFactory;
+import tools.refinery.store.statecoding.StateCoderAdapter;
+import tools.refinery.store.statecoding.StateCoderStoreAdapter;
+import tools.refinery.store.statecoding.StateEquivalenceChecker;
+
+import java.util.Collection;
+import java.util.Objects;
+
+public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter {
+        final ModelStore store;
+        final Collection<Symbol<?>> symbols;
+        final IntSet individuals;
+
+        final StateEquivalenceChecker equivalenceChecker;
+        final StateCodeCalculatorFactory codeCalculatorFactory;
+
+        StateCoderStoreAdapterImpl(ModelStore store,
+                                                           StateCodeCalculatorFactory codeCalculatorFactory,
+                                                           StateEquivalenceChecker equivalenceChecker,
+                                                           Collection<Symbol<?>> symbols,
+                                                           IntSet individuals)
+        {
+                this.codeCalculatorFactory = codeCalculatorFactory;
+                this.equivalenceChecker = equivalenceChecker;
+                this.store = store;
+                this.symbols = symbols;
+                this.individuals = individuals;
+        }
+
+        @Override
+        public ModelStore getStore() {
+                return store;
+        }
+
+        @Override
+        public StateEquivalenceChecker.EquivalenceResult checkEquivalence(Version v1, Version v2) {
+                if (Objects.equals(v1, v2)) {
+                        return StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC;
+                }
+                var model1 = this.getStore().createModelForState(v1);
+                var model2 = this.getStore().createModelForState(v2);
+
+                var s1 = model1.getAdapter(StateCoderAdapter.class).calculateStateCode();
+                var s2 = model2.getAdapter(StateCoderAdapter.class).calculateStateCode();
+
+                if (s1.modelCode() != s2.modelCode()) {
+                        return StateEquivalenceChecker.EquivalenceResult.DIFFERENT;
+                }
+
+                var i1 = symbols.stream().map(model1::getInterpretation).toList();
+                var i2 = symbols.stream().map(model2::getInterpretation).toList();
+
+                return equivalenceChecker.constructMorphism(individuals, i1, s1.objectCode(), i2, s2.objectCode());
+        }
+
+        @Override
+        public StateCoderAdapter createModelAdapter(Model model) {
+                var interpretations = symbols.stream().map(model::getInterpretation).toList();
+                var coder = codeCalculatorFactory.create(interpretations, individuals);
+                return new StateCoderAdapterImpl(this, coder, model);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java
new file mode 100644
index 00000000..5d390da2
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java
@@ -0,0 +1,96 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.neighbourhood;
+
+import org.eclipse.collections.api.factory.primitive.IntLongMaps;
+import org.eclipse.collections.api.map.primitive.MutableIntLongMap;
+import org.eclipse.collections.api.set.primitive.IntSet;
+import tools.refinery.store.model.AnyInterpretation;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.statecoding.ObjectCode;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple0;
+
+import java.util.*;
+
+public abstract class AbstractNeighbourhoodCalculator {
+        protected final List<AnyInterpretation> nullImpactValues;
+        protected final LinkedHashMap<AnyInterpretation, long[]> impactValues;
+        protected final MutableIntLongMap individualHashValues = IntLongMaps.mutable.empty();
+
+        protected static final long PRIME = 31;
+
+        protected AbstractNeighbourhoodCalculator(List<? extends AnyInterpretation> interpretations, IntSet individuals) {
+                this.nullImpactValues = new ArrayList<>();
+                this.impactValues = new LinkedHashMap<>();
+                // Random isn't used for cryptographical purposes but just to assign distinguishable identifiers to symbols.
+                @SuppressWarnings("squid:S2245")
+                Random random = new Random(1);
+
+                var individualsInOrder = individuals.toSortedList(Integer::compare);
+                for(int i = 0; i<individualsInOrder.size(); i++) {
+                        individualHashValues.put(individualsInOrder.get(i), random.nextLong());
+                }
+
+                for (AnyInterpretation interpretation : interpretations) {
+                        int arity = interpretation.getSymbol().arity();
+                        if (arity == 0) {
+                                nullImpactValues.add(interpretation);
+                        } else {
+                                long[] impact = new long[arity];
+                                for (int i = 0; i < arity; i++) {
+                                        impact[i] = random.nextInt();
+                                }
+                                impactValues.put(interpretation, impact);
+                        }
+                }
+        }
+
+        protected void initializeWithIndividuals(ObjectCodeImpl previous) {
+                for (var entry : individualHashValues.keyValuesView()) {
+                        previous.set(entry.getOne(), entry.getTwo());
+                }
+        }
+
+        protected long getTupleHash1(Tuple tuple, Object value, ObjectCode objectCodeImpl) {
+                long result = Objects.hashCode(value);
+                result = result * PRIME + objectCodeImpl.get(tuple.get(0));
+                return result;
+        }
+
+        protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) {
+                long result = Objects.hashCode(value);
+                result = result * PRIME + objectCodeImpl.get(tuple.get(0));
+                result = result * PRIME + objectCodeImpl.get(tuple.get(1));
+                if (tuple.get(0) == tuple.get(1)) {
+                        result += PRIME;
+                        result *= PRIME;
+                }
+                return result;
+        }
+
+        protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) {
+                long result = Objects.hashCode(value);
+                for (int i = 0; i < tuple.getSize(); i++) {
+                        result = result * PRIME + objectCodeImpl.get(tuple.get(i));
+                }
+                return result;
+        }
+
+        protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) {
+                long x = tupleHash * impact;
+                objectCodeImpl.set(o, objectCodeImpl.get(o) + x);
+        }
+
+        protected long calculateModelCode(long lastSum) {
+                long result = 0;
+                for (var nullImpactValue : nullImpactValues) {
+                        result = result * PRIME + Objects.hashCode(((Interpretation<?>) nullImpactValue).get(Tuple0.INSTANCE));
+                }
+                result += lastSum;
+                return result;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java
new file mode 100644
index 00000000..c188a839
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java
@@ -0,0 +1,193 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.neighbourhood;
+
+import org.eclipse.collections.api.factory.primitive.LongIntMaps;
+import org.eclipse.collections.api.map.primitive.LongIntMap;
+import org.eclipse.collections.api.map.primitive.MutableLongIntMap;
+import org.eclipse.collections.api.set.primitive.IntSet;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.model.AnyInterpretation;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.statecoding.StateCodeCalculator;
+import tools.refinery.store.statecoding.StateCoderResult;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.List;
+
+public class LazyNeighbourhoodCalculator extends AbstractNeighbourhoodCalculator implements StateCodeCalculator {
+        public LazyNeighbourhoodCalculator(List<? extends AnyInterpretation> interpretations, IntSet individuals) {
+                super(interpretations, individuals);
+        }
+
+        public StateCoderResult calculateCodes() {
+                ObjectCodeImpl previousObjectCode = new ObjectCodeImpl();
+                MutableLongIntMap prevHash2Amount = LongIntMaps.mutable.empty();
+
+                long lastSum;
+                // All hash code is 0, except to the individuals.
+                int lastSize = 1;
+                boolean first = true;
+
+                boolean grows;
+                int rounds = 0;
+                do {
+                        final ObjectCodeImpl nextObjectCode;
+                        if (first) {
+                                nextObjectCode = new ObjectCodeImpl();
+                                initializeWithIndividuals(nextObjectCode);
+                        } else {
+                                nextObjectCode = new ObjectCodeImpl(previousObjectCode);
+                        }
+                        constructNextObjectCodes(previousObjectCode, nextObjectCode, prevHash2Amount);
+
+                        MutableLongIntMap nextHash2Amount = LongIntMaps.mutable.empty();
+                        lastSum = calculateLastSum(previousObjectCode, nextObjectCode, prevHash2Amount, nextHash2Amount);
+
+                        int nextSize = nextHash2Amount.size();
+                        grows = nextSize > lastSize;
+                        lastSize = nextSize;
+                        first = false;
+
+                        previousObjectCode = nextObjectCode;
+                        prevHash2Amount = nextHash2Amount;
+                } while (grows && rounds++ < 4/*&& lastSize < previousObjectCode.getSize()*/);
+
+                long result = calculateModelCode(lastSum);
+
+                return new StateCoderResult((int) result, previousObjectCode);
+        }
+
+        private long calculateLastSum(ObjectCodeImpl previous, ObjectCodeImpl next, LongIntMap hash2Amount,
+                                                                  MutableLongIntMap nextHash2Amount) {
+                long lastSum = 0;
+                for (int i = 0; i < next.getSize(); i++) {
+                        final long hash;
+                        if (isUnique(hash2Amount, previous, i)) {
+                                hash = previous.get(i);
+                                next.set(i, hash);
+                        } else {
+                                hash = next.get(i);
+                        }
+
+                        final int amount = nextHash2Amount.get(hash);
+                        nextHash2Amount.put(hash, amount + 1);
+
+                        final long shifted1 = hash >>> 8;
+                        final long shifted2 = hash << 8;
+                        final long shifted3 = hash >> 2;
+                        lastSum += shifted1 * shifted3 + shifted2;
+                }
+                return lastSum;
+        }
+
+        private void constructNextObjectCodes(ObjectCodeImpl previous, ObjectCodeImpl next, LongIntMap hash2Amount) {
+                for (var impactValueEntry : this.impactValues.entrySet()) {
+                        Interpretation<?> interpretation = (Interpretation<?>) impactValueEntry.getKey();
+                        var cursor = interpretation.getAll();
+                        int arity = interpretation.getSymbol().arity();
+                        long[] impactValue = impactValueEntry.getValue();
+
+                        if (arity == 1) {
+                                while (cursor.move()) {
+                                        lazyImpactCalculation1(hash2Amount, previous, next, impactValue, cursor);
+                                }
+                        } else if (arity == 2) {
+                                while (cursor.move()) {
+                                        lazyImpactCalculation2(hash2Amount, previous, next, impactValue, cursor);
+                                }
+                        } else {
+                                while (cursor.move()) {
+                                        lazyImpactCalculationN(hash2Amount, previous, next, impactValue, cursor);
+                                }
+                        }
+                }
+        }
+
+        private boolean isUnique(LongIntMap hash2Amount, ObjectCodeImpl objectCodeImpl, int object) {
+                final long hash = objectCodeImpl.get(object);
+                if (hash == 0) {
+                        return false;
+                }
+                final int amount = hash2Amount.get(hash);
+                return amount == 1;
+        }
+
+        private void lazyImpactCalculation1(LongIntMap hash2Amount, ObjectCodeImpl previous, ObjectCodeImpl next,
+                                                                                long[] impactValues, Cursor<Tuple, ?> cursor) {
+
+                Tuple tuple = cursor.getKey();
+                int o = tuple.get(0);
+
+                if (isUnique(hash2Amount, previous, o)) {
+                        next.ensureSize(o);
+                } else {
+                        Object value = cursor.getValue();
+                        long tupleHash = getTupleHash1(tuple, value, previous);
+
+                        addHash(next, o, impactValues[0], tupleHash);
+                }
+        }
+
+        private void lazyImpactCalculation2(LongIntMap hash2Amount, ObjectCodeImpl previous, ObjectCodeImpl next,
+                                                                                long[] impactValues, Cursor<Tuple, ?> cursor) {
+                final Tuple tuple = cursor.getKey();
+                final int o1 = tuple.get(0);
+                final int o2 = tuple.get(1);
+
+                final boolean u1 = isUnique(hash2Amount, previous, o1);
+                final boolean u2 = isUnique(hash2Amount, previous, o2);
+
+                if (u1 && u2) {
+                        next.ensureSize(o1);
+                        next.ensureSize(o2);
+                } else {
+                        Object value = cursor.getValue();
+                        long tupleHash = getTupleHash2(tuple, value, previous);
+
+                        if (!u1) {
+                                addHash(next, o1, impactValues[0], tupleHash);
+                                next.ensureSize(o2);
+                        }
+                        if (!u2) {
+                                next.ensureSize(o1);
+                                addHash(next, o2, impactValues[1], tupleHash);
+                        }
+                }
+        }
+
+        private void lazyImpactCalculationN(LongIntMap hash2Amount, ObjectCodeImpl previous, ObjectCodeImpl next,
+                                                                                long[] impactValues, Cursor<Tuple, ?> cursor) {
+                final Tuple tuple = cursor.getKey();
+
+                final boolean[] uniques = new boolean[tuple.getSize()];
+                boolean allUnique = true;
+                for (int i = 0; i < tuple.getSize(); i++) {
+                        final boolean isUnique = isUnique(hash2Amount, previous, tuple.get(i));
+                        uniques[i] = isUnique;
+                        allUnique &= isUnique;
+                }
+
+                if (allUnique) {
+                        for (int i = 0; i < tuple.getSize(); i++) {
+                                next.ensureSize(tuple.get(i));
+                        }
+                } else {
+                        Object value = cursor.getValue();
+                        long tupleHash = getTupleHashN(tuple, value, previous);
+
+                        for (int i = 0; i < tuple.getSize(); i++) {
+                                int o = tuple.get(i);
+                                if (!uniques[i]) {
+                                        addHash(next, o, impactValues[i], tupleHash);
+                                } else {
+                                        next.ensureSize(o);
+                                }
+                        }
+                }
+        }
+
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java
new file mode 100644
index 00000000..785fda7a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java
@@ -0,0 +1,115 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.neighbourhood;
+
+import org.eclipse.collections.api.set.primitive.IntSet;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.statecoding.ObjectCode;
+import tools.refinery.store.statecoding.StateCodeCalculator;
+import tools.refinery.store.statecoding.StateCoderResult;
+import tools.refinery.store.tuple.Tuple;
+import tools.refinery.store.tuple.Tuple0;
+
+import java.util.List;
+import java.util.Objects;
+
+public class NeighbourhoodCalculator extends AbstractNeighbourhoodCalculator implements StateCodeCalculator {
+        public NeighbourhoodCalculator(List<? extends Interpretation<?>> interpretations, IntSet individuals) {
+                super(interpretations, individuals);
+        }
+
+        public StateCoderResult calculateCodes() {
+                ObjectCodeImpl previousObjectCode = new ObjectCodeImpl();
+                initializeWithIndividuals(previousObjectCode);
+
+                int rounds = 0;
+                do {
+                        final ObjectCodeImpl nextObjectCode = rounds == 0 ? new ObjectCodeImpl() :
+                                        new ObjectCodeImpl(previousObjectCode.getSize());
+
+                        constructNextObjectCodes(previousObjectCode, nextObjectCode);
+                        previousObjectCode = nextObjectCode;
+                        rounds++;
+                } while (rounds <= 7 && rounds <= previousObjectCode.getEffectiveSize());
+
+                long result = calculateLastSum(previousObjectCode);
+                return new StateCoderResult((int) result, previousObjectCode);
+        }
+
+        private long calculateLastSum(ObjectCode codes) {
+                long result = 0;
+                for (var nullImpactValue : nullImpactValues) {
+                        result = result * 31 + Objects.hashCode(((Interpretation<?>) nullImpactValue).get(Tuple0.INSTANCE));
+                }
+
+                for (int i = 0; i < codes.getSize(); i++) {
+                        final long hash = codes.get(i);
+                        result += hash*PRIME;
+                }
+
+                return result;
+        }
+
+        private void constructNextObjectCodes(ObjectCodeImpl previous, ObjectCodeImpl next) {
+                for (var impactValueEntry : this.impactValues.entrySet()) {
+                        Interpretation<?> interpretation = (Interpretation<?>) impactValueEntry.getKey();
+                        var cursor = interpretation.getAll();
+                        int arity = interpretation.getSymbol().arity();
+                        long[] impactValue = impactValueEntry.getValue();
+
+                        if (arity == 1) {
+                                while (cursor.move()) {
+                                        impactCalculation1(previous, next, impactValue, cursor);
+                                }
+                        } else if (arity == 2) {
+                                while (cursor.move()) {
+                                        impactCalculation2(previous, next, impactValue, cursor);
+                                }
+                        } else {
+                                while (cursor.move()) {
+                                        impactCalculationN(previous, next, impactValue, cursor);
+                                }
+                        }
+                }
+        }
+
+
+        private void impactCalculation1(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues,
+                                                                        Cursor<Tuple, ?> cursor) {
+
+                Tuple tuple = cursor.getKey();
+                int o = tuple.get(0);
+                Object value = cursor.getValue();
+                long tupleHash = getTupleHash1(tuple, value, previous);
+                addHash(next, o, impactValues[0], tupleHash);
+        }
+
+        private void impactCalculation2(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues,
+                                                                        Cursor<Tuple, ?> cursor) {
+                final Tuple tuple = cursor.getKey();
+                final int o1 = tuple.get(0);
+                final int o2 = tuple.get(1);
+
+                Object value = cursor.getValue();
+                long tupleHash = getTupleHash2(tuple, value, previous);
+
+                addHash(next, o1, impactValues[0], tupleHash);
+                addHash(next, o2, impactValues[1], tupleHash);
+        }
+
+        private void impactCalculationN(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues,
+                                                                        Cursor<Tuple, ?> cursor) {
+                final Tuple tuple = cursor.getKey();
+
+                Object value = cursor.getValue();
+                long tupleHash = getTupleHashN(tuple, value, previous);
+
+                for (int i = 0; i < tuple.getSize(); i++) {
+                        addHash(next, tuple.get(i), impactValues[i], tupleHash);
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java
new file mode 100644
index 00000000..0cd7ff58
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java
@@ -0,0 +1,81 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.neighbourhood;
+
+import tools.refinery.store.statecoding.ObjectCode;
+
+import java.util.Arrays;
+
+public class ObjectCodeImpl implements ObjectCode {
+        private long[] vector;
+        private int size;
+        private int effectiveSize;
+
+        public ObjectCodeImpl() {
+                vector = new long[10];
+                size = 0;
+                effectiveSize = 0;
+        }
+
+        public ObjectCodeImpl(int size) {
+                this.vector = new long[size];
+                this.size = size;
+                effectiveSize = 0;
+        }
+
+        public ObjectCodeImpl(ObjectCodeImpl copy) {
+                this.vector = Arrays.copyOf(copy.vector, copy.size);
+                this.size = copy.size;
+                effectiveSize = copy.effectiveSize;
+        }
+
+        public void ensureSize(int object) {
+                if (object >= size) {
+                        size = object + 1;
+                }
+
+                if (object >= vector.length) {
+                        int newLength = vector.length * 2;
+                        while (object >= newLength) {
+                                newLength *= 2;
+                        }
+
+                        long[] newVector = new long[newLength];
+                        System.arraycopy(vector, 0, newVector, 0, vector.length);
+                        this.vector = newVector;
+                }
+        }
+
+        public long get(int object) {
+                if (object < vector.length) {
+                        return vector[object];
+                } else {
+                        return 0;
+                }
+        }
+
+        public void set(int object, long value) {
+                ensureSize(object);
+                final long valueToPut = value == 0 ? 1 : value;
+                if (vector[object] == 0) effectiveSize++;
+                vector[object] = valueToPut;
+        }
+
+        public int getSize() {
+                return this.size;
+        }
+
+        public int getEffectiveSize() {
+                return this.effectiveSize;
+        }
+
+        @Override
+        public String toString() {
+                return "ObjectCodeImpl{" +
+                                "vector=" + Arrays.toString(Arrays.copyOf(vector, this.size)) +
+                                '}';
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/CombinationNodePairing.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/CombinationNodePairing.java
new file mode 100644
index 00000000..0682e1a4
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/CombinationNodePairing.java
@@ -0,0 +1,89 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.stateequivalence;
+
+import org.eclipse.collections.api.factory.primitive.IntIntMaps;
+import org.eclipse.collections.api.map.primitive.IntIntMap;
+import org.eclipse.collections.api.set.primitive.IntSet;
+
+import java.util.*;
+
+public class CombinationNodePairing implements NodePairing {
+        private final int[] left;
+        private final int[] right;
+
+        CombinationNodePairing(IntSet left, IntSet right) {
+                this.left = left.toArray();
+                this.right = right.toArray();
+
+                Arrays.sort(this.left);
+                Arrays.sort(this.right);
+        }
+
+        @Override
+        public int size() {
+                return left.length;
+        }
+
+        private static final int LIMIT = 5;
+        // Enum-based singleton used to delay generating all permutations until they are first needed.
+        @SuppressWarnings("squid:S6548")
+        private enum PermutationsHolder {
+                INSTANCE;
+
+                final CombinationNodePairingPermutations permutations = new CombinationNodePairingPermutations(LIMIT);
+        }
+
+        @Override
+        public List<IntIntMap> permutations() {
+                int limit = this.size();
+                Iterable<Integer> interval = () -> new IntervalIterator(limit);
+
+                if (isComplete()) {
+                        final List<int[]> p = PermutationsHolder.INSTANCE.permutations.getPermutations(this.size() - 1);
+                        return p.stream().map(x -> constructPermutationMap(interval, x)).toList();
+                } else {
+                        return List.of(constructTrivialMap(interval));
+                }
+        }
+
+        private IntIntMap constructTrivialMap(Iterable<Integer> interval) {
+                return IntIntMaps.immutable.from(interval, l -> left[l], r -> right[r]);
+        }
+
+        private IntIntMap constructPermutationMap(Iterable<Integer> interval, int[] permutation) {
+                return IntIntMaps.immutable.from(interval, l -> left[l], r -> right[permutation[r]]);
+        }
+
+        @Override
+        public boolean isComplete() {
+                return this.size() <= LIMIT;
+        }
+
+        private static class IntervalIterator implements Iterator<Integer> {
+                private final int limit;
+                private int value = 0;
+
+                private IntervalIterator(int max) {
+                        this.limit = max;
+                }
+
+                @Override
+                public boolean hasNext() {
+                        return value < limit;
+                }
+
+                @Override
+                public Integer next() {
+                        if (value >= limit) {
+                                throw new NoSuchElementException("End of interval");
+                        }
+                        int next = value;
+                        value++;
+                        return next;
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/CombinationNodePairingPermutations.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/CombinationNodePairingPermutations.java
new file mode 100644
index 00000000..eacd3a2a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/CombinationNodePairingPermutations.java
@@ -0,0 +1,57 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.stateequivalence;
+
+import java.util.ArrayList;
+import java.util.List;
+
+class CombinationNodePairingPermutations {
+        private final List<List<int[]>> permutations = new ArrayList<>();
+
+        public CombinationNodePairingPermutations(int max) {
+                initializePermutations(max);
+        }
+
+        public List<int[]> getPermutations(int max) {
+                if (max >= permutations.size()) {
+                        throw new IllegalArgumentException("Only permutations up to %d elements are supported".formatted(max));
+                }
+                return permutations.get(max);
+        }
+
+        /**
+         * Generates and stores permutations up to a given size. If the number would be more than a limit, it provides a
+         * single permutation only.
+         *
+         * @param max The max number in the permutation
+         * @return A complete list of permutations of numbers 0...max, or a single permutation.
+         */
+        private List<int[]> initializePermutations(int max) {
+                if (max < permutations.size()) {
+                        return permutations.get(max);
+                }
+                if (max == 0) {
+                        List<int[]> result = new ArrayList<>();
+                        result.add(new int[1]);
+                        permutations.add(result);
+                        return result;
+                }
+                List<int[]> result = new ArrayList<>();
+                List<int[]> previousPermutations = initializePermutations(max - 1);
+                for (var permutation : previousPermutations) {
+                        for (int pos = 0; pos <= max; pos++) {
+                                int[] newPermutation = new int[max + 1];
+                                System.arraycopy(permutation, 0, newPermutation, 0, pos);
+                                newPermutation[pos] = max;
+                                if (max - (pos + 1) >= 0)
+                                        System.arraycopy(permutation, pos + 1, newPermutation, pos + 1 + 1, max - (pos + 1));
+                                result.add(newPermutation);
+                        }
+                }
+                permutations.add(result);
+                return result;
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/NodePairing.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/NodePairing.java
new file mode 100644
index 00000000..f45f0d2e
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/NodePairing.java
@@ -0,0 +1,33 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.stateequivalence;
+
+import org.eclipse.collections.api.map.primitive.IntIntMap;
+import org.eclipse.collections.api.set.primitive.IntSet;
+
+import java.util.List;
+
+public interface NodePairing {
+        int size();
+
+        List<IntIntMap> permutations();
+
+        boolean isComplete();
+
+        static NodePairing constructNodePairing(IntSet left, IntSet right){
+                if(left.size() !=  right.size()) {
+                        return null;
+                }
+
+                if(left.size() == 1) {
+                        int leftValue = left.intIterator().next();
+                        int rightValue = right.intIterator().next();
+                        return new TrivialNodePairing(leftValue, rightValue);
+                } else {
+                        return new CombinationNodePairing(left,right);
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/PermutationMorphism.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/PermutationMorphism.java
new file mode 100644
index 00000000..bc4d723a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/PermutationMorphism.java
@@ -0,0 +1,64 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.stateequivalence;
+
+import org.eclipse.collections.api.map.primitive.IntIntMap;
+import tools.refinery.store.statecoding.Morphism;
+
+import java.util.List;
+
+public class PermutationMorphism implements Morphism {
+        private final IntIntMap object2PermutationGroup;
+        private final List<? extends List<? extends IntIntMap>> permutationsGroups;
+        private final int[] selection;
+        private boolean hasNext;
+
+        PermutationMorphism(IntIntMap object2PermutationGroup,
+                                                List<? extends List<? extends IntIntMap>> permutationsGroups) {
+                this.object2PermutationGroup = object2PermutationGroup;
+                this.permutationsGroups = permutationsGroups;
+
+                this.selection = new int[this.permutationsGroups.size()];
+                this.hasNext = true;
+        }
+
+        public boolean next() {
+                return next(0);
+        }
+
+        private boolean next(int position) {
+                if (position >= permutationsGroups.size()) {
+                        this.hasNext = false;
+                        return false;
+                }
+                if (selection[position] + 1 < permutationsGroups.get(position).size()) {
+                        selection[position] = selection[position] + 1;
+                        return true;
+                } else {
+                        selection[position] = 0;
+                        return next(position + 1);
+                }
+        }
+
+        @Override
+        public int get(int object) {
+                if(!hasNext) {
+                        throw new IllegalArgumentException("No next permutation!");
+                }
+
+                final int groupIndex = object2PermutationGroup.get(object);
+                final var selectedGroup = permutationsGroups.get(groupIndex);
+                final int permutationIndex = selection[groupIndex];
+                final var selectedPermutation = selectedGroup.get(permutationIndex);
+
+                return selectedPermutation.get(object);
+        }
+
+        @Override
+        public int getSize() {
+                return object2PermutationGroup.size();
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java
new file mode 100644
index 00000000..5a62d8a0
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java
@@ -0,0 +1,166 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.stateequivalence;
+
+import org.eclipse.collections.api.factory.primitive.IntIntMaps;
+import org.eclipse.collections.api.factory.primitive.IntSets;
+import org.eclipse.collections.api.factory.primitive.LongObjectMaps;
+import org.eclipse.collections.api.map.primitive.IntIntMap;
+import org.eclipse.collections.api.map.primitive.MutableIntIntMap;
+import org.eclipse.collections.api.map.primitive.MutableLongObjectMap;
+import org.eclipse.collections.api.set.primitive.IntSet;
+import org.eclipse.collections.api.set.primitive.MutableIntSet;
+import tools.refinery.store.model.AnyInterpretation;
+import tools.refinery.store.model.Interpretation;
+import tools.refinery.store.statecoding.Morphism;
+import tools.refinery.store.statecoding.ObjectCode;
+import tools.refinery.store.statecoding.StateEquivalenceChecker;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+
+public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker {
+        public static final int LIMIT = 1000;
+
+        @Override
+        public EquivalenceResult constructMorphism(IntSet individuals,
+                                                                                           List<? extends AnyInterpretation> interpretations1,
+                                                                                           ObjectCode code1,
+                                                                                           List<? extends AnyInterpretation> interpretations2,
+                                                                                           ObjectCode code2) {
+                MutableIntIntMap object2PermutationGroup = IntIntMaps.mutable.empty();
+                List<List<IntIntMap>> permutationsGroups = new ArrayList<>();
+
+                final EquivalenceResult permutations = constructPermutationNavigation(individuals,
+                                indexByHash(code1, individuals), indexByHash(code2, individuals),
+                                object2PermutationGroup, permutationsGroups);
+
+                if (permutations == EquivalenceResult.DIFFERENT) {
+                        return EquivalenceResult.DIFFERENT;
+                }
+
+                boolean hasNext;
+                PermutationMorphism morphism = new PermutationMorphism(object2PermutationGroup, permutationsGroups);
+                int tried = 0;
+                do {
+                        if (testMorphism(interpretations1, interpretations2, morphism)) {
+                                return permutations;
+                        }
+
+                        if (tried >= LIMIT) {
+                                return EquivalenceResult.UNKNOWN;
+                        }
+
+                        hasNext = morphism.next();
+                        tried++;
+                } while (hasNext);
+
+                if (permutations == EquivalenceResult.UNKNOWN) {
+                        return EquivalenceResult.UNKNOWN;
+                } else {
+                        return EquivalenceResult.DIFFERENT;
+                }
+        }
+
+        private MutableLongObjectMap<MutableIntSet> indexByHash(ObjectCode code, IntSet individuals) {
+                MutableLongObjectMap<MutableIntSet> result = LongObjectMaps.mutable.empty();
+                for (int o = 0; o < code.getSize(); o++) {
+                        if (!individuals.contains(o)) {
+                                long hash = code.get(o);
+                                if (hash != 0) {
+                                        var equivalenceClass = result.get(hash);
+                                        if (equivalenceClass == null) {
+                                                equivalenceClass = IntSets.mutable.empty();
+                                                result.put(hash, equivalenceClass);
+                                        }
+                                        equivalenceClass.add(o);
+                                }
+                        }
+                }
+                return result;
+        }
+
+        private EquivalenceResult constructPermutationNavigation(
+                        IntSet individuals, MutableLongObjectMap<MutableIntSet> map1, MutableLongObjectMap<MutableIntSet> map2,
+                        MutableIntIntMap object2OptionIndex, List<List<IntIntMap>> listOfOptions) {
+                if (map1.size() != map2.size()) {
+                        return EquivalenceResult.DIFFERENT;
+                }
+
+                var iterator = map1.keySet().longIterator();
+
+                boolean allComplete = true;
+
+                while (iterator.hasNext()) {
+                        long hash = iterator.next();
+                        var set1 = map1.get(hash);
+                        var set2 = map2.get(hash);
+                        if (set2 == null) {
+                                return EquivalenceResult.DIFFERENT;
+                        }
+
+                        var pairing = NodePairing.constructNodePairing(set1, set2);
+                        if (pairing == null) {
+                                return EquivalenceResult.DIFFERENT;
+                        }
+
+                        allComplete &= pairing.isComplete();
+
+                        final int optionIndex = listOfOptions.size();
+                        set1.forEach(key -> object2OptionIndex.put(key, optionIndex));
+                        listOfOptions.add(pairing.permutations());
+                }
+
+                individuals.forEach(o -> listOfOptions.add(o, List.of(IntIntMaps.immutable.of(o, o))));
+
+                if (allComplete) {
+                        return EquivalenceResult.ISOMORPHIC;
+                } else {
+                        return EquivalenceResult.UNKNOWN;
+                }
+        }
+
+        private boolean testMorphism(List<? extends AnyInterpretation> s, List<? extends AnyInterpretation> t,
+                                                                 Morphism m) {
+                for (int interpretationIndex = 0; interpretationIndex < s.size(); interpretationIndex++) {
+                        var sI = s.get(interpretationIndex);
+                        var tI = t.get(interpretationIndex);
+
+                        var cursor = ((Interpretation<?>) sI).getAll();
+                        while (cursor.move()) {
+                                final Tuple sTuple = cursor.getKey();
+                                final Object sValue = cursor.getValue();
+
+                                final Tuple tTuple = apply(sTuple, m);
+                                final Object tValue = ((Interpretation<?>) tI).get(tTuple);
+
+                                if (!Objects.equals(sValue, tValue)) {
+                                        return false;
+                                }
+                        }
+                }
+                return true;
+        }
+
+        private Tuple apply(Tuple t, Morphism m) {
+                final int arity = t.getSize();
+                if (arity == 0) {
+                        return Tuple.of();
+                } else if (arity == 1) {
+                        return Tuple.of(m.get(t.get(0)));
+                } else if (arity == 2) {
+                        return Tuple.of(m.get(t.get(0)), m.get(t.get(1)));
+                } else {
+                        int[] newTupleIndices = new int[arity];
+                        for (int i = 0; i < arity; i++) {
+                                newTupleIndices[i] = m.get(t.get(i));
+                        }
+                        return Tuple.of(newTupleIndices);
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/TrivialNodePairing.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/TrivialNodePairing.java
new file mode 100644
index 00000000..f5eadfb9
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/TrivialNodePairing.java
@@ -0,0 +1,36 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.statecoding.stateequivalence;
+
+import org.eclipse.collections.api.factory.primitive.IntIntMaps;
+import org.eclipse.collections.api.map.primitive.IntIntMap;
+
+import java.util.List;
+
+public class TrivialNodePairing implements NodePairing {
+        final int left;
+        final int right;
+
+        TrivialNodePairing(int left, int right) {
+                this.left = left;
+                this.right = right;
+        }
+
+        @Override
+        public int size() {
+                return 1;
+        }
+
+        @Override
+        public List<IntIntMap> permutations() {
+                return List.of(IntIntMaps.immutable.of(left,right));
+        }
+
+        @Override
+        public boolean isComplete() {
+                return true;
+        }
+}