Package org.apache.lucene.util.hnsw
Class NeighborQueue
- java.lang.Object
-
- org.apache.lucene.util.hnsw.NeighborQueue
-
public class NeighborQueue extends java.lang.Object
NeighborQueue uses aLongHeap
to store lists of arcs in an HNSW graph, represented as a neighbor node id with an associated score packed together as a sortable long, which is sorted primarily by score. The queue provides both fixed-size and unbounded operations viainsertWithOverflow(int, float)
andadd(int, float)
, and provides MIN and MAX heap subclasses.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
NeighborQueue.Order
-
Field Summary
Fields Modifier and Type Field Description private LongHeap
heap
private boolean
incomplete
private NeighborQueue.Order
order
private int
visitedCount
-
Constructor Summary
Constructors Constructor Description NeighborQueue(int initialSize, boolean reversed)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(int newNode, float newScore)
Adds a new graph arc, extending the storage as needed.void
clear()
private long
encode(int node, float score)
boolean
incomplete()
boolean
insertWithOverflow(int newNode, float newScore)
If the heap is not full (size is less than the initialSize provided to the constructor), adds a new node-and-score element.void
markIncomplete()
int[]
nodes()
int
pop()
Removes the top element and returns its node id.void
setVisitedCount(int visitedCount)
int
size()
int
topNode()
Returns the top element's node id.float
topScore()
Returns the top element's node score.java.lang.String
toString()
int
visitedCount()
-
-
-
Field Detail
-
heap
private final LongHeap heap
-
order
private final NeighborQueue.Order order
-
visitedCount
private int visitedCount
-
incomplete
private boolean incomplete
-
-
Method Detail
-
size
public int size()
- Returns:
- the number of elements in the heap
-
add
public void add(int newNode, float newScore)
Adds a new graph arc, extending the storage as needed.- Parameters:
newNode
- the neighbor node idnewScore
- the score of the neighbor, relative to some other node
-
insertWithOverflow
public boolean insertWithOverflow(int newNode, float newScore)
If the heap is not full (size is less than the initialSize provided to the constructor), adds a new node-and-score element. If the heap is full, compares the score against the current top score, and replaces the top element if newScore is better than (greater than unless the heap is reversed), the current top score.- Parameters:
newNode
- the neighbor node idnewScore
- the score of the neighbor, relative to some other node
-
encode
private long encode(int node, float score)
-
pop
public int pop()
Removes the top element and returns its node id.
-
nodes
public int[] nodes()
-
topNode
public int topNode()
Returns the top element's node id.
-
topScore
public float topScore()
Returns the top element's node score.
-
clear
public void clear()
-
visitedCount
public int visitedCount()
-
setVisitedCount
public void setVisitedCount(int visitedCount)
-
incomplete
public boolean incomplete()
-
markIncomplete
public void markIncomplete()
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-