Java Priority Queue Compare String to String[]

Question

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

your Comparator is broken, please consult its documentation (e.g. "Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.", "The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y", ...) — user16320675
– user16320675, Commented Nov 20, 2022 at 21:19

Progman · Accepted Answer · 2022-11-20 21:28:24Z

1

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)

answered Nov 20, 2022 at 21:28

Progman

20.1k7 gold badges58 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

efoc Over a year ago

As I was rereading the documentation as per @user16320675 mentioned, I managed to create a working version as well (check new edit). Yours works as well! And you explained it well for me to understand the use case.

shmosel · Accepted Answer · 2022-11-20 21:35:48Z

1

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

answered Nov 20, 2022 at 21:35

shmosel

51k7 gold badges81 silver badges147 bronze badges

2 Comments

efoc Over a year ago

Ah this one is shorter, but I was pretty confused on the return statement, I didn't know you can have two ternary operators in one line.

shmosel Over a year ago

Valid point. It would be best to default to compareTo() instead of 0, as Progman suggested.

Collectives™ on Stack Overflow

Java Priority Queue Compare String to String[]

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related