runxiyu.tngl.sh
Fast implementation of Git in pure Go
1package commitquery
2
3import "container/heap"
4
5// priorityQueue orders internal nodes using one query context's comparator.
6type priorityQueue struct {
7 query *Query
8 items []nodeIndex
9}
10
11// newPriorityQueue builds one empty priority queue over one query context.
12func newPriorityQueue(query *Query) *priorityQueue {
13 queue := &priorityQueue{query: query}
14 heap.Init(queue)
15
16 return queue
17}
18
19// Len reports the number of queued items.
20func (queue *priorityQueue) Len() int {
21 return len(queue.items)
22}
23
24// Less reports whether one heap slot sorts ahead of another.
25func (queue *priorityQueue) Less(left, right int) bool {
26 return queue.query.compare(queue.items[left], queue.items[right]) > 0
27}
28
29// Swap exchanges two heap slots.
30func (queue *priorityQueue) Swap(left, right int) {
31 queue.items[left], queue.items[right] = queue.items[right], queue.items[left]
32}
33
34// Push appends one heap element.
35func (queue *priorityQueue) Push(item any) {
36 idx, ok := item.(nodeIndex)
37 if !ok {
38 panic("commitquery: heap push item is not a nodeIndex")
39 }
40
41 queue.items = append(queue.items, idx)
42}
43
44// Pop removes one heap element.
45func (queue *priorityQueue) Pop() any {
46 last := len(queue.items) - 1
47 item := queue.items[last]
48 queue.items = queue.items[:last]
49
50 return item
51}
52
53// PushNode inserts one internal node.
54func (queue *priorityQueue) PushNode(idx nodeIndex) {
55 heap.Push(queue, idx)
56}
57
58// PopNode removes the highest-priority internal node.
59func (queue *priorityQueue) PopNode() nodeIndex {
60 item := heap.Pop(queue)
61
62 idx, ok := item.(nodeIndex)
63 if !ok {
64 panic("commitquery: heap pop item is not a nodeIndex")
65 }
66
67 return idx
68}