-
Notifications
You must be signed in to change notification settings - Fork 0
/
priority_queue.go
56 lines (47 loc) · 1.57 KB
/
priority_queue.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Package Pqueue implements a priority queue data structure supporting arbitrary
// value types and float priorities.
//
// The reasoning behind using floats for the priorities vs. ints or interfaces
// was larger flexibility without sacrificing too much performance or code
// complexity.
//
// 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.
package pqueue
import "container/heap"
// Priority queue data structure.
type Pqueue struct {
container *sStack
}
// Creates a new priority queue.
func New() *Pqueue {
return &Pqueue{newSstack()}
}
// Pushes a value with a given priority into the queue, expanding if necessary.
func (p *Pqueue) Push(data interface{}, priority float32) {
heap.Push(p.container, &item{data, priority})
}
// Pops the value with the greates priority off the stack and returns it.
// Currently no shrinking is done.
func (p *Pqueue) Pop() (interface{}, float32) {
item := heap.Pop(p.container).(*item)
return item.value, item.priority
}
// Pops only the value from the queue, dropping the associated priority.
func (p *Pqueue) PopValue() interface{} {
return heap.Pop(p.container).(*item).value
}
// Checks whether the priority queue is empty.
func (p *Pqueue) Empty() bool {
return p.container.Len() == 0
}
// Returns the number of element in the priority queue.
func (p *Pqueue) Size() int {
return p.container.Len()
}
// Clears the contents of the priority queue.
func (p *Pqueue) Reset() {
*p = *New()
}