开发者

Using a container/heap to implement a priority queue

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.


UPDATE: For the sake of those who come across this in searches in the future, the code above is chock full of gross misconceptions. Take a look below for a much more useful template to work off of: Node.go:

// Node.go
package pqueue

import "fmt"

type Node struct {
    row    int
    col    int
    myVal  int
    sumVal int
    parent *Node
}

func NewNode(r, c, mv, sv int, n *Node) *Node {
    return &Node{r, c, mv, sv, n}
}

func (n *Node) Eq(o *Node) bool {
    return n.row == o.row && n.col == o.col
}

func (n *Node) String() string {
    return fmt.Sprintf("{%d, %d, %d, %d}", n.row, n.col, n.myVal, n.sumVal)
}

func (n *Node) Row() int {
    return n.row
}

func (n *Node) Col() int {
    return n.col
}

func (n *Node) SetParent(p *Node) {
    n.parent = p
}

func (n *Node) Parent() *Node {
    return n.parent
}

func (n *Node) MyVal() int {
    return n.myVal
}

func (n *Node) SumVal() int {
    return n.sumVal
}

func (n *Node) SetSumVal(sv int) {
    n.sumVal = sv
}

PQueue.go:

// PQueue.go
package pqueue

type PQueue []*Node

func (pq *PQueue) IsEmpty() bool {
    return len(*pq) == 0
}

func (pq *PQueue) Push(i interface{}) {
    a := *pq
    n := len(a)
    a = a[0 : n+1]
    r := i.(*Node)
    a[n] = r
    *pq = a
}

func (pq *PQueue) Pop() interface{} {
    a := *pq
    *pq = a[0 : len(a)-1]
    r := a[len(a)-1]
    return r
}

func (pq *PQueue) Len() int {
    return len(*pq)
}

// post: true iff is i less than j
func (pq *PQueue) Less(i, j int) bool {
    I := (*pq)[i]
    J := (*pq)[j]
    return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}

func (pq *PQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}

func (pq *PQueue) String() string {
    var build string = "{"
    for _, v := range *pq {
        build += v.String()
    }
    build += "}"
    return build
}


package main
var PQ pqueue.PQueue
var firstNode pqueue.Node
PQ.Push(firstNode)

The variable firstNode is passed by value which means that there is an implicit assignment of the argument to the parameter in the function call PQ.Push(firstNode). The type pqueue.Node contains private fields such as row which are not exported from package pqueue to package main: "implicit assignment of unexported field 'row' of pqueue.Node in function argument."

In Node.go, add this function to package pqueue:

func NewNode() *Node {
    return &Node{}
}

In PQueue.go, add this function to package pqueue:

func NewPQueue() *PQueue {
    return &PQueue{}
}

Then. in package main, you can write:

PQ := pqueue.NewPQueue()
firstNode := pqueue.NewNode()
PQ.Push(firstNode)
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜