| /******************************************************************************* |
| * 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; |
| import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff.DifferentialWeightedTreeProvider; |
| import org.eclipse.tracecompass.incubator.analysis.core.weighted.tree.diff.DifferentialWeightedTreeSet; |
| import org.eclipse.tracecompass.tmf.core.util.Pair; |
| |
| import com.google.common.collect.ImmutableList; |
| |
| /** |
| * 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; |
| } |
| |
| /** |
| * Does the differential between 2 weighted tree sets, ie for each |
| * comparable elements, what happened in tree set 2 differently than in tree |
| * set 1. The base weight come from the second tree set and the differential |
| * value will show the difference with the first tree. |
| * <p> |
| * Calling this method assumes the tree sets are comparable. It is the |
| * caller's responsibility to make sure the parameters make sense. If the 2 |
| * tree sets come from different {@link IWeightedTreeProvider}, they should |
| * be of similar types, otherwise, the comparison may not make sense. |
| * </p> |
| * <p> |
| * The elements of each tree set are paired as follows: |
| * </p> |
| * <p> |
| * 1- If there is only one element in each tree, they will be paired. |
| * </p> |
| * <p> |
| * 2- If the same elements are present in both tree sets, they will be |
| * paired, all other elements are ignored |
| * </p> |
| * <p> |
| * 3- If no elements are paired, they will be paired by name (and |
| * hierarchical names, if it applies). Unmatched elements will be ignored. |
| * </p> |
| * <p> |
| * If elements are not paired at this point, it will return |
| * <code>null</code> |
| * </p> |
| * |
| * @param <N> |
| * The type of element in the tree |
| * @param provider |
| * The base provider of one of the trees, it will be used by the |
| * differential weighted tree provider to display the metrics and |
| * titles, etc.. It could be the provider of the second tree set, |
| * as it serves as the base values. |
| * @param first |
| * The first treeset to compare to |
| * @param second |
| * The second treeset to compare. |
| * @return A differential weighted tree provider wrapping the resulting tree |
| * set, or <code>null</code> if the 2 treesets have no elements in |
| * common |
| */ |
| public static <@NonNull N> @Nullable DifferentialWeightedTreeProvider<N> diffTreeSets(IWeightedTreeProvider<N, ?, WeightedTree<N>> provider, |
| IWeightedTreeSet<N, @NonNull ?, WeightedTree<N>> first, |
| IWeightedTreeSet<N, @NonNull ?, WeightedTree<N>> second) { |
| Collection<Pair<@NonNull ?, @NonNull ?>> pairedElements = pairElementsFromTrees(first, second); |
| if (pairedElements.isEmpty()) { |
| return null; |
| } |
| DifferentialWeightedTreeSet<N> treeSet = new DifferentialWeightedTreeSet<>(); |
| for (Pair<@NonNull ?, @NonNull ?> pair : pairedElements) { |
| Collection<WeightedTree<N>> trees1 = first.getTreesFor(pair.getFirst()); |
| Collection<WeightedTree<N>> trees2 = second.getTreesFor(pair.getSecond()); |
| Collection<DifferentialWeightedTree<N>> diffTrees = WeightedTreeUtils.diffTrees(trees1, trees2); |
| for (DifferentialWeightedTree<N> tree: diffTrees) { |
| treeSet.addWeightedTree(pair.getFirst(), tree); |
| } |
| } |
| |
| return new DifferentialWeightedTreeProvider<>(provider, treeSet); |
| } |
| |
| private static <@NonNull N> Collection<Pair<@NonNull ?, @NonNull ?>> pairElementsFromTrees(IWeightedTreeSet<N, @NonNull ?, WeightedTree<N>> first, IWeightedTreeSet<N, @NonNull ?, WeightedTree<N>> second) { |
| Collection<@NonNull ?> elements1 = first.getElements(); |
| Collection<@NonNull ?> elements2 = second.getElements(); |
| // If there is only one element and it is not a tree, pair it |
| if (elements1.size() == 1 && elements2.size() == 1) { |
| @NonNull Object element1 = elements1.iterator().next(); |
| @NonNull Object element2 = elements2.iterator().next(); |
| if (!(element1 instanceof ITree) && !(element2 instanceof ITree)) { |
| return ImmutableList.of(new Pair(element1, element2)); |
| } |
| } |
| |
| // Try to find equal elements in both trees |
| Collection<Pair<@NonNull ?, @NonNull ?>> pairedElements = pairEqualElements(elements1, elements2); |
| if (!pairedElements.isEmpty()) { |
| return pairedElements; |
| } |
| |
| // Compare ITree elements by names |
| pairedElements = pairSameNameElements(elements1, elements2); |
| return pairedElements; |
| } |
| |
| private static Collection<Pair<@NonNull ?, @NonNull ?>> pairEqualElements(Collection<@NonNull ?> elements1, Collection<@NonNull ?> elements2) { |
| List<Pair<@NonNull ?, @NonNull ?>> pairedElements = new ArrayList<>(); |
| for (@NonNull Object element1 : elements1) { |
| for (@NonNull Object element2 : elements2) { |
| if (element1.equals(element2)) { |
| pairedElements.add(new Pair<>(element1, element1)); |
| if (element1 instanceof ITree && element2 instanceof ITree) { |
| pairedElements.addAll(pairEqualElements(((ITree) element1).getChildren(), ((ITree) element2).getChildren())); |
| } |
| break; |
| } |
| } |
| } |
| return pairedElements; |
| } |
| |
| private static Collection<Pair<@NonNull ?, @NonNull ?>> pairSameNameElements(Collection<@NonNull ?> elements1, Collection<?> elements2) { |
| List<Pair<@NonNull ?, @NonNull ?>> pairedElements = new ArrayList<>(); |
| for (@NonNull Object element1 : elements1) { |
| if (!(element1 instanceof ITree)) { |
| continue; |
| } |
| for (@NonNull Object element2 : elements2) { |
| if (!(element2 instanceof ITree)) { |
| continue; |
| } |
| if (((ITree) element1).getName().equals(((ITree) element2).getName())) { |
| pairedElements.add(new Pair<>(element1, element2)); |
| pairedElements.addAll(pairSameNameElements(((ITree) element1).getChildren(), ((ITree) element2).getChildren())); |
| break; |
| } |
| } |
| } |
| return pairedElements; |
| } |
| |
| 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; |
| } |
| |
| } |
