I am getting confused on the PriorityQueue, not sure if there is a different method for my use case.

Instead of comparing two Strings, I want to compare the incoming Strings against a String[].

It somewhat works but the head node does not move.

Main:

public class App 
{
    public static void main( String[] args )
    {
        PriorityString priorityString = new PriorityString();
        
        PriorityQueue<String> priorityQueue = new PriorityQueue<String>(priorityString);
        
        priorityQueue.add("test");
        priorityQueue.add("john");
        priorityQueue.add("blue");
        priorityQueue.add("orange");
        priorityQueue.add("grape");
        priorityQueue.add("handle");
        
        while (!priorityQueue.isEmpty()) {
            System.out.println("Removed: "   priorityQueue.remove());
        } 
    }
}

Comparator class:

public class PriorityString implements Comparator<String> {
    
    String[] valueStrings;
    
    PriorityString() {
        valueStrings = new String[] {"all", "john", "door", "floor", "record", "desk", "orange"};
    }

    public int compare(String o1, String o2) {
        if (Arrays.asList(valueStrings).contains(o1))
            return 0;
        else
            return 1;
    }

}

Result:

Removed: test
Removed: john
Removed: orange
Removed: blue
Removed: handle
Removed: grape

The values 'test' comes first all the time even though it is not in the String[]. The other values seem to be in the correct order since 'john' and 'orange' are in the String[] and the rest is not.

What is the issue and is this the right way to implement my use case?

Edit: I have also tried this

    public int compare(String o1, String o2) {
        if (Arrays.asList(valueStrings).contains(o1))
            return -1;
        else if (Arrays.asList(valueStrings).contains(o2)) 
            return 0;
        else
            return 1;
    }

Which gives this result:

Removed: orange
Removed: handle
Removed: grape
Removed: test
Removed: blue
Removed: john

orange is in the right place by john is at the bottom when it should be right after orange

New Edit: after rereading the doc as per the comment, I managed to get a working version implemented in this way. Probably will add @Progman else return.

    public int compare(String o1, String o2) {
        if (Arrays.asList(valueStrings).contains(o1))
            return -1;
        else if (Arrays.asList(valueStrings).contains(o2)) 
            return 1;
        else
            return 0;
    }

Result:

Removed: orange
Removed: john
Removed: grape
Removed: test
Removed: blue
Removed: handle

CodePudding user response：

Your compare() method is not checking both String objects coming in. That makes it difficult to compare two strings when you look only at one. Also, your compare() method is not symmetric in a sense that sgn(compare(x,y)) is not the same as -sgn(compare(y,x)) (notice the -), as defined in https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#compare-T-T-. Which makes it very difficult (or unpredictable) how the String objects are ordered inside by the PriorityQueue.

When you want some kind of "VIP" String list, which are sorted at the beginning, you have to check for several situations for the compare(x, y) method:

• x is a "VIP" value, but y is not.
• x is a "VIP" value as well as y.
• x is not a "VIP" value, but y is.
• x is not a "VIP" value, neither is y.

Specially, when the values are both "VIP" values or are both NOT "VIP" values, you still have to return a reasonable compare value for these strings. The approach is to handle the cases first where one value is in the "VIP" list and the other is not. After that, compare the strings as normal using String.compareTo(). The method can look like this:

public int compare(String o1, String o2) {
    if (valueStringsList.contains(o1) &&
        !valueStringsList.contains(o2)) {
        return -1; // only o1 is a "VIP"
    }
    if (!valueStringsList.contains(o1) &&
        valueStringsList.contains(o2)) {
        return 1;  // only o2 is a "VIP"
    }
    return o1.compareTo(o2); // normal sorting
}

(You might need to swap 1 and -1)

CodePudding user response：

The logic is off. You need to return 0 iff both are present or both are absent. Here's one way to achieve that:

public int compare(String o1, String o2) {
    List<String> list = Arrays.asList(valueStrings);
    boolean found1 = list.contains(o1);
    boolean found2 = list.contains(o2);
    return found1 == found2 ? 0 : found1 ? -1 : 1;
}

Alternatively, you can construct a comparator from a lambda instead of implementing it by hand:

Comparator.comparing(Arrays.asList(valueStrings)::contains).reversed()