Merged nodes in cache

5 files changed, 207 insertions, 32 deletions

diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
index c5516cda..d115833e 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
@@ -3,14 +3,18 @@ package org.eclipse.viatra.solver.data.map;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
+import java.util.WeakHashMap;
 
 import org.eclipse.viatra.solver.data.map.internal.ImmutableNode;
+import org.eclipse.viatra.solver.data.map.internal.Node;
 import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
 
 public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY, VALUE> {
         protected final ContinousHashProvider<? super KEY> hashProvider;
         protected final VALUE defaultValue;
+        
         protected Map<Long, ImmutableNode<KEY,VALUE>> states;
+        protected WeakHashMap<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache;
         protected long nextID;
         
         public VersionedMapStoreImpl(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue) {
@@ -42,8 +46,12 @@ public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY,
                 return states.get(state);
         }
 
+        private long getNextID() {
+                if(nextID == Long.MAX_VALUE) throw new IllegalStateException("Map store run out of Id-s");
+                return nextID++;
+        }
         public long addState(ImmutableNode<KEY,VALUE> data) {
-                long id = nextID++;
+                long id = getNextID();
                 states.put(id,data);
                 return id;
         }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
index 1765a54e..daff1af1 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
@@ -1,36 +1,54 @@
 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<KEY, VALUE> extends Node<KEY, VALUE> {
         /**
          * Bitmap defining the stored key and values.
          */
-        int dataMap;
+        final int dataMap;
         /**
          * Bitmap defining the positions of further nodes.
          */
-        int nodeMap;
+        final int nodeMap;
         /**
          * Stores Keys, Values, and subnodes. Structure: (KEY,VALUE)*,NODE; NODES are stored backwards. 
          */
-        Object[] content;
+        final Object[] content;
         
         /**
-         * Constructor with given content
+         * Hash code derived from immutable hash code
          */
-        protected ImmutableNode(int dataMap, int nodeMap, Object[] content) {
+        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
          */
         @SuppressWarnings("unchecked")
-        protected ImmutableNode(MutableNode<KEY,VALUE> node) {
+        static <KEY,VALUE> ImmutableNode<KEY,VALUE> constructImmutable(MutableNode<KEY,VALUE> node, Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
+                // 1. try to return from cache
+                ImmutableNode<KEY, VALUE> cachedResult = cache.get(node);
+                if(cachedResult != null) {
+                        // 1.1 Already cached, return from cache.
+                        return cachedResult;
+                }
+                
+                // 2. otherwise construct a new ImmutableNode
+                
+                final int resultHash = node.hashCode();
+                
                 int size = 0;
                 for(int i = 0; i<node.content.length; i++) {
                         if(node.content[i]!=null) {
@@ -40,28 +58,30 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
                 
                 int datas = 0;
                 int nodes = 0;
-                this.dataMap = 0;
-                this.nodeMap = 0;
-                this.content = new Object[size];
+                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) {
-                                dataMap |= bitposition;
-                                content[datas*2] = key;
-                                content[datas*2+1] = node.content[i*2+1];
+                                resultDataMap |= bitposition;
+                                resultContent[datas*2] = key;
+                                resultContent[datas*2+1] = node.content[i*2+1];
                                 datas++;
                         } else {
                                 Node<KEY,VALUE> subnode = (Node<KEY, VALUE>) node.content[i*2+1];
                                 if(subnode != null) {
-                                        ImmutableNode<KEY, VALUE> immutableSubnode = subnode.toImmutable();
-                                        nodeMap |=bitposition;
-                                        content[size-1-nodes] = immutableSubnode;
+                                        ImmutableNode<KEY, VALUE> immutableSubnode = subnode.toImmutable(cache);
+                                        resultNodeMap |=bitposition;
+                                        resultContent[size-1-nodes] = immutableSubnode;
                                         nodes++;
                                 }
                         }
                         bitposition<<=1;
                 }
+                
+                return new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash);
         }
         
         private int index(int bitmap, int bitpos) {
@@ -179,6 +199,12 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
                 return this;
         }
         
+        @Override
+        public ImmutableNode<KEY, VALUE> toImmutable(
+                        Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
+                return this;
+        }
+        
         @SuppressWarnings("unchecked")
         @Override
         boolean moveToNext(MapCursor<KEY, VALUE> cursor) {
@@ -260,4 +286,67 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
                         nodeMask<<=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)
+                                return false;
+                        if (dataMap != other.dataMap)
+                                return false;
+                        if (nodeMap != other.nodeMap)
+                                return false;
+                        if (!Arrays.deepEquals(content, other.content))
+                                return false;
+                        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 = immutable.content[i*2];
+                        if(key != null) {
+                                if(datas*2+nodes+2 <= immutableLength) {
+                                        if(     mutable.content[datas*2]        != key ||
+                                                mutable.content[datas*2+1]      != immutable.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) {
+                                                Node<?,?> immutableSubnode = (Node<?, ?>) immutable.content[immutableLength-1-nodes];
+                                                if(!mutableSubnode.equals(immutableSubnode)) {
+                                                        return false;
+                                                }
+                                                nodes++;
+                                        }
+                                }
+                        }
+                }
+                return true;
+        }
+        
 }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
index 0a6386a5..6e177d9f 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -1,11 +1,17 @@
 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<KEY,VALUE> extends Node<KEY,VALUE> {
-        Object[] content;
+        int cachedHash;
+        protected Object[] content;
+        
         protected MutableNode() {
                 this.content = new Object[2*factor];
+                updateHash();
         }
         public static <KEY,VALUE> MutableNode<KEY,VALUE> initialize(
                         KEY key, VALUE value,
@@ -24,6 +30,10 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                 }
         }
         
+        /**
+         * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
+         * @param node
+         */
         protected MutableNode(ImmutableNode<KEY,VALUE> node) {
                 this.content = new Object[2*factor]; 
                 int dataUsed=0;
@@ -39,6 +49,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                                 nodeUsed++;
                         }
                 }
+                updateHash();
         }
         
         @SuppressWarnings("unchecked")
@@ -57,7 +68,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                         if(nodeCandidate != null) {
                                 int newHash = newHash(hashProvider, key, hash, depth);
                                 int newDepth = depth+1;
-                                return (VALUE) nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
+                                return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
                         } else {
                                 return defaultValue;
                         }
@@ -89,6 +100,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                         
                         subNode.content[newFragment2*2]=key2;
                         subNode.content[newFragment2*2+1]=value2;
+                        subNode.updateHash();
                         return subNode;
                 } else {
                         MutableNode<KEY,VALUE> subSubNode = createNewNode(
@@ -97,6 +109,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                                         key2, value2, newHash2,
                                         newdepth+1);
                         subNode.content[newFragment1*2+1] = subSubNode;
+                        subNode.updateHash();
                         return subNode;
                 }
         }
@@ -112,8 +125,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                                 if(value == defaultValue) {
                                         return removeEntry(selectedHashFragment);
                                 } else {
-                                        content[2*selectedHashFragment+1] = value;
-                                        return this;
+                                        return updateValue(value,selectedHashFragment);
                                 }
                         } else {
                                 if(value == defaultValue) {
@@ -134,30 +146,50 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                                         // dont need to add new key-value pair
                                         return this;
                                 } else {
-                                        content[2*selectedHashFragment] = key;
-                                        content[2*selectedHashFragment+1] = value;
-                                        return this;
+                                        return addEntry(key, value, selectedHashFragment);
                                 }
                                 
                         }
                 }
         }
-        
+
+        private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) {
+                content[2*selectedHashFragment] = key;
+                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
+         */
         Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) {
                 content[2*selectedHashFragment+1] = value;
+                updateHash();
                 return this;
         }
         
+        /**
+         * 
+         * @param selectedHashFragment
+         * @param newNode
+         * @return
+         */
         Node<KEY, VALUE> updateSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode) {
                 content[2*selectedHashFragment+1] = newNode;
                 for(int i = 0; i<this.content.length; i++) {
-                        if(content[i]!=null) return this;
+                        if(content[i]!=null) {
+                                updateHash();
+                                return this;
+                        }
                 }
                 return null;
         }
         
         @SuppressWarnings("unchecked")
-        Node<KEY, VALUE> moveDown(
+        private Node<KEY, VALUE> moveDown(
                         KEY key, VALUE value,
                         ContinousHashProvider<? super KEY> hashProvider, int hash,
                         int depth, int selectedHashFragment, KEY keyCandidate) {
@@ -172,6 +204,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                 
                 content[2*selectedHashFragment] = null;
                 content[2*selectedHashFragment+1] = subNode;
+                updateHash();
                 return this;
         }
         
@@ -179,6 +212,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                 content[2*selectedHashFragment] = null;
                 content[2*selectedHashFragment+1] = null;
                 if(hasContent()) {
+                        updateHash();
                         return this;
                 } else {
                         return null;
@@ -209,7 +243,12 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
         
         @Override
         public ImmutableNode<KEY,VALUE> toImmutable() {
-                return new ImmutableNode<KEY,VALUE>(this);
+                return ImmutableNode.constructImmutable(this,null);
+        }
+        
+        @Override
+        public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
+                return ImmutableNode.constructImmutable(this,cache);
         }
         
         @SuppressWarnings("unchecked")
@@ -295,4 +334,42 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                         }
                 }
         }
+        
+        protected void updateHash() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + Arrays.deepHashCode(content);
+                this.cachedHash = result;
+        }
+        
+        @Override
+        public int hashCode() {
+                return this.cachedHash;
+        }
+        
+        public void checkHashCodeConsistency() {
+                int oldHash = this.hashCode();
+                updateHash();
+                int newHash = this.hashCode();
+                if(oldHash != newHash) {
+                        throw new IllegalStateException("Inconsistent hash code!");
+                }
+        }
+        
+        @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/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java
index e7be5684..7d547dce 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java
@@ -1,5 +1,7 @@
 package org.eclipse.viatra.solver.data.map.internal;
 
+import java.util.Map;
+
 import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
 
 public abstract class Node<KEY,VALUE>{
@@ -54,6 +56,8 @@ public abstract class Node<KEY,VALUE>{
         
         abstract MutableNode<KEY, VALUE> toMutable();
         public abstract ImmutableNode<KEY, VALUE> toImmutable();
+        public abstract ImmutableNode<KEY, VALUE> toImmutable(
+                        Map<Node<KEY, VALUE>,ImmutableNode<KEY, VALUE>> cache);
         
         /**
          * Moves a {@link MapCursor} to its next position.
@@ -62,9 +66,6 @@ public abstract class Node<KEY,VALUE>{
          */
         abstract boolean moveToNext(MapCursor<KEY,VALUE> cursor);
         
-        ///////// For iterators
-        //abstract boolean moveIteratorToNextData(NodeIterator<KEY,VALUE> iterator, int currentIndex);
-        //abstract boolean moveIteratorToNextNode(NodeIterator<KEY,VALUE> iterator, int currentIndex);
         ///////// FOR printing
         abstract public void prettyPrint(StringBuilder builder, int depth, int code);
         @Override
@@ -73,4 +74,5 @@ public abstract class Node<KEY,VALUE>{
                 prettyPrint(stringBuilder, 0, -1);
                 return stringBuilder.toString();
         }
+        
 }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
index 537da4e1..ad734932 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
@@ -23,7 +23,6 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
         protected final VALUE defaultValue;
         protected Node<KEY,VALUE> root;
         WeakHashMap<MapCursor<KEY, VALUE>, Boolean> iterators;
-        //TODO: protected final iterators
         
         public VersionedMapImpl(
                         VersionedMapStoreImpl<KEY,VALUE> store,