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 ¶
- type LazyQueue
- func (q *LazyQueue) Empty() bool
- func (q *LazyQueue) MultiPop(callback func(data interface{}, priority int64) bool)
- func (q *LazyQueue) Pop() (interface{}, int64)
- func (q *LazyQueue) PopItem() interface{}
- func (q *LazyQueue) Push(data interface{})
- func (q *LazyQueue) Refresh()
- func (q *LazyQueue) Remove(index int) interface{}
- func (q *LazyQueue) Reset()
- func (q *LazyQueue) Size() int
- func (q *LazyQueue) Update(index int)
- type MaxPriorityCallback
- type PriorityCallback
- type Prque
- func (p *Prque) Empty() bool
- func (p *Prque) Peek() (interface{}, int64)
- func (p *Prque) Pop() (interface{}, int64)
- func (p *Prque) PopItem() interface{}
- func (p *Prque) Push(data interface{}, priority int64)
- func (p *Prque) Remove(i int) interface{}
- func (p *Prque) Reset()
- func (p *Prque) Size() int
- type SetIndexCallback
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LazyQueue ¶ added in v0.4.0
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 v0.4.0
func NewLazyQueue(setIndex SetIndexCallback, priority PriorityCallback, maxPriority MaxPriorityCallback, clock mclock.Clock, refreshPeriod time.Duration) *LazyQueue
NewLazyQueue creates a new lazy queue
func (*LazyQueue) MultiPop ¶ added in v0.4.0
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 v0.4.0
Pop removes and returns the item with the greatest actual priority
func (*LazyQueue) PopItem ¶ added in v0.4.0
func (q *LazyQueue) PopItem() interface{}
PopItem pops the item from the queue only, dropping the associated priority value.
func (*LazyQueue) Push ¶ added in v0.4.0
func (q *LazyQueue) Push(data interface{})
Push adds an item to the queue
func (*LazyQueue) Refresh ¶ added in v0.4.0
func (q *LazyQueue) Refresh()
Refresh performs queue re-evaluation if necessary
func (*LazyQueue) Reset ¶ added in v0.4.0
func (q *LazyQueue) Reset()
Reset clears the contents of the queue
type MaxPriorityCallback ¶ added in v0.4.0
type PriorityCallback ¶ added in v0.4.0
type Prque ¶
type Prque struct {
// contains filtered or unexported fields
}
Priority queue data structure.
func (*Prque) Peek ¶ added in v0.1.6
Peek returns the value with the greates priority but does not pop it off.
func (*Prque) Pop ¶
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.
type SetIndexCallback ¶ added in v0.1.6
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.