-
Notifications
You must be signed in to change notification settings - Fork 645
/
queue.go
94 lines (71 loc) · 1.67 KB
/
queue.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Copyright (C) 2019-2024, Ava Labs, Inc. All rights reserved.
// See the file LICENSE for licensing terms.
package heap
import (
"container/heap"
"github.com/ava-labs/avalanchego/utils"
)
var _ heap.Interface = (*queue[int])(nil)
// NewQueue returns an empty heap. See QueueOf for more.
func NewQueue[T any](less func(a, b T) bool) Queue[T] {
return QueueOf(less)
}
// QueueOf returns a heap containing entries ordered by less.
func QueueOf[T any](less func(a, b T) bool, entries ...T) Queue[T] {
q := Queue[T]{
queue: &queue[T]{
entries: make([]T, len(entries)),
less: less,
},
}
copy(q.queue.entries, entries)
heap.Init(q.queue)
return q
}
type Queue[T any] struct {
queue *queue[T]
}
func (q *Queue[T]) Len() int {
return len(q.queue.entries)
}
func (q *Queue[T]) Push(t T) {
heap.Push(q.queue, t)
}
func (q *Queue[T]) Pop() (T, bool) {
if q.Len() == 0 {
return utils.Zero[T](), false
}
return heap.Pop(q.queue).(T), true
}
func (q *Queue[T]) Peek() (T, bool) {
if q.Len() == 0 {
return utils.Zero[T](), false
}
return q.queue.entries[0], true
}
func (q *Queue[T]) Fix(i int) {
heap.Fix(q.queue, i)
}
type queue[T any] struct {
entries []T
less func(a, b T) bool
}
func (q *queue[T]) Len() int {
return len(q.entries)
}
func (q *queue[T]) Less(i, j int) bool {
return q.less(q.entries[i], q.entries[j])
}
func (q *queue[T]) Swap(i, j int) {
q.entries[i], q.entries[j] = q.entries[j], q.entries[i]
}
func (q *queue[T]) Push(e any) {
q.entries = append(q.entries, e.(T))
}
func (q *queue[T]) Pop() any {
end := len(q.entries) - 1
popped := q.entries[end]
q.entries[end] = utils.Zero[T]()
q.entries = q.entries[:end]
return popped
}