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

    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

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

        NewLazyQueue creates a new lazy queue

        func (*LazyQueue) Empty

        func (q *LazyQueue) Empty() bool

          Empty checks whether the priority queue is empty.

          func (*LazyQueue) MultiPop

          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

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

              Pop removes and returns the item with the greatest actual priority

              func (*LazyQueue) PopItem

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

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

                func (*LazyQueue) Push

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

                  Push adds an item to the queue

                  func (*LazyQueue) Refresh

                  func (q *LazyQueue) Refresh()

                    Refresh performs queue re-evaluation if necessary

                    func (*LazyQueue) Remove

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

                      Remove removes removes the item with the given index.

                      func (*LazyQueue) Reset

                      func (q *LazyQueue) Reset()

                        Reset clears the contents of the queue

                        func (*LazyQueue) Size

                        func (q *LazyQueue) Size() int

                          Size returns the number of items in the priority queue.

                          func (*LazyQueue) Update

                          func (q *LazyQueue) Update(index int)

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

                            type MaxPriorityCallback

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

                            type PriorityCallback

                            type PriorityCallback func(data interface{}) 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

                                  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

                                                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.