Documentation ¶
Overview ¶
Package queues defines the Queue interface used in package dispatch, and several Queue implementations.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ArrayPriorityQueue ¶
type ArrayPriorityQueue struct {
// contains filtered or unexported fields
}
An array-based priority queue with a constant time dequeue and a linear time equeue. It should slightly outperform a VectorPriorityQueue, but will likely be removed from the library because it is requires more maintenance.
func NewArrayPriorityQueue ¶
func NewArrayPriorityQueue() *ArrayPriorityQueue
Create a new array-based priority queue.
func (*ArrayPriorityQueue) Dequeue ¶
func (apq *ArrayPriorityQueue) Dequeue() RegisteredTask
Remove the next task with a runtime O(1).
func (*ArrayPriorityQueue) Enqueue ¶
func (apq *ArrayPriorityQueue) Enqueue(task RegisteredTask)
Add a task to the queue with runtime O(n) (on average n/2 + log_2(n))
func (*ArrayPriorityQueue) Len ¶
func (apq *ArrayPriorityQueue) Len() int
The number of PrioritizedTasks in the queue.
func (*ArrayPriorityQueue) SetKey ¶
func (apq *ArrayPriorityQueue) SetKey(id int64, k float64)
Add a task to the queue with runtime O(n).
type FIFO ¶
type FIFO struct {
// contains filtered or unexported fields
}
A First In First Out (FIFO) Queue implemented as a circular slice.
func (*FIFO) Enqueue ¶
func (dq *FIFO) Enqueue(task RegisteredTask)
Add a task in O(1) amortized time.
type LIFO ¶
type LIFO struct {
// contains filtered or unexported fields
}
A Last In First Out (LIFO) Queue (also known as a stack) implemented with a slice.
func (*LIFO) Dequeue ¶
func (dq *LIFO) Dequeue() RegisteredTask
Dequeue (pop) a task off the LIFO in O(1) time.
func (*LIFO) Enqueue ¶
func (dq *LIFO) Enqueue(task RegisteredTask)
Enqueue (push) a task on the LIFO in O(1) amortized time.
type PTask ¶
A structure that satisfies the PrioritizedTask interface (and thus Task aswell).
type PrioritizedTask ¶
A PrioritizedTask is a Task that also has key (float64). Generally, a lower key means higher priority.
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
A heap-based priority queue. This implementation of a priority queue is ideal for many situations involving a priority queue. However, other priority queue implementations exist, each with their strengths and weaknesses. See ArrayPriorityQueue and VectorPriorityQueue.
func NewPriorityQueue ¶
func NewPriorityQueue() *PriorityQueue
Create a new heap-based priority queue.
func (*PriorityQueue) Dequeue ¶
func (pq *PriorityQueue) Dequeue() RegisteredTask
Remove a task from the queue with runtime O(log(n)).
func (*PriorityQueue) Enqueue ¶
func (pq *PriorityQueue) Enqueue(task RegisteredTask)
Add a task to the queue with runtime O(log(n)). The Task() method of task must satisfy the PrioritizedTask interface, or a runtime panic is thrown.
func (*PriorityQueue) SetKey ¶
func (pq *PriorityQueue) SetKey(id int64, k float64)
Set a task's key with runtime O(n).
type Queue ¶
type Queue interface { Enqueue(task RegisteredTask) // Insert a task Dequeue() RegisteredTask // Remove the next task. Len() int // Number of items waiting for processing. SetKey(int64, float64) // Set a task's key (priority queues). }
A Queue is a queue for RegisteredTasks, used by a Dispatch. Queue objects can be priority queues or not, but they all must implement a method SetKey(...). For non-priority queues, that method should just return immediately.
To avoid race conditions, when Queue methods are called by a Dispatch, the Dispatch locks the queue and prevents any other methods from being called on it. This is something to think about when creating/choosing a Queue implementation.
type RegisteredTask ¶
A Task given to a Dispatch is given a unique id and becomes a RegisteredTask.
type Task ¶
type Task interface { SetFunc(func(id int64)) Func() func(id int64) Type() string // Used mostly for debugging }
A Task is the interface satisfied by objects passed to a Dispatch.
type VectorPriorityQueue ¶
type VectorPriorityQueue struct {
// contains filtered or unexported fields
}
A priority queue based on the "container/vector" package. This priority queue implementation has fast dequeues and slow enqueues.
func NewVectorPriorityQueue ¶
func NewVectorPriorityQueue() *VectorPriorityQueue
Create a new VectorPriorityQueue.
func (*VectorPriorityQueue) Dequeue ¶
func (vpq *VectorPriorityQueue) Dequeue() RegisteredTask
Remove the task with the smallest key in O(1) amortized time.
func (*VectorPriorityQueue) Enqueue ¶
func (vpq *VectorPriorityQueue) Enqueue(task RegisteredTask)
Add a task to the priority queue in O(n) time. This is done with a O(log(n)) binary search and an insert operation.
func (*VectorPriorityQueue) Len ¶
func (vpq *VectorPriorityQueue) Len() int
Returns the number of PrioritizedTasks in the queue.
func (*VectorPriorityQueue) SetKey ¶
func (vpq *VectorPriorityQueue) SetKey(id int64, k float64)
Change the value of a task's key in O(n) time. This performs search, delete, and enqueue operations. Hence, this is not a fast method.