Tests and iterators

12 files changed, 247 insertions, 19 deletions

diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java
index 3d691407..28264f2f 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java
@@ -6,7 +6,7 @@ import java.util.Map;
 public interface VersionedMap<KEY,VALUE> extends Versioned{
         public void put(KEY key, VALUE value);
         public VALUE get(KEY key);
-        public int getSize();
+        public long getSize();
         public Iterator<Map.Entry<KEY,VALUE>> getIterator();
         public Cursor<KEY,VALUE> getCursor();
 }
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 1e1352ab..c5516cda 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
@@ -43,15 +43,9 @@ public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY,
         }
 
         public long addState(ImmutableNode<KEY,VALUE> data) {
-                if(data != null) {
-                        ImmutableNode<KEY, VALUE> immutable = data.toImmutable();
-                        long id = nextID++;
-                        states.put(id,immutable);
-                        return id;
-                } else {
-                        throw new NullPointerException("data is null!");
-                }
-                
+                long id = nextID++;
+                states.put(id,data);
+                return id;
         }
 //      public void removeState(long state) {
 //              if(states.containsKey(state)) {
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/debug/VersionedMapDebug.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/debug/VersionedMapDebug.java
new file mode 100644
index 00000000..0f5332d2
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/debug/VersionedMapDebug.java
@@ -0,0 +1,53 @@
+package org.eclipse.viatra.solver.data.map.debug;
+
+import java.util.Iterator;
+import java.util.Map.Entry;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+
+public class VersionedMapDebug<KEY, VALUE> implements VersionedMap<KEY, VALUE> {
+
+        @Override
+        public long commit() {
+                // TODO Auto-generated method stub
+                return 0;
+        }
+
+        @Override
+        public void restore(long state) {
+                // TODO Auto-generated method stub
+                
+        }
+
+        @Override
+        public void put(KEY key, VALUE value) {
+                // TODO Auto-generated method stub
+                
+        }
+
+        @Override
+        public VALUE get(KEY key) {
+                // TODO Auto-generated method stub
+                return null;
+        }
+
+        @Override
+        public long getSize() {
+                // TODO Auto-generated method stub
+                return 0;
+        }
+
+        @Override
+        public Iterator<Entry<KEY, VALUE>> getIterator() {
+                // TODO Auto-generated method stub
+                return null;
+        }
+
+        @Override
+        public Cursor<KEY, VALUE> getCursor() {
+                // TODO Auto-generated method stub
+                return null;
+        }
+
+}
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/debug/VersionedMapStoreDebug.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/debug/VersionedMapStoreDebug.java
new file mode 100644
index 00000000..f7c13416
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/debug/VersionedMapStoreDebug.java
@@ -0,0 +1,20 @@
+package org.eclipse.viatra.solver.data.map.debug;
+
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+import org.eclipse.viatra.solver.data.map.VersionedMapStore;
+
+public class VersionedMapStoreDebug<KEY, VALUE> implements VersionedMapStore<KEY, VALUE> {
+
+        @Override
+        public VersionedMap<KEY, VALUE> createMap() {
+                // TODO Auto-generated method stub
+                return null;
+        }
+
+        @Override
+        public VersionedMap<KEY, VALUE> createMap(long state) throws IllegalAccessException {
+                // TODO Auto-generated method stub
+                return null;
+        }
+
+}
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 860c258a..1765a54e 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
@@ -32,7 +32,7 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
         @SuppressWarnings("unchecked")
         protected ImmutableNode(MutableNode<KEY,VALUE> node) {
                 int size = 0;
-                for(int i = 0; i<factor; i++) {
+                for(int i = 0; i<node.content.length; i++) {
                         if(node.content[i]!=null) {
                                 size++;
                         }
@@ -160,7 +160,7 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
         
         @SuppressWarnings("unchecked")
         @Override
-        public int getSize() {
+        public long getSize() {
                 int result = Integer.bitCount(this.dataMap);
                 for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
                         ImmutableNode<KEY,VALUE> subnode = (ImmutableNode<KEY, VALUE>) this.content[this.content.length-1-subnodeIndex];
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
index 9489d110..d658e9d8 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
@@ -1,6 +1,7 @@
 package org.eclipse.viatra.solver.data.map.internal;
 
 import java.util.ArrayDeque;
+import java.util.ConcurrentModificationException;
 import java.util.Deque;
 
 import org.eclipse.viatra.solver.data.map.Cursor;
@@ -19,6 +20,12 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
         KEY key;
         VALUE value;
         
+        // State
+        /**
+         * Dirty bit for Conc
+         */
+        boolean dirty; 
+        
         public MapCursor(Node<KEY, VALUE> root) {
                 // Initializing tree stack
                 super();
@@ -34,6 +41,9 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
                 this.key = null;
                 this.value = null;
                 
+                // Initializing state
+                this.dirty = false;
+                
                 // move to first
                 move();
         }
@@ -51,10 +61,17 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
         }
         
         public boolean move() {
+                if(dirty) {
+                        throw new ConcurrentModificationException();
+                }
                 if(!isTerminated()) {
                         return this.nodeStack.peek().moveToNext(this);
                 } else {
                         return false;
                 }
         }
+        
+        public void setDirty() {
+                this.dirty = 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 b22c7b14..0a6386a5 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
@@ -187,7 +187,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
         
         @SuppressWarnings("unchecked")
         @Override
-        public int getSize() {
+        public long getSize() {
                 int size = 0;
                 for(int i=0; i<factor; i++) {
                         if(content[i*2]!=null) {
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 ee81493f..e7be5684 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
@@ -50,7 +50,7 @@ public abstract class Node<KEY,VALUE>{
         
         abstract public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue,  int hash, int depth);
         abstract public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth);
-        abstract public int getSize();
+        abstract public long getSize();
         
         abstract MutableNode<KEY, VALUE> toMutable();
         public abstract ImmutableNode<KEY, VALUE> toImmutable();
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 92ba17ab..537da4e1 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
@@ -2,6 +2,7 @@ package org.eclipse.viatra.solver.data.map.internal;
 
 import java.util.Iterator;
 import java.util.Map;
+import java.util.WeakHashMap;
 
 import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
 import org.eclipse.viatra.solver.data.map.Cursor;
@@ -21,6 +22,7 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
         protected final ContinousHashProvider<? super KEY> hashProvider;
         protected final VALUE defaultValue;
         protected Node<KEY,VALUE> root;
+        WeakHashMap<MapCursor<KEY, VALUE>, Boolean> iterators;
         //TODO: protected final iterators
         
         public VersionedMapImpl(
@@ -32,6 +34,7 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
                 this.hashProvider = hashProvider;
                 this.defaultValue = defaultValue;
                 this.root = null;
+                iterators = new WeakHashMap<>();
         }
         public VersionedMapImpl(
                         VersionedMapStoreImpl<KEY,VALUE> store,
@@ -42,6 +45,7 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
                 this.hashProvider = hashProvider;
                 this.defaultValue = defaultValue;
                 this.root = data;
+                iterators = new WeakHashMap<>();
         }
                 
         public VALUE getDefaultValue() {
@@ -52,6 +56,9 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
         }
         @Override
         public void put(KEY key, VALUE value) {
+                for(MapCursor<KEY, VALUE> iterator : iterators.keySet()) {
+                        iterator.setDirty();
+                }
                 if(root!=null) {
                         root = root.putValue(key, value, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
                 } else {
@@ -67,7 +74,7 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
                 }
         }
         @Override
-        public int getSize() {
+        public long getSize() {
                 if(root == null) {
                         return 0;
                 } else {
@@ -77,11 +84,15 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
         @Override
         public
         Iterator<Map.Entry<KEY,VALUE>> getIterator() {
-                return new MapEntryIterator<>(this.root);
+                MapEntryIterator<KEY,VALUE> iterator = new MapEntryIterator<>(this.root);
+                iterators.put(iterator, null);
+                return iterator;
         }
         @Override
         public Cursor<KEY, VALUE> getCursor() {
-                return new MapEntryIterator<>(this.root);
+                MapEntryIterator<KEY,VALUE> cursor = new MapEntryIterator<>(this.root);
+                iterators.put(cursor, null);
+                return cursor;
         }
 
         @Override
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java
index 507e8dc2..1dcf7a63 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java
@@ -61,7 +61,7 @@ public class MapTestEnvironment<KEY,VALUE> {
                 // 3. Checking sizes
                 // Counting of non-default value pairs.
                 int oracleSize = oracle.entrySet().size();
-                int sutSize = sut.getSize();
+                long sutSize = sut.getSize();
                 if(oracleSize != sutSize || oracleSize != elementsInSutEntrySet) {
                         printComparison();
                         fail(title + ": Non-eqivalent size() result: SUT.getSize()="+sutSize+", SUT.entryset.size="+elementsInSutEntrySet+", Oracle="+oracleSize+"!" );
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapSmokeTest.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java
index 8532da63..9b08a7bc 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapSmokeTest.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java
@@ -7,7 +7,7 @@ import java.util.Random;
 import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
 import org.junit.jupiter.api.Test;
 
-public class MapSmokeTest {
+public class SmokeTest1Mutable {
         
         private void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue) {
                 String[] values = prepareValues(maxValue);
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java
new file mode 100644
index 00000000..8be9adb6
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java
@@ -0,0 +1,133 @@
+package org.eclipse.viatra.solver.data.map;
+
+import static org.junit.Assert.fail;
+
+import java.util.Random;
+
+import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
+import org.junit.jupiter.api.Test;
+
+public class SmokeTest2Commit {
+        private void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency) {
+                String[] values = prepareValues(maxValue);
+                ContinousHashProvider<Integer> chp = prepareHashProvider();
+                
+                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
+                VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
+                MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
+                
+                Random r = new Random(seed);
+                
+                iterativeRandomPutsAndCommits(scenario, steps, maxKey, values, e, r, commitFrequency);
+        }
+
+
+
+        private String[] prepareValues(int maxValue) {
+                String[] values = new String[maxValue];
+                values[0] = "DEFAULT";
+                for(int i = 1; i<values.length; i++) {
+                        values[i] = "VAL"+i;
+                }
+                return values;
+        }
+        private ContinousHashProvider<Integer> prepareHashProvider() {
+                ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() {
+                        
+                        @Override
+                        public int getHash(Integer key, int index) {
+                                int result = 1;
+                                final int prime = 31;
+                                result = prime*result + key;
+                                result = prime*result + index;
+                                return result;
+                        }
+                        
+                        @Override
+                        public boolean equals(Integer key1, Integer key2) {
+                                return key1.equals(key2);
+                        }
+                };
+                return chp;
+        }
+        
+        void iterativeRandomPutsAndCommits(
+                String scenario,
+                int steps,
+                int maxKey,
+                String[] values,
+                MapTestEnvironment<Integer, String> e,
+                Random r,
+                int commitFrequency)
+        {
+                int stopAt = -1;
+                for(int i=0; i<steps; i++) {
+                        int index = i+1;
+                        int nextKey = r.nextInt(maxKey);
+                        String nextValue = values[r.nextInt(values.length)];
+                        if(index == stopAt) {
+                                System.out.println("issue!");
+                                System.out.println("State before:");
+                                e.printComparison();
+                                e.sut.prettyPrint();
+                                System.out.println("Next: put("+nextKey+","+nextValue+")");
+                        }
+                        try {
+                                e.put(nextKey, nextValue);
+                                if(index == stopAt) {
+                                        e.sut.prettyPrint();
+                                }
+                                e.checkEquivalence(scenario+":"+index);
+                        } catch (Exception exception) {
+                                exception.printStackTrace();
+                                fail(scenario+":"+index+": exception happened: "+exception);
+                        }
+                        if(index%10000==0) System.out.println(scenario+":"+index+" finished");
+                        if(index%commitFrequency == 0) {
+                                long version = e.sut.commit();
+                                System.out.println(scenario+":"+index+": Commit! " + version);
+                        }
+                }
+        }
+        
+        @Test
+        void MiniSmokeK3V2v1() {
+                runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 2, 10);
+        }
+        @Test
+        void MiniSmokeK3V2v2() {
+                runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 2, 10);
+        }
+        @Test
+        void MiniSmokeK3V2v3() {
+                runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 2, 10);
+        }
+        @Test
+        void MiniSmokeK3V3v1() {
+                runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 3, 10);
+        }
+        @Test
+        void MiniSmokeK3V3v2() {
+                runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 3, 10);
+        }
+        @Test
+        void MiniSmokeK3V3v3() {
+                runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 3, 10);
+        }
+        @Test
+        void MediumSmokeK3V2v1() {
+                runSmokeTest("MediumSmokeK3V2v1",1, 1000, 32, 2, 10);
+        }
+        @Test
+        void MediumSmokeK3V2v2() {
+                runSmokeTest("MediumSmokeK3V2v2",2, 1000, 32, 2, 10);
+        }
+        @Test
+        void MediumSmokeK3V2v3() {
+                runSmokeTest("MediumSmokeK3V2v3",3, 1000, 32, 2, 10);
+        }
+//      @Test
+//      void SmokeLarge() {
+//              runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2);
+//      }
+}