/* 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() } }