Just deque

8 files changed, 9 insertions, 351 deletions

diff --git a/README.md b/README.md
index 0403f41..65661f1 100644
--- a/README.md
+++ b/README.md
@@ -1,7 +1,9 @@
-# container: the missing piece of the Go standard library
+# deque: a high-performance slice-backed double-ended queue inspired by Rust's VecDeque
 
-container implements efficient slice-backed data structures that would probably
-have been included in Go's standard library if generics had been available from
-the start. Package deque implements a double-ended queue inspired by Rust's
-wonderful VecDeque type. Package heap is a reimagining of the standard library
-container/heap with a generics-first implementation.
+Compared to other popular slice-backed deque implementations, this one
+
+ - is only 32 bytes;
+ - uses append to get an optimial growth factor;
+ - supports iterating using Go 1.23 iterators;
+ - and steals Rust's clever strategy for minimizing the amount of data copied
+   on reallocation.
diff --git a/deque/deque.go b/deque.go
index ace06f6..e8a9018 100644
--- a/deque/deque.go
+++ b/deque.go
@@ -9,13 +9,6 @@
 // Deque goes front to back.
 //
 // The core implementation is "ported" (stolen) from Rust's VecDeque.
-//
-// Compared to other popular slice-backed deque implementations, this one
-//   - is only 32 bytes;
-//   - uses append to get an optimial growth factor;
-//   - supports iterating using Go 1.23 iterators;
-//   - and steals Rust's clever strategy for minimizing the amount of data copied
-//     on reallocation.
 package deque
 
 import (
diff --git a/deque/deque_test.go b/deque_test.go
index 27ae232..27ae232 100644
--- a/deque/deque_test.go
+++ b/deque_test.go
diff --git a/deque/example_test.go b/example_test.go
index 3e1ac80..3e1ac80 100644
--- a/deque/example_test.go
+++ b/example_test.go
diff --git a/go.mod b/go.mod
index 376dd83..d50fe8a 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,3 @@
-module github.com/rhogenson/container
+module github.com/rhogenson/deque
 
 go 1.24.1
diff --git a/heap/example_test.go b/heap/example_test.go
deleted file mode 100644
index f8ea7d8..0000000
--- a/heap/example_test.go
+++ /dev/null
@@ -1,178 +0,0 @@
-package heap_test
-
-import (
-	"cmp"
-	"fmt"
-
-	"github.com/rhogenson/container/heap"
-)
-
-func Example_dijkstra() {
-	const (
-		maze = `
----------------------
-    |   |           |
-| --- | | --- ----- |
-|   | |   |   |     |
-|-- |-----| ----- --|
-|   |     |     | | |
-| --- --- | --- | | |
-| |   | |     | | | |
-| | --- | | --- | | |
-| | |   | | |   |   |
-| | --- | |-- --|-- |
-| |   | | |   | |   |
-| |-- | | | --- | --|
-| |   | |   |     | |
-| | --| ----- ----- |
-| |   |       |     |
-| | | | --------- | |
-| | | |     |   | | |
-| --- |---- | | | | |
-|     |       |      
----------------------
-`
-		width  = 21
-		height = 21
-	)
-
-	type point struct{ x, y int }
-	start := point{0, 1}
-	goal := point{20, 19}
-	neighbors := func(p point) []point {
-		return []point{
-			{p.x - 1, p.y},
-			{p.x + 1, p.y},
-			{p.x, p.y - 1},
-			{p.x, p.y + 1},
-		}
-	}
-	walkable := func(p point) bool {
-		return 0 <= p.y && p.y < height &&
-			0 <= p.x && p.x < width &&
-			maze[p.y*(width+1)+p.x+1] == ' '
-	}
-
-	visited := map[point]int{start: 1}
-	q := heap.New(func(x, y point) int { return cmp.Compare(visited[x], visited[y]) })
-	q.Push(start)
-Dijkstra:
-	for {
-		p, ok := q.Pop()
-		if !ok {
-			fmt.Println("Giving up!")
-			return
-		}
-		for _, neighbor := range neighbors(p) {
-			if !walkable(neighbor) || visited[neighbor] > 0 {
-				continue
-			}
-			visited[neighbor] = visited[p] + 1
-			if neighbor == goal {
-				break Dijkstra
-			}
-			q.Push(neighbor)
-		}
-	}
-
-	completedMaze := []byte(maze)
-	fillIn := func(p point) {
-		completedMaze[p.y*(width+1)+p.x+1] = '*'
-	}
-	for p := goal; p != start; {
-		fillIn(p)
-		closestPoint := p
-		for _, neighbor := range neighbors(p) {
-			if walkable(neighbor) && visited[neighbor] > 0 && visited[neighbor] < visited[closestPoint] {
-				closestPoint = neighbor
-			}
-		}
-		p = closestPoint
-	}
-	fillIn(start)
-
-	fmt.Printf("%s\n", completedMaze)
-
-	// Output:
-	// ---------------------
-	// **  |   |    *******|
-	// |*--- | | ---*-----*|
-	// |***| |   |***|  ***|
-	// |--*|-----|*-----*--|
-	// |***|*****|*    |*| |
-	// |*---*---*|*--- |*| |
-	// |*|***| |***  | |*| |
-	// |*|*--- | | --- |*| |
-	// |*|*|   | | |   |***|
-	// |*|*--- | |-- --|--*|
-	// |*|***| | |   | |***|
-	// |*|--*| | | --- |*--|
-	// |*|***| |   |*****| |
-	// |*|*--| -----*----- |
-	// |*|***|*******|     |
-	// |*| |*|*--------- | |
-	// |*| |*|*****|***| | |
-	// |*---*|----*|*|*| | |
-	// |*****|    ***|******
-	// ---------------------
-}
-
-func ExampleNew() {
-	priority := map[string]int{
-		"job1": 10,
-		"job2": 30,
-		"job3": 100,
-		"job4": 20,
-	}
-	h := heap.New(func(j1, j2 string) int { return cmp.Compare(priority[j1], priority[j2]) })
-	h.Push("job1")
-	h.Push("job2")
-	h.Push("job3")
-	h.Push("job4")
-	if highestPriorityJob, ok := h.Pop(); ok {
-		fmt.Println(highestPriorityJob)
-	}
-
-	// Output:
-	// job1
-}
-
-func ExampleHeap_Len() {
-	h := heap.New(cmp.Compare[int])
-	h.Push(1)
-	h.Push(2)
-	h.Push(3)
-	fmt.Println(h.Len())
-
-	// Output:
-	// 3
-}
-
-func ExampleHeap_Grow() {
-	h := heap.New(cmp.Compare[int])
-	h.Grow(3)
-	// Push without allocating:
-	h.Push(1)
-	h.Push(2)
-	h.Push(3)
-}
-
-func ExampleHeap_Push() {
-	h := heap.New(cmp.Compare[int])
-	h.Push(1)
-	h.Push(2)
-	h.Push(3)
-}
-
-func ExampleHeap_Pop() {
-	h := heap.New(cmp.Compare[int])
-	h.Push(1)
-	h.Push(2)
-	h.Push(3)
-	if n, ok := h.Pop(); ok {
-		fmt.Println(n)
-	}
-
-	// Output:
-	// 1
-}
diff --git a/heap/heap.go b/heap/heap.go
deleted file mode 100644
index 612d5a8..0000000
--- a/heap/heap.go
+++ /dev/null
@@ -1,87 +0,0 @@
-// Package heap implements a priority queue as a min heap backed by a slice.
-//
-// This can be seen as a replacement for the standard library [container/heap]
-// package which was created before generics were a thing.
-package heap
-
-import (
-	"slices"
-)
-
-// Heap is a binary heap backed by a slice.
-type Heap[T any] struct {
-	buf     []T
-	compare func(T, T) int
-}
-
-// New creates a new heap with the given comparison function.
-func New[T any](compare func(T, T) int) *Heap[T] {
-	return &Heap[T]{compare: compare}
-}
-
-// Len returns the number of elements in the Heap.
-func (h *Heap[T]) Len() int {
-	return len(h.buf)
-}
-
-// Grow makes space for at least n more elements to be pushed onto the heap
-// without reallocating.
-func (h *Heap[T]) Grow(n int) {
-	h.buf = slices.Grow(h.buf, n)
-}
-
-// Push pushes the element x onto the heap.
-// The complexity is O(log n) where n = h.Len().
-func (h *Heap[T]) Push(x T) {
-	n := len(h.buf)
-	h.buf = append(h.buf, x)
-	h.up(n)
-}
-
-// Pop removes and returns the minimum element (according to Less) from
-// the heap. The complexity is O(log n) where n = h.Len().
-func (h *Heap[T]) Pop() (T, bool) {
-	if len(h.buf) == 0 {
-		var zero T
-		return zero, false
-	}
-	x := h.buf[0]
-	last := h.buf[len(h.buf)-1]
-	h.buf = h.buf[:len(h.buf)-1]
-	if len(h.buf) > 0 {
-		h.down(0, last)
-	}
-	return x, true
-}
-
-func (h *Heap[T]) up(j int) {
-	x := h.buf[j]
-	for {
-		i := (j - 1) / 2 // parent
-		if i == j || h.compare(x, h.buf[i]) >= 0 {
-			break
-		}
-		h.buf[j] = h.buf[i]
-		j = i
-	}
-	h.buf[j] = x
-}
-
-func (h *Heap[T]) down(i int, x T) {
-	for {
-		j1 := 2*i + 1
-		if j1 >= len(h.buf) || j1 < 0 { // j1 < 0 after int overflow
-			break
-		}
-		j := j1 // left child
-		if j2 := j1 + 1; j2 < len(h.buf) && h.compare(h.buf[j2], h.buf[j1]) < 0 {
-			j = j2 // = 2*i + 2  // right child
-		}
-		if h.compare(x, h.buf[j]) <= 0 {
-			break
-		}
-		h.buf[i] = h.buf[j]
-		i = j
-	}
-	h.buf[i] = x
-}
diff --git a/heap/heap_test.go b/heap/heap_test.go
deleted file mode 100644
index afbc721..0000000
--- a/heap/heap_test.go
+++ /dev/null
@@ -1,72 +0,0 @@
-package heap
-
-import (
-	"cmp"
-	"testing"
-)
-
-func verify(t *testing.T, h *Heap[int], i int) {
-	t.Helper()
-
-	n := h.Len()
-	j1 := 2*i + 1
-	j2 := 2*i + 2
-	if j1 < n {
-		if h.compare(h.buf[j1], h.buf[i]) < 0 {
-			t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.buf[i], j1, h.buf[j1])
-			return
-		}
-		verify(t, h, j1)
-	}
-	if j2 < n {
-		if h.compare(h.buf[j2], h.buf[i]) < 0 {
-			t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.buf[i], j1, h.buf[j2])
-			return
-		}
-		verify(t, h, j2)
-	}
-}
-
-func Test(t *testing.T) {
-	t.Parallel()
-
-	h := New(cmp.Compare[int])
-	verify(t, h, 0)
-	h.Grow(20)
-	verify(t, h, 0)
-
-	for i := 20; i > 10; i-- {
-		h.Push(i)
-	}
-	verify(t, h, 0)
-
-	for i := 10; i > 0; i-- {
-		h.Push(i)
-		verify(t, h, 0)
-	}
-
-	for i := 1; h.Len() > 0; i++ {
-		x, ok := h.Pop()
-		if !ok {
-			t.Errorf("Pop() = false, want %d", i)
-		}
-		if i < 20 {
-			h.Push(20 + i)
-		}
-		verify(t, h, 0)
-		if x != i {
-			t.Errorf("%d.th pop got %d; want %d", i, x, i)
-		}
-	}
-}
-
-func TestPopEmpty(t *testing.T) {
-	t.Parallel()
-
-	h := New(cmp.Compare[int])
-	_, gotOk := h.Pop()
-	const want = false
-	if gotOk != want {
-		t.Errorf("Pop() on empty heap = %t, want %t", gotOk, want)
-	}
-}