build: migration to Gradle 7

17 files changed, 1837 insertions, 0 deletions

diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
new file mode 100644
index 00000000..dd64f901
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
@@ -0,0 +1,69 @@
+package org.eclipse.viatra.solver.data.map;
+
+import org.eclipse.viatra.solver.data.map.internal.Node;
+
+/**
+ * A class representing an equivalence relation for a type {@code K} with a
+ * continuous hash function.
+ * 
+ * @author Oszkar Semerath
+ *
+ * @param <K> Target java type.
+ */
+public interface ContinousHashProvider<K> {
+        public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
+        public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1;
+
+        /**
+         * Maximal practical depth for differentiating keys. If two keys have the same
+         * hash code until that depth, the algorithm can stop.
+         */
+        public static final int MAX_PRACTICAL_DEPTH = 500;
+
+        /**
+         * Provides a hash code for a object {@code key} with a given {@code index}. It
+         * has the following contracts:
+         * <ul>
+         * <li>If {@link #equals}{@code (key1,key2)}, then
+         * {@code getHash(key1, index) == getHash(key2, index)} for all values of
+         * {@code index}.</li>
+         * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of
+         * {@code index}, then {@link #equals}{@code (key1, key2)}</li>
+         * <li>In current implementation, we use only the least significant
+         * {@link #EFFECTIVE_BITS}
+         * </ul>
+         * Check {@link #equals} for further details.
+         * 
+         * @param key   The target data object.
+         * @param index The depth of the the hash code. Needs to be non-negative.
+         * @return A hash code.
+         */
+        public int getHash(K key, int index);
+
+        public default int getEffectiveHash(K key, int index) {
+                return getHash(key, index) & EFFECTIVE_BIT_MASK;
+        }
+
+        public default int compare(K key1, K key2) {
+                if (key1.equals(key2)) {
+                        return 0;
+                } else {
+                        for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
+                                int hash1 = getEffectiveHash(key1, i);
+                                int hash2 = getEffectiveHash(key2, i);
+                                for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
+                                        final int factorMask = (1<<Node.BRANCHING_FACTOR_BITS)-1;
+                                        int hashFragment1 = (hash1>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
+                                        int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
+                                        var result = Integer.compare(hashFragment1, hashFragment2);
+                                        if (result != 0) {
+                                                return result;
+                                        }
+                                }
+                        }
+                        throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
+                                        + ") have the same hashcode over the practical depth limitation ("
+                                        + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
new file mode 100644
index 00000000..e45b1f20
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
@@ -0,0 +1,14 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.List;
+
+public interface Cursor<K,V> {
+        public K getKey();
+        public V getValue();
+        public boolean isTerminated();
+        public boolean move();
+        public boolean isDirty();
+        
+        @SuppressWarnings("squid:S1452")
+        public List<VersionedMap<?,?>> getDependingMaps();
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java
new file mode 100644
index 00000000..b29b3119
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java
@@ -0,0 +1,57 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.function.BiFunction;
+import java.util.function.BiPredicate;
+
+public class CursorAsIterator<K,V,D> implements Iterator<D> {
+        private final Cursor<K, V> internal;
+        private final BiFunction<K, V, D> entryTransformation;
+        private final BiPredicate<K,V> filtering;
+        
+        D lastValidElement;
+        
+        public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = filtering;
+                
+                moveToNext();
+        }
+        public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = ((k,v)->true);
+                
+                moveToNext();
+        }
+        
+        private void moveToNext() {
+                internal.move();
+                while(!internal.isTerminated() && !filtering.test(internal.getKey(), internal.getValue())) {
+                        internal.move();
+                }
+                if(!internal.isTerminated()) {
+                        lastValidElement = entryTransformation.apply(internal.getKey(), internal.getValue());
+                }
+        }
+        
+        
+        @Override
+        public boolean hasNext() {
+                return !internal.isTerminated();
+        }
+        @Override
+        public D next() {
+                if(hasNext()) {
+                        D last = lastValidElement;
+                        moveToNext();
+                        return last;
+                } else {
+                        throw new NoSuchElementException();
+                }
+
+        }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
new file mode 100644
index 00000000..f0af1436
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
@@ -0,0 +1,6 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface DiffCursor<K, V> extends Cursor<K,V> {
+        public V getFromValue();
+        public V getToValue();
+}
\ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java
new file mode 100644
index 00000000..22b5e6c1
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java
@@ -0,0 +1,26 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.Iterator;
+import java.util.function.BiFunction;
+import java.util.function.BiPredicate;
+
+public class MapAsIterable<K,V,D> implements Iterable<D> {
+        private final VersionedMap<K, V> internal;
+        private final BiFunction<K, V, D> entryTransformation;
+        private final BiPredicate<K,V> filtering;
+        
+        public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = filtering;
+        }
+        public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation) {
+                this.internal = internal;
+                this.entryTransformation = entryTransformation;
+                this.filtering = ((k,v)->true);
+        }
+        @Override
+        public Iterator<D> iterator() {
+                return new CursorAsIterator<>(internal.getAll(), entryTransformation, filtering);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
new file mode 100644
index 00000000..e46be237
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
@@ -0,0 +1,7 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface Versioned {
+        public long commit();
+        //maybe revert()?
+        public void restore(long state);
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
new file mode 100644
index 00000000..3a35b9f0
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
@@ -0,0 +1,13 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface VersionedMap<K,V> extends Versioned{
+        public V get(K key);
+        public Cursor<K,V> getAll();
+        
+        public V put(K key, V value);
+        public void putAll(Cursor<K,V> cursor);
+        
+        public long getSize();
+        
+        public DiffCursor<K,V> getDiffCursor(long state);
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
new file mode 100644
index 00000000..0ff0773f
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
@@ -0,0 +1,14 @@
+package org.eclipse.viatra.solver.data.map;
+
+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();
+
+        public DiffCursor<K,V> getDiffCursor(long fromState, long toState);
+}
\ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
new file mode 100644
index 00000000..be768e98
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
@@ -0,0 +1,48 @@
+package org.eclipse.viatra.solver.data.map;
+
+public class VersionedMapStoreConfiguration {
+        
+        public VersionedMapStoreConfiguration() {
+                
+        }
+        public VersionedMapStoreConfiguration(boolean immutableWhenCommiting, boolean sharedNodeCacheInStore,
+                        boolean sharedNodeCacheInStoreGroups) {
+                super();
+                this.immutableWhenCommiting = immutableWhenCommiting;
+                this.sharedNodeCacheInStore = sharedNodeCacheInStore;
+                this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups;
+        }
+
+        /**
+         * If true root is replaced with immutable node when committed. Frees up memory
+         * by releasing immutable nodes, but it may decrease performance by recreating
+         * immutable nodes upon changes (some evidence).
+         */
+        private boolean immutableWhenCommiting = true;
+        public boolean isImmutableWhenCommiting() {
+                return immutableWhenCommiting;
+        }
+
+        /**
+         * If true, all subnodes are cached within a {@link VersionedMapStore}. It
+         * decreases the memory requirements. It may increase performance by discovering
+         * existing immutable copy of a node (some evidence). Additional overhead may
+         * decrease performance (no example found). The option permits the efficient
+         * implementation of version deletion.
+         */
+        private boolean sharedNodeCacheInStore = true;
+        public boolean isSharedNodeCacheInStore() {
+                return sharedNodeCacheInStore;
+        }
+        
+        /**
+         * If true, all subnodes are cached within a group of
+         * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}.
+         * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is
+         * <code>false</code>, then it has currently no impact.
+         */
+        private boolean sharedNodeCacheInStoreGroups = true;
+        public boolean isSharedNodeCacheInStoreGroups() {
+                return sharedNodeCacheInStoreGroups;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
new file mode 100644
index 00000000..83d0e8cd
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
@@ -0,0 +1,135 @@
+package org.eclipse.viatra.solver.data.map;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.viatra.solver.data.map.internal.ImmutableNode;
+import org.eclipse.viatra.solver.data.map.internal.MapDiffCursor;
+import org.eclipse.viatra.solver.data.map.internal.Node;
+import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
+
+public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
+        // Configuration
+        private final boolean immutableWhenCommiting;
+
+        // Static data
+        protected final ContinousHashProvider<K> hashProvider;
+        protected final V defaultValue;
+
+        // Dynamic data
+        protected final Map<Long, ImmutableNode<K, V>> states = new HashMap<>();
+        protected final Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
+        protected long nextID = 0;
+
+        public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
+                        VersionedMapStoreConfiguration config) {
+                this.immutableWhenCommiting = config.isImmutableWhenCommiting();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                if (config.isSharedNodeCacheInStore()) {
+                        nodeCache = new HashMap<>();
+                } else {
+                        nodeCache = null;
+                }
+        }
+
+        private VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
+                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache, VersionedMapStoreConfiguration config) {
+                this.immutableWhenCommiting = config.isImmutableWhenCommiting();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.nodeCache = nodeCache;
+        }
+
+        public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue) {
+                this(hashProvider, defaultValue, new VersionedMapStoreConfiguration());
+        }
+
+        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
+                        ContinousHashProvider<K> hashProvider, V defaultValue,
+                        VersionedMapStoreConfiguration config) {
+                List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
+                if (config.isSharedNodeCacheInStoreGroups()) {
+                        Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
+                        if (config.isSharedNodeCacheInStore()) {
+                                nodeCache = new HashMap<>();
+                        } else {
+                                nodeCache = null;
+                        }
+                        for (int i = 0; i < amount; i++) {
+                                result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config));
+                        }
+                } else {
+                        for (int i = 0; i < amount; i++) {
+                                result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config));
+                        }
+                }
+                return result;
+        }
+
+        public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
+                        ContinousHashProvider<K> hashProvider, V defaultValue) {
+                return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration());
+        }
+        
+        @Override
+        public synchronized Set<Long> getStates() {
+                return new HashSet<>(states.keySet());
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap() {
+                return new VersionedMapImpl<>(this, hashProvider, defaultValue);
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap(long state) {
+                ImmutableNode<K, V> data = revert(state);
+                return new VersionedMapImpl<>(this, hashProvider, defaultValue, data);
+        }
+        
+
+        public synchronized ImmutableNode<K, V> revert(long state) {
+                if (states.containsKey(state)) {
+                        return states.get(state);
+                } else {
+                        ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
+                        Collections.sort(existingKeys);
+                        throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: "
+                                        + Arrays.toString(existingKeys.toArray()));
+                }
+        }
+
+        public synchronized long commit(Node<K, V> data, VersionedMapImpl<K, V> mapToUpdateRoot) {
+                ImmutableNode<K, V> immutable;
+                if (data != null) {
+                        immutable = data.toImmutable(this.nodeCache);
+                } else {
+                        immutable = null;
+                }
+
+                if (nextID == Long.MAX_VALUE)
+                        throw new IllegalStateException("Map store run out of Id-s");
+                long id = nextID++;
+                this.states.put(id, immutable);
+                if (this.immutableWhenCommiting) {
+                        mapToUpdateRoot.setRoot(immutable);
+                }
+                return id;
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
+                VersionedMap<K, V> map1 = createMap(fromState);
+                VersionedMap<K, V> map2 = createMap(toState);
+                Cursor<K, V> cursor1 = map1.getAll();
+                Cursor<K, V> cursor2 = map2.getAll();
+                return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2);
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
new file mode 100644
index 00000000..04a9b19a
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
@@ -0,0 +1,379 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Arrays;
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class ImmutableNode<K, V> extends Node<K, V> {
+        /**
+         * Bitmap defining the stored key and values.
+         */
+        final int dataMap;
+        /**
+         * Bitmap defining the positions of further nodes.
+         */
+        final int nodeMap;
+        /**
+         * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored backwards. 
+         */
+        final Object[] content;
+        
+        /**
+         * Hash code derived from immutable hash code
+         */
+        final int precalculatedHash;
+                
+        private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) {
+                super();
+                this.dataMap = dataMap;
+                this.nodeMap = nodeMap;
+                this.content = content;
+                this.precalculatedHash = precalculatedHash;
+        }
+
+        /**
+         * Constructor that copies a mutable node to an immutable.
+         * 
+         * @param node  A mutable node.
+         * @param cache A cache of existing immutable nodes. It can be used to search
+         *              and place reference immutable nodes. It can be null, if no cache
+         *              available.
+         * @return an immutable version of the input node.
+         */
+        @SuppressWarnings("unchecked")
+        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);
+                        if(cachedResult != null) {
+                                // 1.1 Already cached, return from cache.
+                                return cachedResult;
+                        }
+                }
+                
+                // 2. otherwise construct a new ImmutableNode
+                int size = 0;
+                for(int i = 0; i<node.content.length; i++) {
+                        if(node.content[i]!=null) {
+                                size++;
+                        }
+                }
+                
+                int datas = 0;
+                int nodes = 0;
+                int resultDataMap = 0;
+                int resultNodeMap = 0;
+                final Object[] resultContent = new Object[size];
+                int bitposition = 1;
+                for(int i = 0; i<FACTOR; i++) {
+                        Object key = node.content[i*2];
+                        if(key != null) {
+                                resultDataMap |= bitposition;
+                                resultContent[datas*2] = key;
+                                resultContent[datas*2+1] = node.content[i*2+1];
+                                datas++;
+                        } else {
+                                Node<K,V> 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;
+                                        nodes++;
+                                }
+                        }
+                        bitposition<<=1;
+                }
+                final int resultHash = node.hashCode();
+                ImmutableNode<K,V> newImmutable = new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash);
+                
+                // 3. save new immutable.
+                if(cache != null) {
+                        cache.put(newImmutable, newImmutable);
+                }
+                return newImmutable;
+        }
+        
+        private int index(int bitmap, int bitpos) {
+                return Integer.bitCount(bitmap & (bitpos-1));
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+                int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
+                int bitposition = 1 << selectedHashFragment;
+                // If the key is stored as a data
+                if((dataMap & bitposition) != 0) {
+                        int keyIndex = 2*index(dataMap, bitposition);
+                        K keyCandidate = (K) content[keyIndex];
+                        if(keyCandidate.equals(key)) {
+                                return (V) content[keyIndex+1];
+                        } else {
+                                return defaultValue;
+                        }
+                }
+                // the key is stored as a node
+                else if((nodeMap & bitposition) != 0) {
+                        int keyIndex = content.length-1-index(nodeMap, bitposition);
+                        ImmutableNode<K,V> subNode = (ImmutableNode<K,V>) content[keyIndex];
+                        int newDepth = depth+1;
+                        int newHash = newHash(hashProvider, key, hash, newDepth);
+                        return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
+                }
+                // the key is not stored at all
+                else {
+                        return defaultValue;
+                }
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        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);
+                        K keyCandidate = (K) content[keyIndex];
+                        if(keyCandidate.equals(key)) {
+                                if(value == defaultValue) {
+                                        // delete
+                                        MutableNode<K, V> mutable = this.toMutable();
+                                        return mutable.removeEntry(selectedHashFragment,oldValue);
+                                } else if(value == content[keyIndex+1]) {
+                                        // dont change
+                                        oldValue.setOldValue(value);
+                                        return this;
+                                } else {
+                                        // update existing value
+                                        MutableNode<K, V> mutable = this.toMutable();
+                                        return mutable.updateValue(value, oldValue, selectedHashFragment);
+                                }
+                        } else {
+                                if(value == defaultValue) {
+                                        // dont change
+                                        oldValue.setOldValue(defaultValue);
+                                        return this;
+                                } else {
+                                        // 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);
+                        ImmutableNode<K,V> subNode = (ImmutableNode<K,V>) content[keyIndex];
+                        int newDepth = depth+1;
+                        int newHash = newHash(hashProvider, key, hash, newDepth);
+                        Node<K,V> newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth);
+                        
+                        if(subNode == newsubNode) {
+                                // nothing changed
+                                return this;
+                        } else {
+                                MutableNode<K, V> mutable  = toMutable();
+                                return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue));
+                        }
+                } else {
+                        // add new key + value
+                        MutableNode<K, V> mutable = this.toMutable();
+                        return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
+                }
+        }
+        
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public long getSize() {
+                int result = Integer.bitCount(this.dataMap);
+                for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
+                        ImmutableNode<K,V> subnode =
+                                (ImmutableNode<K, V>) this.content[this.content.length-1-subnodeIndex];
+                        result += subnode.getSize();
+                }
+                return result;
+        }
+        
+        @Override
+        protected MutableNode<K,V> toMutable() {
+                return new MutableNode<>(this);
+        }
+        
+        @Override
+        public ImmutableNode<K, V> toImmutable(
+                        Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+                return this;
+        }
+        
+        @Override
+        protected MutableNode<K, V> isMutable() {
+                return null;
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        boolean moveToNext(MapCursor<K, V> cursor) {
+                // 1. try to move to data
+                int datas = Integer.bitCount(this.dataMap);
+                if(cursor.dataIndex != MapCursor.INDEX_FINISH) {
+                        int newDataIndex = cursor.dataIndex + 1;
+                        if(newDataIndex < datas) {
+                                cursor.dataIndex = newDataIndex;
+                                cursor.key = (K) this.content[newDataIndex*2];
+                                cursor.value = (V) this.content[newDataIndex*2+1];
+                                return true;
+                        } else {
+                                cursor.dataIndex = MapCursor.INDEX_FINISH;
+                        }
+                }
+                
+                // 2. look inside the subnodes
+                int nodes = Integer.bitCount(this.nodeMap);
+                int newNodeIndex = cursor.nodeIndexStack.peek() + 1;
+                if(newNodeIndex < nodes) {
+                        // 2.1 found next subnode, move down to the subnode
+                        Node<K, V> subnode = (Node<K, V>) this.content[this.content.length-1-newNodeIndex];
+                        cursor.dataIndex = MapCursor.INDEX_START;
+                        cursor.nodeIndexStack.pop();
+                        cursor.nodeIndexStack.push(newNodeIndex);
+                        cursor.nodeIndexStack.push(MapCursor.INDEX_START);
+                        cursor.nodeStack.push(subnode);
+                        return subnode.moveToNext(cursor);
+                } else {
+                        // 3. no subnode found, move up
+                        cursor.nodeStack.pop();
+                        cursor.nodeIndexStack.pop();
+                        if(!cursor.nodeStack.isEmpty()) {
+                                Node<K, V> supernode = cursor.nodeStack.peek();
+                                return supernode.moveToNext(cursor);
+                        } else {
+                                cursor.key = null;
+                                cursor.value = null;
+                                return false;
+                        }
+                }
+        }
+        
+        @Override
+        public void prettyPrint(StringBuilder builder, int depth, int code) {
+                for(int i = 0; i<depth; i++) {
+                        builder.append("\t");
+                }
+                if(code>=0) {
+                        builder.append(code);
+                        builder.append(":");
+                }
+                builder.append("Immutable(");
+                boolean hadContent = false;
+                int dataMask = 1;
+                for(int i = 0; i<FACTOR; i++) {
+                        if((dataMask & dataMap) != 0) {
+                                if(hadContent) {
+                                        builder.append(",");
+                                }
+                                builder.append(i);
+                                builder.append(":[");
+                                builder.append(content[2*index(dataMap, dataMask)].toString());
+                                builder.append("]->[");
+                                builder.append(content[2*index(dataMap, dataMask)+1].toString());
+                                builder.append("]");
+                                hadContent = true;
+                        }
+                        dataMask<<=1;
+                }
+                builder.append(")");
+                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)];
+                                builder.append("\n");
+                                subNode.prettyPrint(builder, depth+1, i);
+                        }
+                        nodeMask<<=1;
+                }
+        }
+        
+        @SuppressWarnings("unchecked")
+        @Override
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+                if(depth>0) {
+                        boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0;
+                        if(orphaned) {
+                                throw new IllegalStateException("Orphaned node! " + dataMap + ": " +  content[0]);
+                        }
+                }
+                // check the place of data
+                
+                // check subnodes
+                for(int i = 0; i<Integer.bitCount(nodeMap); i++) {
+                        Node<K,V> 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);
+                        }
+                }
+        }
+        
+        @Override
+        public int hashCode() {
+                return this.precalculatedHash;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (obj instanceof ImmutableNode<?,?>) {
+                        ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj;
+                        if (precalculatedHash != other.precalculatedHash || dataMap != other.dataMap || nodeMap != other.nodeMap || !Arrays.deepEquals(content, other.content))
+                                return false;
+                        else return true;
+                } else if(obj instanceof MutableNode<?,?>) {
+                        return ImmutableNode.compareImmutableMutable(this, (MutableNode<?, ?>) obj);
+                } else {
+                        return false;
+                }
+        }
+        public static boolean compareImmutableMutable(
+                        ImmutableNode<?, ?> immutable,
+                        MutableNode<?, ?> mutable)
+        {
+                int datas = 0;
+                int nodes = 0;
+                final int immutableLength = immutable.content.length;
+                for(int i = 0; i<FACTOR; i++) {
+                        Object key = mutable.content[i*2];
+                        // For each key candidate
+                        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]))
+                                        {
+                                                return false;
+                                        }
+                                } else return false;
+                                datas++;
+                        } else {
+                                Node<?,?> 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)) {
+                                                        return false;
+                                                }
+                                                nodes++;
+                                        } else {
+                                                return false;
+                                        }
+                                }
+                        }
+                }
+                return true;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
new file mode 100644
index 00000000..cc5a3982
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
@@ -0,0 +1,131 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.ArrayDeque;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+
+public class MapCursor<K,V> implements Cursor<K,V> {
+        // Constants
+        static final int INDEX_START = -1;
+        static final int INDEX_FINISH = -2;
+        
+        // Tree stack
+        ArrayDeque<Node<K,V>> nodeStack;
+        ArrayDeque<Integer> nodeIndexStack;
+        int dataIndex;
+        
+        // Values
+        K key;
+        V value;
+        
+        // Hash code for checking concurrent modifications
+        final VersionedMap<K,V> map;
+        final int creationHash; 
+        
+        public MapCursor(Node<K, V> root, VersionedMap<K,V> map) {
+                // Initializing tree stack
+                super();
+                this.nodeStack = new ArrayDeque<>();
+                this.nodeIndexStack = new ArrayDeque<>();
+                if(root != null) {
+                        this.nodeStack.add(root);
+                        this.nodeIndexStack.push(INDEX_START);
+                }
+                
+                this.dataIndex = INDEX_START;
+                
+                // Initializing cache
+                this.key = null;
+                this.value = null;
+                
+                // Initializing state
+                this.map=map;
+                this.creationHash = map.hashCode();
+        }
+        
+        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()) {
+                        boolean result = this.nodeStack.peek().moveToNext(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();
+                dataIndex = INDEX_FINISH;
+                return move();
+        }
+        @Override
+        public boolean isDirty() {
+                return this.map.hashCode() != this.creationHash;
+        }
+        @Override
+        public List<VersionedMap<?, ?>> getDependingMaps() {
+                return List.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/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
new file mode 100644
index 00000000..e97e4aa1
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
@@ -0,0 +1,214 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+
+/**
+ * A cursor representing the difference between two states of a map.
+ * @author Oszkar Semerath
+ *
+ */
+public class MapDiffCursor<K,V> implements DiffCursor<K, V>, Cursor<K,V>{
+        /**
+         * Default value representing missing elements.
+         */
+        private V defaultValue;
+        private MapCursor<K,V> cursor1;
+        private MapCursor<K,V> cursor2;
+        private ContinousHashProvider<? super K> hashProvider;
+        
+        // Values
+        private K key;
+        private V fromValue;
+        private V toValue;
+        
+        // State
+        /**
+         * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
+         */
+        private int cursorRelation;
+        /**
+         * Denotes a state when two cursors are in the same position, but they contain different keys.
+         * Possible values:
+         * <ul>
+         * <li>0: not stuck</li>
+         * <li>1: hashClash, next it should return the key of cursor 1.</li>
+         * <li>2: hashClash, next it should return the key of cursor 2.</li>
+         * </ul>
+         */
+        private int hashClash=0;
+        
+        public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, Cursor<K, V> cursor2) {
+                super();
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.cursor1 = (MapCursor<K, V>) cursor1;
+                this.cursor2 = (MapCursor<K, V>) cursor2;
+        }
+        @Override
+        public K getKey() {
+                return key;
+        }
+        @Override
+        public V getFromValue() {
+                return fromValue;
+        }
+        @Override
+        public V getToValue() {
+                return toValue;
+        }
+        @Override
+        public V getValue() {
+                return getToValue();
+        }
+        public boolean isTerminated() {
+                return cursor1.isTerminated() && cursor2.isTerminated();
+        }
+        @Override
+        public boolean isDirty() {
+                return this.cursor1.isDirty() || this.cursor2.isDirty();
+        }
+        @Override
+        public List<VersionedMap<?, ?>> getDependingMaps() {
+                return Stream.concat(
+                                cursor1.getDependingMaps().stream(),
+                                cursor2.getDependingMaps().stream()
+                        ).collect(Collectors.toList());
+        }
+        
+        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 {
+                                        resolveHashClash1();
+                                }
+                        }
+                }
+        }
+        protected void resolveHashClash1() {
+                int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key);
+                if(compareResult<0) {
+                        this.hashClash = 2;
+                        this.cursorRelation = 0;
+                        this.key = cursor1.key;
+                        this.fromValue = cursor1.value;
+                        this.toValue = defaultValue;
+                } else if(compareResult>0) {
+                        this.hashClash = 1;
+                        this.cursorRelation = 0;
+                        this.key = cursor2.key;
+                        this.fromValue = defaultValue;
+                        this.toValue = cursor2.value;
+                } else {
+                        throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
+                }
+        }
+        protected boolean isInHashClash() {
+                return this.hashClash != 0;
+        }
+        protected void resolveHashClash2() {
+                if(hashClash == 1) {
+                        this.hashClash = 0;
+                        this.cursorRelation = 0;
+                        this.key = cursor1.key;
+                        this.fromValue = cursor1.value;
+                        this.toValue = defaultValue;
+                } else if(hashClash == 2) {
+                        this.hashClash = 0;
+                        this.cursorRelation = 0;
+                        this.key = cursor2.key;
+                        this.fromValue = defaultValue;
+                        this.toValue = cursor2.value;
+                } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
+        }
+
+        
+        protected boolean sameValues() {
+                if(this.fromValue == null) {
+                        return this.toValue == null;
+                } else {
+                        return this.fromValue.equals(this.toValue);
+                }
+        }
+        protected boolean moveOne() {
+                if(isTerminated()) {
+                        return false;
+                }
+                if(this.cursorRelation > 0 || cursor2.isTerminated()) {
+                        return cursor1.move();
+                } else if(this.cursorRelation < 0 || cursor1.isTerminated()) {
+                        return cursor2.move();
+                } else {
+                        boolean moved1 = cursor1.move();
+                        boolean moved2 = cursor2.move();
+                        return moved1 && moved2;
+                }
+        }
+        private boolean skipNode() {
+                if(isTerminated()) {
+                        throw new IllegalStateException("DiffCursor tries to skip when terminated!");
+                }
+                boolean update1 = cursor1.skipCurrentNode();
+                boolean update2 = cursor2.skipCurrentNode();
+                updateState();
+                return update1 && update2;
+        }
+        
+        protected boolean moveToConsistentState() {
+                if(!isTerminated()) {
+                        boolean changed;
+                        boolean lastResult = true;
+                        do {
+                                changed = false;
+                                if(MapCursor.sameSubnode(cursor1, cursor2)) {
+                                        lastResult = skipNode();
+                                        changed = true;
+                                }
+                                if(sameValues()) {
+                                        lastResult = moveOne();
+                                        changed = true;
+                                }
+                                updateState();
+                        } while(changed && !isTerminated());
+                        return lastResult;
+                } else {
+                        return false;
+                }
+        }
+        
+        public boolean move() {
+                if(!isTerminated()) {
+                        if(isInHashClash()) {
+                                this.resolveHashClash2();
+                                return true;
+                        } else {
+                                if(moveOne()) {
+                                        return moveToConsistentState();
+                                } else {
+                                        return false;
+                                }
+                        }
+                        
+                } else return false;
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
new file mode 100644
index 00000000..9e63b941
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -0,0 +1,449 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Arrays;
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class MutableNode<K, V> extends Node<K, V> {
+        int cachedHash;
+        protected Object[] content;
+
+        protected MutableNode() {
+                this.content = new Object[2 * FACTOR];
+                updateHash();
+        }
+
+        public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider,
+                        V defaultValue) {
+                if (value == defaultValue) {
+                        return null;
+                } else {
+                        int hash = hashProvider.getHash(key, 0);
+                        int fragment = hashFragment(hash, 0);
+                        MutableNode<K, V> res = new MutableNode<>();
+                        res.content[2 * fragment] = key;
+                        res.content[2 * fragment + 1] = value;
+                        res.updateHash();
+                        return res;
+                }
+        }
+
+        /**
+         * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
+         * 
+         * @param node
+         */
+        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) {
+                                content[2 * i] = node.content[dataUsed * 2];
+                                content[2 * i + 1] = node.content[dataUsed * 2 + 1];
+                                dataUsed++;
+                        } else if ((node.nodeMap & bitposition) != 0) {
+                                content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed];
+                                nodeUsed++;
+                        }
+                }
+                this.cachedHash = node.hashCode();
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
+                int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
+                K keyCandidate = (K) this.content[2 * selectedHashFragment];
+                if (keyCandidate != null) {
+                        if (keyCandidate.equals(key)) {
+                                return (V) this.content[2 * selectedHashFragment + 1];
+                        } else {
+                                return defaultValue;
+                        }
+                } else {
+                        Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        if (nodeCandidate != null) {
+                                int newDepth = depth + 1;
+                                int newHash = newHash(hashProvider, key, hash, newDepth);
+                                return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
+                        } else {
+                                return defaultValue;
+                        }
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        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));
+                K keyCandidate = (K) content[2 * selectedHashFragment];
+                if (keyCandidate != null) {
+                        // If has key
+                        if (keyCandidate.equals(key)) {
+                                // The key is equals to an existing key -> update entry
+                                if (value == defaultValue) {
+                                        return removeEntry(selectedHashFragment, oldValue);
+                                } else {
+                                        return updateValue(value, oldValue, selectedHashFragment);
+                                }
+                        } else {
+                                // The key is not equivalent to an existing key on the same hash bin
+                                // -> split entry if it is necessary
+                                if (value == defaultValue) {
+                                        // Value is default -> do not need to add new node
+                                        oldValue.setOldValue(defaultValue);
+                                        return this;
+                                } else {
+                                        // Value is not default -> Split entry data to a new node
+                                        oldValue.setOldValue(defaultValue);
+                                        return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
+                                }
+                        }
+                } else {
+                        // If it does not have key, check for value
+                        Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        if (nodeCandidate != null) {
+                                // If it has value, it is a subnode -> upate that
+                                Node<K, V> newNode = nodeCandidate.putValue(key, value, oldValue, hashProvider, defaultValue,
+                                                newHash(hashProvider, key, hash, depth + 1), depth + 1);
+                                return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
+                        } else {
+                                // If it does not have value, put it in the empty place
+                                if (value == defaultValue) {
+                                        // dont need to add new key-value pair
+                                        oldValue.setOldValue(defaultValue);
+                                        return this;
+                                } else {
+                                        return addEntry(key, value, oldValue, selectedHashFragment);
+                                }
+
+                        }
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        private Node<K, V> addEntry(K key, V value, OldValueBox<V> oldValue, int selectedHashFragment) {
+                content[2 * selectedHashFragment] = key;
+                oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
+                content[2 * selectedHashFragment + 1] = value;
+                updateHash();
+                return this;
+        }
+
+        /**
+         * Updates an entry in a selected hash-fragment to a non-default value.
+         * 
+         * @param value
+         * @param selectedHashFragment
+         * @return
+         */
+        @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();
+                return this;
+        }
+
+        /**
+         * 
+         * @param selectedHashFragment
+         * @param newNode
+         * @return
+         */
+        Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
+                if (deletionHappened) {
+                        if (newNode == null) {
+                                // Check whether this node become empty
+                                content[2 * selectedHashFragment + 1] = null; // i.e. the new node
+                                if (hasContent()) {
+                                        updateHash();
+                                        return this;
+                                } else {
+                                        return null;
+                                }
+                        } else {
+                                // check whether newNode is orphan
+                                MutableNode<K, V> immutableNewNode = newNode.isMutable();
+                                if (immutableNewNode != null) {
+                                        int orphaned = immutableNewNode.isOrphaned();
+                                        if (orphaned >= 0) {
+                                                // orphan subnode data is replaced with data
+                                                content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
+                                                content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
+                                                updateHash();
+                                                return this;
+                                        }
+                                }
+                        }
+                }
+                // normal behaviour
+                content[2 * selectedHashFragment + 1] = newNode;
+                updateHash();
+                return this;
+
+        }
+
+        private boolean hasContent() {
+                for (Object element : this.content) {
+                        if (element != null)
+                                return true;
+                }
+                return false;
+        }
+
+        @Override
+        protected MutableNode<K, V> isMutable() {
+                return this;
+        }
+
+        protected int isOrphaned() {
+                int dataFound = -2;
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[i * 2] != null) {
+                                if (dataFound >= 0) {
+                                        return -1;
+                                } else {
+                                        dataFound = i;
+                                }
+                        } else if (content[i * 2 + 1] != null) {
+                                return -3;
+                        }
+                }
+                return dataFound;
+        }
+
+        @SuppressWarnings("unchecked")
+        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);
+
+                content[2 * selectedHashFragmentOfCurrentDepth] = null;
+                content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
+                updateHash();
+                return this;
+        }
+
+        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) {
+                        subNode.content[newFragment1 * 2] = key1;
+                        subNode.content[newFragment1 * 2 + 1] = value1;
+
+                        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);
+                        subNode.content[newFragment1 * 2 + 1] = subSubNode;
+                }
+                subNode.updateHash();
+                return subNode;
+        }
+
+        @SuppressWarnings("unchecked")
+        Node<K, V> removeEntry(int selectedHashFragment, OldValueBox<V> oldValue) {
+                content[2 * selectedHashFragment] = null;
+                oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
+                content[2 * selectedHashFragment + 1] = null;
+                if (hasContent()) {
+                        updateHash();
+                        return this;
+                } else {
+                        return null;
+                }
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public long getSize() {
+                int size = 0;
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[i * 2] != null) {
+                                size++;
+                        } else {
+                                Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1];
+                                if (nodeCandidate != null) {
+                                        size += nodeCandidate.getSize();
+                                }
+                        }
+                }
+                return size;
+        }
+
+        @Override
+        protected MutableNode<K, V> toMutable() {
+                return this;
+        }
+
+        @Override
+        public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+                return ImmutableNode.constructImmutable(this, cache);
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        boolean moveToNext(MapCursor<K, V> cursor) {
+                // 1. try to move to data
+                if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
+                        for (int index = cursor.dataIndex + 1; index < FACTOR; index++) {
+                                if (this.content[index * 2] != null) {
+                                        // 1.1 found next data
+                                        cursor.dataIndex = index;
+                                        cursor.key = (K) this.content[index * 2];
+                                        cursor.value = (V) this.content[index * 2 + 1];
+                                        return true;
+                                }
+                        }
+                        cursor.dataIndex = MapCursor.INDEX_FINISH;
+                }
+
+                // 2. look inside the subnodes
+                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
+                                Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
+
+                                cursor.dataIndex = MapCursor.INDEX_START;
+                                cursor.nodeIndexStack.pop();
+                                cursor.nodeIndexStack.push(index);
+                                cursor.nodeIndexStack.push(MapCursor.INDEX_START);
+                                cursor.nodeStack.push(subnode);
+
+                                return subnode.moveToNext(cursor);
+                        }
+                }
+                // 3. no subnode found, move up
+                cursor.nodeStack.pop();
+                cursor.nodeIndexStack.pop();
+                if (!cursor.nodeStack.isEmpty()) {
+                        Node<K, V> supernode = cursor.nodeStack.peek();
+                        return supernode.moveToNext(cursor);
+                } else {
+                        cursor.key = null;
+                        cursor.value = null;
+                        return false;
+                }
+        }
+
+        @Override
+        public void prettyPrint(StringBuilder builder, int depth, int code) {
+                for (int i = 0; i < depth; i++) {
+                        builder.append("\t");
+                }
+                if (code >= 0) {
+                        builder.append(code);
+                        builder.append(":");
+                }
+                builder.append("Mutable(");
+                // print content
+                boolean hadContent = false;
+                for (int i = 0; i < FACTOR; i++) {
+                        if (content[2 * i] != null) {
+                                if (hadContent) {
+                                        builder.append(",");
+                                }
+                                builder.append(i);
+                                builder.append(":[");
+                                builder.append(content[2 * i].toString());
+                                builder.append("]->[");
+                                builder.append(content[2 * i + 1].toString());
+                                builder.append("]");
+                                hadContent = true;
+                        }
+                }
+                builder.append(")");
+                // print subnodes
+                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];
+                                builder.append("\n");
+                                subNode.prettyPrint(builder, depth + 1, i);
+                        }
+                }
+        }
+
+        @SuppressWarnings({ "unchecked" })
+        @Override
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+                // check for orphan nodes
+                if (depth > 0) {
+                        int orphaned = isOrphaned();
+                        if (orphaned >= 0) {
+                                throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]);
+                        }
+                }
+                // check the place of data
+                for (int i = 0; i < FACTOR; i++) {
+                        if (this.content[2 * i] != null) {
+                                K key = (K) this.content[2 * i];
+                                V value = (V) this.content[2 * i + 1];
+
+                                if (value == defaultValue) {
+                                        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);
+                                }
+                        }
+                }
+                // check subnodes
+                for (int i = 0; i < FACTOR; i++) {
+                        if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
+                                Node<K, V> subNode = (Node<K, V>) this.content[2 * i + 1];
+                                subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
+                        }
+                }
+                // 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 + ")");
+                }
+        }
+
+        protected void updateHash() {
+                this.cachedHash = Arrays.hashCode(content);
+        }
+
+        @Override
+        public int hashCode() {
+                return this.cachedHash;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (obj instanceof MutableNode<?, ?>) {
+                        MutableNode<?, ?> other = (MutableNode<?, ?>) obj;
+                        return Arrays.deepEquals(this.content, other.content);
+                } else if (obj instanceof ImmutableNode<?, ?>) {
+                        ImmutableNode<?, ?> other = (ImmutableNode<?, ?>) obj;
+                        return ImmutableNode.compareImmutableMutable(other, this);
+                } else {
+                        return false;
+                }
+        }
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
new file mode 100644
index 00000000..d40f980a
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
@@ -0,0 +1,85 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public abstract class Node<K,V>{
+        public static final int BRANCHING_FACTOR_BITS = 5;
+        public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
+        protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
+        protected static final int FACTOR_MASK = FACTOR-1;
+        public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
+        
+        /**
+         * Calculates the index for the continuous hash.
+         * @param depth The depth of the node in the tree.
+         * @return The index of the continuous hash.
+         */
+        protected static int hashDepth(int depth) {
+                return depth/NUMBER_OF_FACTORS;
+        }
+        
+        /**
+         * Calculates the which segment of a single hash should be used.
+         * @param depth The depth of the node in the tree. 
+         * @return The segment of a hash code.
+         */
+        protected static int shiftDepth(int depth) {
+                return depth%NUMBER_OF_FACTORS;
+        }
+        /**
+         * Selects a segments from a complete hash for a given depth.
+         * @param hash A complete hash.
+         * @param shiftDepth The index of the segment.
+         * @return The segment as an integer.
+         */
+        protected static int hashFragment(int hash, int shiftDepth) {
+                if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
+                return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK;
+        }
+        
+        /**
+         * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1.
+         * @param key The key.
+         * @param hash Hash code for depth-1
+         * @param depth The depth.
+         * @return The new hash code.
+         */
+        protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) {
+                final int hashDepth = hashDepth(depth);
+                if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) {
+                        throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!");
+                }
+                return depth%NUMBER_OF_FACTORS == 0?
+                                hashProvider.getHash(key, hashDepth) :
+                                hash;
+        }
+        
+        
+        public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue,  int hash, int depth);
+        public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
+        public abstract long getSize();
+        
+        abstract MutableNode<K, V> toMutable();
+        public abstract ImmutableNode<K, V> toImmutable(
+                        Map<Node<K, V>,ImmutableNode<K, V>> cache);
+        protected abstract MutableNode<K, V> isMutable();
+        /**
+         * Moves a {@link MapCursor} to its next position.
+         * @param cursor the cursor
+         * @return Whether there was a next value to move on.
+         */
+        abstract boolean moveToNext(MapCursor<K,V> cursor);
+        
+        ///////// FOR printing
+        public abstract void prettyPrint(StringBuilder builder, int depth, int code);
+        @Override
+        public String toString() {
+                StringBuilder stringBuilder = new StringBuilder();
+                prettyPrint(stringBuilder, 0, -1);
+                return stringBuilder.toString();
+        }
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java
new file mode 100644
index 00000000..23502857
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java
@@ -0,0 +1,19 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+public class OldValueBox<V>{
+        V oldValue;
+        boolean isSet = false;
+
+        public V getOldValue() {
+                if(!isSet) throw new IllegalStateException();
+                isSet = false;
+                return oldValue;
+        }
+
+        public void setOldValue(V ouldValue) {
+                if(isSet) throw new IllegalStateException();
+                this.oldValue = ouldValue;
+                isSet = true;
+        }
+        
+}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
new file mode 100644
index 00000000..de41e602
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
@@ -0,0 +1,171 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
+
+/**
+ * Not threadSafe in itself
+ * @author Oszkar Semerath
+ *
+ * @param <K>
+ * @param <V>
+ */
+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;
+        
+        private OldValueBox<V> oldValueBox = new OldValueBox<>();
+        
+        public VersionedMapImpl(
+                        VersionedMapStoreImpl<K,V> store,
+                        ContinousHashProvider<K> hashProvider,
+                        V defaultValue)
+        {
+                this.store = store;
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.root = null;
+        }
+        public VersionedMapImpl(
+                        VersionedMapStoreImpl<K,V> store,
+                        ContinousHashProvider<K> hashProvider,
+                        V defaultValue, Node<K,V> data)
+        {
+                this.store = store;
+                this.hashProvider = hashProvider;
+                this.defaultValue = defaultValue;
+                this.root = data;
+        }
+                
+        public V getDefaultValue() {
+                return defaultValue;
+        }
+        public ContinousHashProvider<K> getHashProvider() {
+                return hashProvider;
+        }
+        @Override
+        public V put(K key, V value) {
+                if(root!=null) {
+                        root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
+                        return oldValueBox.getOldValue();
+                } else {
+                        root = MutableNode.initialize(key, value, hashProvider, defaultValue);
+                        return defaultValue;
+                }
+        }
+        
+        @Override
+        public void putAll(Cursor<K, V> cursor) {
+                if(cursor.getDependingMaps().contains(this)) {
+                        List<K> keys = new LinkedList<>();
+                        List<V> values = new LinkedList<>();
+                        while(cursor.move()) {
+                                keys.add(cursor.getKey());
+                                values.add(cursor.getValue());
+                        }
+                        Iterator<K> keyIterator = keys.iterator();
+                        Iterator<V> valueIterator = values.iterator();
+                        while(keyIterator.hasNext()) {
+                                this.put(keyIterator.next(), valueIterator.next());
+                        }
+                } else {
+                        while(cursor.move()) {
+                                this.put(cursor.getKey(), cursor.getValue());
+                        }
+                }
+        }
+        
+        @Override
+        public V get(K key) {
+                if(root!=null) {
+                        return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
+                } else {
+                        return defaultValue;
+                }
+        }
+        @Override
+        public long getSize() {
+                if(root == null) {
+                        return 0;
+                } else {
+                        return root.getSize();
+                }
+        }
+
+        @Override
+        public Cursor<K, V> getAll() {
+                return new MapCursor<>(this.root,this);
+        }
+        @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);
+                
+        }
+        
+
+        @Override
+        public long commit() {
+                return this.store.commit(root,this);
+        }
+        public void setRoot(Node<K, V> root) {
+                this.root = root;
+        }
+
+        @Override
+        public void restore(long state) {
+                root = this.store.revert(state);
+        }
+        
+        @Override
+        public int hashCode() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + ((root == null) ? 0 : root.hashCode());
+                return result;
+        }
+        
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (getClass() != obj.getClass())
+                        return false;
+                VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj;
+                if (root == null) {
+                        if (other.root != null)
+                                return false;
+                } else if (!root.equals(other.root))
+                        return false;
+                return true;
+        }
+        public void prettyPrint() {
+                StringBuilder s = new StringBuilder();
+                if(this.root != null) {
+                        this.root.prettyPrint(s, 0, -1);
+                        System.out.println(s.toString());
+                } else {
+                        System.out.println("empty tree");
+                }
+        }
+        public void checkIntegrity() {
+                if(this.root != null) {
+                        this.root.checkIntegrity(hashProvider, defaultValue, 0);
+                }
+        }
+
+}