Merge pull request #30 from OszkarSemerath/datastructure

Datastructure

46 files changed, 2351 insertions, 815 deletions

diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java
index 66f043c6..32f51cf0 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTransactionTest.java
@@ -6,7 +6,6 @@
 package tools.refinery.store.query.viatra;
 
 import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
-import org.junit.jupiter.api.Disabled;
 import org.junit.jupiter.api.Test;
 import tools.refinery.store.model.ModelStore;
 import tools.refinery.store.query.ModelQueryAdapter;
@@ -283,7 +282,6 @@ class QueryTransactionTest {
                 assertResults(Map.of(Tuple.of(0), false), queryResultSet);
         }
 
-        @Disabled("TODO Fix DiffCursor")
         @Test
         void commitAfterFlushTest() {
                 var store = ModelStore.builder()
@@ -332,7 +330,6 @@ class QueryTransactionTest {
                 ), predicateResultSet);
         }
 
-        @Disabled("TODO Fix DiffCursor")
         @Test
         void commitWithoutFlushTest() {
                 var store = ModelStore.builder()
diff --git a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java
index edd4f53e..7e89cd06 100644
--- a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java
+++ b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java
@@ -40,7 +40,7 @@ public class ImmutablePutExecutionPlan {
         @Setup(Level.Trial)
         public void setUpTrial() {
                 random = new Random();
-                values = MapTestEnvironment.prepareValues(nValues);
+                values = MapTestEnvironment.prepareValues(nValues, true);
         }
 
         public VersionedMapImpl<Integer, String> createSut() {
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/VersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java
index 9bbde24d..c8226c3e 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();
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..b24c404c 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,21 @@
  */
 package tools.refinery.store.map;
 
+import tools.refinery.store.map.internal.VersionedMapStoreFactoryBuilderImpl;
+
 import java.util.Set;
 
 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();
+
+        VersionedMap<K, V> createMap(long state);
+
+        Set<Long> getStates();
+
+        DiffCursor<K,V> getDiffCursor(long fromState, long toState);
 
-        public DiffCursor<K,V> getDiffCursor(long fromState, long toState);
-}
\ No newline at end of file
+        static <K,V> VersionedMapStoreFactoryBuilder<K,V> builder() {
+                return new VersionedMapStoreFactoryBuilderImpl<>();
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java
new file mode 100644
index 00000000..0c61bd09
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java
@@ -0,0 +1,99 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map;
+
+import java.util.*;
+
+import tools.refinery.store.map.internal.*;
+
+public class VersionedMapStoreDeltaImpl<K, V> implements VersionedMapStore<K, V> {
+        // Configuration
+        protected final boolean summarizeChanges;
+
+        // Static data
+        protected final V defaultValue;
+
+        // Dynamic data
+        protected final Map<Long, MapTransaction<K, V>> states = new HashMap<>();
+        protected long nextID = 0;
+
+        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(long state) {
+                VersionedMapDeltaImpl<K, V> result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue);
+                result.restore(state);
+                return result;
+        }
+
+        public synchronized MapTransaction<K, V> appendTransaction(MapDelta<K, V>[] deltas, MapTransaction<K, V> previous, long[] versionContainer) {
+                long version = nextID++;
+                versionContainer[0] = version;
+                if (deltas == null) {
+                        states.put(version, previous);
+                        return previous;
+                } else {
+                        MapTransaction<K, V> transaction = new MapTransaction<>(deltas, version, previous);
+                        states.put(version, transaction);
+                        return transaction;
+                }
+        }
+
+        private synchronized MapTransaction<K, V> getState(long state) {
+                return states.get(state);
+        }
+
+        public MapTransaction<K, V> getPath(long 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(long from, long 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.version() < toTransaction.version())) {
+                                forwardTransactions.add(toTransaction.deltas());
+                                toTransaction = toTransaction.parent();
+                        } else {
+                                backwardTransactions.add(fromTransaction.deltas());
+                                fromTransaction = fromTransaction.parent();
+                        }
+                }
+                return target;
+        }
+
+
+        @Override
+        public synchronized Set<Long> getStates() {
+                return new HashSet<>(states.keySet());
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(long fromState, long 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/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..6329a2f6
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java
@@ -0,0 +1,29 @@
+/*
+ * 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> stateBasedImmutableWhenCommitting(boolean transformToImmutable);
+        VersionedMapStoreFactoryBuilder<K,V> stateBasedSharingStrategy(SharingStrategy sharingStrategy);
+        VersionedMapStoreFactoryBuilder<K,V> stateBasedHashProvider(ContinousHashProvider<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
index aade4aeb..a934d59e 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
@@ -5,10 +5,7 @@
  */
 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 tools.refinery.store.map.internal.*;
 
 import java.util.*;
 
@@ -98,7 +95,7 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
                 } else {
                         ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
                         Collections.sort(existingKeys);
-                        throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: "
+                        throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: "
                                         + Arrays.toString(existingKeys.toArray()));
                 }
         }
@@ -123,10 +120,10 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
 
         @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);
+                VersionedMapImpl<K, V> map1 = (VersionedMapImpl<K, V>) createMap(fromState);
+                VersionedMapImpl<K, V> map2 = (VersionedMapImpl<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/map/internal/DeltaBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java
new file mode 100644
index 00000000..fe490f46
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java
@@ -0,0 +1,39 @@
+/*
+ * 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.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreDeltaImpl;
+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/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java
new file mode 100644
index 00000000..cc9003e3
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java
@@ -0,0 +1,147 @@
+/*
+ * 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.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/HashClash.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java
index 61b3d1b8..a357fbce 100644
--- 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
@@ -10,12 +10,12 @@ 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.
          */
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/ImmutableNode.java
index 03dffc15..d052318f 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/ImmutableNode.java
@@ -20,7 +20,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 +47,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 +70,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);
@@ -112,11 +110,9 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 // 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 +121,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,14 +133,12 @@ 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, ContinousHashProvider<? 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
@@ -156,7 +149,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                         oldValue.setOldValue(value);
                                         return this;
                                 } else {
-                                        // update existing nodeId
+                                        // update existing value
                                         MutableNode<K, V> mutable = this.toMutable();
                                         return mutable.updateValue(value, oldValue, selectedHashFragment);
                                 }
@@ -166,16 +159,15 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                         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 +176,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 +190,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 +230,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 +259,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,10 +330,9 @@ 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;
                 }
@@ -315,12 +350,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 +366,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 +387,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 +407,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/InOrderMapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java
new file mode 100644
index 00000000..cb3f366f
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java
@@ -0,0 +1,146 @@
+/*
+ * 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.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(VersionedMapImpl<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/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java
new file mode 100644
index 00000000..d1ab8bb1
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java
@@ -0,0 +1,66 @@
+/*
+ * 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.*;
+import java.util.Map.Entry;
+
+import tools.refinery.store.map.AnyVersionedMap;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.VersionedMap;
+
+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/internal/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
index f34ec7bb..d42519b2 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/MapCursor.java
@@ -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/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java
new file mode 100644
index 00000000..2674236c
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java
@@ -0,0 +1,20 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal;
+
+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/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
index d31f1a05..fb1d5d2b 100644
--- 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
@@ -6,10 +6,10 @@
 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.Objects;
 import java.util.Set;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
@@ -18,37 +18,78 @@ 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 MapCursor<K, V> cursor1;
-        private final MapCursor<K, V> cursor2;
-        private final ContinousHashProvider<? super K> hashProvider;
+        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;
 
-        // 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) {
+        public MapDiffCursor(V defaultValue, InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
                 super();
-                this.hashProvider = hashProvider;
                 this.defaultValue = defaultValue;
-                this.cursor1 = (MapCursor<K, V>) cursor1;
-                this.cursor2 = (MapCursor<K, V>) cursor2;
+                this.cursor1 = cursor1;
+                this.cursor2 = cursor2;
         }
 
         @Override
@@ -72,7 +113,7 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
         }
 
         public boolean isTerminated() {
-                return cursor1.isTerminated() && cursor2.isTerminated();
+                return this.state == State.TERMINATED_TERMINATED;
         }
 
         @Override
@@ -82,148 +123,142 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
 
         @Override
         public Set<AnyVersionedMap> getDependingMaps() {
-                return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream())
-                                .map(AnyVersionedMap.class::cast)
-                                .collect(Collectors.toUnmodifiableSet());
+                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();
-                                }
-                        }
-                }
+        private boolean isInStableState() {
+                return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE
+                                && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT;
         }
 
-        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");
-                }
+        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;
+                        }
+                };
         }
 
-        protected boolean isInHashClash() {
-                return this.hashClash != HashClash.NONE;
+        public boolean move() {
+                do {
+                        this.state = moveOne(this.state);
+                } while (!isInStableState());
+                return updateAndReturnWithResult();
         }
 
-        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");
-                }
+        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!");
+                };
         }
 
-        protected boolean sameValues() {
-                if (this.fromValue == null) {
-                        return this.toValue == null;
+        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 this.fromValue.equals(this.toValue);
+                        return State.TERMINATED_TERMINATED;
                 }
         }
 
-        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 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;
                 }
-        }
 
-        private boolean skipNode() {
-                if (isTerminated()) {
-                        throw new IllegalStateException("DiffCursor tries to skip when terminated!");
+                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;
+                        }
                 }
-                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;
+                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 false;
+                        return State.MOVING_MOVING_HASH1;
                 }
-        }
-
-        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/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java
new file mode 100644
index 00000000..d63522cd
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java
@@ -0,0 +1,39 @@
+/*
+ * 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.Arrays;
+import java.util.Objects;
+
+public record MapTransaction<K, V>(MapDelta<K, V>[] deltas, long version, MapTransaction<K, V> parent) {
+
+        @Override
+        public int hashCode() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + Arrays.hashCode(deltas);
+                result = prime * result + Objects.hash(parent, version);
+                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 Arrays.equals(deltas, other.deltas) && Objects.equals(parent, other.parent) && version == other.version;
+        }
+
+        @Override
+        public String toString() {
+                return "MapTransaction " + version + " " + Arrays.toString(deltas);
+        }
+}
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/MutableNode.java
index 1129ee5a..bb85deb9 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/MutableNode.java
@@ -12,15 +12,15 @@ 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, ContinousHashProvider<? 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) {
                 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, ContinousHashProvider<? 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(ContinousHashProvider<? 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(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));
 
                 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,13 +407,12 @@ 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);
                         }
                 }
         }
@@ -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/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
index 958d645f..4b44f760 100644
--- 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
@@ -9,82 +9,123 @@ import java.util.Map;
 
 import tools.refinery.store.map.ContinousHashProvider;
 
-public abstract class Node<K,V>{
+public abstract class Node<K, V> {
         public static final int BRANCHING_FACTOR_BITS = 5;
-        public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
+        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;
+        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/NUMBER_OF_FACTORS;
+                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%NUMBER_OF_FACTORS;
+                return depth & FACTOR_SELECTION_MASK;
         }
+
         /**
          * Selects a segments from a complete hash for a given depth.
-         * @param hash A complete hash.
+         *
+         * @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;
+                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
+         * 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+")!");
+                final int shiftDepth = shiftDepth(depth);
+                if (shiftDepth == 0) {
+                        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 hashProvider.getHash(key, hashDepth);
+                } else {
+                        return hash;
                 }
-                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 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);
+
+        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.
+         * @return Whether there was a next value to move on.
          */
-        abstract boolean moveToNext(MapCursor<K,V> cursor);
+        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(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
 
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java
new file mode 100644
index 00000000..1c3ab27b
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java
@@ -0,0 +1,38 @@
+/*
+ * 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.*;
+
+import java.util.List;
+
+public class StateBasedVersionedMapStoreFactory<K, V> implements VersionedMapStoreFactory<K, V> {
+        private final V defaultValue;
+        private final ContinousHashProvider<K> continousHashProvider;
+        private final VersionedMapStoreConfiguration config;
+
+        public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinousHashProvider<K> continousHashProvider) {
+                this.defaultValue = defaultValue;
+                this.continousHashProvider = continousHashProvider;
+
+                this.config = new VersionedMapStoreConfiguration(
+                                transformToImmutable,
+                                sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP,
+                                sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP);
+        }
+
+        @Override
+        public VersionedMapStore<K, V> createOne() {
+                return new VersionedMapStoreImpl<>(continousHashProvider, defaultValue, config);
+
+        }
+
+        @Override
+        public List<VersionedMapStore<K, V>> createGroup(int amount) {
+                return VersionedMapStoreImpl.createSharedVersionedMapStores(amount, continousHashProvider, defaultValue,
+                                config);
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java
new file mode 100644
index 00000000..ba59cfef
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java
@@ -0,0 +1,36 @@
+/*
+ * 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.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/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java
new file mode 100644
index 00000000..61a34351
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java
@@ -0,0 +1,53 @@
+/*
+ * 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.*;
+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/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java
new file mode 100644
index 00000000..438b5561
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java
@@ -0,0 +1,29 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.internal;
+
+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/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java
new file mode 100644
index 00000000..ae47feda
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java
@@ -0,0 +1,219 @@
+/*
+ * 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.*;
+
+import tools.refinery.store.map.*;
+
+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 long commit() {
+                MapDelta<K, V>[] deltas = uncommittedStore.extractAndDeleteDeltas();
+                long[] versionContainer = new long[1];
+                this.previous = this.store.appendTransaction(deltas, previous, versionContainer);
+                return versionContainer[0];
+        }
+
+        @Override
+        public void restore(long 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.version(), 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) {
+                for (int i = 0; i < changes.size(); i++) {
+                        backward(changes.get(i));
+                }
+        }
+
+        protected void forward(MapDelta<K, V>[] changes) {
+                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(long 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.version(), 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!");
+                        }
+                }
+        }
+}
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/VersionedMapImpl.java
index 7abece0d..c107f7e0 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/VersionedMapImpl.java
@@ -23,7 +23,6 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
         protected final VersionedMapStoreImpl<K, V> store;
 
         protected final ContinousHashProvider<K> hashProvider;
-
         protected final V defaultValue;
         protected Node<K, V> root;
 
@@ -49,6 +48,7 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                 this.root = data;
         }
 
+        @Override
         public V getDefaultValue() {
                 return defaultValue;
         }
@@ -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()) {
@@ -114,11 +116,10 @@ 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);
-
+                InOrderMapCursor<K, V> fromCursor = new InOrderMapCursor<>(this);
+                VersionedMapImpl<K, V> toMap = (VersionedMapImpl<K, V>) this.store.createMap(toVersion);
+                InOrderMapCursor<K, V> toCursor = new InOrderMapCursor<>(toMap);
+                return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor);
         }
 
 
@@ -136,16 +137,17 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                 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,7 +157,11 @@ 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
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..cf117d95
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java
@@ -0,0 +1,137 @@
+/*
+ * 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.ContinousHashProvider;
+import tools.refinery.store.map.VersionedMapStoreFactory;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
+
+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 ContinousHashProvider<K> continousHashProvider = 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, continousHashProvider, 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> 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(ContinousHashProvider<K> hashProvider) {
+                this.continousHashProvider = 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(continousHashProvider == null) {
+                                        throw new IllegalArgumentException("Continuous hash provider is missing!");
+                                }
+                                yield new StateBasedVersionedMapStoreFactory<>(defaultValue,
+                                                getOrDefault(transformToImmutable,true),
+                                                getOrDefault(sharingStrategy, SharingStrategy.SHARED_NODE_CACHE_IN_GROUP),
+                                                continousHashProvider);
+                        }
+                        case DELTA -> new DeltaBasedVersionedMapStoreFactory<>(defaultValue,
+                                        getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST));
+                };
+        }
+
+        @Override
+        public String toString() {
+                return "VersionedMapStoreBuilder{" +
+                                "defaultValue=" + defaultValue +
+                                ", strategy=" + strategy +
+                                ", stateBasedImmutableWhenCommitting=" + transformToImmutable +
+                                ", stateBasedNodeSharingStrategy=" + sharingStrategy +
+                                ", hashProvider=" + continousHashProvider +
+                                ", deltaStorageStrategy=" + deltaTransactionStrategy +
+                                '}';
+        }
+}
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..fdd4425e 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
@@ -7,39 +7,43 @@ package tools.refinery.store.model;
 
 import tools.refinery.store.map.ContinousHashProvider;
 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 };
+        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/internal/VersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
index 86101ce3..404be65f 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
@@ -9,11 +9,9 @@ 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.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 +22,13 @@ import java.util.List;
 public 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<>();
 
-        private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store,
-                                                                        VersionedMap<Tuple, T> map) {
+        private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) {
                 this.model = model;
                 this.symbol = symbol;
-                this.store = store;
                 this.map = map;
         }
 
@@ -116,9 +111,7 @@ public 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);
+                return map.getDiffCursor(to);
         }
 
         public long commit() {
@@ -153,7 +146,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 @SuppressWarnings("unchecked")
                 var typedSymbol = (Symbol<T>) symbol;
                 var map = store.createMap();
-                return new VersionedInterpretation<>(model, typedSymbol, store, map);
+                return new VersionedInterpretation<>(model, typedSymbol, map);
         }
 
         static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store,
@@ -161,6 +154,6 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
                 @SuppressWarnings("unchecked")
                 var typedSymbol = (Symbol<T>) symbol;
                 var map = store.createMap(state);
-                return new VersionedInterpretation<>(model, typedSymbol, store, map);
+                return new VersionedInterpretation<>(model, typedSymbol, map);
         }
 }
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java
new file mode 100644
index 00000000..4ada4ea4
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java
@@ -0,0 +1,56 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.tests;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
+import tools.refinery.store.map.internal.InOrderMapCursor;
+import tools.refinery.store.map.internal.VersionedMapImpl;
+import tools.refinery.store.map.tests.utils.MapTestEnvironment;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class InOrderCursorTest {
+        @Test
+        void testCursor() {
+                var store = VersionedMapStore.<Integer,String>builder()
+                                .strategy(VersionedMapStoreFactoryBuilder.StoreStrategy.STATE)
+                                .stateBasedImmutableWhenCommitting(true)
+                                .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false))
+                                .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE)
+                                .defaultValue("x")
+                                .build()
+                                .createOne();
+
+                VersionedMapImpl<Integer,String> map = (VersionedMapImpl<Integer,String>) store.createMap();
+                checkMove(map,0);
+
+                map.put(1,"A");
+                map.commit();
+                checkMove(map,1);
+
+
+                map.put(2,"B");
+                map.commit();
+                checkMove(map,2);
+
+                map.put(3,"C");
+                map.commit();
+                checkMove(map,3);
+
+        }
+
+        private void checkMove(VersionedMapImpl<Integer,String> map, int num) {
+                InOrderMapCursor<Integer,String> cursor = new InOrderMapCursor<>(map);
+                for(int i=0; i<num; i++) {
+                        assertTrue(cursor.move());
+                        assertFalse(cursor.isTerminated());
+                }
+                assertFalse(cursor.move());
+                assertTrue(cursor.isTerminated());
+        }
+}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java
index 153f2e78..2be49bd9 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java
@@ -23,4 +23,75 @@ class MapUnitTests {
                 var out2 = map.put(Tuple.of(1), true);
                 assertEquals(false, out2);
         }
+
+        @Test
+        void deltaRestoreTest() {
+                VersionedMapStore<Integer,String> store =
+                                VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne();
+                var map = store.createMap();
+                map.put(1,"val");
+                var version1 = map.commit();
+                map.put(1,"x");
+                map.restore(version1);
+                System.out.println(map.getSize());
+                assertEquals(1,map.getSize());
+        }
+
+        @Test
+        void deltaRestoreTest2() {
+                VersionedMapStore<Integer,String> store =
+                                VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne();
+                var map = store.createMap();
+                map.put(1,"x");
+                var version1 = map.commit();
+                map.put(1,"1");
+                map.restore(version1);
+                System.out.println(map.getSize());
+                assertEquals(0,map.getSize());
+        }
+        @Test
+        void deltaRestoreTest3() {
+                VersionedMapStore<Integer,String> store =
+                                VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne();
+                var map = store.createMap();
+                map.commit();
+                map.put(1,"1");
+                map.put(2,"x");
+                assertEquals(1,map.getSize());
+                var version1 = map.commit();
+                map.put(1,"x");
+                assertEquals(0,map.getSize());
+                map.put(2,"2");
+                assertEquals(1,map.getSize());
+                map.put(2,"x");
+                assertEquals(0,map.getSize());
+                var version2 = map.commit();
+                map.restore(version1);
+                assertEquals(1,map.getSize());
+                map.restore(version2);
+                assertEquals(0,map.getSize());
+        }
+
+        @Test
+        void deltaRestoreTest4() {
+                VersionedMapStore<Integer,String> store =
+                                VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne();
+                var map = store.createMap();
+                map.commit();
+                map.put(1,"1");
+                map.put(2,"x");
+                assertEquals(1,map.getSize());
+                var version1 = map.commit();
+                map.put(1,"x");
+                assertEquals(0,map.getSize());
+                map.put(2,"2");
+                assertEquals(1,map.getSize());
+                map.put(2,"x");
+                assertEquals(0,map.getSize());
+                var version2 = map.commit();
+                map.restore(version1);
+                assertEquals(1,map.getSize());
+                map.restore(version2);
+                assertEquals(0,map.getSize());
+        }
 }
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java
index eabe5bd1..58206eda 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java
@@ -5,33 +5,32 @@
  */
 package tools.refinery.store.map.tests.fuzz;
 
-import static org.junit.jupiter.api.Assertions.fail;
-
-import java.util.Random;
-import java.util.stream.Stream;
-
 import org.junit.jupiter.api.Tag;
 import org.junit.jupiter.api.Timeout;
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
-
-import tools.refinery.store.map.ContinousHashProvider;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.VersionedMapStoreImpl;
-import tools.refinery.store.map.internal.VersionedMapImpl;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
+import java.util.Random;
+import java.util.stream.Stream;
+
+import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
+
 class CommitFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
-                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
 
-                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
-                VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
-                MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
+                                                         boolean nullDefault, int commitFrequency,
+                                                         VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
+
+                VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne();
+                var sut = store.createMap();
+                MapTestEnvironment<Integer, String> e = new MapTestEnvironment<>(sut);
 
                 Random r = new Random(seed);
 
@@ -39,24 +38,13 @@ class CommitFuzzTest {
         }
 
         private void iterativeRandomPutsAndCommits(String scenario, int steps, int maxKey, String[] values,
-                        MapTestEnvironment<Integer, String> e, Random r, int commitFrequency) {
-                int stopAt = -1;
+                                                                                           MapTestEnvironment<Integer, String> e, Random r, int commitFrequency) {
                 for (int i = 0; i < steps; i++) {
                         int index = i + 1;
                         int nextKey = r.nextInt(maxKey);
                         String nextValue = values[r.nextInt(values.length)];
-                        if (index == stopAt) {
-                                System.out.println("issue!");
-                                System.out.println("State before:");
-                                e.printComparison();
-                                e.sut.prettyPrint();
-                                System.out.println("Next: put(" + nextKey + "," + nextValue + ")");
-                        }
                         try {
                                 e.put(nextKey, nextValue);
-                                if (index == stopAt) {
-                                        e.sut.prettyPrint();
-                                }
                                 e.checkEquivalence(scenario + ":" + index);
                         } catch (Exception exception) {
                                 exception.printStackTrace();
@@ -64,35 +52,37 @@ class CommitFuzzTest {
                         }
                         MapTestEnvironment.printStatus(scenario, index, steps, null);
                         if (index % commitFrequency == 0) {
-                                e.sut.commit();
+                                e.commit();
                         }
                 }
         }
 
-        @ParameterizedTest(name = "Commit {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        public static final String title = "Commit {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit frequency={5} " +
+                        "seed={6} config={7}";
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
-        void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                commitFrequencyOptions, randomSeedOptions, storeConfigs);
         }
 
-        @ParameterizedTest(name = "Commit {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = title)
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
index b0502a2b..c49911b8 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
@@ -10,8 +10,10 @@ import org.junit.jupiter.api.Timeout;
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
-import tools.refinery.store.map.*;
-import tools.refinery.store.map.internal.VersionedMapImpl;
+import tools.refinery.store.map.Cursor;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
@@ -22,23 +24,25 @@ import java.util.List;
 import java.util.Random;
 import java.util.stream.Stream;
 
-import static org.junit.jupiter.api.Assertions.*;
+import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
 
 class ContentEqualsFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                                                         boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
-                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
+                                                         boolean nullDefault, int commitFrequency,
+                                                         VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
+
 
                 Random r = new Random(seed);
 
-                iterativeRandomPutsAndCommitsThenCompare(scenario, chp, steps, maxKey, values, r, commitFrequency);
+                iterativeRandomPutsAndCommitsThenCompare(scenario, builder, steps, maxKey, values, r, commitFrequency);
         }
 
-        private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider<Integer> chp,
+        private void iterativeRandomPutsAndCommitsThenCompare(String scenario, VersionedMapStoreFactoryBuilder<Integer, String> builder,
                                                                                                                   int steps, int maxKey, String[] values, Random r,
                                                                                                                   int commitFrequency) {
-                VersionedMapStore<Integer, String> store1 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
+                VersionedMapStore<Integer, String> store1 = builder.defaultValue(values[0]).build().createOne();
                 VersionedMap<Integer, String> sut1 = store1.createMap();
 
                 // Fill one map
@@ -68,7 +72,7 @@ class ContentEqualsFuzzTest {
                 // Randomize the order of the content
                 Collections.shuffle(content, r);
 
-                VersionedMapStore<Integer, String> store2 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
+                VersionedMapStore<Integer, String> store2 = builder.defaultValue(values[0]).build().createOne();
                 VersionedMap<Integer, String> sut2 = store2.createMap();
                 int index2 = 1;
                 for (SimpleEntry<Integer, String> entry : content) {
@@ -78,40 +82,39 @@ class ContentEqualsFuzzTest {
                 }
 
                 // Check the integrity of the maps
-                ((VersionedMapImpl<Integer, String>) sut1).checkIntegrity();
-                ((VersionedMapImpl<Integer, String>) sut2).checkIntegrity();
+                sut1.checkIntegrity();
+                sut2.checkIntegrity();
 
                 // Compare the two maps
                 MapTestEnvironment.compareTwoMaps(scenario, sut1, sut2);
         }
 
-        @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} " +
-                        "evil-hash={6}")
+        public static final String title = "Compare {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} commit frequency={5}" +
+                        "seed={6} config={7}";
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
-        void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                                                          boolean evilHash) {
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[]{FuzzTestUtils.FAST_STEP_COUNT}, new Object[]{3, 32,
-                                                32 * 32},
-                                new Object[]{2, 3}, new Object[]{1, 10, 100}, new Object[]{1, 2, 3},
-                                new Object[]{false, true});
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                commitFrequencyOptions, randomSeedOptions, storeConfigs);
         }
 
-        @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} " +
-                        "evil-hash={6}")
+        @ParameterizedTest(name = title)
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                                                          boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull, int commitFrequency,
+                                                          int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                defaultNull, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
index 8274336e..5a4f8038 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
@@ -5,115 +5,133 @@
  */
 package tools.refinery.store.map.tests.fuzz;
 
-import static org.junit.jupiter.api.Assertions.fail;
-
-import java.util.Random;
-import java.util.stream.Stream;
-
 import org.junit.jupiter.api.Tag;
 import org.junit.jupiter.api.Timeout;
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
-
-import tools.refinery.store.map.ContinousHashProvider;
 import tools.refinery.store.map.DiffCursor;
+import tools.refinery.store.map.VersionedMap;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.VersionedMapStoreImpl;
-import tools.refinery.store.map.internal.VersionedMapImpl;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
+import java.util.Random;
+import java.util.stream.Stream;
+
+import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
+
 class DiffCursorFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
-                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault,
+                                                         int commitFrequency, boolean commitBeforeDiffCursor,
+                                                         VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
 
-                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
-                iterativeRandomPutsAndCommitsThenDiffcursor(scenario, store, steps, maxKey, values, seed, commitFrequency);
+                VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne();
+                iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency,
+                                commitBeforeDiffCursor);
         }
 
-        private void iterativeRandomPutsAndCommitsThenDiffcursor(String scenario, VersionedMapStore<Integer, String> store,
-                        int steps, int maxKey, String[] values, int seed, int commitFrequency) {
-                // 1. build a map with versions
-                Random r = new Random(seed);
-                VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
+        private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore<Integer, String> store,
+                                                                                                                         int steps, int maxKey, String[] values, int seed,
+                                                                                                                         int commitFrequency, boolean commitBeforeDiffCursor) {
+
                 int largestCommit = -1;
 
-                for (int i = 0; i < steps; i++) {
-                        int index = i + 1;
-                        int nextKey = r.nextInt(maxKey);
-                        String nextValue = values[r.nextInt(values.length)];
-                        try {
-                                versioned.put(nextKey, nextValue);
-                        } catch (Exception exception) {
-                                exception.printStackTrace();
-                                fail(scenario + ":" + index + ": exception happened: " + exception);
-                        }
-                        if (index % commitFrequency == 0) {
-                                long version = versioned.commit();
-                                largestCommit = (int) version;
-                        }
-                        if (index % 10000 == 0)
-                                System.out.println(scenario + ":" + index + "/" + steps + " building finished");
-                }
-                // 2. create a non-versioned map,
-                VersionedMapImpl<Integer, String> moving = (VersionedMapImpl<Integer, String>) store.createMap();
-                Random r2 = new Random(seed + 1);
-
-                final int diffTravelFrequency = commitFrequency * 2;
-                for (int i = 0; i < steps; i++) {
-                        int index = i + 1;
-                        if (index % diffTravelFrequency == 0) {
-                                // difftravel
-                                long travelToVersion = r2.nextInt(largestCommit + 1);
-                                DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
-                                moving.putAll(diffCursor);
-
-                        } else {
-                                // random puts
-                                int nextKey = r2.nextInt(maxKey);
-                                String nextValue = values[r2.nextInt(values.length)];
+                {
+                        // 1. build a map with versions
+                        Random r = new Random(seed);
+                        VersionedMap<Integer, String> versioned = store.createMap();
+                        for (int i = 0; i < steps; i++) {
+                                int index = i + 1;
+                                int nextKey = r.nextInt(maxKey);
+                                String nextValue = values[r.nextInt(values.length)];
                                 try {
-                                        moving.put(nextKey, nextValue);
+                                        versioned.put(nextKey, nextValue);
                                 } catch (Exception exception) {
                                         exception.printStackTrace();
                                         fail(scenario + ":" + index + ": exception happened: " + exception);
                                 }
                                 if (index % commitFrequency == 0) {
-                                        versioned.commit();
+                                        long version = versioned.commit();
+                                        largestCommit = (int) version;
                                 }
                                 if (index % 10000 == 0)
                                         System.out.println(scenario + ":" + index + "/" + steps + " building finished");
                         }
                 }
 
+                {
+                        // 2. create a non-versioned map,
+                        VersionedMap<Integer, String> moving = store.createMap();
+                        Random r2 = new Random(seed + 1);
+
+                        final int diffTravelFrequency = commitFrequency * 2;
+                        for (int i = 0; i < steps; i++) {
+                                int index = i + 1;
+                                if (index % diffTravelFrequency == 0) {
+                                        // diff-travel
+                                        long travelToVersion = r2.nextInt(largestCommit + 1);
+
+                                        VersionedMap<Integer, String> oracle = store.createMap(travelToVersion);
+
+                                        if(commitBeforeDiffCursor) {
+                                                moving.commit();
+                                        }
+                                        DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
+                                        moving.putAll(diffCursor);
+                                        moving.commit();
+
+                                        MapTestEnvironment.compareTwoMaps(scenario + ":c" + index, oracle, moving);
+
+                                        moving.restore(travelToVersion);
+
+                                } else {
+                                        // random puts
+                                        int nextKey = r2.nextInt(maxKey);
+                                        String nextValue = values[r2.nextInt(values.length)];
+                                        try {
+                                                moving.put(nextKey, nextValue);
+                                        } catch (Exception exception) {
+                                                exception.printStackTrace();
+                                                fail(scenario + ":" + index + ": exception happened: " + exception);
+                                        }
+                                        if (index % 10000 == 0)
+                                                System.out.println(scenario + ":" + index + "/" + steps + " building finished");
+                                }
+                        }
+                }
         }
 
-        @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " +
+                        "commit frequency={5} seed={6} commit before diff={7} config={8}";
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
-        void parametrizedFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
-                runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
-                                noKeys, noValues, commitFrequency, evilHash);
+        void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault,
+                                                  int commitFrequency, int seed, boolean commitBeforeDiffCursor,
+                                                  VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
+                                noKeys, noValues, nullDefault, commitFrequency, commitBeforeDiffCursor, builder);
         }
 
         static Stream<Arguments> parametrizedFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(new Object[]{100}, keyCounts, valueCounts, nullDefaultOptions,
+                                commitFrequencyOptions, randomSeedOptions, new Object[]{false,true}, storeConfigs);
         }
-        @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
-                runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                        int seed, boolean commitBeforeDiffCursor, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
+                                nullDefault, commitFrequency, commitBeforeDiffCursor, builder);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java
index ab2b9435..3b55434c 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java
@@ -5,95 +5,96 @@
  */
 package tools.refinery.store.map.tests.fuzz;
 
-import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.fail;
-
-import java.util.Collections;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.stream.Stream;
-
 import org.junit.jupiter.api.Tag;
 import org.junit.jupiter.api.Timeout;
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
-
-import tools.refinery.store.map.ContinousHashProvider;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.VersionedMapStoreImpl;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.stream.Stream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
+
 class MultiThreadFuzzTest {
-        public static final int noThreads = 32;
-        
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
-                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
-
-                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
-                
+        public static final int noThreads = 10;
+
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
+
+                VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne();
+
                 // initialize runnables
                 MultiThreadTestRunnable[] runnables = new MultiThreadTestRunnable[noThreads];
-                for(int i = 0; i<noThreads; i++) {
-                        runnables[i] = new MultiThreadTestRunnable(scenario+"-T"+(i+1), store, steps, maxKey, values, seed, commitFrequency);
+                for (int i = 0; i < noThreads; i++) {
+                        runnables[i] = new MultiThreadTestRunnable(scenario + "-T" + (i + 1), store, steps, maxKey, values, seed
+                                         , commitFrequency);
                 }
-                
+
                 // initialize threads
                 Thread[] threads = new Thread[noThreads];
-                for(int i = 0; i<noThreads; i++) {
+                for (int i = 0; i < noThreads; i++) {
                         threads[i] = new Thread(runnables[i]);
                 }
-                
+
                 // start threads;
-                for(int i = 0; i<noThreads; i++) {
-                        threads[i].start();
+                for (int i = 0; i < noThreads; i++) {
+                        runnables[i].run();
+                        //threads[i].start();
                 }
-                
+
                 // wait all the threads;
-                for(int i = 0; i<noThreads; i++) {
+                for (int i = 0; i < noThreads; i++) {
                         try {
                                 threads[i].join();
                         } catch (InterruptedException e) {
-                                fail("Thread "+i+" interrupted.");
+                                fail("Thread " + i + " interrupted.");
                         }
                 }
-                
+
                 // collect errors
                 List<Throwable> errors = new LinkedList<>();
-                for(int i = 0; i<noThreads; i++) {
+                for (int i = 0; i < noThreads; i++) {
                         errors.addAll(runnables[i].getErrors());
                 }
-                
+
                 assertEquals(Collections.EMPTY_LIST, errors);
         }
 
-        @ParameterizedTest(name = "Multithread {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        static final String title = "MultiThread {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} commit " +
+                         "frequency={5} seed={6} config={7}";
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
-        void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
-                runFuzzTest("MultithreadS" + steps + "K" + noKeys + "V" + noValues + "CF" + commitFrequency + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull,
+                                                           int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                runFuzzTest("MultiThreadS" + steps + "K" + noKeys + "V" + noValues + defaultNull + "CF" + commitFrequency +
+                                 "s" + seed, seed, steps, noKeys, noValues, defaultNull, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                 new Object[]{10, 100}, randomSeedOptions, storeConfigs);
         }
 
-        @ParameterizedTest(name = "Multithread {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = title)
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault,
+                                                          int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java
index 502c8362..9b2e591a 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java
@@ -13,22 +13,22 @@ import java.util.List;
 import java.util.Map;
 import java.util.Random;
 
+import tools.refinery.store.map.VersionedMap;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.internal.VersionedMapImpl;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
 public class MultiThreadTestRunnable implements Runnable {
-        String scenario;
-        VersionedMapStore<Integer, String> store;
-        int steps;
-        int maxKey;
-        String[] values;
-        int seed;
-        int commitFrequency;
-        List<Throwable> errors = new LinkedList<>();
-        
+        final String scenario;
+        final VersionedMapStore<Integer, String> store;
+        final int steps;
+        final int maxKey;
+        final String[] values;
+        final int seed;
+        final int commitFrequency;
+        final List<Throwable> errors = new LinkedList<>();
+
         public MultiThreadTestRunnable(String scenario, VersionedMapStore<Integer, String> store, int steps,
-                        int maxKey, String[] values, int seed, int commitFrequency) {
+                                                                   int maxKey, String[] values, int seed, int commitFrequency) {
                 super();
                 this.scenario = scenario;
                 this.store = store;
@@ -43,16 +43,24 @@ public class MultiThreadTestRunnable implements Runnable {
                 AssertionError error = new AssertionError(message);
                 errors.add(error);
         }
-        
+
         public List<Throwable> getErrors() {
                 return errors;
         }
-        
+
         @Override
         public void run() {
+                try{
+                        task();
+                } catch(Exception e) {
+                        e.printStackTrace();
+                }
+        }
+
+        private void task() {
                 // 1. build a map with versions
                 Random r = new Random(seed);
-                VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
+                VersionedMap<Integer, String> versioned =  store.createMap();
                 Map<Integer, Long> index2Version = new HashMap<>();
 
                 for (int i = 0; i < steps; i++) {
@@ -71,10 +79,10 @@ public class MultiThreadTestRunnable implements Runnable {
                         }
                         MapTestEnvironment.printStatus(scenario, index, steps, "building");
                 }
-                // 2. create a non-versioned 
-                VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap();
+                // 2. create a non-versioned
+                VersionedMap<Integer, String> reference = store.createMap();
                 r = new Random(seed);
-                Random r2 = new Random(seed+1);
+                Random r2 = new Random(seed + 1);
 
                 for (int i = 0; i < steps; i++) {
                         int index = i + 1;
@@ -89,13 +97,17 @@ public class MultiThreadTestRunnable implements Runnable {
                         // go back to an existing state and compare to the reference
                         if (index % (commitFrequency) == 0) {
                                 versioned.restore(index2Version.get(i));
-                                MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned,errors);
-                                
+                                MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned, null);
+
                                 // go back to a random state (probably created by another thread)
                                 List<Long> states = new ArrayList<>(store.getStates());
+                                states.sort(Long::compare);
                                 Collections.shuffle(states, r2);
-                                for(Long state : states.subList(0, Math.min(states.size(), 100))) {
-                                        versioned.restore(state);
+                                for (Long state : states.subList(0, Math.min(states.size(), 100))) {
+                                        long x = state;
+                                        versioned.restore(x);
+                                        var clean = store.createMap(x);
+                                        MapTestEnvironment.compareTwoMaps(scenario + ":" + index, clean, versioned, null);
                                 }
                                 versioned.restore(index2Version.get(i));
                         }
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java
index 32dde0da..fdcd7f9f 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.map.tests.fuzz;
 
 import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
 
 import java.util.Random;
 import java.util.stream.Stream;
@@ -16,21 +17,18 @@ import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
 
-import tools.refinery.store.map.ContinousHashProvider;
-import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.VersionedMapStoreImpl;
-import tools.refinery.store.map.internal.VersionedMapImpl;
+import tools.refinery.store.map.*;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
 class MutableFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
-                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
+                                                         boolean nullDefault, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
 
-                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
-                VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
-                MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
+                VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne();
+                VersionedMap<Integer, String> sut = store.createMap();
+                MapTestEnvironment<Integer, String> e = new MapTestEnvironment<>(sut);
 
                 Random r = new Random(seed);
 
@@ -38,24 +36,14 @@ class MutableFuzzTest {
         }
 
         private void iterativeRandomPuts(String scenario, int steps, int maxKey, String[] values,
-                        MapTestEnvironment<Integer, String> e, Random r) {
-                int stopAt = -1;
+                                                                         MapTestEnvironment<Integer, String> e, Random r) {
                 for (int i = 0; i < steps; i++) {
                         int index = i + 1;
                         int nextKey = r.nextInt(maxKey);
                         String nextValue = values[r.nextInt(values.length)];
-                        if (index == stopAt) {
-                                System.out.println("issue!");
-                                System.out.println("State before:");
-                                e.printComparison();
-                                e.sut.prettyPrint();
-                                System.out.println("Next: put(" + nextKey + "," + nextValue + ")");
-                        }
+
                         try {
                                 e.put(nextKey, nextValue);
-                                if (index == stopAt) {
-                                        e.sut.prettyPrint();
-                                }
                                 e.checkEquivalence(scenario + ":" + index);
                         } catch (Exception exception) {
                                 exception.printStackTrace();
@@ -65,30 +53,34 @@ class MutableFuzzTest {
                 }
         }
 
-        @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}")
+        final String title = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} seed={5} " +
+                        "config={6}";
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
-        void parametrizedFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) {
+        void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull, int seed,
+                                                  VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest(
-                                "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"),
-                                seed, steps, noKeys, noValues, evilHash);
+                                "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed,
+                                seed, steps, noKeys, noValues, defaultNull, builder);
         }
 
         static Stream<Arguments> parametrizedFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT },
-                                new Object[] { 3, 32, 32 * 32, 32 * 32 * 32 * 32 }, new Object[] { 2, 3 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                randomSeedOptions, storeConfigs);
         }
-        
-        @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}")
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
-        void parametrizedSlowFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int seed,
+                                                          VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest(
-                                "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"),
-                                seed, steps, noKeys, noValues, evilHash);
+                                "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed,
+                                seed, steps, noKeys, noValues, nullDefault, builder);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java
index 347c49be..420dade6 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java
@@ -6,6 +6,7 @@
 package tools.refinery.store.map.tests.fuzz;
 
 import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
 
 import java.util.Random;
 import java.util.stream.Stream;
@@ -24,12 +25,12 @@ import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
 class MutableImmutableCompareFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
+                                                         boolean nullDefault, int commitFrequency, boolean evilHash) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
                 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
 
-                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
+                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<>(chp, values[0]);
                 VersionedMapImpl<Integer, String> immutable = (VersionedMapImpl<Integer, String>) store.createMap();
                 VersionedMapImpl<Integer, String> mutable = (VersionedMapImpl<Integer, String>) store.createMap();
 
@@ -40,8 +41,8 @@ class MutableImmutableCompareFuzzTest {
         }
 
         private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl<Integer, String> immutable,
-                        VersionedMapImpl<Integer, String> mutable, int steps, int maxKey, String[] values, Random r,
-                        int commitFrequency) {
+                                                                                                                 VersionedMapImpl<Integer, String> mutable, int steps, int maxKey, String[] values, Random r,
+                                                                                                                 int commitFrequency) {
                 for (int i = 0; i < steps; i++) {
                         int index = i + 1;
                         int nextKey = r.nextInt(maxKey);
@@ -62,30 +63,31 @@ class MutableImmutableCompareFuzzTest {
                 }
         }
 
-        @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " +
+                        "commit frequency={5} seed={6} evil-hash={7}")
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
-        void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, boolean evilHash) {
                 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
-                                noKeys, noValues, commitFrequency, evilHash);
+                                noKeys, noValues, nullDefault, commitFrequency, evilHash);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                commitFrequencyOptions, randomSeedOptions, new Object[]{false, true});
         }
 
-        @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " +
+                        "commit frequency={5} seed={6} evil-hash={7}")
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, boolean evilHash) {
                 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
-                                noKeys, noValues, commitFrequency, evilHash);
+                                noKeys, noValues, nullDefault, commitFrequency, evilHash);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java
index f7b9d61e..0b399c3a 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java
@@ -5,42 +5,41 @@
  */
 package tools.refinery.store.map.tests.fuzz;
 
-import static org.junit.jupiter.api.Assertions.fail;
-
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Random;
-import java.util.stream.Stream;
-
 import org.junit.jupiter.api.Tag;
 import org.junit.jupiter.api.Timeout;
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
-
-import tools.refinery.store.map.ContinousHashProvider;
+import tools.refinery.store.map.VersionedMap;
 import tools.refinery.store.map.VersionedMapStore;
-import tools.refinery.store.map.VersionedMapStoreImpl;
-import tools.refinery.store.map.internal.VersionedMapImpl;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.stream.Stream;
+
+import static org.junit.jupiter.api.Assertions.fail;
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
+
 class RestoreFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
-                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
+                                                         boolean nullDefault, int commitFrequency,
+                                                         VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
 
-                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
+                VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne();
 
                 iterativeRandomPutsAndCommitsThenRestore(scenario, store, steps, maxKey, values, seed, commitFrequency);
         }
 
         private void iterativeRandomPutsAndCommitsThenRestore(String scenario, VersionedMapStore<Integer, String> store,
-                        int steps, int maxKey, String[] values, int seed, int commitFrequency) {
+                                                                                                                  int steps, int maxKey, String[] values, int seed, int commitFrequency) {
                 // 1. build a map with versions
                 Random r = new Random(seed);
-                VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
+                VersionedMap<Integer, String> versioned = store.createMap();
                 Map<Integer, Long> index2Version = new HashMap<>();
 
                 for (int i = 0; i < steps; i++) {
@@ -60,7 +59,7 @@ class RestoreFuzzTest {
                         MapTestEnvironment.printStatus(scenario, index, steps, "building");
                 }
                 // 2. create a non-versioned and
-                VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap();
+                VersionedMap<Integer, String> reference = store.createMap();
                 r = new Random(seed);
 
                 for (int i = 0; i < steps; i++) {
@@ -82,30 +81,32 @@ class RestoreFuzzTest {
 
         }
 
-        @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        public static final String title = "Commit {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit frequency={5} " +
+                        "seed={6} config={7}";
+
+        @ParameterizedTest(name = title)
         @MethodSource
         @Timeout(value = 10)
         @Tag("smoke")
-        void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                commitFrequencyOptions, randomSeedOptions, storeConfigs);
         }
 
-        @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = title)
         @MethodSource
         @Tag("smoke")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
                 runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, builder);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java
index 4b4172d0..680d962d 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java
@@ -25,10 +25,12 @@ import tools.refinery.store.map.internal.VersionedMapImpl;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
+
 class SharedStoreFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
-                String[] values = MapTestEnvironment.prepareValues(maxValue);
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
+                                                         boolean nullDefault, int commitFrequency, boolean evilHash) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
                 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
 
                 List<VersionedMapStore<Integer, String>> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]);
@@ -37,22 +39,22 @@ class SharedStoreFuzzTest {
         }
 
         private void iterativeRandomPutsAndCommitsThenRestore(String scenario, List<VersionedMapStore<Integer, String>> stores,
-                        int steps, int maxKey, String[] values, int seed, int commitFrequency) {
+                                                                                                                  int steps, int maxKey, String[] values, int seed, int commitFrequency) {
                 // 1. maps with versions
                 Random r = new Random(seed);
                 List<VersionedMapImpl<Integer, String>> versioneds = new LinkedList<>();
-                for(VersionedMapStore<Integer, String> store : stores) {
+                for (VersionedMapStore<Integer, String> store : stores) {
                         versioneds.add((VersionedMapImpl<Integer, String>) store.createMap());
                 }
-                                
+
                 List<Map<Integer, Long>> index2Version = new LinkedList<>();
-                for(int i = 0; i<stores.size(); i++) {
+                for (int i = 0; i < stores.size(); i++) {
                         index2Version.add(new HashMap<>());
                 }
 
                 for (int i = 0; i < steps; i++) {
                         int stepIndex = i + 1;
-                        for (int storeIndex = 0; storeIndex<versioneds.size(); storeIndex++) {
+                        for (int storeIndex = 0; storeIndex < versioneds.size(); storeIndex++) {
                                 int nextKey = r.nextInt(maxKey);
                                 String nextValue = values[r.nextInt(values.length)];
                                 versioneds.get(storeIndex).put(nextKey, nextValue);
@@ -61,18 +63,18 @@ class SharedStoreFuzzTest {
                                         index2Version.get(storeIndex).put(i, version);
                                 }
                                 MapTestEnvironment.printStatus(scenario, stepIndex, steps, "building");
-                        }               
+                        }
                 }
                 // 2. create a non-versioned and
                 List<VersionedMapImpl<Integer, String>> reference = new LinkedList<>();
-                for(VersionedMapStore<Integer, String> store : stores) {
+                for (VersionedMapStore<Integer, String> store : stores) {
                         reference.add((VersionedMapImpl<Integer, String>) store.createMap());
                 }
                 r = new Random(seed);
 
                 for (int i = 0; i < steps; i++) {
                         int index = i + 1;
-                        for (int storeIndex = 0; storeIndex<versioneds.size(); storeIndex++) {
+                        for (int storeIndex = 0; storeIndex < versioneds.size(); storeIndex++) {
                                 int nextKey = r.nextInt(maxKey);
                                 String nextValue = values[r.nextInt(values.length)];
                                 reference.get(storeIndex).put(nextKey, nextValue);
@@ -81,35 +83,36 @@ class SharedStoreFuzzTest {
                                         MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference.get(storeIndex), versioneds.get(storeIndex));
                                 }
                         }
-                        MapTestEnvironment.printStatus(scenario, index, steps, "comparison");   
+                        MapTestEnvironment.printStatus(scenario, index, steps, "comparison");
                 }
 
         }
 
-        @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit " +
+                        "frequency={4} seed={5} evil-hash={6}")
         @MethodSource
         @Timeout(value = 10)
         @Tag("smoke")
-        void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, boolean evilHash) {
                 runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, evilHash);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                commitFrequencyOptions, randomSeedOptions, new Object[]{false, true});
         }
 
-        @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit " +
+                        "frequency={4} seed={5} evil-hash={6}")
         @MethodSource
         @Tag("smoke")
         @Tag("slow")
-        void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
+                                                          int seed, boolean evilHash) {
                 runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                commitFrequency, evilHash);
+                                nullDefault, commitFrequency, evilHash);
         }
 
         static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SingleThreadFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SingleThreadFuzzTest.java
new file mode 100644
index 00000000..1337cf3a
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SingleThreadFuzzTest.java
@@ -0,0 +1,66 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.tests.fuzz;
+
+import org.junit.jupiter.api.Tag;
+import org.junit.jupiter.api.Timeout;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
+import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
+import tools.refinery.store.map.tests.utils.MapTestEnvironment;
+
+import java.util.stream.Stream;
+
+import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
+
+class SingleThreadFuzzTest {
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
+
+                VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne();
+
+                // initialize runnables
+                MultiThreadTestRunnable runnable = new MultiThreadTestRunnable(scenario, store, steps, maxKey, values, seed, commitFrequency);
+
+                // start threads;
+                runnable.run();
+        }
+
+        static final String title = "SingleThread {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} commit " +
+                        "frequency={5} seed={6} config={7}";
+
+        @ParameterizedTest(name = title)
+        @MethodSource
+        @Timeout(value = 10)
+        @Tag("fuzz")
+        void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull,
+                                                          int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                runFuzzTest("SingleThreadS" + steps + "K" + noKeys + "V" + noValues + defaultNull + "CF" + commitFrequency +
+                                "s" + seed, seed, steps, noKeys, noValues, defaultNull, commitFrequency, builder);
+        }
+
+        static Stream<Arguments> parametrizedFastFuzz() {
+                return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions,
+                                new Object[]{10, 100}, randomSeedOptions, storeConfigs);
+        }
+
+        @ParameterizedTest(name = title)
+        @MethodSource
+        @Tag("fuzz")
+        @Tag("slow")
+        void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault,
+                                                          int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) {
+                runFuzzTest("SingleThreadS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
+                                nullDefault, commitFrequency, builder);
+        }
+
+        static Stream<Arguments> parametrizedSlowFuzz() {
+                return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1);
+        }
+}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java
new file mode 100644
index 00000000..4c3ecb09
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java
@@ -0,0 +1,44 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.map.tests.fuzz.utils;
+
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreFactoryBuilder;
+import tools.refinery.store.map.tests.utils.MapTestEnvironment;
+
+public final class FuzzTestCollections {
+        public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT};
+        public static final Object[] keyCounts = {1 , 32, 32 * 32};
+        public static final Object[] valueCounts = {2, 3};
+        public static final Object[] nullDefaultOptions = {false, true};
+        public static final Object[] commitFrequencyOptions = {1, 10, 100};
+        public static final Object[] randomSeedOptions = {1};
+        public static final Object[] storeConfigs = {
+                        // State based
+                        VersionedMapStore.<Integer,String>builder()
+                                        .stateBasedImmutableWhenCommitting(true)
+                                        .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false))
+                                        .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE),
+                        VersionedMapStore.<Integer,String>builder()
+                                        .stateBasedImmutableWhenCommitting(true)
+                                        .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(true))
+                                        .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE),
+                        VersionedMapStore.<Integer,String>builder()
+                                        .stateBasedImmutableWhenCommitting(false)
+                                        .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false))
+                                        .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE),
+                        VersionedMapStore.<Integer,String>builder()
+                                        .stateBasedImmutableWhenCommitting(false)
+                                        .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false))
+                                        .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.NO_NODE_CACHE),
+
+                        // Delta based
+                        VersionedMapStore.<Integer,String>builder()
+                                        .deltaTransactionStrategy(VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET),
+                        VersionedMapStore.<Integer,String>builder()
+                                        .deltaTransactionStrategy(VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.LIST)
+        };
+}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java
index a819d348..32675635 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java
@@ -13,7 +13,7 @@ import java.util.stream.Stream;
 import org.junit.jupiter.params.provider.Arguments;
 
 public final class FuzzTestUtils {
-        public static final int FAST_STEP_COUNT = 500;
+        public static final int FAST_STEP_COUNT = 250;
         public static final int SLOW_STEP_COUNT = 32 * 32 * 32 * 32;
 
         private FuzzTestUtils() {
@@ -56,14 +56,12 @@ public final class FuzzTestUtils {
 
         public static Stream<Arguments> permutationWithSize(Object[]... valueOption) {
                 int size = 1;
-                for (int i = 0; i < valueOption.length; i++) {
-                        size *= valueOption[i].length;
+                for (Object[] objects : valueOption) {
+                        size *= objects.length;
                 }
                 Object[][] newValueOption = new Object[valueOption.length + 1][];
-                newValueOption[0] = new Object[] { size };
-                for (int i = 1; i < newValueOption.length; i++) {
-                        newValueOption[i] = valueOption[i - 1];
-                }
+                newValueOption[0] = new Object[]{size};
+                System.arraycopy(valueOption, 0, newValueOption, 1, newValueOption.length - 1);
                 return permutation(newValueOption);
         }
 }
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java
index dc621574..951d6336 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java
@@ -6,31 +6,36 @@
 package tools.refinery.store.map.tests.fuzz.utils;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
 
 import java.util.List;
+import java.util.Optional;
 
 import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.provider.Arguments;
 
 class FuzzTestUtilsTest {
         @Test
         void permutationInternalTest() {
-                List<List<Object>> res = FuzzTestUtils.permutationInternal(0, new Object[] { 1, 2, 3 },
-                                new Object[] { 'a', 'b', 'c' }, new Object[] { "alpha", "beta", "gamma", "delta" });
+                List<List<Object>> res = FuzzTestUtils.permutationInternal(0, new Object[]{1, 2, 3},
+                                new Object[]{'a', 'b', 'c'}, new Object[]{"alpha", "beta", "gamma", "delta"});
                 assertEquals(3 * 3 * 4, res.size());
         }
 
         @Test
         void permutationTest1() {
-                var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' },
-                                new Object[] { "alpha", "beta", "gamma", "delta" });
+                var res = FuzzTestUtils.permutation(new Object[]{1, 2, 3}, new Object[]{'a', 'b', 'c'},
+                                new Object[]{"alpha", "beta", "gamma", "delta"});
                 assertEquals(3 * 3 * 4, res.count());
         }
 
         @Test
         void permutationTest2() {
-                var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' },
-                                new Object[] { "alpha", "beta", "gamma", "delta" });
-                var arguments = res.findFirst().get().get();
+                var res = FuzzTestUtils.permutation(new Object[]{1, 2, 3}, new Object[]{'a', 'b', 'c'},
+                                new Object[]{"alpha", "beta", "gamma", "delta"});
+                Optional<Arguments> first = res.findFirst();
+                assertTrue(first.isPresent());
+                var arguments = first.get().get();
                 assertEquals(1, arguments[0]);
                 assertEquals('a', arguments[1]);
                 assertEquals("alpha", arguments[2]);
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
index f861f496..e7348370 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
@@ -14,9 +14,14 @@ import java.util.Map.Entry;
 import static org.junit.jupiter.api.Assertions.*;
 
 public class MapTestEnvironment<K, V> {
-        public static String[] prepareValues(int maxValue) {
+        public static String[] prepareValues(int maxValue, boolean nullDefault) {
                 String[] values = new String[maxValue];
-                values[0] = "DEFAULT";
+                if (nullDefault) {
+                        values[0] = null;
+                } else {
+                        values[0] = "DEFAULT";
+                }
+
                 for (int i = 1; i < values.length; i++) {
                         values[i] = "VAL" + i;
                 }
@@ -26,23 +31,18 @@ public class MapTestEnvironment<K, V> {
         public static ContinousHashProvider<Integer> prepareHashProvider(final boolean evil) {
                 // Use maxPrime = 2147483629
 
-                ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() {
-
-                        @Override
-                        public int getHash(Integer key, int index) {
-                                if (evil && index < 15 && index < key / 3) {
-                                        return 7;
-                                }
-                                int result = 1;
-                                final int prime = 31;
+                return (key, index) -> {
+                        if (evil && index < 15 && index < key / 3) {
+                                return 7;
+                        }
+                        int result = 1;
+                        final int prime = 31;
 
-                                result = prime * result + key;
-                                result = prime * result + index;
+                        result = prime * result + key;
+                        result = prime * result + index;
 
-                                return result;
-                        }
+                        return result;
                 };
-                return chp;
         }
 
         public static void printStatus(String scenario, int actual, int max, String stepName) {
@@ -60,29 +60,17 @@ public class MapTestEnvironment<K, V> {
 
         public static <K, V> void compareTwoMaps(String title, VersionedMap<K, V> map1,
                                                                                          VersionedMap<K, V> map2, List<Throwable> errors) {
-                assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors);
+                map1.checkIntegrity();
+                map2.checkIntegrity();
 
-                Cursor<K, V> cursor1 = map1.getAll();
-                Cursor<K, V> cursor2 = map2.getAll();
-                while (!cursor1.isTerminated()) {
-                        if (cursor2.isTerminated()) {
-                                fail("cursor 2 terminated before cursor1");
-                        }
-                        assertEqualsList(cursor1.getKey(), cursor2.getKey(), title + ": Keys not equal", errors);
-                        assertEqualsList(cursor2.getValue(), cursor2.getValue(), title + ": Values not equal", errors);
-                        cursor1.move();
-                        cursor2.move();
-                }
-                if (!cursor2.isTerminated()) {
-                        fail("cursor 1 terminated before cursor 2");
-                }
+                assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors);
+                assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors);
+                assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors);
 
                 for (var mode : ContentHashCode.values()) {
                         assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode),
                                         title + ": " + mode + " hashCode check", errors);
                 }
-                assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors);
-                assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors);
         }
 
         private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) {
@@ -112,29 +100,35 @@ public class MapTestEnvironment<K, V> {
                 }
         }
 
-        public VersionedMapImpl<K, V> sut;
-        Map<K, V> oracle = new HashMap<K, V>();
+        final private VersionedMap<K, V> sut;
+        final private V defaultValue;
+        Map<K, V> oracle = new HashMap<>();
 
-        public MapTestEnvironment(VersionedMapImpl<K, V> sut) {
+        public MapTestEnvironment(VersionedMap<K, V> sut) {
                 this.sut = sut;
+                this.defaultValue = sut.getDefaultValue();
         }
 
         public void put(K key, V value) {
                 V oldSutValue = sut.put(key, value);
                 V oldOracleValue;
-                if (value != sut.getDefaultValue()) {
+                if (value != defaultValue) {
                         oldOracleValue = oracle.put(key, value);
                 } else {
                         oldOracleValue = oracle.remove(key);
                 }
-                if (oldSutValue == sut.getDefaultValue() && oldOracleValue != null) {
+                if (oldSutValue == defaultValue && oldOracleValue != null) {
                         fail("After put, SUT old nodeId was default, but oracle old value was " + oldOracleValue);
                 }
-                if (oldSutValue != sut.getDefaultValue()) {
+                if (oldSutValue != defaultValue) {
                         assertEquals(oldOracleValue, oldSutValue);
                 }
         }
 
+        public long commit(){
+                return sut.commit();
+        }
+
         public void checkEquivalence(String title) {
                 // 0. Checking integrity
                 try {
@@ -181,7 +175,7 @@ public class MapTestEnvironment<K, V> {
                 long sutSize = sut.getSize();
                 if (oracleSize != sutSize || oracleSize != elementsInSutEntrySet) {
                         printComparison();
-                        fail(title + ": Non-equivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entryset.size="
+                        fail(title + ": Non-equivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entrySet.size="
                                         + elementsInSutEntrySet + ", Oracle=" + oracleSize + "!");
                 }
         }
@@ -190,7 +184,8 @@ public class MapTestEnvironment<K, V> {
                 K previous = null;
                 Cursor<K, V> cursor = versionedMap.getAll();
                 while (cursor.move()) {
-                        System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0));
+                        //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider()
+                        // .getHash(cursor.getKey(), 0));
                         if (previous != null) {
                                 int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous,
                                                 cursor.getKey());
@@ -198,7 +193,6 @@ public class MapTestEnvironment<K, V> {
                         }
                         previous = cursor.getKey();
                 }
-                System.out.println();
         }
 
         public void printComparison() {