You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2012/11/02 00:00:50 UTC
svn commit: r1404819 - in /lucene/dev/branches/branch_4x: ./ lucene/
lucene/core/ lucene/core/src/java/org/apache/lucene/util/fst/Util.java
lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
Author: mikemccand
Date: Thu Nov 1 23:00:50 2012
New Revision: 1404819
URL: http://svn.apache.org/viewvc?rev=1404819&view=rev
Log:
cleanup TopNSearcher: don't copy same comparator instance in the paths
Modified:
lucene/dev/branches/branch_4x/ (props changed)
lucene/dev/branches/branch_4x/lucene/ (props changed)
lucene/dev/branches/branch_4x/lucene/core/ (props changed)
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/fst/Util.java?rev=1404819&r1=1404818&r2=1404819&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/fst/Util.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/fst/Util.java Thu Nov 1 23:00:50 2012
@@ -232,16 +232,14 @@ public final class Util {
}
}
- private static class FSTPath<T> implements Comparable<FSTPath<T>> {
+ private static class FSTPath<T> {
public FST.Arc<T> arc;
public T cost;
public final IntsRef input;
- final Comparator<T> comparator;
- public FSTPath(T cost, FST.Arc<T> arc, Comparator<T> comparator, IntsRef input) {
+ public FSTPath(T cost, FST.Arc<T> arc, IntsRef input) {
this.arc = new FST.Arc<T>().copyFrom(arc);
this.cost = cost;
- this.comparator = comparator;
this.input = input;
}
@@ -249,12 +247,21 @@ public final class Util {
public String toString() {
return "input=" + input + " cost=" + cost;
}
+ }
+
+ /** Compares first by the provided comparator, and then
+ * tie breaks by path.input. */
+ private static class TieBreakByInputComparator<T> implements Comparator<FSTPath<T>> {
+ private final Comparator<T> comparator;
+ public TieBreakByInputComparator(Comparator<T> comparator) {
+ this.comparator = comparator;
+ }
@Override
- public int compareTo(FSTPath<T> other) {
- int cmp = comparator.compare(cost, other.cost);
+ public int compare(FSTPath<T> a, FSTPath<T> b) {
+ int cmp = comparator.compare(a.cost, b.cost);
if (cmp == 0) {
- return input.compareTo(other.input);
+ return a.input.compareTo(b.input);
} else {
return cmp;
}
@@ -283,7 +290,7 @@ public final class Util {
this.maxQueueDepth = maxQueueDepth;
this.comparator = comparator;
- queue = new TreeSet<FSTPath<T>>();
+ queue = new TreeSet<FSTPath<T>>(new TieBreakByInputComparator<T>(comparator));
}
// If back plus this arc is competitive then add to queue:
@@ -326,7 +333,7 @@ public final class Util {
System.arraycopy(path.input.ints, 0, newInput.ints, 0, path.input.length);
newInput.ints[path.input.length] = path.arc.label;
newInput.length = path.input.length+1;
- final FSTPath<T> newPath = new FSTPath<T>(cost, path.arc, comparator, newInput);
+ final FSTPath<T> newPath = new FSTPath<T>(cost, path.arc, newInput);
queue.add(newPath);
@@ -344,7 +351,7 @@ public final class Util {
startOutput = fst.outputs.getNoOutput();
}
- FSTPath<T> path = new FSTPath<T>(startOutput, node, comparator, input);
+ FSTPath<T> path = new FSTPath<T>(startOutput, node, input);
fst.readFirstTargetArc(node, path.arc, bytesReader);
//System.out.println("add start paths");
@@ -402,7 +409,7 @@ public final class Util {
//System.out.println(" empty string! cost=" + path.cost);
// Empty string!
path.input.length--;
- results.add(new MinResult<T>(path.input, path.cost, comparator));
+ results.add(new MinResult<T>(path.input, path.cost));
continue;
}
@@ -465,7 +472,7 @@ public final class Util {
//System.out.println(" done!: " + path);
T finalOutput = fst.outputs.add(path.cost, path.arc.output);
if (acceptResult(path.input, finalOutput)) {
- results.add(new MinResult<T>(path.input, finalOutput, comparator));
+ results.add(new MinResult<T>(path.input, finalOutput));
} else {
rejectCount++;
assert rejectCount + topN <= maxQueueDepth: "maxQueueDepth (" + maxQueueDepth + ") is too small for topN (" + topN + "): rejected " + rejectCount + " paths";
@@ -492,24 +499,12 @@ public final class Util {
/** Holds a single input (IntsRef) + output, returned by
* {@link #shortestPaths shortestPaths()}. */
- public final static class MinResult<T> implements Comparable<MinResult<T>> {
+ public final static class MinResult<T> {
public final IntsRef input;
public final T output;
- final Comparator<T> comparator;
- public MinResult(IntsRef input, T output, Comparator<T> comparator) {
+ public MinResult(IntsRef input, T output) {
this.input = input;
this.output = output;
- this.comparator = comparator;
- }
-
- @Override
- public int compareTo(MinResult<T> other) {
- int cmp = comparator.compare(output, other.output);
- if (cmp == 0) {
- return input.compareTo(other.input);
- } else {
- return cmp;
- }
}
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java?rev=1404819&r1=1404818&r2=1404819&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java Thu Nov 1 23:00:50 2012
@@ -1336,12 +1336,12 @@ public class TestFSTs extends LuceneTest
if (e.getKey().startsWith(prefix)) {
//System.out.println(" consider " + e.getKey());
matches.add(new Util.MinResult<Long>(Util.toIntsRef(new BytesRef(e.getKey().substring(prefix.length())), new IntsRef()),
- e.getValue() - prefixOutput, minLongComparator));
+ e.getValue() - prefixOutput));
}
}
assertTrue(matches.size() > 0);
- Collections.sort(matches);
+ Collections.sort(matches, new TieBreakByInputComparator(minLongComparator));
if (matches.size() > topN) {
matches.subList(topN, matches.size()).clear();
}
@@ -1355,7 +1355,24 @@ public class TestFSTs extends LuceneTest
}
}
}
-
+
+ private static class TieBreakByInputComparator<T> implements Comparator<Util.MinResult<T>> {
+ private final Comparator<T> comparator;
+ public TieBreakByInputComparator(Comparator<T> comparator) {
+ this.comparator = comparator;
+ }
+
+ @Override
+ public int compare(Util.MinResult<T> a, Util.MinResult<T> b) {
+ int cmp = comparator.compare(a.output, b.output);
+ if (cmp == 0) {
+ return a.input.compareTo(b.input);
+ } else {
+ return cmp;
+ }
+ }
+ }
+
// used by slowcompletor
class TwoLongs {
long a;
@@ -1440,13 +1457,12 @@ public class TestFSTs extends LuceneTest
if (e.getKey().startsWith(prefix)) {
//System.out.println(" consider " + e.getKey());
matches.add(new Util.MinResult<Pair<Long,Long>>(Util.toIntsRef(new BytesRef(e.getKey().substring(prefix.length())), new IntsRef()),
- outputs.newPair(e.getValue().a - prefixOutput.output1, e.getValue().b - prefixOutput.output2),
- minPairWeightComparator));
+ outputs.newPair(e.getValue().a - prefixOutput.output1, e.getValue().b - prefixOutput.output2)));
}
}
assertTrue(matches.size() > 0);
- Collections.sort(matches);
+ Collections.sort(matches, new TieBreakByInputComparator(minPairWeightComparator));
if (matches.size() > topN) {
matches.subList(topN, matches.size()).clear();
}