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 tools.refinery.data.map.internal;
import java.util.ArrayDeque;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import tools.refinery.data.map.Cursor;
import tools.refinery.data.map.VersionedMap;
public class MapCursor<K,V> implements Cursor<K,V> {
// Constants
static final int INDEX_START = -1;
static final int INDEX_FINISH = -2;
// Tree stack
ArrayDeque<Node<K,V>> nodeStack;
ArrayDeque<Integer> nodeIndexStack;
int dataIndex;
// Values
K key;
V value;
// Hash code for checking concurrent modifications
final VersionedMap<K,V> map;
final int creationHash;
public MapCursor(Node<K, V> root, VersionedMap<K,V> map) {
// Initializing tree stack
super();
this.nodeStack = new ArrayDeque<>();
this.nodeIndexStack = new ArrayDeque<>();
if(root != null) {
this.nodeStack.add(root);
this.nodeIndexStack.push(INDEX_START);
}
this.dataIndex = INDEX_START;
// Initializing cache
this.key = null;
this.value = null;
// Initializing state
this.map=map;
this.creationHash = map.hashCode();
}
public K getKey() {
return key;
}
public V 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 = INDEX_FINISH;
return move();
}
@Override
public boolean isDirty() {
return this.map.hashCode() != this.creationHash;
}
@Override
public List<VersionedMap<?, ?>> getDependingMaps() {
return List.of(this.map);
}
public static <K,V> boolean sameSubnode(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) {
Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
if(nodeOfCursor1 != null && nodeOfCursor2 != null) {
return nodeOfCursor1.equals(nodeOfCursor2);
} else {
return false;
}
}
/**
*
* @param <K>
* @param <V>
* @param cursor1
* @param cursor2
* @return 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 <K,V> int compare(MapCursor<K,V> cursor1, MapCursor<K,V> 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);
}
}
|