Priority queues of objects in Java

Question

Hello Im a bit lost n the priority queues and comparator. I dont really see how to make a comparator in java So what I have is giving me a error and what I have read is no help to me http://www.tutorialspoint.com/java/java_using_comparator.htm This post game me some ideas but Im still stuck on how to do it How do I use a PriorityQueue?

What i have is a class that creates an object with a priority, arrival time, and finish time. I also have a number of priority queues to place them into. When i start I place them into the arrival queue to sort them and then see which one came in first and place that into the queue one. But when I try to add a second one to the arrival queue it fails and throws an exception. What I want to do first is to add all the processes to the arrival queue and then sort them so the one with the smallest arrival time will be the first one out of the arrival queue and into the queue one. Thanks for any help with this

    //the comparator
    Comparator<Integer> comparator = new Comparator();
    //priority queues
    //only needs 10 elements to  hold
    PriorityQueue one = new PriorityQueue(10, comparator);
    PriorityQueue two = new PriorityQueue(10, comparator);
    PriorityQueue three = new PriorityQueue(10, comparator);
    PriorityQueue four = new PriorityQueue(10, comparator);
    PriorityQueue arrival = new PriorityQueue(10, comparator);

    //put all processes in arrival queue
    arrival.add(p1);
    arrival.add(p2);
    arrival.add(p3);
    arrival.add(p4);
    arrival.add(p5);
    arrival.add(p6);
    arrival.add(p7);
    arrival.add(p8);
    arrival.add(p9);
    arrival.add(p10);

Solution

Let's look at how you're defining Comparator, because at the moment I don't think what you've written would even compile.

Comparator is an interface, meaning that you need to define a class that implements it. That is, you need to define a class that has concrete implementations of the methods described by the interface. Here, there's only one method you need to worry about - compare. (The interface also defines equals, but that's an odd choice since it's equal to the one on Object and so every class will implement this by default...)

The compare method takes two objects of the target type, and decides which one of them comes "before" the other. It returns:

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

So - you want to compare objects of whatever the class of your p1, p2 instances are (I'll call it MyClass). That means that you have to define a class:

class MyComparator implements Comparator<MyClass> {

    public int compare(MyClass a, MyClass b) {
        // TODO
    }
}

We know that the compare method should return a value depending on which of the MyClass arguments comes before the other one. You've said in your question that the one that comes first, is the one that has the smallest (i.e. earliest?) arrival time.

This is actually very easy, because that's the so-called natural ordering on java.util.Date objects - so you can just compare their arrival times against each other directly, as the result of that comparison is the same as the overall comparison.

Therefore the implementation of compare can simply be (assuming a sensibly-named accessor method):

public int compare(MyClass a, MyClass b) {
    return a.getStartTime().compareTo(b.getStartTime());
}

And there you go! You've just defined your own comparator, that will sort MyClass objects by start time ascending. You can use it in the priority queues similarly to what you have already:

Comparator<MyClass> comparator = new MyComparator();
PriorityQueue<MyClass> arrival = new PriorityQueue<MyClass>(10, comparator);

Comments

[MNM]

Ah thanks now I see what I was getting wrong, but one problem on the comparing part {return a.getArrivalTime().compareTo(b.getArrivalTime()); } this gives an error int cannot be dereferenced what does that mean?

[Andrzej Doyle]

Oh, you're storing the start times as ints? That may not be the best choice to represent an instance in time (if nothing else you should write a wrapper class for clarity and somewhere to put methods), but fair enough. In that case you need to compare two ints - use b.getStartTime() - a.getStartTime() for this (which returns an appropriate answer from compareTo).

[Andrzej Doyle]

To answer your actual question - "int cannot be dereferenced" means that you can't call methods on an int (or get fields - anything that involves dereferencing by using the dot to refer to something inside it). Only objects can be dereferenced, and since an int is a primitive, it's not an object so has no fields/methods and can't be dereferenced.