diff options
| -rw-r--r-- | README.md | 7 | ||||
| -rw-r--r-- | deque/deque.go (renamed from deque.go) | 13 | ||||
| -rw-r--r-- | deque/deque_test.go (renamed from deque_test.go) | 37 | ||||
| -rw-r--r-- | deque/example_test.go | 156 | ||||
| -rw-r--r-- | go.mod | 2 | ||||
| -rw-r--r-- | heap/example_test.go | 178 | ||||
| -rw-r--r-- | heap/heap.go | 87 | ||||
| -rw-r--r-- | heap/heap_test.go | 72 |
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 + // [] +} @@ -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) + } +} |