Documentation
¶
Overview ¶
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.
Index ¶
- type Deque
- 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]) Front() T
- func (q *Deque[T]) Index(f func(T) bool) int
- func (q *Deque[T]) Insert(at int, item T)
- 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]) Remove(at int) T
- func (q *Deque[T]) Rotate(n int)
- func (q *Deque[T]) Set(i int, elem T)
- func (q *Deque[T]) SetMinCapacity(minCapacityExp uint)
- type Item
- type PriorityQueue
- func (pq *PriorityQueue) GetHighest() *Item
- func (pq *PriorityQueue) Init(initItemSliceNum int)
- func (pq *PriorityQueue) Len() int
- func (pq *PriorityQueue) Pop() *Item
- func (pq *PriorityQueue) Push(item *Item)
- func (pq *PriorityQueue) Remove(item *Item)
- func (pq *PriorityQueue) Update(item *Item, value interface{}, priority int)
- type PriorityQueueSlice
- func (pq PriorityQueueSlice) Len() int
- func (pq PriorityQueueSlice) Less(i, j int) bool
- func (pq *PriorityQueueSlice) Pop() interface{}
- func (pq *PriorityQueueSlice) Push(x interface{})
- func (pq PriorityQueueSlice) Swap(i, j int)
- func (pq *PriorityQueueSlice) Update(item *Item, value interface{}, priority int)
- type Queue
- type SCursor
- type SQueue
- func (s *SQueue[ElementType]) GetCursor() (cur SCursor[ElementType])
- func (s *SQueue[ElementType]) GetPosCursor(pos int) (cur SCursor[ElementType], ret bool)
- func (s *SQueue[ElementType]) IsEmpty() bool
- func (s *SQueue[ElementType]) IsFull() bool
- func (s *SQueue[ElementType]) Len() int
- func (s *SQueue[ElementType]) Pop() (elem ElementType, ret bool)
- func (s *SQueue[ElementType]) Push(elem ElementType) bool
- func (s *SQueue[ElementType]) RemoveElement(elementNum int) (removeNum int)
- type SyncQueue
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 sepcified by the type argument.
func New ¶
New creates a new Deque, optionally setting the current and minimum capacity when non-zero values are given for these. The Deque instance returns operates on items of the type specified by the type argument. For example, to create a Deque that contains strings,
stringDeque := deque.New[string]()
To create a Deque with capacity to store 2048 ints without resizing, and that will not resize below space for 32 items when removing items:
d := deque.New[int](2048, 32)
To create a Deque that has not yet allocated memory, but after it does will never resize to have space for less than 64 items:
d := deque.New[int](0, 64)
Any size values supplied here are rounded up to the nearest power of 2.
func (*Deque[T]) At ¶
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]) 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]) 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]) Index ¶
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 ¶
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). 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]) Len ¶
Len returns the number of elements currently stored in the queue. If q is nil, q.Len() is 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 ¶
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]) Remove ¶
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 ¶
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 ¶
Set puts the element at index i in the queue. Set shares the same purpose than At() but perform the opposite operation. The index i is the same index defined by At(). If the index is invalid, the call panics.
func (*Deque[T]) SetMinCapacity ¶
SetMinCapacity sets a minimum capacity of 2^minCapacityExp. If the value of the minimum capacity is less than or equal to the minimum allowed, then capacity is set to the minimum allowed. This may be called at anytime to set a new minimum capacity.
Setting a larger minimum capacity may be used to prevent resizing when the number of stored items changes frequently across a wide range.
type Item ¶
type Item struct {
Value interface{} // The Value of the item; arbitrary.
Priority int // The Priority of the item in the queue.
// The Index is needed by update and is maintained by the heap.Interface methods.
Index int // The Index of the item in the heap.
}
An Item is something we manage in a Priority queue.
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
func (*PriorityQueue) GetHighest ¶
func (pq *PriorityQueue) GetHighest() *Item
func (*PriorityQueue) Len ¶
func (pq *PriorityQueue) Len() int
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() *Item
func (*PriorityQueue) Push ¶
func (pq *PriorityQueue) Push(item *Item)
func (*PriorityQueue) Remove ¶
func (pq *PriorityQueue) Remove(item *Item)
func (*PriorityQueue) Update ¶
func (pq *PriorityQueue) Update(item *Item, value interface{}, priority int)
type PriorityQueueSlice ¶
type PriorityQueueSlice []*Item
A PriorityQueueSlice implements heap.Interface and holds Items.
func (PriorityQueueSlice) Len ¶
func (pq PriorityQueueSlice) Len() int
func (PriorityQueueSlice) Less ¶
func (pq PriorityQueueSlice) Less(i, j int) bool
func (*PriorityQueueSlice) Pop ¶
func (pq *PriorityQueueSlice) Pop() interface{}
func (*PriorityQueueSlice) Push ¶
func (pq *PriorityQueueSlice) Push(x interface{})
func (PriorityQueueSlice) Swap ¶
func (pq PriorityQueueSlice) Swap(i, j int)
func (*PriorityQueueSlice) Update ¶
func (pq *PriorityQueueSlice) Update(item *Item, value interface{}, priority int)
update modifies the Priority and Value of an Item in the queue.
type Queue ¶
type Queue struct {
// contains filtered or unexported fields
}
Queue represents a single instance of the queue data structure.
func (*Queue) Add ¶
func (q *Queue) Add(elem interface{})
Add puts an element on the end of the queue.
func (*Queue) Get ¶
Get returns the element at index i in the queue. If the index is invalid, the call will panic. This method accepts both positive and negative index values. Index 0 refers to the first element, and index -1 refers to the last.
type SCursor ¶
type SCursor[ElementType any] struct { // contains filtered or unexported fields }
游标,通过该游标获取数据
type SQueue ¶
type SQueue[ElementType any] struct { // contains filtered or unexported fields }
这是一个循环队列
func (*SQueue[ElementType]) GetPosCursor ¶
获取指定位置的游标
func (*SQueue[ElementType]) RemoveElement ¶
从队首移除掉指定数量元素
type SyncQueue ¶
type SyncQueue struct {
// contains filtered or unexported fields
}
func NewSyncQueue ¶
func NewSyncQueue() *SyncQueue
func (*SyncQueue) RLockRange ¶
func (q *SyncQueue) RLockRange(f func(interface{}))
Source Files