Diffcursor, first implementation

3 files changed, 147 insertions, 2 deletions

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
new file mode 100644
index 00000000..d93d26d6
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/DiffCursor.java
@@ -0,0 +1,5 @@
+package org.eclipse.viatra.solver.data.map;
+
+public interface DiffCursor<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/internal/MapCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
index e77d073f..bfbf8fcb 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
@@ -3,6 +3,7 @@ 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 org.eclipse.viatra.solver.data.map.Cursor;
 import org.eclipse.viatra.solver.data.map.VersionedMap;
@@ -13,8 +14,8 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
         static int IndexFinish = -2;
         
         // Tree stack
-        Deque<Node<KEY,VALUE>> nodeStack;
-        Deque<Integer> nodeIndexStack;
+        ArrayDeque<Node<KEY,VALUE>> nodeStack;
+        ArrayDeque<Integer> nodeIndexStack;
         int dataIndex;
         
         // Values
@@ -74,4 +75,39 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
         public boolean isDirty() {
                 return this.map.hashCode() != this.creationHash;
         }
+        
+        /**
+         * 
+         * @param <KEY>
+         * @param <VALUE>
+         * @param cursor1
+         * @param cursor2
+         * @returnv 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 <KEY,VALUE> int compare(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> 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/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
new file mode 100644
index 00000000..3e0a823e
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
@@ -0,0 +1,104 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.DiffCursor;
+
+/**
+ * A cursor representing the difference between two states of a map.
+ * @author Oszkar Semerath
+ *
+ */
+public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE> {
+        /**
+         * Default value representing missing elements.
+         */
+        VALUE defaultValue;
+        MapCursor<KEY,VALUE> cursor1;
+        MapCursor<KEY,VALUE> cursor2;
+        
+        // Values
+        KEY key;
+        VALUE value1;
+        VALUE value2;
+        
+        // State
+        /**
+         * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
+         */
+        int cursorRelation;
+        
+        public MapDiffCursor(VALUE defaultValue, Cursor<KEY, VALUE> cursor1, Cursor<KEY, VALUE> cursor2) {
+                super();
+                this.defaultValue = defaultValue;
+                this.cursor1 = (MapCursor<KEY, VALUE>) cursor1;
+                this.cursor2 = (MapCursor<KEY, VALUE>) cursor2;
+                
+                this.updateState();
+                this.moveToConsistentState();
+        }
+
+        public KEY getKey() {
+                return key;
+        }
+        public VALUE getValue1() {
+                return value1;
+        }
+        public VALUE getValue2() {
+                return value2;
+        }
+        public boolean isTerminated() {
+                return cursor1.isTerminated() && cursor2.isTerminated();
+        }
+        
+        protected void updateState() {
+                this.cursorRelation = MapCursor.compare(cursor1, cursor2);
+                if(cursorRelation > 0 || cursor2.isTerminated()) {
+                        this.key = cursor1.getKey();
+                        this.value1 = cursor1.getValue();
+                        this.value2 = defaultValue;
+                } else if(cursorRelation < 0|| cursor1.isTerminated()){
+                        this.key = cursor2.getKey();
+                        this.value1 = defaultValue;
+                        this.value2 = cursor1.getValue();
+                } else {
+                        // cursor1 = cursor2
+                        if(!cursor1.getKey().equals(cursor2.getKey())) {
+                                throw new IllegalStateException(
+                                        "Cursor comarison tells that they are in the same state, but keys are different. " + cursor1.getKey() + " - " + cursor2.getKey());
+                        }
+                        this.key = cursor1.getKey();
+                        this.value1 = cursor1.getValue();
+                        this.value2 = defaultValue;
+                }
+        }
+        
+        protected boolean canStop() {
+                return this.value1 != this.value2;
+        }
+        protected void moveOne() {
+                if(isTerminated()) {
+                        throw new IllegalStateException("DiffCursor tries to move when terminated!");
+                }
+                if(this.cursorRelation > 0 || cursor2.isTerminated()) {
+                        cursor1.move();
+                } else if(this.cursorRelation < 0 || cursor1.isTerminated()) {
+                        cursor2.move();
+                } else {
+                        cursor1.move();
+                        cursor2.move();
+                }
+                updateState();
+        }
+        protected void moveToConsistentState() {
+                while(!canStop() && !isTerminated()) {
+                        moveOne();
+                }
+        }
+        
+        public void move() {
+                if(!isTerminated()) {
+                        moveOne();
+                        moveToConsistentState();
+                }
+        }
+}