queue.gno

 1package dijkstra
 2
 3// queue is the frontier: a binary min-heap of node indices ordered by their
 4// current distance, with a position table so a node already in the heap can be
 5// moved up when its distance improves.
 6//
 7// The alternative, pushing a second entry and discarding stale pops, is
 8// shorter and is what a generic priority queue forces on you. It also lets the
 9// heap grow to one entry per arc, which is the size this package refuses to
10// let a caller guess at: here the heap holds at most one entry per node, so
11// MaxNodes bounds the memory and MaxEdges bounds only the work.
12//
13// Ordering is total: distance first, then node index. Node indices are
14// assigned in the order AddNode saw them, so an equal-distance tie resolves to
15// the order the caller built the graph in, identically on every machine.
16type queue struct {
17	heap []int // heap positions -> node index
18	pos  []int // node index -> heap position, -1 when not queued
19	dist []int // the live distance table, read, never written
20}
21
22func newQueue(n int, dist []int) *queue {
23	q := &queue{dist: dist, pos: make([]int, n)}
24	for i := 0; i < n; i++ {
25		q.pos[i] = -1
26	}
27	return q
28}
29
30func (q *queue) empty() bool { return len(q.heap) == 0 }
31
32func (q *queue) less(a, b int) bool {
33	if q.dist[a] != q.dist[b] {
34		return q.dist[a] < q.dist[b]
35	}
36	return a < b
37}
38
39func (q *queue) swap(i, j int) {
40	q.heap[i], q.heap[j] = q.heap[j], q.heap[i]
41	q.pos[q.heap[i]] = i
42	q.pos[q.heap[j]] = j
43}
44
45// push queues a node whose distance has just become finite.
46func (q *queue) push(node int) {
47	q.heap = append(q.heap, node)
48	q.pos[node] = len(q.heap) - 1
49	q.up(len(q.heap) - 1)
50}
51
52// decreased re-sifts a queued node after its distance dropped.
53func (q *queue) decreased(node int) { q.up(q.pos[node]) }
54
55// pop removes and returns the closest outstanding node.
56func (q *queue) pop() int {
57	top := q.heap[0]
58	last := len(q.heap) - 1
59	q.swap(0, last)
60	q.heap = q.heap[:last]
61	q.pos[top] = -1
62	if last > 0 {
63		q.down(0)
64	}
65	return top
66}
67
68func (q *queue) up(i int) {
69	for i > 0 {
70		parent := (i - 1) / 2
71		if !q.less(q.heap[i], q.heap[parent]) {
72			break
73		}
74		q.swap(i, parent)
75		i = parent
76	}
77}
78
79func (q *queue) down(i int) {
80	n := len(q.heap)
81	for {
82		small := i
83		if l := 2*i + 1; l < n && q.less(q.heap[l], q.heap[small]) {
84			small = l
85		}
86		if r := 2*i + 2; r < n && q.less(q.heap[r], q.heap[small]) {
87			small = r
88		}
89		if small == i {
90			return
91		}
92		q.swap(i, small)
93		i = small
94	}
95}