internal/priorityqueue: Actually just make our own priority queue

2 files changed, 0 insertions, 157 deletions

diff --git a/internal/heap/heap.go b/internal/heap/heap.go
deleted file mode 100644
index 7ad551ab..00000000
--- a/internal/heap/heap.go
+++ /dev/null
@@ -1,93 +0,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
-	}
-}
diff --git a/internal/heap/heap_test.go b/internal/heap/heap_test.go
deleted file mode 100644
index 46795702..00000000
--- a/internal/heap/heap_test.go
+++ /dev/null
@@ -1,64 +0,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())
-	}
-}