From 49f3565457b25fb62ea8e491614deb97c0d0d72c Mon Sep 17 00:00:00 2001 From: Oszkar Semerath Date: Mon, 26 Jul 2021 01:18:03 +0200 Subject: Diffcursor, first implementation --- .../eclipse/viatra/solver/data/map/DiffCursor.java | 5 + .../viatra/solver/data/map/internal/MapCursor.java | 40 +++++++- .../solver/data/map/internal/MapDiffCursor.java | 104 +++++++++++++++++++++ 3 files changed, 147 insertions(+), 2 deletions(-) create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/DiffCursor.java create mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java (limited to 'Solvers') 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 { + +} \ 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 implements Cursor { static int IndexFinish = -2; // Tree stack - Deque> nodeStack; - Deque nodeIndexStack; + ArrayDeque> nodeStack; + ArrayDeque nodeIndexStack; int dataIndex; // Values @@ -74,4 +75,39 @@ public class MapCursor implements Cursor { public boolean isDirty() { return this.map.hashCode() != this.creationHash; } + + /** + * + * @param + * @param + * @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 int compare(MapCursor cursor1, MapCursor cursor2) { + // two cursors are equally deep + Iterator stack1 = cursor1.nodeIndexStack.descendingIterator(); + Iterator 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 implements DiffCursor { + /** + * Default value representing missing elements. + */ + VALUE defaultValue; + MapCursor cursor1; + MapCursor 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 cursor1, Cursor cursor2) { + super(); + this.defaultValue = defaultValue; + this.cursor1 = (MapCursor) cursor1; + this.cursor2 = (MapCursor) 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(); + } + } +} -- cgit v1.2.3-54-g00ecf