You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by th...@apache.org on 2025/07/03 15:04:47 UTC
(lucene) branch main updated: Change PriorityQueue to use LessThan interface by default (#14873)
This is an automated email from the ASF dual-hosted git repository.
thecoop pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 39549329509 Change PriorityQueue to use LessThan interface by default (#14873)
39549329509 is described below
commit 395493295090e19c4f4ce2f5e9df0c2dfd7e5481
Author: Simon Cooper <si...@elastic.co>
AuthorDate: Thu Jul 3 16:04:41 2025 +0100
Change PriorityQueue to use LessThan interface by default (#14873)
Rather than overriding an abstract method, pass in an interface implementation as a more extensible way of specifying the comparison logic
---
lucene/CHANGES.txt | 3 +
.../org/apache/lucene/index/MultiTermsEnum.java | 7 +-
.../apache/lucene/search/FieldValueHitQueue.java | 150 +++++++++------------
.../java/org/apache/lucene/search/HitQueue.java | 4 +-
.../src/java/org/apache/lucene/search/TopDocs.java | 26 ++--
.../apache/lucene/search/TopFieldCollector.java | 4 +-
.../lucene/search/TopFieldCollectorManager.java | 4 +-
.../java/org/apache/lucene/util/PriorityQueue.java | 73 ++++------
.../org/apache/lucene/util/TestPriorityQueue.java | 29 +---
.../apache/lucene/facet/TopOrdAndNumberQueue.java | 7 +-
.../lucene/search/spell/SuggestWordQueue.java | 14 +-
11 files changed, 119 insertions(+), 202 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index d0958246ce5..f4115ba9874 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -26,6 +26,9 @@ API Changes
to ValueQueryNode. Made existing implementations public in all classes which
implement ValueQueryNode. (Peter Barna, Adam Schwartz)
+* GITHUB#14873: Change PriorityQueue to take a LessThan interface implementation
+ in its constructor rather than overriding the lessThan abstract method (Simon Cooper)
+
New Features
---------------------
* GITHUB#14097: Binary partitioning merge policy over float-valued vector field. (Mike Sokolov)
diff --git a/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java b/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java
index 420c5847481..8449fbacae7 100644
--- a/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java
+++ b/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java
@@ -375,15 +375,10 @@ public final class MultiTermsEnum extends BaseTermsEnum {
final int[] stack;
TermMergeQueue(int size) {
- super(size);
+ super(size, (a, b) -> a.compareTermTo(b) < 0);
this.stack = new int[size];
}
- @Override
- protected boolean lessThan(TermsEnumWithSlice termsA, TermsEnumWithSlice termsB) {
- return termsA.compareTermTo(termsB) < 0;
- }
-
/**
* Add the {@link #top()} slice as well as all slices that are positioned on the same term to
* {@code tops} and return how many of them there are.
diff --git a/lucene/core/src/java/org/apache/lucene/search/FieldValueHitQueue.java b/lucene/core/src/java/org/apache/lucene/search/FieldValueHitQueue.java
index 187afa6009d..104b438a721 100644
--- a/lucene/core/src/java/org/apache/lucene/search/FieldValueHitQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/search/FieldValueHitQueue.java
@@ -27,8 +27,7 @@ import org.apache.lucene.util.PriorityQueue;
* @since 2.9
* @see IndexSearcher#search(Query,int,Sort)
*/
-public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry>
- extends PriorityQueue<T> {
+public class FieldValueHitQueue<T extends FieldValueHitQueue.Entry> extends PriorityQueue<T> {
/** Extension of ScoreDoc to also store the {@link FieldComparator} slot. */
public static class Entry extends ScoreDoc {
@@ -45,41 +44,32 @@ public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry>
}
}
- /**
- * An implementation of {@link FieldValueHitQueue} which is optimized in case there is just one
- * comparator.
- */
- private static final class OneComparatorFieldValueHitQueue<T extends FieldValueHitQueue.Entry>
- extends FieldValueHitQueue<T> {
-
- private final int oneReverseMul;
- private final FieldComparator<?> oneComparator;
+ private static class EntryLessThan implements LessThan<Entry> {
- public OneComparatorFieldValueHitQueue(SortField[] fields, int size) {
- super(fields, size);
+ // All these are required by this class's API - need to return arrays.
+ // Therefore, even in the case of a single comparator, store an array
+ // anyway.
+ protected final FieldComparator<?>[] comparators;
+ protected final int[] reverseMul;
- assert fields.length == 1;
- oneComparator = comparators[0];
- oneReverseMul = reverseMul[0];
+ private EntryLessThan(FieldComparator<?>[] comparators, int[] reverseMul) {
+ assert comparators.length == reverseMul.length;
+ this.comparators = comparators;
+ this.reverseMul = reverseMul;
}
- /**
- * Returns whether <code>hitA</code> is less relevant than <code>hitB</code>.
- *
- * @param hitA Entry
- * @param hitB Entry
- * @return <code>true</code> if document <code>hitA</code> should be sorted after document
- * <code>hitB</code>.
- */
@Override
- protected boolean lessThan(final Entry hitA, final Entry hitB) {
-
+ public boolean lessThan(Entry hitA, Entry hitB) {
assert hitA != hitB;
assert hitA.slot != hitB.slot;
- final int c = oneReverseMul * oneComparator.compare(hitA.slot, hitB.slot);
- if (c != 0) {
- return c > 0;
+ int numComparators = comparators.length;
+ for (int i = 0; i < numComparators; ++i) {
+ final int c = reverseMul[i] * comparators[i].compare(hitA.slot, hitB.slot);
+ if (c != 0) {
+ // Short circuit
+ return c > 0;
+ }
}
// avoid random sort order that could lead to duplicates (bug #31241):
@@ -87,30 +77,27 @@ public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry>
}
}
- /**
- * An implementation of {@link FieldValueHitQueue} which is optimized in case there is more than
- * one comparator.
- */
- private static final class MultiComparatorsFieldValueHitQueue<T extends FieldValueHitQueue.Entry>
- extends FieldValueHitQueue<T> {
+ // optimisation for the case when there's only one comparator
+ private static class OneComparatorEntryLessThan extends EntryLessThan {
+ private final int oneReverseMul;
+ private final FieldComparator<?> oneComparator;
+
+ private OneComparatorEntryLessThan(FieldComparator<?>[] comparators, int[] reverseMul) {
+ super(comparators, reverseMul);
- public MultiComparatorsFieldValueHitQueue(SortField[] fields, int size) {
- super(fields, size);
+ assert comparators.length == 1;
+ oneComparator = comparators[0];
+ oneReverseMul = reverseMul[0];
}
@Override
- protected boolean lessThan(final Entry hitA, final Entry hitB) {
-
+ public boolean lessThan(Entry hitA, Entry hitB) {
assert hitA != hitB;
assert hitA.slot != hitB.slot;
- int numComparators = comparators.length;
- for (int i = 0; i < numComparators; ++i) {
- final int c = reverseMul[i] * comparators[i].compare(hitA.slot, hitB.slot);
- if (c != 0) {
- // Short circuit
- return c > 0;
- }
+ final int c = oneReverseMul * oneComparator.compare(hitA.slot, hitB.slot);
+ if (c != 0) {
+ return c > 0;
}
// avoid random sort order that could lead to duplicates (bug #31241):
@@ -118,29 +105,18 @@ public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry>
}
}
+ /** Stores the sort criteria being used. */
+ private final SortField[] fields;
+
+ private final EntryLessThan lessThan;
+
// prevent instantiation and extension.
- private FieldValueHitQueue(SortField[] fields, int size) {
- super(size);
+ private FieldValueHitQueue(SortField[] fields, int size, EntryLessThan lessThan) {
+ super(size, lessThan);
// When we get here, fields.length is guaranteed to be > 0, therefore no
// need to check it again.
-
- // All these are required by this class's API - need to return arrays.
- // Therefore, even in the case of a single comparator, create an array
- // anyway.
this.fields = fields;
- int numComparators = fields.length;
- comparators = new FieldComparator<?>[numComparators];
- reverseMul = new int[numComparators];
- for (int i = 0; i < numComparators; ++i) {
- SortField field = fields[i];
- reverseMul[i] = field.reverse ? -1 : 1;
- comparators[i] =
- field.getComparator(
- size,
- i == 0
- ? (numComparators > 1 ? Pruning.GREATER_THAN : Pruning.GREATER_THAN_OR_EQUAL_TO)
- : Pruning.NONE);
- }
+ this.lessThan = lessThan;
}
/**
@@ -160,38 +136,44 @@ public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry>
throw new IllegalArgumentException("Sort must contain at least one field");
}
- if (fields.length == 1) {
- return new OneComparatorFieldValueHitQueue<>(fields, size);
- } else {
- return new MultiComparatorsFieldValueHitQueue<>(fields, size);
+ int numComparators = fields.length;
+ FieldComparator<?>[] comparators = new FieldComparator<?>[numComparators];
+ int[] reverseMul = new int[numComparators];
+ for (int i = 0; i < numComparators; ++i) {
+ SortField field = fields[i];
+ reverseMul[i] = field.reverse ? -1 : 1;
+ comparators[i] =
+ field.getComparator(
+ size,
+ i == 0
+ ? (numComparators > 1 ? Pruning.GREATER_THAN : Pruning.GREATER_THAN_OR_EQUAL_TO)
+ : Pruning.NONE);
}
+
+ return new FieldValueHitQueue<>(
+ fields,
+ size,
+ fields.length == 1
+ ? new OneComparatorEntryLessThan(comparators, reverseMul)
+ : new EntryLessThan(comparators, reverseMul));
}
public FieldComparator<?>[] getComparators() {
- return comparators;
+ return lessThan.comparators;
}
public int[] getReverseMul() {
- return reverseMul;
+ return lessThan.reverseMul;
}
public LeafFieldComparator[] getComparators(LeafReaderContext context) throws IOException {
- LeafFieldComparator[] comparators = new LeafFieldComparator[this.comparators.length];
+ LeafFieldComparator[] comparators = new LeafFieldComparator[lessThan.comparators.length];
for (int i = 0; i < comparators.length; ++i) {
- comparators[i] = this.comparators[i].getLeafComparator(context);
+ comparators[i] = lessThan.comparators[i].getLeafComparator(context);
}
return comparators;
}
- /** Stores the sort criteria being used. */
- protected final SortField[] fields;
-
- protected final FieldComparator<?>[] comparators;
- protected final int[] reverseMul;
-
- @Override
- protected abstract boolean lessThan(final Entry a, final Entry b);
-
/**
* Given a queue Entry, creates a corresponding FieldDoc that contains the values used to sort the
* given document. These values are not the raw values out of the index, but the internal
@@ -203,10 +185,10 @@ public abstract class FieldValueHitQueue<T extends FieldValueHitQueue.Entry>
* @see IndexSearcher#search(Query,int,Sort)
*/
FieldDoc fillFields(final Entry entry) {
- final int n = comparators.length;
+ final int n = lessThan.comparators.length;
final Object[] fields = new Object[n];
for (int i = 0; i < n; ++i) {
- fields[i] = comparators[i].value(entry.slot);
+ fields[i] = lessThan.comparators[i].value(entry.slot);
}
// if (maxscore > 1.0f) doc.score /= maxscore; // normalize scores
return new FieldDoc(entry.doc, entry.score, fields);
diff --git a/lucene/core/src/java/org/apache/lucene/search/HitQueue.java b/lucene/core/src/java/org/apache/lucene/search/HitQueue.java
index edb7d518e7a..a2032991f4b 100644
--- a/lucene/core/src/java/org/apache/lucene/search/HitQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/search/HitQueue.java
@@ -62,6 +62,7 @@ public final class HitQueue extends PriorityQueue<ScoreDoc> {
public HitQueue(int size, boolean prePopulate) {
super(
size,
+ HitQueue::lessThan,
prePopulate
? () -> {
// Always set the doc Id to MAX_VALUE so that it won't be favored by
@@ -72,8 +73,7 @@ public final class HitQueue extends PriorityQueue<ScoreDoc> {
: () -> null);
}
- @Override
- protected final boolean lessThan(ScoreDoc hitA, ScoreDoc hitB) {
+ private static boolean lessThan(ScoreDoc hitA, ScoreDoc hitB) {
int cmp = Float.compare(hitA.score, hitB.score);
if (cmp == 0) {
return hitA.doc > hitB.doc;
diff --git a/lucene/core/src/java/org/apache/lucene/search/TopDocs.java b/lucene/core/src/java/org/apache/lucene/search/TopDocs.java
index d9f864b9bad..e6157ba1d4f 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TopDocs.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TopDocs.java
@@ -92,14 +92,12 @@ public class TopDocs {
return value < 0;
}
- // Specialized MergeSortQueue that just merges by
- // relevance score, descending:
- private static class ScoreMergeSortQueue extends PriorityQueue<ShardRef> {
- final ScoreDoc[][] shardHits;
- final Comparator<ScoreDoc> tieBreakerComparator;
+ // LessThan that just sorts by relevance score, descending:
+ private static class ScoreLessThan implements PriorityQueue.LessThan<ShardRef> {
+ private final ScoreDoc[][] shardHits;
+ private final Comparator<ScoreDoc> tieBreakerComparator;
- public ScoreMergeSortQueue(TopDocs[] shardHits, Comparator<ScoreDoc> tieBreakerComparator) {
- super(shardHits.length);
+ public ScoreLessThan(TopDocs[] shardHits, Comparator<ScoreDoc> tieBreakerComparator) {
this.shardHits = new ScoreDoc[shardHits.length][];
for (int shardIDX = 0; shardIDX < shardHits.length; shardIDX++) {
this.shardHits[shardIDX] = shardHits[shardIDX].scoreDocs;
@@ -123,16 +121,14 @@ public class TopDocs {
}
}
- @SuppressWarnings({"rawtypes", "unchecked"})
- private static class MergeSortQueue extends PriorityQueue<ShardRef> {
+ private static class ShardRefLessThan implements PriorityQueue.LessThan<ShardRef> {
// These are really FieldDoc instances:
final ScoreDoc[][] shardHits;
final FieldComparator<?>[] comparators;
final int[] reverseMul;
final Comparator<ScoreDoc> tieBreaker;
- public MergeSortQueue(Sort sort, TopDocs[] shardHits, Comparator<ScoreDoc> tieBreaker) {
- super(shardHits.length);
+ private ShardRefLessThan(Sort sort, TopDocs[] shardHits, Comparator<ScoreDoc> tieBreaker) {
this.shardHits = new ScoreDoc[shardHits.length][];
this.tieBreaker = tieBreaker;
for (int shardIDX = 0; shardIDX < shardHits.length; shardIDX++) {
@@ -159,7 +155,7 @@ public class TopDocs {
}
final SortField[] sortFields = sort.getSort();
- comparators = new FieldComparator[sortFields.length];
+ comparators = new FieldComparator<?>[sortFields.length];
reverseMul = new int[sortFields.length];
for (int compIDX = 0; compIDX < sortFields.length; compIDX++) {
final SortField sortField = sortFields[compIDX];
@@ -170,6 +166,7 @@ public class TopDocs {
// Returns true if first is < second
@Override
+ @SuppressWarnings({"rawtypes", "unchecked"})
public boolean lessThan(ShardRef first, ShardRef second) {
assert first != second;
final FieldDoc firstFD = (FieldDoc) shardHits[first.shardIndex][first.hitIndex];
@@ -283,9 +280,10 @@ public class TopDocs {
final PriorityQueue<ShardRef> queue;
if (sort == null) {
- queue = new ScoreMergeSortQueue(shardHits, tieBreaker);
+ queue = new PriorityQueue<>(shardHits.length, new ScoreLessThan(shardHits, tieBreaker));
} else {
- queue = new MergeSortQueue(sort, shardHits, tieBreaker);
+ queue =
+ new PriorityQueue<>(shardHits.length, new ShardRefLessThan(sort, shardHits, tieBreaker));
}
long totalHitCount = 0;
diff --git a/lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java b/lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java
index 1b24e37c004..568ebf8cf01 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java
@@ -241,7 +241,7 @@ public abstract class TopFieldCollector extends TopDocsCollector<Entry> {
this.queue = queue;
this.after = after;
- FieldComparator<?>[] comparators = queue.comparators;
+ FieldComparator<?>[] comparators = queue.getComparators();
// Tell all comparators their top value:
for (int i = 0; i < comparators.length; i++) {
@SuppressWarnings("unchecked")
@@ -335,7 +335,7 @@ public abstract class TopFieldCollector extends TopDocsCollector<Entry> {
this.totalHitsThreshold = Math.max(totalHitsThreshold, numHits);
this.numComparators = pq.getComparators().length;
this.firstComparator = pq.getComparators()[0];
- int reverseMul = pq.reverseMul[0];
+ int reverseMul = pq.getReverseMul()[0];
if (firstComparator.getClass().equals(FieldComparator.RelevanceComparator.class)
&& reverseMul == 1 // if the natural sort is preserved (sort by descending relevance)
diff --git a/lucene/core/src/java/org/apache/lucene/search/TopFieldCollectorManager.java b/lucene/core/src/java/org/apache/lucene/search/TopFieldCollectorManager.java
index 1f37a82864e..c62e9dc9f25 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TopFieldCollectorManager.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TopFieldCollectorManager.java
@@ -144,8 +144,8 @@ public class TopFieldCollectorManager implements CollectorManager<TopFieldCollec
// to enable some optimizations for skipping over non-competitive documents
// We can't set single sort when the `after` parameter is non-null as it's
// an implicit sort over the document id.
- if (queue.comparators.length == 1) {
- queue.comparators[0].setSingleSort();
+ if (queue.getComparators().length == 1) {
+ queue.getComparators()[0].setSingleSort();
}
collector =
new TopFieldCollector.SimpleFieldCollector(
diff --git a/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java b/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
index 8b31baed9e9..de4f8e81265 100644
--- a/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
@@ -30,13 +30,13 @@ import java.util.function.Supplier;
* cost implemented here is linear.
*
* <p><b>NOTE</b>: This class pre-allocates an array of length {@code maxSize+1} and pre-fills it
- * with elements if instantiated via the {@link #PriorityQueue(int,Supplier)} constructor.
+ * with elements if instantiated via the {@link #PriorityQueue(int,LessThan,Supplier)} constructor.
*
* <p><b>NOTE</b>: Iteration order is not specified.
*
* @lucene.internal
*/
-public abstract class PriorityQueue<T> implements Iterable<T> {
+public class PriorityQueue<T> implements Iterable<T> {
/** Represents a {@code <} operation, which is less prescriptive than {@link Comparator} */
@FunctionalInterface
@@ -46,54 +46,36 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
/** Create a {@code PriorityQueue} that orders elements using the specified {@code lessThan} */
public static <T> PriorityQueue<T> usingLessThan(int maxSize, LessThan<? super T> lessThan) {
- return new PriorityQueue<>(maxSize) {
- @Override
- protected boolean lessThan(T a, T b) {
- return lessThan.lessThan(a, b);
- }
- };
+ return new PriorityQueue<>(maxSize, lessThan);
}
/** Create a {@code PriorityQueue} that orders elements using the specified {@code lessThan} */
public static <T> PriorityQueue<T> usingLessThan(
int maxSize, Supplier<T> sentinelObjectSupplier, LessThan<? super T> lessThan) {
- return new PriorityQueue<>(maxSize, sentinelObjectSupplier) {
- @Override
- protected boolean lessThan(T a, T b) {
- return lessThan.lessThan(a, b);
- }
- };
+ return new PriorityQueue<>(maxSize, lessThan, sentinelObjectSupplier);
}
/** Create a {@code PriorityQueue} that orders elements using the specified {@code comparator} */
public static <T> PriorityQueue<T> usingComparator(
int maxSize, Comparator<? super T> comparator) {
- return new PriorityQueue<>(maxSize) {
- @Override
- protected boolean lessThan(T a, T b) {
- return comparator.compare(a, b) < 0;
- }
- };
+ return new PriorityQueue<>(maxSize, (a, b) -> comparator.compare(a, b) < 0);
}
/** Create a {@code PriorityQueue} that orders elements using the specified {@code comparator} */
public static <T> PriorityQueue<T> usingComparator(
int maxSize, Supplier<T> sentinelObjectSupplier, Comparator<? super T> comparator) {
- return new PriorityQueue<>(maxSize, sentinelObjectSupplier) {
- @Override
- protected boolean lessThan(T a, T b) {
- return comparator.compare(a, b) < 0;
- }
- };
+ return new PriorityQueue<>(
+ maxSize, (a, b) -> comparator.compare(a, b) < 0, sentinelObjectSupplier);
}
private int size = 0;
private final int maxSize;
private final T[] heap;
+ private final LessThan<? super T> lessThan;
- /** Create an empty priority queue of the configured size. */
- public PriorityQueue(int maxSize) {
- this(maxSize, () -> null);
+ /** Create an empty priority queue of the configured size using the specified {@link LessThan}. */
+ public PriorityQueue(int maxSize, LessThan<? super T> lessThan) {
+ this(maxSize, lessThan, () -> null);
}
/**
@@ -111,7 +93,7 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
* recommended:
*
* <pre class="prettyprint">
- * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
+ * PriorityQueue<MyObject> pq = new PriorityQueue<MyObject>(numHits, lessThan);
* // save the 'top' element, which is guaranteed to not be null.
* MyObject pqTop = pq.top();
* <...>
@@ -124,9 +106,10 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
* <b>NOTE:</b> the given supplier will be called {@code maxSize} times, relying on a new object
* to be returned and will not check if it's null again. Therefore you should ensure any call to
* this method creates a new instance and behaves consistently, e.g., it cannot return null if it
- * previously returned non-null and all returned instances must {@link #lessThan compare equal}.
+ * previously returned non-null and all returned instances must {@link LessThan compare equal}.
*/
- public PriorityQueue(int maxSize, Supplier<T> sentinelObjectSupplier) {
+ public PriorityQueue(
+ int maxSize, LessThan<? super T> lessThan, Supplier<T> sentinelObjectSupplier) {
final int heapSize;
if (0 == maxSize) {
@@ -149,6 +132,7 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
final T[] h = (T[]) new Object[heapSize];
this.heap = h;
this.maxSize = maxSize;
+ this.lessThan = lessThan;
// If sentinel objects are supported, populate the queue with them
T sentinel = sentinelObjectSupplier.get();
@@ -180,9 +164,8 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
// Heap with size S always takes first S elements of the array,
// and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
- Iterator<T> iterator = elements.iterator();
- while (iterator.hasNext()) {
- this.heap[size + 1] = iterator.next();
+ for (T element : elements) {
+ this.heap[size + 1] = element;
this.size++;
}
@@ -192,14 +175,6 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
}
}
- /**
- * Determines the ordering of objects in this priority queue. Subclasses must define this one
- * method.
- *
- * @return <code>true</code> iff parameter <code>a</code> is less than parameter <code>b</code>.
- */
- protected abstract boolean lessThan(T a, T b);
-
/**
* Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than
* maxSize from initialize an {@link ArrayIndexOutOfBoundsException} is thrown.
@@ -226,7 +201,7 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
if (size < maxSize) {
add(element);
return null;
- } else if (size > 0 && lessThan(heap[1], element)) {
+ } else if (size > 0 && lessThan.lessThan(heap[1], element)) {
T ret = heap[1];
heap[1] = element;
updateTop();
@@ -349,7 +324,7 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
int i = origPos;
T node = heap[i]; // save bottom node
int j = i >>> 1;
- while (j > 0 && lessThan(node, heap[j])) {
+ while (j > 0 && lessThan.lessThan(node, heap[j])) {
heap[i] = heap[j]; // shift parents down
i = j;
j = j >>> 1;
@@ -362,15 +337,15 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
T node = heap[i]; // save top node
int j = i << 1; // find smaller child
int k = j + 1;
- if (k <= size && lessThan(heap[k], heap[j])) {
+ if (k <= size && lessThan.lessThan(heap[k], heap[j])) {
j = k;
}
- while (j <= size && lessThan(heap[j], node)) {
+ while (j <= size && lessThan.lessThan(heap[j], node)) {
heap[i] = heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
- if (k <= size && lessThan(heap[k], heap[j])) {
+ if (k <= size && lessThan.lessThan(heap[k], heap[j])) {
j = k;
}
}
@@ -388,7 +363,7 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
@Override
public Iterator<T> iterator() {
- return new Iterator<T>() {
+ return new Iterator<>() {
int i = 1;
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java b/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
index 19246b5c1bc..01dc80a7c67 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
@@ -35,12 +35,7 @@ public class TestPriorityQueue extends LuceneTestCase {
private static class IntegerQueue extends PriorityQueue<Integer> {
public IntegerQueue(int count) {
- super(count);
- }
-
- @Override
- protected boolean lessThan(Integer a, Integer b) {
- return (a < b);
+ super(count, (a, b) -> a < b);
}
protected final void checkValidity() {
@@ -48,9 +43,7 @@ public class TestPriorityQueue extends LuceneTestCase {
for (int i = 1; i <= size(); i++) {
int parent = i >>> 1;
if (parent > 1) {
- if (lessThan((Integer) heapArray[parent], (Integer) heapArray[i]) == false) {
- assertEquals(heapArray[parent], heapArray[i]);
- }
+ assertThat((Integer) heapArray[i], greaterThanOrEqualTo((Integer) heapArray[parent]));
}
}
}
@@ -77,13 +70,7 @@ public class TestPriorityQueue extends LuceneTestCase {
}
}
- PriorityQueue<Value> pq =
- new PriorityQueue<>(5) {
- @Override
- protected boolean lessThan(Value a, Value b) {
- return a.value < b.value;
- }
- };
+ PriorityQueue<Value> pq = new PriorityQueue<>(5, (a, b) -> a.value < b.value);
// Make all elements equal but record insertion order.
for (int i = 0; i < 100; i++) {
@@ -345,15 +332,7 @@ public class TestPriorityQueue extends LuceneTestCase {
public void testMaxIntSize() {
expectThrows(
IllegalArgumentException.class,
- () -> {
- new PriorityQueue<Boolean>(Integer.MAX_VALUE) {
- @Override
- public boolean lessThan(Boolean a, Boolean b) {
- // uncalled
- return true;
- }
- };
- });
+ () -> new PriorityQueue<Boolean>(Integer.MAX_VALUE, (_, _) -> true));
}
private void assertOrderedWhenDrained(IntegerQueue pq, List<Integer> referenceDataList) {
diff --git a/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndNumberQueue.java b/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndNumberQueue.java
index 07b91f9b5fb..2fb3f89f1bf 100644
--- a/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndNumberQueue.java
+++ b/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndNumberQueue.java
@@ -39,12 +39,7 @@ public abstract class TopOrdAndNumberQueue extends PriorityQueue<TopOrdAndNumber
/** Sole constructor. */
public TopOrdAndNumberQueue(int topN) {
- super(topN);
- }
-
- @Override
- public boolean lessThan(TopOrdAndNumberQueue.OrdAndValue a, TopOrdAndNumberQueue.OrdAndValue b) {
- return a.lessThan(b);
+ super(topN, OrdAndValue::lessThan);
}
/**
diff --git a/lucene/suggest/src/java/org/apache/lucene/search/spell/SuggestWordQueue.java b/lucene/suggest/src/java/org/apache/lucene/search/spell/SuggestWordQueue.java
index bab8eb166e9..f36114e7eac 100644
--- a/lucene/suggest/src/java/org/apache/lucene/search/spell/SuggestWordQueue.java
+++ b/lucene/suggest/src/java/org/apache/lucene/search/spell/SuggestWordQueue.java
@@ -33,16 +33,13 @@ public final class SuggestWordQueue extends PriorityQueue<SuggestWord> {
*/
public static final Comparator<SuggestWord> DEFAULT_COMPARATOR = new SuggestWordScoreComparator();
- private Comparator<SuggestWord> comparator;
-
/**
* Use the {@link #DEFAULT_COMPARATOR}
*
* @param size The size of the queue
*/
public SuggestWordQueue(int size) {
- super(size);
- comparator = DEFAULT_COMPARATOR;
+ this(size, DEFAULT_COMPARATOR);
}
/**
@@ -52,13 +49,6 @@ public final class SuggestWordQueue extends PriorityQueue<SuggestWord> {
* @param comparator The comparator.
*/
public SuggestWordQueue(int size, Comparator<SuggestWord> comparator) {
- super(size);
- this.comparator = comparator;
- }
-
- @Override
- protected final boolean lessThan(SuggestWord wa, SuggestWord wb) {
- int val = comparator.compare(wa, wb);
- return val < 0;
+ super(size, (a, b) -> comparator.compare(a, b) < 0);
}
}