What is wrong with my comparable interface logic?

Question

So the question is as follows

A unique id is assigned to each student entering the queue. The queue serves the students based on the following criteria (priority criteria):

The student having the highest Cumulative Grade Point Average (CGPA) is served first.

Any students having the same CGPA will be served by name in ascending case-sensitive alphabetical order.

Any students having the same CGPA and name will be served in ascending order of the id

My code

class Priorities{
    public List<Students> getStudents(List<String> events) {
            PriorityQueue<Students> pq = new PriorityQueue<Students>();
            for ( String s : events) {
                if ( s.contains("ENTER")) {
                    String [] arr = s.split(" ");
                    int id = Integer.parseInt(arr[3]);
                    String name = arr[1];
                    Double cgpa = Double.parseDouble(arr[2]);       
                    pq.add(new Students(id, name, cgpa));
                }
                else
                    pq.poll();
            
            }
            List<Students> studentList = new ArrayList<Students>(pq);
    
            return studentList;
        }
        
        
        
    }
    
class Students implements Comparable<Students>{
    
    int id;
    String name;
    double cgpa;
    
    public Students(int id, String name, double cgpa) {
        this.id = id;
        this.name = name;
        this.cgpa = cgpa;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getCgpa() {
        return cgpa;
    }

    public void setCgpa(double cgpa) {
        this.cgpa = cgpa;
    }
        // -1 return left, 1 return right
    public int compareTo(Students other) {
    if ( this.equals(other))
        return 0;
    else if ( this.getCgpa() > other.getCgpa())
        return -1;
    else if ( this.getCgpa() < other.getCgpa())
        return 1;
    else if ( this.getCgpa() == other.getCgpa() && this.getName().compareTo(other.getName()) == 0)
        return Integer.compare(this.getId(), other.getId());
    else 
        return this.getName().compareTo(other.getName());
    
        
}
}

Sample input

12
ENTER John 3.75 50
ENTER Mark 3.8 24
ENTER Shafaet 3.7 35
SERVED
SERVED
ENTER Samiha 3.85 36
SERVED
ENTER Ashley 3.9 42
ENTER Maria 3.6 46
ENTER Anik 3.95 49
ENTER Dan 3.95 50
SERVED

Sample output

Dan
Ashley
Shafaet
Maria

I'm getting the following

Dan
Ashley
Maria
Shafaet

Edit: Using

List<Students> studentList = new ArrayList<Students>();
        while(!pq.isEmpty())
        {
            studentList.add(pq.poll());
        }

instead of List studentList = new ArrayList(pq); helps with copying the exact order of the PQ to the list.

Answer 1

The issue is that PriorityQueue's ordering semantic are not guaranteed in its iterator (on top of that, note that PriorityQueue is not a List !)

Quoting from the java doc (emphasis mine) :

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Which means you will not get your comparator's ordering unless you use the queue semantics (e.g. add, poll, remove, offer... and the likes).

And looking at implementations, calling new ArrayList<Students>(pq); (or PriorityQueue#toString() for that matter) is implemented using an iterator, so it does not respect the priority.

The takeaway here :

• Using PriorityQueue is OK in the case of queue semantics only, not iteration / random access
• Combining both List and "live" sorting is not provided by a standard Java class that I know of (see also). (You can sort a list using a comparator, but there is no list that is sorted each time you add an element). There are such collections, though, using Set semantics, see TreeSet, you'll find them on the linked answers. Be warned that Set semantics are different (they maintain unicity of their elements, the meaning of unicity being somewhat tricky to get. For example, HashSet unicity is defined by hashCode/equals, but TreeSet's is defined by a comparator's).

That being said, Andy's implementation of the comparator is by far more readable (and avoids repetitions).

Answer 2

The general structure of a comparator should be: compare a field; if the field values differ, return; if they are the same, proceed to the next field.

In this case, it could look something like:

int cmp;

cmp = Double.compare(other.getCgpa(), this.getCgpa());
if (cmp != 0) return cmp;

cmp = this.getName().compareTo(other.getName());
if (cmp != 0) return cmp;

cmp = Integer.compare(this.getId(), other.getId());
if (cmp != 0) return cmp;

return 0;

(The last if and return could be collapsed to just return cmp;; but I think it's easier to extend later if you do it as above, because you can then just insert another cmp/if.)