prque

package
v1.14.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 21, 2021 License: GPL-3.0 Imports: 3 Imported by: 0

Documentation

Overview

Package prque implements a priority queue data structure supporting arbitrary value types and int64 priorities.

If you would like to use a min-priority queue, simply negate the priorities.

Internally the queue is based on the standard heap package working on a sortable version of the block based stack.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type LazyQueue added in v1.9.2

type LazyQueue struct {
	// contains filtered or unexported fields
}

LazyQueue is a priority queue data structure where priorities can change over time and are only evaluated on demand. Two callbacks are required:

  • priority evaluates the actual priority of an item
  • maxPriority gives an upper estimate for the priority in any moment between now and the given absolute time

If the upper estimate is exceeded then Update should be called for that item. A global Refresh function should also be called periodically.

func NewLazyQueue added in v1.9.2

func NewLazyQueue(setIndex SetIndexCallback, priority PriorityCallback, maxPriority MaxPriorityCallback, clock mclock.Clock, refreshPeriod time.Duration) *LazyQueue

NewLazyQueue creates a new lazy queue

func (*LazyQueue) Empty added in v1.9.2

func (q *LazyQueue) Empty() bool

Empty checks whether the priority queue is empty.

func (*LazyQueue) MultiPop added in v1.9.2

func (q *LazyQueue) MultiPop(callback func(data interface{}, priority int64) bool)

MultiPop pops multiple items from the queue and is more efficient than calling Pop multiple times. Popped items are passed to the callback. MultiPop returns when the callback returns false or there are no more items to pop.

func (*LazyQueue) Pop added in v1.9.2

func (q *LazyQueue) Pop() (interface{}, int64)

Pop removes and returns the item with the greatest actual priority

func (*LazyQueue) PopItem added in v1.9.2

func (q *LazyQueue) PopItem() interface{}

PopItem pops the item from the queue only, dropping the associated priority value.

func (*LazyQueue) Push added in v1.9.2

func (q *LazyQueue) Push(data interface{})

Push adds an item to the queue

func (*LazyQueue) Refresh added in v1.9.2

func (q *LazyQueue) Refresh()

Refresh performs queue re-evaluation if necessary

func (*LazyQueue) Remove added in v1.9.2

func (q *LazyQueue) Remove(index int) interface{}

Remove removes removes the item with the given index.

func (*LazyQueue) Reset added in v1.9.2

func (q *LazyQueue) Reset()

Reset clears the contents of the queue

func (*LazyQueue) Size added in v1.9.2

func (q *LazyQueue) Size() int

Size returns the number of items in the priority queue.

func (*LazyQueue) Update added in v1.9.2

func (q *LazyQueue) Update(index int)

Update updates the upper priority estimate for the item with the given queue index

type MaxPriorityCallback added in v1.9.2

type MaxPriorityCallback func(data interface{}, until mclock.AbsTime) int64 // estimated maximum priority callback

type PriorityCallback added in v1.9.2

type PriorityCallback func(data interface{}, now mclock.AbsTime) int64 // actual priority callback

type Prque

type Prque struct {
	// contains filtered or unexported fields
}

Priority queue data structure.

func New

func New(setIndex SetIndexCallback) *Prque

New creates a new priority queue.

func (*Prque) Empty

func (p *Prque) Empty() bool

Checks whether the priority queue is empty.

func (*Prque) Peek added in v1.9.0

func (p *Prque) Peek() (interface{}, int64)

Peek returns the value with the greates priority but does not pop it off.

func (*Prque) Pop

func (p *Prque) Pop() (interface{}, int64)

Pops the value with the greates priority off the stack and returns it. Currently no shrinking is done.

func (*Prque) PopItem

func (p *Prque) PopItem() interface{}

Pops only the item from the queue, dropping the associated priority value.

func (*Prque) Push

func (p *Prque) Push(data interface{}, priority int64)

Pushes a value with a given priority into the queue, expanding if necessary.

func (*Prque) Remove

func (p *Prque) Remove(i int) interface{}

Remove removes the element with the given index.

func (*Prque) Reset

func (p *Prque) Reset()

Clears the contents of the priority queue.

func (*Prque) Size

func (p *Prque) Size() int

Returns the number of element in the priority queue.

type SetIndexCallback added in v1.9.0

type SetIndexCallback func(data interface{}, index int)

SetIndexCallback is called when the element is moved to a new index. Providing SetIndexCallback is optional, it is needed only if the application needs to delete elements other than the top one.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL