107 lines
2.0 KiB
Go
107 lines
2.0 KiB
Go
// Package queue implements a non-concurrent queue.
|
|
//
|
|
// # Implementation
|
|
//
|
|
// [Q] is a classic ring buffer. It tracks its head, tail, and length. This
|
|
// makes determining whether the queue is full or empty trivial.
|
|
package queue
|
|
|
|
import "iter"
|
|
|
|
// Q is a non-concurrent queue.
|
|
type Q[T any] struct {
|
|
buf []T
|
|
len int
|
|
head int
|
|
tail int
|
|
}
|
|
|
|
// Make creates a new queue.
|
|
func Make[T any](cap int) Q[T] {
|
|
buf := make([]T, cap)
|
|
return Q[T]{buf: buf}
|
|
}
|
|
|
|
// Capacity returns the total capacity of the queue.
|
|
func (b *Q[T]) Capacity() int {
|
|
return cap(b.buf)
|
|
}
|
|
|
|
// Len returns the number of items in the queue.
|
|
func (b *Q[T]) Len() int {
|
|
return b.len
|
|
}
|
|
|
|
// CanPush returns true if the queue has space for new items.
|
|
func (b *Q[T]) CanPush() bool {
|
|
return cap(b.buf)-b.len != 0
|
|
}
|
|
|
|
// CanPop returns true if the queue has one or more items.
|
|
func (b *Q[T]) CanPop() bool {
|
|
return b.len != 0
|
|
}
|
|
|
|
// PopFront returns the front-most item from the queue.
|
|
//
|
|
// If the queue is empty, it panics.
|
|
func (b *Q[T]) PopFront() T {
|
|
if !b.CanPop() {
|
|
panic("cannot pop from empty queue")
|
|
}
|
|
item := b.buf[b.head]
|
|
// clear queue slot so as not to hold on to garbage
|
|
var empty T
|
|
b.buf[b.head] = empty
|
|
b.len--
|
|
b.head++
|
|
if b.head == cap(b.buf) {
|
|
b.head = 0
|
|
}
|
|
return item
|
|
}
|
|
|
|
// PushBack adds an item to the end of the queue.
|
|
//
|
|
// If the queue is full, it panics.
|
|
func (b *Q[T]) PushBack(value T) {
|
|
if !b.CanPush() {
|
|
panic("cannot push back to full queue")
|
|
}
|
|
b.buf[b.tail] = value
|
|
b.len++
|
|
b.tail++
|
|
if b.tail == cap(b.buf) {
|
|
b.tail = 0
|
|
}
|
|
}
|
|
|
|
// Iter returns an iterator over all items in the queue.
|
|
//
|
|
// This does not pop items off the queue.
|
|
func (b *Q[T]) Iter() iter.Seq[T] {
|
|
return func(yield func(T) bool) {
|
|
remaining := b.len
|
|
i := b.head
|
|
for remaining > 0 {
|
|
yield(b.buf[i])
|
|
remaining--
|
|
i++
|
|
if i == b.len {
|
|
i = 0
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// IterPop returns an iterator that pops each item off the queue.
|
|
func (b *Q[T]) IterPop() iter.Seq[T] {
|
|
return func(yield func(T) bool) {
|
|
for b.CanPop() {
|
|
if !yield(b.PopFront()) {
|
|
break
|
|
}
|
|
}
|
|
}
|
|
}
|