package main

import (
	"container/heap"
)

// pqueue represents a min priority queue
// it implements the heap.Interface interface
type pqueue []*node

func newPriorityQueue() *pqueue {
	pq := make(pqueue, 0)
	return &pq
}

func (pq pqueue) Len() int {
	return len(pq)
}

func (pq *pqueue) Push(x interface{}) {
	n := len(*pq)
	node := x.(*node)
	node.index = n
	*pq = append(*pq, node)
}

func (pq *pqueue) Pop() interface{} {
	old := *pq
	n := len(old)
	node := old[n-1]
	node.index = -1
	*pq = old[0 : n-1]
	return node
}

func (pq *pqueue) Update(node *node, value int) {
	node.cost = value
	heap.Fix(pq, node.index)
}

func (pq pqueue) Less(i, j int) bool {
	return pq[i].cost < pq[j].cost
}

func (pq pqueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}