internal/priorityqueue: Add

1 files changed, 45 insertions, 0 deletions

diff --git a/internal/priorityqueue/queue.go b/internal/priorityqueue/queue.go
new file mode 100644
index 00000000..2d09add8
--- /dev/null
+++ b/internal/priorityqueue/queue.go
@@ -0,0 +1,45 @@
+package priorityqueue
+
+// Queue is one slice-backed priority queue.
+//
+// Labels: MT-Unsafe.
+type Queue[T any] struct {
+	items []T
+	less  func(left, right T) bool
+}
+
+// New builds one empty priority queue ordered by less.
+func New[T any](less func(left, right T) bool) *Queue[T] {
+	return &Queue[T]{less: less}
+}
+
+// Len reports the number of queued items.
+func (queue *Queue[T]) Len() int {
+	return len(queue.items)
+}
+
+// Pop removes one highest-priority item.
+func (queue *Queue[T]) Pop() (T, bool) {
+	if len(queue.items) == 0 {
+		var zero T
+
+		return zero, false
+	}
+
+	last := len(queue.items) - 1
+	top := queue.items[0]
+	queue.items[0] = queue.items[last]
+	queue.items = queue.items[:last]
+
+	if len(queue.items) > 0 {
+		queue.siftDown(0)
+	}
+
+	return top, true
+}
+
+// Push inserts one item.
+func (queue *Queue[T]) Push(item T) {
+	queue.items = append(queue.items, item)
+	queue.siftUp(len(queue.items) - 1)
+}