1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
package org.eclipse.viatra.solver.data.map.internal;
import java.util.ArrayDeque;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import org.eclipse.viatra.solver.data.map.Cursor;
import org.eclipse.viatra.solver.data.map.VersionedMap;
public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
// Constants
static int IndexStart = -1;
static int IndexFinish = -2;
// Tree stack
ArrayDeque<Node<KEY,VALUE>> nodeStack;
ArrayDeque<Integer> nodeIndexStack;
int dataIndex;
// Values
KEY key;
VALUE value;
// Hash code for checking concurrent modifications
final VersionedMap<KEY,VALUE> map;
final int creationHash;
public MapCursor(Node<KEY, VALUE> root, VersionedMap<KEY,VALUE> map) {
// Initializing tree stack
super();
this.nodeStack = new ArrayDeque<>();
this.nodeIndexStack = new ArrayDeque<>();
if(root != null) {
this.nodeStack.add(root);
this.nodeIndexStack.push(IndexStart);
}
this.dataIndex = IndexStart;
// Initializing cache
this.key = null;
this.value = null;
// Initializing state
this.map=map;
this.creationHash = map.hashCode();
}
public KEY getKey() {
return key;
}
public VALUE getValue() {
return value;
}
public boolean isTerminated() {
return this.nodeStack.isEmpty();
}
public boolean move() {
if(isDirty()) {
throw new ConcurrentModificationException();
}
if(!isTerminated()) {
boolean result = this.nodeStack.peek().moveToNext(this);
if(this.nodeIndexStack.size() != this.nodeStack.size()) {
throw new IllegalArgumentException("Node stack is corrupted by illegal moves!");
}
return result;
}
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<VersionedMap<KEY, VALUE>> getDependingMaps() {
return List.of(this.map);
}
public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) {
Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek();
Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek();
if(nodeOfCursor1 != null && nodeOfCursor2 != null) {
return nodeOfCursor1.equals(nodeOfCursor2);
} else {
return false;
}
}
/**
*
* @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);
}
}
|