aboutsummaryrefslogtreecommitdiffstats
path: root/store/src/test/java/org/eclipse/viatra/solver/data/model
diff options
context:
space:
mode:
Diffstat (limited to 'store/src/test/java/org/eclipse/viatra/solver/data/model')
-rw-r--r--store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java160
-rw-r--r--store/src/test/java/org/eclipse/viatra/solver/data/model/tests/ModelTest.java147
2 files changed, 307 insertions, 0 deletions
diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java
new file mode 100644
index 00000000..c4d98a43
--- /dev/null
+++ b/store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java
@@ -0,0 +1,160 @@
1package org.eclipse.viatra.solver.data.model.hashTests;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import java.util.ArrayList;
6import java.util.LinkedList;
7import java.util.List;
8import java.util.Random;
9
10import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
11import org.eclipse.viatra.solver.data.model.Tuple;
12import org.eclipse.viatra.solver.data.model.TupleHashProvider;
13import org.eclipse.viatra.solver.data.model.TupleHashProviderBitMagic;
14import org.junit.jupiter.api.Test;
15
16class HashEfficiencyTest {
17
18 private static List<Tuple> permutations(int range, int arity) {
19 if(arity == 1) {
20 List<Tuple> result = new ArrayList<>(range);
21 for(int i=0; i<range; i++) {
22 result.add(Tuple.of(i));
23 }
24 return result;
25 } else if(arity > 1) {
26 List<Tuple> smallers = permutations(range, arity-1);
27 List<Tuple> result = new ArrayList<>(range*smallers.size());
28 for(Tuple smaller : smallers) {
29 for(int i=0; i<range; i++) {
30 int[] larger = new int[arity];
31 for(int x = 0; x<smaller.getSize(); x++) {
32 larger[x] = smaller.get(x);
33 }
34 larger[arity-1] = i;
35 result.add(Tuple.of(larger));
36 }
37 }
38 return result;
39 } else throw new IllegalArgumentException();
40 }
41
42 private static int amountToRange(int arity, int n) {
43 int range = 1;
44 while(Math.pow(range,arity)<n+0.1) {
45 range++;
46 }
47 return 1024;
48 }
49
50 public static List<Tuple> nPermutations(int arity, int n) {
51 int range = amountToRange(arity, n);
52 List<Tuple> permutations = permutations(range, arity);
53 return permutations.subList(0, n);
54 }
55
56 public static List<Tuple> nRandoms(int arity, int n, int seed) {
57 int range = amountToRange(arity, n);
58 List<Tuple> permutations = new ArrayList<>(n);
59 Random r = new Random(seed);
60 for(int i = 0; i<n; i++) {
61 int[] tuple = new int[arity];
62 for(int j=0; j<arity; j++) {
63 tuple[j] = r.nextInt(range);
64 }
65 permutations.add(Tuple.of(tuple));
66 }
67 return permutations;
68 }
69
70 @Test
71 void permutationTest() {
72 List<Tuple> p = permutations(10, 2);
73 assertEquals(p.size(),10*10);
74 }
75// private void printTuples(List<Tuple> p) {
76// for(Tuple element : p) {
77// System.out.println(element);
78// }
79// }
80 @Test
81 void nPermutationTest() {
82 final int amount = 500;
83 List<Tuple> p = nPermutations(2, amount);
84 assertEquals(amount,p.size());
85 }
86 @Test
87 void nRandomTest() {
88 final int amount = 500;
89 List<Tuple> p = nRandoms(2, amount, 1);;
90 assertEquals(amount,p.size());
91 }
92 private static double calculateHashClashes(List<Tuple> tuples, ContinousHashProvider<Tuple> chp) {
93 int sumClashes = 0;
94
95 for(int i = 0; i<tuples.size(); i++) {
96 int height = 0;
97 for(int j=0; j<tuples.size(); j++) {
98 int clashes = calculateHashClash(chp, tuples.get(i), tuples.get(j));
99 height = Math.max(height, clashes);
100 }
101 sumClashes += height;
102 }
103 return (sumClashes+0.0) / tuples.size();
104 }
105 private static int calculateHashClash(ContinousHashProvider<Tuple> chp, Tuple a, Tuple b) {
106 if(a.equals(b)) return 0;
107 final int bits = 5;
108 final int segments = Integer.SIZE/bits;
109 final int mask = (1<<bits)-1;
110 for(int i = 0;;i++) {
111 int index = i/segments;
112 int depth = i%segments;
113 int aHash = (chp.getHash(a, index)>>(depth*5))&mask;
114 int bHash = (chp.getHash(b, index)>>(depth*5))&mask;
115 if(aHash != bHash) {
116 return i+1;
117 }
118 if(i>400) {
119 throw new IllegalStateException(a+" vs "+b);
120 }
121 }
122 }
123 private static double caclulateOptimalHashClash(int size) {
124 return (Math.log(size)/Math.log(32));
125 }
126 public static void main(String[] args) {
127 List<String> hashNames = new LinkedList<>();
128 List<ContinousHashProvider<Tuple>> hashes = new LinkedList<>();
129 hashNames.add("PrimeGroup");
130 hashes.add(new TupleHashProvider());
131 hashNames.add("BitMagic");
132 hashes.add(new TupleHashProviderBitMagic());
133
134 int[] arities = new int[] {2,3,4,5};
135 int[] sizes = new int[] {32*32,32*32*8};
136
137 System.out.println("Size,Arity,DataSource,Hash,Chashes,Optimal,Badness");
138 for(int size : sizes) {
139 double optimalClashes = caclulateOptimalHashClash(size);
140 for(int arity : arities) {
141 List<String> dataSourceNames = new LinkedList<>();
142 List<List<Tuple>> dataSources = new LinkedList<>();
143
144// dataSourceNames.add("Permutation");
145// dataSources.add(nPermutations(arity, size));
146 dataSourceNames.add("Random");
147 dataSources.add(nRandoms(arity, size, 0));
148
149 for(int dataSourceIndex = 0; dataSourceIndex<dataSourceNames.size(); dataSourceIndex++) {
150 for(int hashIndex = 0; hashIndex<hashNames.size(); hashIndex++) {
151 double clashes = calculateHashClashes(dataSources.get(dataSourceIndex),hashes.get(hashIndex));
152 System.out.println(
153 size+","+arity+","+dataSourceNames.get(dataSourceIndex)+","+hashNames.get(hashIndex)+","+
154 clashes+","+optimalClashes+","+(clashes+0.0)/optimalClashes);
155 }
156 }
157 }
158 }
159 }
160}
diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/model/tests/ModelTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/model/tests/ModelTest.java
new file mode 100644
index 00000000..c9bf3da9
--- /dev/null
+++ b/store/src/test/java/org/eclipse/viatra/solver/data/model/tests/ModelTest.java
@@ -0,0 +1,147 @@
1package org.eclipse.viatra.solver.data.model.tests;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static org.junit.jupiter.api.Assertions.assertFalse;
5import static org.junit.jupiter.api.Assertions.assertTrue;
6
7import java.util.Set;
8
9import org.eclipse.viatra.solver.data.model.Model;
10import org.eclipse.viatra.solver.data.model.ModelStore;
11import org.eclipse.viatra.solver.data.model.ModelStoreImpl;
12import org.eclipse.viatra.solver.data.model.Tuple;
13import org.eclipse.viatra.solver.data.model.representation.Relation;
14import org.junit.jupiter.api.Assertions;
15import org.junit.jupiter.api.Test;
16
17class ModelTest {
18
19 @Test
20 void modelConstructionTest() {
21 Relation<Boolean> person = new Relation<>("Person", 1, false);
22 Relation<Boolean> friend = new Relation<>("friend", 2, false);
23
24 ModelStore store = new ModelStoreImpl(Set.of(person, friend));
25 Model model = store.createModel();
26
27 assertTrue(store.getDataRepresentations().contains(person));
28 assertTrue(store.getDataRepresentations().contains(friend));
29 assertTrue(model.getDataRepresentations().contains(person));
30 assertTrue(model.getDataRepresentations().contains(friend));
31
32 Relation<Integer> other = new Relation<Integer>("other", 2, null);
33 assertFalse(model.getDataRepresentations().contains(other));
34 }
35
36 @Test
37 void modelBuildingTest() {
38 Relation<Boolean> person = new Relation<>("Person", 1, false);
39 Relation<Integer> age = new Relation<Integer>("age", 1, null);
40 Relation<Boolean> friend = new Relation<>("friend", 2, false);
41
42 ModelStore store = new ModelStoreImpl(Set.of(person, age, friend));
43 Model model = store.createModel();
44
45 model.put(person, Tuple.of(0), true);
46 model.put(person, Tuple.of(1), true);
47 model.put(age, Tuple.of(0), 3);
48 model.put(age, Tuple.of(1), 1);
49 model.put(friend, Tuple.of(0, 1), true);
50 model.put(friend, Tuple.of(1, 0), true);
51
52 assertTrue(model.get(person, Tuple.of(0)));
53 assertTrue(model.get(person, Tuple.of(1)));
54 assertFalse(model.get(person, Tuple.of(2)));
55
56 assertEquals(3, model.get(age, Tuple.of(0)));
57 assertEquals(1, model.get(age, Tuple.of(1)));
58 assertEquals(null, model.get(age, Tuple.of(2)));
59
60 assertTrue(model.get(friend, Tuple.of(0, 1)));
61 assertFalse(model.get(friend, Tuple.of(0, 5)));
62 }
63
64 @Test
65 void modelBuildingArityFailTest() {
66 Relation<Boolean> person = new Relation<>("Person", 1, false);
67 ModelStore store = new ModelStoreImpl(Set.of(person));
68 Model model = store.createModel();
69
70 final Tuple tuple3 = Tuple.of(1, 1, 1);
71 Assertions.assertThrows(IllegalArgumentException.class, () -> model.put(person, tuple3, true));
72 Assertions.assertThrows(IllegalArgumentException.class, () -> model.get(person, tuple3));
73 }
74
75 @Test
76 void modelBuildingNullFailTest() {
77 Relation<Integer> age = new Relation<Integer>("age", 1, null);
78 ModelStore store = new ModelStoreImpl(Set.of(age));
79 Model model = store.createModel();
80
81 model.put(age, Tuple.of(1), null); // valid
82 Assertions.assertThrows(IllegalArgumentException.class, () -> model.put(age, null, 1));
83 Assertions.assertThrows(IllegalArgumentException.class, () -> model.get(age, null));
84
85 }
86
87 @Test
88 void modelUpdateTest() {
89 Relation<Boolean> person = new Relation<>("Person", 1, false);
90 Relation<Integer> age = new Relation<Integer>("age", 1, null);
91 Relation<Boolean> friend = new Relation<>("friend", 2, false);
92
93 ModelStore store = new ModelStoreImpl(Set.of(person, age, friend));
94 Model model = store.createModel();
95
96 model.put(person, Tuple.of(0), true);
97 model.put(person, Tuple.of(1), true);
98 model.put(age, Tuple.of(0), 3);
99 model.put(age, Tuple.of(1), 1);
100 model.put(friend, Tuple.of(0, 1), true);
101 model.put(friend, Tuple.of(1, 0), true);
102
103 assertEquals(3, model.get(age, Tuple.of(0)));
104 assertTrue(model.get(friend, Tuple.of(0, 1)));
105
106 model.put(age, Tuple.of(0), 4);
107 model.put(friend, Tuple.of(0, 1), false);
108
109 assertEquals(4, model.get(age, Tuple.of(0)));
110 assertFalse(model.get(friend, Tuple.of(0, 1)));
111 }
112
113 @Test
114 void restoreTest() {
115 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
116 Relation<Boolean> friend = new Relation<Boolean>("friend", 2, false);
117
118 ModelStore store = new ModelStoreImpl(Set.of(person, friend));
119 Model model = store.createModel();
120
121 model.put(person, Tuple.of(0), true);
122 model.put(person, Tuple.of(1), true);
123 model.put(friend, Tuple.of(0, 1), true);
124 model.put(friend, Tuple.of(1, 0), true);
125 long state1 = model.commit();
126
127 assertFalse(model.get(person, Tuple.of(2)));
128 assertFalse(model.get(friend, Tuple.of(0, 2)));
129
130 model.put(person, Tuple.of(2), true);
131 model.put(friend, Tuple.of(0, 2), true);
132 long state2 = model.commit();
133
134 assertTrue(model.get(person, Tuple.of(2)));
135 assertTrue(model.get(friend, Tuple.of(0, 2)));
136
137 model.restore(state1);
138
139 assertFalse(model.get(person, Tuple.of(2)));
140 assertFalse(model.get(friend, Tuple.of(0, 2)));
141
142 model.restore(state2);
143
144 assertTrue(model.get(person, Tuple.of(2)));
145 assertTrue(model.get(friend, Tuple.of(0, 2)));
146 }
147}
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-20 00:36:18 +0000