weighted tree: Add a differential tree class
Adds a utility method to calculate a differential tree between 2 trees.
Also add the class to represent a differential weighted tree and its
provider.
[added] Differential weighted tree classes
Change-Id: I458d7bdb402d4e957b7ee8c4868d3cb078d193ca
Signed-off-by: Geneviève Bastien <gbastien+lttng@versatic.net>
Reviewed-on: https://git.eclipse.org/r/149206
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Tested-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Tested-by: CI Bot
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core.tests/src/org/eclipse/tracecompass/incubator/analysis/core/tests/weighted/WeightedTreeUtilsTest.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core.tests/src/org/eclipse/tracecompass/incubator/analysis/core/tests/weighted/WeightedTreeUtilsTest.java
new file mode 100644
index 0000000..1a4e7b6
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core.tests/src/org/eclipse/tracecompass/incubator/analysis/core/tests/weighted/WeightedTreeUtilsTest.java
@@ -0,0 +1,151 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.tests.weighted;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import org.eclipse.jdt.annotation.NonNullByDefault;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.WeightedTree;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.WeightedTreeUtils;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff.DifferentialWeightedTree;
+import org.junit.Test;
+
+/**
+ * Test the operations on the the {@link WeightedTree} class
+ *
+ * @author Geneviève Bastien
+ */
+@NonNullByDefault
+public class WeightedTreeUtilsTest {
+
+ private static final Integer ELEMENT1 = 1;
+ private static final Integer ELEMENT2 = 2;
+ private static final Integer ELEMENT3 = 3;
+ private static final Integer ELEMENT4 = 4;
+ private static final Integer ELEMENT5 = 5;
+
+ /**
+ * Test the {@link WeightedTreeUtils#diffTrees(Collection, Collection)}
+ * method with simple trees
+ */
+ @Test
+ public void testDiffTree() {
+ // Create a simple tree with 2 elements and a level of children
+ List<WeightedTree<Integer>> tree1 = new ArrayList<>();
+ List<WeightedTree<Integer>> tree2 = new ArrayList<>();
+ /**
+ * <pre>
+ * Create a first collection of tree
+ * * 1 -> 10
+ * | * 2 -> 4
+ * | * 3 -> 3
+ * | * 3 -> 1
+ * * 2 -> 10
+ * | * 4 -> 5
+ * | * 5 -> 5
+ * </pre>
+ */
+ WeightedTree<Integer> element1 = new WeightedTree<>(ELEMENT1, 10);
+ element1.addChild(new WeightedTree<>(ELEMENT2, 4));
+ WeightedTree<Integer> element2 = new WeightedTree<>(ELEMENT3, 3);
+ element1.addChild(element2);
+ element2.addChild(new WeightedTree<>(ELEMENT3, 1));
+ tree1.add(element1);
+ element1 = new WeightedTree<>(ELEMENT2, 10);
+ element1.addChild(new WeightedTree<>(ELEMENT4, 5));
+ element1.addChild(new WeightedTree<>(ELEMENT5, 5));
+ tree1.add(element1);
+
+ /**
+ * <pre>
+ * Create a second collection of tree
+ * * 1 -> 10
+ * | * 2 -> 3
+ * | * 3 -> 3
+ * | * 3 -> 1
+ * * 2 -> 20
+ * | * 4 -> 10
+ * | * 5 -> 10
+ * | * 3 -> 5
+ * </pre>
+ */
+ element1 = new WeightedTree<>(ELEMENT1, 10);
+ element1.addChild(new WeightedTree<>(ELEMENT2, 3));
+ element2 = new WeightedTree<>(ELEMENT3, 3);
+ element1.addChild(element2);
+ element2.addChild(new WeightedTree<>(ELEMENT3, 1));
+ tree2.add(element1);
+ element1 = new WeightedTree<>(ELEMENT2, 20);
+ element1.addChild(new WeightedTree<>(ELEMENT4, 10));
+ element2 = new WeightedTree<>(ELEMENT5, 10);
+ element1.addChild(element2);
+ element2.addChild(new WeightedTree<>(ELEMENT3, 5));
+ tree2.add(element1);
+
+ // Differentiate tree1 and tree2
+ Collection<DifferentialWeightedTree<Integer>> diffTrees = WeightedTreeUtils.diffTrees(tree1, tree2);
+ assertEquals("Size of differential tree", 2, diffTrees.size());
+ // Compare the first element
+ Collection<DifferentialWeightedTree<Integer>> nextTree = getAndVerifyTree(diffTrees, ELEMENT1, 10, 0);
+ assertEquals("Size of differential tree level 2", 2, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT2, 3, -0.25);
+ nextTree = getAndVerifyTree(nextTree, ELEMENT3, 3, 0);
+ assertEquals("Size of diferential tree level 3", 1, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT3, 1, 0);
+
+ // Compare the second element
+ nextTree = getAndVerifyTree(diffTrees, ELEMENT2, 20, 1.0);
+ assertEquals("Size of differential tree level 2", 2, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT4, 10, 1.0);
+ nextTree = getAndVerifyTree(nextTree, ELEMENT5, 10, 1.0);
+ assertEquals("Size of diferential tree level 3", 1, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT3, 5, Double.NaN);
+
+ // Reverse: Differentiate tree2 and tree1
+ diffTrees = WeightedTreeUtils.diffTrees(tree2, tree1);
+ assertEquals("Size of differential tree", 2, diffTrees.size());
+ // Compare the first element
+ nextTree = getAndVerifyTree(diffTrees, ELEMENT1, 10, 0);
+ assertEquals("Size of differential tree level 2", 2, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT2, 4, 0.33333);
+ nextTree = getAndVerifyTree(nextTree, ELEMENT3, 3, 0);
+ assertEquals("Size of diferential tree level 3", 1, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT3, 1, 0);
+
+ // Compare the first element
+ nextTree = getAndVerifyTree(diffTrees, ELEMENT2, 10, -0.5);
+ assertEquals("Size of differential tree level 2", 2, nextTree.size());
+ getAndVerifyTree(nextTree, ELEMENT4, 5, -0.5);
+ nextTree = getAndVerifyTree(nextTree, ELEMENT5, 5, -0.5);
+ assertTrue(nextTree.isEmpty());
+ }
+
+ private static Collection<DifferentialWeightedTree<Integer>> getAndVerifyTree(Collection<DifferentialWeightedTree<Integer>> diffTrees, Integer element, int expectedWeight, double expectedDiff) {
+ for (DifferentialWeightedTree<Integer> tree : diffTrees) {
+ List<DifferentialWeightedTree<Integer>> children = new ArrayList<>();
+ if (tree.getObject().equals(element)) {
+ // Found the tree, verify its values and return its children
+ assertEquals("Base weight of " + element, expectedWeight, tree.getWeight());
+ assertEquals("Differential value of " + element, expectedDiff, tree.getDifference(), 0.001);
+ for (WeightedTree<Integer> child : tree.getChildren()) {
+ children.add((DifferentialWeightedTree<Integer>) child);
+ }
+ return children;
+ }
+ }
+ throw new NullPointerException("Tree not found for object " + element);
+ }
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF b/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF
index ca80ce5..b9b86cb 100644
--- a/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF
@@ -22,8 +22,10 @@
org.eclipse.tracecompass.incubator.analysis.core.concepts,
org.eclipse.tracecompass.incubator.analysis.core.model,
org.eclipse.tracecompass.incubator.analysis.core.weighted.tree,
+ org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff,
org.eclipse.tracecompass.incubator.internal.analysis.core;x-internal:=true,
org.eclipse.tracecompass.incubator.internal.analysis.core.aspects;x-internal:=true,
org.eclipse.tracecompass.incubator.internal.analysis.core.model;x-friends:="org.eclipse.tracecompass.incubator.analysis.core.tests,org.eclipse.tracecompass.incubator.callstack.core.tests"
-Import-Package: com.google.common.collect
+Import-Package: com.google.common.collect,
+ org.apache.commons.lang3
Automatic-Module-Name: org.eclipse.tracecompass.incubator.analysis.core
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTreeUtils.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTreeUtils.java
new file mode 100644
index 0000000..fc95ac3
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTreeUtils.java
@@ -0,0 +1,72 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff.DifferentialWeightedTree;
+
+/**
+ * Utility methods to operate on {@link WeightedTree} objects
+ *
+ * @author Geneviève Bastien
+ */
+public final class WeightedTreeUtils {
+
+ private WeightedTreeUtils() {
+ // Nothing to do
+ }
+
+ /**
+ * Does the differential between 2 weighted trees, ie what happened in tree2
+ * differently than in tree1. The base weight come from the second tree and
+ * the differential value will show the difference with the first tree.
+ *
+ * @param <T>
+ * The type of element in the tree
+ * @param first
+ * The tree that will be differentiated.
+ * @param second
+ * The tree to use as the base
+ * @return The differential weighted tree
+ */
+ public static <@NonNull T> Collection<DifferentialWeightedTree<T>> diffTrees(Collection<WeightedTree<T>> first, Collection<WeightedTree<T>> second) {
+ List<DifferentialWeightedTree<T>> diffTrees = new ArrayList<>();
+ for (WeightedTree<T> base : second) {
+ T object = base.getObject();
+ // Find the equivalent tree in the first collection
+ WeightedTree<T> other = findObject(first, object);
+ double diffWeight = other == null ? Double.NaN : (double) (base.getWeight() - other.getWeight()) / other.getWeight();
+ DifferentialWeightedTree<@NonNull T> diffTree = new DifferentialWeightedTree<>(base, object, base.getWeight(), diffWeight);
+ diffTrees.add(diffTree);
+
+ // Make the differential of the children
+ for (DifferentialWeightedTree<T> childTree : diffTrees(other == null ? Collections.emptyList() : other.getChildren(), base.getChildren())) {
+ diffTree.addChild(childTree);
+ }
+ }
+ return diffTrees;
+ }
+
+ private static @Nullable <@NonNull T> WeightedTree<T> findObject(Collection<WeightedTree<T>> tree, @NonNull T object) {
+ for (WeightedTree<T> other : tree) {
+ if (other.getObject().equals(object)) {
+ return other;
+ }
+ }
+ return null;
+ }
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/DifferentialWeightedTree.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/DifferentialWeightedTree.java
new file mode 100644
index 0000000..9ed8c87
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/DifferentialWeightedTree.java
@@ -0,0 +1,73 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.WeightedTree;
+
+/**
+ * A class that represents a differential weighted tree. The weight is the base
+ * weight of one of the differentiated tree[set] and a differencial value is
+ * used to represent how it differs with the weight value of another tree.
+ *
+ * @author Geneviève Bastien
+ *
+ * @param <T>
+ * The type of object this tree uses
+ */
+public class DifferentialWeightedTree<@NonNull T> extends WeightedTree<@NonNull T> {
+
+ private final double fDifference;
+ private final WeightedTree<@NonNull T> fOriginalTree;
+
+ /**
+ * Constructor
+ *
+ * @param originalTree
+ * The base tree from which this differential tree was computed.
+ * Used for additional metrics and texts.
+ * @param object
+ * The object this tree is linked to
+ * @param initialWeight
+ * The initial weight of this tree
+ * @param diffWeight
+ * The differential weight with the base
+ */
+ public DifferentialWeightedTree(WeightedTree<T> originalTree, T object, long initialWeight, double diffWeight) {
+ super(object, initialWeight);
+ fDifference = diffWeight;
+ fOriginalTree = originalTree;
+ }
+
+ /**
+ * Get the differential value for this object. This value is the relative
+ * difference between the value of a first tree and the second tree
+ * compared. A positive value means the object's value is superior than the
+ * previous value. Conversely a negative difference means the second value
+ * is inferior to the initial value. 0 means there was no difference.
+ *
+ * It can also be {@link Double#NaN} if the value did not exist before
+ *
+ * @return The differential value
+ */
+ public double getDifference() {
+ return fDifference;
+ }
+
+ /**
+ * Get the base tree from which this differential weighted tree was computed
+ *
+ * @return The original base tree
+ */
+ public WeightedTree<@NonNull T> getOriginalTree() {
+ return fOriginalTree;
+ }
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/DifferentialWeightedTreeProvider.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/DifferentialWeightedTreeProvider.java
new file mode 100644
index 0000000..e540c1e
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/DifferentialWeightedTreeProvider.java
@@ -0,0 +1,129 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff;
+
+import java.text.DecimalFormat;
+import java.text.FieldPosition;
+import java.text.Format;
+import java.text.ParsePosition;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import org.apache.commons.lang3.StringUtils;
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.IWeightedTreeProvider;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.WeightedTree;
+
+/**
+ * Weighted tree provider that provides a differential weighted tree. Since any
+ * tree can be differentiated with other trees, this class is mostly a wrapper
+ * around the original tree provider, only the elements and trees are specific
+ * to this class.
+ *
+ * @author Geneviève Bastien
+ */
+public class DifferentialWeightedTreeProvider implements IWeightedTreeProvider<Object, String, DifferentialWeightedTree<Object>> {
+
+ private static final String DEFAULT_ELEMENT = "diff"; //$NON-NLS-1$
+ private static final Format FORMAT = new DecimalFormat("#.#"); //$NON-NLS-1$
+
+ private static final Format DIFFERENTIAL_FORMAT = new Format() {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ public @Nullable StringBuffer format(@Nullable Object obj, @Nullable StringBuffer toAppendTo, @Nullable FieldPosition pos) {
+ StringBuffer buf = toAppendTo;
+ if (buf == null) {
+ buf = new StringBuffer();
+ }
+ if (obj instanceof Number) {
+ double num = ((Number) obj).doubleValue();
+ if (num == 0.0) {
+ return buf.append("No Difference"); //$NON-NLS-1$
+ }
+ return buf.append((num > 0 ? "+" : "")).append(FORMAT.format(num * 100)).append("%"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+ }
+ return FORMAT.format(obj, toAppendTo, pos);
+ }
+
+ @Override
+ public @Nullable Object parseObject(@Nullable String source, @Nullable ParsePosition pos) {
+ return null;
+ }
+
+ };
+
+ private static final List<MetricType> WEIGHT_TYPES = Collections.singletonList(new MetricType("Differential", DataType.OTHER, DIFFERENTIAL_FORMAT)); //$NON-NLS-1$
+
+ private final Collection<DifferentialWeightedTree<Object>> fTrees;
+
+ private final IWeightedTreeProvider<Object, ?, WeightedTree<Object>> fOriginalTree;
+
+ /**
+ * Constructor
+ *
+ * @param originalTree
+ * The original tree provider, used to get information for texts and metrics.
+ * @param trees
+ * The differential tree
+ */
+ public DifferentialWeightedTreeProvider(IWeightedTreeProvider<Object, ?, WeightedTree<Object>> originalTree, Collection<DifferentialWeightedTree<Object>> trees) {
+ fTrees = trees;
+ fOriginalTree = originalTree;
+ }
+
+ @Override
+ public Collection<DifferentialWeightedTree<Object>> getTreesFor(String element) {
+ if (element.equals(DEFAULT_ELEMENT)) {
+ return fTrees;
+ }
+ return Collections.emptyList();
+ }
+
+ @Override
+ public Collection<String> getElements() {
+ return Collections.singleton(DEFAULT_ELEMENT);
+ }
+
+ @Override
+ public String getTitle() {
+ return "Differential tree"; //$NON-NLS-1$
+ }
+
+ @Override
+ public @NonNull MetricType getWeightType() {
+ return fOriginalTree.getWeightType();
+ }
+
+ @Override
+ public String toDisplayString(DifferentialWeightedTree<Object> tree) {
+ return fOriginalTree.toDisplayString(tree.getOriginalTree());
+ }
+
+ @Override
+ public List<MetricType> getAdditionalMetrics() {
+ return WEIGHT_TYPES;
+ }
+
+ @Override
+ public Object getAdditionalMetric(DifferentialWeightedTree<Object> object, int metricIndex) {
+ if (metricIndex == 0) {
+ return object.getDifference();
+ }
+ return StringUtils.EMPTY;
+ }
+
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/package-info.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/package-info.java
new file mode 100644
index 0000000..9d63fc3
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/diff/package-info.java
@@ -0,0 +1,11 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+@org.eclipse.jdt.annotation.NonNullByDefault
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff;
