Updated cursor interface, removed inefficient iterator interface.

9 files changed, 235 insertions, 87 deletions

diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/Cursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/Cursor.java
index 81c7a7ec..969f96c9 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/Cursor.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/Cursor.java
@@ -1,8 +1,13 @@
 package org.eclipse.viatra.solver.data.map;
 
+import java.util.List;
+
 public interface Cursor<KEY,VALUE> {
         public KEY getKey();
         public VALUE getValue();
         public boolean isTerminated();
         public boolean move();
+        public boolean isDirty();
+        
+        public List<VersionedMap<KEY,VALUE>> getDependingMaps();
 }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/DiffCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/DiffCursor.java
index d93d26d6..2be2e024 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/DiffCursor.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/DiffCursor.java
@@ -1,5 +1,5 @@
 package org.eclipse.viatra.solver.data.map;
 
-public interface DiffCursor<KEY, VALUE> {
+public interface DiffCursor<KEY, VALUE> extends Cursor<KEY,VALUE> {
 
 }
\ No newline at end of file
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 2754c246..11077dca 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
@@ -1,13 +1,11 @@
 package org.eclipse.viatra.solver.data.map;
 
-import java.util.Iterator;
-import java.util.Map;
-
 public interface VersionedMap<KEY,VALUE> extends Versioned{
         public void put(KEY key, VALUE value);
         public VALUE get(KEY key);
         public long getSize();
-        public Iterator<Map.Entry<KEY,VALUE>> getIterator();
+        
         public Cursor<KEY,VALUE> getCursor();
         public DiffCursor<KEY,VALUE> getDiffCursor(long state);
+        public void putAll(Cursor<KEY,VALUE> cursor);
 }
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 bfbf8fcb..5b9d5c7d 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
@@ -2,8 +2,8 @@ package org.eclipse.viatra.solver.data.map.internal;
 
 import java.util.ArrayDeque;
 import java.util.ConcurrentModificationException;
-import java.util.Deque;
 import java.util.Iterator;
+import java.util.List;
 
 import org.eclipse.viatra.solver.data.map.Cursor;
 import org.eclipse.viatra.solver.data.map.VersionedMap;
@@ -44,9 +44,6 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
                 // Initializing state
                 this.map=map;
                 this.creationHash = map.hashCode();
-                
-                // move to first
-                move();
         }
         
         public KEY getKey() {
@@ -67,14 +64,29 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
                 }
                 if(!isTerminated()) {
                         return this.nodeStack.peek().moveToNext(this);
-                } else {
-                        return false;
                 }
+                return false;
         }
-        
+        public boolean skipCurrentNode() {
+                nodeStack.pop();
+                nodeIndexStack.pop();
+                dataIndex = IndexFinish;
+                return move();
+        }
+        @Override
         public boolean isDirty() {
                 return this.map.hashCode() != this.creationHash;
         }
+        @Override
+        public List<VersionedMap<KEY, VALUE>> getDependingMaps() {
+                return List.of(this.map);
+        }
+        
+        public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) {
+                Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek();
+                Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek();
+                return nodeOfCursor1.equals(nodeOfCursor2);
+        }
         
         /**
          * 
@@ -106,8 +118,5 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
                         return 1;
                 }
                 return Integer.compare(cursor1.dataIndex, cursor2.dataIndex);
-                
-                        
-                        
         }
 }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
index 3e0a823e..5c911bb4 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
@@ -1,14 +1,19 @@
 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.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<KEY,VALUE> implements DiffCursor<KEY, VALUE> {
+public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor<KEY,VALUE>{
         /**
          * Default value representing missing elements.
          */
@@ -46,9 +51,24 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE> {
         public VALUE getValue2() {
                 return value2;
         }
+        @Override
+        public VALUE getValue() {
+                return this.value2;
+        }
         public boolean isTerminated() {
                 return cursor1.isTerminated() && cursor2.isTerminated();
         }
+        @Override
+        public boolean isDirty() {
+                return this.cursor1.isDirty() || this.cursor2.isDirty();
+        }
+        @Override
+        public List<VersionedMap<KEY, VALUE>> getDependingMaps() {
+                return Stream.concat(
+                                cursor1.getDependingMaps().stream(),
+                                cursor2.getDependingMaps().stream()
+                        ).collect(Collectors.toList());
+        }
         
         protected void updateState() {
                 this.cursorRelation = MapCursor.compare(cursor1, cursor2);
@@ -72,33 +92,61 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE> {
                 }
         }
         
-        protected boolean canStop() {
+        protected boolean differentValues() {
                 return this.value1 != this.value2;
         }
-        protected void moveOne() {
+        protected boolean moveOne() {
                 if(isTerminated()) {
                         throw new IllegalStateException("DiffCursor tries to move when terminated!");
                 }
                 if(this.cursorRelation > 0 || cursor2.isTerminated()) {
-                        cursor1.move();
+                        return cursor1.move();
                 } else if(this.cursorRelation < 0 || cursor1.isTerminated()) {
-                        cursor2.move();
+                        return cursor2.move();
                 } else {
-                        cursor1.move();
-                        cursor2.move();
+                        boolean moved1 = cursor1.move();
+                        boolean moved2 = cursor2.move();
+                        return moved1 && moved2;
                 }
-                updateState();
         }
-        protected void moveToConsistentState() {
-                while(!canStop() && !isTerminated()) {
-                        moveOne();
+        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;
         }
         
-        public void move() {
+        protected boolean moveToConsistentState() {
                 if(!isTerminated()) {
-                        moveOne();
-                        moveToConsistentState();
+                        boolean changed;
+                        boolean lastResult = true;
+                        do {
+                                changed = false;
+                                if(MapCursor.sameSubnode(cursor1, cursor2)) {
+                                        lastResult = skipNode();
+                                        changed = true;
+                                }
+                                if(differentValues()) {
+                                        lastResult = moveOne();
+                                        changed = true;
+                                }
+                        } while(changed && !isTerminated());
+                        return lastResult;
+                } else {
+                        return false;
                 }
         }
+        
+        public boolean move() {
+                if(!isTerminated()) {
+                        if(moveOne()) {
+                                return moveToConsistentState();
+                        } else {
+                                return false;
+                        }
+                } else return false;
+        }
 }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java
deleted file mode 100644
index e471af31..00000000
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java
+++ /dev/null
@@ -1,41 +0,0 @@
-package org.eclipse.viatra.solver.data.map.internal;
-
-import java.util.AbstractMap;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.Map.Entry;
-import java.util.NoSuchElementException;
-
-import org.eclipse.viatra.solver.data.map.VersionedMap;
-
-/**
- * Preorder iterator for map {@link #Node}s. 
- * 
- * @author Oszkar Semerath
- *
- * @param <KEY>
- * @param <VALUE>
- */
-public class MapEntryIterator<KEY,VALUE> extends MapCursor<KEY, VALUE> implements Iterator<Map.Entry<KEY,VALUE>>{
-
-        public MapEntryIterator(Node<KEY, VALUE> root, VersionedMap<KEY,VALUE> map) {
-                super(root,map);
-
-        }
-        
-        @Override
-        public boolean hasNext() {
-                return !this.isTerminated();
-        }
-
-        @Override
-        public Entry<KEY, VALUE> next() {
-                if(this.hasNext()) {
-                        Map.Entry<KEY, VALUE> result = new AbstractMap.SimpleEntry<KEY, VALUE>(this.key, this.value);
-                        this.move();
-                        return result;
-                } else {
-                        throw new NoSuchElementException();
-                }
-        }
-}
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 4fb8d7f8..fcee6f46 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
@@ -1,7 +1,8 @@
 package org.eclipse.viatra.solver.data.map.internal;
 
 import java.util.Iterator;
-import java.util.Map;
+import java.util.LinkedList;
+import java.util.List;
 
 import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
 import org.eclipse.viatra.solver.data.map.Cursor;
@@ -58,6 +59,28 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
                         root = MutableNode.initialize(key, value, hashProvider, defaultValue);
                 }
         }
+        
+        @Override
+        public void putAll(Cursor<KEY, VALUE> cursor) {
+                if(cursor.getDependingMaps().contains(this)) {
+                        List<KEY> keys = new LinkedList<>();
+                        List<VALUE> values = new LinkedList<>();
+                        while(cursor.move()) {
+                                keys.add(cursor.getKey());
+                                values.add(cursor.getValue());
+                        }
+                        Iterator<KEY> keyIterator = keys.iterator();
+                        Iterator<VALUE> valueIterator = values.iterator();
+                        while(keyIterator.hasNext()) {
+                                this.put(keyIterator.next(), valueIterator.next());
+                        }
+                } else {
+                        while(cursor.move()) {
+                                this.put(cursor.getKey(), cursor.getValue());
+                        }
+                }
+        }
+        
         @Override
         public VALUE get(KEY key) {
                 if(root!=null) {
@@ -74,21 +97,16 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
                         return root.getSize();
                 }
         }
-        @Override
-        public
-        Iterator<Map.Entry<KEY,VALUE>> getIterator() {
-                MapEntryIterator<KEY,VALUE> iterator = new MapEntryIterator<>(this.root,this);
-                return iterator;
-        }
+
         @Override
         public Cursor<KEY, VALUE> getCursor() {
-                MapEntryIterator<KEY,VALUE> cursor = new MapEntryIterator<>(this.root,this);
+                MapCursor<KEY,VALUE> cursor = new MapCursor<>(this.root,this);
                 return cursor;
         }
         @Override
-        public DiffCursor<KEY, VALUE> getDiffCursor(long to) {
+        public DiffCursor<KEY, VALUE> getDiffCursor(long toVersion) {
                 Cursor<KEY, VALUE> fromCursor = this.getCursor();
-                VersionedMap<KEY, VALUE> toMap = this.store.createMap(to);
+                VersionedMap<KEY, VALUE> toMap = this.store.createMap(toVersion);
                 Cursor<KEY, VALUE> toCursor = toMap.getCursor();
                 return new MapDiffCursor<KEY, VALUE>(defaultValue, fromCursor, toCursor);
                 
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/smoke/fast/SmokeTest5DiffCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/smoke/fast/SmokeTest5DiffCursor.java
index d25b6303..94324e96 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/smoke/fast/SmokeTest5DiffCursor.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/smoke/fast/SmokeTest5DiffCursor.java
@@ -1,5 +1,108 @@
 package org.eclipse.viatra.solver.data.map.test.smoke.fast;
 
-public class SmokeTest5DiffCursor {
+import static org.junit.Assert.fail;
+
+import java.util.Random;
+import java.util.stream.Stream;
 
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+import org.eclipse.viatra.solver.data.map.VersionedMapStore;
+import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
+import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
+import org.eclipse.viatra.solver.data.map.test.smoke.TestPermuter;
+import org.eclipse.viatra.solver.data.map.test.support.MapTestEnvironment;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class SmokeTest5DiffCursor {
+        public void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, boolean evilHash) {
+                String[] values = MapTestEnvironment.prepareValues(maxValue);
+                ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
+                
+                VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
+                iterativeRandomPutsAndCommitsThenDiffcursor(scenario,store, steps, maxKey, values,  seed, commitFrequency);
+        }
+        
+        void iterativeRandomPutsAndCommitsThenDiffcursor(
+                String scenario,
+                VersionedMapStore<Integer, String> store,
+                int steps,
+                int maxKey,
+                String[] values,
+                int seed,
+                int commitFrequency)
+        {
+                // 1. build a map with versions
+                Random r = new Random(seed);
+                VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
+                int largestCommit=-1;
+                
+                for(int i=0; i<steps; i++) {
+                        int index = i+1;
+                        int nextKey = r.nextInt(maxKey);
+                        String nextValue = values[r.nextInt(values.length)];
+                        try {
+                                versioned.put(nextKey, nextValue);
+                        } catch (Exception exception) {
+                                exception.printStackTrace();
+                                fail(scenario+":"+index+": exception happened: "+exception);
+                        }
+                        if(index%commitFrequency == 0) {
+                                long version = versioned.commit();
+                                largestCommit=(int) version;
+                        }
+                        if(index%10000==0) System.out.println(scenario+":"+index+"/"+steps+" building finished");
+                }
+                // 2. create a non-versioned map,  
+                VersionedMapImpl<Integer, String> moving = (VersionedMapImpl<Integer, String>) store.createMap();
+                Random r2 = new Random(seed+1);
+                
+                final int diffTravelFrequency = commitFrequency*2;
+                for(int i=0; i<steps; i++) {
+                        int index = i+1;
+                        if(index%diffTravelFrequency == 0) {
+                                // difftravel
+                                long travelToVersion = r2.nextInt(largestCommit+1);
+                                DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
+                                moving.putAll(diffCursor);
+                                
+                        } else {
+                                // random puts
+                                int nextKey = r2.nextInt(maxKey);
+                                String nextValue = values[r2.nextInt(values.length)];
+                                try {
+                                        moving.put(nextKey, nextValue);
+                                } catch (Exception exception) {
+                                        exception.printStackTrace();
+                                        fail(scenario+":"+index+": exception happened: "+exception);
+                                }
+                                if(index%commitFrequency == 0) {
+                                        versioned.commit();
+                                }
+                                if(index%10000==0) System.out.println(scenario+":"+index+"/"+steps+" building finished");
+                        }
+                }
+                
+                
+                
+        }
+        
+        @ParameterizedTest(name = "Mutable-Immutable Compare Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @MethodSource
+        void parametrizedSmoke(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, boolean evilHash) {
+                runSmokeTest("SmokeMutableImmutableCompareS"+steps+"K"+noKeys+"V"+noValues+"s"+seed,seed,steps,noKeys,noValues,commitFrequency,evilHash);
+        }
+        
+        public static Stream<Arguments> parametrizedSmoke(){
+                return TestPermuter.permutationWithSize(
+                        new Object[] {1000},
+                        new Object[] {3,32, 32*32},
+                        new Object[] {2,3},
+                        new Object[] {1,10,100},
+                        new Object[] {1,2,3},
+                        new Object[] {false,true}
+                );
+        }
 }
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/support/MapTestEnvironment.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/support/MapTestEnvironment.java
index 1ff29d68..8c86eb4d 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/support/MapTestEnvironment.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/test/support/MapTestEnvironment.java
@@ -114,12 +114,11 @@ public class MapTestEnvironment<KEY,VALUE> {
                 // Tests iterators
                 // TODO: Counts the number of elements in the entryset
                 int elementsInSutEntrySet = 0;
-                Iterator<Entry<KEY, VALUE>> iterator = sut.getIterator();
-                while(iterator.hasNext()) {
+                Cursor<KEY, VALUE> cursor = sut.getCursor();
+                while(cursor.move()) {
                         elementsInSutEntrySet++;
-                        Entry<KEY, VALUE> entry = iterator.next();
-                        KEY key = entry.getKey();
-                        VALUE sutValue = entry.getValue();
+                        KEY key = cursor.getKey();
+                        VALUE sutValue = cursor.getValue();
                         //System.out.println(key + " -> " + sutValue);
                         VALUE oracleValue = oracle.get(key);
                         if(sutValue != oracleValue) {
@@ -142,7 +141,7 @@ public class MapTestEnvironment<KEY,VALUE> {
         }
         public void printComparison() {
                 System.out.println("SUT:");
-                printEntrySet(sut.getIterator());
+                printEntrySet(sut.getCursor());
                 System.out.println("Oracle:");
                 printEntrySet(oracle.entrySet().iterator());
         }
@@ -156,4 +155,13 @@ public class MapTestEnvironment<KEY,VALUE> {
                         System.out.println("\t" + e.getKey() + " -> " + e.getValue());
                 }
         }
+        private void printEntrySet(Cursor<KEY, VALUE> cursor) {
+                TreeMap<KEY, VALUE> treemap= new TreeMap<>();
+                while(cursor.move()) {
+                        treemap.put(cursor.getKey(),cursor.getValue());
+                }
+                for(Entry<KEY, VALUE> e : treemap.entrySet()) {
+                        System.out.println("\t" + e.getKey() + " -> " + e.getValue());
+                }
+        }
 }