CODEWITHSUNDEEP
algorithmgopriority-queuereusability
cobie
cobie

Reputation: 7271

Reusable Priority queue implementation in google go

How would one go about writing the code for a reusable priority queue in Google Go or is one expected to define the Less Push and Pop function everytime a priority queue implementation is needed?

Upvotes: 1

Views: 717

Answers (4)

David Farrell
David Farrell

Reputation: 3722

I'm not sure I understand the question.

I've implemented a queue (and stack and ring) using interface{} as the stored type here:

https://github.com/iNamik/go_container

Using interface{} allows you to store any type you want - although it doesn't help you enforce types ala generics, it gets the job done.

I could see creating a priority queue without much hassle.

Am I missing something?

I'd be happy to add a priority queue container if you think you'd find it useful.

Upvotes: 0

Sonia
Sonia

Reputation: 28375

Haven't tried it, but maybe you could use reflection and struct tags, if your cases happened to fit certain restrictons. You would require that your heapable type be a struct with a tag like `pq:"Key"` on the field you use for ordering, and that that field type be < comparable. It's far less powerful than a Less method but it might meet your needs.

Sorry I have no example code for you. I don't think it wouldn be terribly hard, but it would take me some time. Left for an exercise.

I might try this technique if I had a situation where I needed to handle arbitrary structs and I could live with the simplistic key restriction. For a finite set of types though, I wouldn't do this. I would just do it by the book, implementing heap.Interface separately for each type. It's really not that much work nor that many lines of code.

Upvotes: 1

newacct
newacct

Reputation: 122489

There used to be vector types in the container/vector module of the standard library that implemented these methods, based on a resizable slice, and perfectly worked as the container to be used with the heap module. Unfortunately, they got rid of vector, which I never understood as it implemented a nice method-level abstraction over a slice variable. So now, every time I see someone using the heap module in Go, they have to basically re-implement part of vector -- writing Push, Pop, Length, etc. based on a slice variable.

Upvotes: 0

zzzz
zzzz

Reputation: 91303

The later case is what one has to do. As far as Go doesn't have generics, it's the only available option at the moment.

Upvotes: 3

Related Questions