deque

Documentation

Index

• type Deque
  • func (q *Deque[T]) AppendToSlice(out []T) []T
  • func (q *Deque[T]) At(i int) T
  • func (q *Deque[T]) Back() T
  • func (q *Deque[T]) Cap() int
  • func (q *Deque[T]) Clear()
  • func (q *Deque[T]) Copy(src Deque[T]) int
  • func (q *Deque[T]) CopyInSlice(in []T)
  • func (q *Deque[T]) CopyOutSlice(out []T) int
  • func (q *Deque[T]) Front() T
  • func (q *Deque[T]) Grow(n int)
  • func (q *Deque[T]) Index(f func(T) bool) int
  • func (q *Deque[T]) Insert(at int, item T)
  • func (q *Deque[T]) Iter() func(yield func(T) bool)
  • func (q *Deque[T]) IterPopBack() func(yield func(T) bool)
  • func (q *Deque[T]) IterPopFront() func(yield func(T) bool)
  • func (q *Deque[T]) Len() int
  • func (q *Deque[T]) PopBack() T
  • func (q *Deque[T]) PopFront() T
  • func (q *Deque[T]) PushBack(elem T)
  • func (q *Deque[T]) PushFront(elem T)
  • func (q *Deque[T]) RIndex(f func(T) bool) int
  • func (q *Deque[T]) RIter() func(yield func(T) bool)
  • func (q *Deque[T]) Remove(at int) T
  • func (q *Deque[T]) Rotate(n int)
  • func (q *Deque[T]) Set(i int, item T)
  • func (q *Deque[T]) SetBaseCap(baseCap int)
  • func (q *Deque[T]) Swap(idxA, idxB int)

Types

type Deque

type Deque[T any] struct {
	// contains filtered or unexported fields
}

Deque represents a single instance of the deque data structure. A Deque instance contains items of the type specified by the type argument.

For example, to create a Deque that contains strings do one of the following:

var stringDeque deque.Deque[string]
stringDeque := new(deque.Deque[string])
stringDeque := &deque.Deque[string]{}

To create a Deque that will never resize to have space for less than 64 items, specify a base capacity:

var d deque.Deque[int]
d.SetBaseCap(64)

To ensure the Deque can store 1000 items without needing to resize while items are added:

d.Grow(1000)

Any values supplied to [SetBaseCap] and [Grow] are rounded up to the nearest power of 2, since the Deque grows by powers of 2.

func (*Deque[T]) AppendToSlice

func (q *Deque[T]) AppendToSlice(out []T) []T

AppendToSlice appends from the Deque to the given slice. If the slice has insufficient capacity to store all elements in Deque, then allocate a new slice. Returns the resulting slice.

out = q.AppendToSlice(out)

is an efficient shortcut for

for i := 0; i < q.Len(); i++ {
	x = append(out, q.At(i))
}

func (*Deque[T]) At

func (q *Deque[T]) At(i int) T

At returns the element at index i in the queue without removing the element from the queue. This method accepts only non-negative index values. At(0) refers to the first element and is the same as [Front]. At(Len()-1) refers to the last element and is the same as [Back]. If the index is invalid, the call panics.

The purpose of At is to allow Deque to serve as a more general purpose circular buffer, where items are only added to and removed from the ends of the deque, but may be read from any place within the deque. Consider the case of a fixed-size circular log buffer: A new entry is pushed onto one end and when full the oldest is popped from the other end. All the log entries in the buffer must be readable without altering the buffer contents.

func (*Deque[T]) Back

func (q *Deque[T]) Back() T

Back returns the element at the back of the queue. This is the element that would be returned by [PopBack]. This call panics if the queue is empty.

func (*Deque[T]) Cap

func (q *Deque[T]) Cap() int

Cap returns the current capacity of the Deque. If q is nil, q.Cap() is zero.

func (*Deque[T]) Clear

func (q *Deque[T]) Clear()

Clear removes all elements from the queue, but retains the current capacity. This is useful when repeatedly reusing the queue at high frequency to avoid GC during reuse. The queue will not be resized smaller as long as items are only added. Only when items are removed is the queue subject to getting resized smaller.

func (*Deque[T]) Copy

func (q *Deque[T]) Copy(src Deque[T]) int

Copy copies the contents of the given src Deque into this Deque.

n := b.Copy(a)

is an efficient shortcut for

b.Clear()
n := a.Len()
b.Grow(n)
for i := 0; i < n; i++ {
	b.PushBack(a.At(i))
}

func (*Deque[T]) CopyInSlice

func (q *Deque[T]) CopyInSlice(in []T)

CopyInSlice replaces the contents of Deque with all the elements from the given slice, in. If len(in) is zero, then this is equivalent to calling [Clear].

q.CopyInSlice(in)

is an efficient shortcut for

q.Clear()
for i := range in {
	q.PushBack(in[i])
}

func (*Deque[T]) CopyOutSlice

func (q *Deque[T]) CopyOutSlice(out []T) int

CopyOutSlice copies elements from the Deque into the given slice, up to the size of the buffer. Returns the number of elements copied, which will be the minimum of q.Len() and len(out).

n := q.CopyOutSlice(out)

is an efficient shortcut for

n := min(len(out), q.Len())
for i := 0; i < n; i++ {
 	out[i] = q.At(i)
}

This function is preferable to one that returns a copy of the internal buffer because this allows reuse of memory receiving data, for repeated copy operations.

func (*Deque[T]) Front

func (q *Deque[T]) Front() T

Front returns the element at the front of the queue. This is the element that would be returned by [PopFront]. This call panics if the queue is empty.

func (*Deque[T]) Grow

func (q *Deque[T]) Grow(n int)

Grow grows deque's capacity, if necessary, to guarantee space for another n items. After Grow(n), at least n items can be written to the deque without another allocation. If n is negative, Grow panics.

func (*Deque[T]) Index

func (q *Deque[T]) Index(f func(T) bool) int

Index returns the index into the Deque of the first item satisfying f(item), or -1 if none do. If q is nil, then -1 is always returned. Search is linear starting with index 0.

func (*Deque[T]) Insert

func (q *Deque[T]) Insert(at int, item T)

Insert is used to insert an element into the middle of the queue, before the element at the specified index. Insert(0,e) is the same as PushFront(e) and Insert(Len(),e) is the same as PushBack(e). Out of range indexes result in pushing the item onto the front of back of the deque.

Important: Deque is optimized for O(1) operations at the ends of the queue, not for operations in the the middle. Complexity of this function is constant plus linear in the lesser of the distances between the index and either of the ends of the queue.

func (*Deque[T]) Iter

func (q *Deque[T]) Iter() func(yield func(T) bool)

Iter returns a go iterator to range over all items in the Deque, yielding each item from front (index 0) to back (index Len()-1). Modification of Deque during iteration panics.

func (*Deque[T]) IterPopBack

func (q *Deque[T]) IterPopBack() func(yield func(T) bool)

IterPopBack returns an iterator that iteratively removes items from the back of the deque. This is more efficient than removing items one at a time because it avoids intermediate resizing. If a resize is necessary, only one is done when iteration ends.

func (*Deque[T]) IterPopFront

func (q *Deque[T]) IterPopFront() func(yield func(T) bool)

IterPopFront returns an iterator that iteratively removes items from the front of the deque. This is more efficient than removing items one at a time because it avoids intermediate resizing. If a resize is necessary, only one is done when iteration ends.

func (*Deque[T]) Len

func (q *Deque[T]) Len() int

Len returns the number of elements currently stored in the queue. If q is nil, q.Len() returns zero.

func (*Deque[T]) PopBack

func (q *Deque[T]) PopBack() T

PopBack removes and returns the element from the back of the queue. Implements LIFO when used with [PushBack]. If the queue is empty, the call panics.

func (*Deque[T]) PopFront

func (q *Deque[T]) PopFront() T

PopFront removes and returns the element from the front of the queue. Implements FIFO when used with [PushBack]. If the queue is empty, the call panics.

func (*Deque[T]) PushBack

func (q *Deque[T]) PushBack(elem T)

PushBack appends an element to the back of the queue. Implements FIFO when elements are removed with [PopFront], and LIFO when elements are removed with [PopBack].

func (*Deque[T]) PushFront

func (q *Deque[T]) PushFront(elem T)

PushFront prepends an element to the front of the queue.

func (*Deque[T]) RIndex

func (q *Deque[T]) RIndex(f func(T) bool) int

RIndex is the same as Index, but searches from Back to Front. The index returned is from Front to Back, where index 0 is the index of the item returned by [Front].

func (*Deque[T]) RIter

func (q *Deque[T]) RIter() func(yield func(T) bool)

RIter returns a reverse go iterator to range over all items in the Deque, yielding each item from back (index Len()-1) to front (index 0). Modification of Deque during iteration panics.

func (*Deque[T]) Remove

func (q *Deque[T]) Remove(at int) T

Remove removes and returns an element from the middle of the queue, at the specified index. Remove(0) is the same as [PopFront] and Remove(Len()-1) is the same as [PopBack]. Accepts only non-negative index values, and panics if index is out of range.

Important: Deque is optimized for O(1) operations at the ends of the queue, not for operations in the the middle. Complexity of this function is constant plus linear in the lesser of the distances between the index and either of the ends of the queue.

func (*Deque[T]) Rotate

func (q *Deque[T]) Rotate(n int)

Rotate rotates the deque n steps front-to-back. If n is negative, rotates back-to-front. Having Deque provide Rotate avoids resizing that could happen if implementing rotation using only Pop and Push methods. If q.Len() is one or less, or q is nil, then Rotate does nothing.

func (*Deque[T]) Set

func (q *Deque[T]) Set(i int, item T)

Set assigns the item to index i in the queue. Set indexes the deque the same as [At] but perform the opposite operation. If the index is invalid, the call panics.

func (*Deque[T]) SetBaseCap

func (q *Deque[T]) SetBaseCap(baseCap int)

SetBaseCap sets a base capacity so that at least the specified number of items can always be stored without resizing.

func (*Deque[T]) Swap

func (q *Deque[T]) Swap(idxA, idxB int)

Swap exchanges the two values at idxA and idxB. It panics if either index is out of range.