diff options
author | Oszkar Semerath <Oszkar Semerath@DESKTOP-DNR7JQ7> | 2021-07-04 18:29:07 +0200 |
---|---|---|
committer | Oszkar Semerath <Oszkar Semerath@DESKTOP-DNR7JQ7> | 2021-07-04 18:29:07 +0200 |
commit | cc88903d7559890f1d1bf02cf349cb2be86f9ba1 (patch) | |
tree | e00f1a93a381f341af91a8ea83985dd710a1a9b0 /Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data | |
parent | First version of the versioned hashmap (diff) | |
download | VIATRA-Generator-cc88903d7559890f1d1bf02cf349cb2be86f9ba1.tar.gz VIATRA-Generator-cc88903d7559890f1d1bf02cf349cb2be86f9ba1.tar.zst VIATRA-Generator-cc88903d7559890f1d1bf02cf349cb2be86f9ba1.zip |
First version of Cursor, Iterator and getSize()
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data')
7 files changed, 193 insertions, 16 deletions
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 41fd55b7..d5c636d9 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 | |||
@@ -3,9 +3,10 @@ package org.eclipse.viatra.solver.data.map; | |||
3 | import java.util.Iterator; | 3 | import java.util.Iterator; |
4 | import java.util.Map; | 4 | import java.util.Map; |
5 | 5 | ||
6 | import org.eclipse.viatra.solver.data.map.internal.MapCursor; | ||
7 | import org.eclipse.viatra.solver.data.map.internal.MapEntryIterator; | ||
6 | import org.eclipse.viatra.solver.data.map.internal.MutableNode; | 8 | import org.eclipse.viatra.solver.data.map.internal.MutableNode; |
7 | import org.eclipse.viatra.solver.data.map.internal.Node; | 9 | import org.eclipse.viatra.solver.data.map.internal.Node; |
8 | import org.eclipse.viatra.solver.data.map.internal.NodeIterator; | ||
9 | 10 | ||
10 | public class VersionedMap<KEY,VALUE> implements Versioned{ | 11 | public class VersionedMap<KEY,VALUE> implements Versioned{ |
11 | 12 | ||
@@ -47,7 +48,7 @@ public class VersionedMap<KEY,VALUE> implements Versioned{ | |||
47 | } | 48 | } |
48 | } | 49 | } |
49 | Iterator<Map.Entry<KEY,VALUE>> getIterator() { | 50 | Iterator<Map.Entry<KEY,VALUE>> getIterator() { |
50 | return new NodeIterator<KEY, VALUE>(this.root); | 51 | return new MapEntryIterator<>(this.root); |
51 | } | 52 | } |
52 | 53 | ||
53 | @Override | 54 | @Override |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java index e2bc06a9..908d335c 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | |||
@@ -158,9 +158,15 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
158 | } | 158 | } |
159 | 159 | ||
160 | 160 | ||
161 | @SuppressWarnings("unchecked") | ||
161 | @Override | 162 | @Override |
162 | public int getSize() { | 163 | public int getSize() { |
163 | throw new UnsupportedOperationException(); | 164 | int result = Integer.bitCount(this.dataMap); |
165 | for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { | ||
166 | ImmutableNode<KEY,VALUE> subnode = (ImmutableNode<KEY, VALUE>) this.content[this.content.length-1-subnodeIndex]; | ||
167 | result += subnode.getSize(); | ||
168 | } | ||
169 | return result; | ||
164 | } | 170 | } |
165 | 171 | ||
166 | @Override | 172 | @Override |
@@ -173,6 +179,48 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
173 | return this; | 179 | return this; |
174 | } | 180 | } |
175 | 181 | ||
182 | @SuppressWarnings("unchecked") | ||
183 | @Override | ||
184 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { | ||
185 | // 1. try to move to data | ||
186 | int datas = Integer.bitCount(this.dataMap); | ||
187 | if(cursor.dataIndex != MapCursor.IndexFinish) { | ||
188 | int newDataIndex = cursor.dataIndex + 1; | ||
189 | if(newDataIndex < datas) { | ||
190 | cursor.dataIndex = newDataIndex; | ||
191 | cursor.key = (KEY) this.content[newDataIndex*2]; | ||
192 | cursor.value = (VALUE) this.content[newDataIndex*2+1]; | ||
193 | return true; | ||
194 | } else { | ||
195 | cursor.dataIndex = MapCursor.IndexFinish; | ||
196 | } | ||
197 | } | ||
198 | |||
199 | // 2. look inside the subnodes | ||
200 | int nodes = Integer.bitCount(this.nodeMap); | ||
201 | int newNodeIndex = cursor.nodeIndexStack.peek() + 1; | ||
202 | if(newNodeIndex < nodes) { | ||
203 | // 2.1 found next subnode, move down to the subnode | ||
204 | Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[this.content.length-1-newNodeIndex]; | ||
205 | cursor.dataIndex = MapCursor.IndexStart; | ||
206 | cursor.nodeStack.add(subnode); | ||
207 | cursor.nodeIndexStack.add(newNodeIndex); | ||
208 | return subnode.moveToNext(cursor); | ||
209 | } else { | ||
210 | // 3. no subnode found, move up | ||
211 | cursor.nodeStack.pop(); | ||
212 | cursor.nodeIndexStack.pop(); | ||
213 | if(!cursor.nodeStack.empty()) { | ||
214 | Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); | ||
215 | return supernode.moveToNext(cursor); | ||
216 | } else { | ||
217 | cursor.key = null; | ||
218 | cursor.value = null; | ||
219 | return false; | ||
220 | } | ||
221 | } | ||
222 | } | ||
223 | |||
176 | @Override | 224 | @Override |
177 | protected void prettyPrint(StringBuilder builder, int depth, int code) { | 225 | protected void prettyPrint(StringBuilder builder, int depth, int code) { |
178 | for(int i = 0; i<depth; i++) { | 226 | for(int i = 0; i<depth; i++) { |
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 new file mode 100644 index 00000000..4a4912d8 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java | |||
@@ -0,0 +1,52 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Stack; | ||
4 | |||
5 | public class MapCursor<KEY,VALUE> { | ||
6 | // Constants | ||
7 | static int IndexStart = -1; | ||
8 | static int IndexFinish = -2; | ||
9 | |||
10 | // Tree stack | ||
11 | Stack<Node<KEY,VALUE>> nodeStack; | ||
12 | Stack<Integer> nodeIndexStack; | ||
13 | int dataIndex; | ||
14 | |||
15 | // Values | ||
16 | KEY key; | ||
17 | VALUE value; | ||
18 | |||
19 | public MapCursor(Node<KEY, VALUE> root) { | ||
20 | // Initializing tree stack | ||
21 | super(); | ||
22 | this.nodeStack = new Stack<>(); | ||
23 | this.nodeStack.add(root); | ||
24 | this.nodeIndexStack = new Stack<>(); | ||
25 | this.nodeIndexStack.add(IndexStart); | ||
26 | this.dataIndex = IndexStart; | ||
27 | |||
28 | // Initializing cache | ||
29 | this.key = null; | ||
30 | this.value = null; | ||
31 | } | ||
32 | |||
33 | public KEY getKey() { | ||
34 | return key; | ||
35 | } | ||
36 | |||
37 | public VALUE getValue() { | ||
38 | return value; | ||
39 | } | ||
40 | |||
41 | public boolean isTerminated() { | ||
42 | return this.nodeStack.empty(); | ||
43 | } | ||
44 | |||
45 | public boolean move() { | ||
46 | if(this.isTerminated()) { | ||
47 | return false; | ||
48 | } else { | ||
49 | return true; | ||
50 | } | ||
51 | } | ||
52 | } | ||
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 new file mode 100644 index 00000000..82983484 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java | |||
@@ -0,0 +1,40 @@ | |||
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 | /** | ||
10 | * Preorder iterator for map {@link #Node}s. | ||
11 | * | ||
12 | * @author Oszkar Semerath | ||
13 | * | ||
14 | * @param <KEY> | ||
15 | * @param <VALUE> | ||
16 | */ | ||
17 | public class MapEntryIterator<KEY,VALUE> extends MapCursor<KEY, VALUE> implements Iterator<Map.Entry<KEY,VALUE>>{ | ||
18 | |||
19 | public MapEntryIterator(Node<KEY, VALUE> root) { | ||
20 | super(root); | ||
21 | // move to first | ||
22 | move(); | ||
23 | } | ||
24 | |||
25 | @Override | ||
26 | public boolean hasNext() { | ||
27 | return this.isTerminated(); | ||
28 | } | ||
29 | |||
30 | @Override | ||
31 | public Entry<KEY, VALUE> next() { | ||
32 | if(!this.hasNext()) { | ||
33 | Map.Entry<KEY, VALUE> result = new AbstractMap.SimpleEntry<KEY, VALUE>(this.key, this.value); | ||
34 | this.move(); | ||
35 | return result; | ||
36 | } else { | ||
37 | throw new NoSuchElementException(); | ||
38 | } | ||
39 | } | ||
40 | } | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java index f6d0323e..9b30dbb7 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java | |||
@@ -203,6 +203,48 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
203 | return new ImmutableNode<KEY,VALUE>(this); | 203 | return new ImmutableNode<KEY,VALUE>(this); |
204 | } | 204 | } |
205 | 205 | ||
206 | @SuppressWarnings("unchecked") | ||
207 | @Override | ||
208 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { | ||
209 | // 1. try to move to data | ||
210 | if(cursor.dataIndex != MapCursor.IndexFinish) { | ||
211 | for(int index = cursor.dataIndex+1; index < factor; index++) { | ||
212 | if(this.content[index*2]!=null) { | ||
213 | // 1.1 found next data | ||
214 | cursor.dataIndex = index; | ||
215 | cursor.key = (KEY) this.content[index*2]; | ||
216 | cursor.value = (VALUE) this.content[index*2+1]; | ||
217 | return true; | ||
218 | } | ||
219 | } | ||
220 | } | ||
221 | cursor.dataIndex = MapCursor.IndexFinish; | ||
222 | // 2. look inside the subnodes | ||
223 | for(int index = cursor.nodeIndexStack.peek()+1; index < factor; index++) { | ||
224 | if(this.content[index*2]==null && this.content[index*2+1] !=null) { | ||
225 | // 2.1 found next subnode, move down to the subnode | ||
226 | Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index*2+1]; | ||
227 | |||
228 | cursor.dataIndex = MapCursor.IndexStart; | ||
229 | cursor.nodeStack.add(subnode); | ||
230 | cursor.nodeIndexStack.add(index); | ||
231 | |||
232 | return subnode.moveToNext(cursor); | ||
233 | } | ||
234 | } | ||
235 | // 3. no subnode found, move up | ||
236 | cursor.nodeStack.pop(); | ||
237 | cursor.nodeIndexStack.pop(); | ||
238 | if(!cursor.nodeStack.empty()) { | ||
239 | Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); | ||
240 | return supernode.moveToNext(cursor); | ||
241 | } else { | ||
242 | cursor.key = null; | ||
243 | cursor.value = null; | ||
244 | return false; | ||
245 | } | ||
246 | } | ||
247 | |||
206 | @Override | 248 | @Override |
207 | protected void prettyPrint(StringBuilder builder, int depth, int code) { | 249 | protected void prettyPrint(StringBuilder builder, int depth, int code) { |
208 | for(int i = 0; i<depth; i++) { | 250 | for(int i = 0; i<depth; i++) { |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java index 89c52f7f..7a6599a2 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java | |||
@@ -55,6 +55,13 @@ public abstract class Node<KEY,VALUE>{ | |||
55 | abstract protected MutableNode<KEY, VALUE> toMutable(); | 55 | abstract protected MutableNode<KEY, VALUE> toMutable(); |
56 | abstract protected ImmutableNode<KEY, VALUE> toImmutable(); | 56 | abstract protected ImmutableNode<KEY, VALUE> toImmutable(); |
57 | 57 | ||
58 | /** | ||
59 | * Moves a {@link MapCursor} to its next position. | ||
60 | * @param cursor the cursor | ||
61 | * @return Whether there was a next value to move on. | ||
62 | */ | ||
63 | abstract boolean moveToNext(MapCursor<KEY,VALUE> cursor); | ||
64 | |||
58 | ///////// For iterators | 65 | ///////// For iterators |
59 | //abstract boolean moveIteratorToNextData(NodeIterator<KEY,VALUE> iterator, int currentIndex); | 66 | //abstract boolean moveIteratorToNextData(NodeIterator<KEY,VALUE> iterator, int currentIndex); |
60 | //abstract boolean moveIteratorToNextNode(NodeIterator<KEY,VALUE> iterator, int currentIndex); | 67 | //abstract boolean moveIteratorToNextNode(NodeIterator<KEY,VALUE> iterator, int currentIndex); |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/NodeIterator.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/NodeIterator.java deleted file mode 100644 index 4c426b1e..00000000 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/NodeIterator.java +++ /dev/null | |||
@@ -1,13 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Iterator; | ||
4 | import java.util.Map; | ||
5 | |||
6 | public abstract class NodeIterator<NODETYPE extends Node<KEY,VALUE>,KEY,VALUE> | ||
7 | implements Iterator<Map.Entry<KEY,VALUE>> | ||
8 | { | ||
9 | protected NODETYPE node; | ||
10 | public NodeIterator(NODETYPE node) { | ||
11 | this.node = node; | ||
12 | } | ||
13 | } | ||