diff options
author | Kristóf Marussy <marussy@mit.bme.hu> | 2021-07-29 19:01:25 +0200 |
---|---|---|
committer | Kristóf Marussy <marussy@mit.bme.hu> | 2021-07-29 19:01:25 +0200 |
commit | 7f6a2528bf83f93e3d35eff228f7180e0181f4eb (patch) | |
tree | 068dc3454cc9f968162e5ae03cc8733f9011de72 /model-data/src/main/java/org/eclipse | |
parent | Refactoring based on Sonar reports (diff) | |
download | refinery-7f6a2528bf83f93e3d35eff228f7180e0181f4eb.tar.gz refinery-7f6a2528bf83f93e3d35eff228f7180e0181f4eb.tar.zst refinery-7f6a2528bf83f93e3d35eff228f7180e0181f4eb.zip |
Add new data structure for backend
Co-authored-by: Oszkár Semeráth <semerath@mit.bme.hu>
Diffstat (limited to 'model-data/src/main/java/org/eclipse')
25 files changed, 1776 insertions, 0 deletions
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java new file mode 100644 index 00000000..7b0e565b --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java | |||
@@ -0,0 +1,17 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class BooleanValue implements TruthValue { | ||
4 | private final boolean value; | ||
5 | protected BooleanValue(final boolean value) { | ||
6 | this.value = value; | ||
7 | } | ||
8 | public static final BooleanValue trueValue = new BooleanValue(true); | ||
9 | public static final BooleanValue falseValue = new BooleanValue(false); | ||
10 | |||
11 | @Override | ||
12 | public String getName() { | ||
13 | // TODO Auto-generated method stub | ||
14 | return Boolean.toString(value); | ||
15 | } | ||
16 | |||
17 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java new file mode 100644 index 00000000..74624db6 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java | |||
@@ -0,0 +1,5 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class DataSymbol { | ||
4 | |||
5 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java new file mode 100644 index 00000000..40d01721 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java | |||
@@ -0,0 +1,11 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class DefinedSymbol extends Symbol { | ||
4 | private final String name; | ||
5 | public DefinedSymbol(String name) { | ||
6 | this.name = name; | ||
7 | } | ||
8 | public String getName() { | ||
9 | return name; | ||
10 | } | ||
11 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java new file mode 100644 index 00000000..7a807155 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java | |||
@@ -0,0 +1,9 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class Logic2Valued { | ||
4 | protected static final String trueName = "true"; | ||
5 | protected static final String falseName = "false"; | ||
6 | |||
7 | public static final TruthValue trueValue = new NamedTruthValue(trueName); | ||
8 | public static final TruthValue falseValue = new NamedTruthValue(falseName); | ||
9 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java new file mode 100644 index 00000000..5f1e2bd8 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java | |||
@@ -0,0 +1,22 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class Logic4Valued extends Logic2Valued { | ||
4 | protected static final String unknownName = "unknown"; | ||
5 | protected static final String errorName = "error"; | ||
6 | |||
7 | public static final TruthValue unknownValue = new NamedTruthValue(unknownName); | ||
8 | public static final TruthValue errorValue = new NamedTruthValue(errorName); | ||
9 | |||
10 | // public TruthValue getImplMin(TruthValue a, TruthValue b) { | ||
11 | // | ||
12 | // } | ||
13 | // public TruthValue getImplMax(TruthValue a, TruthValue b) { | ||
14 | // | ||
15 | // } | ||
16 | // public TruthValue getInfoMin(TruthValue a, TruthValue b) { | ||
17 | // | ||
18 | // } | ||
19 | // public TruthValue getInfoMax(TruthValue a, TruthValue b) { | ||
20 | // | ||
21 | // } | ||
22 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java new file mode 100644 index 00000000..6f5c58ce --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java | |||
@@ -0,0 +1,10 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | import java.util.List; | ||
4 | import java.util.Map; | ||
5 | import java.util.Set; | ||
6 | |||
7 | public class Model { | ||
8 | Set<ModelObject> objects; | ||
9 | Map<String,Map<List<ModelObject>,TruthValue>> interpretation; | ||
10 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java new file mode 100644 index 00000000..73607f82 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java | |||
@@ -0,0 +1,5 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class ModelObject { | ||
4 | |||
5 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java new file mode 100644 index 00000000..be3a2351 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java | |||
@@ -0,0 +1,13 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class NamedTruthValue implements TruthValue { | ||
4 | private final String name; | ||
5 | public NamedTruthValue(String name) { | ||
6 | this.name = name; | ||
7 | } | ||
8 | @Override | ||
9 | public String getName() { | ||
10 | return this.name; | ||
11 | } | ||
12 | |||
13 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java new file mode 100644 index 00000000..6bf0b195 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java | |||
@@ -0,0 +1,5 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class PrimitiveSymbol { | ||
4 | |||
5 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java new file mode 100644 index 00000000..d403e181 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java | |||
@@ -0,0 +1,5 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | public class Symbol { | ||
4 | |||
5 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java new file mode 100644 index 00000000..5dbde11c --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java | |||
@@ -0,0 +1,5 @@ | |||
1 | package org.eclipse.viatra.solver.data; | ||
2 | |||
3 | interface TruthValue { | ||
4 | public String getName(); | ||
5 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java new file mode 100644 index 00000000..79ca4412 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java | |||
@@ -0,0 +1,64 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | import org.eclipse.viatra.solver.data.map.internal.Node; | ||
4 | |||
5 | /** | ||
6 | * A class representing an equivalence relation for a type {@code KEY} with a | ||
7 | * continuous hash function. | ||
8 | * | ||
9 | * @author Oszkar Semerath | ||
10 | * | ||
11 | * @param <K> Target java type. | ||
12 | */ | ||
13 | public interface ContinousHashProvider<K> { | ||
14 | public static final int EFFECTIVE_BITS = Node.effectiveBits; | ||
15 | public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1; | ||
16 | |||
17 | /** | ||
18 | * Maximal practical depth for differentiating keys. If two keys have the same | ||
19 | * hash code until that depth, the algorithm can stop. | ||
20 | */ | ||
21 | public static final int MAX_PRACTICAL_DEPTH = 500; | ||
22 | |||
23 | /** | ||
24 | * Provides a hash code for a object {@code key} with a given {@code index}. It | ||
25 | * has the following contracts: | ||
26 | * <ul> | ||
27 | * <li>If {@link #equals}{@code (key1,key2)}, then | ||
28 | * {@code getHash(key1, index) == getHash(key2, index)} for all values of | ||
29 | * {@code index}.</li> | ||
30 | * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of | ||
31 | * {@code index}, then {@link #equals}{@code (key1, key2)}</li> | ||
32 | * <li>In current implementation, we use only the least significant | ||
33 | * {@link #EFFECTIVE_BITS} | ||
34 | * </ul> | ||
35 | * Check {@link #equals} for further details. | ||
36 | * | ||
37 | * @param key The target data object. | ||
38 | * @param index The depth of the the hash code. Needs to be non-negative. | ||
39 | * @return A hash code. | ||
40 | */ | ||
41 | public int getHash(K key, int index); | ||
42 | |||
43 | public default int getEffectiveHash(K key, int index) { | ||
44 | return getHash(key, index) & EFFECTIVE_BIT_MASK; | ||
45 | } | ||
46 | |||
47 | public default int compare(K key1, K key2) { | ||
48 | if (key1.equals(key2)) { | ||
49 | return 0; | ||
50 | } else { | ||
51 | for (var i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { | ||
52 | int hash1 = getEffectiveHash(key1, i); | ||
53 | int hash2 = getEffectiveHash(key2, i); | ||
54 | var result = Integer.compare(hash1, hash2); | ||
55 | if (result != 0) { | ||
56 | return result; | ||
57 | } | ||
58 | } | ||
59 | throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 | ||
60 | + ") have the same hashcode over the practical depth limitation (" | ||
61 | + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); | ||
62 | } | ||
63 | } | ||
64 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java new file mode 100644 index 00000000..969f96c9 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java | |||
@@ -0,0 +1,13 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | import java.util.List; | ||
4 | |||
5 | public interface Cursor<KEY,VALUE> { | ||
6 | public KEY getKey(); | ||
7 | public VALUE getValue(); | ||
8 | public boolean isTerminated(); | ||
9 | public boolean move(); | ||
10 | public boolean isDirty(); | ||
11 | |||
12 | public List<VersionedMap<KEY,VALUE>> getDependingMaps(); | ||
13 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java new file mode 100644 index 00000000..2be2e024 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java | |||
@@ -0,0 +1,5 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | public interface DiffCursor<KEY, VALUE> extends Cursor<KEY,VALUE> { | ||
4 | |||
5 | } \ No newline at end of file | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java new file mode 100644 index 00000000..68970a94 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java | |||
@@ -0,0 +1,7 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | public interface Versioned { | ||
4 | public long commit(); | ||
5 | //public void revert(); | ||
6 | public void restore(long state); | ||
7 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java new file mode 100644 index 00000000..11077dca --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java | |||
@@ -0,0 +1,11 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | public interface VersionedMap<KEY,VALUE> extends Versioned{ | ||
4 | public void put(KEY key, VALUE value); | ||
5 | public VALUE get(KEY key); | ||
6 | public long getSize(); | ||
7 | |||
8 | public Cursor<KEY,VALUE> getCursor(); | ||
9 | public DiffCursor<KEY,VALUE> getDiffCursor(long state); | ||
10 | public void putAll(Cursor<KEY,VALUE> cursor); | ||
11 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java new file mode 100644 index 00000000..d92e5ad6 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java | |||
@@ -0,0 +1,10 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | public interface VersionedMapStore<KEY, VALUE> { | ||
4 | |||
5 | public VersionedMap<KEY, VALUE> createMap(); | ||
6 | |||
7 | public VersionedMap<KEY, VALUE> createMap(long state) throws IllegalAccessException; | ||
8 | |||
9 | public DiffCursor<KEY,VALUE> getDiffCursor(long fromState, long toState); | ||
10 | } \ No newline at end of file | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java new file mode 100644 index 00000000..196adf2c --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java | |||
@@ -0,0 +1,27 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | public class VersionedMapStoreConfiguration { | ||
4 | /** | ||
5 | * If true root is replaced with immutable node when committed. Frees up memory | ||
6 | * by releasing immutable nodes, but it may decrease performance by recreating | ||
7 | * immutable nodes upon changes (some evidence). | ||
8 | */ | ||
9 | public boolean immutableWhenCommiting = true; | ||
10 | |||
11 | /** | ||
12 | * If true, all subnodes are cached within a {@link VersionedMapStore}. It | ||
13 | * decreases the memory requirements. It may increase performance by discovering | ||
14 | * existing immutable copy of a node (some evidence). Additional overhead may | ||
15 | * decrease performance (no example found). The option permits the efficient | ||
16 | * implementation of version deletion. | ||
17 | */ | ||
18 | public boolean sharedNodeCacheInStore = true; | ||
19 | |||
20 | /** | ||
21 | * If true, all subnodes are cached within a group of | ||
22 | * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}. | ||
23 | * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is | ||
24 | * <code>false</code>, then it has currently no impact. | ||
25 | */ | ||
26 | public boolean sharedNodeCacheInStoreGroups = true; | ||
27 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java new file mode 100644 index 00000000..c551ffe7 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java | |||
@@ -0,0 +1,162 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | ||
2 | |||
3 | import java.util.ArrayList; | ||
4 | import java.util.Collections; | ||
5 | import java.util.HashMap; | ||
6 | import java.util.List; | ||
7 | import java.util.Map; | ||
8 | import java.util.Set; | ||
9 | |||
10 | import org.eclipse.viatra.solver.data.map.internal.ImmutableNode; | ||
11 | import org.eclipse.viatra.solver.data.map.internal.MapDiffCursor; | ||
12 | import org.eclipse.viatra.solver.data.map.internal.Node; | ||
13 | import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; | ||
14 | |||
15 | public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY, VALUE> { | ||
16 | // Configuration | ||
17 | final private boolean immutableWhenCommiting; | ||
18 | |||
19 | // Static data | ||
20 | protected final ContinousHashProvider<? super KEY> hashProvider; | ||
21 | protected final VALUE defaultValue; | ||
22 | |||
23 | // Dynamic data | ||
24 | final protected Map<Long, ImmutableNode<KEY,VALUE>> states; | ||
25 | final protected Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache; | ||
26 | protected long nextID; | ||
27 | |||
28 | public VersionedMapStoreImpl( | ||
29 | ContinousHashProvider<? super KEY> hashProvider, | ||
30 | VALUE defaultValue, | ||
31 | VersionedMapStoreConfiguration config) | ||
32 | { | ||
33 | this.immutableWhenCommiting = config.immutableWhenCommiting; | ||
34 | |||
35 | this.hashProvider = hashProvider; | ||
36 | this.defaultValue = defaultValue; | ||
37 | |||
38 | states = new HashMap<>(); | ||
39 | nextID = 0; | ||
40 | if(config.sharedNodeCacheInStore) { | ||
41 | nodeCache = new HashMap<>(); | ||
42 | } else { | ||
43 | nodeCache = null; | ||
44 | } | ||
45 | } | ||
46 | private VersionedMapStoreImpl( | ||
47 | ContinousHashProvider<? super KEY> hashProvider, | ||
48 | VALUE defaultValue, | ||
49 | Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache, | ||
50 | VersionedMapStoreConfiguration config) | ||
51 | { | ||
52 | this.immutableWhenCommiting = config.immutableWhenCommiting; | ||
53 | |||
54 | this.hashProvider = hashProvider; | ||
55 | this.defaultValue = defaultValue; | ||
56 | |||
57 | states = new HashMap<>(); | ||
58 | nextID = 0; | ||
59 | this.nodeCache = nodeCache; | ||
60 | } | ||
61 | |||
62 | public VersionedMapStoreImpl(ContinousHashProvider<KEY> hashProvider, VALUE defaultValue) { | ||
63 | this(hashProvider,defaultValue,new VersionedMapStoreConfiguration()); | ||
64 | } | ||
65 | |||
66 | public static <MAP,KEY,VALUE> List<VersionedMapStore<KEY,VALUE>> createSharedVersionedMapStores( | ||
67 | int amount, | ||
68 | ContinousHashProvider<? super KEY> hashProvider, | ||
69 | VALUE defaultValue, | ||
70 | VersionedMapStoreConfiguration config) | ||
71 | { | ||
72 | List<VersionedMapStore<KEY,VALUE>> result = new ArrayList<>(amount); | ||
73 | if(config.sharedNodeCacheInStoreGroups) { | ||
74 | Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache; | ||
75 | if(config.sharedNodeCacheInStore) { | ||
76 | nodeCache = new HashMap<>(); | ||
77 | } else { | ||
78 | nodeCache = null; | ||
79 | } | ||
80 | for (int i = 0; i < amount; i++) { | ||
81 | result.add(new VersionedMapStoreImpl<KEY, VALUE>(hashProvider, defaultValue, nodeCache, config)); | ||
82 | } | ||
83 | } else { | ||
84 | for (int i = 0; i < amount; i++) { | ||
85 | result.add(new VersionedMapStoreImpl<KEY, VALUE>(hashProvider, defaultValue, config)); | ||
86 | } | ||
87 | } | ||
88 | return result; | ||
89 | } | ||
90 | public static <MAP,KEY,VALUE> List<VersionedMapStore<KEY,VALUE>> createSharedVersionedMapStores( | ||
91 | int amount, | ||
92 | ContinousHashProvider<? super KEY> hashProvider, | ||
93 | VALUE defaultValue) | ||
94 | { | ||
95 | return createSharedVersionedMapStores(amount,hashProvider,defaultValue,new VersionedMapStoreConfiguration()); | ||
96 | } | ||
97 | |||
98 | synchronized Set<Long> getStates() { | ||
99 | return states.keySet(); | ||
100 | } | ||
101 | |||
102 | @Override | ||
103 | public VersionedMap<KEY,VALUE> createMap() { | ||
104 | return new VersionedMapImpl<KEY,VALUE>(this,hashProvider,defaultValue); | ||
105 | } | ||
106 | @Override | ||
107 | public VersionedMap<KEY,VALUE> createMap(long state) { | ||
108 | ImmutableNode<KEY, VALUE> data = revert(state); | ||
109 | return new VersionedMapImpl<KEY,VALUE>(this,hashProvider,defaultValue,data); | ||
110 | } | ||
111 | |||
112 | synchronized public ImmutableNode<KEY,VALUE> revert(long state) { | ||
113 | if(states.containsKey(state)) { | ||
114 | return states.get(state); | ||
115 | } else { | ||
116 | ArrayList<Long> existingKeys = new ArrayList<Long>(states.keySet()); | ||
117 | Collections.sort(existingKeys); | ||
118 | throw new IllegalArgumentException( | ||
119 | "Store does not contain state "+state+"! Avaliable states: "+existingKeys.toArray().toString()); | ||
120 | } | ||
121 | } | ||
122 | synchronized public long commit(Node<KEY,VALUE> data, VersionedMapImpl<KEY, VALUE> mapToUpdateRoot) { | ||
123 | ImmutableNode<KEY,VALUE> immutable; | ||
124 | if(data != null) { | ||
125 | if(this.nodeCache != null) { | ||
126 | immutable = data.toImmutable(this.nodeCache); | ||
127 | } else { | ||
128 | immutable = data.toImmutable(); | ||
129 | } | ||
130 | } else { | ||
131 | immutable = null; | ||
132 | } | ||
133 | |||
134 | |||
135 | if(nextID == Long.MAX_VALUE) throw new IllegalStateException( | ||
136 | "Map store run out of Id-s"); | ||
137 | long id = nextID++; | ||
138 | this.states.put(id, immutable); | ||
139 | if(this.immutableWhenCommiting) { | ||
140 | mapToUpdateRoot.setRoot(immutable); | ||
141 | } | ||
142 | return id; | ||
143 | } | ||
144 | |||
145 | // public Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> getStore() { | ||
146 | // return this.nodeCache; | ||
147 | // } | ||
148 | // public long addState(ImmutableNode<KEY,VALUE> data) { | ||
149 | // | ||
150 | // states.put(id,data); | ||
151 | // return id; | ||
152 | // } | ||
153 | |||
154 | @Override | ||
155 | public DiffCursor<KEY, VALUE> getDiffCursor(long fromState, long toState) { | ||
156 | VersionedMap<KEY, VALUE> map1 = createMap(fromState); | ||
157 | VersionedMap<KEY, VALUE> map2 = createMap(toState); | ||
158 | Cursor<KEY, VALUE> cursor1 = map1.getCursor(); | ||
159 | Cursor<KEY, VALUE> cursor2 = map2.getCursor(); | ||
160 | return new MapDiffCursor<KEY, VALUE>(this.hashProvider,this.defaultValue,cursor1,cursor2); | ||
161 | } | ||
162 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java new file mode 100644 index 00000000..087c12a1 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | |||
@@ -0,0 +1,366 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Arrays; | ||
4 | import java.util.Map; | ||
5 | |||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
7 | |||
8 | public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | ||
9 | /** | ||
10 | * Bitmap defining the stored key and values. | ||
11 | */ | ||
12 | final int dataMap; | ||
13 | /** | ||
14 | * Bitmap defining the positions of further nodes. | ||
15 | */ | ||
16 | final int nodeMap; | ||
17 | /** | ||
18 | * Stores Keys, Values, and subnodes. Structure: (KEY,VALUE)*,NODE; NODES are stored backwards. | ||
19 | */ | ||
20 | final Object[] content; | ||
21 | |||
22 | /** | ||
23 | * Hash code derived from immutable hash code | ||
24 | */ | ||
25 | final int precalculatedHash; | ||
26 | |||
27 | private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { | ||
28 | super(); | ||
29 | this.dataMap = dataMap; | ||
30 | this.nodeMap = nodeMap; | ||
31 | this.content = content; | ||
32 | this.precalculatedHash = precalculatedHash; | ||
33 | } | ||
34 | |||
35 | /** | ||
36 | * Constructor that copies a mutable node to an immutable. | ||
37 | * | ||
38 | * @param node A mutable node. | ||
39 | * @param cache A cache of existing immutable nodes. It can be used to search | ||
40 | * and place reference immutable nodes. It can be null, if no cache | ||
41 | * available. | ||
42 | * @return an immutable version of the input node. | ||
43 | */ | ||
44 | @SuppressWarnings("unchecked") | ||
45 | static <KEY,VALUE> ImmutableNode<KEY,VALUE> constructImmutable(MutableNode<KEY,VALUE> node, Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) { | ||
46 | // 1. try to return from cache | ||
47 | if(cache != null) { | ||
48 | ImmutableNode<KEY, VALUE> cachedResult = cache.get(node); | ||
49 | if(cachedResult != null) { | ||
50 | // 1.1 Already cached, return from cache. | ||
51 | return cachedResult; | ||
52 | } | ||
53 | } | ||
54 | |||
55 | // 2. otherwise construct a new ImmutableNode | ||
56 | int size = 0; | ||
57 | for(int i = 0; i<node.content.length; i++) { | ||
58 | if(node.content[i]!=null) { | ||
59 | size++; | ||
60 | } | ||
61 | } | ||
62 | |||
63 | int datas = 0; | ||
64 | int nodes = 0; | ||
65 | int resultDataMap = 0; | ||
66 | int resultNodeMap = 0; | ||
67 | final Object[] resultContent = new Object[size]; | ||
68 | int bitposition = 1; | ||
69 | for(int i = 0; i<factor; i++) { | ||
70 | Object key = node.content[i*2]; | ||
71 | if(key != null) { | ||
72 | resultDataMap |= bitposition; | ||
73 | resultContent[datas*2] = key; | ||
74 | resultContent[datas*2+1] = node.content[i*2+1]; | ||
75 | datas++; | ||
76 | } else { | ||
77 | Node<KEY,VALUE> subnode = (Node<KEY, VALUE>) node.content[i*2+1]; | ||
78 | if(subnode != null) { | ||
79 | ImmutableNode<KEY, VALUE> immutableSubnode = subnode.toImmutable(cache); | ||
80 | resultNodeMap |=bitposition; | ||
81 | resultContent[size-1-nodes] = immutableSubnode; | ||
82 | nodes++; | ||
83 | } | ||
84 | } | ||
85 | bitposition<<=1; | ||
86 | } | ||
87 | final int resultHash = node.hashCode(); | ||
88 | ImmutableNode<KEY,VALUE> newImmutable = new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash); | ||
89 | |||
90 | // 3. save new immutable. | ||
91 | if(cache != null) { | ||
92 | cache.put(newImmutable, newImmutable); | ||
93 | } | ||
94 | return newImmutable; | ||
95 | } | ||
96 | |||
97 | private int index(int bitmap, int bitpos) { | ||
98 | return Integer.bitCount(bitmap & (bitpos-1)); | ||
99 | } | ||
100 | |||
101 | @SuppressWarnings("unchecked") | ||
102 | @Override | ||
103 | public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | ||
104 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | ||
105 | int bitposition = 1 << selectedHashFragment; | ||
106 | // If the key is stored as a data | ||
107 | if((dataMap & bitposition) != 0) { | ||
108 | int keyIndex = 2*index(dataMap, bitposition); | ||
109 | KEY keyCandidate = (KEY) content[keyIndex]; | ||
110 | if(keyCandidate.equals(key)) { | ||
111 | return (VALUE) content[keyIndex+1]; | ||
112 | } else { | ||
113 | return defaultValue; | ||
114 | } | ||
115 | } | ||
116 | // the key is stored as a node | ||
117 | else if((nodeMap & bitposition) != 0) { | ||
118 | int keyIndex = content.length-1-index(nodeMap, bitposition); | ||
119 | ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex]; | ||
120 | int newDepth = depth+1; | ||
121 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
122 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); | ||
123 | } | ||
124 | // the key is not stored at all | ||
125 | else { | ||
126 | return defaultValue; | ||
127 | } | ||
128 | } | ||
129 | |||
130 | @SuppressWarnings("unchecked") | ||
131 | @Override | ||
132 | public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | ||
133 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | ||
134 | int bitposition = 1 << selectedHashFragment; | ||
135 | if((dataMap & bitposition) != 0) { | ||
136 | int keyIndex = 2*index(dataMap, bitposition); | ||
137 | KEY keyCandidate = (KEY) content[keyIndex]; | ||
138 | if(keyCandidate.equals(key)) { | ||
139 | if(value == defaultValue) { | ||
140 | // delete | ||
141 | MutableNode<KEY, VALUE> mutable = this.toMutable(); | ||
142 | Node<KEY, VALUE> result = mutable.removeEntry(selectedHashFragment); | ||
143 | return result; | ||
144 | } else if(value == content[keyIndex+1]) { | ||
145 | // dont change | ||
146 | return this; | ||
147 | } else { | ||
148 | // update existing value | ||
149 | MutableNode<KEY, VALUE> mutable = this.toMutable(); | ||
150 | Node<KEY, VALUE> result = mutable.updateValue(value, selectedHashFragment); | ||
151 | return result; | ||
152 | } | ||
153 | } else { | ||
154 | if(value == defaultValue) { | ||
155 | // dont change | ||
156 | return this; | ||
157 | } else { | ||
158 | // add new key + value | ||
159 | MutableNode<KEY, VALUE> mutable = this.toMutable(); | ||
160 | Node<KEY, VALUE> result = mutable.putValue(key, value, hashProvider, defaultValue, hash, depth); | ||
161 | return result; | ||
162 | } | ||
163 | } | ||
164 | } else if((nodeMap & bitposition)!=0) { | ||
165 | |||
166 | int keyIndex = content.length-1-index(nodeMap, bitposition); | ||
167 | ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex]; | ||
168 | int newDepth = depth+1; | ||
169 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
170 | Node<KEY,VALUE> newsubNode = subNode.putValue(key, value, hashProvider, defaultValue, newHash, newDepth); | ||
171 | |||
172 | if(subNode == newsubNode) { | ||
173 | // nothing changed | ||
174 | return this; | ||
175 | } else { | ||
176 | MutableNode<KEY, VALUE> mutable = toMutable(); | ||
177 | Node<KEY, VALUE> result = mutable.updateSubNode(selectedHashFragment, newsubNode); | ||
178 | return result; | ||
179 | } | ||
180 | } else { | ||
181 | // add new key + value | ||
182 | MutableNode<KEY, VALUE> mutable = this.toMutable(); | ||
183 | Node<KEY, VALUE> result = mutable.putValue(key, value, hashProvider, defaultValue, hash, depth); | ||
184 | return result; | ||
185 | } | ||
186 | } | ||
187 | |||
188 | |||
189 | @SuppressWarnings("unchecked") | ||
190 | @Override | ||
191 | public long getSize() { | ||
192 | int result = Integer.bitCount(this.dataMap); | ||
193 | for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { | ||
194 | ImmutableNode<KEY,VALUE> subnode = | ||
195 | (ImmutableNode<KEY, VALUE>) this.content[this.content.length-1-subnodeIndex]; | ||
196 | result += subnode.getSize(); | ||
197 | } | ||
198 | return result; | ||
199 | } | ||
200 | |||
201 | @Override | ||
202 | protected MutableNode<KEY,VALUE> toMutable() { | ||
203 | return new MutableNode<KEY,VALUE>(this); | ||
204 | } | ||
205 | |||
206 | @Override | ||
207 | public ImmutableNode<KEY,VALUE> toImmutable() { | ||
208 | return this; | ||
209 | } | ||
210 | |||
211 | @Override | ||
212 | public ImmutableNode<KEY, VALUE> toImmutable( | ||
213 | Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) { | ||
214 | return this; | ||
215 | } | ||
216 | |||
217 | @SuppressWarnings("unchecked") | ||
218 | @Override | ||
219 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { | ||
220 | // 1. try to move to data | ||
221 | int datas = Integer.bitCount(this.dataMap); | ||
222 | if(cursor.dataIndex != MapCursor.IndexFinish) { | ||
223 | int newDataIndex = cursor.dataIndex + 1; | ||
224 | if(newDataIndex < datas) { | ||
225 | cursor.dataIndex = newDataIndex; | ||
226 | cursor.key = (KEY) this.content[newDataIndex*2]; | ||
227 | cursor.value = (VALUE) this.content[newDataIndex*2+1]; | ||
228 | return true; | ||
229 | } else { | ||
230 | cursor.dataIndex = MapCursor.IndexFinish; | ||
231 | } | ||
232 | } | ||
233 | |||
234 | // 2. look inside the subnodes | ||
235 | int nodes = Integer.bitCount(this.nodeMap); | ||
236 | int newNodeIndex = cursor.nodeIndexStack.peek() + 1; | ||
237 | if(newNodeIndex < nodes) { | ||
238 | // 2.1 found next subnode, move down to the subnode | ||
239 | Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[this.content.length-1-newNodeIndex]; | ||
240 | cursor.dataIndex = MapCursor.IndexStart; | ||
241 | cursor.nodeIndexStack.pop(); | ||
242 | cursor.nodeIndexStack.push(newNodeIndex); | ||
243 | cursor.nodeIndexStack.push(MapCursor.IndexStart); | ||
244 | cursor.nodeStack.push(subnode); | ||
245 | return subnode.moveToNext(cursor); | ||
246 | } else { | ||
247 | // 3. no subnode found, move up | ||
248 | cursor.nodeStack.pop(); | ||
249 | cursor.nodeIndexStack.pop(); | ||
250 | if(!cursor.nodeStack.isEmpty()) { | ||
251 | Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); | ||
252 | return supernode.moveToNext(cursor); | ||
253 | } else { | ||
254 | cursor.key = null; | ||
255 | cursor.value = null; | ||
256 | return false; | ||
257 | } | ||
258 | } | ||
259 | } | ||
260 | |||
261 | @Override | ||
262 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
263 | for(int i = 0; i<depth; i++) { | ||
264 | builder.append("\t"); | ||
265 | } | ||
266 | if(code>=0) { | ||
267 | builder.append(code); | ||
268 | builder.append(":"); | ||
269 | } | ||
270 | builder.append("Immutable("); | ||
271 | boolean hadContent = false; | ||
272 | int dataMask = 1; | ||
273 | for(int i = 0; i<factor; i++) { | ||
274 | if((dataMask & dataMap) != 0) { | ||
275 | if(hadContent) { | ||
276 | builder.append(","); | ||
277 | } | ||
278 | builder.append(i); | ||
279 | builder.append(":["); | ||
280 | builder.append(content[2*index(dataMap, dataMask)].toString()); | ||
281 | builder.append("]->["); | ||
282 | builder.append(content[2*index(dataMap, dataMask)+1].toString()); | ||
283 | builder.append("]"); | ||
284 | hadContent = true; | ||
285 | } | ||
286 | dataMask<<=1; | ||
287 | } | ||
288 | builder.append(")"); | ||
289 | int nodeMask = 1; | ||
290 | for(int i = 0; i<factor; i++) { | ||
291 | if((nodeMask & nodeMap)!=0) { | ||
292 | @SuppressWarnings("unchecked") | ||
293 | Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) content[content.length-1-index(nodeMap, nodeMask)]; | ||
294 | builder.append("\n"); | ||
295 | subNode.prettyPrint(builder, depth+1, i); | ||
296 | } | ||
297 | nodeMask<<=1; | ||
298 | } | ||
299 | } | ||
300 | |||
301 | @Override | ||
302 | public int hashCode() { | ||
303 | return this.precalculatedHash; | ||
304 | } | ||
305 | |||
306 | @Override | ||
307 | public boolean equals(Object obj) { | ||
308 | if (this == obj) | ||
309 | return true; | ||
310 | if (obj == null) | ||
311 | return false; | ||
312 | if (obj instanceof ImmutableNode<?,?>) { | ||
313 | ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj; | ||
314 | if (precalculatedHash != other.precalculatedHash) | ||
315 | return false; | ||
316 | if (dataMap != other.dataMap) | ||
317 | return false; | ||
318 | if (nodeMap != other.nodeMap) | ||
319 | return false; | ||
320 | if (!Arrays.deepEquals(content, other.content)) | ||
321 | return false; | ||
322 | return true; | ||
323 | } else if(obj instanceof MutableNode<?,?>) { | ||
324 | return ImmutableNode.compareImmutableMutable(this, (MutableNode<?, ?>) obj); | ||
325 | } else { | ||
326 | return false; | ||
327 | } | ||
328 | } | ||
329 | public static boolean compareImmutableMutable( | ||
330 | ImmutableNode<?, ?> immutable, | ||
331 | MutableNode<?, ?> mutable) | ||
332 | { | ||
333 | int datas = 0; | ||
334 | int nodes = 0; | ||
335 | final int immutableLength = immutable.content.length; | ||
336 | for(int i = 0; i<factor; i++) { | ||
337 | Object key = mutable.content[i*2]; | ||
338 | // For each key candidate | ||
339 | if(key != null) { | ||
340 | // Check whether a new Key-Value pair can fit into the immutable container | ||
341 | if(datas*2+nodes+2 <= immutableLength) { | ||
342 | if( !immutable.content[datas*2].equals(key) || | ||
343 | !immutable.content[datas*2+1].equals(mutable.content[i*2+1])) | ||
344 | { | ||
345 | return false; | ||
346 | } | ||
347 | } else return false; | ||
348 | datas++; | ||
349 | } else { | ||
350 | Node<?,?> mutableSubnode = (Node<?, ?>) mutable.content[i*2+1]; | ||
351 | if(mutableSubnode != null) { | ||
352 | if(datas*2+nodes+1 <= immutableLength) { | ||
353 | Object immutableSubnode = immutable.content[immutableLength-1-nodes]; | ||
354 | if(!mutableSubnode.equals(immutableSubnode)) { | ||
355 | return false; | ||
356 | } | ||
357 | nodes++; | ||
358 | } else { | ||
359 | return false; | ||
360 | } | ||
361 | } | ||
362 | } | ||
363 | } | ||
364 | return true; | ||
365 | } | ||
366 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java new file mode 100644 index 00000000..6c177611 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java | |||
@@ -0,0 +1,131 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.ArrayDeque; | ||
4 | import java.util.ConcurrentModificationException; | ||
5 | import java.util.Iterator; | ||
6 | import java.util.List; | ||
7 | |||
8 | import org.eclipse.viatra.solver.data.map.Cursor; | ||
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
10 | |||
11 | public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | ||
12 | // Constants | ||
13 | static int IndexStart = -1; | ||
14 | static int IndexFinish = -2; | ||
15 | |||
16 | // Tree stack | ||
17 | ArrayDeque<Node<KEY,VALUE>> nodeStack; | ||
18 | ArrayDeque<Integer> nodeIndexStack; | ||
19 | int dataIndex; | ||
20 | |||
21 | // Values | ||
22 | KEY key; | ||
23 | VALUE value; | ||
24 | |||
25 | // Hash code for checking concurrent modifications | ||
26 | final VersionedMap<KEY,VALUE> map; | ||
27 | final int creationHash; | ||
28 | |||
29 | public MapCursor(Node<KEY, VALUE> root, VersionedMap<KEY,VALUE> map) { | ||
30 | // Initializing tree stack | ||
31 | super(); | ||
32 | this.nodeStack = new ArrayDeque<>(); | ||
33 | this.nodeIndexStack = new ArrayDeque<>(); | ||
34 | if(root != null) { | ||
35 | this.nodeStack.add(root); | ||
36 | this.nodeIndexStack.push(IndexStart); | ||
37 | } | ||
38 | |||
39 | this.dataIndex = IndexStart; | ||
40 | |||
41 | // Initializing cache | ||
42 | this.key = null; | ||
43 | this.value = null; | ||
44 | |||
45 | // Initializing state | ||
46 | this.map=map; | ||
47 | this.creationHash = map.hashCode(); | ||
48 | } | ||
49 | |||
50 | public KEY getKey() { | ||
51 | return key; | ||
52 | } | ||
53 | |||
54 | public VALUE getValue() { | ||
55 | return value; | ||
56 | } | ||
57 | |||
58 | public boolean isTerminated() { | ||
59 | return this.nodeStack.isEmpty(); | ||
60 | } | ||
61 | |||
62 | public boolean move() { | ||
63 | if(isDirty()) { | ||
64 | throw new ConcurrentModificationException(); | ||
65 | } | ||
66 | if(!isTerminated()) { | ||
67 | boolean result = this.nodeStack.peek().moveToNext(this); | ||
68 | if(this.nodeIndexStack.size() != this.nodeStack.size()) { | ||
69 | throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); | ||
70 | } | ||
71 | return result; | ||
72 | } | ||
73 | return false; | ||
74 | } | ||
75 | public boolean skipCurrentNode() { | ||
76 | nodeStack.pop(); | ||
77 | nodeIndexStack.pop(); | ||
78 | dataIndex = IndexFinish; | ||
79 | return move(); | ||
80 | } | ||
81 | @Override | ||
82 | public boolean isDirty() { | ||
83 | return this.map.hashCode() != this.creationHash; | ||
84 | } | ||
85 | @Override | ||
86 | public List<VersionedMap<KEY, VALUE>> getDependingMaps() { | ||
87 | return List.of(this.map); | ||
88 | } | ||
89 | |||
90 | public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) { | ||
91 | Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
92 | Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
93 | if(nodeOfCursor1 != null && nodeOfCursor2 != null) { | ||
94 | return nodeOfCursor1.equals(nodeOfCursor2); | ||
95 | } else { | ||
96 | return false; | ||
97 | } | ||
98 | } | ||
99 | |||
100 | /** | ||
101 | * | ||
102 | * @param <KEY> | ||
103 | * @param <VALUE> | ||
104 | * @param cursor1 | ||
105 | * @param cursor2 | ||
106 | * @returnv Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. | ||
107 | */ | ||
108 | public static <KEY,VALUE> int compare(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) { | ||
109 | // two cursors are equally deep | ||
110 | Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator(); | ||
111 | Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator(); | ||
112 | if(stack1.hasNext()) { | ||
113 | if(!stack2.hasNext()) { | ||
114 | // stack 2 has no more element, thus stack 1 is deeper | ||
115 | return 1; | ||
116 | } | ||
117 | int val1 = stack1.next(); | ||
118 | int val2 = stack2.next(); | ||
119 | if(val1 < val2) { | ||
120 | return -1; | ||
121 | } else if(val2 < val1) { | ||
122 | return 1; | ||
123 | } | ||
124 | } | ||
125 | if(stack2.hasNext()) { | ||
126 | // stack 2 has more element, thus stack 2 is deeper | ||
127 | return 1; | ||
128 | } | ||
129 | return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); | ||
130 | } | ||
131 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java new file mode 100644 index 00000000..8d7cda14 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java | |||
@@ -0,0 +1,208 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.List; | ||
4 | import java.util.stream.Collectors; | ||
5 | import java.util.stream.Stream; | ||
6 | |||
7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
8 | import org.eclipse.viatra.solver.data.map.Cursor; | ||
9 | import org.eclipse.viatra.solver.data.map.DiffCursor; | ||
10 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
11 | |||
12 | /** | ||
13 | * A cursor representing the difference between two states of a map. | ||
14 | * @author Oszkar Semerath | ||
15 | * | ||
16 | */ | ||
17 | public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor<KEY,VALUE>{ | ||
18 | /** | ||
19 | * Default value representing missing elements. | ||
20 | */ | ||
21 | private VALUE defaultValue; | ||
22 | private MapCursor<KEY,VALUE> cursor1; | ||
23 | private MapCursor<KEY,VALUE> cursor2; | ||
24 | private ContinousHashProvider<? super KEY> hashProvider; | ||
25 | |||
26 | // Values | ||
27 | private KEY key; | ||
28 | private VALUE fromValue; | ||
29 | private VALUE toValue; | ||
30 | |||
31 | // State | ||
32 | /** | ||
33 | * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. | ||
34 | */ | ||
35 | private int cursorRelation; | ||
36 | /** | ||
37 | * Denotes a state when two cursors are in the same position, but they contain different keys. | ||
38 | * Possible values: | ||
39 | * <ul> | ||
40 | * <li>0: not stuck</li> | ||
41 | * <li>1: hashClash, next it should return the key of cursor 1.</li> | ||
42 | * <li>2: hashClash, next it should return the key of cursor 2.</li> | ||
43 | * </ul> | ||
44 | */ | ||
45 | private int hashClash=0; | ||
46 | |||
47 | public MapDiffCursor(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, Cursor<KEY, VALUE> cursor1, Cursor<KEY, VALUE> cursor2) { | ||
48 | super(); | ||
49 | this.hashProvider = hashProvider; | ||
50 | this.defaultValue = defaultValue; | ||
51 | this.cursor1 = (MapCursor<KEY, VALUE>) cursor1; | ||
52 | this.cursor2 = (MapCursor<KEY, VALUE>) cursor2; | ||
53 | } | ||
54 | |||
55 | public KEY getKey() { | ||
56 | return key; | ||
57 | } | ||
58 | public VALUE getFromValue() { | ||
59 | return fromValue; | ||
60 | } | ||
61 | public VALUE getToValue() { | ||
62 | return toValue; | ||
63 | } | ||
64 | @Override | ||
65 | public VALUE getValue() { | ||
66 | return getToValue(); | ||
67 | } | ||
68 | public boolean isTerminated() { | ||
69 | return cursor1.isTerminated() && cursor2.isTerminated(); | ||
70 | } | ||
71 | @Override | ||
72 | public boolean isDirty() { | ||
73 | return this.cursor1.isDirty() || this.cursor2.isDirty(); | ||
74 | } | ||
75 | @Override | ||
76 | public List<VersionedMap<KEY, VALUE>> getDependingMaps() { | ||
77 | return Stream.concat( | ||
78 | cursor1.getDependingMaps().stream(), | ||
79 | cursor2.getDependingMaps().stream() | ||
80 | ).collect(Collectors.toList()); | ||
81 | } | ||
82 | |||
83 | protected void updateState() { | ||
84 | if(!isTerminated()) { | ||
85 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | ||
86 | if(cursorRelation > 0 || cursor2.isTerminated()) { | ||
87 | this.key = cursor1.getKey(); | ||
88 | this.fromValue = cursor1.getValue(); | ||
89 | this.toValue = defaultValue; | ||
90 | } else if(cursorRelation < 0 || cursor1.isTerminated()){ | ||
91 | this.key = cursor2.getKey(); | ||
92 | this.fromValue = defaultValue; | ||
93 | this.toValue = cursor1.getValue(); | ||
94 | } else { | ||
95 | // cursor1 = cursor2 | ||
96 | if(cursor1.getKey().equals(cursor2.getKey())) { | ||
97 | this.key = cursor1.getKey(); | ||
98 | this.fromValue = cursor1.getValue(); | ||
99 | this.toValue = defaultValue; | ||
100 | } else { | ||
101 | resolveHashClash1(); | ||
102 | } | ||
103 | } | ||
104 | } | ||
105 | } | ||
106 | protected void resolveHashClash1() { | ||
107 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | ||
108 | if(compareResult<0) { | ||
109 | this.hashClash = 2; | ||
110 | this.cursorRelation = 0; | ||
111 | this.key = cursor1.key; | ||
112 | this.fromValue = cursor1.value; | ||
113 | this.toValue = defaultValue; | ||
114 | } else if(compareResult>0) { | ||
115 | this.hashClash = 1; | ||
116 | this.cursorRelation = 0; | ||
117 | this.key = cursor2.key; | ||
118 | this.fromValue = defaultValue; | ||
119 | this.toValue = cursor2.value; | ||
120 | } else { | ||
121 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
122 | } | ||
123 | } | ||
124 | protected boolean isInHashClash() { | ||
125 | return this.hashClash != 0; | ||
126 | } | ||
127 | protected void resolveHashClash2() { | ||
128 | if(hashClash == 1) { | ||
129 | this.hashClash = 0; | ||
130 | this.cursorRelation = 0; | ||
131 | this.key = cursor1.key; | ||
132 | this.fromValue = cursor1.value; | ||
133 | this.toValue = defaultValue; | ||
134 | } else if(hashClash == 2) { | ||
135 | this.hashClash = 0; | ||
136 | this.cursorRelation = 0; | ||
137 | this.key = cursor2.key; | ||
138 | this.fromValue = defaultValue; | ||
139 | this.toValue = cursor2.value; | ||
140 | } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
141 | } | ||
142 | |||
143 | |||
144 | protected boolean sameValues() { | ||
145 | return this.fromValue == this.toValue; | ||
146 | } | ||
147 | protected boolean moveOne() { | ||
148 | if(isTerminated()) { | ||
149 | return false; | ||
150 | } | ||
151 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { | ||
152 | return cursor1.move(); | ||
153 | } else if(this.cursorRelation < 0 || cursor1.isTerminated()) { | ||
154 | return cursor2.move(); | ||
155 | } else { | ||
156 | boolean moved1 = cursor1.move(); | ||
157 | boolean moved2 = cursor2.move(); | ||
158 | return moved1 && moved2; | ||
159 | } | ||
160 | } | ||
161 | private boolean skipNode() { | ||
162 | if(isTerminated()) { | ||
163 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); | ||
164 | } | ||
165 | boolean update1 = cursor1.skipCurrentNode(); | ||
166 | boolean update2 = cursor2.skipCurrentNode(); | ||
167 | updateState(); | ||
168 | return update1 && update2; | ||
169 | } | ||
170 | |||
171 | protected boolean moveToConsistentState() { | ||
172 | if(!isTerminated()) { | ||
173 | boolean changed; | ||
174 | boolean lastResult = true; | ||
175 | do { | ||
176 | changed = false; | ||
177 | if(MapCursor.sameSubnode(cursor1, cursor2)) { | ||
178 | lastResult = skipNode(); | ||
179 | changed = true; | ||
180 | } | ||
181 | if(sameValues()) { | ||
182 | lastResult = moveOne(); | ||
183 | changed = true; | ||
184 | } | ||
185 | updateState(); | ||
186 | } while(changed && !isTerminated()); | ||
187 | return lastResult; | ||
188 | } else { | ||
189 | return false; | ||
190 | } | ||
191 | } | ||
192 | |||
193 | public boolean move() { | ||
194 | if(!isTerminated()) { | ||
195 | if(isInHashClash()) { | ||
196 | this.resolveHashClash2(); | ||
197 | return true; | ||
198 | } else { | ||
199 | if(moveOne()) { | ||
200 | return moveToConsistentState(); | ||
201 | } else { | ||
202 | return false; | ||
203 | } | ||
204 | } | ||
205 | |||
206 | } else return false; | ||
207 | } | ||
208 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java new file mode 100644 index 00000000..963ce111 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java | |||
@@ -0,0 +1,411 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Arrays; | ||
4 | import java.util.Map; | ||
5 | |||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
7 | |||
8 | public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | ||
9 | int cachedHash; | ||
10 | protected Object[] content; | ||
11 | |||
12 | protected MutableNode() { | ||
13 | this.content = new Object[2*factor]; | ||
14 | updateHash(); | ||
15 | } | ||
16 | public static <KEY,VALUE> MutableNode<KEY,VALUE> initialize( | ||
17 | KEY key, VALUE value, | ||
18 | ContinousHashProvider<? super KEY> hashProvider, | ||
19 | VALUE defaultValue) | ||
20 | { | ||
21 | if(value == defaultValue) { | ||
22 | return null; | ||
23 | } else { | ||
24 | int hash = hashProvider.getHash(key, 0); | ||
25 | int fragment = hashFragment(hash, 0); | ||
26 | MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>(); | ||
27 | res.content[2*fragment] = key; | ||
28 | res.content[2*fragment+1] = value; | ||
29 | res.updateHash(); | ||
30 | return res; | ||
31 | } | ||
32 | } | ||
33 | |||
34 | /** | ||
35 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} | ||
36 | * @param node | ||
37 | */ | ||
38 | protected MutableNode(ImmutableNode<KEY,VALUE> node) { | ||
39 | this.content = new Object[2*factor]; | ||
40 | int dataUsed=0; | ||
41 | int nodeUsed=0; | ||
42 | for(int i=0; i<factor; i++) { | ||
43 | int bitposition = 1 << i; | ||
44 | if((node.dataMap & bitposition) != 0) { | ||
45 | content[2*i] = node.content[dataUsed*2]; | ||
46 | content[2*i+1] = node.content[dataUsed*2+1]; | ||
47 | dataUsed++; | ||
48 | } else if((node.nodeMap & bitposition) != 0) { | ||
49 | content[2*i+1] = node.content[node.content.length-1-nodeUsed]; | ||
50 | nodeUsed++; | ||
51 | } | ||
52 | } | ||
53 | this.cachedHash = node.hashCode(); | ||
54 | } | ||
55 | |||
56 | @SuppressWarnings("unchecked") | ||
57 | @Override | ||
58 | public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | ||
59 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | ||
60 | KEY keyCandidate = (KEY) this.content[2*selectedHashFragment]; | ||
61 | if(keyCandidate != null) { | ||
62 | if(keyCandidate.equals(key)) { | ||
63 | return (VALUE) this.content[2*selectedHashFragment+1]; | ||
64 | } else { | ||
65 | return defaultValue; | ||
66 | } | ||
67 | } else { | ||
68 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; | ||
69 | if(nodeCandidate != null) { | ||
70 | int newDepth = depth+1; | ||
71 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
72 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); | ||
73 | } else { | ||
74 | return defaultValue; | ||
75 | } | ||
76 | } | ||
77 | } | ||
78 | |||
79 | private boolean hasContent() { | ||
80 | for(Object element : this.content) { | ||
81 | if(element != null) return true; | ||
82 | } | ||
83 | return false; | ||
84 | } | ||
85 | |||
86 | @SuppressWarnings("unchecked") | ||
87 | @Override | ||
88 | public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | ||
89 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | ||
90 | KEY keyCandidate = (KEY) content[2*selectedHashFragment]; | ||
91 | if(keyCandidate != null) { | ||
92 | // If has key | ||
93 | if(keyCandidate.equals(key)) { | ||
94 | // The key is equals to an existing key -> update entry | ||
95 | if(value == defaultValue) { | ||
96 | return removeEntry(selectedHashFragment); | ||
97 | } else { | ||
98 | return updateValue(value,selectedHashFragment); | ||
99 | } | ||
100 | } else { | ||
101 | // The key is not equivalent to an existing key on the same hash bin | ||
102 | // -> split entry if it is necessary | ||
103 | if(value == defaultValue) { | ||
104 | // Value is default -> do not need to add new node | ||
105 | return this; | ||
106 | } else { | ||
107 | // Value is not default -> Split entry data to a new node | ||
108 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); | ||
109 | } | ||
110 | } | ||
111 | } else { | ||
112 | // If it does not have key, check for value | ||
113 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; | ||
114 | if(nodeCandidate != null) { | ||
115 | // If it has value, it is a subnode -> upate that | ||
116 | Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1); | ||
117 | return updateSubNode(selectedHashFragment,newNode); | ||
118 | } else { | ||
119 | // If it does not have value, put it in the empty place | ||
120 | if(value == defaultValue) { | ||
121 | // dont need to add new key-value pair | ||
122 | return this; | ||
123 | } else { | ||
124 | return addEntry(key, value, selectedHashFragment); | ||
125 | } | ||
126 | |||
127 | } | ||
128 | } | ||
129 | } | ||
130 | |||
131 | |||
132 | |||
133 | private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) { | ||
134 | content[2*selectedHashFragment] = key; | ||
135 | content[2*selectedHashFragment+1] = value; | ||
136 | updateHash(); | ||
137 | return this; | ||
138 | } | ||
139 | /** | ||
140 | * Updates an entry in a selected hash-fragment to a non-default value. | ||
141 | * @param value | ||
142 | * @param selectedHashFragment | ||
143 | * @return | ||
144 | */ | ||
145 | Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) { | ||
146 | content[2*selectedHashFragment+1] = value; | ||
147 | updateHash(); | ||
148 | return this; | ||
149 | } | ||
150 | |||
151 | /** | ||
152 | * | ||
153 | * @param selectedHashFragment | ||
154 | * @param newNode | ||
155 | * @return | ||
156 | */ | ||
157 | Node<KEY, VALUE> updateSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode) { | ||
158 | content[2*selectedHashFragment+1] = newNode; | ||
159 | for(int i = 0; i<this.content.length; i++) { | ||
160 | if(content[i]!=null) { | ||
161 | updateHash(); | ||
162 | return this; | ||
163 | } | ||
164 | } | ||
165 | return null; | ||
166 | } | ||
167 | |||
168 | @SuppressWarnings("unchecked") | ||
169 | private Node<KEY, VALUE> moveDownAndSplit( | ||
170 | ContinousHashProvider<? super KEY> hashProvider, | ||
171 | KEY newKey, VALUE newValue, KEY previousKey, | ||
172 | int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) | ||
173 | { | ||
174 | VALUE previousValue = (VALUE) content[2*selectedHashFragmentOfCurrentDepth+1]; | ||
175 | |||
176 | //final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); | ||
177 | MutableNode<KEY,VALUE> newSubNode = newNodeWithTwoEntries( | ||
178 | hashProvider, | ||
179 | previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), | ||
180 | newKey, newValue, hashOfNewKey, | ||
181 | depth+1); | ||
182 | |||
183 | content[2*selectedHashFragmentOfCurrentDepth] = null; | ||
184 | content[2*selectedHashFragmentOfCurrentDepth+1] = newSubNode; | ||
185 | updateHash(); | ||
186 | return this; | ||
187 | } | ||
188 | private MutableNode<KEY,VALUE> newNodeWithTwoEntries( | ||
189 | ContinousHashProvider<? super KEY> hashProvider, | ||
190 | KEY key1, VALUE value1, int oldHash1, | ||
191 | KEY key2, VALUE value2, int oldHash2, | ||
192 | int newdepth) | ||
193 | { | ||
194 | // final int depthLimit = 4000; | ||
195 | // if(newdepth>depthLimit) { | ||
196 | // final int newHashes = 4000/numberOfFactors; | ||
197 | // throw new IllegalArgumentException( | ||
198 | // "Continuous hash was same " + newHashes + " times for non-equivalent objects " + key1 + " and " + key2 +"."); | ||
199 | // } | ||
200 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | ||
201 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | ||
202 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | ||
203 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); | ||
204 | |||
205 | MutableNode<KEY,VALUE> subNode = new MutableNode<KEY,VALUE>(); | ||
206 | if(newFragment1 != newFragment2) { | ||
207 | subNode.content[newFragment1*2]=key1; | ||
208 | subNode.content[newFragment1*2+1]=value1; | ||
209 | |||
210 | subNode.content[newFragment2*2]=key2; | ||
211 | subNode.content[newFragment2*2+1]=value2; | ||
212 | } else { | ||
213 | MutableNode<KEY,VALUE> subSubNode = newNodeWithTwoEntries( | ||
214 | hashProvider, | ||
215 | key1, value1, newHash1, | ||
216 | key2, value2, newHash2, | ||
217 | newdepth+1); | ||
218 | subNode.content[newFragment1*2+1] = subSubNode; | ||
219 | } | ||
220 | subNode.updateHash(); | ||
221 | return subNode; | ||
222 | } | ||
223 | |||
224 | Node<KEY, VALUE> removeEntry(int selectedHashFragment) { | ||
225 | content[2*selectedHashFragment] = null; | ||
226 | content[2*selectedHashFragment+1] = null; | ||
227 | if(hasContent()) { | ||
228 | updateHash(); | ||
229 | return this; | ||
230 | } else { | ||
231 | return null; | ||
232 | } | ||
233 | } | ||
234 | |||
235 | @SuppressWarnings("unchecked") | ||
236 | @Override | ||
237 | public long getSize() { | ||
238 | int size = 0; | ||
239 | for(int i=0; i<factor; i++) { | ||
240 | if(content[i*2]!=null) { | ||
241 | size++; | ||
242 | } else{ | ||
243 | Node<KEY,VALUE> nodeCandidate = (Node<KEY, VALUE>) content[i*2+1]; | ||
244 | if(nodeCandidate!=null) { | ||
245 | size+=nodeCandidate.getSize(); | ||
246 | } | ||
247 | } | ||
248 | } | ||
249 | return size; | ||
250 | } | ||
251 | |||
252 | @Override | ||
253 | protected MutableNode<KEY,VALUE> toMutable() { | ||
254 | return this; | ||
255 | } | ||
256 | |||
257 | @Override | ||
258 | public ImmutableNode<KEY,VALUE> toImmutable() { | ||
259 | return ImmutableNode.constructImmutable(this,null); | ||
260 | } | ||
261 | |||
262 | @Override | ||
263 | public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) { | ||
264 | return ImmutableNode.constructImmutable(this,cache); | ||
265 | } | ||
266 | |||
267 | @SuppressWarnings("unchecked") | ||
268 | @Override | ||
269 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { | ||
270 | // 1. try to move to data | ||
271 | if(cursor.dataIndex != MapCursor.IndexFinish) { | ||
272 | for(int index = cursor.dataIndex+1; index < factor; index++) { | ||
273 | if(this.content[index*2]!=null) { | ||
274 | // 1.1 found next data | ||
275 | cursor.dataIndex = index; | ||
276 | cursor.key = (KEY) this.content[index*2]; | ||
277 | cursor.value = (VALUE) this.content[index*2+1]; | ||
278 | return true; | ||
279 | } | ||
280 | } | ||
281 | cursor.dataIndex = MapCursor.IndexFinish; | ||
282 | } | ||
283 | |||
284 | // 2. look inside the subnodes | ||
285 | for(int index = cursor.nodeIndexStack.peek()+1; index < factor; index++) { | ||
286 | if(this.content[index*2]==null && this.content[index*2+1] !=null) { | ||
287 | // 2.1 found next subnode, move down to the subnode | ||
288 | Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index*2+1]; | ||
289 | |||
290 | cursor.dataIndex = MapCursor.IndexStart; | ||
291 | cursor.nodeIndexStack.pop(); | ||
292 | cursor.nodeIndexStack.push(index); | ||
293 | cursor.nodeIndexStack.push(MapCursor.IndexStart); | ||
294 | cursor.nodeStack.push(subnode); | ||
295 | |||
296 | |||
297 | return subnode.moveToNext(cursor); | ||
298 | } | ||
299 | } | ||
300 | // 3. no subnode found, move up | ||
301 | cursor.nodeStack.pop(); | ||
302 | cursor.nodeIndexStack.pop(); | ||
303 | if(!cursor.nodeStack.isEmpty()) { | ||
304 | Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); | ||
305 | return supernode.moveToNext(cursor); | ||
306 | } else { | ||
307 | cursor.key = null; | ||
308 | cursor.value = null; | ||
309 | return false; | ||
310 | } | ||
311 | } | ||
312 | |||
313 | @Override | ||
314 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
315 | for(int i = 0; i<depth; i++) { | ||
316 | builder.append("\t"); | ||
317 | } | ||
318 | if(code>=0) { | ||
319 | builder.append(code); | ||
320 | builder.append(":"); | ||
321 | } | ||
322 | builder.append("Mutable("); | ||
323 | // print content | ||
324 | boolean hadContent = false; | ||
325 | for(int i = 0; i<factor; i++) { | ||
326 | if(content[2*i] != null) { | ||
327 | if(hadContent) { | ||
328 | builder.append(","); | ||
329 | } | ||
330 | builder.append(i); | ||
331 | builder.append(":["); | ||
332 | builder.append(content[2*i].toString()); | ||
333 | builder.append("]->["); | ||
334 | builder.append(content[2*i+1].toString()); | ||
335 | builder.append("]"); | ||
336 | hadContent = true; | ||
337 | } | ||
338 | } | ||
339 | builder.append(")"); | ||
340 | // print subnodes | ||
341 | for(int i = 0; i<factor; i++) { | ||
342 | if(content[2*i] == null && content[2*i+1]!=null) { | ||
343 | @SuppressWarnings("unchecked") | ||
344 | Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) content[2*i+1]; | ||
345 | builder.append("\n"); | ||
346 | subNode.prettyPrint(builder, depth+1, i); | ||
347 | } | ||
348 | } | ||
349 | } | ||
350 | @SuppressWarnings({"unchecked"}) | ||
351 | @Override | ||
352 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) { | ||
353 | for(int i = 0; i<factor; i++) { | ||
354 | if(this.content[2*i] != null) { | ||
355 | KEY key = (KEY) this.content[2*i]; | ||
356 | VALUE value = (VALUE) this.content[2*i+1]; | ||
357 | |||
358 | if(value == defaultValue) { | ||
359 | throw new IllegalStateException("Node contains default value!"); | ||
360 | } | ||
361 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); | ||
362 | int shiftDepth = shiftDepth(depth); | ||
363 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); | ||
364 | if(i != selectedHashFragment) { | ||
365 | throw new IllegalStateException( | ||
366 | "Key "+key+" with hash code "+hashCode+" is in bad place! Fragment=" + selectedHashFragment +", Place="+i); | ||
367 | } | ||
368 | } | ||
369 | } | ||
370 | for(int i = 0; i<factor; i++) { | ||
371 | if(this.content[2*i+1] != null && this.content[2*i] == null) { | ||
372 | Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) this.content[2*i+1]; | ||
373 | subNode.checkIntegrity(hashProvider, defaultValue, depth+1); | ||
374 | } | ||
375 | } | ||
376 | int oldHash = this.cachedHash; | ||
377 | updateHash(); | ||
378 | int newHash = this.cachedHash; | ||
379 | if(oldHash != newHash) { | ||
380 | throw new IllegalStateException("Hash code was not up to date! (old="+oldHash+",new="+newHash+")"); | ||
381 | } | ||
382 | } | ||
383 | |||
384 | |||
385 | protected void updateHash() { | ||
386 | this.cachedHash = Arrays.hashCode(content); | ||
387 | } | ||
388 | |||
389 | @Override | ||
390 | public int hashCode() { | ||
391 | return this.cachedHash; | ||
392 | } | ||
393 | |||
394 | |||
395 | @Override | ||
396 | public boolean equals(Object obj) { | ||
397 | if (this == obj) | ||
398 | return true; | ||
399 | if (obj == null) | ||
400 | return false; | ||
401 | if (obj instanceof MutableNode<?, ?>) { | ||
402 | MutableNode<?,?> other = (MutableNode<?,?>) obj; | ||
403 | return Arrays.deepEquals(this.content, other.content); | ||
404 | } else if(obj instanceof ImmutableNode<?,?>) { | ||
405 | ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj; | ||
406 | return ImmutableNode.compareImmutableMutable(other, this); | ||
407 | } else { | ||
408 | return false; | ||
409 | } | ||
410 | } | ||
411 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java new file mode 100644 index 00000000..3695825d --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java | |||
@@ -0,0 +1,86 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Map; | ||
4 | |||
5 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
6 | |||
7 | public abstract class Node<KEY,VALUE>{ | ||
8 | protected static final int branchingFactorBit = 5; | ||
9 | protected static final int factor = 1<<branchingFactorBit; | ||
10 | protected static final int numberOfFactors = Integer.SIZE / branchingFactorBit; | ||
11 | protected static final int factorMask = factor-1; | ||
12 | public static final int effectiveBits = branchingFactorBit * numberOfFactors; | ||
13 | |||
14 | /** | ||
15 | * Calculates the index for the continuous hash. | ||
16 | * @param depth The depth of the node in the tree. | ||
17 | * @return The index of the continuous hash. | ||
18 | */ | ||
19 | protected static int hashDepth(int depth) { | ||
20 | return depth/numberOfFactors; | ||
21 | } | ||
22 | |||
23 | /** | ||
24 | * Calculates the which segment of a single hash should be used. | ||
25 | * @param depth The depth of the node in the tree. | ||
26 | * @return The segment of a hash code. | ||
27 | */ | ||
28 | protected static int shiftDepth(int depth) { | ||
29 | return depth%numberOfFactors; | ||
30 | } | ||
31 | /** | ||
32 | * Selects a segments from a complete hash for a given depth. | ||
33 | * @param hash A complete hash. | ||
34 | * @param shiftDepth The index of the segment. | ||
35 | * @return The segment as an integer. | ||
36 | */ | ||
37 | protected static int hashFragment(int hash, int shiftDepth) { | ||
38 | if(shiftDepth<0 && 5<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); | ||
39 | return (hash >>> shiftDepth*branchingFactorBit) & factorMask; | ||
40 | } | ||
41 | |||
42 | /** | ||
43 | * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1. | ||
44 | * @param key The key. | ||
45 | * @param hash Hash code for depth-1 | ||
46 | * @param depth The depth. | ||
47 | * @return The new hash code. | ||
48 | */ | ||
49 | protected int newHash(final ContinousHashProvider<? super KEY> hashProvider, KEY key, int hash, int depth) { | ||
50 | final int hashDepth = hashDepth(depth); | ||
51 | if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) { | ||
52 | throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!"); | ||
53 | } | ||
54 | return depth%numberOfFactors == 0? | ||
55 | hashProvider.getHash(key, hashDepth) : | ||
56 | hash; | ||
57 | } | ||
58 | |||
59 | |||
60 | abstract public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth); | ||
61 | abstract public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth); | ||
62 | abstract public long getSize(); | ||
63 | |||
64 | abstract MutableNode<KEY, VALUE> toMutable(); | ||
65 | public abstract ImmutableNode<KEY, VALUE> toImmutable(); | ||
66 | public abstract ImmutableNode<KEY, VALUE> toImmutable( | ||
67 | Map<Node<KEY, VALUE>,ImmutableNode<KEY, VALUE>> cache); | ||
68 | |||
69 | /** | ||
70 | * Moves a {@link MapCursor} to its next position. | ||
71 | * @param cursor the cursor | ||
72 | * @return Whether there was a next value to move on. | ||
73 | */ | ||
74 | abstract boolean moveToNext(MapCursor<KEY,VALUE> cursor); | ||
75 | |||
76 | ///////// FOR printing | ||
77 | abstract public void prettyPrint(StringBuilder builder, int depth, int code); | ||
78 | @Override | ||
79 | public String toString() { | ||
80 | StringBuilder stringBuilder = new StringBuilder(); | ||
81 | prettyPrint(stringBuilder, 0, -1); | ||
82 | return stringBuilder.toString(); | ||
83 | } | ||
84 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) {} | ||
85 | |||
86 | } | ||
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java new file mode 100644 index 00000000..715a9d74 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java | |||
@@ -0,0 +1,168 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Iterator; | ||
4 | import java.util.LinkedList; | ||
5 | import java.util.List; | ||
6 | |||
7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
8 | import org.eclipse.viatra.solver.data.map.Cursor; | ||
9 | import org.eclipse.viatra.solver.data.map.DiffCursor; | ||
10 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
11 | import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; | ||
12 | |||
13 | /** | ||
14 | * Not threadSafe in itself | ||
15 | * @author Oszkar Semerath | ||
16 | * | ||
17 | * @param <KEY> | ||
18 | * @param <VALUE> | ||
19 | */ | ||
20 | public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{ | ||
21 | protected final VersionedMapStoreImpl<KEY,VALUE> store; | ||
22 | |||
23 | protected final ContinousHashProvider<? super KEY> hashProvider; | ||
24 | protected final VALUE defaultValue; | ||
25 | protected Node<KEY,VALUE> root; | ||
26 | |||
27 | public VersionedMapImpl( | ||
28 | VersionedMapStoreImpl<KEY,VALUE> store, | ||
29 | ContinousHashProvider<? super KEY> hashProvider, | ||
30 | VALUE defaultValue) | ||
31 | { | ||
32 | this.store = store; | ||
33 | this.hashProvider = hashProvider; | ||
34 | this.defaultValue = defaultValue; | ||
35 | this.root = null; | ||
36 | } | ||
37 | public VersionedMapImpl( | ||
38 | VersionedMapStoreImpl<KEY,VALUE> store, | ||
39 | ContinousHashProvider<? super KEY> hashProvider, | ||
40 | VALUE defaultValue, Node<KEY,VALUE> data) | ||
41 | { | ||
42 | this.store = store; | ||
43 | this.hashProvider = hashProvider; | ||
44 | this.defaultValue = defaultValue; | ||
45 | this.root = data; | ||
46 | } | ||
47 | |||
48 | public VALUE getDefaultValue() { | ||
49 | return defaultValue; | ||
50 | } | ||
51 | public ContinousHashProvider<? super KEY> getHashProvider() { | ||
52 | return hashProvider; | ||
53 | } | ||
54 | @Override | ||
55 | public void put(KEY key, VALUE value) { | ||
56 | if(root!=null) { | ||
57 | root = root.putValue(key, value, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); | ||
58 | } else { | ||
59 | root = MutableNode.initialize(key, value, hashProvider, defaultValue); | ||
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 | |||
84 | @Override | ||
85 | public VALUE get(KEY key) { | ||
86 | if(root!=null) { | ||
87 | return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); | ||
88 | } else { | ||
89 | return defaultValue; | ||
90 | } | ||
91 | } | ||
92 | @Override | ||
93 | public long getSize() { | ||
94 | if(root == null) { | ||
95 | return 0; | ||
96 | } else { | ||
97 | return root.getSize(); | ||
98 | } | ||
99 | } | ||
100 | |||
101 | @Override | ||
102 | public Cursor<KEY, VALUE> getCursor() { | ||
103 | MapCursor<KEY,VALUE> cursor = new MapCursor<>(this.root,this); | ||
104 | return cursor; | ||
105 | } | ||
106 | @Override | ||
107 | public DiffCursor<KEY, VALUE> getDiffCursor(long toVersion) { | ||
108 | Cursor<KEY, VALUE> fromCursor = this.getCursor(); | ||
109 | VersionedMap<KEY, VALUE> toMap = this.store.createMap(toVersion); | ||
110 | Cursor<KEY, VALUE> toCursor = toMap.getCursor(); | ||
111 | return new MapDiffCursor<KEY, VALUE>(this.hashProvider,this.defaultValue, fromCursor, toCursor); | ||
112 | |||
113 | } | ||
114 | |||
115 | |||
116 | @Override | ||
117 | public long commit() { | ||
118 | return this.store.commit(root,this); | ||
119 | } | ||
120 | public void setRoot(Node<KEY, VALUE> root) { | ||
121 | this.root = root; | ||
122 | } | ||
123 | |||
124 | @Override | ||
125 | public void restore(long state) { | ||
126 | root = this.store.revert(state); | ||
127 | } | ||
128 | |||
129 | @Override | ||
130 | public int hashCode() { | ||
131 | final int prime = 31; | ||
132 | int result = 1; | ||
133 | result = prime * result + ((root == null) ? 0 : root.hashCode()); | ||
134 | return result; | ||
135 | } | ||
136 | |||
137 | @Override | ||
138 | public boolean equals(Object obj) { | ||
139 | if (this == obj) | ||
140 | return true; | ||
141 | if (obj == null) | ||
142 | return false; | ||
143 | if (getClass() != obj.getClass()) | ||
144 | return false; | ||
145 | VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj; | ||
146 | if (root == null) { | ||
147 | if (other.root != null) | ||
148 | return false; | ||
149 | } else if (!root.equals(other.root)) | ||
150 | return false; | ||
151 | return true; | ||
152 | } | ||
153 | public void prettyPrint() { | ||
154 | StringBuilder s = new StringBuilder(); | ||
155 | if(this.root != null) { | ||
156 | this.root.prettyPrint(s, 0, -1); | ||
157 | System.out.println(s.toString()); | ||
158 | } else { | ||
159 | System.out.println("empty tree"); | ||
160 | } | ||
161 | } | ||
162 | public void checkIntegrity() { | ||
163 | if(this.root != null) { | ||
164 | this.root.checkIntegrity(hashProvider, defaultValue, 0); | ||
165 | } | ||
166 | } | ||
167 | |||
168 | } | ||