From 8dec6434f6c598476cf4917bb8c3297e0fabec1f Mon Sep 17 00:00:00 2001 From: Oszkar Semerath Date: Wed, 28 Jul 2021 15:10:13 +0200 Subject: Updated cursor interface, removed inefficient iterator interface. --- .../org/eclipse/viatra/solver/data/map/Cursor.java | 5 ++ .../eclipse/viatra/solver/data/map/DiffCursor.java | 2 +- .../viatra/solver/data/map/VersionedMap.java | 6 +- .../viatra/solver/data/map/internal/MapCursor.java | 29 ++++++--- .../solver/data/map/internal/MapDiffCursor.java | 76 ++++++++++++++++++---- .../solver/data/map/internal/MapEntryIterator.java | 41 ------------ .../solver/data/map/internal/VersionedMapImpl.java | 38 ++++++++--- 7 files changed, 117 insertions(+), 80 deletions(-) delete mode 100644 Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data') 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 { public KEY getKey(); public VALUE getValue(); public boolean isTerminated(); public boolean move(); + public boolean isDirty(); + + public List> 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 { +public interface DiffCursor extends Cursor { } \ 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 extends Versioned{ public void put(KEY key, VALUE value); public VALUE get(KEY key); public long getSize(); - public Iterator> getIterator(); + public Cursor getCursor(); public DiffCursor getDiffCursor(long state); + public void putAll(Cursor 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 implements Cursor { // Initializing state this.map=map; this.creationHash = map.hashCode(); - - // move to first - move(); } public KEY getKey() { @@ -67,14 +64,29 @@ public class MapCursor implements Cursor { } 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> getDependingMaps() { + return List.of(this.map); + } + + public static boolean sameSubnode(MapCursor cursor1, MapCursor cursor2) { + Node nodeOfCursor1 = cursor1.nodeStack.peek(); + Node nodeOfCursor2 = cursor2.nodeStack.peek(); + return nodeOfCursor1.equals(nodeOfCursor2); + } /** * @@ -106,8 +118,5 @@ public class MapCursor implements Cursor { 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 implements DiffCursor { +public class MapDiffCursor implements DiffCursor, Cursor{ /** * Default value representing missing elements. */ @@ -46,9 +51,24 @@ public class MapDiffCursor implements DiffCursor { 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> 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 implements DiffCursor { } } - 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 - * @param - */ -public class MapEntryIterator extends MapCursor implements Iterator>{ - - public MapEntryIterator(Node root, VersionedMap map) { - super(root,map); - - } - - @Override - public boolean hasNext() { - return !this.isTerminated(); - } - - @Override - public Entry next() { - if(this.hasNext()) { - Map.Entry result = new AbstractMap.SimpleEntry(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 implements VersionedMap{ root = MutableNode.initialize(key, value, hashProvider, defaultValue); } } + + @Override + public void putAll(Cursor cursor) { + if(cursor.getDependingMaps().contains(this)) { + List keys = new LinkedList<>(); + List values = new LinkedList<>(); + while(cursor.move()) { + keys.add(cursor.getKey()); + values.add(cursor.getValue()); + } + Iterator keyIterator = keys.iterator(); + Iterator 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 implements VersionedMap{ return root.getSize(); } } - @Override - public - Iterator> getIterator() { - MapEntryIterator iterator = new MapEntryIterator<>(this.root,this); - return iterator; - } + @Override public Cursor getCursor() { - MapEntryIterator cursor = new MapEntryIterator<>(this.root,this); + MapCursor cursor = new MapCursor<>(this.root,this); return cursor; } @Override - public DiffCursor getDiffCursor(long to) { + public DiffCursor getDiffCursor(long toVersion) { Cursor fromCursor = this.getCursor(); - VersionedMap toMap = this.store.createMap(to); + VersionedMap toMap = this.store.createMap(toVersion); Cursor toCursor = toMap.getCursor(); return new MapDiffCursor(defaultValue, fromCursor, toCursor); -- cgit v1.2.3-70-g09d2