/*

Package queue provides a fast, ring-buffer queue based on the version suggested by Dariusz Górecki.

Using this instead of other, simpler, queue implementations (slice+append or linked list) provides

substantial memory and time benefits, and fewer GC pauses.

The queue implemented here is as fast as it is for an additional reason: it is *not* thread-safe.

*/

package queue

const minQueueLen = 16

// Queue represents a single instance of the queue data structure.

type Queue struct {

buf []interface{}

head, tail, count int

}

// New constructs and returns a new Queue.

func New() *Queue {

return &Queue{buf: make([]interface{}, minQueueLen)}

}

// Length returns the number of elements currently stored in the queue.

func (q *Queue) Length() int {

return q.count

}

func (q *Queue) resize() {

newBuf := make([]interface{}, q.count*2)

if q.tail > q.head {

copy(newBuf, q.buf[q.head:q.tail])

} else {

copy(newBuf, q.buf[q.head:len(q.buf)])

copy(newBuf[len(q.buf)-q.head:], q.buf[:q.tail])

}

q.head = 0

q.tail = q.count

q.buf = newBuf

}

// Add puts an element on the end of the queue.

func (q *Queue) Add(elem interface{}) {

if q.count == len(q.buf) {

q.resize()

}

q.buf[q.tail] = elem

q.tail = (q.tail + 1) % len(q.buf)

q.count++

}

// Peek returns the element at the head of the queue. This call panics

// if the queue is empty.

func (q *Queue) Peek() interface{} {

if q.count <= 0 {

panic("queue: Peek() called on empty queue")

}

return q.buf[q.head]

}

// Get returns the element at index i in the queue. If the index is

// invalid, the call will panic.

func (q *Queue) Get(i int) interface{} {

if i >= q.count || i < 0 {

panic("queue: Get() called with index out of range")

}

return q.buf[(q.head+i)%len(q.buf)]

}

// Remove removes the element from the front of the queue. If you actually

// want the element, call Peek first. This call panics if the queue is empty.

func (q *Queue) Remove() {

if q.count <= 0 {

panic("queue: Remove() called on empty queue")

}

q.buf[q.head] = nil

q.head = (q.head + 1) % len(q.buf)

q.count--

if len(q.buf) > minQueueLen && q.count*4 <= len(q.buf) {

q.resize()

}

}