Go - Using a container/heap to implement a priority queue

Posted by Seth Hoenig on Stack Overflow See other posts from Stack Overflow or by Seth Hoenig
Published on 2011-01-16T06:27:08Z Indexed on 2011/01/16 7:53 UTC
Read the original article Hit count: 281

Filed under:
|
|

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.

© Stack Overflow or respective owner

Related posts about heap

Related posts about go

  • Go import error while trying to import web.go package after using goinstall

    as seen on Stack Overflow - Search for 'Stack Overflow'
    With halfdans advice, I was successfully able to use goinstall github.com/hoisie/web.go without any errors after installing git first. However, now when I try to compile the sample code given, go is not finding the web package. I get the error, main.go:4: can't find import: web On this code package… >>> More

  • Go Big or Go Home

    as seen on Oracle Blogs - Search for 'Oracle Blogs'
    The Oracle Develop conference (#oracledevelop10), being co-located for the first time ever with JavaOne in San Francisco, is guaranteed to be the ultimate rush for developers this year. Where else can you go to learn about, interact with, and meet fellow devotees of the entire Oracle Development… >>> More

  • Go Big or Go Home

    as seen on Oracle Blogs - Search for 'Oracle Blogs'
    For those who don’t know, Oracle sponsors a group called “OWL” – Oracle Women’s Leadership - and the purpose of the group is to create local and global opportunities that support, educate and empower current and future women leaders at Oracle. This week, I had the opportunity to attend the Denver… >>> More

  • Go Big or Go Special

    as seen on SQL Team - Search for 'SQL Team'
    Watching Shark Tank tonight and the first presentation was by Mango Mango Preserves and it highlighted an interesting contrast in business trends today and how to capitalize on opportunities.  <Spoiler Alert> Even though every one of the sharks was raving about the product samples they tried… >>> More

  • juju bootstrap fails with a local environment, why?

    as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
    Each time I try to bootstrap juju using a local enviroment it fails starting the juju-db-braiam-local script as follows: $ sudo juju --debug --verbose bootstrap 2013-10-20 02:28:53 INFO juju.provider.local environprovider.go:32 opening environment "local" 2013-10-20 02:28:53 DEBUG juju.provider.local… >>> More