weighted tree: Add test for the WeightedTree class
And update the javadoc for this class
Change-Id: I35cec4dec6b56584a536b4759eeafa15ac042225
Signed-off-by: Geneviève Bastien <gbastien+lttng@versatic.net>
Reviewed-on: https://git.eclipse.org/r/153137
Tested-by: CI Bot
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core.tests/src/org/eclipse/tracecompass/incubator/analysis/core/tests/weighted/WeightedTreeTest.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core.tests/src/org/eclipse/tracecompass/incubator/analysis/core/tests/weighted/WeightedTreeTest.java
new file mode 100644
index 0000000..5dd9887
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core.tests/src/org/eclipse/tracecompass/incubator/analysis/core/tests/weighted/WeightedTreeTest.java
@@ -0,0 +1,313 @@
+/*******************************************************************************
+ * 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.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.Collection;
+
+import org.eclipse.jdt.annotation.NonNullByDefault;
+import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.WeightedTree;
+import org.junit.Test;
+
+/**
+ * Test the {@link WeightedTree} class
+ *
+ * @author Geneviève Bastien
+ */
+@NonNullByDefault
+public class WeightedTreeTest {
+
+ private static final String OBJECT_NAME1 = "obj1";
+ private static final String OBJECT_NAME2 = "obj2";
+ private static final String OBJECT_NAME3 = "obj3";
+ private static final String OBJECT_NAME4 = "obj4";
+ private static final String OBJECT_NAME5 = "obj5";
+
+ /**
+ * Test the constructors
+ */
+ @Test
+ public void testConstructors() {
+ // Test the default constructor with only object
+ WeightedTree<String> wt = new WeightedTree<>(OBJECT_NAME1);
+ assertEquals("default constructor name", OBJECT_NAME1, wt.getObject());
+ assertEquals("default constructor initial weight", 0, wt.getWeight());
+ assertTrue("default constructor no children", wt.getChildren().isEmpty());
+ assertEquals("default depth", 1, wt.getMaxDepth());
+
+ // Test the constructor with initial weight
+ int initialWeight = 150;
+ wt = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+ assertEquals("constructor with weight name", OBJECT_NAME1, wt.getObject());
+ assertEquals("constructor with weight initial weight", initialWeight, wt.getWeight());
+ assertTrue("constructor with weight no children", wt.getChildren().isEmpty());
+ assertEquals("constructor with weight depth", 1, wt.getMaxDepth());
+ }
+
+ /**
+ * Test the {@link WeightedTree#merge(WeightedTree)} method
+ */
+ @Test
+ public void testSimpleMerge() {
+ int initialWeight = 150;
+ WeightedTree<String> wt = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+
+ // Merge without children
+ WeightedTree<String> wt2 = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+ wt.merge(wt2);
+ assertEquals("Value after merge", initialWeight * 2, wt.getWeight());
+ assertEquals("merged tree unmodified", initialWeight, wt2.getWeight());
+ }
+
+ /**
+ * Test merging trees for different objects, exception expected
+ */
+ @Test(expected = IllegalArgumentException.class)
+ public void testMergeWrongObject() {
+ int initialWeight = 150;
+ WeightedTree<String> wt = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+ WeightedTree<String> wt2 = new WeightedTree<>(OBJECT_NAME2, initialWeight);
+ wt.merge(wt2);
+ }
+
+ /**
+ * Test the {@link WeightedTree#addToWeight(long)} method
+ */
+ @Test
+ public void testAddToWeight() {
+ int initialWeight = 150;
+ WeightedTree<String> wt = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+ assertEquals("initial weight", initialWeight, wt.getWeight());
+
+ wt.addToWeight(initialWeight);
+ assertEquals("initial weight", initialWeight * 2, wt.getWeight());
+ }
+
+ /**
+ * Test the {@link WeightedTree#copyOf()} method
+ */
+ @Test
+ public void testCopyOf() {
+ int initialWeight = 150;
+ int childWeight = 50;
+ WeightedTree<String> wt = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+
+ // Test the copy without children
+ WeightedTree<String> wtCopy = wt.copyOf();
+ assertEquals("same weight", wt.getWeight(), wtCopy.getWeight());
+
+ // Make sure modifying the copy does not affect the original
+ wtCopy.addToWeight(initialWeight);
+ assertEquals("New copy weight", initialWeight * 2, wtCopy.getWeight());
+ assertEquals("Unchanged original weight", initialWeight, wt.getWeight());
+
+ // Add a child to wt and copy, children are also copied
+ WeightedTree<String> child = new WeightedTree<>(OBJECT_NAME1, childWeight);
+ wt.addChild(child);
+ wtCopy = wt.copyOf();
+ assertEquals("Same weight", wt.getWeight(), wtCopy.getWeight());
+ Collection<WeightedTree<String>> children = wtCopy.getChildren();
+ assertEquals("No children copied", 1, children.size());
+
+ // Make sure modifying the child does not affect the original child
+ WeightedTree<String> childCopy = children.iterator().next();
+ childCopy.addToWeight(childWeight);
+ assertEquals("New child copy weight", childWeight * 2, childCopy.getWeight());
+ assertEquals("Unchanged original child weight", childWeight, child.getWeight());
+
+ }
+
+ /**
+ * Test the {@link WeightedTree#addChild(WeightedTree)} method
+ */
+ @Test
+ public void testAddChild() {
+ int initialWeight = 150;
+ WeightedTree<String> wt = new WeightedTree<>(OBJECT_NAME1, initialWeight);
+
+ int childWeight = 30;
+ WeightedTree<String> child1 = new WeightedTree<>(OBJECT_NAME2, childWeight);
+
+ // Add a first child
+ wt.addChild(child1);
+ assertEquals("Unchanged parent weight", initialWeight, wt.getWeight());
+ assertEquals("Unchanged child weight", childWeight, child1.getWeight());
+ assertEquals("Children of parent", 1, wt.getChildren().size());
+ assertTrue("No child to child", child1.getChildren().isEmpty());
+ WeightedTree<String> treeChild = wt.getChildren().iterator().next();
+ assertEquals("Child of parent", child1, treeChild);
+
+ // Add a second child for different object
+ WeightedTree<String> child2 = new WeightedTree<>(OBJECT_NAME3, childWeight);
+ wt.addChild(child2);
+ assertEquals("Unchanged parent weight", initialWeight, wt.getWeight());
+ assertEquals("Unchanged child weight", childWeight, child2.getWeight());
+ assertEquals("Children of parent", 2, wt.getChildren().size());
+
+ // Add a third child to merge with child1
+ WeightedTree<String> child3 = new WeightedTree<>(OBJECT_NAME2, childWeight);
+ wt.addChild(child3);
+ assertEquals("Unchanged parent weight", initialWeight, wt.getWeight());
+ assertEquals("Unchanged child weight", childWeight, child3.getWeight());
+ assertEquals("Children of parent", 2, wt.getChildren().size());
+ assertEquals("New tree child weight", childWeight * 2, treeChild.getWeight());
+
+ assertEquals("Max depth", 2, wt.getMaxDepth());
+
+ // Add wt as a child to a new parent tree
+ WeightedTree<String> parent = new WeightedTree<>(OBJECT_NAME4, initialWeight * 2);
+ parent.addChild(wt);
+ assertFalse("Parent's child", parent.getChildren().isEmpty());
+ treeChild = parent.getChildren().iterator().next();
+ assertEquals("no children lost", 2, treeChild.getChildren().size());
+ assertEquals("Final max depth", 3, parent.getMaxDepth());
+ }
+
+ /**
+ * Test the {@link WeightedTree#merge(WeightedTree)} method for objects that
+ * have many levels of similar children
+ */
+ @Test
+ public void testDeepMerge() {
+ /**
+ * Here's the layout of the objects to merge
+ *
+ * <pre>
+ * 1 1
+ * / \ \ / \ \
+ * 1 2 3 1 2 5
+ * / \ | / \ | |
+ * 4 5 2 3 4 1 2
+ *
+ * Expected:
+ * 1*2
+ * / | \ \
+ * 1*2 2*2 3 5
+ * / | \ / \ |
+ * 3 4*2 5 1 2 2
+ * </pre>
+ */
+ int level0Weight = 150;
+ int level1Weight = 40;
+ int level2Weight = 10;
+
+ // Prepare the objects to merge
+ // First object
+ WeightedTree<String> wtParent1 = new WeightedTree<>(OBJECT_NAME1, level0Weight);
+ WeightedTree<String> wtLevel1 = new WeightedTree<>(OBJECT_NAME1, level1Weight);
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME4, level2Weight));
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME5, level2Weight));
+ wtParent1.addChild(wtLevel1);
+
+ wtLevel1 = new WeightedTree<>(OBJECT_NAME2, level1Weight);
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME2, level2Weight));
+ wtParent1.addChild(wtLevel1);
+
+ wtParent1.addChild(new WeightedTree<>(OBJECT_NAME3, level1Weight));
+
+ // Second object
+ WeightedTree<String> wtParent2 = new WeightedTree<>(OBJECT_NAME1, level0Weight);
+ wtLevel1 = new WeightedTree<>(OBJECT_NAME1, level1Weight);
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME3, level2Weight));
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME4, level2Weight));
+ wtParent2.addChild(wtLevel1);
+
+ wtLevel1 = new WeightedTree<>(OBJECT_NAME2, level1Weight);
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME1, level2Weight));
+ wtParent2.addChild(wtLevel1);
+
+ wtLevel1 = new WeightedTree<>(OBJECT_NAME5, level1Weight);
+ wtLevel1.addChild(new WeightedTree<>(OBJECT_NAME2, level2Weight));
+ wtParent2.addChild(wtLevel1);
+
+ // Merge the objects and test its content
+ wtParent1.merge(wtParent2);
+
+ assertEquals("Level 0 Weight", level0Weight * 2, wtParent1.getWeight());
+ Collection<WeightedTree<String>> level1Children = wtParent1.getChildren();
+ assertEquals("Level 0 Nb children", 4, level1Children.size());
+ assertEquals("Max depth", 3, wtParent1.getMaxDepth());
+
+ for (WeightedTree<String> level1Child : level1Children) {
+ switch (level1Child.getObject()) {
+ case OBJECT_NAME1:
+ {
+ assertEquals("Level 1 Weight 1", level1Weight * 2, level1Child.getWeight());
+ Collection<WeightedTree<String>> level2Children = level1Child.getChildren();
+ assertEquals("Level 1 Nb children 1", 3, level2Children.size());
+ for (WeightedTree<String> level2Child : level2Children) {
+ switch (level2Child.getObject()) {
+ case OBJECT_NAME3: // Fall-through, same weight and children
+ case OBJECT_NAME5:
+ assertEquals("Level 2-1 Weight", level2Weight, level2Child.getWeight());
+ assertTrue("Empty children at last level", level2Child.getChildren().isEmpty());
+ break;
+ case OBJECT_NAME4:
+ assertEquals("Level 2-1 Weight", level2Weight * 2, level2Child.getWeight());
+ assertTrue("Empty children at last level", level2Child.getChildren().isEmpty());
+ break;
+ default:
+ fail("Unknown child " + level2Child.getObject());
+ break;
+ }
+ }
+ }
+ break;
+ case OBJECT_NAME2:
+ {
+ assertEquals("Level 1 Weight 2", level1Weight * 2, level1Child.getWeight());
+ Collection<WeightedTree<String>> level2Children = level1Child.getChildren();
+ assertEquals("Level 1 Nb children 2", 2, level2Children.size());
+ for (WeightedTree<String> level2Child : level2Children) {
+ switch (level2Child.getObject()) {
+ case OBJECT_NAME1: // Fall-through, same weight and children
+ case OBJECT_NAME2:
+ assertEquals("Level 2-2 Weight", level2Weight, level2Child.getWeight());
+ assertTrue("Empty children at last level", level2Child.getChildren().isEmpty());
+ break;
+ default:
+ fail("Unknown child " + level2Child.getObject());
+ break;
+ }
+ }
+ }
+ break;
+ case OBJECT_NAME3:
+ assertEquals("Level 1 Weight 3", level1Weight, level1Child.getWeight());
+ assertTrue("Empty children at last level", level1Child.getChildren().isEmpty());
+ break;
+ case OBJECT_NAME5:
+ assertEquals("Level 1 Weight 4", level1Weight, level1Child.getWeight());
+ Collection<WeightedTree<String>> level2Children = level1Child.getChildren();
+ assertEquals("Level 1 Nb children 4", 1, level2Children.size());
+ for (WeightedTree<String> level2Child : level2Children) {
+ switch (level2Child.getObject()) {
+ case OBJECT_NAME2:
+ assertEquals("Level 2-2 Weight", level2Weight, level2Child.getWeight());
+ assertTrue("Empty children at last level", level2Child.getChildren().isEmpty());
+ break;
+ default:
+ fail("Unknown child " + level2Child.getObject());
+ break;
+ }
+ }
+ break;
+ default:
+ fail("Unknown child " + level1Child.getObject());
+ break;
+ }
+ }
+ }
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java
index 0113e40..7273fb2 100644
--- a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java
@@ -44,25 +44,23 @@
/**
* Constructor
*
- * @param symbol
- * The symbol of the call site. It can eventually be resolved to
- * a string using the symbol providers
+ * @param object
+ * The object that goes with this tree.
*/
- public WeightedTree(T symbol) {
- this(symbol, 0);
+ public WeightedTree(T object) {
+ this(object, 0);
}
/**
* Constructor
*
- * @param symbol
- * The symbol of the call site. It can eventually be resolved to
- * a string using the symbol providers
+ * @param object
+ * The object that goes with this tree.
* @param initialWeight
* The initial length of this object
*/
- public WeightedTree(T symbol, long initialWeight) {
- fObject = symbol;
+ public WeightedTree(T object, long initialWeight) {
+ fObject = object;
fParent = null;
fWeight = initialWeight;
}
@@ -71,7 +69,7 @@
* Copy constructor
*
* @param copy
- * The call site to copy
+ * The tree to copy
*/
protected WeightedTree(WeightedTree<T> copy) {
fObject = copy.fObject;
@@ -83,41 +81,41 @@
}
/**
- * Get the aggregated value of this callsite. The units of this length will
- * depend on the time of callstack. Typically, for sampled, it will be the
- * number of times this symbol was hit, while for instrumented, it can be
- * the total time spent in this callstack element
+ * Get the weight of this tree. The unit of this weight will depend on the
+ * metric it represents.
*
- * @return The aggregated value of this callsite
+ * @return The weight of this tree
*/
public long getWeight() {
return fWeight;
}
/**
- * Make a copy of this callsite, with its statistics. Implementing classes
- * should make sure they copy all fields of the callsite, including the
+ * Make a copy of this tree, with its statistics. Implementing classes
+ * should make sure they copy all fields of the tree, including the
* statistics.
*
- * @return A copy of this aggregated call site
+ * This constructor recursively copies all the children.
+ *
+ * @return A copy of this weighted tree
*/
public WeightedTree<T> copyOf() {
return new WeightedTree<>(this);
}
/**
- * Get the symbol associated with this callsite
+ * Get the object associated with this tree
*
- * @return The symbol for this callsite
+ * @return The object for this tree
*/
public T getObject() {
return fObject;
}
/**
- * Get the caller of this callsite (parent)
+ * Get the parent of this tree
*
- * @return The caller of this callsite
+ * @return The parent of this tree
*/
protected @Nullable WeightedTree<T> getParent() {
return fParent;
@@ -134,16 +132,16 @@
}
/**
- * Get the callees of this callsite, ie the functions called by this one
+ * Get the children of this tree
*
- * @return A collection of callees' callsites
+ * @return A collection of children trees
*/
public Collection<WeightedTree<T>> getChildren() {
return fChildren.values();
}
/**
- * Add value to the length of this callsite
+ * Add value to the weight of this tree
*
* @param weight
* the amount to add to the length
@@ -153,35 +151,35 @@
}
/**
- * Add a callee to this callsite. If a callee for the same object already
- * exists, the data for both callees will be merged.
+ * Add a child to this tree. If a child for the same object already
+ * exists, the data for both children will be merged.
*
- * @param callee
- * the call site of the callee
+ * @param child
+ * the child tree to add
*/
- public void addChild(WeightedTree<T> callee) {
- WeightedTree<T> callsite = fChildren.get(callee.getObject());
- if (callsite == null) {
- callee.setParent(this);
- fChildren.put(callee.getObject(), callee);
+ public void addChild(WeightedTree<T> child) {
+ WeightedTree<T> childTree = fChildren.get(child.getObject());
+ if (childTree == null) {
+ child.setParent(this);
+ fChildren.put(child.getObject(), child);
return;
}
- callsite.merge(callee);
+ childTree.merge(child);
}
/**
- * Merge a callsite's data with this one. This method will modify the
- * current callsite.
+ * Merge a tree's data with this one. This method will modify the current
+ * tree.
*
* It will first call {@link #mergeData(WeightedTree)} that needs to be
* implemented for each implementation of this class.
*
- * It will then merge the callees of both callsites by adding the other's
- * callees to this one.
+ * It will then merge the children of both trees by adding the other's
+ * children to this one.
*
* @param other
- * The call site to merge. It has to have the same symbol as the
- * current callsite otherwise it will throw an
+ * The tree to merge. It has to have the same object as the
+ * current tree otherwise it will throw an
* {@link IllegalArgumentException}
*/
public final void merge(WeightedTree<T> other) {
@@ -194,29 +192,29 @@
}
/**
- * Merge the data of two callsites. This should modify the current
- * callsite's specific data. It is called by {@link #merge(WeightedTree)}
- * and this method MUST NOT touch the callees of the callsites.
+ * Merge the data of two trees. This should modify the current
+ * tree's specific data. It is called by {@link #merge(WeightedTree)}
+ * and this method MUST NOT touch the children of the tree.
*
* @param other
- * The call site to merge to this one
+ * The tree to merge to this one
*/
protected void mergeData(WeightedTree<T> other) {
// Nothing to do in main class
}
/**
- * Merge the children callsites
+ * Merge the children trees
*
* @param other
- * The call site to merge to this one
+ * The tree to merge to this one
*/
private void mergeChildren(WeightedTree<T> other) {
for (WeightedTree<T> otherChildSite : other.fChildren.values()) {
- T childSymbol = otherChildSite.getObject();
- WeightedTree<T> childSite = fChildren.get(childSymbol);
+ T childObject = otherChildSite.getObject();
+ WeightedTree<T> childSite = fChildren.get(childObject);
if (childSite == null) {
- fChildren.put(childSymbol, otherChildSite.copyOf());
+ fChildren.put(childObject, otherChildSite.copyOf());
} else {
// combine children
childSite.merge(otherChildSite);
@@ -225,11 +223,11 @@
}
/**
- * Get the maximum depth under and including this aggregated callsite. A
- * depth of 1 means there is one element under and including this element.
+ * Get the maximum depth under and including this tree. A depth of 1 means
+ * there is one element under and including this element.
*
- * @return The maximum depth under and including this aggregated call site.
- * The minimal value for the depth is 1.
+ * @return The maximum depth under and including this tree. The minimal
+ * value for the depth is 1.
*/
public int getMaxDepth() {
int maxDepth = 0;
@@ -243,17 +241,17 @@
* Get other children of this tree that are not its direct descendants. It
* can be used for instance to represent extra data, for example kernel
* statuses for a callstack.
- * <p>
- * A weighted tree provider will advertise those potential children data
- * that come with this tree, and consumers can then call this method with
- * the index of this extra type, if the tree has more than one extra data
- * set
+ *
+ * A {@link IWeightedTreeProvider} will advertise those potential children
+ * data that come with this tree, and consumers can then call this method
+ * with the index of this extra type, if the tree has more than one extra
+ * data set
*
* @param index
* The index of this extra children set, as provided by the
* {@link IWeightedTreeProvider#getExtraDataSets()} method.
*
- * @return The extra children sites
+ * @return The extra children trees
*/
public Collection<WeightedTree<@NonNull T>> getExtraDataTrees(int index) {
return Collections.emptyList();
@@ -261,7 +259,7 @@
@Override
public String toString() {
- return "WeightedTreeNode: " + fObject; //$NON-NLS-1$
+ return "[" + fObject + "]: " + fWeight; //$NON-NLS-1$ //$NON-NLS-2$
}
@Override
