Class DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap

java.lang.Object
org.apache.lucene.search.join.DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap
Enclosing class:
DiversifyingNearestChildrenKnnCollector

private static class DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap extends Object
This is a minimum binary heap, inspired by LongHeap. But instead of encoding and using `long` values. Node ids and scores are kept separate. Additionally, this prevents duplicate nodes from being added.

So, for every node added, we will update its score if the newly provided score is better. Every time we update a node's stored score, we ensure the heap's order.

  • Field Details

  • Constructor Details

    • NodeIdCachingHeap

      public NodeIdCachingHeap(int maxSize)
  • Method Details

    • topNode

      public final int topNode()
    • topScore

      public final float topScore()
    • pushIn

      private void pushIn(int nodeId, int parentId, float score)
    • updateElement

      private void updateElement(int heapIndex, int nodeId, int parentId, float score)
    • insertWithOverflow

      public boolean insertWithOverflow(int node, int parentNode, float score)
      Adds a value to an heap in log(size) time. If the number of values would exceed the heap's maxSize, the least value is discarded.

      If `node` already exists in the heap, this will return true if the stored score is updated OR the heap is not currently at the maxSize.

      Returns:
      whether the value was added or updated
    • popToDrain

      private void popToDrain()
    • updateTop

      private void updateTop(int nodeId, int parentId, float score)
    • size

      public final int size()
      Returns the number of elements currently stored in the PriorityQueue.
    • upHeap

      private void upHeap(int origPos)
    • downHeap

      private int downHeap(int i)
    • downHeapWithoutCacheUpdate

      private int downHeapWithoutCacheUpdate(int i)