From b3ce67680f630c31bf715447c604019682c9c9ce Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sat, 12 Apr 2025 17:43:42 -0700 Subject: Rebrand to github.com/rhogenson/container I also added a heap package --- README.md | 7 ++ deque.go | 207 ------------------------------- deque/deque.go | 218 ++++++++++++++++++++++++++++++++ deque/deque_test.go | 336 ++++++++++++++++++++++++++++++++++++++++++++++++++ deque/example_test.go | 156 +++++++++++++++++++++++ deque_test.go | 299 -------------------------------------------- go.mod | 2 +- heap/example_test.go | 178 ++++++++++++++++++++++++++ heap/heap.go | 87 +++++++++++++ heap/heap_test.go | 72 +++++++++++ 10 files changed, 1055 insertions(+), 507 deletions(-) create mode 100644 README.md delete mode 100644 deque.go create mode 100644 deque/deque.go create mode 100644 deque/deque_test.go create mode 100644 deque/example_test.go delete mode 100644 deque_test.go create mode 100644 heap/example_test.go create mode 100644 heap/heap.go create mode 100644 heap/heap_test.go 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.go deleted file mode 100644 index e4f48d0..0000000 --- a/deque.go +++ /dev/null @@ -1,207 +0,0 @@ -// Package deque implements a double-ended queue (deque) implemented with a -// growable 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 core implementation is "ported" (stolen) from Rust's VecDeque. -package deque - -import ( - "fmt" - "iter" - "slices" - "strings" -) - -// Deque is a double-ended queue. The zero value is ready for use. -type Deque[T any] struct { - head int - buf []T -} - -// WithCapacity allocates a deque with the given capacity. -func WithCapacity[T any](cap int) *Deque[T] { - return &Deque[T]{buf: make([]T, 0, cap)} -} - -// From creates a new queue using the given slice as the backing buffer. -func From[S ~[]T, T any](slice S) *Deque[T] { - return &Deque[T]{buf: slice} -} - -func (q *Deque[T]) wrapAdd(i, addend int) int { - i += addend - if i >= cap(q.buf) { - return i - cap(q.buf) - } - return i -} - -func (q *Deque[T]) toPhysicalIdx(i int) int { - return q.wrapAdd(q.head, i) -} - -// At returns the item at position i. At panics if i < 0 or i >= q.Len(). -func (q *Deque[T]) At(i int) T { - if !(0 <= i && i < len(q.buf)) { - panic(fmt.Sprintf("index out of range [%d] with length %d", i, len(q.buf))) - } - return q.buf[:cap(q.buf)][q.toPhysicalIdx(i)] -} - -// Cap returns the number of elements the deque can hold without reallocating. -func (q *Deque[T]) Cap() int { - return cap(q.buf) -} - -// Len returns the number of elements in the deque. -func (q *Deque[T]) Len() int { - return len(q.buf) -} - -// PopFront removes and returns the item at index 0 if the deque is non-empty. -func (q *Deque[T]) PopFront() (T, bool) { - if len(q.buf) == 0 { - var zero T - return zero, false - } - oldHead := q.head - q.head = q.toPhysicalIdx(1) - q.buf = q.buf[:len(q.buf)-1] - return q.buf[:cap(q.buf)][oldHead], true -} - -// PopBack removes and returns the last item in the deque if it is non-empty. -func (q *Deque[T]) PopBack() (T, bool) { - if len(q.buf) == 0 { - var zero T - return zero, false - } - q.buf = q.buf[:len(q.buf)-1] - return q.buf[:cap(q.buf)][q.toPhysicalIdx(len(q.buf))], true -} - -// PushFront prepends the given items to the front of the deque. -func (q *Deque[T]) PushFront(values ...T) { - q.Grow(len(values)) - q.buf = q.buf[:len(q.buf)+len(values)] - if q.head >= len(values) { - newHead := q.head - len(values) - copy(q.buf[newHead:q.head], values) - q.head = newHead - } else { - tailLen := len(values) - q.head - copy(q.buf[:q.head], values[tailLen:]) - copy(q.buf[cap(q.buf)-tailLen:cap(q.buf)], values[:tailLen]) - q.head = cap(q.buf) - tailLen - } -} - -// PushBack appends the given items to the back of the deque. -func (q *Deque[T]) PushBack(values ...T) { - q.Grow(len(values)) - endIdx := q.wrapAdd(q.head, len(q.buf)) - if len(values) <= cap(q.buf)-endIdx { - copy(q.buf[endIdx:endIdx+len(values)], values) - } else { - headLen := cap(q.buf) - endIdx - copy(q.buf[endIdx:cap(q.buf)], values[:headLen]) - copy(q.buf[:len(values)-headLen], values[headLen:]) - } - q.buf = q.buf[:len(q.buf)+len(values)] -} - -// Reset empties the deque, retaining the underlying storage for use by -// future pushes. -func (q *Deque[T]) Reset() { - q.buf = q.buf[:0] -} - -// Grow makes space for at least n more elements to be inserted in the given -// deque without reallocation. -func (q *Deque[T]) Grow(n int) { - if n <= cap(q.buf)-len(q.buf) { - return - } - - oldCap := cap(q.buf) - q.buf = slices.Grow(q.buf, n) - newCap := cap(q.buf) - - // Move the shortest contiguous section of the ring buffer - // - // H := head - // L := last element (`self.to_physical_idx(self.len - 1)`) - // - // H L - // [o o o o o o o o ] - // H L - // A [o o o o o o o o . . . . . . . . ] - // L H - // [o o o o o o o o ] - // H L - // B [. . . o o o o o o o o . . . . . ] - // L H - // [o o o o o o o o ] - // L H - // C [o o o o o o . . . . . . . . o o ] - - if q.head <= oldCap-len(q.buf) { - // A - return - } - headLen := oldCap - q.head - tailLen := len(q.buf) - headLen - if headLen > tailLen && newCap-oldCap >= tailLen { - // B - copy(q.buf[oldCap:oldCap+tailLen], q.buf[:tailLen]) - return - } - // C - newHead := newCap - headLen - copy(q.buf[newHead:newHead+headLen], q.buf[q.head:q.head+headLen]) - q.head = newHead -} - -// All returns an iterator over the elements in the deque. It does not pop -// any elements. -func (q *Deque[T]) All() iter.Seq2[int, T] { - return func(yield func(int, T) bool) { - // Don't use range over int in case the length changes while - // we're iterating - for i := 0; i < len(q.buf); i++ { - if !yield(i, q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) { - return - } - } - } -} - -// PopAll empties the deque and returns an iterator over the popped elements. -// It's not safe to modify the deque while iterating using PopAll. -func (q *Deque[T]) PopAll() iter.Seq[T] { - n := len(q.buf) - q.buf = q.buf[:0] - return func(yield func(T) bool) { - for i := range n { - if !yield(q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) { - return - } - } - } -} - -// String displays the deque as a string, using fmt.Sprint to show each element. -func (q *Deque[T]) String() string { - buf := new(strings.Builder) - buf.WriteString("[") - for i := range len(q.buf) { - if i > 0 { - buf.WriteString(" ") - } - fmt.Fprint(buf, q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) - } - buf.WriteString("]") - return buf.String() -} diff --git a/deque/deque.go b/deque/deque.go new file mode 100644 index 0000000..ace06f6 --- /dev/null +++ b/deque/deque.go @@ -0,0 +1,218 @@ +// Package deque implements a double-ended queue (deque) implemented with a +// 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 ( + "fmt" + "iter" + "slices" + "strings" +) + +// Deque is a double-ended queue. The zero value is ready for use. +type Deque[T any] struct { + head int + buf []T +} + +// WithCapacity allocates a deque with the given capacity. +func WithCapacity[T any](cap int) *Deque[T] { + return &Deque[T]{buf: make([]T, 0, cap)} +} + +// From creates a new queue using the given slice as the backing buffer. +func From[S ~[]T, T any](slice S) *Deque[T] { + return &Deque[T]{buf: slice} +} + +func (q *Deque[T]) wrapAdd(i, addend int) int { + i += addend + if i >= cap(q.buf) { + return i - cap(q.buf) + } + return i +} + +func (q *Deque[T]) toPhysicalIdx(i int) int { + return q.wrapAdd(q.head, i) +} + +// At returns the item at position i. At panics if i < 0 or i >= q.Len(). +func (q *Deque[T]) At(i int) T { + if !(0 <= i && i < len(q.buf)) { + panic(fmt.Sprintf("index out of range [%d] with length %d", i, len(q.buf))) + } + return q.buf[:cap(q.buf)][q.toPhysicalIdx(i)] +} + +// Cap returns the number of elements the deque can hold without reallocating. +func (q *Deque[T]) Cap() int { + return cap(q.buf) +} + +// Len returns the number of elements in the deque. +func (q *Deque[T]) Len() int { + return len(q.buf) +} + +// PopFront removes and returns the item at index 0 if the deque is non-empty. +func (q *Deque[T]) PopFront() (T, bool) { + if len(q.buf) == 0 { + var zero T + return zero, false + } + oldHead := q.head + q.head = q.toPhysicalIdx(1) + q.buf = q.buf[:len(q.buf)-1] + return q.buf[:cap(q.buf)][oldHead], true +} + +// PopBack removes and returns the last item in the deque if it is non-empty. +func (q *Deque[T]) PopBack() (T, bool) { + if len(q.buf) == 0 { + var zero T + return zero, false + } + q.buf = q.buf[:len(q.buf)-1] + return q.buf[:cap(q.buf)][q.toPhysicalIdx(len(q.buf))], true +} + +// PushFront prepends the given items to the front of the deque. +func (q *Deque[T]) PushFront(values ...T) { + q.Grow(len(values)) + q.buf = q.buf[:len(q.buf)+len(values)] + if q.head >= len(values) { + newHead := q.head - len(values) + copy(q.buf[newHead:q.head], values) + q.head = newHead + } else { + tailLen := len(values) - q.head + copy(q.buf[:q.head], values[tailLen:]) + copy(q.buf[cap(q.buf)-tailLen:cap(q.buf)], values[:tailLen]) + q.head = cap(q.buf) - tailLen + } +} + +// PushBack appends the given items to the back of the deque. +func (q *Deque[T]) PushBack(values ...T) { + q.Grow(len(values)) + endIdx := q.wrapAdd(q.head, len(q.buf)) + if len(values) <= cap(q.buf)-endIdx { + copy(q.buf[endIdx:endIdx+len(values)], values) + } else { + headLen := cap(q.buf) - endIdx + copy(q.buf[endIdx:cap(q.buf)], values[:headLen]) + copy(q.buf[:len(values)-headLen], values[headLen:]) + } + q.buf = q.buf[:len(q.buf)+len(values)] +} + +// Reset empties the deque, retaining the underlying storage for use by +// future pushes. +func (q *Deque[T]) Reset() { + q.buf = q.buf[:0] +} + +// Grow makes space for at least n more elements to be inserted in the given +// deque without reallocation. +func (q *Deque[T]) Grow(n int) { + if n <= cap(q.buf)-len(q.buf) { + return + } + + oldCap := cap(q.buf) + q.buf = slices.Grow(q.buf, n) + newCap := cap(q.buf) + + // Move the shortest contiguous section of the ring buffer + // + // H := head + // L := last element (`self.to_physical_idx(self.len - 1)`) + // + // H L + // [o o o o o o o o ] + // H L + // A [o o o o o o o o . . . . . . . . ] + // L H + // [o o o o o o o o ] + // H L + // B [. . . o o o o o o o o . . . . . ] + // L H + // [o o o o o o o o ] + // L H + // C [o o o o o o . . . . . . . . o o ] + + if q.head <= oldCap-len(q.buf) { + // A + return + } + headLen := oldCap - q.head + tailLen := len(q.buf) - headLen + if headLen > tailLen && newCap-oldCap >= tailLen { + // B + copy(q.buf[oldCap:oldCap+tailLen], q.buf[:tailLen]) + return + } + // C + newHead := newCap - headLen + copy(q.buf[newHead:newHead+headLen], q.buf[q.head:q.head+headLen]) + q.head = newHead +} + +// All returns an iterator over the elements in the deque. It does not pop +// any elements. +func (q *Deque[T]) All() iter.Seq2[int, T] { + return func(yield func(int, T) bool) { + // Don't use range over int in case the length changes while + // we're iterating + for i := 0; i < len(q.buf); i++ { + if !yield(i, q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) { + return + } + } + } +} + +// PopAll empties the deque and returns an iterator over the popped elements. +// It's not safe to modify the deque while iterating using PopAll. +func (q *Deque[T]) PopAll() iter.Seq[T] { + n := len(q.buf) + q.buf = q.buf[:0] + return func(yield func(T) bool) { + for i := range n { + if !yield(q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) { + return + } + } + } +} + +// String displays the deque as a string, using fmt.Sprint to show each element. +func (q *Deque[T]) String() string { + buf := new(strings.Builder) + buf.WriteString("[") + for i := range len(q.buf) { + if i > 0 { + buf.WriteString(" ") + } + fmt.Fprint(buf, q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) + } + buf.WriteString("]") + return buf.String() +} diff --git a/deque/deque_test.go b/deque/deque_test.go new file mode 100644 index 0000000..b14e53d --- /dev/null +++ b/deque/deque_test.go @@ -0,0 +1,336 @@ +package deque + +import ( + "cmp" + "slices" + "testing" +) + +func TestWithCapacity(t *testing.T) { + t.Parallel() + + const cap = 10 + q := WithCapacity[int](cap) + for i := range cap { + q.PushBack(i) + } + if got := q.Cap(); got != cap { + t.Errorf("Cap() = %d, want %d", got, cap) + } +} + +func TestAt(t *testing.T) { + t.Parallel() + + q := new(Deque[int]) + for i := range 10 { + q.PushBack(i) + } + for i := range 3 { + if got := q.At(i); got != i { + t.Errorf("At(%d) = %d, want %d", i, got, i) + } + } +} + +func TestPopFront(t *testing.T) { + t.Parallel() + + for _, tc := range []struct { + desc string + in []int + wantOk bool + wantVal int + wantContents []int + }{{ + desc: "PopVal", + in: []int{1, 2, 3}, + wantOk: true, + wantVal: 1, + wantContents: []int{2, 3}, + }, { + desc: "PopNone", + in: nil, + wantOk: false, + }} { + t.Run(tc.desc, func(t *testing.T) { + t.Parallel() + + q := From(tc.in) + got, ok := q.PopFront() + if ok != tc.wantOk { + t.Errorf("%d: PopFront() returned ok = %t, want %t", tc.in, ok, tc.wantOk) + } + if got != tc.wantVal { + t.Errorf("%d: PopFront() = %d, want %d", tc.in, got, tc.wantVal) + } + gotContents := make([]int, q.Len()) + for i, x := range q.All() { + gotContents[i] = x + } + if !slices.Equal(gotContents, tc.wantContents) { + t.Errorf("%d: Contents after PopFront are %d, want %d", tc.in, gotContents, tc.wantContents) + } + }) + } +} + +func TestPopBack(t *testing.T) { + t.Parallel() + + for _, tc := range []struct { + desc string + in []int + wantOk bool + wantVal int + wantContents []int + }{{ + desc: "PopVal", + in: []int{1, 2, 3}, + wantOk: true, + wantVal: 3, + wantContents: []int{1, 2}, + }, { + desc: "PopNone", + in: nil, + wantOk: false, + }} { + t.Run(tc.desc, func(t *testing.T) { + t.Parallel() + + q := From(tc.in) + got, ok := q.PopBack() + if ok != tc.wantOk { + t.Errorf("%d: PopBack() returned ok = %t, want %t", tc.in, ok, tc.wantOk) + } + if got != tc.wantVal { + t.Errorf("%d: PopBack() = %d, want %d", tc.in, got, tc.wantVal) + } + gotContents := make([]int, q.Len()) + for i, x := range q.All() { + gotContents[i] = x + } + if !slices.Equal(gotContents, tc.wantContents) { + t.Errorf("%d: Contents after PopBack are %d, want %d", tc.in, gotContents, tc.wantContents) + } + }) + } +} + +func TestPushFront(t *testing.T) { + t.Parallel() + + for _, tc := range []struct { + desc string + prevContent []int + push []int + want []int + }{{ + desc: "PushNil", + prevContent: nil, + push: []int{1}, + want: []int{1}, + }, { + desc: "PushExisting", + prevContent: []int{1, 2, 3}, + push: []int{4, 5, 6}, + want: []int{4, 5, 6, 1, 2, 3}, + }} { + t.Run(tc.desc, func(t *testing.T) { + t.Parallel() + + q := From(tc.prevContent) + q.PushFront(tc.push...) + got := make([]int, q.Len()) + for i, x := range q.All() { + got[i] = x + } + if !slices.Equal(got, tc.want) { + t.Errorf("%d: PushFront(%d) = %d, want %d", tc.prevContent, tc.push, got, tc.want) + } + }) + } +} + +func TestPushBack(t *testing.T) { + t.Parallel() + + for _, tc := range []struct { + desc string + prevContent []int + push []int + want []int + }{{ + desc: "PushNil", + prevContent: nil, + push: []int{1}, + want: []int{1}, + }, { + desc: "PushExisting", + prevContent: []int{1, 2, 3}, + push: []int{4, 5, 6}, + want: []int{1, 2, 3, 4, 5, 6}, + }} { + t.Run(tc.desc, func(t *testing.T) { + t.Parallel() + + q := From(tc.prevContent) + q.PushBack(tc.push...) + got := make([]int, q.Len()) + for i, x := range q.All() { + got[i] = x + } + if !slices.Equal(got, tc.want) { + t.Errorf("%d: PushBack(%d) = %d, want %d", tc.prevContent, tc.push, got, tc.want) + } + }) + } +} + +func TestPopFrontPushBackB(t *testing.T) { + t.Parallel() + + q := From([]int{1, 2, 3}) + q.PopFront() + q.PushBack(4) + q.PushBack(5) + got := make([]int, q.Len()) + for i, x := range q.All() { + got[i] = x + } + want := []int{2, 3, 4, 5} + if !slices.Equal(got, want) { + t.Errorf("Contents = %d, want %d", got, want) + } +} + +func TestPopFrontPushBackC(t *testing.T) { + t.Parallel() + + q := From([]int{1, 2, 3}) + q.PopFront() + q.PopFront() + q.PushBack(4) + q.PushBack(5) + q.PushBack(6) + got := make([]int, q.Len()) + for i, x := range q.All() { + got[i] = x + } + want := []int{3, 4, 5, 6} + if !slices.Equal(got, want) { + t.Errorf("Contents = %d, want %d", got, want) + } +} + +func TestPopFrontPushFront(t *testing.T) { + t.Parallel() + + q := From([]int{1, 2, 3}) + q.PopFront() + q.PopFront() + q.PushFront(4, 5) + if got, want := q.Cap(), 3; got != want { + t.Errorf("Cap() = %d, want %d", got, want) + } + got := make([]int, q.Len()) + for i, x := range q.All() { + got[i] = x + } + want := []int{4, 5, 3} + if !slices.Equal(got, want) { + t.Errorf("Contents = %d, want %d", got, want) + } +} + +func TestReset(t *testing.T) { + t.Parallel() + + q := From([]int{1, 2, 3, 4, 5}) + q.Reset() + if got, want := q.Len(), 0; got != want { + t.Errorf("After Reset() Len() = %d, want %d", got, want) + } + if got, want := q.Cap(), 5; got != want { + t.Errorf("After Reset() Cap() = %d, want %d", got, want) + } +} + +func TestPopAll(t *testing.T) { + t.Parallel() + + for _, tc := range []struct { + desc string + content []int + }{{ + desc: "PopAll", + content: []int{1, 2, 3}, + }, { + desc: "PopAllEmpty", + content: make([]int, 0, 3), + }} { + t.Run(tc.desc, func(t *testing.T) { + t.Parallel() + + q := From(tc.content) + got := make([]int, 0, q.Len()) + for x := range q.PopAll() { + got = append(got, x) + } + if got, want := q.Len(), 0; got != want { + t.Errorf("Len() = %d, want %d", got, want) + } + if !slices.Equal(got, tc.content) { + t.Errorf("PopAll() returned values %d, want %d", got, tc.content) + } + }) + } +} + +func TestString(t *testing.T) { + t.Parallel() + + in := []int{1, 2, 3, 4, 5} + q := From(in) + const want = "[1 2 3 4 5]" + got := q.String() + if got != want { + 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/deque_test.go b/deque_test.go deleted file mode 100644 index 27ae232..0000000 --- a/deque_test.go +++ /dev/null @@ -1,299 +0,0 @@ -package deque - -import ( - "slices" - "testing" -) - -func TestWithCapacity(t *testing.T) { - t.Parallel() - - const cap = 10 - q := WithCapacity[int](cap) - for i := range cap { - q.PushBack(i) - } - if got := q.Cap(); got != cap { - t.Errorf("Cap() = %d, want %d", got, cap) - } -} - -func TestAt(t *testing.T) { - t.Parallel() - - q := new(Deque[int]) - for i := range 10 { - q.PushBack(i) - } - for i := range 3 { - if got := q.At(i); got != i { - t.Errorf("At(%d) = %d, want %d", i, got, i) - } - } -} - -func TestPopFront(t *testing.T) { - t.Parallel() - - for _, tc := range []struct { - desc string - in []int - wantOk bool - wantVal int - wantContents []int - }{{ - desc: "PopVal", - in: []int{1, 2, 3}, - wantOk: true, - wantVal: 1, - wantContents: []int{2, 3}, - }, { - desc: "PopNone", - in: nil, - wantOk: false, - }} { - t.Run(tc.desc, func(t *testing.T) { - t.Parallel() - - q := From(tc.in) - got, ok := q.PopFront() - if ok != tc.wantOk { - t.Errorf("%d: PopFront() returned ok = %t, want %t", tc.in, ok, tc.wantOk) - } - if got != tc.wantVal { - t.Errorf("%d: PopFront() = %d, want %d", tc.in, got, tc.wantVal) - } - gotContents := make([]int, q.Len()) - for i, x := range q.All() { - gotContents[i] = x - } - if !slices.Equal(gotContents, tc.wantContents) { - t.Errorf("%d: Contents after PopFront are %d, want %d", tc.in, gotContents, tc.wantContents) - } - }) - } -} - -func TestPopBack(t *testing.T) { - t.Parallel() - - for _, tc := range []struct { - desc string - in []int - wantOk bool - wantVal int - wantContents []int - }{{ - desc: "PopVal", - in: []int{1, 2, 3}, - wantOk: true, - wantVal: 3, - wantContents: []int{1, 2}, - }, { - desc: "PopNone", - in: nil, - wantOk: false, - }} { - t.Run(tc.desc, func(t *testing.T) { - t.Parallel() - - q := From(tc.in) - got, ok := q.PopBack() - if ok != tc.wantOk { - t.Errorf("%d: PopBack() returned ok = %t, want %t", tc.in, ok, tc.wantOk) - } - if got != tc.wantVal { - t.Errorf("%d: PopBack() = %d, want %d", tc.in, got, tc.wantVal) - } - gotContents := make([]int, q.Len()) - for i, x := range q.All() { - gotContents[i] = x - } - if !slices.Equal(gotContents, tc.wantContents) { - t.Errorf("%d: Contents after PopBack are %d, want %d", tc.in, gotContents, tc.wantContents) - } - }) - } -} - -func TestPushFront(t *testing.T) { - t.Parallel() - - for _, tc := range []struct { - desc string - prevContent []int - push []int - want []int - }{{ - desc: "PushNil", - prevContent: nil, - push: []int{1}, - want: []int{1}, - }, { - desc: "PushExisting", - prevContent: []int{1, 2, 3}, - push: []int{4, 5, 6}, - want: []int{4, 5, 6, 1, 2, 3}, - }} { - t.Run(tc.desc, func(t *testing.T) { - t.Parallel() - - q := From(tc.prevContent) - q.PushFront(tc.push...) - got := make([]int, q.Len()) - for i, x := range q.All() { - got[i] = x - } - if !slices.Equal(got, tc.want) { - t.Errorf("%d: PushFront(%d) = %d, want %d", tc.prevContent, tc.push, got, tc.want) - } - }) - } -} - -func TestPushBack(t *testing.T) { - t.Parallel() - - for _, tc := range []struct { - desc string - prevContent []int - push []int - want []int - }{{ - desc: "PushNil", - prevContent: nil, - push: []int{1}, - want: []int{1}, - }, { - desc: "PushExisting", - prevContent: []int{1, 2, 3}, - push: []int{4, 5, 6}, - want: []int{1, 2, 3, 4, 5, 6}, - }} { - t.Run(tc.desc, func(t *testing.T) { - t.Parallel() - - q := From(tc.prevContent) - q.PushBack(tc.push...) - got := make([]int, q.Len()) - for i, x := range q.All() { - got[i] = x - } - if !slices.Equal(got, tc.want) { - t.Errorf("%d: PushBack(%d) = %d, want %d", tc.prevContent, tc.push, got, tc.want) - } - }) - } -} - -func TestPopFrontPushBackB(t *testing.T) { - t.Parallel() - - q := From([]int{1, 2, 3}) - q.PopFront() - q.PushBack(4) - q.PushBack(5) - got := make([]int, q.Len()) - for i, x := range q.All() { - got[i] = x - } - want := []int{2, 3, 4, 5} - if !slices.Equal(got, want) { - t.Errorf("Contents = %d, want %d", got, want) - } -} - -func TestPopFrontPushBackC(t *testing.T) { - t.Parallel() - - q := From([]int{1, 2, 3}) - q.PopFront() - q.PopFront() - q.PushBack(4) - q.PushBack(5) - q.PushBack(6) - got := make([]int, q.Len()) - for i, x := range q.All() { - got[i] = x - } - want := []int{3, 4, 5, 6} - if !slices.Equal(got, want) { - t.Errorf("Contents = %d, want %d", got, want) - } -} - -func TestPopFrontPushFront(t *testing.T) { - t.Parallel() - - q := From([]int{1, 2, 3}) - q.PopFront() - q.PopFront() - q.PushFront(4, 5) - if got, want := q.Cap(), 3; got != want { - t.Errorf("Cap() = %d, want %d", got, want) - } - got := make([]int, q.Len()) - for i, x := range q.All() { - got[i] = x - } - want := []int{4, 5, 3} - if !slices.Equal(got, want) { - t.Errorf("Contents = %d, want %d", got, want) - } -} - -func TestReset(t *testing.T) { - t.Parallel() - - q := From([]int{1, 2, 3, 4, 5}) - q.Reset() - if got, want := q.Len(), 0; got != want { - t.Errorf("After Reset() Len() = %d, want %d", got, want) - } - if got, want := q.Cap(), 5; got != want { - t.Errorf("After Reset() Cap() = %d, want %d", got, want) - } -} - -func TestPopAll(t *testing.T) { - t.Parallel() - - for _, tc := range []struct { - desc string - content []int - }{{ - desc: "PopAll", - content: []int{1, 2, 3}, - }, { - desc: "PopAllEmpty", - content: make([]int, 0, 3), - }} { - t.Run(tc.desc, func(t *testing.T) { - t.Parallel() - - q := From(tc.content) - got := make([]int, 0, q.Len()) - for x := range q.PopAll() { - got = append(got, x) - } - if got, want := q.Len(), 0; got != want { - t.Errorf("Len() = %d, want %d", got, want) - } - if !slices.Equal(got, tc.content) { - t.Errorf("PopAll() returned values %d, want %d", got, tc.content) - } - }) - } -} - -func TestString(t *testing.T) { - t.Parallel() - - in := []int{1, 2, 3, 4, 5} - q := From(in) - const want = "[1 2 3 4 5]" - got := q.String() - if got != want { - t.Errorf("%d: String() = %q, want %q", in, got, want) - } -} 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) + } +} -- cgit v1.3.1