CODEWITHSUNDEEP
go
jpittis
jpittis

Reputation: 177

Go heap.Interface as a struct

I'm creating a priority queue using Go's heap package. There is an example of one in the documentation.

The queue I'm creating needs to be based around a struct rather than a slice because it requires other properties like a mutex.

type PQueue struct {
    queue []*Item
    sync.Mutex
}

I implement all the methods that heap.Interface requires.

The issue is that my PQueue.Push method seems not to be permanently adding a value to PQueue.queue.

func (p PQueue) Push(x interface{}) {
    p.Lock()
    defer p.Unlock()
    item := x.(*Item)
    item.place = len(p.queue) // the index of an item in the queue
    p.queue = append(p.queue, item)
    // len(p.queue) does increase
    // after the functions exits, the queues length has not increased
}

If I print the length of p.queue at the end of this function, the length has increased. After the functions exits however, it seems the original struct does not get updated.

I think it might be happening because of func (p PQueue) not being a pointer. Why might that be? Is there a way to fix it? If I were to use func (p *PQeueue) Push(x interface{}) instead, I would need to implement my own heap because heap.Interface specifically requires no pointer. Is that my only option?

Upvotes: 0

Views: 628

Answers (3)

Frederik Deweerdt
Frederik Deweerdt

Reputation: 5281

I think it might be happening because of func (p PQueue) not being a pointer

That's right. Quoting Effective Go:

invoking [the method] on a value would cause the method to receive a copy of the value, so any modifications would be discarded.

You say:

heap.Interface specifically requires no pointer

I'm confused, the example you point to is, in fact, using a pointer:

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

Maybe something else is going on?

Upvotes: 0

IamNaN
IamNaN

Reputation: 6864

The problem is that you are appending to a copy of your slice. Thus the change shows within the function, but is lost once you return from the function.

In this blog article from the section Passing slices to functions:

It's important to understand that even though a slice contains a pointer, it is itself a value. Under the covers, it is a struct value holding a pointer and a length. It is not a pointer to a struct.

With append you are modifying the slice header. And

Thus if we want to write a function that modifies the header, we must return it as a result parameter

Or:

Another way to have a function modify the slice header is to pass a pointer to it.

As a result you need to pass a pointer if you want to modify it with append. Simply change the method to use a pointer receiver. And for that to work you need to call init with a pointer like heap.Init(&pq) as shown in the example that you linked to which does just that and also uses pointer receivers.

From the spec on Method Sets:

The method set of the corresponding pointer type *T is the set of all methods declared with receiver *T or T (that is, it also contains the method set of T).

So using a pointer type will work with value and pointer receivers and still implement the interface.

Upvotes: 3

James Henstridge
James Henstridge

Reputation: 43929

You are right about the problem being related to the receiver of your Push method: the method will receive a copy of the PQueue, so any changes made to the struct will not persist.

Changing the method to use a pointer as a receiver is the correct change, but this also means that PQueue no longer implements heap.Interface. This is due to the fact that Go does not let you take a pointer to the value stored inside an interface variable, so the automatic translation of q.Push() to (&q).Push() does not occur.

This isn't a dead end though, since *PQueue should still implement the heap.Interface. So if you were previously calling heap.Init(q), just change it to heap.Init(&q).

Upvotes: 2

Related Questions