Documentation
¶
Index ¶
- type ConcurrentUnboundedQueue
- func (q *ConcurrentUnboundedQueue) Dequeue() (v interface{}, ok bool)
- func (q *ConcurrentUnboundedQueue) Enqueue(item interface{})
- func (q *ConcurrentUnboundedQueue) IsEmpty() bool
- func (q *ConcurrentUnboundedQueue) Len() int
- func (q *ConcurrentUnboundedQueue) Peek() (v interface{}, ok bool)
- func (q *ConcurrentUnboundedQueue) Signal() <-chan struct{}
- type Deque
- func (q *Deque) At(i int) interface{}
- func (q *Deque) Back() interface{}
- func (q *Deque) Cap() int
- func (q *Deque) Clear()
- func (q *Deque) Front() interface{}
- func (q *Deque) Len() int
- func (q *Deque) PopBack() interface{}
- func (q *Deque) PopFront() interface{}
- func (q *Deque) PushBack(elem interface{})
- func (q *Deque) PushFront(elem interface{})
- func (q *Deque) Rotate(n int)
- func (q *Deque) Set(i int, elem interface{})
- func (q *Deque) SetMinCapacity(minCapacityExp uint)
- type PQItem
- type PriorityQueue
- type UnboundedQueue
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ConcurrentUnboundedQueue ¶ added in v0.1.28
type ConcurrentUnboundedQueue struct {
// contains filtered or unexported fields
}
A simple Unbounded FIFO concurrent queue
func NewConcurrentUnboundedQueue ¶ added in v0.1.28
func NewConcurrentUnboundedQueue() *ConcurrentUnboundedQueue
func (*ConcurrentUnboundedQueue) Dequeue ¶ added in v0.1.28
func (q *ConcurrentUnboundedQueue) Dequeue() (v interface{}, ok bool)
Dequeue dequeues an element. Returns false if queue is locked or empty.
func (*ConcurrentUnboundedQueue) Enqueue ¶ added in v0.1.28
func (q *ConcurrentUnboundedQueue) Enqueue(item interface{})
Enqueue enqueues an element
func (*ConcurrentUnboundedQueue) IsEmpty ¶ added in v0.1.28
func (q *ConcurrentUnboundedQueue) IsEmpty() bool
func (*ConcurrentUnboundedQueue) Len ¶ added in v0.1.28
func (q *ConcurrentUnboundedQueue) Len() int
func (*ConcurrentUnboundedQueue) Peek ¶ added in v0.1.28
func (q *ConcurrentUnboundedQueue) Peek() (v interface{}, ok bool)
Peek returns front element's value and keeps the element at the queue
func (*ConcurrentUnboundedQueue) Signal ¶ added in v0.1.28
func (q *ConcurrentUnboundedQueue) Signal() <-chan struct{}
type Deque ¶
type Deque struct {
// contains filtered or unexported fields
}
func NewDeque ¶
NewDeque creates a new Deque, optionally setting the current and minimum capacity when non-zero values are given for these.
To create a Deque with capacity to store 2048 items without resizing, and that will not resize below space for 32 items when removing itmes:
d := deque.New(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(0, 64)
Note that any values supplied here are rounded up to the nearest power of 2.
func (*Deque) 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) Back ¶
func (q *Deque) Back() interface{}
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) Clear ¶
func (q *Deque) 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) Front ¶
func (q *Deque) Front() interface{}
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) PopBack ¶
func (q *Deque) PopBack() interface{}
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) PopFront ¶
func (q *Deque) PopFront() interface{}
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) PushBack ¶
func (q *Deque) PushBack(elem interface{})
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) PushFront ¶
func (q *Deque) PushFront(elem interface{})
PushFront prepends an element to the front of the queue.
func (*Deque) 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.
func (*Deque) 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) 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 PriorityQueue ¶ added in v0.1.28
type PriorityQueue []*PQItem
this is a priority queue as implemented by a min heap ie. the 0th element is the *lowest* value
func NewPriorityQueue ¶ added in v0.1.28
func NewPriorityQueue(capacity int) PriorityQueue
func (PriorityQueue) Len ¶ added in v0.1.28
func (pq PriorityQueue) Len() int
func (PriorityQueue) Less ¶ added in v0.1.28
func (pq PriorityQueue) Less(i, j int) bool
func (*PriorityQueue) PeekAndShift ¶ added in v0.1.28
func (pq *PriorityQueue) PeekAndShift(max int64) (*PQItem, int64)
func (*PriorityQueue) Pop ¶ added in v0.1.28
func (pq *PriorityQueue) Pop() interface{}
func (*PriorityQueue) Push ¶ added in v0.1.28
func (pq *PriorityQueue) Push(x interface{})
func (PriorityQueue) Swap ¶ added in v0.1.28
func (pq PriorityQueue) Swap(i, j int)
type UnboundedQueue ¶
type UnboundedQueue struct {
// contains filtered or unexported fields
}
UnboundedQueue represents an unbounded, dynamically growing FIFO queue. The zero value for queue is an empty queue ready to use. see https://github.com/golang/go/issues/27935
func NewUnboundedQueue ¶ added in v0.1.28
func NewUnboundedQueue() *UnboundedQueue
func (*UnboundedQueue) Front ¶
func (q *UnboundedQueue) Front() (interface{}, bool)
Front returns the first element of queue q or nil if the queue is empty. The second, bool result indicates whether a valid value was returned;
if the queue is empty, false will be returned.
The complexity is O(1).
func (*UnboundedQueue) Init ¶
func (q *UnboundedQueue) Init() *UnboundedQueue
Init initializes or clears queue q.
func (*UnboundedQueue) Len ¶
func (q *UnboundedQueue) Len() int
func (*UnboundedQueue) Pop ¶
func (q *UnboundedQueue) Pop() (interface{}, bool)
Pop retrieves and removes the current element from the queue. The second, bool result indicates whether a valid value was returned;
if the queue is empty, false will be returned.
The complexity is O(1).
func (*UnboundedQueue) Push ¶
func (q *UnboundedQueue) Push(v interface{})
Push adds a value to the queue. The complexity is O(1).