Rebrand to github.com/rhogenson/container

I also added a heap package

8 files changed, 550 insertions, 2 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..0403f41
--- /dev/null
+++ b/README.md
@@ -0,0 +1,7 @@
+# container: the missing piece of the Go standard library
+
+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.
diff --git a/deque.go b/deque/deque.go
index e4f48d0..ace06f6 100644
--- a/deque.go
+++ b/deque/deque.go
@@ -1,10 +1,21 @@
 // Package deque implements a double-ended queue (deque) implemented with a
-// growable ring buffer.
+// slice-backed ring buffer.
 //
 // This queue has O(1) amortized inserts and removals from both ends of the
 // container. It also has O(1) indexing like a vector.
 //
+// The "default" usage of this type as a queue is to use [Deque.PushBack] to add
+// to the queue, and [Deque.PopFront] to remove from the queue. Iterating over
+// 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_test.go b/deque/deque_test.go
index 27ae232..b14e53d 100644
--- a/deque_test.go
+++ b/deque/deque_test.go
@@ -1,6 +1,7 @@
 package deque
 
 import (
+	"cmp"
 	"slices"
 	"testing"
 )
@@ -297,3 +298,39 @@ func TestString(t *testing.T) {
 		t.Errorf("%d: String() = %q, want %q", in, got, want)
 	}
 }
+
+const n = 10000
+
+func BenchmarkSort1(b *testing.B) {
+	q := WithCapacity[int](n)
+	for i := range n {
+		q.PushBack(n - i)
+	}
+	for range n / 2 {
+		q.PopFront()
+	}
+	for i := range n/2 - 500 {
+		q.PushBack(i)
+	}
+	b.ResetTimer()
+	for b.Loop() {
+		q.Sort1(cmp.Compare[int])
+	}
+}
+
+func BenchmarkSort2(b *testing.B) {
+	q := WithCapacity[int](n)
+	for i := range n {
+		q.PushBack(n - i)
+	}
+	for range n / 2 {
+		q.PopFront()
+	}
+	for i := range n/2 - 500 {
+		q.PushBack(i)
+	}
+	b.ResetTimer()
+	for b.Loop() {
+		q.Sort2(cmp.Compare[int])
+	}
+}
diff --git a/deque/example_test.go b/deque/example_test.go
new file mode 100644
index 0000000..3e1ac80
--- /dev/null
+++ b/deque/example_test.go
@@ -0,0 +1,156 @@
+package deque_test
+
+import (
+	"fmt"
+
+	"github.com/rhogenson/container/deque"
+)
+
+func ExampleDeque() {
+	q := new(deque.Deque[int])
+	for i := range 10 {
+		q.PushBack(i)
+	}
+	for range 3 {
+		q.PopFront()
+	}
+	fmt.Println(q)
+
+	// Output:
+	// [3 4 5 6 7 8 9]
+}
+
+func ExampleWithCapacity() {
+	q := deque.WithCapacity[int](10)
+	for i := range 100 {
+		if q.Len() == q.Cap() {
+			q.PopFront()
+		}
+		q.PushBack(i)
+	}
+	fmt.Println(q)
+
+	// Output:
+	// [90 91 92 93 94 95 96 97 98 99]
+}
+
+func ExampleFrom() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	fmt.Println(q.PopFront())
+
+	// Output:
+	// 1 true
+}
+
+func ExampleDeque_At() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	fmt.Println(q.At(3))
+
+	// Output:
+	// 4
+}
+
+func ExampleDeque_Cap() {
+	q := deque.WithCapacity[int](10)
+	q.PushBack(1, 2, 3, 4, 5)
+	fmt.Println(q.Cap())
+
+	// Output:
+	// 10
+}
+
+func ExampleDeque_Len() {
+	q := new(deque.Deque[int])
+	q.PushBack(1, 2, 3, 4, 5)
+	fmt.Println(q.Len())
+
+	// Output:
+	// 5
+}
+
+func ExampleDeque_PopFront() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	for range 3 {
+		q.PopFront()
+	}
+	fmt.Println(q)
+
+	// Output:
+	// [4 5]
+}
+
+func ExampleDeque_PopBack() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	for range 3 {
+		q.PopBack()
+	}
+	fmt.Println(q)
+
+	// Output:
+	// [1 2]
+}
+
+func ExampleDeque_PushFront() {
+	q := deque.From([]int{6, 7, 8, 9, 10})
+	q.PushFront(1, 2, 3, 4, 5)
+	fmt.Println(q)
+
+	// Output:
+	// [1 2 3 4 5 6 7 8 9 10]
+}
+
+func ExampleDeque_PushBack() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	q.PushBack(6, 7, 8, 9, 10)
+	fmt.Println(q)
+
+	// Output:
+	// [1 2 3 4 5 6 7 8 9 10]
+}
+
+func ExampleDeque_Reset() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	q.Reset()
+	fmt.Println(q.Cap())
+
+	// Output:
+	// 5
+}
+
+func ExampleDeque_Grow() {
+	q := new(deque.Deque[int])
+	q.Grow(5)
+	// PushBack will not allocate:
+	q.PushBack(1, 2, 3, 4, 5)
+}
+
+func ExampleDeque_All() {
+	q := new(deque.Deque[int])
+	q.PushBack(1, 2, 3, 4, 5)
+	q.PopFront()
+	for _, x := range q.All() {
+		fmt.Println(x)
+	}
+
+	// Output:
+	// 2
+	// 3
+	// 4
+	// 5
+}
+
+func ExampleDeque_PopAll() {
+	q := deque.From([]int{1, 2, 3, 4, 5})
+	for x := range q.PopAll() {
+		fmt.Println(x)
+	}
+	fmt.Println(q)
+
+	// Output:
+	// 1
+	// 2
+	// 3
+	// 4
+	// 5
+	// []
+}
diff --git a/go.mod b/go.mod
index 98a3cfc..376dd83 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,3 @@
-module gitlab.com/rhogenson/deque
+module github.com/rhogenson/container
 
 go 1.24.1
diff --git a/heap/example_test.go b/heap/example_test.go
new file mode 100644
index 0000000..f8ea7d8
--- /dev/null
+++ b/heap/example_test.go
@@ -0,0 +1,178 @@
+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
new file mode 100644
index 0000000..612d5a8
--- /dev/null
+++ b/heap/heap.go
@@ -0,0 +1,87 @@
+// 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
new file mode 100644
index 0000000..afbc721
--- /dev/null
+++ b/heap/heap_test.go
@@ -0,0 +1,72 @@
+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)
+	}
+}