Initial commit

3 files changed, 432 insertions, 0 deletions

diff --git a/go.mod b/go.mod
new file mode 100644
index 0000000..ff5a669
--- /dev/null
+++ b/go.mod
@@ -0,0 +1,3 @@
+module gitlab.com/rhogenson/vecdeque
+
+go 1.24.1
diff --git a/vecdeque.go b/vecdeque.go
new file mode 100644
index 0000000..737c99e
--- /dev/null
+++ b/vecdeque.go
@@ -0,0 +1,171 @@
+// 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)]
+}
+
+// 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) {
+	if cap(q.buf)-len(q.buf) >= n {
+		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 q.Len() {
+			if !yield(i, q.Get(i)) {
+				return
+			}
+		}
+	}
+}
+
+// PopAll returns an iterator that consumes all the values in the deque, leaving
+// it empty.
+func (q *DQ[T]) PopAll() func(func(T) bool) {
+	return func(yield func(T) bool) {
+		for val, ok := q.PopFront(); ok; val, ok = q.PopFront() {
+			if !yield(val) {
+				return
+			}
+		}
+	}
+}
diff --git a/vecdeque_test.go b/vecdeque_test.go
new file mode 100644
index 0000000..527c46c
--- /dev/null
+++ b/vecdeque_test.go
@@ -0,0 +1,258 @@
+package vecdeque
+
+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 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 TestPopAll(t *testing.T) {
+	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)
+	}
+}