aboutsummaryrefslogtreecommitdiffstats
path: root/store/src/main/java/org/eclipse/viatra/solver/data/map
diff options
context:
space:
mode:
Diffstat (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map')
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java69
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java14
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java57
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java6
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java26
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java7
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java13
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java14
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java48
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java135
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java18
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java378
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java131
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java221
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java456
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java85
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java19
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java171
18 files changed, 0 insertions, 1868 deletions
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
deleted file mode 100644
index dd64f901..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
+++ /dev/null
@@ -1,69 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import org.eclipse.viatra.solver.data.map.internal.Node;
4
5/**
6 * A class representing an equivalence relation for a type {@code K} with a
7 * continuous hash function.
8 *
9 * @author Oszkar Semerath
10 *
11 * @param <K> Target java type.
12 */
13public interface ContinousHashProvider<K> {
14 public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
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 (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
52 int hash1 = getEffectiveHash(key1, i);
53 int hash2 = getEffectiveHash(key2, i);
54 for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
55 final int factorMask = (1<<Node.BRANCHING_FACTOR_BITS)-1;
56 int hashFragment1 = (hash1>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
57 int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
58 var result = Integer.compare(hashFragment1, hashFragment2);
59 if (result != 0) {
60 return result;
61 }
62 }
63 }
64 throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
65 + ") have the same hashcode over the practical depth limitation ("
66 + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
67 }
68 }
69}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
deleted file mode 100644
index e45b1f20..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
+++ /dev/null
@@ -1,14 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.List;
4
5public interface Cursor<K,V> {
6 public K getKey();
7 public V getValue();
8 public boolean isTerminated();
9 public boolean move();
10 public boolean isDirty();
11
12 @SuppressWarnings("squid:S1452")
13 public List<VersionedMap<?,?>> getDependingMaps();
14}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java
deleted file mode 100644
index b29b3119..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/CursorAsIterator.java
+++ /dev/null
@@ -1,57 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.Iterator;
4import java.util.NoSuchElementException;
5import java.util.function.BiFunction;
6import java.util.function.BiPredicate;
7
8public class CursorAsIterator<K,V,D> implements Iterator<D> {
9 private final Cursor<K, V> internal;
10 private final BiFunction<K, V, D> entryTransformation;
11 private final BiPredicate<K,V> filtering;
12
13 D lastValidElement;
14
15 public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
16 this.internal = internal;
17 this.entryTransformation = entryTransformation;
18 this.filtering = filtering;
19
20 moveToNext();
21 }
22 public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation) {
23 this.internal = internal;
24 this.entryTransformation = entryTransformation;
25 this.filtering = ((k,v)->true);
26
27 moveToNext();
28 }
29
30 private void moveToNext() {
31 internal.move();
32 while(!internal.isTerminated() && !filtering.test(internal.getKey(), internal.getValue())) {
33 internal.move();
34 }
35 if(!internal.isTerminated()) {
36 lastValidElement = entryTransformation.apply(internal.getKey(), internal.getValue());
37 }
38 }
39
40
41 @Override
42 public boolean hasNext() {
43 return !internal.isTerminated();
44 }
45 @Override
46 public D next() {
47 if(hasNext()) {
48 D last = lastValidElement;
49 moveToNext();
50 return last;
51 } else {
52 throw new NoSuchElementException();
53 }
54
55 }
56
57}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
deleted file mode 100644
index f0af1436..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
+++ /dev/null
@@ -1,6 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface DiffCursor<K, V> extends Cursor<K,V> {
4 public V getFromValue();
5 public V getToValue();
6} \ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java
deleted file mode 100644
index 22b5e6c1..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/MapAsIterable.java
+++ /dev/null
@@ -1,26 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.Iterator;
4import java.util.function.BiFunction;
5import java.util.function.BiPredicate;
6
7public class MapAsIterable<K,V,D> implements Iterable<D> {
8 private final VersionedMap<K, V> internal;
9 private final BiFunction<K, V, D> entryTransformation;
10 private final BiPredicate<K,V> filtering;
11
12 public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
13 this.internal = internal;
14 this.entryTransformation = entryTransformation;
15 this.filtering = filtering;
16 }
17 public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation) {
18 this.internal = internal;
19 this.entryTransformation = entryTransformation;
20 this.filtering = ((k,v)->true);
21 }
22 @Override
23 public Iterator<D> iterator() {
24 return new CursorAsIterator<>(internal.getAll(), entryTransformation, filtering);
25 }
26}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
deleted file mode 100644
index e46be237..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
+++ /dev/null
@@ -1,7 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface Versioned {
4 public long commit();
5 //maybe revert()?
6 public void restore(long state);
7}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
deleted file mode 100644
index 3a35b9f0..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
+++ /dev/null
@@ -1,13 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface VersionedMap<K,V> extends Versioned{
4 public V get(K key);
5 public Cursor<K,V> getAll();
6
7 public V put(K key, V value);
8 public void putAll(Cursor<K,V> cursor);
9
10 public long getSize();
11
12 public DiffCursor<K,V> getDiffCursor(long state);
13}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
deleted file mode 100644
index 0ff0773f..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
+++ /dev/null
@@ -1,14 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.Set;
4
5public interface VersionedMapStore<K, V> {
6
7 public VersionedMap<K, V> createMap();
8
9 public VersionedMap<K, V> createMap(long state);
10
11 public Set<Long> getStates();
12
13 public DiffCursor<K,V> getDiffCursor(long fromState, long toState);
14} \ No newline at end of file
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
deleted file mode 100644
index be768e98..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
+++ /dev/null
@@ -1,48 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3public class VersionedMapStoreConfiguration {
4
5 public VersionedMapStoreConfiguration() {
6
7 }
8 public VersionedMapStoreConfiguration(boolean immutableWhenCommiting, boolean sharedNodeCacheInStore,
9 boolean sharedNodeCacheInStoreGroups) {
10 super();
11 this.immutableWhenCommiting = immutableWhenCommiting;
12 this.sharedNodeCacheInStore = sharedNodeCacheInStore;
13 this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups;
14 }
15
16 /**
17 * If true root is replaced with immutable node when committed. Frees up memory
18 * by releasing immutable nodes, but it may decrease performance by recreating
19 * immutable nodes upon changes (some evidence).
20 */
21 private boolean immutableWhenCommiting = true;
22 public boolean isImmutableWhenCommiting() {
23 return immutableWhenCommiting;
24 }
25
26 /**
27 * If true, all subnodes are cached within a {@link VersionedMapStore}. It
28 * decreases the memory requirements. It may increase performance by discovering
29 * existing immutable copy of a node (some evidence). Additional overhead may
30 * decrease performance (no example found). The option permits the efficient
31 * implementation of version deletion.
32 */
33 private boolean sharedNodeCacheInStore = true;
34 public boolean isSharedNodeCacheInStore() {
35 return sharedNodeCacheInStore;
36 }
37
38 /**
39 * If true, all subnodes are cached within a group of
40 * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}.
41 * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is
42 * <code>false</code>, then it has currently no impact.
43 */
44 private boolean sharedNodeCacheInStoreGroups = true;
45 public boolean isSharedNodeCacheInStoreGroups() {
46 return sharedNodeCacheInStoreGroups;
47 }
48}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
deleted file mode 100644
index 83d0e8cd..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
+++ /dev/null
@@ -1,135 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.HashSet;
8import java.util.List;
9import java.util.Map;
10import java.util.Set;
11
12import org.eclipse.viatra.solver.data.map.internal.ImmutableNode;
13import org.eclipse.viatra.solver.data.map.internal.MapDiffCursor;
14import org.eclipse.viatra.solver.data.map.internal.Node;
15import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
16
17public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
18 // Configuration
19 private final boolean immutableWhenCommiting;
20
21 // Static data
22 protected final ContinousHashProvider<K> hashProvider;
23 protected final V defaultValue;
24
25 // Dynamic data
26 protected final Map<Long, ImmutableNode<K, V>> states = new HashMap<>();
27 protected final Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
28 protected long nextID = 0;
29
30 public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
31 VersionedMapStoreConfiguration config) {
32 this.immutableWhenCommiting = config.isImmutableWhenCommiting();
33 this.hashProvider = hashProvider;
34 this.defaultValue = defaultValue;
35 if (config.isSharedNodeCacheInStore()) {
36 nodeCache = new HashMap<>();
37 } else {
38 nodeCache = null;
39 }
40 }
41
42 private VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
43 Map<Node<K, V>, ImmutableNode<K, V>> nodeCache, VersionedMapStoreConfiguration config) {
44 this.immutableWhenCommiting = config.isImmutableWhenCommiting();
45 this.hashProvider = hashProvider;
46 this.defaultValue = defaultValue;
47 this.nodeCache = nodeCache;
48 }
49
50 public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue) {
51 this(hashProvider, defaultValue, new VersionedMapStoreConfiguration());
52 }
53
54 public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
55 ContinousHashProvider<K> hashProvider, V defaultValue,
56 VersionedMapStoreConfiguration config) {
57 List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
58 if (config.isSharedNodeCacheInStoreGroups()) {
59 Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
60 if (config.isSharedNodeCacheInStore()) {
61 nodeCache = new HashMap<>();
62 } else {
63 nodeCache = null;
64 }
65 for (int i = 0; i < amount; i++) {
66 result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config));
67 }
68 } else {
69 for (int i = 0; i < amount; i++) {
70 result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config));
71 }
72 }
73 return result;
74 }
75
76 public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
77 ContinousHashProvider<K> hashProvider, V defaultValue) {
78 return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration());
79 }
80
81 @Override
82 public synchronized Set<Long> getStates() {
83 return new HashSet<>(states.keySet());
84 }
85
86 @Override
87 public VersionedMap<K, V> createMap() {
88 return new VersionedMapImpl<>(this, hashProvider, defaultValue);
89 }
90
91 @Override
92 public VersionedMap<K, V> createMap(long state) {
93 ImmutableNode<K, V> data = revert(state);
94 return new VersionedMapImpl<>(this, hashProvider, defaultValue, data);
95 }
96
97
98 public synchronized ImmutableNode<K, V> revert(long state) {
99 if (states.containsKey(state)) {
100 return states.get(state);
101 } else {
102 ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
103 Collections.sort(existingKeys);
104 throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: "
105 + Arrays.toString(existingKeys.toArray()));
106 }
107 }
108
109 public synchronized long commit(Node<K, V> data, VersionedMapImpl<K, V> mapToUpdateRoot) {
110 ImmutableNode<K, V> immutable;
111 if (data != null) {
112 immutable = data.toImmutable(this.nodeCache);
113 } else {
114 immutable = null;
115 }
116
117 if (nextID == Long.MAX_VALUE)
118 throw new IllegalStateException("Map store run out of Id-s");
119 long id = nextID++;
120 this.states.put(id, immutable);
121 if (this.immutableWhenCommiting) {
122 mapToUpdateRoot.setRoot(immutable);
123 }
124 return id;
125 }
126
127 @Override
128 public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
129 VersionedMap<K, V> map1 = createMap(fromState);
130 VersionedMap<K, V> map2 = createMap(toState);
131 Cursor<K, V> cursor1 = map1.getAll();
132 Cursor<K, V> cursor2 = map2.getAll();
133 return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2);
134 }
135}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java
deleted file mode 100644
index c70fb8b8..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java
+++ /dev/null
@@ -1,18 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3enum HashClash {
4 /**
5 * Not stuck.
6 */
7 NONE,
8
9 /**
10 * Clashed, next we should return the key of cursor 1.
11 */
12 STUCK_CURSOR_1,
13
14 /**
15 * Clashed, next we should return the key of cursor 2.
16 */
17 STUCK_CURSOR_2
18}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
deleted file mode 100644
index b507763f..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
+++ /dev/null
@@ -1,378 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7
8public class ImmutableNode<K, V> extends Node<K, V> {
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: (K,V)*,NODE; NODES are stored
19 * backwards.
20 */
21 final Object[] content;
22
23 /**
24 * Hash code derived from immutable hash code
25 */
26 final int precalculatedHash;
27
28 private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) {
29 super();
30 this.dataMap = dataMap;
31 this.nodeMap = nodeMap;
32 this.content = content;
33 this.precalculatedHash = precalculatedHash;
34 }
35
36 /**
37 * Constructor that copies a mutable node to an immutable.
38 *
39 * @param node A mutable node.
40 * @param cache A cache of existing immutable nodes. It can be used to search
41 * and place reference immutable nodes. It can be null, if no cache
42 * available.
43 * @return an immutable version of the input node.
44 */
45 static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node,
46 Map<Node<K, V>, ImmutableNode<K, V>> cache) {
47 // 1. try to return from cache
48 if (cache != null) {
49 ImmutableNode<K, V> cachedResult = cache.get(node);
50 if (cachedResult != null) {
51 // 1.1 Already cached, return from cache.
52 return cachedResult;
53 }
54 }
55
56 // 2. otherwise construct a new ImmutableNode
57 int size = 0;
58 for (int i = 0; i < node.content.length; i++) {
59 if (node.content[i] != null) {
60 size++;
61 }
62 }
63
64 int datas = 0;
65 int nodes = 0;
66 int resultDataMap = 0;
67 int resultNodeMap = 0;
68 final Object[] resultContent = new Object[size];
69 int bitposition = 1;
70 for (int i = 0; i < FACTOR; i++) {
71 Object key = node.content[i * 2];
72 if (key != null) {
73 resultDataMap |= bitposition;
74 resultContent[datas * 2] = key;
75 resultContent[datas * 2 + 1] = node.content[i * 2 + 1];
76 datas++;
77 } else {
78 @SuppressWarnings("unchecked")
79 var subnode = (Node<K, V>) node.content[i * 2 + 1];
80 if (subnode != null) {
81 ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache);
82 resultNodeMap |= bitposition;
83 resultContent[size - 1 - nodes] = immutableSubnode;
84 nodes++;
85 }
86 }
87 bitposition <<= 1;
88 }
89 final int resultHash = node.hashCode();
90 var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash);
91
92 // 3. save new immutable.
93 if (cache != null) {
94 cache.put(newImmutable, newImmutable);
95 }
96 return newImmutable;
97 }
98
99 private int index(int bitmap, int bitpos) {
100 return Integer.bitCount(bitmap & (bitpos - 1));
101 }
102
103 @Override
104 public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
105 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
106 int bitposition = 1 << selectedHashFragment;
107 // If the key is stored as a data
108 if ((dataMap & bitposition) != 0) {
109 int keyIndex = 2 * index(dataMap, bitposition);
110 @SuppressWarnings("unchecked")
111 K keyCandidate = (K) content[keyIndex];
112 if (keyCandidate.equals(key)) {
113 @SuppressWarnings("unchecked")
114 V value = (V) content[keyIndex + 1];
115 return value;
116 } else {
117 return defaultValue;
118 }
119 }
120 // the key is stored as a node
121 else if ((nodeMap & bitposition) != 0) {
122 int keyIndex = content.length - 1 - index(nodeMap, bitposition);
123 @SuppressWarnings("unchecked")
124 var subNode = (ImmutableNode<K, V>) content[keyIndex];
125 int newDepth = depth + 1;
126 int newHash = newHash(hashProvider, key, hash, newDepth);
127 return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
128 }
129 // the key is not stored at all
130 else {
131 return defaultValue;
132 }
133 }
134
135 @Override
136 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider,
137 V defaultValue, int hash, int depth) {
138 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
139 int bitposition = 1 << selectedHashFragment;
140 if ((dataMap & bitposition) != 0) {
141 int keyIndex = 2 * index(dataMap, bitposition);
142 @SuppressWarnings("unchecked")
143 K keyCandidate = (K) content[keyIndex];
144 if (keyCandidate.equals(key)) {
145 if (value == defaultValue) {
146 // delete
147 MutableNode<K, V> mutable = this.toMutable();
148 return mutable.removeEntry(selectedHashFragment, oldValue);
149 } else if (value == content[keyIndex + 1]) {
150 // dont change
151 oldValue.setOldValue(value);
152 return this;
153 } else {
154 // update existing value
155 MutableNode<K, V> mutable = this.toMutable();
156 return mutable.updateValue(value, oldValue, selectedHashFragment);
157 }
158 } else {
159 if (value == defaultValue) {
160 // dont change
161 oldValue.setOldValue(defaultValue);
162 return this;
163 } else {
164 // add new key + value
165 MutableNode<K, V> mutable = this.toMutable();
166 return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
167 }
168 }
169 } else if ((nodeMap & bitposition) != 0) {
170 int keyIndex = content.length - 1 - index(nodeMap, bitposition);
171 @SuppressWarnings("unchecked")
172 var subNode = (ImmutableNode<K, V>) content[keyIndex];
173 int newDepth = depth + 1;
174 int newHash = newHash(hashProvider, key, hash, newDepth);
175 var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth);
176
177 if (subNode == newsubNode) {
178 // nothing changed
179 return this;
180 } else {
181 MutableNode<K, V> mutable = toMutable();
182 return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue));
183 }
184 } else {
185 // add new key + value
186 MutableNode<K, V> mutable = this.toMutable();
187 return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
188 }
189 }
190
191 @Override
192 public long getSize() {
193 int result = Integer.bitCount(this.dataMap);
194 for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
195 @SuppressWarnings("unchecked")
196 var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex];
197 result += subnode.getSize();
198 }
199 return result;
200 }
201
202 @Override
203 protected MutableNode<K, V> toMutable() {
204 return new MutableNode<>(this);
205 }
206
207 @Override
208 public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
209 return this;
210 }
211
212 @Override
213 protected MutableNode<K, V> isMutable() {
214 return null;
215 }
216
217 @SuppressWarnings("unchecked")
218 @Override
219 boolean moveToNext(MapCursor<K, V> cursor) {
220 // 1. try to move to data
221 int datas = Integer.bitCount(this.dataMap);
222 if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
223 int newDataIndex = cursor.dataIndex + 1;
224 if (newDataIndex < datas) {
225 cursor.dataIndex = newDataIndex;
226 cursor.key = (K) this.content[newDataIndex * 2];
227 cursor.value = (V) this.content[newDataIndex * 2 + 1];
228 return true;
229 } else {
230 cursor.dataIndex = MapCursor.INDEX_FINISH;
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<K, V> subnode = (Node<K, V>) this.content[this.content.length - 1 - newNodeIndex];
240 cursor.dataIndex = MapCursor.INDEX_START;
241 cursor.nodeIndexStack.pop();
242 cursor.nodeIndexStack.push(newNodeIndex);
243 cursor.nodeIndexStack.push(MapCursor.INDEX_START);
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<K, V> 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<K, V> subNode = (Node<K, V>) 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 void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
303 if (depth > 0) {
304 boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0;
305 if (orphaned) {
306 throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]);
307 }
308 }
309 // check the place of data
310
311 // check subnodes
312 for (int i = 0; i < Integer.bitCount(nodeMap); i++) {
313 @SuppressWarnings("unchecked")
314 var subnode = (Node<K, V>) this.content[this.content.length - 1 - i];
315 if (!(subnode instanceof ImmutableNode<?, ?>)) {
316 throw new IllegalStateException("Immutable node contains mutable subnodes!");
317 } else {
318 subnode.checkIntegrity(hashProvider, defaultValue, depth + 1);
319 }
320 }
321 }
322
323 @Override
324 public int hashCode() {
325 return this.precalculatedHash;
326 }
327
328 @Override
329 public boolean equals(Object obj) {
330 if (this == obj)
331 return true;
332 if (obj == null)
333 return false;
334 if (obj instanceof ImmutableNode<?, ?> other) {
335 return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap
336 && Arrays.deepEquals(content, other.content);
337 } else if (obj instanceof MutableNode<?, ?> mutableObj) {
338 return ImmutableNode.compareImmutableMutable(this, mutableObj);
339 } else {
340 return false;
341 }
342 }
343
344 public static boolean compareImmutableMutable(ImmutableNode<?, ?> immutable, MutableNode<?, ?> mutable) {
345 int datas = 0;
346 int nodes = 0;
347 final int immutableLength = immutable.content.length;
348 for (int i = 0; i < FACTOR; i++) {
349 Object key = mutable.content[i * 2];
350 // For each key candidate
351 if (key != null) {
352 // Check whether a new Key-Value pair can fit into the immutable container
353 if (datas * 2 + nodes + 2 <= immutableLength) {
354 if (!immutable.content[datas * 2].equals(key)
355 || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) {
356 return false;
357 }
358 } else
359 return false;
360 datas++;
361 } else {
362 var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1];
363 if (mutableSubnode != null) {
364 if (datas * 2 + nodes + 1 <= immutableLength) {
365 Object immutableSubnode = immutable.content[immutableLength - 1 - nodes];
366 if (!mutableSubnode.equals(immutableSubnode)) {
367 return false;
368 }
369 nodes++;
370 } else {
371 return false;
372 }
373 }
374 }
375 }
376 return true;
377 }
378}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
deleted file mode 100644
index cc5a3982..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
+++ /dev/null
@@ -1,131 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.ArrayDeque;
4import java.util.ConcurrentModificationException;
5import java.util.Iterator;
6import java.util.List;
7
8import org.eclipse.viatra.solver.data.map.Cursor;
9import org.eclipse.viatra.solver.data.map.VersionedMap;
10
11public class MapCursor<K,V> implements Cursor<K,V> {
12 // Constants
13 static final int INDEX_START = -1;
14 static final int INDEX_FINISH = -2;
15
16 // Tree stack
17 ArrayDeque<Node<K,V>> nodeStack;
18 ArrayDeque<Integer> nodeIndexStack;
19 int dataIndex;
20
21 // Values
22 K key;
23 V value;
24
25 // Hash code for checking concurrent modifications
26 final VersionedMap<K,V> map;
27 final int creationHash;
28
29 public MapCursor(Node<K, V> root, VersionedMap<K,V> 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(INDEX_START);
37 }
38
39 this.dataIndex = INDEX_START;
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 K getKey() {
51 return key;
52 }
53
54 public V 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 = INDEX_FINISH;
79 return move();
80 }
81 @Override
82 public boolean isDirty() {
83 return this.map.hashCode() != this.creationHash;
84 }
85 @Override
86 public List<VersionedMap<?, ?>> getDependingMaps() {
87 return List.of(this.map);
88 }
89
90 public static <K,V> boolean sameSubnode(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) {
91 Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
92 Node<K, V> 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 <K>
103 * @param <V>
104 * @param cursor1
105 * @param cursor2
106 * @return 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 <K,V> int compare(MapCursor<K,V> cursor1, MapCursor<K,V> 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/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
deleted file mode 100644
index 35d20539..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
+++ /dev/null
@@ -1,221 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.List;
4import java.util.stream.Stream;
5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7import org.eclipse.viatra.solver.data.map.Cursor;
8import org.eclipse.viatra.solver.data.map.DiffCursor;
9import org.eclipse.viatra.solver.data.map.VersionedMap;
10
11/**
12 * A cursor representing the difference between two states of a map.
13 *
14 * @author Oszkar Semerath
15 *
16 */
17public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
18 /**
19 * Default value representing missing elements.
20 */
21 private V defaultValue;
22 private MapCursor<K, V> cursor1;
23 private MapCursor<K, V> cursor2;
24 private ContinousHashProvider<? super K> hashProvider;
25
26 // Values
27 private K key;
28 private V fromValue;
29 private V toValue;
30
31 // State
32 /**
33 * Positive number if cursor 1 is behind, negative number if cursor 2 is behind,
34 * and 0 if they are at the same position.
35 */
36 private int cursorRelation;
37 private HashClash hashClash = HashClash.NONE;
38
39 public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1,
40 Cursor<K, V> cursor2) {
41 super();
42 this.hashProvider = hashProvider;
43 this.defaultValue = defaultValue;
44 this.cursor1 = (MapCursor<K, V>) cursor1;
45 this.cursor2 = (MapCursor<K, V>) cursor2;
46 }
47
48 @Override
49 public K getKey() {
50 return key;
51 }
52
53 @Override
54 public V getFromValue() {
55 return fromValue;
56 }
57
58 @Override
59 public V getToValue() {
60 return toValue;
61 }
62
63 @Override
64 public V getValue() {
65 return getToValue();
66 }
67
68 public boolean isTerminated() {
69 return cursor1.isTerminated() && cursor2.isTerminated();
70 }
71
72 @Override
73 public boolean isDirty() {
74 return this.cursor1.isDirty() || this.cursor2.isDirty();
75 }
76
77 @Override
78 public List<VersionedMap<?, ?>> getDependingMaps() {
79 return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).toList();
80 }
81
82 protected void updateState() {
83 if (!isTerminated()) {
84 this.cursorRelation = MapCursor.compare(cursor1, cursor2);
85 if (cursorRelation > 0 || cursor2.isTerminated()) {
86 this.key = cursor1.getKey();
87 this.fromValue = cursor1.getValue();
88 this.toValue = defaultValue;
89 } else if (cursorRelation < 0 || cursor1.isTerminated()) {
90 this.key = cursor2.getKey();
91 this.fromValue = defaultValue;
92 this.toValue = cursor1.getValue();
93 } else {
94 // cursor1 = cursor2
95 if (cursor1.getKey().equals(cursor2.getKey())) {
96 this.key = cursor1.getKey();
97 this.fromValue = cursor1.getValue();
98 this.toValue = defaultValue;
99 } else {
100 resolveHashClashWithFirstEntry();
101 }
102 }
103 }
104 }
105
106 protected void resolveHashClashWithFirstEntry() {
107 int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key);
108 if (compareResult < 0) {
109 this.hashClash = HashClash.STUCK_CURSOR_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 = HashClash.STUCK_CURSOR_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
125 protected boolean isInHashClash() {
126 return this.hashClash != HashClash.NONE;
127 }
128
129 protected void resolveHashClashWithSecondEntry() {
130 switch (this.hashClash) {
131 case STUCK_CURSOR_1:
132 this.hashClash = HashClash.NONE;
133 this.cursorRelation = 0;
134 this.key = cursor1.key;
135 this.fromValue = cursor1.value;
136 this.toValue = defaultValue;
137 break;
138 case STUCK_CURSOR_2:
139 this.hashClash = HashClash.NONE;
140 this.cursorRelation = 0;
141 this.key = cursor2.key;
142 this.fromValue = defaultValue;
143 this.toValue = cursor2.value;
144 break;
145 default:
146 throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
147 }
148 }
149
150 protected boolean sameValues() {
151 if (this.fromValue == null) {
152 return this.toValue == null;
153 } else {
154 return this.fromValue.equals(this.toValue);
155 }
156 }
157
158 protected boolean moveOne() {
159 if (isTerminated()) {
160 return false;
161 }
162 if (this.cursorRelation > 0 || cursor2.isTerminated()) {
163 return cursor1.move();
164 } else if (this.cursorRelation < 0 || cursor1.isTerminated()) {
165 return cursor2.move();
166 } else {
167 boolean moved1 = cursor1.move();
168 boolean moved2 = cursor2.move();
169 return moved1 && moved2;
170 }
171 }
172
173 private boolean skipNode() {
174 if (isTerminated()) {
175 throw new IllegalStateException("DiffCursor tries to skip when terminated!");
176 }
177 boolean update1 = cursor1.skipCurrentNode();
178 boolean update2 = cursor2.skipCurrentNode();
179 updateState();
180 return update1 && update2;
181 }
182
183 protected boolean moveToConsistentState() {
184 if (!isTerminated()) {
185 boolean changed;
186 boolean lastResult = true;
187 do {
188 changed = false;
189 if (MapCursor.sameSubnode(cursor1, cursor2)) {
190 lastResult = skipNode();
191 changed = true;
192 }
193 if (sameValues()) {
194 lastResult = moveOne();
195 changed = true;
196 }
197 updateState();
198 } while (changed && !isTerminated());
199 return lastResult;
200 } else {
201 return false;
202 }
203 }
204
205 public boolean move() {
206 if (!isTerminated()) {
207 if (isInHashClash()) {
208 this.resolveHashClashWithSecondEntry();
209 return true;
210 } else {
211 if (moveOne()) {
212 return moveToConsistentState();
213 } else {
214 return false;
215 }
216 }
217
218 } else
219 return false;
220 }
221}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
deleted file mode 100644
index b5fee673..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
+++ /dev/null
@@ -1,456 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7
8public class MutableNode<K, V> extends Node<K, V> {
9 int cachedHash;
10 protected Object[] content;
11
12 protected MutableNode() {
13 this.content = new Object[2 * FACTOR];
14 updateHash();
15 }
16
17 public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider,
18 V defaultValue) {
19 if (value == defaultValue) {
20 return null;
21 } else {
22 int hash = hashProvider.getHash(key, 0);
23 int fragment = hashFragment(hash, 0);
24 MutableNode<K, V> res = new MutableNode<>();
25 res.content[2 * fragment] = key;
26 res.content[2 * fragment + 1] = value;
27 res.updateHash();
28 return res;
29 }
30 }
31
32 /**
33 * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
34 *
35 * @param node
36 */
37 protected MutableNode(ImmutableNode<K, V> node) {
38 this.content = new Object[2 * FACTOR];
39 int dataUsed = 0;
40 int nodeUsed = 0;
41 for (int i = 0; i < FACTOR; i++) {
42 int bitposition = 1 << i;
43 if ((node.dataMap & bitposition) != 0) {
44 content[2 * i] = node.content[dataUsed * 2];
45 content[2 * i + 1] = node.content[dataUsed * 2 + 1];
46 dataUsed++;
47 } else if ((node.nodeMap & bitposition) != 0) {
48 content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed];
49 nodeUsed++;
50 }
51 }
52 this.cachedHash = node.hashCode();
53 }
54
55 @Override
56 public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
57 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
58 @SuppressWarnings("unchecked")
59 K keyCandidate = (K) this.content[2 * selectedHashFragment];
60 if (keyCandidate != null) {
61 if (keyCandidate.equals(key)) {
62 @SuppressWarnings("unchecked")
63 V value = (V) this.content[2 * selectedHashFragment + 1];
64 return value;
65 } else {
66 return defaultValue;
67 }
68 } else {
69 @SuppressWarnings("unchecked")
70 var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
71 if (nodeCandidate != null) {
72 int newDepth = depth + 1;
73 int newHash = newHash(hashProvider, key, hash, newDepth);
74 return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
75 } else {
76 return defaultValue;
77 }
78 }
79 }
80
81 @Override
82 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider,
83 V defaultValue, int hash, int depth) {
84 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
85 @SuppressWarnings("unchecked")
86 K keyCandidate = (K) content[2 * selectedHashFragment];
87 if (keyCandidate != null) {
88 // If has key
89 if (keyCandidate.equals(key)) {
90 // The key is equals to an existing key -> update entry
91 if (value == defaultValue) {
92 return removeEntry(selectedHashFragment, oldValue);
93 } else {
94 return updateValue(value, oldValue, selectedHashFragment);
95 }
96 } else {
97 // The key is not equivalent to an existing key on the same hash bin
98 // -> split entry if it is necessary
99 if (value == defaultValue) {
100 // Value is default -> do not need to add new node
101 oldValue.setOldValue(defaultValue);
102 return this;
103 } else {
104 // Value is not default -> Split entry data to a new node
105 oldValue.setOldValue(defaultValue);
106 return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
107 }
108 }
109 } else {
110 // If it does not have key, check for value
111 @SuppressWarnings("unchecked")
112 var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
113 if (nodeCandidate != null) {
114 // If it has value, it is a subnode -> upate that
115 var newNode = nodeCandidate.putValue(key, value, oldValue, hashProvider, defaultValue,
116 newHash(hashProvider, key, hash, depth + 1), depth + 1);
117 return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
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 oldValue.setOldValue(defaultValue);
123 return this;
124 } else {
125 return addEntry(key, value, oldValue, selectedHashFragment);
126 }
127
128 }
129 }
130 }
131
132 private Node<K, V> addEntry(K key, V value, OldValueBox<V> oldValueBox, int selectedHashFragment) {
133 content[2 * selectedHashFragment] = key;
134 @SuppressWarnings("unchecked")
135 V oldValue = (V) content[2 * selectedHashFragment + 1];
136 oldValueBox.setOldValue(oldValue);
137 content[2 * selectedHashFragment + 1] = value;
138 updateHash();
139 return this;
140 }
141
142 /**
143 * Updates an entry in a selected hash-fragment to a non-default value.
144 *
145 * @param value
146 * @param selectedHashFragment
147 * @return
148 */
149 @SuppressWarnings("unchecked")
150 Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) {
151 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
152 content[2 * selectedHashFragment + 1] = value;
153 updateHash();
154 return this;
155 }
156
157 /**
158 *
159 * @param selectedHashFragment
160 * @param newNode
161 * @return
162 */
163 Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
164 if (deletionHappened) {
165 if (newNode == null) {
166 // Check whether this node become empty
167 content[2 * selectedHashFragment + 1] = null; // i.e. the new node
168 if (hasContent()) {
169 updateHash();
170 return this;
171 } else {
172 return null;
173 }
174 } else {
175 // check whether newNode is orphan
176 MutableNode<K, V> immutableNewNode = newNode.isMutable();
177 if (immutableNewNode != null) {
178 int orphaned = immutableNewNode.isOrphaned();
179 if (orphaned >= 0) {
180 // orphan subnode data is replaced with data
181 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
182 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
183 updateHash();
184 return this;
185 }
186 }
187 }
188 }
189 // normal behaviour
190 content[2 * selectedHashFragment + 1] = newNode;
191 updateHash();
192 return this;
193
194 }
195
196 private boolean hasContent() {
197 for (Object element : this.content) {
198 if (element != null)
199 return true;
200 }
201 return false;
202 }
203
204 @Override
205 protected MutableNode<K, V> isMutable() {
206 return this;
207 }
208
209 protected int isOrphaned() {
210 int dataFound = -2;
211 for (int i = 0; i < FACTOR; i++) {
212 if (content[i * 2] != null) {
213 if (dataFound >= 0) {
214 return -1;
215 } else {
216 dataFound = i;
217 }
218 } else if (content[i * 2 + 1] != null) {
219 return -3;
220 }
221 }
222 return dataFound;
223 }
224
225 @SuppressWarnings("unchecked")
226 private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue,
227 K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
228 V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
229
230 MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
231 hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
232
233 content[2 * selectedHashFragmentOfCurrentDepth] = null;
234 content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
235 updateHash();
236 return this;
237 }
238
239 // Pass everything as parameters for performance.
240 @SuppressWarnings("squid:S107")
241 private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1,
242 int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
243 int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
244 int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
245 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
246 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
247
248 MutableNode<K, V> subNode = new MutableNode<>();
249 if (newFragment1 != newFragment2) {
250 subNode.content[newFragment1 * 2] = key1;
251 subNode.content[newFragment1 * 2 + 1] = value1;
252
253 subNode.content[newFragment2 * 2] = key2;
254 subNode.content[newFragment2 * 2 + 1] = value2;
255 } else {
256 MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2,
257 newHash2, newdepth + 1);
258 subNode.content[newFragment1 * 2 + 1] = subSubNode;
259 }
260 subNode.updateHash();
261 return subNode;
262 }
263
264 @SuppressWarnings("unchecked")
265 Node<K, V> removeEntry(int selectedHashFragment, OldValueBox<V> oldValue) {
266 content[2 * selectedHashFragment] = null;
267 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
268 content[2 * selectedHashFragment + 1] = null;
269 if (hasContent()) {
270 updateHash();
271 return this;
272 } else {
273 return null;
274 }
275 }
276
277 @SuppressWarnings("unchecked")
278 @Override
279 public long getSize() {
280 int size = 0;
281 for (int i = 0; i < FACTOR; i++) {
282 if (content[i * 2] != null) {
283 size++;
284 } else {
285 Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1];
286 if (nodeCandidate != null) {
287 size += nodeCandidate.getSize();
288 }
289 }
290 }
291 return size;
292 }
293
294 @Override
295 protected MutableNode<K, V> toMutable() {
296 return this;
297 }
298
299 @Override
300 public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
301 return ImmutableNode.constructImmutable(this, cache);
302 }
303
304 @SuppressWarnings("unchecked")
305 @Override
306 boolean moveToNext(MapCursor<K, V> cursor) {
307 // 1. try to move to data
308 if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
309 for (int index = cursor.dataIndex + 1; index < FACTOR; index++) {
310 if (this.content[index * 2] != null) {
311 // 1.1 found next data
312 cursor.dataIndex = index;
313 cursor.key = (K) this.content[index * 2];
314 cursor.value = (V) this.content[index * 2 + 1];
315 return true;
316 }
317 }
318 cursor.dataIndex = MapCursor.INDEX_FINISH;
319 }
320
321 // 2. look inside the subnodes
322 for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) {
323 if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) {
324 // 2.1 found next subnode, move down to the subnode
325 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
326
327 cursor.dataIndex = MapCursor.INDEX_START;
328 cursor.nodeIndexStack.pop();
329 cursor.nodeIndexStack.push(index);
330 cursor.nodeIndexStack.push(MapCursor.INDEX_START);
331 cursor.nodeStack.push(subnode);
332
333 return subnode.moveToNext(cursor);
334 }
335 }
336 // 3. no subnode found, move up
337 cursor.nodeStack.pop();
338 cursor.nodeIndexStack.pop();
339 if (!cursor.nodeStack.isEmpty()) {
340 Node<K, V> supernode = cursor.nodeStack.peek();
341 return supernode.moveToNext(cursor);
342 } else {
343 cursor.key = null;
344 cursor.value = null;
345 return false;
346 }
347 }
348
349 @Override
350 public void prettyPrint(StringBuilder builder, int depth, int code) {
351 for (int i = 0; i < depth; i++) {
352 builder.append("\t");
353 }
354 if (code >= 0) {
355 builder.append(code);
356 builder.append(":");
357 }
358 builder.append("Mutable(");
359 // print content
360 boolean hadContent = false;
361 for (int i = 0; i < FACTOR; i++) {
362 if (content[2 * i] != null) {
363 if (hadContent) {
364 builder.append(",");
365 }
366 builder.append(i);
367 builder.append(":[");
368 builder.append(content[2 * i].toString());
369 builder.append("]->[");
370 builder.append(content[2 * i + 1].toString());
371 builder.append("]");
372 hadContent = true;
373 }
374 }
375 builder.append(")");
376 // print subnodes
377 for (int i = 0; i < FACTOR; i++) {
378 if (content[2 * i] == null && content[2 * i + 1] != null) {
379 @SuppressWarnings("unchecked")
380 Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
381 builder.append("\n");
382 subNode.prettyPrint(builder, depth + 1, i);
383 }
384 }
385 }
386
387 @Override
388 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
389 // check for orphan nodes
390 if (depth > 0) {
391 int orphaned = isOrphaned();
392 if (orphaned >= 0) {
393 throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]);
394 }
395 }
396 // check the place of data
397 for (int i = 0; i < FACTOR; i++) {
398 if (this.content[2 * i] != null) {
399 @SuppressWarnings("unchecked")
400 K key = (K) this.content[2 * i];
401 @SuppressWarnings("unchecked")
402 V value = (V) this.content[2 * i + 1];
403
404 if (value == defaultValue) {
405 throw new IllegalStateException("Node contains default value!");
406 }
407 int hashCode = hashProvider.getHash(key, hashDepth(depth));
408 int shiftDepth = shiftDepth(depth);
409 int selectedHashFragment = hashFragment(hashCode, shiftDepth);
410 if (i != selectedHashFragment) {
411 throw new IllegalStateException("Key " + key + " with hash code " + hashCode
412 + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
413 }
414 }
415 }
416 // check subnodes
417 for (int i = 0; i < FACTOR; i++) {
418 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
419 @SuppressWarnings("unchecked")
420 var subNode = (Node<K, V>) this.content[2 * i + 1];
421 subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
422 }
423 }
424 // check the hash
425 int oldHash = this.cachedHash;
426 updateHash();
427 int newHash = this.cachedHash;
428 if (oldHash != newHash) {
429 throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
430 }
431 }
432
433 protected void updateHash() {
434 this.cachedHash = Arrays.hashCode(content);
435 }
436
437 @Override
438 public int hashCode() {
439 return this.cachedHash;
440 }
441
442 @Override
443 public boolean equals(Object obj) {
444 if (this == obj)
445 return true;
446 if (obj == null)
447 return false;
448 if (obj instanceof MutableNode<?, ?> mutableObj) {
449 return Arrays.deepEquals(this.content, mutableObj.content);
450 } else if (obj instanceof ImmutableNode<?, ?> immutableObj) {
451 return ImmutableNode.compareImmutableMutable(immutableObj, this);
452 } else {
453 return false;
454 }
455 }
456}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
deleted file mode 100644
index d40f980a..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
+++ /dev/null
@@ -1,85 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Map;
4
5import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
6
7public abstract class Node<K,V>{
8 public static final int BRANCHING_FACTOR_BITS = 5;
9 public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
10 protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
11 protected static final int FACTOR_MASK = FACTOR-1;
12 public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
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/NUMBER_OF_FACTORS;
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%NUMBER_OF_FACTORS;
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 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
39 return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK;
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 K> hashProvider, K 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%NUMBER_OF_FACTORS == 0?
55 hashProvider.getHash(key, hashDepth) :
56 hash;
57 }
58
59
60 public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
61 public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
62 public abstract long getSize();
63
64 abstract MutableNode<K, V> toMutable();
65 public abstract ImmutableNode<K, V> toImmutable(
66 Map<Node<K, V>,ImmutableNode<K, V>> cache);
67 protected abstract MutableNode<K, V> isMutable();
68 /**
69 * Moves a {@link MapCursor} to its next position.
70 * @param cursor the cursor
71 * @return Whether there was a next value to move on.
72 */
73 abstract boolean moveToNext(MapCursor<K,V> cursor);
74
75 ///////// FOR printing
76 public abstract void prettyPrint(StringBuilder builder, int depth, int code);
77 @Override
78 public String toString() {
79 StringBuilder stringBuilder = new StringBuilder();
80 prettyPrint(stringBuilder, 0, -1);
81 return stringBuilder.toString();
82 }
83 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
84
85}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java
deleted file mode 100644
index 23502857..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java
+++ /dev/null
@@ -1,19 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3public class OldValueBox<V>{
4 V oldValue;
5 boolean isSet = false;
6
7 public V getOldValue() {
8 if(!isSet) throw new IllegalStateException();
9 isSet = false;
10 return oldValue;
11 }
12
13 public void setOldValue(V ouldValue) {
14 if(isSet) throw new IllegalStateException();
15 this.oldValue = ouldValue;
16 isSet = true;
17 }
18
19}
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
deleted file mode 100644
index de41e602..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
+++ /dev/null
@@ -1,171 +0,0 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Iterator;
4import java.util.LinkedList;
5import java.util.List;
6
7import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
8import org.eclipse.viatra.solver.data.map.Cursor;
9import org.eclipse.viatra.solver.data.map.DiffCursor;
10import org.eclipse.viatra.solver.data.map.VersionedMap;
11import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
12
13/**
14 * Not threadSafe in itself
15 * @author Oszkar Semerath
16 *
17 * @param <K>
18 * @param <V>
19 */
20public class VersionedMapImpl<K,V> implements VersionedMap<K,V>{
21 protected final VersionedMapStoreImpl<K,V> store;
22
23 protected final ContinousHashProvider<K> hashProvider;
24 protected final V defaultValue;
25 protected Node<K,V> root;
26
27 private OldValueBox<V> oldValueBox = new OldValueBox<>();
28
29 public VersionedMapImpl(
30 VersionedMapStoreImpl<K,V> store,
31 ContinousHashProvider<K> hashProvider,
32 V defaultValue)
33 {
34 this.store = store;
35 this.hashProvider = hashProvider;
36 this.defaultValue = defaultValue;
37 this.root = null;
38 }
39 public VersionedMapImpl(
40 VersionedMapStoreImpl<K,V> store,
41 ContinousHashProvider<K> hashProvider,
42 V defaultValue, Node<K,V> data)
43 {
44 this.store = store;
45 this.hashProvider = hashProvider;
46 this.defaultValue = defaultValue;
47 this.root = data;
48 }
49
50 public V getDefaultValue() {
51 return defaultValue;
52 }
53 public ContinousHashProvider<K> getHashProvider() {
54 return hashProvider;
55 }
56 @Override
57 public V put(K key, V value) {
58 if(root!=null) {
59 root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
60 return oldValueBox.getOldValue();
61 } else {
62 root = MutableNode.initialize(key, value, hashProvider, defaultValue);
63 return defaultValue;
64 }
65 }
66
67 @Override
68 public void putAll(Cursor<K, V> cursor) {
69 if(cursor.getDependingMaps().contains(this)) {
70 List<K> keys = new LinkedList<>();
71 List<V> values = new LinkedList<>();
72 while(cursor.move()) {
73 keys.add(cursor.getKey());
74 values.add(cursor.getValue());
75 }
76 Iterator<K> keyIterator = keys.iterator();
77 Iterator<V> valueIterator = values.iterator();
78 while(keyIterator.hasNext()) {
79 this.put(keyIterator.next(), valueIterator.next());
80 }
81 } else {
82 while(cursor.move()) {
83 this.put(cursor.getKey(), cursor.getValue());
84 }
85 }
86 }
87
88 @Override
89 public V get(K key) {
90 if(root!=null) {
91 return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
92 } else {
93 return defaultValue;
94 }
95 }
96 @Override
97 public long getSize() {
98 if(root == null) {
99 return 0;
100 } else {
101 return root.getSize();
102 }
103 }
104
105 @Override
106 public Cursor<K, V> getAll() {
107 return new MapCursor<>(this.root,this);
108 }
109 @Override
110 public DiffCursor<K, V> getDiffCursor(long toVersion) {
111 Cursor<K, V> fromCursor = this.getAll();
112 VersionedMap<K, V> toMap = this.store.createMap(toVersion);
113 Cursor<K, V> toCursor = toMap.getAll();
114 return new MapDiffCursor<>(this.hashProvider,this.defaultValue, fromCursor, toCursor);
115
116 }
117
118
119 @Override
120 public long commit() {
121 return this.store.commit(root,this);
122 }
123 public void setRoot(Node<K, V> root) {
124 this.root = root;
125 }
126
127 @Override
128 public void restore(long state) {
129 root = this.store.revert(state);
130 }
131
132 @Override
133 public int hashCode() {
134 final int prime = 31;
135 int result = 1;
136 result = prime * result + ((root == null) ? 0 : root.hashCode());
137 return result;
138 }
139
140 @Override
141 public boolean equals(Object obj) {
142 if (this == obj)
143 return true;
144 if (obj == null)
145 return false;
146 if (getClass() != obj.getClass())
147 return false;
148 VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj;
149 if (root == null) {
150 if (other.root != null)
151 return false;
152 } else if (!root.equals(other.root))
153 return false;
154 return true;
155 }
156 public void prettyPrint() {
157 StringBuilder s = new StringBuilder();
158 if(this.root != null) {
159 this.root.prettyPrint(s, 0, -1);
160 System.out.println(s.toString());
161 } else {
162 System.out.println("empty tree");
163 }
164 }
165 public void checkIntegrity() {
166 if(this.root != null) {
167 this.root.checkIntegrity(hashProvider, defaultValue, 0);
168 }
169 }
170
171}
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-20 00:30:45 +0000