1 files changed, 84 insertions, 0 deletions

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
new file mode 100644
index 00000000..53954d62
--- /dev/null
+++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java
@@ -0,0 +1,84 @@
+package tools.refinery.language.semantics.model.internal;
+
+import org.eclipse.collections.api.LazyIntIterable;
+import tools.refinery.store.model.Tuple;
+import tools.refinery.store.model.representation.TruthValue;
+
+abstract class DecisionTreeNode {
+        public DecisionTreeValue getReducedValue() {
+                return getChildKeys().isEmpty() ? getOtherwiseReducedValue() : null;
+        }
+
+        public abstract DecisionTreeValue getValue(int level, Tuple tuple);
+
+        public abstract DecisionTreeNode deepCopy();
+
+        public void mergeValue(int level, Tuple tuple, TruthValue value) {
+                int nextLevel = level - 1;
+                var key = tuple.get(level);
+                if (key < 0) {
+                        mergeAllValues(nextLevel, tuple, value);
+                } else {
+                        mergeSingleValue(key, nextLevel, tuple, value);
+                }
+        }
+
+        protected abstract void mergeAllValues(int nextLevel, Tuple tuple, TruthValue value);
+
+        protected abstract void mergeSingleValue(int key, int nextLevel, Tuple tuple, TruthValue value);
+
+        public DecisionTreeNode withMergedValue(int level, Tuple tuple, TruthValue value) {
+                var copy = deepCopy();
+                copy.mergeValue(level, tuple, value);
+                return copy;
+        }
+
+        public abstract void overwriteValues(DecisionTreeNode values);
+
+        public DecisionTreeNode withOverwrittenValues(DecisionTreeNode values) {
+                var copy = deepCopy();
+                copy.overwriteValues(values);
+                return copy;
+        }
+
+        public boolean moveNext(int level, DecisionTreeCursor cursor) {
+                var currentState = cursor.iterationState[level];
+                boolean found;
+                if (currentState == DecisionTreeCursor.STATE_FINISH) {
+                        // Entering this node for the first time.
+                        cursor.path.push(this);
+                        if (cursor.defaultValue == getOtherwiseReducedValue()) {
+                                var sortedChildren = getChildKeys().toSortedArray();
+                                cursor.sortedChildren[level] = sortedChildren;
+                                found = moveNextSparse(level, cursor, 0, sortedChildren);
+                        } else {
+                                found = moveNextDense(level, cursor, 0);
+                        }
+                } else {
+                        var sortedChildren = cursor.sortedChildren[level];
+                        if (sortedChildren == null) {
+                                found = moveNextDense(level, cursor, currentState + 1);
+                        } else {
+                                found = moveNextSparse(level, cursor, currentState + 1, sortedChildren);
+                        }
+                }
+                if (!found) {
+                        cursor.sortedChildren[level] = null;
+                        cursor.iterationState[level] = DecisionTreeCursor.STATE_FINISH;
+                        var popped = cursor.path.pop();
+                        if (popped != this) {
+                                throw new IllegalStateException("Invalid decision diagram cursor");
+                        }
+                }
+                return found;
+        }
+
+        protected abstract DecisionTreeValue getOtherwiseReducedValue();
+
+        protected abstract LazyIntIterable getChildKeys();
+
+        protected abstract boolean moveNextSparse(int level, DecisionTreeCursor cursor, int startIndex,
+                                                                                          int[] sortedChildren);
+
+        protected abstract boolean moveNextDense(int level, DecisionTreeCursor cursor, int startIndex);
+}