queue.go

// Package queue provides a generic FIFO queue backed by a growable ring
// buffer. Push and Pop are amortized O(1).
package queue

// Queue is a first-in, first-out container backed by a ring buffer.
//
// Use New to construct one; the zero value is not usable.
type Queue[T any] struct {
	buf  []T
	head int // index of the next element to Pop
	tail int // index where the next element will be Pushed
	n    int // number of elements currently in the queue
}

// New returns a new empty queue with the given initial capacity. The
// capacity is rounded up to a sensible minimum.
func New[T any](initialCap int) *Queue[T] {
	if initialCap < 4 {
		initialCap = 4
	}
	return &Queue[T]{buf: make([]T, initialCap)}
}

// Len returns the number of elements currently in the queue.
func (q *Queue[T]) Len() int { return q.n }

// Cap returns the current capacity of the underlying ring buffer.
func (q *Queue[T]) Cap() int { return len(q.buf) }

// Push appends v to the back of the queue, growing the buffer if needed.
func (q *Queue[T]) Push(v T) {
	if q.n == len(q.buf) {
		q.grow()
	}
	q.buf[q.tail] = v
	q.tail = (q.tail + 1) % len(q.buf)
	q.n++
}

// Pop removes and returns the front element along with true. It returns the
// zero value of T and false on an empty queue.
func (q *Queue[T]) Pop() (T, bool) {
	var zero T
	if q.n == 0 {
		return zero, false
	}
	v := q.buf[q.head]
	q.buf[q.head] = zero // help GC if T contains pointers
	q.head = (q.head + 1) % len(q.buf)
	q.n--
	return v, true
}

// Peek returns the front element without removing it.
func (q *Queue[T]) Peek() (T, bool) {
	var zero T
	if q.n == 0 {
		return zero, false
	}
	return q.buf[q.head], true
}

// Snapshot returns a copy of the queue contents from front to back.
func (q *Queue[T]) Snapshot() []T {
	out := make([]T, q.n)
	for i := 0; i < q.n; i++ {
		out[i] = q.buf[(q.head+i)%len(q.buf)]
	}
	return out
}

// grow doubles the underlying buffer and re-linearizes the elements so that
// head ends up at index 0.
func (q *Queue[T]) grow() {
	newCap := len(q.buf) * 2
	nb := make([]T, newCap)
	for i := 0; i < q.n; i++ {
		nb[i] = q.buf[(q.head+i)%len(q.buf)]
	}
	q.buf = nb
	q.head = 0
	q.tail = q.n
}