queue

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 NewPriorityQueue(opts ...PriorityQueueOption) *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
  • func (i *PriorityQueueItem) GetData() interface{}
  • func (i *PriorityQueueItem) GetPriority() int64
  • func (i *PriorityQueueItem) SetData(v interface{})
  • func (i *PriorityQueueItem) SetPriority(v int64)
• type PriorityQueueOption
  • func WithCapacity(v uint) PriorityQueueOption
  • func WithMaxHeap() PriorityQueueOption
  • func WithMinHeap() PriorityQueueOption

Examples

• PriorityQueue

Constants

const (
	// DefaultPriorityQueueCapacity is the default priority queue capacity.
	DefaultPriorityQueueCapacity = math.MaxUint
)

This section defines default configuration.

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) Clear

func (q *PriorityQueue) Clear()

Clear removes all items in the 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.