commitquery: Use internal/heap for the priority queue

2 files changed, 20 insertions, 60 deletions

diff --git a/commitquery/node_paint_down_to_common.go b/commitquery/node_paint_down_to_common.go
index 6bb1f489..a9618c2d 100644
--- a/commitquery/node_paint_down_to_common.go
+++ b/commitquery/node_paint_down_to_common.go
@@ -21,8 +21,15 @@ func (query *query) paintDownToCommon(left nodeIndex, rights []nodeIndex, minGen
 
 	lastGeneration := generationInfinity
 
-	for query.queueHasNonStale(queue) {
-		idx := queue.PopNode()
+	for queue.Len() > 0 {
+		idx, ok := queue.PopNode()
+		if !ok {
+			break
+		}
+
+		if query.hasAnyMarks(idx, markStale) {
+			continue
+		}
 
 		generation := query.effectiveGeneration(idx)
 		if generation > lastGeneration {
diff --git a/commitquery/priority_queue.go b/commitquery/priority_queue.go
index 8651ea0b..7b85e563 100644
--- a/commitquery/priority_queue.go
+++ b/commitquery/priority_queue.go
@@ -1,79 +1,32 @@
 package commitquery
 
-import "container/heap"
+import internalheap "codeberg.org/lindenii/furgit/internal/heap"
 
 // priorityQueue orders internal nodes using one query context's comparator.
 type priorityQueue struct {
-	query *query
-	items []nodeIndex
+	items *internalheap.Heap[nodeIndex]
 }
 
 // newPriorityQueue builds one empty priority queue over one query context.
 func newPriorityQueue(query *query) *priorityQueue {
-	queue := &priorityQueue{query: query}
-	heap.Init(queue)
-
-	return queue
+	return &priorityQueue{
+		items: internalheap.New(func(left, right nodeIndex) bool {
+			return query.compare(left, right) > 0
+		}),
+	}
 }
 
 // Len reports the number of queued items.
 func (queue *priorityQueue) Len() int {
-	return len(queue.items)
-}
-
-// Less reports whether one heap slot sorts ahead of another.
-func (queue *priorityQueue) Less(left, right int) bool {
-	return queue.query.compare(queue.items[left], queue.items[right]) > 0
-}
-
-// Swap exchanges two heap slots.
-func (queue *priorityQueue) Swap(left, right int) {
-	queue.items[left], queue.items[right] = queue.items[right], queue.items[left]
-}
-
-// Push appends one heap element.
-func (queue *priorityQueue) Push(item any) {
-	idx, ok := item.(nodeIndex)
-	if !ok {
-		panic("commitquery: heap push item is not a nodeIndex")
-	}
-
-	queue.items = append(queue.items, idx)
-}
-
-// Pop removes one heap element.
-func (queue *priorityQueue) Pop() any {
-	last := len(queue.items) - 1
-	item := queue.items[last]
-	queue.items = queue.items[:last]
-
-	return item
+	return queue.items.Len()
 }
 
 // PushNode inserts one internal node.
 func (queue *priorityQueue) PushNode(idx nodeIndex) {
-	heap.Push(queue, idx)
+	queue.items.Push(idx)
 }
 
 // PopNode removes the highest-priority internal node.
-func (queue *priorityQueue) PopNode() nodeIndex {
-	item := heap.Pop(queue)
-
-	idx, ok := item.(nodeIndex)
-	if !ok {
-		panic("commitquery: heap pop item is not a nodeIndex")
-	}
-
-	return idx
-}
-
-func (query *query) queueHasNonStale(queue *priorityQueue) bool {
-	// TODO
-	for _, idx := range queue.items {
-		if !query.hasAnyMarks(idx, markStale) {
-			return true
-		}
-	}
-
-	return false
+func (queue *priorityQueue) PopNode() (nodeIndex, bool) {
+	return queue.items.Pop()
 }