From 9c9dc6b65c4b2775e0ba5686d43b0c224fd02836 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Tue, 15 Apr 2025 17:24:29 -0700 Subject: Just deque --- README.md | 14 ++- deque.go | 211 +++++++++++++++++++++++++++++++++++ deque/deque.go | 218 ------------------------------------ deque/deque_test.go | 299 -------------------------------------------------- deque/example_test.go | 156 -------------------------- deque_test.go | 299 ++++++++++++++++++++++++++++++++++++++++++++++++++ example_test.go | 156 ++++++++++++++++++++++++++ go.mod | 2 +- heap/example_test.go | 178 ------------------------------ heap/heap.go | 87 --------------- heap/heap_test.go | 72 ------------ 11 files changed, 675 insertions(+), 1017 deletions(-) create mode 100644 deque.go delete mode 100644 deque/deque.go delete mode 100644 deque/deque_test.go delete mode 100644 deque/example_test.go create mode 100644 deque_test.go create mode 100644 example_test.go delete mode 100644 heap/example_test.go delete mode 100644 heap/heap.go delete mode 100644 heap/heap_test.go 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.go b/deque.go new file mode 100644 index 0000000..e8a9018 --- /dev/null +++ b/deque.go @@ -0,0 +1,211 @@ +// 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. +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 deleted file mode 100644 index ace06f6..0000000 --- a/deque/deque.go +++ /dev/null @@ -1,218 +0,0 @@ -// 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 deleted file mode 100644 index 27ae232..0000000 --- a/deque/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/deque/example_test.go b/deque/example_test.go deleted file mode 100644 index 3e1ac80..0000000 --- a/deque/example_test.go +++ /dev/null @@ -1,156 +0,0 @@ -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 new file mode 100644 index 0000000..27ae232 --- /dev/null +++ b/deque_test.go @@ -0,0 +1,299 @@ +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/example_test.go b/example_test.go new file mode 100644 index 0000000..3e1ac80 --- /dev/null +++ b/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 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) - } -} -- cgit v1.3.1