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 --- vecdeque.go | 196 ------------------------------------------------------------ 1 file changed, 196 deletions(-) delete mode 100644 vecdeque.go (limited to 'vecdeque.go') 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 - } - } - } -} -- cgit v1.3.1