dimanche 28 novembre 2021

Using two different priority queues in Golang

I am a Gopher Noob. I ran into this question recently regarding implementing priority queues in Golang. I went through https://pkg.go.dev/container/heap@go1.17.3 for implementing a priority queue. All one has to do is implement the heap.Interface for the container. Its straightforward enough and i have no questions about that.

My question though is this: I need two priority queues. One is a minimum and maximum priority queue. In Java, this is quiet easy is initialize. I just have to change the comparator during initialization and thats it. In golang, I simply have to change the Less method in sort.Interface which is fine. However, I am not interested in writing redundant code and i am looking for cleaner way to create both priority queues.

Here is an example for what i am looking to do:

// A PriorityQueue1

type PriorityQueue1 []*Item

// Implement all the following methods for the min Prioirity queue
func (pq PriorityQueue1) Len() int { return len(pq) }

func (pq PriorityQueue1) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue1) Swap(i, j int) {
  //Swap
}

func (pq *PriorityQueue1) Push(x interface{}) {
  //Define push logic
}

func (pq *PriorityQueue1) Pop() interface{} {
  //Define pop logic
}

Now, I define the maximum priority queue (**everything is the same except Less**), which goes like this.. 

// A PriorityQueue2

type PriorityQueue2 []*Item

// Implement all the following methods for the max Prioirity queue
func (pq PriorityQueue2) Len() int { return len(pq) }

func (pq PriorityQueue2) Less(i, j int) bool {
    return **pq[i].priority < pq[j].priority**  // Thats it. One line change..
}

func (pq PriorityQueue2) Swap(i, j int) {
  //Swap
}

func (pq *PriorityQueue2) Push(x interface{}) {
  //Define push logic
}

func (pq *PriorityQueue2) Pop() interface{} {
  //Define pop logic
}

Now why would i have to go through this ordeal of rewriting almost the same methods as that of the min queue for a one line change in Less. I am looking to reduce the boilerplate and i am wondering about what is the cleanest and concise way to go about solving this question. I am also not interested in using any third party libraries (but i am interested in its logic if there is one which provides a clean wrapper).

Please provide some inputs. Thanks..

Aucun commentaire:

Enregistrer un commentaire