Module org.apache.lucene.join
Package org.apache.lucene.search.join
Class DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap
- java.lang.Object
-
- org.apache.lucene.search.join.DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap
-
- Enclosing class:
- DiversifyingNearestChildrenKnnCollector
private static class DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap extends java.lang.Object
This is a minimum binary heap, inspired byLongHeap
. 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 Summary
Fields Modifier and Type Field Description private boolean
closed
private DiversifyingNearestChildrenKnnCollector.ParentChildScore[]
heapNodes
private int
maxSize
private java.util.Map<java.lang.Integer,java.lang.Integer>
nodeIdHeapIndex
private int
size
-
Constructor Summary
Constructors Constructor Description NodeIdCachingHeap(int maxSize)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private int
downHeap(int i)
private int
downHeapWithoutCacheUpdate(int i)
boolean
insertWithOverflow(int node, int parentNode, float score)
Adds a value to an heap in log(size) time.private void
popToDrain()
private void
pushIn(int nodeId, int parentId, float score)
int
size()
Returns the number of elements currently stored in the PriorityQueue.int
topNode()
float
topScore()
private void
updateElement(int heapIndex, int nodeId, int parentId, float score)
private void
updateTop(int nodeId, int parentId, float score)
private void
upHeap(int origPos)
-
-
-
Field Detail
-
maxSize
private final int maxSize
-
heapNodes
private DiversifyingNearestChildrenKnnCollector.ParentChildScore[] heapNodes
-
size
private int size
-
nodeIdHeapIndex
private final java.util.Map<java.lang.Integer,java.lang.Integer> nodeIdHeapIndex
-
closed
private boolean closed
-
-
Method Detail
-
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)
-
-