Skip to content

Commit

Permalink
inline metrics in tree
Browse files Browse the repository at this point in the history
  • Loading branch information
@jrfaller
jrfaller committed Apr 18, 2019
1 parent ce51999 commit beee67c
Show file tree
Hide file tree
Showing 36 changed files with 235 additions and 345 deletions.
12 changes: 0 additions & 12 deletions core/src/main/java/com/github/gumtreediff/matchers/Matcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -21,14 +21,8 @@
package com.github.gumtreediff.matchers;

import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.MetricProviderFactory;
import com.github.gumtreediff.tree.TreeMetricsProvider;
import org.atteo.classindex.IndexSubclasses;

import java.util.HashSet;
import java.util.Set;
import java.util.logging.Logger;

@IndexSubclasses
public abstract class Matcher {
protected final ITree src;
Expand All @@ -37,15 +31,9 @@ public abstract class Matcher {

protected final MappingStore mappings;

protected final TreeMetricsProvider srcMetrics;

protected final TreeMetricsProvider dstMetrics;

public Matcher(ITree src, ITree dst, MappingStore mappings) {
this.src = src;
this.dst = dst;
this.srcMetrics = MetricProviderFactory.computeTreeMetrics(src);
this.dstMetrics = MetricProviderFactory.computeTreeMetrics(dst);
this.mappings = mappings;
}

Expand Down
4 changes: 2 additions & 2 deletions core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/AbstractBottomUpMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -65,8 +65,8 @@ protected List<ITree> getDstCandidates(ITree src) {
}

protected void lastChanceMatch(ITree src, ITree dst) {
if (srcMetrics.get(src).size < AbstractBottomUpMatcher.SIZE_THRESHOLD
|| dstMetrics.get(dst).size < AbstractBottomUpMatcher.SIZE_THRESHOLD) {
if (src.getMetrics().size < AbstractBottomUpMatcher.SIZE_THRESHOLD
|| dst.getMetrics().size < AbstractBottomUpMatcher.SIZE_THRESHOLD) {
Matcher m = new ZsMatcher(src, dst, new MappingStore(src, dst));
m.match();
for (Mapping candidate : m.getMappings()) {
Expand Down
21 changes: 6 additions & 15 deletions ...src/main/java/com/github/gumtreediff/matchers/heuristic/gt/AbstractMappingComparator.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -22,19 +22,13 @@
import com.github.gumtreediff.matchers.Mapping;
import com.github.gumtreediff.matchers.MappingStore;
import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;

import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public abstract class AbstractMappingComparator implements Comparator<Mapping> {

protected TreeMetricsProvider srcMetrics;

protected TreeMetricsProvider dstMetrics;

protected List<Mapping> ambiguousMappings;

protected Map<Mapping, Double> similarities = new HashMap<>();
Expand All @@ -43,27 +37,24 @@ public abstract class AbstractMappingComparator implements Comparator<Mapping> {

protected MappingStore mappings;

public AbstractMappingComparator(List<Mapping> ambiguousMappings, MappingStore mappings,
TreeMetricsProvider srcMetrics,
TreeMetricsProvider dstMetrics, int maxTreeSize) {
public AbstractMappingComparator(List<Mapping> ambiguousMappings,
MappingStore mappings, int maxTreeSize) {
this.maxTreeSize = maxTreeSize;
this.mappings = mappings;
this.ambiguousMappings = ambiguousMappings;
this.srcMetrics = srcMetrics;
this.dstMetrics = dstMetrics;
}

@Override
public int compare(Mapping m1, Mapping m2) {
if (similarities.get(m2).compareTo(similarities.get(m1)) != 0) {
return Double.compare(similarities.get(m2), similarities.get(m1));
}
int srcPos = srcMetrics.get(m1.first).position;
int dstPos = srcMetrics.get(m2.first).position;
int srcPos = m1.first.getMetrics().position;
int dstPos = m2.first.getMetrics().position;
if (srcPos != dstPos) {
return Integer.compare(srcPos, dstPos);
}
return Integer.compare(dstMetrics.get(m1.second).position, dstMetrics.get(m2.second).position);
return Integer.compare(m1.second.getMetrics().position, m2.second.getMetrics().position);
}

protected abstract double similarity(ITree src, ITree dst);
Expand All @@ -78,7 +69,7 @@ protected double posInParentSimilarity(ITree src, ITree dst) {
}

protected double numberingSimilarity(ITree src, ITree dst) {
return 1D - ((double) Math.abs(srcMetrics.get(src).position - dstMetrics.get(dst).position)
return 1D - ((double) Math.abs(src.getMetrics().position - dst.getMetrics().position)
/ (double) maxTreeSize);
}

Expand Down
23 changes: 9 additions & 14 deletions core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/AbstractSubtreeMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -24,7 +24,6 @@
import com.github.gumtreediff.matchers.MappingStore;
import com.github.gumtreediff.matchers.MultiMappingStore;
import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;

import java.util.ArrayList;
import java.util.List;
Expand All @@ -51,8 +50,8 @@ private void popLarger(PriorityTreeList srcTrees, PriorityTreeList dstTrees) {
public void match() {
MultiMappingStore multiMappings = new MultiMappingStore();

PriorityTreeList srcTrees = new PriorityTreeList(src, srcMetrics);
PriorityTreeList dstTrees = new PriorityTreeList(dst, dstMetrics);
PriorityTreeList srcTrees = new PriorityTreeList(src);
PriorityTreeList dstTrees = new PriorityTreeList(dst);

while (srcTrees.peekHeight() != -1 && dstTrees.peekHeight() != -1) {
while (srcTrees.peekHeight() != dstTrees.peekHeight())
Expand Down Expand Up @@ -100,13 +99,13 @@ protected double sim(ITree src, ITree dst) {
int maxDstPos = (dst.isRoot()) ? 1 : dst.getParent().getChildren().size();
int maxPosDiff = Math.max(maxSrcPos, maxDstPos);
double pos = 1D - ((double) Math.abs(posSrc - posDst) / (double) maxPosDiff);
double po = 1D - ((double) Math.abs(srcMetrics.get(src).position - dstMetrics.get(dst).position)
double po = 1D - ((double) Math.abs(src.getMetrics().position - dst.getMetrics().position)
/ (double) this.getMaxTreeSize());
return 100 * jaccard + 10 * pos + po;
}

protected int getMaxTreeSize() {
return Math.max(srcMetrics.get(src).size, dstMetrics.get(dst).size);
return Math.max(src.getMetrics().size, dst.getMetrics().size);
}

protected void retainBestMapping(List<Mapping> mappingList, Set<ITree> srcIgnored, Set<ITree> dstIgnored) {
Expand All @@ -121,30 +120,26 @@ protected void retainBestMapping(List<Mapping> mappingList, Set<ITree> srcIgnore
}

private static class PriorityTreeList {

private List<ITree>[] trees;

private TreeMetricsProvider treeMetrics;

private int maxHeight;

private int currentIdx;

@SuppressWarnings("unchecked")
public PriorityTreeList(ITree tree, TreeMetricsProvider treeMetrics) {
this.treeMetrics = treeMetrics;
int listSize = treeMetrics.get(tree).height - MIN_HEIGHT + 1;
public PriorityTreeList(ITree tree) {
int listSize = tree.getMetrics().height - MIN_HEIGHT + 1;
if (listSize < 0)
listSize = 0;
if (listSize == 0)
currentIdx = -1;
trees = (List<ITree>[]) new ArrayList[listSize];
maxHeight = treeMetrics.get(tree).height;
maxHeight = tree.getMetrics().height;
addTree(tree);
}

private int idx(ITree tree) {
return idx(treeMetrics.get(tree).height);
return idx(tree.getMetrics().height);
}

private int idx(int height) {
Expand All @@ -156,7 +151,7 @@ private int height(int idx) {
}

private void addTree(ITree tree) {
if (treeMetrics.get(tree).height >= MIN_HEIGHT) {
if (tree.getMetrics().height >= MIN_HEIGHT) {
int idx = idx(tree);
if (trees[idx] == null) trees[idx] = new ArrayList<>();
trees[idx].add(tree);
Expand Down
14 changes: 7 additions & 7 deletions core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/CliqueSubtreeMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -39,7 +39,7 @@ public CliqueSubtreeMatcher(ITree src, ITree dst, MappingStore store) {
public void filterMappings(MultiMappingStore multiMappings) {
TIntObjectHashMap<Pair<List<ITree>, List<ITree>>> cliques = new TIntObjectHashMap<>();
for (Mapping m : multiMappings) {
int hash = srcMetrics.get(m.first).hash;
int hash = m.first.getMetrics().hash;
if (!cliques.containsKey(hash))
cliques.put(hash, new Pair<>(new ArrayList<>(), new ArrayList<>()));
cliques.get(hash).first.add(m.first);
Expand Down Expand Up @@ -95,11 +95,11 @@ public int compare(Pair<List<ITree>, List<ITree>> l1,
private int minDepth(Pair<List<ITree>, List<ITree>> trees) {
int depth = Integer.MAX_VALUE;
for (ITree t : trees.first)
if (depth > srcMetrics.get(t).depth)
depth = srcMetrics.get(t).depth;
if (depth > t.getMetrics().depth)
depth = t.getMetrics().depth;
for (ITree t : trees.second)
if (depth > dstMetrics.get(t).depth)
depth = dstMetrics.get(t).depth;
if (depth > t.getMetrics().depth)
depth = t.getMetrics().depth;
return depth;
}

Expand Down Expand Up @@ -153,8 +153,8 @@ protected double[] sims(ITree src, ITree dst) {
double[] sims = new double[4];
sims[0] = jaccardSimilarity(src.getParent(), dst.getParent());
sims[1] = src.positionInParent() - dst.positionInParent();
sims[2] = srcMetrics.get(src).position - dstMetrics.get(dst).position;
sims[3] = srcMetrics.get(src).position;
sims[2] = src.getMetrics().position - dst.getMetrics().position;
sims[3] = src.getMetrics().position;
return sims;
}

Expand Down
2 changes: 1 addition & 1 deletion core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/GreedySubtreeMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -55,7 +55,7 @@ else if (!ignored.contains(src)) {
Set<ITree> srcIgnored = new HashSet<>();
Set<ITree> dstIgnored = new HashSet<>();
Collections.sort(ambiguousList,
new SiblingsMappingComparator(ambiguousList, mappings, srcMetrics, dstMetrics, getMaxTreeSize()));
new SiblingsMappingComparator(ambiguousList, mappings, getMaxTreeSize()));

// Select the best ambiguous mappings
retainBestMapping(ambiguousList, srcIgnored, dstIgnored);
Expand Down
6 changes: 2 additions & 4 deletions .../src/main/java/com/github/gumtreediff/matchers/heuristic/gt/ParentsMappingComparator.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -22,17 +22,15 @@
import com.github.gumtreediff.matchers.Mapping;
import com.github.gumtreediff.matchers.MappingStore;
import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;
import com.github.gumtreediff.utils.StringAlgorithms;

import java.util.*;

public final class ParentsMappingComparator extends AbstractMappingComparator {

public ParentsMappingComparator(List<Mapping> ambiguousMappings, MappingStore mappings,
TreeMetricsProvider srcMetrics,
TreeMetricsProvider dstMetrics, int maxTreeSize) {
super(ambiguousMappings, mappings, srcMetrics, dstMetrics, maxTreeSize);
int maxTreeSize) {
super(ambiguousMappings, mappings, maxTreeSize);
for (Mapping ambiguousMapping: ambiguousMappings)
similarities.put(ambiguousMapping, similarity(ambiguousMapping.first, ambiguousMapping.second));
}
Expand Down
6 changes: 2 additions & 4 deletions ...src/main/java/com/github/gumtreediff/matchers/heuristic/gt/SiblingsMappingComparator.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -22,7 +22,6 @@
import com.github.gumtreediff.matchers.Mapping;
import com.github.gumtreediff.matchers.MappingStore;
import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;

import java.util.*;

Expand All @@ -33,9 +32,8 @@ public final class SiblingsMappingComparator extends AbstractMappingComparator {
private Map<ITree, Set<ITree>> dstDescendants = new HashMap<>();

public SiblingsMappingComparator(List<Mapping> ambiguousMappings, MappingStore mappings,
TreeMetricsProvider srcMetrics,
TreeMetricsProvider dstMetrics, int maxTreeSize) {
super(ambiguousMappings, mappings, srcMetrics, dstMetrics, maxTreeSize);
int maxTreeSize) {
super(ambiguousMappings, mappings, maxTreeSize);
for (Mapping ambiguousMapping: ambiguousMappings)
similarities.put(ambiguousMapping, similarity(ambiguousMapping.first, ambiguousMapping.second));
}
Expand Down
2 changes: 1 addition & 1 deletion core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/SimpleBottomUpMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -55,7 +55,7 @@ public void match() {
for (ITree cand: candidates) {
double sim = SimilarityMetrics.jaccardSimilarity(t, cand, mappings);
if (sim > max && sim >= SIM_THRESHOLD) {
if (srcMetrics.get(t).depth == srcMetrics.get(cand).depth) {
if (t.getMetrics().depth == cand.getMetrics().depth) {
lastChanceMatch(t, best);
mappings.addMapping(t, best);
return;
Expand Down
7 changes: 2 additions & 5 deletions core/src/main/java/com/github/gumtreediff/matchers/optimal/rted/InfoTree.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -16,7 +16,6 @@
package com.github.gumtreediff.matchers.optimal.rted;

import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;

import java.util.*;

Expand All @@ -29,7 +28,6 @@
@SuppressWarnings({"rawtypes", "unchecked"})
public class InfoTree {
private ITree inputTree;
private TreeMetricsProvider treeMetrics;

private static final byte LEFT = 0;
private static final byte RIGHT = 1;
Expand Down Expand Up @@ -97,10 +95,9 @@ public static void main(String[] args) {
* @param aInputTree an LblTree object
* @param aLd a LabelDictionary object
*/
public InfoTree(ITree aInputTree, TreeMetricsProvider treeMetrics, LabelDictionary aLd) {
public InfoTree(ITree aInputTree, LabelDictionary aLd) {
this.inputTree = aInputTree;
this.treeMetrics = treeMetrics;
treeSize = treeMetrics.get(inputTree).size;
treeSize = inputTree.getMetrics().size;
this.info = new int[16][treeSize];
Arrays.fill(info[POST2_PARENT], -1);
Arrays.fill(info[POST2_MIN_KR], -1);
Expand Down
7 changes: 3 additions & 4 deletions core/src/main/java/com/github/gumtreediff/matchers/optimal/rted/RtedAlgorithm.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -18,7 +18,6 @@
import java.util.*;

import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;


/**
Expand Down Expand Up @@ -119,10 +118,10 @@ public double nonNormalizedTreeDist() {
return computeDistUsingStrArray(it1, it2);
}

public void init(ITree src, TreeMetricsProvider srcMetrics, ITree dst, TreeMetricsProvider dstMetrics) {
public void init(ITree src, ITree dst) {
ld = new LabelDictionary();
it1 = new InfoTree(src, srcMetrics, ld);
it2 = new InfoTree(dst, dstMetrics, ld);
it1 = new InfoTree(src, ld);
it2 = new InfoTree(dst, ld);
size1 = it1.getSize();
size2 = it2.getSize();
ij = new int[Math.max(size1, size2)][Math.max(size1, size2)];
Expand Down
2 changes: 1 addition & 1 deletion core/src/main/java/com/github/gumtreediff/matchers/optimal/rted/RtedMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -37,7 +37,7 @@ public RtedMatcher(ITree src, ITree dst, MappingStore store) {
@Override
public void match() {
RtedAlgorithm a = new RtedAlgorithm(1D, 1D, 1D);
a.init(src, srcMetrics, dst, dstMetrics);
a.init(src, dst);
a.computeOptimalStrategy();
a.nonNormalizedTreeDist();
ArrayDeque<int[]> arrayMappings = a.computeEditMapping();
Expand Down
10 changes: 4 additions & 6 deletions core/src/main/java/com/github/gumtreediff/matchers/optimal/zs/ZsMatcher.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -23,13 +23,11 @@
import com.github.gumtreediff.matchers.MappingStore;
import com.github.gumtreediff.matchers.Matcher;
import com.github.gumtreediff.tree.ITree;
import com.github.gumtreediff.tree.TreeMetricsProvider;
import org.simmetrics.StringMetrics;

import java.util.*;

public class ZsMatcher extends Matcher {

private ZsTree zsSrc;
private ZsTree zsDst;

Expand All @@ -46,8 +44,8 @@ private static ITree getFirstLeaf(ITree t) {

public ZsMatcher(ITree src, ITree dst, MappingStore store) {
super(src, dst, store);
this.zsSrc = new ZsTree(src, srcMetrics);
this.zsDst = new ZsTree(dst, dstMetrics);
this.zsSrc = new ZsTree(src);
this.zsDst = new ZsTree(dst);
}

private double[][] computeTreeDist() {
Expand Down Expand Up @@ -189,9 +187,9 @@ private static final class ZsTree {

private int[] kr;

private ZsTree(ITree t, TreeMetricsProvider treeMetrics) {
private ZsTree(ITree t) {
this.start = 0;
this.nodeCount = treeMetrics.get(t).size;
this.nodeCount = t.getMetrics().size;
this.leafCount = 0;
this.llds = new int[start + nodeCount];
this.labels = new ITree[start + nodeCount];
Expand Down
Loading

0 comments on commit beee67c

Please sign in to comment.