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
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 Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
private final int
private int
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate 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
private void
pushIn
(int nodeId, int parentId, float score) final int
size()
Returns the number of elements currently stored in the PriorityQueue.final int
topNode()
final 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 Details
-
maxSize
private final int maxSize -
heapNodes
-
size
private int size -
nodeIdHeapIndex
-
closed
private boolean closed
-
-
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)
-