From 7218308c9be553c3e0d2af0dabde853d0dab27cd Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 29 Sep 2022 17:54:03 +0200 Subject: feat: data structure for default assertions --- .../semantics/model/internal/DecisionTree.java | 26 +++++++++-- .../semantics/model/internal/DecisionTreeNode.java | 18 ++++++++ .../model/internal/DecisionTreeValue.java | 8 +++- .../semantics/model/internal/IntermediateNode.java | 44 ++++++++++++++----- .../semantics/model/internal/TerminalNode.java | 50 +++++++++++++++------- 5 files changed, 116 insertions(+), 30 deletions(-) (limited to 'subprojects/language-semantics/src/main') diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java index d743ee2b..3893f396 100644 --- a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java @@ -20,21 +20,41 @@ public class DecisionTree { root = node; } + public DecisionTree(int levels) { + this(levels, null); + } + public TruthValue get(Tuple tuple) { return root.getValue(levels - 1, tuple).getTruthValue(); } public void mergeValue(Tuple tuple, TruthValue truthValue) { - if (truthValue == null) { - return; + if (truthValue != null) { + root.mergeValue(levels - 1, tuple, truthValue); + } + } + + public void setIfMissing(Tuple tuple, TruthValue truthValue) { + if (truthValue != null) { + root.setIfMissing(levels - 1, tuple, truthValue); + } + } + + public void setAllMissing(TruthValue truthValue) { + if (truthValue != null) { + root.setAllMissing(truthValue); } - root.mergeValue(levels - 1, tuple, truthValue); } public void overwriteValues(DecisionTree values) { root.overwriteValues(values.root); } + public TruthValue getReducedValue() { + var reducedValue = root.getReducedValue(); + return reducedValue == null ? null : reducedValue.getTruthValue(); + } + public Cursor getCursor(TruthValue defaultValue, int nodeCount) { return new DecisionTreeCursor(levels, defaultValue, nodeCount, root); } diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java index 7f38fc79..8ca54969 100644 --- a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java @@ -33,6 +33,24 @@ abstract class DecisionTreeNode { return copy; } + public void setIfMissing(int level, Tuple tuple, TruthValue value) { + var key = tuple.get(level); + if (key < 0) { + throw new IllegalArgumentException("Not allowed set a missing wildcard"); + } + doSetIfMissing(key, level - 1, tuple, value); + } + + protected abstract void doSetIfMissing(int key, int nextLevel, Tuple tuple, TruthValue value); + + public DecisionTreeNode withValueSetIfMissing(int level, Tuple tuple, TruthValue value) { + var copy = deepCopy(); + copy.setIfMissing(level, tuple, value); + return copy; + } + + public abstract void setAllMissing(TruthValue value); + public abstract void overwriteValues(DecisionTreeNode values); public DecisionTreeNode withOverwrittenValues(DecisionTreeNode values) { diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java index 1bf3c8b8..993987f5 100644 --- a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java @@ -19,14 +19,18 @@ public enum DecisionTreeValue { return truthValue; } - public DecisionTreeValue merge(TruthValue other) { - return truthValue == null ? fromTruthValue(other) : fromTruthValue(truthValue.merge(other)); + public TruthValue merge(TruthValue other) { + return truthValue == null ? other : truthValue.merge(other); } public DecisionTreeValue overwrite(DecisionTreeValue other) { return other == UNSET ? this : other; } + public TruthValue getTruthValueOrElse(TruthValue other) { + return this == UNSET ? other : truthValue; + } + public static DecisionTreeValue fromTruthValue(TruthValue truthValue) { if (truthValue == null) { return DecisionTreeValue.UNSET; diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java index 7165197c..a7486ecb 100644 --- a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java @@ -62,19 +62,43 @@ final class IntermediateNode extends DecisionTreeNode { } @Override - public void overwriteValues(DecisionTreeNode values) { - if (values instanceof IntermediateNode intermediateValues) { - otherwise.overwriteValues(intermediateValues.otherwise); - for (var pair : children.keyValuesView()) { - pair.getTwo().overwriteValues(intermediateValues.getChild(pair.getOne())); - } - for (var pair : intermediateValues.children.keyValuesView()) { - children.getIfAbsentPut(pair.getOne(), () -> otherwise.withOverwrittenValues(pair.getTwo())); + protected void doSetIfMissing(int key, int nextLevel, Tuple tuple, TruthValue value) { + var child = children.get(key); + if (child == null) { + var otherwiseReducedValue = getOtherwiseReducedValue(); + if (otherwiseReducedValue != null && otherwiseReducedValue != DecisionTreeValue.UNSET) { + // Value already set. + return; } - reduceChildren(); - } else { + var newChild = otherwise.withValueSetIfMissing(nextLevel, tuple, value); + children.put(key, newChild); + return; + } + child.setIfMissing(nextLevel, tuple, value); + } + + @Override + public void setAllMissing(TruthValue value) { + otherwise.setAllMissing(value); + for (var child : children) { + child.setAllMissing(value); + } + reduceChildren(); + } + + @Override + public void overwriteValues(DecisionTreeNode values) { + if (!(values instanceof IntermediateNode intermediateValues)) { throw new IllegalArgumentException("Level mismatch"); } + otherwise.overwriteValues(intermediateValues.otherwise); + for (var pair : children.keyValuesView()) { + pair.getTwo().overwriteValues(intermediateValues.getChild(pair.getOne())); + } + for (var pair : intermediateValues.children.keyValuesView()) { + children.getIfAbsentPut(pair.getOne(), () -> otherwise.withOverwrittenValues(pair.getTwo())); + } + reduceChildren(); } private void reduceChildren() { diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java index f3adea61..c0197e89 100644 --- a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java @@ -8,18 +8,18 @@ import tools.refinery.store.tuple.Tuple; import tools.refinery.store.model.representation.TruthValue; class TerminalNode extends DecisionTreeNode { - private MutableIntObjectMap children; + private MutableIntObjectMap children; private DecisionTreeValue otherwise; - TerminalNode(MutableIntObjectMap children, DecisionTreeValue otherwise) { + TerminalNode(MutableIntObjectMap children, DecisionTreeValue otherwise) { this.children = children; this.otherwise = otherwise; } private DecisionTreeValue getChild(int index) { var child = children.get(index); - return child == null ? otherwise : child; + return child == null ? otherwise : DecisionTreeValue.fromTruthValue(child); } @Override @@ -41,7 +41,7 @@ class TerminalNode extends DecisionTreeNode { @Override protected void mergeAllValues(int nextLevel, Tuple tuple, TruthValue value) { - otherwise = otherwise.merge(value); + otherwise = DecisionTreeValue.fromTruthValue(otherwise.merge(value)); children = IntObjectMaps.mutable.from(children.keyValuesView(), IntObjectPair::getOne, pair -> pair.getTwo().merge(value)); reduceChildren(); @@ -50,7 +50,7 @@ class TerminalNode extends DecisionTreeNode { @Override protected void mergeSingleValue(int key, int nextLevel, Tuple tuple, TruthValue value) { var newChild = getChild(key).merge(value); - if (newChild == otherwise) { + if (otherwise.getTruthValue() == newChild) { children.remove(key); } else { children.put(key, newChild); @@ -58,25 +58,45 @@ class TerminalNode extends DecisionTreeNode { } @Override - public void overwriteValues(DecisionTreeNode values) { - if (values instanceof TerminalNode terminalValues) { - otherwise = otherwise.overwrite(terminalValues.otherwise); - children = IntObjectMaps.mutable.from(children.keyValuesView(), IntObjectPair::getOne, - pair -> pair.getTwo().overwrite(terminalValues.getChild(pair.getOne()))); - for (var pair : terminalValues.children.keyValuesView()) { - children.getIfAbsentPut(pair.getOne(), otherwise.overwrite(pair.getTwo())); - } + public void setIfMissing(int level, Tuple tuple, TruthValue value) { + assertLevel(level); + super.setIfMissing(level, tuple, value); + } + + @Override + protected void doSetIfMissing(int key, int nextLevel, Tuple tuple, TruthValue value) { + if (otherwise == DecisionTreeValue.UNSET) { + children.getIfAbsentPut(key, value); + } + } + + @Override + public void setAllMissing(TruthValue value) { + if (otherwise == DecisionTreeValue.UNSET) { + otherwise = DecisionTreeValue.fromTruthValue(value); reduceChildren(); - } else { + } + } + + @Override + public void overwriteValues(DecisionTreeNode values) { + if (!(values instanceof TerminalNode terminalValues)) { throw new IllegalArgumentException("Level mismatch"); } + otherwise = otherwise.overwrite(terminalValues.otherwise); + children = IntObjectMaps.mutable.from(children.keyValuesView(), IntObjectPair::getOne, + pair -> terminalValues.getChild(pair.getOne()).getTruthValueOrElse(pair.getTwo())); + for (var pair : terminalValues.children.keyValuesView()) { + children.getIfAbsentPut(pair.getOne(), pair.getTwo()); + } + reduceChildren(); } private void reduceChildren() { var iterator = children.iterator(); while (iterator.hasNext()) { var child = iterator.next(); - if (child == otherwise) { + if (otherwise.getTruthValue() == child) { iterator.remove(); } } -- cgit v1.2.3-70-g09d2