1 files changed, 146 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/util/timeline/Timeline.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/util/timeline/Timeline.java
new file mode 100644
index 00000000..9214536c
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/util/timeline/Timeline.java
@@ -0,0 +1,146 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2019, Tamas Szabo, itemis AG, Gabor Bergmann, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.matchers.util.timeline;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import tools.refinery.viatra.runtime.matchers.util.Direction;
+import tools.refinery.viatra.runtime.matchers.util.Signed;
+
+/**
+ * A timeline describes the life cycle of a piece of data (typically a tuple in a relation) as a sequence of moments.
+ * Even moments represent appearances, odd moments represent disappearances. A timeline is immutable, once created, it
+ * is not possible to extend it with further moments.
+ * 
+ * @author Tamas Szabo
+ * @since 2.4
+ */
+public abstract class Timeline<Timestamp extends Comparable<Timestamp>> {
+
+    public abstract Iterable<Signed<Timestamp>> asChangeSequence();
+
+    public abstract boolean isPresentAtInfinity();
+
+    public abstract boolean isEmpty();
+
+    public abstract int size();
+
+    public abstract Signed<Timestamp> getSigned(final int index);
+
+    public abstract Timestamp getUnsigned(final int index);
+
+    public Timeline<Timestamp> mergeMultiplicative(final Timeline<Timestamp> that) {
+        final List<Timestamp> result = new ArrayList<>();
+        int thisIdx = 0, thatIdx = 0;
+        Timestamp thisNext = thisIdx < this.size() ? this.getUnsigned(thisIdx) : null;
+        Timestamp thatNext = thatIdx < that.size() ? that.getUnsigned(thatIdx) : null;
+
+        while (thisNext != null || thatNext != null) {
+            int thisMinusThat = 0;
+            if (thisNext != null && thatNext != null) {
+                thisMinusThat = thisNext.compareTo(thatNext);
+            }
+            if (thisNext == null || thisMinusThat > 0) {
+                if (thisIdx % 2 == 1) {
+                    result.add(thatNext);
+                }
+                thatIdx++;
+                thatNext = thatIdx < that.size() ? that.getUnsigned(thatIdx) : null;
+            } else if (thatNext == null || thisMinusThat < 0) {
+                if (thatIdx % 2 == 1) {
+                    result.add(thisNext);
+                }
+                thisIdx++;
+                thisNext = thisIdx < this.size() ? this.getUnsigned(thisIdx) : null;
+            } else {
+                if (thisIdx % 2 == thatIdx % 2) {
+                    result.add(thisNext);
+                }
+                thisIdx++;
+                thatIdx++;
+                thatNext = thatIdx < that.size() ? that.getUnsigned(thatIdx) : null;
+                thisNext = thisIdx < this.size() ? this.getUnsigned(thisIdx) : null;
+            }
+        }
+
+        return Timelines.createFrom(result);
+    }
+
+    /**
+     * Merges this timeline with the given timestamp diff. The expectation is that the resulting timeline starts with an
+     * insertion. The logic is similar to a merge sort; we iterate side-by-side over the timeline and the diff. During
+     * the merge, cancellation can happen if at the same timestamp we observe different signs at the corresponding
+     * timeline and diff elements.
+     */
+    public Timeline<Timestamp> mergeAdditive(final Diff<Timestamp> diff) {
+        final Iterator<Signed<Timestamp>> thisItr = this.asChangeSequence().iterator();
+        final Iterator<Signed<Timestamp>> diffItr = diff.iterator();
+        final List<Timestamp> result = new ArrayList<>();
+        Direction expected = Direction.INSERT;
+        Signed<Timestamp> thisNext = thisItr.hasNext() ? thisItr.next() : null;
+        Signed<Timestamp> diffNext = diffItr.hasNext() ? diffItr.next() : null;
+
+        while (thisNext != null || diffNext != null) {
+            int thisMinusDiff = 0;
+            if (thisNext != null && diffNext != null) {
+                thisMinusDiff = thisNext.getPayload().compareTo(diffNext.getPayload());
+            }
+
+            if (thisNext == null || thisMinusDiff > 0) {
+                if (!expected.equals(diffNext.getDirection())) {
+                    throw new IllegalStateException(
+                            String.format("Expected direction (%s) constraint violated! %s %s @%s", expected, this,
+                                    diff, diffNext.getPayload()));
+                }
+                result.add(diffNext.getPayload());
+                diffNext = diffItr.hasNext() ? diffItr.next() : null;
+                expected = expected.opposite();
+            } else if (diffNext == null || thisMinusDiff < 0) {
+                if (!expected.equals(thisNext.getDirection())) {
+                    throw new IllegalStateException(
+                            String.format("Expected direction (%s) constraint violated! %s %s @%s", expected, this,
+                                    diff, thisNext.getPayload()));
+                }
+                result.add(thisNext.getPayload());
+                thisNext = thisItr.hasNext() ? thisItr.next() : null;
+                expected = expected.opposite();
+            } else {
+                // they cancel out each other
+                if (diffNext.getDirection().equals(thisNext.getDirection())) {
+                    throw new IllegalStateException(String.format("Changes do not cancel out each other! %s %s @%s",
+                            this, diff, thisNext.getPayload()));
+                }
+                diffNext = diffItr.hasNext() ? diffItr.next() : null;
+                thisNext = thisItr.hasNext() ? thisItr.next() : null;
+            }
+        }
+
+        return Timelines.createFrom(result);
+    }
+
+    @Override
+    public String toString() {
+        final StringBuilder builder = new StringBuilder();
+        builder.append("[");
+        boolean first = true;
+        for (final Signed<Timestamp> element : this.asChangeSequence()) {
+            if (first) {
+                first = false;
+            } else {
+                builder.append(", ");
+            }
+            builder.append(element.toString());
+        }
+        builder.append("]");
+        return builder.toString();
+    }
+
+}