1  package queue
 2  
 3  import (
 4  	"container/heap"
 5  )
 6  
 7  // PriorityQueueItem is an interface that represents items in a PriorityQueue.
 8  // Users of PriorityQueue will need to define a Less function such that
 9  // PriorityQueue will be able to use that to build and restore an underlying
10  // heap.
11  type PriorityQueueItem interface {
12  	// Less must return true if this item is ordered before other and false
13  	// otherwise.
14  	Less(other PriorityQueueItem) bool
15  }
16  
17  type priorityQueue []PriorityQueueItem
18  
19  // Len returns the length of the priorityQueue.
20  func (pq priorityQueue) Len() int { return len(pq) }
21  
22  // Less is used to order PriorityQueueItem items in the queue.
23  func (pq priorityQueue) Less(i, j int) bool {
24  	return pq[i].Less(pq[j])
25  }
26  
27  // Swap swaps two items in the priorityQueue. Swap is used by heap.Interface.
28  func (pq priorityQueue) Swap(i, j int) {
29  	pq[i], pq[j] = pq[j], pq[i]
30  }
31  
32  // Push adds a new item the priorityQueue.
33  func (pq *priorityQueue) Push(x interface{}) {
34  	item := x.(PriorityQueueItem)
35  	*pq = append(*pq, item)
36  }
37  
38  // Pop removes the top item from the priorityQueue.
39  func (pq *priorityQueue) Pop() interface{} {
40  	old := *pq
41  	n := len(old)
42  	item := old[n-1]
43  	old[n-1] = nil
44  	*pq = old[0 : n-1]
45  	return item
46  }
47  
48  // PriorityQueue wraps a standard heap into a self contained class.
49  type PriorityQueue struct {
50  	queue priorityQueue
51  }
52  
53  // Len returns the length of the queue.
54  func (pq *PriorityQueue) Len() int {
55  	return len(pq.queue)
56  }
57  
58  // Empty returns true if the queue is empty.
59  func (pq *PriorityQueue) Empty() bool {
60  	return len(pq.queue) == 0
61  }
62  
63  // Push adds an item to the priority queue.
64  func (pq *PriorityQueue) Push(item PriorityQueueItem) {
65  	heap.Push(&pq.queue, item)
66  }
67  
68  // Pop removes the top most item from the queue.
69  func (pq *PriorityQueue) Pop() PriorityQueueItem {
70  	return heap.Pop(&pq.queue).(PriorityQueueItem)
71  }
72  
73  // Top returns the top most item from the queue without removing it.
74  func (pq *PriorityQueue) Top() PriorityQueueItem {
75  	return pq.queue[0]
76  }