Documentation
¶
Overview ¶
Package queue provides queue data structure.
Priority Queue ¶
PriorityQueue implements container/heap and enriches it with additional features, such as Peek, Update, Remove, Contains, List, Clear, etc.
PriorityQueue provides a standard priority queue feature.
// create priority queue. pq, _ := queue.NewPriorityQueue() pq.Push(1, 1) // push peekItem := pq.Peek() // peek popItem := pq.Pop() // pop
Item priority can be updated after it is pushed.
// change item priority pushItem := pq.Push(1, 1) pushItem.SetPriority(2) // update item priority in queue pq.Update(pushItem)
Remove an item in the queue without pop.
// change item priority pushItem := pq.Push(1, 1) // remove item in queue pq.Remove(pushItem)
Default priority uses min heap, smaller value means higher priority. You can change the heap type to max heap via option. With max heap, a smaller value means lower priority.
pq, _ := queue.NewPriorityQueue() pq.Push(1, 1) // higher priority pq.Push(2, 2) // lower priority pq, _ = queue.NewPriorityQueue(queue.WithMaxHeap()) pq.Push(1, 1) // lower priority pq.Push(2, 2) // higher priority
Index ¶
- Constants
- type PriorityQueue
- func (q *PriorityQueue) Clear()
- func (q *PriorityQueue) Contains(item *PriorityQueueItem) bool
- func (q *PriorityQueue) Len() int
- func (q *PriorityQueue) List() []*PriorityQueueItem
- func (q *PriorityQueue) Peek() *PriorityQueueItem
- func (q *PriorityQueue) Pop() *PriorityQueueItem
- func (q *PriorityQueue) Push(data interface{}, priority int64) (*PriorityQueueItem, error)
- func (q *PriorityQueue) Remove(item *PriorityQueueItem) *PriorityQueueItem
- func (q *PriorityQueue) Update(item *PriorityQueueItem) error
- type PriorityQueueItem
- type PriorityQueueOption
Examples ¶
Constants ¶
const ( // DefaultPriorityQueueCapacity is the default priority queue capacity. DefaultPriorityQueueCapacity = math.MaxUint )
This section defines default configuration.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
PriorityQueue implements a priority queue with a heap. By default, min heap is used with a default queue capacity. Items are sorted by priority, smaller value means higher priority. Queue capacity and heap type can be changed via options.
Example ¶
package main
import (
"fmt"
"github.com/getoutreach/gobox/pkg/queue"
)
func main() {
// Create priority queue.
pq := queue.NewPriorityQueue()
// Push items.
pushItem := func(data interface{}, priority int64) *queue.PriorityQueueItem {
item, err := pq.Push(data, priority)
if err != nil {
panic(err)
}
return item
}
item1 := pushItem(1, 1)
item2 := pushItem(2, 2)
item3 := pushItem(3, 3)
// List items.
list := func(msg string) {
fmt.Println(msg)
for _, item := range pq.List() {
fmt.Println(item.GetPriority(), item.GetData())
}
}
list("list items after push")
// Update item priority.
item1.SetPriority(3)
item2.SetPriority(1)
item3.SetPriority(2)
pq.Update(item1)
pq.Update(item2)
pq.Update(item3)
list("list items after update")
// Remove an item.
pq.Remove(item3)
list("list items after remove")
// Pop items.
fmt.Println("pop items")
for {
item := pq.Pop()
if item == nil {
break
}
fmt.Println(item.GetPriority(), item.GetData())
}
list("list items after pop")
}
Output: list items after push 1 1 2 2 3 3 list items after update 1 2 2 3 3 1 list items after remove 1 2 3 1 pop items 1 2 3 1 list items after pop
func NewPriorityQueue ¶
func NewPriorityQueue(opts ...PriorityQueueOption) *PriorityQueue
NewPriorityQueue creates a new priority queue.
func (*PriorityQueue) Contains ¶
func (q *PriorityQueue) Contains(item *PriorityQueueItem) bool
Contains returns true if the item is in the queue.
func (*PriorityQueue) Len ¶
func (q *PriorityQueue) Len() int
Len returns the number of items in the queue.
func (*PriorityQueue) List ¶
func (q *PriorityQueue) List() []*PriorityQueueItem
List returns a list of items, sorted by priority.
func (*PriorityQueue) Peek ¶
func (q *PriorityQueue) Peek() *PriorityQueueItem
Peek returns the first item in the queue. Peek returns nil if the queue is empty.
func (*PriorityQueue) Pop ¶
func (q *PriorityQueue) Pop() *PriorityQueueItem
Pop removes and returns the first item in the queue. Pop returns nil if the queue is empty.
func (*PriorityQueue) Push ¶
func (q *PriorityQueue) Push(data interface{}, priority int64) (*PriorityQueueItem, error)
Push an item into the queue. Items in the queue will be sorted by priority. Push returns a PriorityQueueItem that can be used for other operations, such as updating item priority or removing the item from the queue.
func (*PriorityQueue) Remove ¶
func (q *PriorityQueue) Remove(item *PriorityQueueItem) *PriorityQueueItem
Remove an item from the queue and return the removed item. If the item does not exist in queue, return nil.
func (*PriorityQueue) Update ¶
func (q *PriorityQueue) Update(item *PriorityQueueItem) error
Update the item priority in the queue. Call this function when the item priority is changed. Return error if the item is not updated successfully.
type PriorityQueueItem ¶
type PriorityQueueItem struct {
// contains filtered or unexported fields
}
PriorityQueueItem represents an item in queue.
func (*PriorityQueueItem) GetData ¶
func (i *PriorityQueueItem) GetData() interface{}
GetData returns the data.
func (*PriorityQueueItem) GetPriority ¶
func (i *PriorityQueueItem) GetPriority() int64
GetPriority returns the priority.
func (*PriorityQueueItem) SetData ¶
func (i *PriorityQueueItem) SetData(v interface{})
SetData sets the data.
func (*PriorityQueueItem) SetPriority ¶
func (i *PriorityQueueItem) SetPriority(v int64)
SetPriority sets priority.
type PriorityQueueOption ¶
type PriorityQueueOption func(q *PriorityQueue)
PriorityQueueOption is used to change priority default configuration.
func WithCapacity ¶
func WithCapacity(v uint) PriorityQueueOption
WithCapacity sets the queue capacity.
func WithMaxHeap ¶
func WithMaxHeap() PriorityQueueOption
WithMaxHeap sets the priority queue to use max heap. A smaller value means lower priority with max heap.
func WithMinHeap ¶
func WithMinHeap() PriorityQueueOption
WithMinHeap sets the priority queue to use min heap. A smaller value means higher priority with min heap.
Source Files