lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From da...@apache.org
Subject [17/36] lucene-solr:jira/http2: LUCENE-8428: PriorityQueue takes sentinels via a Supplier as a constructor argument.
Date Tue, 31 Jul 2018 02:32:33 GMT
LUCENE-8428: PriorityQueue takes sentinels via a Supplier as a constructor argument.


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/914e2641
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/914e2641
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/914e2641

Branch: refs/heads/jira/http2
Commit: 914e2641658b71638f9f4c940fe9f63b1a67ce7d
Parents: 3119fbb
Author: Adrien Grand <jpountz@gmail.com>
Authored: Fri Jul 27 11:06:13 2018 +0200
Committer: Adrien Grand <jpountz@gmail.com>
Committed: Fri Jul 27 11:11:28 2018 +0200

----------------------------------------------------------------------
 lucene/CHANGES.txt                              |   4 +
 .../java/org/apache/lucene/search/HitQueue.java |  20 ++--
 .../lucene/search/spans/SpanPositionQueue.java  |   2 +-
 .../org/apache/lucene/util/PriorityQueue.java   | 108 +++++++++----------
 .../lucene/facet/TopOrdAndFloatQueue.java       |   2 +-
 .../apache/lucene/facet/TopOrdAndIntQueue.java  |   2 +-
 .../lucene/search/TermAutomatonScorer.java      |   4 +-
 7 files changed, 68 insertions(+), 74 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index e7f15aa..2876fa7 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -163,6 +163,10 @@ API Changes:
 
 * LUCENE-7314: Graduate LatLonPoint and query classes to core (Nick Knize)
 
+* LUCENE-8428: The way that oal.util.PriorityQueue creates sentinel objects has
+  been changed from a protected method to a java.util.function.Supplier as a
+  constructor argument. (Adrien Grand)
+
 Bug Fixes:
 
 * LUCENE-8380: UTF8TaxonomyWriterCache inconsistency. (Ruslan Torobaev, Dawid Weiss)

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/core/src/java/org/apache/lucene/search/HitQueue.java
----------------------------------------------------------------------
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 8868c2b..071f4bf 100644
--- a/lucene/core/src/java/org/apache/lucene/search/HitQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/search/HitQueue.java
@@ -58,21 +58,21 @@ final class HitQueue extends PriorityQueue<ScoreDoc> {
    *          the requested size of this queue.
    * @param prePopulate
    *          specifies whether to pre-populate the queue with sentinel values.
-   * @see #getSentinelObject()
    */
   HitQueue(int size, boolean prePopulate) {
-    super(size, prePopulate);
+    super(size, () -> {
+      if (prePopulate) {
+        // Always set the doc Id to MAX_VALUE so that it won't be favored by
+        // lessThan. This generally should not happen since if score is not NEG_INF,
+        // TopScoreDocCollector will always add the object to the queue.
+        return new ScoreDoc(Integer.MAX_VALUE, Float.NEGATIVE_INFINITY);
+      } else {
+        return null;
+      }
+    });
   }
 
   @Override
-  protected ScoreDoc getSentinelObject() {
-    // Always set the doc Id to MAX_VALUE so that it won't be favored by
-    // lessThan. This generally should not happen since if score is not NEG_INF,
-    // TopScoreDocCollector will always add the object to the queue.
-    return new ScoreDoc(Integer.MAX_VALUE, Float.NEGATIVE_INFINITY);
-  }
-  
-  @Override
   protected final boolean lessThan(ScoreDoc hitA, ScoreDoc hitB) {
     if (hitA.score == hitB.score)
       return hitA.doc > hitB.doc; 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionQueue.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionQueue.java b/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionQueue.java
index 2d2bd16..a82261c 100644
--- a/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/search/spans/SpanPositionQueue.java
@@ -21,7 +21,7 @@ import org.apache.lucene.util.PriorityQueue;
 
 class SpanPositionQueue extends PriorityQueue<Spans> {
   SpanPositionQueue(int maxSize) {
-    super(maxSize, false); // do not prepopulate
+    super(maxSize); // do not prepopulate
   }
 
   protected boolean lessThan(Spans s1, Spans s2) {

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
----------------------------------------------------------------------
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 ef08c4a..3c96dc5 100644
--- a/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
@@ -18,6 +18,7 @@ package org.apache.lucene.util;
 
 import java.util.Iterator;
 import java.util.NoSuchElementException;
+import java.util.function.Supplier;
 
 
 /**
@@ -26,10 +27,9 @@ import java.util.NoSuchElementException;
  * require log(size) time but the remove() cost implemented here is linear.
  *
  * <p>
- * <b>NOTE</b>: This class will pre-allocate a full array of length
- * <code>maxSize+1</code> if instantiated via the
- * {@link #PriorityQueue(int,boolean)} constructor with <code>prepopulate</code>
- * set to <code>true</code>.
+ * <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.
  *
  * <b>NOTE</b>: Iteration order is not specified.
  *
@@ -40,11 +40,47 @@ public abstract class PriorityQueue<T> implements Iterable<T>
{
   private final int maxSize;
   private final T[] heap;
 
+  /**
+   * Create an empty priority queue of the configured size.
+   */
   public PriorityQueue(int maxSize) {
-    this(maxSize, true);
+    this(maxSize, () -> null);
   }
 
-  public PriorityQueue(int maxSize, boolean prepopulate) {
+  /**
+   * Create a priority queue that is pre-filled with sentinel objects, so that
+   * the code which uses that queue can always assume it's full and only change
+   * the top without attempting to insert any new object.<br>
+   *
+   * Those sentinel values should always compare worse than any non-sentinel
+   * value (i.e., {@link #lessThan} should always favor the
+   * non-sentinel values).<br>
+   *
+   * By default, the supplier returns null, which means the queue will not be
+   * filled with sentinel values. Otherwise, the value returned will be used to
+   * pre-populate the queue.<br>
+   *
+   * If this method is extended to return a non-null value, then the following
+   * usage pattern is recommended:
+   *
+   * <pre class="prettyprint">
+   * PriorityQueue&lt;MyObject&gt; pq = new MyQueue&lt;MyObject&gt;(numHits);
+   * // save the 'top' element, which is guaranteed to not be null.
+   * MyObject pqTop = pq.top();
+   * &lt;...&gt;
+   * // now in order to add a new element, which is 'better' than top (after
+   * // you've verified it is better), it is as simple as:
+   * pqTop.change().
+   * pqTop = pq.updateTop();
+   * </pre>
+   *
+   * <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}.
+   */
+  public PriorityQueue(int maxSize, Supplier<T> sentinelObjectSupplier) {
     final int heapSize;
     if (0 == maxSize) {
       // We allocate 1 extra to avoid if statement in top()
@@ -65,16 +101,14 @@ public abstract class PriorityQueue<T> implements Iterable<T>
{
     this.heap = h;
     this.maxSize = maxSize;
 
-    if (prepopulate) {
-      // If sentinel objects are supported, populate the queue with them
-      T sentinel = getSentinelObject();
-      if (sentinel != null) {
-        heap[1] = sentinel;
-        for (int i = 2; i < heap.length; i++) {
-          heap[i] = getSentinelObject();
-        }
-        size = maxSize;
+    // If sentinel objects are supported, populate the queue with them
+    T sentinel = sentinelObjectSupplier.get();
+    if (sentinel != null) {
+      heap[1] = sentinel;
+      for (int i = 2; i < heap.length; i++) {
+        heap[i] = sentinelObjectSupplier.get();
       }
+      size = maxSize;
     }
   }
 
@@ -85,50 +119,6 @@ public abstract class PriorityQueue<T> implements Iterable<T>
{
   protected abstract boolean lessThan(T a, T b);
 
   /**
-   * This method can be overridden by extending classes to return a sentinel
-   * object which will be used by the {@link PriorityQueue#PriorityQueue(int,boolean)}
-   * constructor to fill the queue, so that the code which uses that queue can always
-   * assume it's full and only change the top without attempting to insert any new
-   * object.<br>
-   *
-   * Those sentinel values should always compare worse than any non-sentinel
-   * value (i.e., {@link #lessThan} should always favor the
-   * non-sentinel values).<br>
-   *
-   * By default, this method returns null, which means the queue will not be
-   * filled with sentinel values. Otherwise, the value returned will be used to
-   * pre-populate the queue. Adds sentinel values to the queue.<br>
-   *
-   * If this method is extended to return a non-null value, then the following
-   * usage pattern is recommended:
-   *
-   * <pre class="prettyprint">
-   * // extends getSentinelObject() to return a non-null value.
-   * PriorityQueue&lt;MyObject&gt; pq = new MyQueue&lt;MyObject&gt;(numHits);
-   * // save the 'top' element, which is guaranteed to not be null.
-   * MyObject pqTop = pq.top();
-   * &lt;...&gt;
-   * // now in order to add a new element, which is 'better' than top (after
-   * // you've verified it is better), it is as simple as:
-   * pqTop.change().
-   * pqTop = pq.updateTop();
-   * </pre>
-   *
-   * <b>NOTE:</b> if this method returns a non-null value, it will be called
by
-   * the {@link PriorityQueue#PriorityQueue(int,boolean)} constructor
-   * {@link #size()} 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.
-   *
-   * @return the sentinel object to use to pre-populate the queue, or null if
-   *         sentinel objects are not supported.
-   */
-  protected T getSentinelObject() {
-    return null;
-  }
-
-  /**
    * 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.

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndFloatQueue.java
----------------------------------------------------------------------
diff --git a/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndFloatQueue.java b/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndFloatQueue.java
index d0fe8a9..d4072cd 100644
--- a/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndFloatQueue.java
+++ b/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndFloatQueue.java
@@ -38,7 +38,7 @@ public class TopOrdAndFloatQueue extends PriorityQueue<TopOrdAndFloatQueue.OrdAn
 
   /** Sole constructor. */
   public TopOrdAndFloatQueue(int topN) {
-    super(topN, false);
+    super(topN);
   }
 
   @Override

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndIntQueue.java
----------------------------------------------------------------------
diff --git a/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndIntQueue.java b/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndIntQueue.java
index 4429116..85638da 100644
--- a/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndIntQueue.java
+++ b/lucene/facet/src/java/org/apache/lucene/facet/TopOrdAndIntQueue.java
@@ -38,7 +38,7 @@ public class TopOrdAndIntQueue extends PriorityQueue<TopOrdAndIntQueue.OrdAndVal
 
   /** Sole constructor. */
   public TopOrdAndIntQueue(int topN) {
-    super(topN, false);
+    super(topN);
   }
 
   @Override

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/914e2641/lucene/sandbox/src/java/org/apache/lucene/search/TermAutomatonScorer.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/search/TermAutomatonScorer.java b/lucene/sandbox/src/java/org/apache/lucene/search/TermAutomatonScorer.java
index 6887a4c..474a8d9 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/search/TermAutomatonScorer.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/search/TermAutomatonScorer.java
@@ -86,7 +86,7 @@ class TermAutomatonScorer extends Scorer {
    *  the same (lowest) docID. */
   private static class DocIDQueue extends PriorityQueue<EnumAndScorer> {
     public DocIDQueue(int maxSize) {
-      super(maxSize, false);
+      super(maxSize);
     }
 
     @Override
@@ -99,7 +99,7 @@ class TermAutomatonScorer extends Scorer {
    *  position. */
   private static class PositionQueue extends PriorityQueue<EnumAndScorer> {
     public PositionQueue(int maxSize) {
-      super(maxSize, false);
+      super(maxSize);
     }
 
     @Override


Mime
View raw message