ref: 69452f58fb0d6c1ed561df1e25efe51e5b3089fd
parent: 3fdec79ddcafde9848b60fc420bb9222a4786e1f
author: Runxi Yu <runxiyu@umich.edu>
date: Sun Mar 29 10:14:21 EDT 2026
internal/priorityqueue: Actually just make our own priority queue
--- a/internal/heap/heap.go
+++ /dev/null
@@ -1,93 +1,0 @@
-package heap
-
-// Heap is one slice-backed binary heap.
-type Heap[T any] struct {- items []T
- less func(left, right T) bool
-}
-
-// New builds one empty heap ordered by less.
-func New[T any](less func(left, right T) bool) *Heap[T] {- return &Heap[T]{less: less}-}
-
-// Len reports the number of queued items.
-func (heap *Heap[T]) Len() int {- return len(heap.items)
-}
-
-// Empty reports whether the heap is empty.
-func (heap *Heap[T]) Empty() bool {- return len(heap.items) == 0
-}
-
-// Peek returns the top item without removing it.
-func (heap *Heap[T]) Peek() (T, bool) {- if len(heap.items) == 0 {- var zero T
-
- return zero, false
- }
-
- return heap.items[0], true
-}
-
-// Push inserts one item.
-func (heap *Heap[T]) Push(item T) {- heap.items = append(heap.items, item)
- heap.siftUp(len(heap.items) - 1)
-}
-
-// Pop removes one top item.
-func (heap *Heap[T]) Pop() (T, bool) {- if len(heap.items) == 0 {- var zero T
-
- return zero, false
- }
-
- last := len(heap.items) - 1
- top := heap.items[0]
- heap.items[0] = heap.items[last]
- heap.items = heap.items[:last]
-
- if len(heap.items) > 0 {- heap.siftDown(0)
- }
-
- return top, true
-}
-
-func (heap *Heap[T]) siftUp(idx int) {- for idx > 0 {- parent := (idx - 1) / 2
- if !heap.less(heap.items[idx], heap.items[parent]) {- return
- }
-
- heap.items[idx], heap.items[parent] = heap.items[parent], heap.items[idx]
- idx = parent
- }
-}
-
-func (heap *Heap[T]) siftDown(idx int) {- for {- left := idx*2 + 1
- if left >= len(heap.items) {- return
- }
-
- best := left
- right := left + 1
- if right < len(heap.items) && heap.less(heap.items[right], heap.items[left]) {- best = right
- }
-
- if !heap.less(heap.items[best], heap.items[idx]) {- return
- }
-
- heap.items[idx], heap.items[best] = heap.items[best], heap.items[idx]
- idx = best
- }
-}
--- a/internal/heap/heap_test.go
+++ /dev/null
@@ -1,64 +1,0 @@
-package heap_test
-
-import (
- "slices"
- "testing"
-
- internalheap "codeberg.org/lindenii/furgit/internal/heap"
-)
-
-func TestHeapAscending(t *testing.T) {- t.Parallel()
-
- heap := internalheap.New(func(left, right int) bool {- return left < right
- })
-
- for _, value := range []int{5, 1, 4, 3, 2} {- heap.Push(value)
- }
-
- var got []int
- for !heap.Empty() {- value, ok := heap.Pop()
- if !ok {- t.Fatal("Pop should succeed")- }
-
- got = append(got, value)
- }
-
- want := []int{1, 2, 3, 4, 5}- if !slices.Equal(got, want) {- t.Fatalf("pop order = %v, want %v", got, want)- }
-}
-
-func TestHeapPeek(t *testing.T) {- t.Parallel()
-
- heap := internalheap.New(func(left, right int) bool {- return left > right
- })
-
- if _, ok := heap.Peek(); ok {- t.Fatal("Peek on empty heap should miss")- }
-
- heap.Push(1)
- heap.Push(3)
- heap.Push(2)
-
- value, ok := heap.Peek()
- if !ok {- t.Fatal("Peek should succeed")- }
-
- if value != 3 {- t.Fatalf("Peek = %d, want 3", value)- }
-
- if heap.Len() != 3 {- t.Fatalf("Len after Peek = %d, want 3", heap.Len())- }
-}
--- /dev/null
+++ b/internal/priorityqueue/len.go
@@ -1,0 +1,6 @@
+package priorityqueue
+
+// Len reports the number of queued items.
+func (queue *Queue[T]) Len() int {+ return len(queue.items)
+}
--- /dev/null
+++ b/internal/priorityqueue/new.go
@@ -1,0 +1,6 @@
+package priorityqueue
+
+// 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}+}
--- /dev/null
+++ b/internal/priorityqueue/pop.go
@@ -1,0 +1,21 @@
+package priorityqueue
+
+// 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
+}
--- /dev/null
+++ b/internal/priorityqueue/push.go
@@ -1,0 +1,7 @@
+package priorityqueue
+
+// Push inserts one item.
+func (queue *Queue[T]) Push(item T) {+ queue.items = append(queue.items, item)
+ queue.siftUp(len(queue.items) - 1)
+}
--- /dev/null
+++ b/internal/priorityqueue/queue.go
@@ -1,0 +1,7 @@
+package priorityqueue
+
+// Queue is one slice-backed priority queue.
+type Queue[T any] struct {+ items []T
+ less func(left, right T) bool
+}
--- /dev/null
+++ b/internal/priorityqueue/queue_test.go
@@ -1,0 +1,35 @@
+package priorityqueue_test
+
+import (
+ "slices"
+ "testing"
+
+ "codeberg.org/lindenii/furgit/internal/priorityqueue"
+)
+
+func TestQueueAscending(t *testing.T) {+ t.Parallel()
+
+ queue := priorityqueue.New(func(left, right int) bool {+ return left < right
+ })
+
+ for _, value := range []int{5, 1, 4, 3, 2} {+ queue.Push(value)
+ }
+
+ var got []int
+ for queue.Len() > 0 {+ value, ok := queue.Pop()
+ if !ok {+ t.Fatal("Pop should succeed")+ }
+
+ got = append(got, value)
+ }
+
+ want := []int{1, 2, 3, 4, 5}+ if !slices.Equal(got, want) {+ t.Fatalf("pop order = %v, want %v", got, want)+ }
+}
--- /dev/null
+++ b/internal/priorityqueue/sift_down.go
@@ -1,0 +1,23 @@
+package priorityqueue
+
+func (queue *Queue[T]) siftDown(idx int) {+ for {+ left := idx*2 + 1
+ if left >= len(queue.items) {+ return
+ }
+
+ best := left
+ right := left + 1
+ if right < len(queue.items) && queue.less(queue.items[right], queue.items[left]) {+ best = right
+ }
+
+ if !queue.less(queue.items[best], queue.items[idx]) {+ return
+ }
+
+ queue.items[idx], queue.items[best] = queue.items[best], queue.items[idx]
+ idx = best
+ }
+}
--- /dev/null
+++ b/internal/priorityqueue/sift_up.go
@@ -1,0 +1,13 @@
+package priorityqueue
+
+func (queue *Queue[T]) siftUp(idx int) {+ for idx > 0 {+ parent := (idx - 1) / 2
+ if !queue.less(queue.items[idx], queue.items[parent]) {+ return
+ }
+
+ queue.items[idx], queue.items[parent] = queue.items[parent], queue.items[idx]
+ idx = parent
+ }
+}
--
⑨