diff options
author | Oszkar Semerath <Oszkar Semerath@DESKTOP-DNR7JQ7> | 2021-07-28 15:10:13 +0200 |
---|---|---|
committer | Oszkar Semerath <Oszkar Semerath@DESKTOP-DNR7JQ7> | 2021-07-28 15:10:13 +0200 |
commit | 8dec6434f6c598476cf4917bb8c3297e0fabec1f (patch) | |
tree | 832db19af94534ac11c5b9e655b3efabf0308465 /Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data | |
parent | MutableNode hash calcultion simplified (diff) | |
download | VIATRA-Generator-8dec6434f6c598476cf4917bb8c3297e0fabec1f.tar.gz VIATRA-Generator-8dec6434f6c598476cf4917bb8c3297e0fabec1f.tar.zst VIATRA-Generator-8dec6434f6c598476cf4917bb8c3297e0fabec1f.zip |
Updated cursor interface, removed inefficient iterator interface.
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data')
7 files changed, 117 insertions, 80 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 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | 1 | package org.eclipse.viatra.solver.data.map; |
2 | 2 | ||
3 | import java.util.List; | ||
4 | |||
3 | public interface Cursor<KEY,VALUE> { | 5 | public interface Cursor<KEY,VALUE> { |
4 | public KEY getKey(); | 6 | public KEY getKey(); |
5 | public VALUE getValue(); | 7 | public VALUE getValue(); |
6 | public boolean isTerminated(); | 8 | public boolean isTerminated(); |
7 | public boolean move(); | 9 | public boolean move(); |
10 | public boolean isDirty(); | ||
11 | |||
12 | public List<VersionedMap<KEY,VALUE>> getDependingMaps(); | ||
8 | } | 13 | } |
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 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | 1 | package org.eclipse.viatra.solver.data.map; |
2 | 2 | ||
3 | public interface DiffCursor<KEY, VALUE> { | 3 | public interface DiffCursor<KEY, VALUE> extends Cursor<KEY,VALUE> { |
4 | 4 | ||
5 | } \ No newline at end of file | 5 | } \ 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 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | 1 | package org.eclipse.viatra.solver.data.map; |
2 | 2 | ||
3 | import java.util.Iterator; | ||
4 | import java.util.Map; | ||
5 | |||
6 | public interface VersionedMap<KEY,VALUE> extends Versioned{ | 3 | public interface VersionedMap<KEY,VALUE> extends Versioned{ |
7 | public void put(KEY key, VALUE value); | 4 | public void put(KEY key, VALUE value); |
8 | public VALUE get(KEY key); | 5 | public VALUE get(KEY key); |
9 | public long getSize(); | 6 | public long getSize(); |
10 | public Iterator<Map.Entry<KEY,VALUE>> getIterator(); | 7 | |
11 | public Cursor<KEY,VALUE> getCursor(); | 8 | public Cursor<KEY,VALUE> getCursor(); |
12 | public DiffCursor<KEY,VALUE> getDiffCursor(long state); | 9 | public DiffCursor<KEY,VALUE> getDiffCursor(long state); |
10 | public void putAll(Cursor<KEY,VALUE> cursor); | ||
13 | } | 11 | } |
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; | |||
2 | 2 | ||
3 | import java.util.ArrayDeque; | 3 | import java.util.ArrayDeque; |
4 | import java.util.ConcurrentModificationException; | 4 | import java.util.ConcurrentModificationException; |
5 | import java.util.Deque; | ||
6 | import java.util.Iterator; | 5 | import java.util.Iterator; |
6 | import java.util.List; | ||
7 | 7 | ||
8 | import org.eclipse.viatra.solver.data.map.Cursor; | 8 | import org.eclipse.viatra.solver.data.map.Cursor; |
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | 9 | import org.eclipse.viatra.solver.data.map.VersionedMap; |
@@ -44,9 +44,6 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | |||
44 | // Initializing state | 44 | // Initializing state |
45 | this.map=map; | 45 | this.map=map; |
46 | this.creationHash = map.hashCode(); | 46 | this.creationHash = map.hashCode(); |
47 | |||
48 | // move to first | ||
49 | move(); | ||
50 | } | 47 | } |
51 | 48 | ||
52 | public KEY getKey() { | 49 | public KEY getKey() { |
@@ -67,14 +64,29 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | |||
67 | } | 64 | } |
68 | if(!isTerminated()) { | 65 | if(!isTerminated()) { |
69 | return this.nodeStack.peek().moveToNext(this); | 66 | return this.nodeStack.peek().moveToNext(this); |
70 | } else { | ||
71 | return false; | ||
72 | } | 67 | } |
68 | return false; | ||
73 | } | 69 | } |
74 | 70 | public boolean skipCurrentNode() { | |
71 | nodeStack.pop(); | ||
72 | nodeIndexStack.pop(); | ||
73 | dataIndex = IndexFinish; | ||
74 | return move(); | ||
75 | } | ||
76 | @Override | ||
75 | public boolean isDirty() { | 77 | public boolean isDirty() { |
76 | return this.map.hashCode() != this.creationHash; | 78 | return this.map.hashCode() != this.creationHash; |
77 | } | 79 | } |
80 | @Override | ||
81 | public List<VersionedMap<KEY, VALUE>> getDependingMaps() { | ||
82 | return List.of(this.map); | ||
83 | } | ||
84 | |||
85 | public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) { | ||
86 | Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
87 | Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
88 | return nodeOfCursor1.equals(nodeOfCursor2); | ||
89 | } | ||
78 | 90 | ||
79 | /** | 91 | /** |
80 | * | 92 | * |
@@ -106,8 +118,5 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | |||
106 | return 1; | 118 | return 1; |
107 | } | 119 | } |
108 | return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); | 120 | return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); |
109 | |||
110 | |||
111 | |||
112 | } | 121 | } |
113 | } | 122 | } |
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 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | 1 | package org.eclipse.viatra.solver.data.map.internal; |
2 | 2 | ||
3 | import java.util.List; | ||
4 | import java.util.stream.Collectors; | ||
5 | import java.util.stream.Stream; | ||
6 | |||
3 | import org.eclipse.viatra.solver.data.map.Cursor; | 7 | import org.eclipse.viatra.solver.data.map.Cursor; |
4 | import org.eclipse.viatra.solver.data.map.DiffCursor; | 8 | import org.eclipse.viatra.solver.data.map.DiffCursor; |
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
5 | 10 | ||
6 | /** | 11 | /** |
7 | * A cursor representing the difference between two states of a map. | 12 | * A cursor representing the difference between two states of a map. |
8 | * @author Oszkar Semerath | 13 | * @author Oszkar Semerath |
9 | * | 14 | * |
10 | */ | 15 | */ |
11 | public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE> { | 16 | public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor<KEY,VALUE>{ |
12 | /** | 17 | /** |
13 | * Default value representing missing elements. | 18 | * Default value representing missing elements. |
14 | */ | 19 | */ |
@@ -46,9 +51,24 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE> { | |||
46 | public VALUE getValue2() { | 51 | public VALUE getValue2() { |
47 | return value2; | 52 | return value2; |
48 | } | 53 | } |
54 | @Override | ||
55 | public VALUE getValue() { | ||
56 | return this.value2; | ||
57 | } | ||
49 | public boolean isTerminated() { | 58 | public boolean isTerminated() { |
50 | return cursor1.isTerminated() && cursor2.isTerminated(); | 59 | return cursor1.isTerminated() && cursor2.isTerminated(); |
51 | } | 60 | } |
61 | @Override | ||
62 | public boolean isDirty() { | ||
63 | return this.cursor1.isDirty() || this.cursor2.isDirty(); | ||
64 | } | ||
65 | @Override | ||
66 | public List<VersionedMap<KEY, VALUE>> getDependingMaps() { | ||
67 | return Stream.concat( | ||
68 | cursor1.getDependingMaps().stream(), | ||
69 | cursor2.getDependingMaps().stream() | ||
70 | ).collect(Collectors.toList()); | ||
71 | } | ||
52 | 72 | ||
53 | protected void updateState() { | 73 | protected void updateState() { |
54 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | 74 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); |
@@ -72,33 +92,61 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE> { | |||
72 | } | 92 | } |
73 | } | 93 | } |
74 | 94 | ||
75 | protected boolean canStop() { | 95 | protected boolean differentValues() { |
76 | return this.value1 != this.value2; | 96 | return this.value1 != this.value2; |
77 | } | 97 | } |
78 | protected void moveOne() { | 98 | protected boolean moveOne() { |
79 | if(isTerminated()) { | 99 | if(isTerminated()) { |
80 | throw new IllegalStateException("DiffCursor tries to move when terminated!"); | 100 | throw new IllegalStateException("DiffCursor tries to move when terminated!"); |
81 | } | 101 | } |
82 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { | 102 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { |
83 | cursor1.move(); | 103 | return cursor1.move(); |
84 | } else if(this.cursorRelation < 0 || cursor1.isTerminated()) { | 104 | } else if(this.cursorRelation < 0 || cursor1.isTerminated()) { |
85 | cursor2.move(); | 105 | return cursor2.move(); |
86 | } else { | 106 | } else { |
87 | cursor1.move(); | 107 | boolean moved1 = cursor1.move(); |
88 | cursor2.move(); | 108 | boolean moved2 = cursor2.move(); |
109 | return moved1 && moved2; | ||
89 | } | 110 | } |
90 | updateState(); | ||
91 | } | 111 | } |
92 | protected void moveToConsistentState() { | 112 | private boolean skipNode() { |
93 | while(!canStop() && !isTerminated()) { | 113 | if(isTerminated()) { |
94 | moveOne(); | 114 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); |
95 | } | 115 | } |
116 | boolean update1 = cursor1.skipCurrentNode(); | ||
117 | boolean update2 = cursor2.skipCurrentNode(); | ||
118 | updateState(); | ||
119 | return update1 && update2; | ||
96 | } | 120 | } |
97 | 121 | ||
98 | public void move() { | 122 | protected boolean moveToConsistentState() { |
99 | if(!isTerminated()) { | 123 | if(!isTerminated()) { |
100 | moveOne(); | 124 | boolean changed; |
101 | moveToConsistentState(); | 125 | boolean lastResult = true; |
126 | do { | ||
127 | changed = false; | ||
128 | if(MapCursor.sameSubnode(cursor1, cursor2)) { | ||
129 | lastResult = skipNode(); | ||
130 | changed = true; | ||
131 | } | ||
132 | if(differentValues()) { | ||
133 | lastResult = moveOne(); | ||
134 | changed = true; | ||
135 | } | ||
136 | } while(changed && !isTerminated()); | ||
137 | return lastResult; | ||
138 | } else { | ||
139 | return false; | ||
102 | } | 140 | } |
103 | } | 141 | } |
142 | |||
143 | public boolean move() { | ||
144 | if(!isTerminated()) { | ||
145 | if(moveOne()) { | ||
146 | return moveToConsistentState(); | ||
147 | } else { | ||
148 | return false; | ||
149 | } | ||
150 | } else return false; | ||
151 | } | ||
104 | } | 152 | } |
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 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.AbstractMap; | ||
4 | import java.util.Iterator; | ||
5 | import java.util.Map; | ||
6 | import java.util.Map.Entry; | ||
7 | import java.util.NoSuchElementException; | ||
8 | |||
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
10 | |||
11 | /** | ||
12 | * Preorder iterator for map {@link #Node}s. | ||
13 | * | ||
14 | * @author Oszkar Semerath | ||
15 | * | ||
16 | * @param <KEY> | ||
17 | * @param <VALUE> | ||
18 | */ | ||
19 | public class MapEntryIterator<KEY,VALUE> extends MapCursor<KEY, VALUE> implements Iterator<Map.Entry<KEY,VALUE>>{ | ||
20 | |||
21 | public MapEntryIterator(Node<KEY, VALUE> root, VersionedMap<KEY,VALUE> map) { | ||
22 | super(root,map); | ||
23 | |||
24 | } | ||
25 | |||
26 | @Override | ||
27 | public boolean hasNext() { | ||
28 | return !this.isTerminated(); | ||
29 | } | ||
30 | |||
31 | @Override | ||
32 | public Entry<KEY, VALUE> next() { | ||
33 | if(this.hasNext()) { | ||
34 | Map.Entry<KEY, VALUE> result = new AbstractMap.SimpleEntry<KEY, VALUE>(this.key, this.value); | ||
35 | this.move(); | ||
36 | return result; | ||
37 | } else { | ||
38 | throw new NoSuchElementException(); | ||
39 | } | ||
40 | } | ||
41 | } | ||
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 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | 1 | package org.eclipse.viatra.solver.data.map.internal; |
2 | 2 | ||
3 | import java.util.Iterator; | 3 | import java.util.Iterator; |
4 | import java.util.Map; | 4 | import java.util.LinkedList; |
5 | import java.util.List; | ||
5 | 6 | ||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | 7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; |
7 | import org.eclipse.viatra.solver.data.map.Cursor; | 8 | import org.eclipse.viatra.solver.data.map.Cursor; |
@@ -58,6 +59,28 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{ | |||
58 | root = MutableNode.initialize(key, value, hashProvider, defaultValue); | 59 | root = MutableNode.initialize(key, value, hashProvider, defaultValue); |
59 | } | 60 | } |
60 | } | 61 | } |
62 | |||
63 | @Override | ||
64 | public void putAll(Cursor<KEY, VALUE> cursor) { | ||
65 | if(cursor.getDependingMaps().contains(this)) { | ||
66 | List<KEY> keys = new LinkedList<>(); | ||
67 | List<VALUE> values = new LinkedList<>(); | ||
68 | while(cursor.move()) { | ||
69 | keys.add(cursor.getKey()); | ||
70 | values.add(cursor.getValue()); | ||
71 | } | ||
72 | Iterator<KEY> keyIterator = keys.iterator(); | ||
73 | Iterator<VALUE> valueIterator = values.iterator(); | ||
74 | while(keyIterator.hasNext()) { | ||
75 | this.put(keyIterator.next(), valueIterator.next()); | ||
76 | } | ||
77 | } else { | ||
78 | while(cursor.move()) { | ||
79 | this.put(cursor.getKey(), cursor.getValue()); | ||
80 | } | ||
81 | } | ||
82 | } | ||
83 | |||
61 | @Override | 84 | @Override |
62 | public VALUE get(KEY key) { | 85 | public VALUE get(KEY key) { |
63 | if(root!=null) { | 86 | if(root!=null) { |
@@ -74,21 +97,16 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{ | |||
74 | return root.getSize(); | 97 | return root.getSize(); |
75 | } | 98 | } |
76 | } | 99 | } |
77 | @Override | 100 | |
78 | public | ||
79 | Iterator<Map.Entry<KEY,VALUE>> getIterator() { | ||
80 | MapEntryIterator<KEY,VALUE> iterator = new MapEntryIterator<>(this.root,this); | ||
81 | return iterator; | ||
82 | } | ||
83 | @Override | 101 | @Override |
84 | public Cursor<KEY, VALUE> getCursor() { | 102 | public Cursor<KEY, VALUE> getCursor() { |
85 | MapEntryIterator<KEY,VALUE> cursor = new MapEntryIterator<>(this.root,this); | 103 | MapCursor<KEY,VALUE> cursor = new MapCursor<>(this.root,this); |
86 | return cursor; | 104 | return cursor; |
87 | } | 105 | } |
88 | @Override | 106 | @Override |
89 | public DiffCursor<KEY, VALUE> getDiffCursor(long to) { | 107 | public DiffCursor<KEY, VALUE> getDiffCursor(long toVersion) { |
90 | Cursor<KEY, VALUE> fromCursor = this.getCursor(); | 108 | Cursor<KEY, VALUE> fromCursor = this.getCursor(); |
91 | VersionedMap<KEY, VALUE> toMap = this.store.createMap(to); | 109 | VersionedMap<KEY, VALUE> toMap = this.store.createMap(toVersion); |
92 | Cursor<KEY, VALUE> toCursor = toMap.getCursor(); | 110 | Cursor<KEY, VALUE> toCursor = toMap.getCursor(); |
93 | return new MapDiffCursor<KEY, VALUE>(defaultValue, fromCursor, toCursor); | 111 | return new MapDiffCursor<KEY, VALUE>(defaultValue, fromCursor, toCursor); |
94 | 112 | ||