How to sort duplicated Strings using comparator?

Question

Say i have a list containing workers, each workers has 3 fields: its name, the department he's working in (can be just the name of the department or an Object from the class Department) and his salary.

Elvis       Software Engineering        1000
Samba       Mechanical Engineering      2000
Bamba       Industrial Engineering      3000
Bisli       Medical Engineering         4000
Kinder      Electrical Engineering      1000
Elvis       Software Engineering        9999

now i want to sort them by their names and put the result in a Queue. and than put the queue in a map, ordered from the bottom to the top so the result i desire after the sort is:

Bamba       Industrial Engineering      3000
Bisli       Medical Engineering         4000
Elvis       Software Engineering        1000
Elvis       Software Engineering        9999
Samba       Mechanical Engineering      2000
Kinder      Electrical Engineering      1000

I'm not allowed to use Collection.sort(), so i'm using a comparator that sorts the workers by their names, if the name is equal - it sorts by the department, if the department is equal - it sorts by the salary. here's the comparator i wrote:

    class WorkerComparatorByName implements Comparator<Worker<?>> {
    @Override
    public int compare(Worker<?> w1, Worker<?> w2) {
        int compareValue = w1.getName().compareTo(w2.getName());
        if (compareValue != 0)
            return compareValue;
        compareValue = w1.getDepartment().toString().compareTo(w2.getDepartment().toString());
        if (compareValue != 0)
            return compareValue;
        return w1.getSalary() - w2.getSalary();

    }
}

problem is that the result is this:

Bamba       Industrial Engineering      3000
Bisli       Medical Engineering         4000
Elvis       Software Engineering        1000
Samba       Mechanical Engineering      2000
Kinder      Electrical Engineering      1000
Elvis       Software Engineering        9999

all the workers are sorted, but Elvis (which is duplicated) is NOT sorted, it stays at the end of the queue. I tried replacing Elvis with another duplicated name, and same result. What am i missing? how can i sort duplicated value so they'll be one after the other? Here's the code:

    public <T extends Worker<?>> Map<?, ?> createMap(ArrayList<T> list) {
    int i = 1;
    // creating a PriorityQueue sorted by names
    Queue<T> pq = new PriorityQueue<>(new WorkerComparatorByName());
    // filling the PriorityQueue with the workers
    pq.addAll(list);
    Map<Integer, T> treeMap = new TreeMap<Integer, T>();
    // iterating over the PriorityQueue and puting the workers in the map
    for (T element : pq)
        treeMap.put(i++, element);
    return treeMap;
}

Rumilly

Why are you using a PriorityQueue? If you want a data structure to sort the elements for you using that Comparator, use TreeSet. – Cataclysm

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()). Refer the docs: docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html – Ethicize

Answer 1

PriorityQueue API:

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()).

Hardily

Answer 2

Instead of using the foreach loop, use a normal for loop and poll() the items from the queue.

// creating a PriorityQueue sorted by names
Queue<T> pq = new PriorityQueue<>(new WorkerComparatorByName());

// filling the PriorityQueue with the workers
pq.addAll(list);

Map<Integer, T> treeMap = new TreeMap<Integer, T>();

int size = pq.size();
for (int j = 0; j < size; j++) {
        treeMap.put(j + 1, pq.poll());
}

Inconsiderable

thank you everyone, i used TreeSet and defined in the comparator that if the workers are the same, consider one of them as bigger. – Rumilly

Answer 3

Used this question as an streaming/lambda exercise, also used some Java 8 comparing goodies. Saw that you ended up using a TreeSet, which is a good solution, but I am adding this anyway if someone would be interested.

PriorityQueue<Worker> queue =
        new PriorityQueue<>(Comparator.comparing(Worker::getName)
                                    .thenComparing(Worker::getDepartment)
                                    .thenComparing(Worker::getSalary));
queue.addAll(list);

TreeMap<Integer, Worker> treeMap =
        IntStream.range(1, queue.size() + 1)
                .boxed()
                .collect(Collectors.toMap(Function.identity(),
                                          o -> queue.poll(),
                                          (u, v) -> { throw new Error("Will never happen"); },
                                          TreeMap::new));

Reenter