From db03801ae5eaa67f8c150413f483905184f5bdaa Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 22 Sep 2022 22:40:33 +0200 Subject: feat: data structure for assertion merging --- .../semantics/model/tests/DecisionTreeTests.java | 187 +++++++++++++++++++++ 1 file changed, 187 insertions(+) create mode 100644 subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java (limited to 'subprojects/language-semantics/src/test') diff --git a/subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java b/subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java new file mode 100644 index 00000000..8fe866af --- /dev/null +++ b/subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java @@ -0,0 +1,187 @@ +package tools.refinery.language.semantics.model.tests; + +import org.junit.jupiter.api.Test; +import tools.refinery.language.semantics.model.internal.DecisionTree; +import tools.refinery.store.model.Tuple; +import tools.refinery.store.model.representation.TruthValue; + +import java.util.LinkedHashMap; +import java.util.Map; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.*; + +class DecisionTreeTests { + @Test + void initialValueTest() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.UNKNOWN)); + } + + @Test + void mergeValueTest() { + var sut = new DecisionTree(3, TruthValue.FALSE); + sut.mergeValue(Tuple.of(3, 4, 5), TruthValue.TRUE); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.FALSE)); + } + + @Test + void mergeUnknownValueTest() { + var sut = new DecisionTree(3, TruthValue.FALSE); + sut.mergeValue(Tuple.of(3, 4, 5), TruthValue.UNKNOWN); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.FALSE)); + } + + @Test + void mergeWildcardTest() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); + sut.mergeValue(Tuple.of(-1, 4, 5), TruthValue.FALSE); + assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.TRUE)); + assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.UNKNOWN)); + } + + @Test + void mergeWildcardTest2() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + sut.mergeValue(Tuple.of(-1, 4, -1), TruthValue.FALSE); + sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); + assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.TRUE)); + assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 5, 6)), is(TruthValue.UNKNOWN)); + } + + @Test + void mergeWildcardTest3() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + sut.mergeValue(Tuple.of(-1, 4, -1), TruthValue.FALSE); + sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); + sut.mergeValue(Tuple.of(-1, -1, -1), TruthValue.ERROR); + assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.ERROR)); + assertThat(sut.get(Tuple.of(3, 5, 6)), is(TruthValue.ERROR)); + } + + @Test + void mergeOverUnsetTest() { + var sut = new DecisionTree(3, null); + sut.mergeValue(Tuple.of(-1, 4, 5), TruthValue.UNKNOWN); + sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.FALSE); + assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.UNKNOWN)); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 4, 6)), is(nullValue())); + } + + @Test + void emptyIterationTest() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + var map = iterateAll(sut, TruthValue.UNKNOWN, 2); + assertThat(map.keySet(), hasSize(0)); + } + + @Test + void completeIterationTest() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + var map = iterateAll(sut, TruthValue.FALSE, 2); + assertThat(map.keySet(), hasSize(8)); + assertThat(map, hasEntry(Tuple.of(0, 0, 0), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(0, 0, 1), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(0, 1, 0), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(0, 1, 1), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(1, 0, 0), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(1, 0, 1), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(1, 1, 0), TruthValue.UNKNOWN)); + assertThat(map, hasEntry(Tuple.of(1, 1, 1), TruthValue.UNKNOWN)); + } + + @Test + void mergedIterationTest() { + var sut = new DecisionTree(2, TruthValue.UNKNOWN); + sut.mergeValue(Tuple.of(1, -1), TruthValue.TRUE); + sut.mergeValue(Tuple.of(-1, 2), TruthValue.FALSE); + var map = iterateAll(sut, TruthValue.UNKNOWN, 3); + assertThat(map.keySet(), hasSize(5)); + assertThat(map, hasEntry(Tuple.of(0, 2), TruthValue.FALSE)); + assertThat(map, hasEntry(Tuple.of(1, 0), TruthValue.TRUE)); + assertThat(map, hasEntry(Tuple.of(1, 1), TruthValue.TRUE)); + assertThat(map, hasEntry(Tuple.of(1, 2), TruthValue.ERROR)); + assertThat(map, hasEntry(Tuple.of(2, 2), TruthValue.FALSE)); + } + + @Test + void sparseIterationTest() { + var sut = new DecisionTree(2, null); + sut.mergeValue(Tuple.of(0, 0), TruthValue.TRUE); + sut.mergeValue(Tuple.of(1, 1), TruthValue.FALSE); + var map = iterateAll(sut, null, 10); + assertThat(map.keySet(), hasSize(2)); + assertThat(map, hasEntry(Tuple.of(0, 0), TruthValue.TRUE)); + assertThat(map, hasEntry(Tuple.of(1, 1), TruthValue.FALSE)); + } + + @Test + void overwriteNothingTest() { + var sut = new DecisionTree(2, TruthValue.UNKNOWN); + var values = new DecisionTree(2, null); + sut.overwriteValues(values); + assertThat(sut.get(Tuple.of(0, 0)), is(TruthValue.UNKNOWN)); + } + + @Test + void overwriteEverythingTest() { + var sut = new DecisionTree(2, TruthValue.FALSE); + sut.mergeValue(Tuple.of(0, 0), TruthValue.ERROR); + var values = new DecisionTree(2, TruthValue.TRUE); + sut.overwriteValues(values); + assertThat(sut.get(Tuple.of(0, 0)), is(TruthValue.TRUE)); + assertThat(sut.get(Tuple.of(0, 1)), is(TruthValue.TRUE)); + } + + @Test + void overwriteWildcardTest() { + var sut = new DecisionTree(3, TruthValue.UNKNOWN); + sut.mergeValue(Tuple.of(1, 1, 1), TruthValue.FALSE); + sut.mergeValue(Tuple.of(-1, 4, 5), TruthValue.FALSE); + sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); + var values = new DecisionTree(3, null); + values.mergeValue(Tuple.of(2, 2, 2), TruthValue.TRUE); + values.mergeValue(Tuple.of(-1, 4, 5), TruthValue.UNKNOWN); + values.mergeValue(Tuple.of(3, -1, 5), TruthValue.FALSE); + sut.overwriteValues(values); + assertThat(sut.get(Tuple.of(1, 1, 1)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(2, 2, 2)), is(TruthValue.TRUE)); + assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.UNKNOWN)); + assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.FALSE)); + assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.UNKNOWN)); + } + + @Test + void removeIntermediateChildTest() { + var sut = new DecisionTree(3, TruthValue.TRUE); + var values = new DecisionTree(3, null); + values.mergeValue(Tuple.of(1, 1, 1), TruthValue.UNKNOWN); + sut.overwriteValues(values); + sut.mergeValue(Tuple.of(1, 1, 1), TruthValue.TRUE); + assertThat(sut.get(Tuple.of(1, 1, 1)), is(TruthValue.TRUE)); + } + + private Map iterateAll(DecisionTree sut, TruthValue defaultValue, int nodeCount) { + var cursor = sut.getCursor(defaultValue, nodeCount); + var map = new LinkedHashMap(); + while (cursor.move()) { + map.put(cursor.getKey(), cursor.getValue()); + } + assertThat(cursor.isDirty(), is(false)); + assertThat(cursor.isTerminated(), is(true)); + return map; + } +} -- cgit v1.2.3-70-g09d2