From 207aa7e7f6280ba3b89d8096685052eded6f4d45 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sun, 6 Apr 2025 09:14:00 -0700 Subject: Rename to deque --- deque.go | 196 ++++++++++++++++++++++++++++++++++++ deque_test.go | 299 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ vecdeque.go | 196 ------------------------------------ vecdeque_test.go | 299 ------------------------------------------------------- 4 files changed, 495 insertions(+), 495 deletions(-) create mode 100644 deque.go create mode 100644 deque_test.go delete mode 100644 vecdeque.go delete mode 100644 vecdeque_test.go diff --git a/deque.go b/deque.go new file mode 100644 index 0000000..5d6cc92 --- /dev/null +++ b/deque.go @@ -0,0 +1,196 @@ +// Package vecdeque 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. +package vecdeque + +// DQ is a double-ended queue. The zero value is ready for use. +type DQ[T any] struct { + head int + buf []T +} + +// WithCapacity allocates a deque with the given capacity. +func WithCapacity[T any](cap int) *DQ[T] { + return &DQ[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) *DQ[T] { + return &DQ[T]{buf: slice} +} + +func (q *DQ[T]) wrapAdd(i, addend int) int { + i += addend + if i >= cap(q.buf) { + return i - cap(q.buf) + } + return i +} + +func (q *DQ[T]) toPhysicalIdx(i int) int { + return q.wrapAdd(q.head, i) +} + +// Get returns the item at position i. +func (q *DQ[T]) Get(i int) T { + return q.buf[:cap(q.buf)][q.toPhysicalIdx(i)] +} + +// Cap returns the number of elements the deque can hold without reallocating. +func (q *DQ[T]) Cap() int { + return cap(q.buf) +} + +// Len returns the number of elements in the deque. +func (q *DQ[T]) Len() int { + return len(q.buf) +} + +// PopFront removes and returns the item at index 0 if the deque is non-empty. +func (q *DQ[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 *DQ[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.Get(len(q.buf)), true +} + +// PushFront prepends the given items to the front of the deque. +func (q *DQ[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 *DQ[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 *DQ[T]) Reset() { + q.buf = q.buf[:0] +} + +// AvailableBuffer returns an empty slice with q.Cap()-q.Len() capacity. This +// slice is intended to be appended to and passed to an immediately succeeding +// DQ.PushBack call. The slice is only valid until the next push operation on q. +func (q *DQ[T]) AvailableBuffer() []T { + endIdx := q.toPhysicalIdx(len(q.buf)) + if endIdx <= q.head { + return q.buf[endIdx:endIdx:q.head] + } + return q.buf[endIdx:endIdx] +} + +// Grow makes space for at least n more elements to be inserted in the given +// deque without reallocation. +func (q *DQ[T]) Grow(n int) { + n -= cap(q.buf) - len(q.buf) + if n <= 0 { + return + } + + oldCap := cap(q.buf) + q.buf = append(q.buf[:cap(q.buf)], make([]T, n)...)[:len(q.buf)] + 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 *DQ[T]) All() func(func(int, T) bool) { + return func(yield func(int, T) bool) { + for i := range len(q.buf) { + if !yield(i, q.Get(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 *DQ[T]) PopAll() func(func(T) bool) { + n := len(q.buf) + q.buf = q.buf[:0] + return func(yield func(T) bool) { + endIdx := q.toPhysicalIdx(n) + for i := q.head; ; { + if !yield(q.buf[:cap(q.buf)][i]) { + return + } + i = q.wrapAdd(i, 1) + if i == endIdx { + break + } + } + } +} diff --git a/deque_test.go b/deque_test.go new file mode 100644 index 0000000..a66fff4 --- /dev/null +++ b/deque_test.go @@ -0,0 +1,299 @@ +package vecdeque + +import ( + "bytes" + "fmt" + "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 TestGet(t *testing.T) { + t.Parallel() + + q := new(DQ[int]) + for i := range 10 { + q.PushBack(i) + } + for i := range 3 { + if got := q.Get(i); got != i { + t.Errorf("Get(%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() + + q := From([]int{1, 2, 3}) + 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) + } + want := []int{1, 2, 3} + if !slices.Equal(got, want) { + t.Errorf("PopAll() returned values %d, want %d", got, want) + } +} + +func TestAvailableBuffer(t *testing.T) { + t.Parallel() + + const cap = 10 + q := WithCapacity[byte](cap) + q.PushBack(append(q.AvailableBuffer(), []byte(" ")...)...) + q.PushBack(fmt.Appendf(q.AvailableBuffer(), "%d", 12345)...) + for range 5 { + q.PopFront() + } + q.PushBack(fmt.Appendf(q.AvailableBuffer(), "%d", 67890)...) + if got, want := q.Cap(), cap; got != want { + t.Errorf("Cap() = %d, want %d", got, want) + } + got := make([]byte, q.Len()) + for i, x := range q.All() { + got[i] = x + } + want := []byte("1234567890") + if !bytes.Equal(got, want) { + t.Errorf("Incorrect content after appending to AvailableBuffer, got %d want %d", got, want) + } +} diff --git a/vecdeque.go b/vecdeque.go deleted file mode 100644 index 5d6cc92..0000000 --- a/vecdeque.go +++ /dev/null @@ -1,196 +0,0 @@ -// Package vecdeque 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. -package vecdeque - -// DQ is a double-ended queue. The zero value is ready for use. -type DQ[T any] struct { - head int - buf []T -} - -// WithCapacity allocates a deque with the given capacity. -func WithCapacity[T any](cap int) *DQ[T] { - return &DQ[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) *DQ[T] { - return &DQ[T]{buf: slice} -} - -func (q *DQ[T]) wrapAdd(i, addend int) int { - i += addend - if i >= cap(q.buf) { - return i - cap(q.buf) - } - return i -} - -func (q *DQ[T]) toPhysicalIdx(i int) int { - return q.wrapAdd(q.head, i) -} - -// Get returns the item at position i. -func (q *DQ[T]) Get(i int) T { - return q.buf[:cap(q.buf)][q.toPhysicalIdx(i)] -} - -// Cap returns the number of elements the deque can hold without reallocating. -func (q *DQ[T]) Cap() int { - return cap(q.buf) -} - -// Len returns the number of elements in the deque. -func (q *DQ[T]) Len() int { - return len(q.buf) -} - -// PopFront removes and returns the item at index 0 if the deque is non-empty. -func (q *DQ[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 *DQ[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.Get(len(q.buf)), true -} - -// PushFront prepends the given items to the front of the deque. -func (q *DQ[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 *DQ[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 *DQ[T]) Reset() { - q.buf = q.buf[:0] -} - -// AvailableBuffer returns an empty slice with q.Cap()-q.Len() capacity. This -// slice is intended to be appended to and passed to an immediately succeeding -// DQ.PushBack call. The slice is only valid until the next push operation on q. -func (q *DQ[T]) AvailableBuffer() []T { - endIdx := q.toPhysicalIdx(len(q.buf)) - if endIdx <= q.head { - return q.buf[endIdx:endIdx:q.head] - } - return q.buf[endIdx:endIdx] -} - -// Grow makes space for at least n more elements to be inserted in the given -// deque without reallocation. -func (q *DQ[T]) Grow(n int) { - n -= cap(q.buf) - len(q.buf) - if n <= 0 { - return - } - - oldCap := cap(q.buf) - q.buf = append(q.buf[:cap(q.buf)], make([]T, n)...)[:len(q.buf)] - 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 *DQ[T]) All() func(func(int, T) bool) { - return func(yield func(int, T) bool) { - for i := range len(q.buf) { - if !yield(i, q.Get(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 *DQ[T]) PopAll() func(func(T) bool) { - n := len(q.buf) - q.buf = q.buf[:0] - return func(yield func(T) bool) { - endIdx := q.toPhysicalIdx(n) - for i := q.head; ; { - if !yield(q.buf[:cap(q.buf)][i]) { - return - } - i = q.wrapAdd(i, 1) - if i == endIdx { - break - } - } - } -} diff --git a/vecdeque_test.go b/vecdeque_test.go deleted file mode 100644 index a66fff4..0000000 --- a/vecdeque_test.go +++ /dev/null @@ -1,299 +0,0 @@ -package vecdeque - -import ( - "bytes" - "fmt" - "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 TestGet(t *testing.T) { - t.Parallel() - - q := new(DQ[int]) - for i := range 10 { - q.PushBack(i) - } - for i := range 3 { - if got := q.Get(i); got != i { - t.Errorf("Get(%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() - - q := From([]int{1, 2, 3}) - 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) - } - want := []int{1, 2, 3} - if !slices.Equal(got, want) { - t.Errorf("PopAll() returned values %d, want %d", got, want) - } -} - -func TestAvailableBuffer(t *testing.T) { - t.Parallel() - - const cap = 10 - q := WithCapacity[byte](cap) - q.PushBack(append(q.AvailableBuffer(), []byte(" ")...)...) - q.PushBack(fmt.Appendf(q.AvailableBuffer(), "%d", 12345)...) - for range 5 { - q.PopFront() - } - q.PushBack(fmt.Appendf(q.AvailableBuffer(), "%d", 67890)...) - if got, want := q.Cap(), cap; got != want { - t.Errorf("Cap() = %d, want %d", got, want) - } - got := make([]byte, q.Len()) - for i, x := range q.All() { - got[i] = x - } - want := []byte("1234567890") - if !bytes.Equal(got, want) { - t.Errorf("Incorrect content after appending to AvailableBuffer, got %d want %d", got, want) - } -} -- cgit v1.3.1