Go - Using a container/heap to implement a priority queue
- by Seth Hoenig
In the big picture, I'm trying to implement Dijkstra's algorithm using a priority queue.
According to members of golang-nuts, the idiomatic way to do this in Go is to use the heap interface with a custom underlying data structure. So I have created Node.go and PQueue.go like so:
//Node.go
package pqueue
type Node struct {
row int
col int
myVal int
sumVal int
}
func (n *Node) Init(r, c, mv, sv int) {
n.row = r
n.col = c
n.myVal = mv
n.sumVal = sv
}
func (n *Node) Equals(o *Node) bool {
return n.row == o.row && n.col == o.col
}
And PQueue.go:
// PQueue.go
package pqueue
import "container/vector"
import "container/heap"
type PQueue struct {
data vector.Vector
size int
}
func (pq *PQueue) Init() {
heap.Init(pq)
}
func (pq *PQueue) IsEmpty() bool {
return pq.size == 0
}
func (pq *PQueue) Push(i interface{}) {
heap.Push(pq, i)
pq.size++
}
func (pq *PQueue) Pop() interface{} {
pq.size--
return heap.Pop(pq)
}
func (pq *PQueue) Len() int {
return pq.size
}
func (pq *PQueue) Less(i, j int) bool {
I := pq.data.At(i).(Node)
J := pq.data.At(j).(Node)
return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}
func (pq *PQueue) Swap(i, j int) {
temp := pq.data.At(i).(Node)
pq.data.Set(i, pq.data.At(j).(Node))
pq.data.Set(j, temp)
}
And main.go: (the action is in SolveMatrix)
// Euler 81
package main
import "fmt"
import "io/ioutil"
import "strings"
import "strconv"
import "./pqueue"
const MATSIZE = 5
const MATNAME = "matrix_small.txt"
func main() {
var matrix [MATSIZE][MATSIZE]int
contents, err := ioutil.ReadFile(MATNAME)
if err != nil {
panic("FILE IO ERROR!")
}
inFileStr := string(contents)
byrows := strings.Split(inFileStr, "\n", -1)
for row := 0; row < MATSIZE; row++ {
byrows[row] = (byrows[row])[0 : len(byrows[row])-1]
bycols := strings.Split(byrows[row], ",", -1)
for col := 0; col < MATSIZE; col++ {
matrix[row][col], _ = strconv.Atoi(bycols[col])
}
}
PrintMatrix(matrix)
sum, len := SolveMatrix(matrix)
fmt.Printf("len: %d, sum: %d\n", len, sum)
}
func PrintMatrix(mat [MATSIZE][MATSIZE]int) {
for r := 0; r < MATSIZE; r++ {
for c := 0; c < MATSIZE; c++ {
fmt.Printf("%d ", mat[r][c])
}
fmt.Print("\n")
}
}
func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
var PQ pqueue.PQueue
var firstNode pqueue.Node
var endNode pqueue.Node
msm1 := MATSIZE - 1
firstNode.Init(0, 0, mat[0][0], 0)
endNode.Init(msm1, msm1, mat[msm1][msm1], 0)
if PQ.IsEmpty() { // make compiler stfu about unused variable
fmt.Print("empty")
}
PQ.Push(firstNode) // problem
return 0, 0
}
The problem is, upon compiling i get the error message:
[~/Code/Euler/81] $ make
6g -o pqueue.6 Node.go PQueue.go
6g main.go
main.go:58: implicit assignment of unexported field 'row' of pqueue.Node in function argument
make: *** [all] Error 1
And commenting out the line PQ.Push(firstNode) does satisfy the compiler. But I don't understand why I'm getting the error message in the first place. Push doesn't modify the argument in any way.
