Search code examples
javaqueuecomparatorpriority-queue

Can't get Priority Queue/Comparator to Work For Custom Objects


I know this question has been asked several times, but after searching through all the answers I don't think my problem is with using poll() during iteration, but perhaps my comparator is messed up. Every time I try to print the elements, they are in a random order. I understand that the priority queue internally is a tree, where the minimum element is the root. I figured iterating through and using poll() would work, but it didn't fix anything (before I tried to remove and making a custom iterator). I think something may be wrong with my comparator. I attached my code and the output output

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Iterator;

public class scheduleCPU
{

    public static void main(String[] args)
    {
        jobCompare compare = new jobCompare();
        PriorityQueue<JobNode> jobQueue = new PriorityQueue<>(); // creating queue of job nodes

        int pJob = 0;
        String nJob = null;
        int lJob = 0;
        Scanner userInput = new Scanner(System.in); // Create a Scanner object
        
        Boolean exitInput = false;

        // taking in input
        while(exitInput != true)
        {
            System.out.println("Enter priority, length, and name of job, enter 101 to stop entering jobs");
            pJob = userInput.nextInt();
            
            if(pJob ==101) 
            {
                userInput.close();
                break;
            }
            
            lJob = userInput.nextInt();
            
            nJob = userInput.next();
            
            JobNode currentJob = new JobNode(pJob, nJob, lJob); 
            jobQueue.add(currentJob);
        }
        
        Iterator<JobNode> jobIt = jobQueue.iterator();
        // to print the jobs
        while(!jobQueue.isEmpty()) 
        {
            // Arrays.sort(jobQueue.toArray());
            JobNode currentJob = jobQueue.poll();
            System.out.println(currentJob.name);
            // System.out.println(jobQueue);
        }
        
        // to process the jobs
        while(jobQueue.size()>0) 
        {
        JobNode current = jobQueue.remove();
        int jobLength = current.length;
        for(int i =0; i<jobLength;i++) 
        {
            System.out.println("Job"+ current.name + " is " + ((i/jobLength)*100) + "% complete");
        }
        }
    }

}

class JobNode implements Comparable<JobNode>
{
    int priority;
    String name;
    int length;

    // constructor
    JobNode(int p, String n, int l)
    {
        priority = p;
        name = n;
        length = l;
    }

    @Override
    public int compareTo(JobNode o)
    {
        return this.priority;
    }
}

class jobCompare implements Comparator<JobNode>
{
    @Override
    public int compare(JobNode j1, JobNode j2)
    {
        if (j1.priority < j2.priority)
            return 1;
        else if (j1.priority > j2.priority)
            return -1;
        return 0;
    }
}

Solution

  • You've incorrectly implemented Comparable interface in the JobNode.

    Instead of comparing priority values of two JobNode instances (this and the argument o), you're simply returning the value of priority of this instance, ignoring the argument.

    That's how compareTo() implementation might look like:

    @Override
    public int compareTo(JobNode o) {
        return Integer.compare(priority,  o.priority);
    }