README
¶
deque
Blazingly fast ring-buffer deque (double-ended queue) with both low level and high level APIs. Gives you full control.
Installation
$ go get github.com/lucasgdosr/deque
Deque data structure
Deques generalize queues, stacks, and arrays. Adding or removing elements from both ends are O(1) operations, as is indexing into any position. Queue (FIFO) operations are supported using PushBack* and PopFront*. Stack (LIFO) operations are supported using PushBack* and PopBack*. Array indexing operations are supported using At* and Set*. Much of the slices package functionality is implemented either as methods or functions which take *Deque as arguments.
Ring-buffer implementation
The implementation consists of an underlying generic slice ([]T) with a power of two length with a head and a tail, which can also be thought of as the count of pushed and popped elements in a queue. This slice wraps around as elements are pushed and popped, reusing memory as long as it fits all elements, and reallocating to the next power of two if it doesn't.
Powers of two have a special property in binary. They're all of the form 0*10*, that is, leading zeroes, a single one, and trailing zeroes. This also means a power of two minus one has the form 0*1* - the original one is flipped to zero and all originally trailing zeroes are flipped to ones. In this way, % len(slice) is equivalent to & (len(slice) - 1). This allows us to monotonically increase the head and tail counts and bitwise-and them with a mask that's just the length of the slice minus one to get the index. We can avoid maintaining a count of the number of elements and maintaining head and tail within the index bounds of the slice with an array + two unmasked indices, also known as a virtual stream.
API
Construction
Every method takes a pointer as its receiver. To instantiate a deque and get its pointer, call deque.MakeDeque(). If you already have an upper bound on the number of elements that may be stored in the deque, prefer deque.MakeDequeWithCapacity(capacity) to avoid reallocations. You do not need to worry about passing in a power of two, but be aware that whatever capacity you pass will be rounded up to a power of two. Alternatively, you may instantiate a deque out of an existing slice with deque.CopySliceToDeque(s). Note this is a copy, and does not reuse the passed slice. The deque owns its underlying slice, and does not share memory.
Pushing, peeking, and popping
Pushing can be done to either end of the deque with PushFront and PushBack. Conventionally, PushBack is generally preferred. These methods take in a variable number of elements, so pushing an entire slice onto a deque can be done with a single call to d.PushBack(s...). They may reallocate into a larger slice if there is no space left. You may use d.Reserve(n) to ensure there's enough space to hold at least n more elements, reallocating if needed. You may also use d.Resize(newCapacity) if you prefer to specify the number of total elements. Do not worry about passing in a power of two, as the input is rounded up to a power of two.
Peeking is how you access the ends of the deque without removing the elements. There is PeekFront* and PeekBack*, with safe and Unsafe variants. Safe variants return a bool indicating whether the deque had any elements, and the unsafe variants do not check whether the deque is empty and always return something, which might be a previously popped element if the deque is empty. Only ever call the unsafe versions if you're certain the deque isn't empty.
Popping is how you remove elements from the deque. There are safe and Unsafe variants just like in Peek*, with the same bool mechanism. Do not call the Unsafe version unless you are absolutely sure the deque is not empty. Results are catastrophic. There are also Zero variants and Shrink variants. Zero variants overwrite the popped element with their zero value, effectively allowing garbage collection to happen for elements that hold pointers. Prefer the Zero variants if your elements are pointers or are structs that hold pointers, or you might leak memory until the element is overwritten with another push. The Shrink variants are designed to give you the option to reallocate the underlying slice if it is ever needlessly large. Do not favor the Shrink variants if many pushes might follow. You can also call Resize explicitly when you're sure you're done pushing and want to claim back memory using d.Resize(d.Len()).
Clear and drop
If you ever need to get rid of the elements in the deque but don't care about their contents, instead of calling multiple Pops and ignoring their return, favor Clear* and Drop*. These methods keep the original capacity and the underlying slice. Both of them have Zero and regular variants, which are useful for elements with and without pointers, respectivelly, just as Pop. ClearEager is the Zero variant, and ClearLazy is the regular variant. The regular variants have O(1) cost, as they just update the head and tail, while the zero versions have O(n) cost, as they actually need to overwrite the deque's contents. Clear clears every element, and Drop(Front/Back)* drops n elements.
Slices
You may access any element in the deque by index using At* and Set for read / write operations. The head is the zeroth index, and the tail is the d.Len() - 1th index. There are both safe and Unsafe variants. Unlike regular slices, the Unsafe variants to not panic, but they return the contents of another index (possibly of a previously popped element) or set the wrong index. Only call the Unsafe variants if you are absolutely sure they are within bounds. These operations may be combined into Swap*, with safe and Unsafe versions.
If you don't actually want to go through specific indexes, but rather through all of them, prefer ForEach, which applies a function to every element until it returns false, or All, which returns an iterator over index-value pairs, or Iter, which returns an iterator over values. TODO: RIter, IterPop(Front/Back)(Zero)*.
Other functionality from the slices package is available, such as Contains*, Equal*, Index*, Min*, Max*, with the regular and Func variants. The Func variants are generally methods, while the regular variants are functions that take in *Deque as arguments due to generic limitations. MinFunc and MaxFunc are also functions.
If you actually need explicit slices, you can get a shallow copy of the deque's elements. These slices do not share memory with the deque. Generally the best way is to pass your own slice to d.CopySlice(start, buf) and have it filled with copies of the elements in the deque. It has the same semantics as the copy built-in function, copying elements up until one of the slices is over. This allows you to reuse buffers. If you actually want to allocate new slices, there're three options. d.MakeSliceCopy() allocates a new slice with just enough capacity to hold every element in the deque, fills it with copies, and returns it. If you don't want every element, only a subset of them, call d.MakeSliceIndexCopy(start, end). This is equivalent to s[start:end] in regular slice syntax, except it's a copy. If you want the resulting slice to have extra capacity, use d.MakeSliceIndexCopyWithCapacity(start, end, capacity), and the returned slice will still have room for more elements to be appended.
Documentation
¶
Index ¶
- Variables
- func Contains[T comparable](d *Deque[T], t T) bool
- func Equal[T comparable](d1 *Deque[T], d2 *Deque[T]) bool
- func Index[T comparable](d *Deque[T], t T) int
- func Max[T cmp.Ordered](d *Deque[T]) T
- func MaxFunc[T cmp.Ordered](d *Deque[T], cmp func(T, T) int) T
- func Min[T cmp.Ordered](d *Deque[T]) T
- func MinFunc[T cmp.Ordered](d *Deque[T], cmp func(T, T) int) T
- type Deque
- func (d *Deque[T]) All() iter.Seq2[int, T]
- func (d *Deque[T]) At(i int) T
- func (d *Deque[T]) AtUnsafe(i int) T
- func (d *Deque[T]) Cap() int
- func (d *Deque[T]) ClearEager()
- func (d *Deque[T]) ClearLazy()
- func (d *Deque[T]) ContainsFunc(f func(T) bool) bool
- func (d *Deque[T]) CopySlice(start int, buf []T) int
- func (d *Deque[T]) DropBack(n int)
- func (d *Deque[T]) DropBackZero(n int)
- func (d *Deque[T]) DropFront(n int)
- func (d *Deque[T]) DropFrontZero(n int)
- func (d *Deque[T]) Empty() bool
- func (d1 *Deque[T]) EqualFunc(d2 *Deque[T], f func(T, T) bool) bool
- func (d *Deque[T]) ForEach(f func(T) bool)
- func (d *Deque[T]) Full() bool
- func (d *Deque[T]) IndexFunc(f func(T) bool) int
- func (d *Deque[T]) Iter() iter.Seq[T]
- func (d *Deque[T]) Len() int
- func (d *Deque[T]) MakeSliceCopy() []T
- func (d *Deque[T]) MakeSliceIndexCopy(start, end int) []T
- func (d *Deque[T]) MakeSliceIndexCopyWithCapacity(start, end, capacity int) []T
- func (d *Deque[T]) PeekBack() (t T, ok bool)
- func (d *Deque[T]) PeekBackUnsafe() T
- func (d *Deque[T]) PeekFront() (t T, ok bool)
- func (d *Deque[T]) PeekFrontUnsafe() T
- func (d *Deque[T]) PopBack() (t T, ok bool)
- func (d *Deque[T]) PopBackShrink() (t T, ok bool)
- func (d *Deque[T]) PopBackUnsafe() T
- func (d *Deque[T]) PopBackZero() (t T, ok bool)
- func (d *Deque[T]) PopBackZeroUnsafe() T
- func (d *Deque[T]) PopFront() (t T, ok bool)
- func (d *Deque[T]) PopFrontShrink() (t T, ok bool)
- func (d *Deque[T]) PopFrontUnsafe() T
- func (d *Deque[T]) PopFrontZero() (t T, ok bool)
- func (d *Deque[T]) PopFrontZeroUnsafe() T
- func (d *Deque[T]) PushBack(ts ...T)
- func (d *Deque[T]) PushFront(ts ...T)
- func (d *Deque[T]) Reserve(n int) error
- func (d *Deque[T]) Resize(minCapacity int) error
- func (d *Deque[T]) Set(i int, t T)
- func (d *Deque[T]) SetUnsafe(i int, t T)
- func (d *Deque[T]) Shrink() uint
- func (d *Deque[T]) Swap(i, j int)
- func (d *Deque[T]) SwapUnsafe(i, j int)
Constants ¶
This section is empty.
Variables ¶
var ErrNegativeCapacity = errors.New("capacity cannot be negative")
ErrNegativeCapacity is returned when trying to resize a Deque to a negative capacity.
var ErrNotEnoughCapacity = errors.New("cannot hold existing elements in asked capacity")
ErrNotEnoughCapacity is returned when trying to resize a Deque to a capacity that cannot hold its existing elements.
var ErrSameCapacity = errors.New("already at asked capacity")
ErrSameCapacity is returned when trying to resize a Deque to its current capacity.
Functions ¶
func Contains ¶
func Contains[T comparable](d *Deque[T], t T) bool
Contains returns whether the element is in the Deque. This must not be a method, otherwise Deque would be constrained to comparable elements. It has the same semantics as slices.Contains.
func Equal ¶
func Equal[T comparable](d1 *Deque[T], d2 *Deque[T]) bool
Equal returns whether both Deques have the same length and the same elements in the same order. Two nil Deques are equal, but an empty Deque and nil are not. This must not be a method, otherwise Deque would be constrained to comparable elements. Equal's semantics differs from slices.Equal in the nil vs empty comparison.
func Index ¶
func Index[T comparable](d *Deque[T], t T) int
Index returns the index of the first ocurrence of t in the Deque or -1 if absent. It cannot be a method, otherwise Deque would be constrained to comparable elements only. Index has the same semantics as slices.Index.
func Max ¶
Max returns the maximum element in the queue. It must not be a method, otherwise Deque would be constrained to comparable elements only. It has the same semantics as slices.Max, so it panics on an empty Deque.
func MaxFunc ¶
MaxFunc returns the maximum element in the queue. It must not be a method, otherwise Deque would be constrained to comparable elements only. It has the same semantics as slices.MaxFunc, so it panics on an empty Deque.
Types ¶
type Deque ¶
type Deque[T any] struct { // contains filtered or unexported fields }
Deque is a double-ended queue that can be used for either LIFO or FIFO ordering, or something in between.
To create a Deque instance, you must use one of the available constructors, MakeDeque(), MakeDequeWithCapacity(cap), or CopySliceToDeque(s). nil Deques panic when called, except for Len. Creating a Deque in the following way is wrong:
var deque Deque[int] // wrong
This implementation requires a buffer with a power of two length. If a Deque ever overflows its underlying buffer, it reallocates to twice the size. It does not shrink by default, so you must explicitly call a method to shrink it.
func CopySliceToDeque ¶
CopySliceToDeque takes in a slice, allocates a new buffer rounding len(s) to the next power of two, and copies every element of the slice to the Deque. The slice's capacity is irrelevant to CopySliceToDeque, and memory is not shared.
func MakeDequeWithCapacity ¶
MakeDequeWithCapacity takes in the desired capacity. Note that if the supplied capacity is not a power of two, it will be increased to the next power of two. Returns an error if passed a negative value.
func (*Deque[T]) All ¶
All returns an iterator over index-value pairs in order. It has the same semantics as slices.All. If you don't need indexes, use Iter instead. Does not panic if modified during iteration.
func (*Deque[T]) AtUnsafe ¶
AtUnsafe indexes into the i-th position in the Deque. It never panics, but returns garbage if i is out of bounds.
func (*Deque[T]) ClearEager ¶
func (d *Deque[T]) ClearEager()
ClearEager empties the Deque in O(d.Len()), zeroing existing elements and maintaining capacity. This is useful for reusing a Deque with references.
func (*Deque[T]) ClearLazy ¶
func (d *Deque[T]) ClearLazy()
ClearLazy empties the Deque in O(1), but does not zero the elements. If references remain, the memory they point to will not be garbage collected. Capacity is retained. This is useful for reusing a Deque with no references.
func (*Deque[T]) ContainsFunc ¶
ContainsFunc returns whether an element satisfying f is in the Deque. It has the same semantics as slices.ContainsFunc.
func (*Deque[T]) CopySlice ¶
CopySlice has the same semantics as the copy() built-in function. It copies elements in the Deque starting at the start index up until the buffer is full or the Deque is over, whichever happens first.
CopySlice returns the number of elements copied, which will be the minimum of len(buf) and d.Len().
func (*Deque[T]) DropBack ¶
DropBack removes the n last elements of the deque in O(1), but doesn't clear references. If the Deque has fewer than n elements, it drops every element. If n is negative, no element is dropped. If your elements have references, prefer DropBackZero, which takes O(n).
func (*Deque[T]) DropBackZero ¶
DropBackZero removes the n last elements of the deque in O(n) and clears references, allowing garbage collection to occur. If the Deque has fewer than n elements, it drops every element. If your elements don't have references, prefer DropBack, which takes O(1).
func (*Deque[T]) DropFront ¶
DropFront removes the n first elements of the deque in O(1), but doesn't clear references. If the Deque has fewer than n elements, it drops every element. If n is negative, no element is dropped. If your elements have references, prefer DropFrontZero, which takes O(n).
func (*Deque[T]) DropFrontZero ¶
DropFrontZero removes the n first elements of the deque in O(n) and clears references, allowing garbage collection to occur. If the Deque has fewer than n elements, it drops every element. If your elements don't have references, prefer DropFront, which takes O(1).
func (*Deque[T]) EqualFunc ¶
EqualFunc returns whether both Deques have the same length and the same elements in the same order. Two nil Deques are equal, but an empty Deque and nil are not. EqualFunc's semantics differs from slices.EqualFunc in the nil vs empty comparison.
func (*Deque[T]) ForEach ¶
ForEach takes in a function that returns a bool and calls it in order for every element in the queue, or until the first call that returns false.
func (*Deque[T]) Full ¶
Full returns whether the Deque is full. Pushing to a full Deque reallocates.
func (*Deque[T]) IndexFunc ¶
IndexFunc returns the index of the first element that satisfies f in the Deque or -1 if none do. IndexFunc has the same semantics as slices.IndexFunc.
func (*Deque[T]) Iter ¶
Iter returns an iterator over values only in order. If you need indexes, use All instead. Does not panic if the Deque is modified during iteration.
func (*Deque[T]) MakeSliceCopy ¶
func (d *Deque[T]) MakeSliceCopy() []T
MakeSliceCopy allocates a slice to hold every Deque element and copies them. Prefer passing a buffer to CopyToSlice for memory reuse.
func (*Deque[T]) MakeSliceIndexCopy ¶
MakeSliceIndexCopy allocates a slice and copies the contents from the start index (inclusive) to the end index (non-inclusive). This is regular slice semantics, except it's a copy, and doesn't share memory with the Deque. This means it also panics with invalid indexes.
Prefer passing a buffer to CopyToSlice for memory reuse.
func (*Deque[T]) MakeSliceIndexCopyWithCapacity ¶
MakeSliceIndexCopyWithCapacity allocates a slice and copies the contents from the start index (inclusive) to the end index (non-inclusive). This is regular slice semantics, except it's a copy, and doesn't share memory with the Deque. This means it also panics with invalid indexes.
Use this method when you need to append to the slice after copying it. Prefer passing a subslice of a buffer to CopyToSlice for memory reuse.
func (*Deque[T]) PeekBack ¶
PeekBack returns the last element in the Deque. If the Deque is empty, it returns false.
func (*Deque[T]) PeekBackUnsafe ¶
func (d *Deque[T]) PeekBackUnsafe() T
PeekBackUnsafe returns the last element in the Deque. Does not panic, but worse: silently returns garbage.
func (*Deque[T]) PeekFront ¶
PeekFront returns the first element in the Deque. If the Deque is empty, it returns false.
func (*Deque[T]) PeekFrontUnsafe ¶
func (d *Deque[T]) PeekFrontUnsafe() T
PeekFrontUnsafe returns the first element in the Deque. Does not panic, but worse: silently returns garbage.
func (*Deque[T]) PopBack ¶
PopBack removes the last element in the Deque and returns it. If it's empty, returns false. This does not zero the element, so references remain and the garbage collector does not free. If your elements have references, prefer PopBackZero. PopBack is mainly used for LIFO ordering in types with no references.
func (*Deque[T]) PopBackShrink ¶
PopBackShrink removes the last element in the Deque and returns it. If it's empty, false is returned. If the Deque is at <= 25% capacity, it is shrunk to <= 50% capacity.
It is more efficient to call PopBackShrink only once, when you're done popping, to avoid multiple reallocations. It is also more efficient to avoid calling this method when you might push many elements, which might require growing the Deque back.
func (*Deque[T]) PopBackUnsafe ¶
func (d *Deque[T]) PopBackUnsafe() T
PopBackUnsafe removes the last element in the Deque and returns it. It does not zero the element, which means if the type has references, they will leak memory. Prefer PopBackZeroUnsafe if your type has references. Calling this method with an empty Deque leads to undefined behavior from then on.
func (*Deque[T]) PopBackZero ¶
PopBackZero removes the last element in the Deque, zeroes its slot, and returns it. If it's empty, returns false. This is useful to clear references that the underlying element might hold. If your elements have references, this is how you should use the Deque for LIFO ordering.
func (*Deque[T]) PopBackZeroUnsafe ¶
func (d *Deque[T]) PopBackZeroUnsafe() T
PopBackZeroUnsafe removes the last element in the Deque and returns it. The element is zeroed, clearing references and making it available for garbage collection. If your elements don't have references, prefer PopFrontUnsafe. Calling this method with an empty Deque leads to undefined behavior from then on.
func (*Deque[T]) PopFront ¶
PopFront removes the first element in the Deque and returns it. If it's empty, returns false. This does not zero the element, so references remain and the garbage collector does not free. If your elements have references, prefer PopFrontZero. PopFront is mainly used for FIFO ordering in types with no references.
func (*Deque[T]) PopFrontShrink ¶
PopFrontShrink removes the first element in the Deque and returns it. If it's empty, false is returned. If the Deque is at <= 25% capacity, it is shrunk to <= 50% capacity.
It is more efficient to call PopFrontShrink only once, when you're done popping, to avoid multiple reallocations. It is also more efficient to avoid calling this method when you might push many elements, which might require growing the Deque back.
func (*Deque[T]) PopFrontUnsafe ¶
func (d *Deque[T]) PopFrontUnsafe() T
PopFrontUnsafe removes the first element in the Deque and returns it. The element is not zeroed, avoiding garbage collection of elements containing references. If your elements have references, prefer PopFrontZeroUnsafe. Calling this method with an empty Deque leads to undefined behavior from then on.
func (*Deque[T]) PopFrontZero ¶
PopFrontZero removes the first element in the Deque, zeroes its slot, and returns it. If it's empty, returns false. This is useful to clear references that the underlying element might hold. If your elements have references, this is how you should use the Deque for FIFO ordering.
func (*Deque[T]) PopFrontZeroUnsafe ¶
func (d *Deque[T]) PopFrontZeroUnsafe() T
PopFrontZeroUnsafe removes the first element in the Deque and returns it. The element is zeroed, clearing references and making it available for garbage collection. If your elements don't have references, prefer PopFrontUnsafe. Calling this method with an empty Deque leads to undefined behavior from then on.
func (*Deque[T]) PushBack ¶
func (d *Deque[T]) PushBack(ts ...T)
PushBack takes in a variable number of arguments and puts them at the back of the Deque. Use PushBack and PopFront for FIFO ordering, or PushBack and PopBack for LIFO ordering.
PushBack reallocates at most once, no matter how many arguments. It is more efficient to push multiple elements at once. The last argument is the new back of the list.
func (*Deque[T]) PushFront ¶
func (d *Deque[T]) PushFront(ts ...T)
PushFront takes in a variable number of arguments and puts them at the front of the Deque.
PushFront reallocates at most once, no matter how many arguments. It is more efficient to push multiple elements at once. The last argument is the new front of the list.
func (*Deque[T]) Reserve ¶
Reserve ensures there's enough capacity to add at least n more elements to the Deque, reallocating if necessary. It returns an error if n is negative.
func (*Deque[T]) Resize ¶
Resize takes in the minimum desired capacity, rounds it up to a power of two, and reallocates the underlying buffer.
It returns an error if the new capacity matches the old, or if the new capacity cannot hold the existing elements, or if minCapacity is negative.
func (*Deque[T]) SetUnsafe ¶
SetUnsafe writes t to the i-th position in the Deque. It never panics, but writes to another index inside the deque if out of bounds.
func (*Deque[T]) Shrink ¶
Shrink reallocates the underlying slice to the smallest size possible and returns the new Deque's capacity.
func (*Deque[T]) Swap ¶
Swap swaps the elements in the i-th and j-th indexes. Panics if out of bounds.
func (*Deque[T]) SwapUnsafe ¶
SwapUnsafe swaps the elements in the i-th and j-th indexes. It never panics, but swaps the wrong elements if indexes are out of bounds.
Source Files